BLI_heap_simple.c File Reference

#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_heap_simple.h"
#include "BLI_utildefines.h"
#include "BLI_strict_flags.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
HeapSimple *	BLI_heapsimple_new_ex (uint reserve_num)
HeapSimple *	BLI_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)
void *	BLI_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))

Referenced by heapsimple_down().

HEAP_PARENT

#define HEAP_PARENT

(

i

)

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

Definition at line 25 of file BLI_heap_simple.c.

Referenced by heapsimple_up().

NODE

#define NODE

(

offset

)

(*(HeapSimpleNode *)(tree_buf + (offset)))

Referenced by heapsimple_down().

OFFSET

#define OFFSET

(

i

)

(i * (uint)sizeof(HeapSimpleNode))

Referenced by heapsimple_down().

Typedef Documentation

HeapSimpleNode

typedef struct HeapSimpleNode HeapSimpleNode

Function Documentation

BLI_heapsimple_clear()

void BLI_heapsimple_clear	(	HeapSimple *	heap,
		HeapSimpleFreeFP	ptrfreefp )

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

Definition at line 154 of file BLI_heap_simple.c.

References MEM_freeN(), HeapSimpleNode::ptr, HeapSimple::size, and HeapSimple::tree.

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), blender::bke::pbvh::bmesh_update_topology(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), heap_find_nearest_begin(), hull_merge_triangles(), random_heapsimple_helper(), TEST(), TEST(), TEST(), TEST(), and TEST().

BLI_heapsimple_insert()

void BLI_heapsimple_insert	(	HeapSimple *	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 177 of file BLI_heap_simple.c.

References HeapSimple::bufsize, heapsimple_up(), MEM_reallocN, ptr, HeapSimple::size, HeapSimple::tree, and UNLIKELY.

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), blender::bke::pbvh::edge_queue_insert(), edgetag_add_adjacent(), edgetag_add_adjacent_uv(), facetag_add_adjacent(), facetag_add_adjacent_uv(), heap_find_nearest_inner(), hull_merge_triangles(), random_heapsimple_helper(), state_link_add_test(), TEST(), TEST(), TEST(), TEST(), verttag_add_adjacent(), and verttag_add_adjacent_uv().

BLI_heapsimple_is_empty()

bool BLI_heapsimple_is_empty

(

const HeapSimple *

heap

)

Definition at line 187 of file BLI_heap_simple.c.

References HeapSimple::size.

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), heap_find_nearest_begin(), hull_merge_triangles(), blender::bke::pbvh::pbvh_bmesh_collapse_short_edges(), blender::bke::pbvh::pbvh_bmesh_subdivide_long_edges(), random_heapsimple_helper(), TEST(), TEST(), TEST(), TEST(), and TEST().

BLI_heapsimple_len()

uint BLI_heapsimple_len

(

const HeapSimple *

heap

)

Definition at line 192 of file BLI_heap_simple.c.

References HeapSimple::size.

Referenced by bmo_connect_vert_pair_exec(), TEST(), and TEST().

BLI_heapsimple_new()

HeapSimple * BLI_heapsimple_new

(

void

)

Definition at line 149 of file BLI_heap_simple.c.

References BLI_heapsimple_new_ex().

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), hull_merge_triangles(), blender::bke::pbvh::long_edge_queue_create(), random_heapsimple_helper(), blender::bke::pbvh::short_edge_queue_create(), TEST(), TEST(), TEST(), TEST(), and TEST().

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 139 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

)

Pop the top node off the heap and return its pointer.

Definition at line 204 of file BLI_heap_simple.c.

References BLI_assert, heapsimple_down(), HeapSimpleNode::ptr, ptr, HeapSimple::size, and HeapSimple::tree.

Referenced by BLI_astar_graph_solve(), BM_mesh_calc_path_edge(), BM_mesh_calc_path_face(), BM_mesh_calc_path_uv_edge(), BM_mesh_calc_path_uv_face(), BM_mesh_calc_path_uv_vert(), BM_mesh_calc_path_vert(), bmo_connect_vert_pair_exec(), curve_select_shortest_path_surf(), edbm_average_normals_exec(), heap_find_nearest_begin(), hull_merge_triangles(), blender::bke::pbvh::pbvh_bmesh_collapse_short_edges(), blender::bke::pbvh::pbvh_bmesh_subdivide_long_edges(), random_heapsimple_helper(), TEST(), TEST(), TEST(), and TEST().

BLI_heapsimple_top_value()

float BLI_heapsimple_top_value

(

const HeapSimple *

heap

)

Return the lowest value of the heap.

Definition at line 197 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

Definition at line 48 of file BLI_heap_simple.c.

References HEAP_LEFT_OFFSET, init(), l, LIKELY, NODE, OFFSET, HeapSimple::size, HeapSimple::tree, tree, and UNLIKELY.

Referenced by BLI_heapsimple_pop_min().

heapsimple_up()

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

static

Definition at line 114 of file BLI_heap_simple.c.

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

Referenced by BLI_heapsimple_insert().