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

#include "BLI_compiler_attrs.h"

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 20 of file BLI_heap.h.

◆ HeapFreeFP

typedef void(* HeapFreeFP) (void *ptr)

Definition at line 23 of file BLI_heap.h.

◆ HeapNode

typedef struct HeapNode HeapNode

Definition at line 21 of file BLI_heap.h.

Function Documentation

◆ BLI_heap_clear()

void BLI_heap_clear	(	Heap *	heap,
		HeapFreeFP	ptrfreefp )

Definition at line 214 of file BLI_heap.c.

References Heap::chunk, Heap::free, MEM_freeN(), Heap::nodes, NULL, HeapNode_Chunk::prev, HeapNode::ptr, Heap::size, HeapNode_Chunk::size, and Heap::tree.

Referenced by blender::geometry::PackIsland::add_polygon(), 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 192 of file BLI_heap.c.

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

Referenced by 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(), 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 235 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 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(), 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.

Referenced by 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.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(), 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.c.

References heap_is_minheap().

Referenced by random_heap_reinsert_helper().

◆ BLI_heap_len()

unsigned int BLI_heap_len ( const Heap * heap )

Definition at line 274 of file BLI_heap.c.

References Heap::size.

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

◆ BLI_heap_new()

Heap * BLI_heap_new ( void )

Definition at line 187 of file BLI_heap.c.

References BLI_heap_new_ex().

Referenced by 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 172 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(), 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.c.

References HeapNode::ptr.

Referenced by 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.c.

References HeapNode::value.

Referenced by BM_mesh_decimate_dissolve_ex(), EDBM_select_interior_faces(), and random_heap_reinsert_helper().

◆ 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.

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

◆ BLI_heap_node_value_update_ptr()

void void BLI_heap_node_value_update_ptr	(	Heap *	heap,
		HeapNode *	node,
		float	value,
		void *	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.c.

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

Referenced by 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(), 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 )

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(), 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.c.

References Heap::tree.

Referenced by 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.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().

Typedefs

Functions