Blender  V3.3
Typedefs | Functions
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

HeapBLI_heap_new_ex (unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
 
HeapBLI_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)
 
HeapNodeBLI_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)
 
HeapNodeBLI_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)
 
voidBLI_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)
 
voidBLI_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 21 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 
)

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

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)

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

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

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

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)

◆ BLI_heap_remove()

void void BLI_heap_remove ( Heap heap,
HeapNode node 
)

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