BLI_heap.h File Reference

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

#include <stdbool.h>
#include <stddef.h>
#include "BLI_compiler_attrs.h"

Go to the source code of this file.

Typedefs
typedef struct Heap	Heap
typedef struct HeapNode	HeapNode
typedef void(*)	HeapFreeFP(void *ptr)

Functions
Heap *	BLI_heap_new_ex (unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Heap *	BLI_heap_new (void) ATTR_WARN_UNUSED_RESULT
void	BLI_heap_clear (Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
void	BLI_heap_free (Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
HeapNode *	BLI_heap_insert (Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
void	BLI_heap_insert_or_update (Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
void void	BLI_heap_remove (Heap *heap, HeapNode *node) ATTR_NONNULL(1
void void bool	BLI_heap_is_empty (const Heap *heap) ATTR_NONNULL(1)
unsigned int	BLI_heap_len (const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
HeapNode *	BLI_heap_top (const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
float	BLI_heap_top_value (const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void *	BLI_heap_pop_min (Heap *heap) ATTR_NONNULL(1)
void	BLI_heap_node_value_update (Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1
void void	BLI_heap_node_value_update_ptr (Heap *heap, HeapNode *node, float value, void *ptr) ATTR_NONNULL(1
void void float	BLI_heap_node_value (const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void *	BLI_heap_node_ptr (const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
bool	BLI_heap_is_valid (const Heap *heap)

Detailed Description

A min-heap / priority queue ADT.

Definition in file BLI_heap.h.

Typedef Documentation

Heap

typedef struct Heap Heap

Definition at line 19 of file BLI_heap.h.

HeapFreeFP

typedef void(*) HeapFreeFP(void *ptr)

Definition at line 22 of file BLI_heap.h.

HeapNode

typedef struct HeapNode HeapNode

Definition at line 20 of file BLI_heap.h.

Function Documentation

BLI_heap_clear()

void BLI_heap_clear	(	Heap *	heap,
		HeapFreeFP	ptrfreefp )

Definition at line 213 of file BLI_heap.cc.

References BLI_heap_clear(), i, MEM_freeN(), Heap::nodes, HeapNode::ptr, Heap::size, and Heap::tree.

Referenced by blender::geometry::PackIsland::add_polygon(), BLI_heap_clear(), BLI_polyfill_beautify(), bm_face_split_by_concave(), and uv_select_overlap().

BLI_heap_free()

void BLI_heap_free	(	Heap *	heap,
		HeapFreeFP	ptrfreefp )

Definition at line 191 of file BLI_heap.cc.

References BLI_heap_free(), i, MEM_freeN(), Heap::nodes, HeapNode_Chunk::prev, HeapNode::ptr, Heap::size, and Heap::tree.

Referenced by BLI_heap_free(), 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(), bmo_join_triangles_exec(), blender::geometry::ngon::calc_corner_tris(), colorband_init_from_table_rgba_resample(), curve_decimate(), EDBM_select_interior_faces(), blender::geometry::finalize_geometry(), blender::geometry::p_chart_fill_boundary(), blender::geometry::p_chart_simplify_compute(), random_heap_helper(), random_heap_reinsert_helper(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test_polyfill_template(), uv_select_overlap(), uvedit_pack_islands_multi(), and blender::geometry::ParamHandle::~ParamHandle().

BLI_heap_insert()

HeapNode * BLI_heap_insert	(	Heap *	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 234 of file BLI_heap.cc.

References BLI_heap_insert(), Heap::bufsize, heap_node_alloc(), heap_up(), HeapNode::index, MEM_reallocN, HeapNode::ptr, Heap::size, Heap::tree, UNLIKELY, and HeapNode::value.

Referenced by BLI_heap_insert(), 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(), bmo_join_triangles_exec(), colorband_init_from_table_rgba_resample(), EDBM_select_interior_faces(), blender::geometry::p_chart_fill_boundary(), blender::geometry::p_chart_simplify_compute(), random_heap_helper(), random_heap_reinsert_helper(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

BLI_heap_insert_or_update()

void BLI_heap_insert_or_update	(	Heap *	heap,
		HeapNode **	node_p,
		float	value,
		void *	ptr )

Convenience function since this is a common pattern.

References ATTR_NONNULL, and BLI_heap_insert_or_update().

Referenced by BLI_heap_insert_or_update(), BLI_heap_insert_or_update(), bm_decim_build_edge_cost_single(), knot_remove_error_recalculate(), and polyedge_beauty_cost_update_single().

BLI_heap_is_empty()

void void bool BLI_heap_is_empty

(

const Heap *

heap

)

Definition at line 269 of file BLI_heap.cc.

References BLI_heap_is_empty(), and Heap::size.

Referenced by BLI_heap_is_empty(), BLI_heap_remove(), BLI_polyfill_beautify(), BM_mesh_beautify_fill(), BM_mesh_decimate_collapse(), BM_mesh_decimate_dissolve_ex(), bm_rotate_edges_shared(), bmo_join_triangles_exec(), colorband_init_from_table_rgba_resample(), curve_decimate(), EDBM_select_interior_faces(), blender::geometry::p_chart_simplify_compute(), random_heap_helper(), random_heap_reinsert_helper(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

BLI_heap_is_valid()

bool BLI_heap_is_valid

(

const Heap *

heap

)

Only for checking internal errors (gtest).

Definition at line 378 of file BLI_heap.cc.

References BLI_heap_is_valid(), and heap_is_minheap().

Referenced by BLI_heap_is_valid(), BLI_heap_node_value_update_ptr(), and random_heap_reinsert_helper().

BLI_heap_len()

unsigned int BLI_heap_len

(

const Heap *

heap

)

Definition at line 274 of file BLI_heap.cc.

References BLI_heap_len(), and Heap::size.

Referenced by BLI_heap_len(), BLI_heap_remove(), blender::geometry::PackIsland::finalize_geometry_(), TEST(), and TEST().

BLI_heap_new()

Heap * BLI_heap_new

(

void

)

Definition at line 186 of file BLI_heap.cc.

References BLI_heap_new(), and BLI_heap_new_ex().

Referenced by BLI_heap_new(), bmo_join_triangles_exec(), blender::geometry::finalize_geometry(), blender::geometry::p_chart_fill_boundary(), blender::geometry::p_chart_simplify_compute(), random_heap_helper(), random_heap_reinsert_helper(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and uvedit_pack_islands_multi().

BLI_heap_new_ex()

Heap * BLI_heap_new_ex

(

unsigned int

reserve_num

)

Creates a new heap. Removed nodes are recycled, so memory usage will not shrink.

Note

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

Definition at line 171 of file BLI_heap.cc.

References BLI_heap_new_ex(), Heap::bufsize, HEAP_CHUNK_DEFAULT_NUM, heap_node_alloc_chunk(), MEM_calloc_arrayN(), MEM_callocN(), Heap::nodes, Heap::size, and Heap::tree.

Referenced by BLI_heap_new(), BLI_heap_new_ex(), 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(), blender::geometry::ngon::calc_corner_tris(), colorband_init_from_table_rgba_resample(), curve_decimate(), EDBM_select_interior_faces(), blender::geometry::ParamHandle::ParamHandle(), test_polyfill_template(), and uv_select_overlap().

BLI_heap_node_ptr()

void * BLI_heap_node_ptr

(

const HeapNode *

heap

)

Definition at line 352 of file BLI_heap.cc.

References BLI_heap_node_ptr(), and HeapNode::ptr.

Referenced by BLI_heap_node_ptr(), BLI_heap_node_value_update_ptr(), BM_mesh_decimate_collapse(), BM_mesh_decimate_dissolve_ex(), EDBM_select_interior_faces(), and knot_remove_error_recalculate().

BLI_heap_node_value()

void void float BLI_heap_node_value

(

const HeapNode *

heap

)

Return the value or pointer of a heap node.

Definition at line 347 of file BLI_heap.cc.

References BLI_heap_node_value(), and HeapNode::value.

Referenced by BLI_heap_node_value(), BLI_heap_node_value_update_ptr(), BM_mesh_decimate_dissolve_ex(), EDBM_select_interior_faces(), random_heap_reinsert_helper(), and reprioritize_join().

BLI_heap_node_value_update()

void BLI_heap_node_value_update	(	Heap *	heap,
		HeapNode *	node,
		float	value )

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.

References ATTR_NONNULL, and BLI_heap_node_value_update().

Referenced by BLI_heap_node_value_update(), BLI_heap_node_value_update(), BM_mesh_decimate_dissolve_ex(), colorband_init_from_table_rgba_resample(), EDBM_select_interior_faces(), random_heap_reinsert_helper(), reprioritize_join(), and TEST().

BLI_heap_node_value_update_ptr()

void void BLI_heap_node_value_update_ptr	(	Heap *	heap,
		HeapNode *	node,
		float	value,
		void *	ptr )

References ATTR_NONNULL, ATTR_WARN_UNUSED_RESULT, BLI_heap_is_valid(), BLI_heap_node_ptr(), BLI_heap_node_value(), and BLI_heap_node_value_update_ptr().

Referenced by BLI_heap_insert_or_update(), BLI_heap_node_value_update_ptr(), and BLI_heap_node_value_update_ptr().

BLI_heap_pop_min()

void * BLI_heap_pop_min

(

Heap *

heap

)

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

Definition at line 291 of file BLI_heap.cc.

References BLI_assert, BLI_heap_pop_min(), heap_down(), heap_node_free(), heap_swap(), HeapNode::ptr, Heap::size, and Heap::tree.

Referenced by BLI_heap_pop_min(), BLI_heap_remove(), BLI_heap_remove(), BLI_polyfill_beautify(), BM_mesh_beautify_fill(), BM_mesh_decimate_collapse(), bm_rotate_edges_shared(), bmo_join_triangles_exec(), colorband_init_from_table_rgba_resample(), curve_decimate(), EDBM_select_interior_faces(), blender::geometry::p_chart_fill_boundary(), blender::geometry::p_chart_simplify_compute(), random_heap_helper(), random_heap_reinsert_helper(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

BLI_heap_remove()

void void BLI_heap_remove	(	Heap *	heap,
		HeapNode *	node )

References ATTR_NONNULL, ATTR_WARN_UNUSED_RESULT, BLI_heap_is_empty(), BLI_heap_len(), BLI_heap_pop_min(), BLI_heap_remove(), BLI_heap_top(), and BLI_heap_top_value().

Referenced by BLI_heap_remove(), BLI_heap_remove(), 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(), blender::geometry::p_chart_fill_boundary(), blender::geometry::p_chart_simplify_compute(), polyedge_beauty_cost_update_single(), and TEST().

BLI_heap_top()

HeapNode * BLI_heap_top

(

const Heap *

heap

)

Return the top node of the heap. This is the node with the lowest value.

Definition at line 279 of file BLI_heap.cc.

References BLI_heap_top(), and Heap::tree.

Referenced by BLI_heap_remove(), BLI_heap_top(), BM_mesh_decimate_dissolve_ex(), EDBM_select_interior_faces(), blender::geometry::p_chart_simplify_compute(), and random_heap_reinsert_helper().

BLI_heap_top_value()

float BLI_heap_top_value

(

const Heap *

heap

)

Return the value of top node of the heap. This is the node with the lowest value.

Definition at line 284 of file BLI_heap.cc.

References BLI_assert, BLI_heap_top_value(), Heap::size, Heap::tree, and HeapNode::value.

Referenced by BLI_heap_remove(), BLI_heap_top_value(), BM_mesh_decimate_collapse(), bmo_join_triangles_exec(), colorband_init_from_table_rgba_resample(), and random_heap_reinsert_helper().