Blender
V3.3
|
A min-heap / priority queue ADT. More...
#include "BLI_math.h"
Go to the source code of this file.
Typedefs | |
typedef struct Heap | Heap |
typedef struct HeapNode | HeapNode |
typedef void(* | HeapFreeFP) (void *ptr) |
A min-heap / priority queue ADT.
Definition in file BLI_heap.h.
Definition at line 1 of file BLI_heap.h.
Definition at line 21 of file BLI_heap.h.
Definition at line 1 of file BLI_heap.h.
void BLI_heap_clear | ( | Heap * | heap, |
HeapFreeFP | ptrfreefp | ||
) |
Definition at line 224 of file BLI_heap.c.
References Heap::chunk, Heap::free, MEM_freeN, Heap::nodes, NULL, HeapNode_Chunk::prev, HeapNode::ptr, HeapNode_Chunk::size, Heap::size, and Heap::tree.
Referenced by BLI_polyfill_beautify(), and bm_face_split_by_concave().
void BLI_heap_free | ( | Heap * | heap, |
HeapFreeFP | ptrfreefp | ||
) |
Definition at line 202 of file BLI_heap.c.
References Heap::chunk, MEM_freeN, Heap::nodes, HeapNode_Chunk::prev, HeapNode::ptr, Heap::size, and Heap::tree.
Referenced by BKE_gpencil_stroke_uniform_subdivide(), bm_decim_triangulate_begin(), BM_mesh_beautify_fill(), BM_mesh_calc_tessellation_beauty(), BM_mesh_decimate_collapse(), BM_mesh_decimate_dissolve_ex(), BM_mesh_triangulate(), bm_rotate_edges_shared(), bmo_connect_verts_concave_exec(), colorband_init_from_table_rgba_resample(), curve_decimate(), EDBM_select_interior_faces(), GEO_uv_parametrizer_delete(), p_chart_fill_boundary(), random_heap_helper(), random_heap_reinsert_helper(), TEST(), and test_polyfill_template().
Insert heap node with a value (often a 'cost') and pointer into the heap, duplicate values are allowed.
Definition at line 245 of file BLI_heap.c.
References Heap::bufsize, heap_node_alloc(), heap_up(), MEM_reallocN, node, ptr, Heap::size, Heap::tree, and UNLIKELY.
Referenced by BKE_gpencil_stroke_uniform_subdivide(), BLI_heap_insert_or_update(), BLI_polyfill_beautify(), bm_decim_invalid_edge_cost_single(), bm_edge_update_beauty_cost_single(), BM_mesh_beautify_fill(), BM_mesh_decimate_dissolve_ex(), bm_rotate_edges_shared(), colorband_init_from_table_rgba_resample(), EDBM_select_interior_faces(), p_chart_fill_boundary(), random_heap_helper(), random_heap_reinsert_helper(), and TEST().
Convenience function since this is a common pattern.
Referenced by bm_decim_build_edge_cost_single(), knot_remove_error_recalculate(), and polyedge_beauty_cost_update_single().
Definition at line 279 of file BLI_heap.c.
References Heap::size.
Referenced by BLI_polyfill_beautify(), BM_mesh_beautify_fill(), BM_mesh_decimate_collapse(), BM_mesh_decimate_dissolve_ex(), bm_rotate_edges_shared(), colorband_init_from_table_rgba_resample(), curve_decimate(), EDBM_select_interior_faces(), random_heap_helper(), random_heap_reinsert_helper(), and TEST().
Only for checking internal errors (gtest).
Definition at line 388 of file BLI_heap.c.
References heap_is_minheap().
Referenced by random_heap_reinsert_helper().
unsigned int BLI_heap_len | ( | const Heap * | heap | ) |
Definition at line 197 of file BLI_heap.c.
References BLI_heap_new_ex().
Referenced by BKE_gpencil_stroke_uniform_subdivide(), p_chart_fill_boundary(), random_heap_helper(), random_heap_reinsert_helper(), and TEST().
Heap* BLI_heap_new_ex | ( | unsigned int | reserve_num | ) |
Creates a new heap. Removed nodes are recycled, so memory usage will not shrink.
Definition at line 182 of file BLI_heap.c.
References Heap::bufsize, Heap::chunk, Heap::free, HEAP_CHUNK_DEFAULT_NUM, heap_node_alloc_chunk(), MAX2, MEM_mallocN, Heap::nodes, NULL, Heap::size, and Heap::tree.
Referenced by BLI_heap_new(), bm_decim_triangulate_begin(), BM_mesh_beautify_fill(), BM_mesh_decimate_collapse(), BM_mesh_decimate_dissolve_ex(), BM_mesh_triangulate(), bm_rotate_edges_shared(), bmesh_calc_tessellation_for_face_beauty(), bmo_connect_verts_concave_exec(), colorband_init_from_table_rgba_resample(), curve_decimate(), EDBM_select_interior_faces(), GEO_uv_parametrizer_construct_begin(), and test_polyfill_template().
Definition at line 362 of file BLI_heap.c.
References HeapNode::ptr.
Referenced by BM_mesh_decimate_collapse(), BM_mesh_decimate_dissolve_ex(), EDBM_select_interior_faces(), and knot_remove_error_recalculate().
Return the value or pointer of a heap node.
Definition at line 357 of file BLI_heap.c.
References HeapNode::value.
Referenced by BM_mesh_decimate_dissolve_ex(), EDBM_select_interior_faces(), and random_heap_reinsert_helper().
Can be used to avoid BLI_heap_remove, BLI_heap_insert calls, balancing the tree still has a performance cost, but is often much less than remove/insert, difference is most noticeable with large heaps.
Referenced by BM_mesh_decimate_dissolve_ex(), colorband_init_from_table_rgba_resample(), EDBM_select_interior_faces(), random_heap_reinsert_helper(), and TEST().
Pop the top node off the heap and return its pointer.
Definition at line 301 of file BLI_heap.c.
References BLI_assert, heap_down(), heap_node_free(), heap_swap(), HeapNode::ptr, ptr, Heap::size, and Heap::tree.
Referenced by BKE_gpencil_stroke_uniform_subdivide(), BLI_heap_remove(), BLI_polyfill_beautify(), BM_mesh_beautify_fill(), BM_mesh_decimate_collapse(), bm_rotate_edges_shared(), colorband_init_from_table_rgba_resample(), curve_decimate(), EDBM_select_interior_faces(), p_chart_fill_boundary(), random_heap_helper(), random_heap_reinsert_helper(), and TEST().
Referenced by bm_decim_build_edge_cost_single(), bm_decim_edge_collapse(), bm_edge_update_beauty_cost_single(), BM_mesh_decimate_collapse(), BM_mesh_decimate_dissolve_ex(), colorband_init_from_table_rgba_resample(), EDBM_select_interior_faces(), knot_remove_error_recalculate(), p_chart_fill_boundary(), polyedge_beauty_cost_update_single(), and TEST().
Return the top node of the heap. This is the node with the lowest value.
Definition at line 289 of file BLI_heap.c.
References Heap::tree.
Referenced by BM_mesh_decimate_dissolve_ex(), EDBM_select_interior_faces(), and random_heap_reinsert_helper().
Return the value of top node of the heap. This is the node with the lowest value.
Definition at line 294 of file BLI_heap.c.
References BLI_assert, Heap::size, Heap::tree, and HeapNode::value.
Referenced by BM_mesh_decimate_collapse(), colorband_init_from_table_rgba_resample(), and random_heap_reinsert_helper().