BLI_heap.c File Reference

#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_heap.h"
#include "BLI_utildefines.h"
#include "BLI_strict_flags.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))

Functions
Internal Memory Management
static struct HeapNode_Chunk *	heap_node_alloc_chunk (uint nodes_num, struct HeapNode_Chunk *chunk_prev)
static HeapNode *	heap_node_alloc (Heap *heap)
static void	heap_node_free (Heap *heap, HeapNode *node)
Public Heap API
Heap *	BLI_heap_new_ex (uint reserve_num)
Heap *	BLI_heap_new (void)
void	BLI_heap_free (Heap *heap, HeapFreeFP ptrfreefp)
void	BLI_heap_clear (Heap *heap, HeapFreeFP ptrfreefp)
HeapNode *	BLI_heap_insert (Heap *heap, float value, void *ptr)
void	BLI_heap_insert_or_update (Heap *heap, HeapNode **node_p, float value, void *ptr)
bool	BLI_heap_is_empty (const Heap *heap)
uint	BLI_heap_len (const Heap *heap)
HeapNode *	BLI_heap_top (const Heap *heap)
float	BLI_heap_top_value (const Heap *heap)
void *	BLI_heap_pop_min (Heap *heap)
void	BLI_heap_remove (Heap *heap, HeapNode *node)
void	BLI_heap_node_value_update (Heap *heap, HeapNode *node, float value)
void	BLI_heap_node_value_update_ptr (Heap *heap, HeapNode *node, float value, void *ptr)
float	BLI_heap_node_value (const HeapNode *heap)
void *	BLI_heap_node_ptr (const HeapNode *heap)
static bool	heap_is_minheap (const Heap *heap, uint root)
bool	BLI_heap_is_valid (const Heap *heap)

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)

Detailed Description

A min-heap / priority queue ADT.

Definition in file BLI_heap.c.

Macro Definition Documentation

HEAP_CHUNK_DEFAULT_NUM

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

Note

Optimize number for 64kb allocations.

keep type in sync with nodes_num in heap_node_alloc_chunk.

Definition at line 43 of file BLI_heap.c.

Referenced by BLI_heap_new_ex(), and heap_node_alloc().

HEAP_COMPARE

#define HEAP_COMPARE	(		a,
			b )   ((a)->value < (b)->value)

Definition at line 66 of file BLI_heap.c.

Referenced by heap_down(), heap_is_minheap(), and heap_up().

HEAP_LEFT

#define HEAP_LEFT

(

i

)

(((i) << 1) + 1)

Definition at line 64 of file BLI_heap.c.

Referenced by heap_down(), and heap_is_minheap().

HEAP_PARENT

#define HEAP_PARENT

(

i

)

(((i)-1) >> 1)

Definition at line 63 of file BLI_heap.c.

Referenced by BLI_heap_remove(), and heap_up().

HEAP_RIGHT

#define HEAP_RIGHT

(

i

)

(((i) << 1) + 2)

Definition at line 65 of file BLI_heap.c.

Referenced by heap_down(), and heap_is_minheap().

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 )

Definition at line 259 of file BLI_heap.c.

References BLI_heap_insert(), BLI_heap_node_value_update_ptr(), NULL, and ptr.

BLI_heap_is_empty()

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

uint 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()

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 )

Definition at line 322 of file BLI_heap.c.

References heap_down(), and heap_up().

BLI_heap_node_value_update_ptr()

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

Definition at line 334 of file BLI_heap.c.

References heap_down(), heap_up(), and ptr.

Referenced by BLI_heap_insert_or_update().

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 BLI_heap_remove	(	Heap *	heap,
		HeapNode *	node )

Definition at line 307 of file BLI_heap.c.

References BLI_assert, BLI_heap_pop_min(), HEAP_PARENT, heap_swap(), and Heap::size.

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

heap_down()

static void heap_down ( Heap * heap, uint i )

static

Definition at line 82 of file BLI_heap.c.

References HEAP_COMPARE, HEAP_LEFT, HEAP_RIGHT, heap_swap(), l, LIKELY, 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().

heap_is_minheap()

static bool heap_is_minheap ( const Heap * heap, uint root )

static

Definition at line 357 of file BLI_heap.c.

References HEAP_COMPARE, heap_is_minheap(), HEAP_LEFT, HEAP_RIGHT, HeapNode::index, l, and Heap::tree.

Referenced by BLI_heap_is_valid(), and heap_is_minheap().

heap_node_alloc()

static HeapNode * heap_node_alloc ( Heap * heap )

static

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

heap_node_alloc_chunk()

static struct HeapNode_Chunk * heap_node_alloc_chunk ( uint nodes_num, struct HeapNode_Chunk * chunk_prev )

static

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

heap_node_free()

static void heap_node_free ( Heap * heap, HeapNode * node )

static

Definition at line 160 of file BLI_heap.c.

References Heap::free, node, Heap::nodes, and HeapNode::ptr.

Referenced by BLI_heap_pop_min().

heap_swap()

BLI_INLINE void heap_swap	(	Heap *	heap,
		const uint	i,
		const uint	j )

Definition at line 72 of file BLI_heap.c.

References Heap::tree, and tree.

Referenced by BLI_heap_pop_min(), BLI_heap_remove(), heap_down(), and heap_up().

heap_up()

static void heap_up ( Heap * heap, uint i )

static

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