Blender  V3.3
Classes | Macros
BLI_heap.c File Reference
#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_heap.h"
#include "BLI_strict_flags.h"
#include "BLI_utildefines.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_Chunkheap_node_alloc_chunk (uint nodes_num, struct HeapNode_Chunk *chunk_prev)
 
static struct HeapNodeheap_node_alloc (Heap *heap)
 
static void heap_node_free (Heap *heap, HeapNode *node)
 
Public Heap API
HeapBLI_heap_new_ex (uint reserve_num)
 
HeapBLI_heap_new (void)
 
void BLI_heap_free (Heap *heap, HeapFreeFP ptrfreefp)
 
void BLI_heap_clear (Heap *heap, HeapFreeFP ptrfreefp)
 
HeapNodeBLI_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)
 
HeapNodeBLI_heap_top (const Heap *heap)
 
float BLI_heap_top_value (const Heap *heap)
 
voidBLI_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)
 
voidBLI_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 allocs.
keep type in sync with nodes_num in heap_node_alloc_chunk.

Definition at line 40 of file BLI_heap.c.

◆ HEAP_COMPARE

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

Definition at line 63 of file BLI_heap.c.

◆ HEAP_LEFT

#define HEAP_LEFT (   i)    (((i) << 1) + 1)

Definition at line 61 of file BLI_heap.c.

◆ HEAP_PARENT

#define HEAP_PARENT (   i)    (((i)-1) >> 1)

Definition at line 60 of file BLI_heap.c.

◆ HEAP_RIGHT

#define HEAP_RIGHT (   i)    (((i) << 1) + 2)

Definition at line 62 of file BLI_heap.c.

Function Documentation

◆ BLI_heap_clear()

void BLI_heap_clear ( Heap heap,
HeapFreeFP  ptrfreefp 
)

◆ BLI_heap_free()

void BLI_heap_free ( Heap heap,
HeapFreeFP  ptrfreefp 
)

◆ BLI_heap_insert()

HeapNode* BLI_heap_insert ( Heap heap,
float  value,
void ptr 
)

◆ BLI_heap_insert_or_update()

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

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

◆ BLI_heap_is_valid()

bool BLI_heap_is_valid ( const Heap heap)

Only for checking internal errors (gtest).

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

References Heap::size.

Referenced by TEST().

◆ BLI_heap_new()

Heap* BLI_heap_new ( void  )

◆ BLI_heap_new_ex()

Heap* BLI_heap_new_ex ( unsigned int  reserve_num)

◆ BLI_heap_node_ptr()

void* BLI_heap_node_ptr ( const HeapNode heap)

◆ BLI_heap_node_value()

float BLI_heap_node_value ( const HeapNode heap)

Return the value or pointer of a heap node.

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

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

◆ BLI_heap_node_value_update_ptr()

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

Definition at line 344 of file BLI_heap.c.

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

Referenced by BLI_heap_insert_or_update().

◆ BLI_heap_pop_min()

void* BLI_heap_pop_min ( Heap heap)

◆ BLI_heap_remove()

void BLI_heap_remove ( Heap heap,
HeapNode node 
)

Definition at line 317 of file BLI_heap.c.

References BLI_assert, BLI_heap_pop_min(), HEAP_PARENT, heap_swap(), node, 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 289 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 294 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

◆ heap_is_minheap()

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

Definition at line 367 of file BLI_heap.c.

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

Referenced by BLI_heap_is_valid().

◆ heap_node_alloc()

static struct HeapNode* heap_node_alloc ( Heap heap)
static

◆ heap_node_alloc_chunk()

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

◆ heap_node_free()

static void heap_node_free ( Heap heap,
HeapNode node 
)
static

Definition at line 170 of file BLI_heap.c.

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

Referenced by BLI_heap_pop_min().

◆ heap_swap()

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

Definition at line 69 of file BLI_heap.c.

References HeapNode::index, node, SWAP, SWAP_TVAL, 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