Blender V5.3
BLI_heap.cc File Reference
#include <algorithm>
#include <cstdlib>
#include "MEM_guardedalloc.h"
#include "BLI_heap.hh"
#include "BLI_utildefines.hh"
#include "BLI_strict_flags.hh"

Go to the source code of this file.

Classes

struct  blender::HeapNode
struct  blender::HeapNode_Chunk
struct  blender::Heap

Namespaces

namespace  blender
 BMesh Iterators.

Macros

#define HEAP_CHUNK_DEFAULT_NUM   uint(MEM_SIZE_OPTIMAL((1 << 16) - sizeof(HeapNode_Chunk)) / sizeof(HeapNode))

Functions

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

Internal Functions

#define HEAP_PARENT(i)
#define HEAP_LEFT(i)
#define HEAP_RIGHT(i)
#define HEAP_COMPARE(a, b)
BLI_INLINE void blender::heap_swap (Heap *heap, const uint i, const uint j)
static void blender::heap_down (Heap *heap, uint i)
static void blender::heap_up (Heap *heap, uint i)

Detailed Description

A min-heap / priority queue ADT.

Definition in file BLI_heap.cc.

Macro Definition Documentation

◆ HEAP_CHUNK_DEFAULT_NUM

#define HEAP_CHUNK_DEFAULT_NUM   uint(MEM_SIZE_OPTIMAL((1 << 16) - sizeof(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 45 of file BLI_heap.cc.

Referenced by blender::BLI_heap_new_ex(), and blender::heap_node_alloc().

◆ HEAP_COMPARE

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

Definition at line 68 of file BLI_heap.cc.

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

◆ HEAP_LEFT

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

Definition at line 66 of file BLI_heap.cc.

Referenced by blender::heap_down(), and blender::heap_is_minheap().

◆ HEAP_PARENT

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

Definition at line 65 of file BLI_heap.cc.

Referenced by blender::BLI_heap_remove(), blender::heap_up(), and blender::heapsimple_up().

◆ HEAP_RIGHT

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

Definition at line 67 of file BLI_heap.cc.

Referenced by blender::heap_down(), and blender::heap_is_minheap().