Blender: BLI_heap.c File Reference

Blender V2.61 - r43446

#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_memarena.h"
#include "BLI_heap.h"

Go to the source code of this file.

Classes
struct	HeapNode
struct	Heap
Defines
#define	SWAP(type, a, b) { type sw_ap; sw_ap=(a); (a)=(b); (b)=sw_ap; }
#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)
#define	HEAP_EQUALS(a, b) (a->value == b->value)
#define	HEAP_SWAP(heap, i, j)
Functions
Heap *	BLI_heap_new (void)
void	BLI_heap_free (Heap *heap, HeapFreeFP ptrfreefp)
static void	BLI_heap_down (Heap *heap, int i)
static void	BLI_heap_up (Heap *heap, int i)
HeapNode *	BLI_heap_insert (Heap heap, float value, void ptr)
int	BLI_heap_empty (Heap *heap)
int	BLI_heap_size (Heap *heap)
HeapNode *	BLI_heap_top (Heap *heap)
void *	BLI_heap_popmin (Heap *heap)
void	BLI_heap_remove (Heap heap, HeapNode node)
float	BLI_heap_node_value (HeapNode *node)
void *	BLI_heap_node_ptr (HeapNode *node)

Detailed Description

Definition in file BLI_heap.c.

Define Documentation

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

Definition at line 62 of file BLI_heap.c.

Referenced by BLI_heap_down(), and BLI_heap_up().

#define HEAP_EQUALS	(		a,
			b
	)		(a->value == b->value)

Definition at line 63 of file BLI_heap.c.

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

Definition at line 60 of file BLI_heap.c.

Referenced by BLI_heap_down().

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

Definition at line 59 of file BLI_heap.c.

Referenced by BLI_heap_remove(), and BLI_heap_up().

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

Definition at line 61 of file BLI_heap.c.

Referenced by BLI_heap_down().

#define HEAP_SWAP	(		heap,
			i,
			j
	)

Value:

{                                                                             \
    SWAP(int, heap->tree[i]->index, heap->tree[j]->index);                    \
    SWAP(HeapNode*, heap->tree[i], heap->tree[j]);                            \
}

Definition at line 64 of file BLI_heap.c.

Referenced by BLI_heap_down(), BLI_heap_popmin(), BLI_heap_remove(), and BLI_heap_up().

#define SWAP	(		type,
			a,
			b
	)		{ type sw_ap; sw_ap=(a); (a)=(b); (b)=sw_ap; }

Definition at line 57 of file BLI_heap.c.

Function Documentation

static void BLI_heap_down	(	Heap *	heap,
		int	i
	)		`[static]`

Definition at line 95 of file BLI_heap.c.

References HEAP_COMPARE, HEAP_LEFT, HEAP_RIGHT, HEAP_SWAP, Heap::size, size(), and Heap::tree.

Referenced by BLI_heap_popmin().

int BLI_heap_empty ( Heap * heap )

Definition at line 164 of file BLI_heap.c.

References Heap::size.

Referenced by edgetag_shortest_path(), and select_vertex_path_exec().

void BLI_heap_free	(	Heap *	heap,
		HeapFreeFP	ptrfreefp
	)

Definition at line 82 of file BLI_heap.c.

References Heap::arena, BLI_memarena_free(), i, MEM_freeN(), HeapNode::ptr, Heap::size, and Heap::tree.

Referenced by edgetag_shortest_path(), p_chart_fill_boundary(), select_vertex_path_exec(), and shortestPathsFromVert().

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

Definition at line 128 of file BLI_heap.c.

References Heap::arena, BLI_heap_up(), BLI_memarena_alloc(), Heap::bufsize, Heap::freenodes, HeapNode::index, MEM_freeN(), MEM_mallocN(), HeapNode::ptr, Heap::size, Heap::tree, and HeapNode::value.

Referenced by edgetag_add_adjacent(), edgetag_shortest_path(), p_chart_fill_boundary(), select_vertex_path_exec(), and shortestPathsFromVert().

Heap* BLI_heap_new ( void )

Definition at line 72 of file BLI_heap.c.

References Heap::arena, BLI_memarena_new(), Heap::bufsize, MEM_callocN(), MEM_mallocN(), and Heap::tree.

Referenced by edgetag_shortest_path(), p_chart_fill_boundary(), select_vertex_path_exec(), and shortestPathsFromVert().

void* BLI_heap_node_ptr ( HeapNode * node )

Definition at line 217 of file BLI_heap.c.

References HeapNode::ptr.

float BLI_heap_node_value ( HeapNode * node )

Definition at line 212 of file BLI_heap.c.

References HeapNode::value.

Referenced by shortestPathsFromVert().

void* BLI_heap_popmin ( Heap * heap )

Definition at line 179 of file BLI_heap.c.

References BLI_heap_down(), Heap::freenodes, HEAP_SWAP, HeapNode::ptr, Heap::size, and Heap::tree.

Referenced by BLI_heap_remove(), edgetag_shortest_path(), p_chart_fill_boundary(), select_vertex_path_exec(), and shortestPathsFromVert().

void BLI_heap_remove	(	Heap *	heap,
		HeapNode *	node
	)

Definition at line 198 of file BLI_heap.c.

References BLI_heap_popmin(), HEAP_PARENT, HEAP_SWAP, i, HeapNode::index, and p.

Referenced by p_chart_fill_boundary().

int BLI_heap_size ( Heap * heap )

Definition at line 169 of file BLI_heap.c.

References Heap::size.

Referenced by shortestPathsFromVert().

HeapNode* BLI_heap_top ( Heap * heap )

Definition at line 174 of file BLI_heap.c.

References Heap::tree.

Referenced by shortestPathsFromVert().

static void BLI_heap_up	(	Heap *	heap,
		int	i
	)		`[static]`

Definition at line 115 of file BLI_heap.c.

References HEAP_COMPARE, HEAP_PARENT, HEAP_SWAP, p, and Heap::tree.

Referenced by BLI_heap_insert().