Blender
V3.3
|
#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_heap.h"
#include "BLI_strict_flags.h"
#include "BLI_utildefines.h"
Go to the source code of this file.
Classes | |
struct | HeapNode |
struct | HeapNode_Chunk |
struct | Heap |
Macros | |
#define | HEAP_CHUNK_DEFAULT_NUM ((uint)((MEM_SIZE_OPTIMAL((1 << 16) - sizeof(struct HeapNode_Chunk))) / sizeof(HeapNode))) |
Internal Functions | |
#define | HEAP_PARENT(i) (((i)-1) >> 1) |
#define | HEAP_LEFT(i) (((i) << 1) + 1) |
#define | HEAP_RIGHT(i) (((i) << 1) + 2) |
#define | HEAP_COMPARE(a, b) ((a)->value < (b)->value) |
BLI_INLINE void | heap_swap (Heap *heap, const uint i, const uint j) |
static void | heap_down (Heap *heap, uint i) |
static void | heap_up (Heap *heap, uint i) |
A min-heap / priority queue ADT.
Definition in file BLI_heap.c.
#define HEAP_CHUNK_DEFAULT_NUM ((uint)((MEM_SIZE_OPTIMAL((1 << 16) - sizeof(struct HeapNode_Chunk))) / sizeof(HeapNode))) |
Number of nodes to include per HeapNode_Chunk when no reserved size is passed, or we allocate past the reserved number.
Definition at line 40 of file BLI_heap.c.
#define HEAP_COMPARE | ( | a, | |
b | |||
) | ((a)->value < (b)->value) |
Definition at line 63 of file BLI_heap.c.
#define HEAP_LEFT | ( | i | ) | (((i) << 1) + 1) |
Definition at line 61 of file BLI_heap.c.
#define HEAP_PARENT | ( | i | ) | (((i)-1) >> 1) |
Definition at line 60 of file BLI_heap.c.
#define HEAP_RIGHT | ( | i | ) | (((i) << 1) + 2) |
Definition at line 62 of file BLI_heap.c.
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().
Definition at line 269 of file BLI_heap.c.
References BLI_heap_insert(), BLI_heap_node_value_update_ptr(), NULL, and ptr.
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().
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().
Definition at line 332 of file BLI_heap.c.
References heap_down(), heap_up(), and node.
Definition at line 344 of file BLI_heap.c.
References heap_down(), heap_up(), node, and ptr.
Referenced by BLI_heap_insert_or_update().
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().
Definition at line 317 of file BLI_heap.c.
References BLI_assert, BLI_heap_pop_min(), HEAP_PARENT, heap_swap(), node, and Heap::size.
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().
Definition at line 92 of file BLI_heap.c.
References HEAP_COMPARE, HEAP_LEFT, HEAP_RIGHT, heap_swap(), l, LIKELY, r, size(), Heap::size, Heap::tree, tree, and UNLIKELY.
Referenced by BLI_heap_node_value_update(), BLI_heap_node_value_update_ptr(), and BLI_heap_pop_min().
Definition at line 367 of file BLI_heap.c.
References HEAP_COMPARE, HEAP_LEFT, HEAP_RIGHT, HeapNode::index, l, r, size(), and Heap::tree.
Referenced by BLI_heap_is_valid().
Definition at line 151 of file BLI_heap.c.
References HeapNode_Chunk::buf, HeapNode_Chunk::bufsize, Heap::chunk, Heap::free, HEAP_CHUNK_DEFAULT_NUM, heap_node_alloc_chunk(), node, Heap::nodes, HeapNode::ptr, HeapNode_Chunk::size, and UNLIKELY.
Referenced by BLI_heap_insert().
|
static |
Definition at line 140 of file BLI_heap.c.
References HeapNode_Chunk::bufsize, MEM_mallocN, HeapNode_Chunk::prev, and HeapNode_Chunk::size.
Referenced by BLI_heap_new_ex(), and heap_node_alloc().
Definition at line 170 of file BLI_heap.c.
References Heap::free, node, and Heap::nodes.
Referenced by BLI_heap_pop_min().
BLI_INLINE void heap_swap | ( | Heap * | heap, |
const uint | i, | ||
const uint | j | ||
) |
Definition at line 69 of file BLI_heap.c.
References HeapNode::index, node, SWAP, SWAP_TVAL, Heap::tree, and tree.
Referenced by BLI_heap_pop_min(), BLI_heap_remove(), heap_down(), and heap_up().
Definition at line 119 of file BLI_heap.c.
References HEAP_COMPARE, HEAP_PARENT, heap_swap(), LIKELY, Heap::tree, and tree.
Referenced by BLI_heap_insert(), BLI_heap_node_value_update(), and BLI_heap_node_value_update_ptr().