Blender  V3.3
Classes | Macros
BLI_heap_simple.c File Reference
#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_heap_simple.h"
#include "BLI_strict_flags.h"
#include "BLI_utildefines.h"

Go to the source code of this file.

Classes

struct  HeapSimpleNode
 
struct  HeapSimple
 

Macros

#define HEAP_PARENT(i)   (((i)-1) >> 1)
 
#define OFFSET(i)   (i * (uint)sizeof(HeapSimpleNode))
 
#define NODE(offset)   (*(HeapSimpleNode *)(tree_buf + (offset)))
 
#define HEAP_LEFT_OFFSET(i)   (((i) << 1) + OFFSET(1))
 

Typedefs

HeapSimple Internal Structs
typedef struct HeapSimpleNode HeapSimpleNode
 

Functions

HeapSimple Internal Functions
static void heapsimple_down (HeapSimple *heap, uint start_i, const HeapSimpleNode *init)
 
static void heapsimple_up (HeapSimple *heap, uint i, float active_val, void *active_ptr)
 
Public HeapSimple API
HeapSimpleBLI_heapsimple_new_ex (uint reserve_num)
 
HeapSimpleBLI_heapsimple_new (void)
 
void BLI_heapsimple_free (HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
 
void BLI_heapsimple_clear (HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
 
void BLI_heapsimple_insert (HeapSimple *heap, float value, void *ptr)
 
bool BLI_heapsimple_is_empty (const HeapSimple *heap)
 
uint BLI_heapsimple_len (const HeapSimple *heap)
 
float BLI_heapsimple_top_value (const HeapSimple *heap)
 
voidBLI_heapsimple_pop_min (HeapSimple *heap)
 

Detailed Description

A min-heap / priority queue ADT.

Simplified version of the heap that only supports insertion and removal from top.

See BLI_heap.c for a more full featured heap implementation.

Definition in file BLI_heap_simple.c.

Macro Definition Documentation

◆ HEAP_LEFT_OFFSET

#define HEAP_LEFT_OFFSET (   i)    (((i) << 1) + OFFSET(1))

◆ HEAP_PARENT

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

Definition at line 22 of file BLI_heap_simple.c.

◆ NODE

#define NODE (   offset)    (*(HeapSimpleNode *)(tree_buf + (offset)))

◆ OFFSET

#define OFFSET (   i)    (i * (uint)sizeof(HeapSimpleNode))

Typedef Documentation

◆ HeapSimpleNode

Function Documentation

◆ BLI_heapsimple_clear()

void BLI_heapsimple_clear ( HeapSimple heap,
HeapSimpleFreeFP  ptrfreefp 
)

Definition at line 163 of file BLI_heap_simple.c.

References HeapSimpleNode::ptr, HeapSimple::size, and HeapSimple::tree.

Referenced by bmo_connect_vert_pair_exec().

◆ BLI_heapsimple_free()

void BLI_heapsimple_free ( HeapSimple heap,
HeapSimpleFreeFP  ptrfreefp 
)

◆ BLI_heapsimple_insert()

void BLI_heapsimple_insert ( HeapSimple heap,
float  value,
void ptr 
)

◆ BLI_heapsimple_is_empty()

bool BLI_heapsimple_is_empty ( const HeapSimple heap)

◆ BLI_heapsimple_len()

uint BLI_heapsimple_len ( const HeapSimple heap)

Definition at line 189 of file BLI_heap_simple.c.

References HeapSimple::size.

Referenced by bmo_connect_vert_pair_exec(), and TEST().

◆ BLI_heapsimple_new()

HeapSimple* BLI_heapsimple_new ( void  )

◆ BLI_heapsimple_new_ex()

HeapSimple* BLI_heapsimple_new_ex ( unsigned int  reserve_num)

Creates a new simple heap, which only supports insertion and removal from top.

Note
Use when the size of the heap is known in advance.

Definition at line 136 of file BLI_heap_simple.c.

References HeapSimple::bufsize, MAX2, MEM_mallocN, HeapSimple::size, and HeapSimple::tree.

Referenced by BLI_heapsimple_new(), and heap_find_nearest_begin().

◆ BLI_heapsimple_pop_min()

void* BLI_heapsimple_pop_min ( HeapSimple heap)

◆ BLI_heapsimple_top_value()

float BLI_heapsimple_top_value ( const HeapSimple heap)

Return the lowest value of the heap.

Definition at line 194 of file BLI_heap_simple.c.

References BLI_assert, HeapSimple::size, HeapSimple::tree, and HeapSimpleNode::value.

Referenced by edbm_average_normals_exec(), and heap_find_nearest_begin().

◆ heapsimple_down()

static void heapsimple_down ( HeapSimple heap,
uint  start_i,
const HeapSimpleNode init 
)
static

◆ heapsimple_up()

static void heapsimple_up ( HeapSimple heap,
uint  i,
float  active_val,
void active_ptr 
)
static

Definition at line 111 of file BLI_heap_simple.c.

References HEAP_PARENT, LIKELY, HeapSimple::tree, and tree.

Referenced by BLI_heapsimple_insert().