BLI_heap_simple.h File Reference

A min-heap / priority queue ADT. More...

Go to the source code of this file.

Typedefs
typedef struct HeapSimple	HeapSimple
typedef void(*	HeapSimpleFreeFP) (void *ptr)

Functions
HeapSimple *	BLI_heapsimple_new_ex (unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
HeapSimple *	BLI_heapsimple_new (void) ATTR_WARN_UNUSED_RESULT
void	BLI_heapsimple_clear (HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
void	BLI_heapsimple_free (HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
void	BLI_heapsimple_insert (HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
bool	BLI_heapsimple_is_empty (const HeapSimple *heap) ATTR_NONNULL(1)
uint	BLI_heapsimple_len (const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
float	BLI_heapsimple_top_value (const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void *	BLI_heapsimple_pop_min (HeapSimple *heap) ATTR_NONNULL(1)

Detailed Description

A min-heap / priority queue ADT.

Definition in file BLI_heap_simple.h.

Typedef Documentation

HeapSimple

typedef struct HeapSimple HeapSimple

Definition at line 17 of file BLI_heap_simple.h.

HeapSimpleFreeFP

typedef void(* HeapSimpleFreeFP) (void *ptr)

Definition at line 19 of file BLI_heap_simple.h.

Function Documentation

BLI_heapsimple_clear()

void BLI_heapsimple_clear	(	HeapSimple *	heap,
		HeapSimpleFreeFP	ptrfreefp )

Definition at line 166 of file BLI_heap_simple.c.

References HeapSimpleNode::ptr, HeapSimple::size, and HeapSimple::tree.

Referenced by bmo_connect_vert_pair_exec().

BLI_heapsimple_free()

void BLI_heapsimple_free	(	HeapSimple *	heap,
		HeapSimpleFreeFP	ptrfreefp )

Definition at line 154 of file BLI_heap_simple.c.

References MEM_freeN(), HeapSimpleNode::ptr, HeapSimple::size, and HeapSimple::tree.

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), blender::bke::pbvh::bmesh_update_topology(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), heap_find_nearest_begin(), hull_merge_triangles(), random_heapsimple_helper(), TEST(), TEST(), TEST(), TEST(), and TEST().

BLI_heapsimple_insert()

void BLI_heapsimple_insert	(	HeapSimple *	heap,
		float	value,
		void *	ptr )

Insert heap node with a value (often a 'cost') and pointer into the heap, duplicate values are allowed.

Definition at line 177 of file BLI_heap_simple.c.

References HeapSimple::bufsize, heapsimple_up(), MEM_reallocN, ptr, HeapSimple::size, HeapSimple::tree, and UNLIKELY.

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), blender::bke::pbvh::edge_queue_insert(), edgetag_add_adjacent(), edgetag_add_adjacent_uv(), facetag_add_adjacent(), facetag_add_adjacent_uv(), heap_find_nearest_inner(), hull_merge_triangles(), random_heapsimple_helper(), state_link_add_test(), TEST(), TEST(), TEST(), TEST(), verttag_add_adjacent(), and verttag_add_adjacent_uv().

BLI_heapsimple_is_empty()

bool BLI_heapsimple_is_empty

(

const HeapSimple *

heap

)

Definition at line 187 of file BLI_heap_simple.c.

References HeapSimple::size.

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), heap_find_nearest_begin(), hull_merge_triangles(), blender::bke::pbvh::pbvh_bmesh_collapse_short_edges(), blender::bke::pbvh::pbvh_bmesh_subdivide_long_edges(), random_heapsimple_helper(), TEST(), TEST(), TEST(), TEST(), and TEST().

BLI_heapsimple_len()

uint BLI_heapsimple_len

(

const HeapSimple *

heap

)

Definition at line 192 of file BLI_heap_simple.c.

References HeapSimple::size.

Referenced by bmo_connect_vert_pair_exec(), TEST(), and TEST().

BLI_heapsimple_new()

HeapSimple * BLI_heapsimple_new

(

void

)

Definition at line 149 of file BLI_heap_simple.c.

References BLI_heapsimple_new_ex().

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), hull_merge_triangles(), blender::bke::pbvh::long_edge_queue_create(), random_heapsimple_helper(), blender::bke::pbvh::short_edge_queue_create(), TEST(), TEST(), TEST(), TEST(), and TEST().

BLI_heapsimple_new_ex()

HeapSimple * BLI_heapsimple_new_ex

(

unsigned int

reserve_num

)

Creates a new simple heap, which only supports insertion and removal from top.

Note

Use when the size of the heap is known in advance.

Definition at line 139 of file BLI_heap_simple.c.

References HeapSimple::bufsize, MAX2, MEM_mallocN, HeapSimple::size, and HeapSimple::tree.

Referenced by BLI_heapsimple_new(), and heap_find_nearest_begin().

BLI_heapsimple_pop_min()

void * BLI_heapsimple_pop_min

(

HeapSimple *

heap

)

Pop the top node off the heap and return its pointer.

Definition at line 204 of file BLI_heap_simple.c.

References BLI_assert, heapsimple_down(), HeapSimpleNode::ptr, ptr, HeapSimple::size, and HeapSimple::tree.

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), heap_find_nearest_begin(), hull_merge_triangles(), blender::bke::pbvh::pbvh_bmesh_collapse_short_edges(), blender::bke::pbvh::pbvh_bmesh_subdivide_long_edges(), random_heapsimple_helper(), TEST(), TEST(), TEST(), and TEST().

BLI_heapsimple_top_value()

float BLI_heapsimple_top_value

(

const HeapSimple *

heap

)

Return the lowest value of the heap.

Definition at line 197 of file BLI_heap_simple.c.

References BLI_assert, HeapSimple::size, HeapSimple::tree, and HeapSimpleNode::value.

Referenced by edbm_average_normals_exec(), and heap_find_nearest_begin().