Blender
V3.3
|
#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_heap_simple.h"
#include "BLI_strict_flags.h"
#include "BLI_utildefines.h"
Go to the source code of this file.
Classes | |
struct | HeapSimpleNode |
struct | HeapSimple |
Macros | |
#define | HEAP_PARENT(i) (((i)-1) >> 1) |
#define | OFFSET(i) (i * (uint)sizeof(HeapSimpleNode)) |
#define | NODE(offset) (*(HeapSimpleNode *)(tree_buf + (offset))) |
#define | HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1)) |
Typedefs | |
HeapSimple Internal Structs | |
typedef struct HeapSimpleNode | HeapSimpleNode |
Functions | |
HeapSimple Internal Functions | |
static void | heapsimple_down (HeapSimple *heap, uint start_i, const HeapSimpleNode *init) |
static void | heapsimple_up (HeapSimple *heap, uint i, float active_val, void *active_ptr) |
Public HeapSimple API | |
HeapSimple * | BLI_heapsimple_new_ex (uint reserve_num) |
HeapSimple * | BLI_heapsimple_new (void) |
void | BLI_heapsimple_free (HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) |
void | BLI_heapsimple_clear (HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) |
void | BLI_heapsimple_insert (HeapSimple *heap, float value, void *ptr) |
bool | BLI_heapsimple_is_empty (const HeapSimple *heap) |
uint | BLI_heapsimple_len (const HeapSimple *heap) |
float | BLI_heapsimple_top_value (const HeapSimple *heap) |
void * | BLI_heapsimple_pop_min (HeapSimple *heap) |
A min-heap / priority queue ADT.
Simplified version of the heap that only supports insertion and removal from top.
See BLI_heap.c for a more full featured heap implementation.
Definition in file BLI_heap_simple.c.
#define HEAP_PARENT | ( | i | ) | (((i)-1) >> 1) |
Definition at line 22 of file BLI_heap_simple.c.
#define NODE | ( | offset | ) | (*(HeapSimpleNode *)(tree_buf + (offset))) |
#define OFFSET | ( | i | ) | (i * (uint)sizeof(HeapSimpleNode)) |
typedef struct HeapSimpleNode HeapSimpleNode |
void BLI_heapsimple_clear | ( | HeapSimple * | heap, |
HeapSimpleFreeFP | ptrfreefp | ||
) |
Definition at line 163 of file BLI_heap_simple.c.
References HeapSimpleNode::ptr, HeapSimple::size, and HeapSimple::tree.
Referenced by bmo_connect_vert_pair_exec().
void BLI_heapsimple_free | ( | HeapSimple * | heap, |
HeapSimpleFreeFP | ptrfreefp | ||
) |
Definition at line 151 of file BLI_heap_simple.c.
References MEM_freeN, HeapSimpleNode::ptr, HeapSimple::size, and HeapSimple::tree.
Referenced by BKE_pbvh_bmesh_update_topology(), 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(), random_heapsimple_helper(), and TEST().
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 174 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(), 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(), verttag_add_adjacent(), and verttag_add_adjacent_uv().
bool BLI_heapsimple_is_empty | ( | const HeapSimple * | heap | ) |
Definition at line 184 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(), pbvh_bmesh_collapse_short_edges(), pbvh_bmesh_subdivide_long_edges(), random_heapsimple_helper(), and TEST().
uint BLI_heapsimple_len | ( | const HeapSimple * | heap | ) |
Definition at line 189 of file BLI_heap_simple.c.
References HeapSimple::size.
Referenced by bmo_connect_vert_pair_exec(), and TEST().
HeapSimple* BLI_heapsimple_new | ( | void | ) |
Definition at line 146 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(), long_edge_queue_create(), random_heapsimple_helper(), short_edge_queue_create(), and TEST().
HeapSimple* BLI_heapsimple_new_ex | ( | unsigned int | reserve_num | ) |
Creates a new simple heap, which only supports insertion and removal from top.
Definition at line 136 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().
void* BLI_heapsimple_pop_min | ( | HeapSimple * | heap | ) |
Pop the top node off the heap and return its pointer.
Definition at line 201 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(), pbvh_bmesh_collapse_short_edges(), pbvh_bmesh_subdivide_long_edges(), random_heapsimple_helper(), and TEST().
float BLI_heapsimple_top_value | ( | const HeapSimple * | heap | ) |
Return the lowest value of the heap.
Definition at line 194 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().
|
static |
Definition at line 45 of file BLI_heap_simple.c.
References define(), HEAP_LEFT_OFFSET, init, l, LIKELY, NODE, offset, OFFSET, r, size(), HeapSimple::size, HeapSimple::tree, tree, and UNLIKELY.
Referenced by BLI_heapsimple_pop_min().
|
static |
Definition at line 111 of file BLI_heap_simple.c.
References HEAP_PARENT, LIKELY, HeapSimple::tree, and tree.
Referenced by BLI_heapsimple_insert().