BLI_heap.h File Reference

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)

Functions
Heap *	BLI_heap_new_ex (unsigned int tot_reserve) 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 1 of file BLI_heap.h.

HeapFreeFP

typedef void(* HeapFreeFP) (void *ptr)

Definition at line 35 of file BLI_heap.h.

HeapNode

typedef struct HeapNode HeapNode

Definition at line 1 of file BLI_heap.h.

Function Documentation

BLI_heap_clear()

void BLI_heap_clear	(	Heap *	heap,
		HeapFreeFP	ptrfreefp
	)

Definition at line 243 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().

BLI_heap_free()

void BLI_heap_free	(	Heap *	heap,
		HeapFreeFP	ptrfreefp
	)

Definition at line 221 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(), p_chart_fill_boundary(), param_delete(), random_heap_helper(), random_heap_reinsert_helper(), TEST(), and test_polyfill_template().

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 268 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().

BLI_heap_insert_or_update()

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

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 305 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().

BLI_heap_is_valid()

bool BLI_heap_is_valid

(

const Heap *

heap

)

Only for checking internal errors (gtest).

Definition at line 433 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 310 of file BLI_heap.c.

References Heap::size.

Referenced by TEST().

BLI_heap_new()

Heap* BLI_heap_new

(

void

)

Definition at line 216 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().

BLI_heap_new_ex()

Heap* BLI_heap_new_ex

(

uint

tot_reserve

)

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 201 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_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(), param_construct_begin(), and test_polyfill_template().

BLI_heap_node_ptr()

void* BLI_heap_node_ptr

(

const HeapNode *

heap

)

Definition at line 404 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

)

Definition at line 399 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
	)

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 338 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().

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(), p_chart_fill_boundary(), 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 319 of file BLI_heap.c.

References Heap::tree.

Referenced by BM_mesh_decimate_dissolve_ex(), EDBM_select_interior_faces(), 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 328 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().