LALHeap.c File Reference

Prototypes
static int	heap_no_param_cmp (void *param, const void *x, const void *y)
static int	heap_resize (LALHeap *h)
static void	heap_bubble_up (LALHeap *h, int i)
static void	heap_trickle_down (LALHeap *h, int i)
static int	heap_add_full (LALHeap *h, void **x)
static int	heap_add_not_full (LALHeap *h, void **x)
LALHeap *	XLALHeapCreate (LALHeapDtorFcn dtor, int max_size, int min_or_max_heap, LALHeapCmpFcn cmp)
	Create a heap. More...
LALHeap *	XLALHeapCreate2 (LALHeapDtorFcn dtor, int max_size, int min_or_max_heap, LALHeapCmpParamFcn cmp, void *cmp_param)
	Create a heap with a parameterised comparison function. More...
void	XLALHeapDestroy (LALHeap *h)
	Destroy a heap and its elements. More...
int	XLALHeapClear (LALHeap *h)
	Clear a heap. More...
int	XLALHeapSize (const LALHeap *h)
	Return the size of a heap. More...
int	XLALHeapMaxSize (const LALHeap *h)
	Return the maximum size of a heap. More...
int	XLALHeapIsFull (const LALHeap *h)
	Return >0 if a limited-size heap is full, 0 otherwise (or if heap has unlimited size), or <0 on error. More...
const void *	XLALHeapRoot (const LALHeap *h)
	Return the root element of a heap. More...
int	XLALHeapResize (LALHeap *h, int max_size)
	Change the maximum size of a heap; if the heap is contracted, excess elements are destroyed. More...
int	XLALHeapAdd (LALHeap *h, void **x)
	Add a new element to a heap; if the heap is of fixed size and full, the root element is removed. More...
void *	XLALHeapExtractRoot (LALHeap *h)
	Remove the root element of a heap. More...
int	XLALHeapRemoveRoot (LALHeap *h)
	Remove and destroy the root element of a heap. More...
int	XLALHeapExchangeRoot (LALHeap *h, void **x)
	Exchange the root element of a non-empty heap with the new element in *x More...
int	XLALHeapVisit (const LALHeap *h, LALHeapVisitFcn visit, void *visit_param)
	Visit each element in the heap in the order given by the comparison function. More...
int	XLALHeapModify (LALHeap *h, LALHeapModifyFcn modify, void *modify_param)
	Visit (and possibly modify) each element in the heap in the order given by the comparison function. More...
static int	heap_get_elems_visitor (void *param, const void *x)
const void **	XLALHeapElements (const LALHeap *h)
	Allocate and return an array containing all elements in the heap. More...

Go to the source code of this file.

Data Structures
struct	LALHeap
	Generic heap with elements of type void * More...

Macros
#define	LEFT(i)   (2*(i) + 1) /* Left child of binary heap element 'i' */
#define	RIGHT(i)   (2*(i) + 2) /* Right child of binary heap element 'i' */
#define	PARENT(i)   (((i) - 1)/2) /* Parent of binary heap element 'i' */
#define	SWAP(x, y)   do { void *z = (x); (x) = (y); (y) = z; } while (0)
#define	UNORDERED(h, x, y)   ((h)->cmp((h)->cmp_param, (x), (y)) * (h)->min_or_max_heap > 0)

Typedefs
typedef int(*	LALHeapAddFcn) (LALHeap *h, void **x)

Macro Definition Documentation

LEFT

#define LEFT

(

i

)

(2*(i) + 1) /* Left child of binary heap element 'i' */

Definition at line 22 of file LALHeap.c.

RIGHT

#define RIGHT

(

i

)

(2*(i) + 2) /* Right child of binary heap element 'i' */

Definition at line 23 of file LALHeap.c.

PARENT

#define PARENT

(

i

)

(((i) - 1)/2) /* Parent of binary heap element 'i' */

Definition at line 24 of file LALHeap.c.

SWAP

#define SWAP	(		x,
			y
	)		do { void *z = (x); (x) = (y); (y) = z; } while (0)

Definition at line 27 of file LALHeap.c.

UNORDERED

#define UNORDERED	(		h,
			x,
			y
	)		((h)->cmp((h)->cmp_param, (x), (y)) * (h)->min_or_max_heap > 0)

Definition at line 30 of file LALHeap.c.

Typedef Documentation

LALHeapAddFcn

typedef int( * LALHeapAddFcn) (LALHeap *h, void **x)

Definition at line 33 of file LALHeap.c.

Function Documentation

heap_no_param_cmp()

static int heap_no_param_cmp ( void *  param, const void *  x, const void *  y  )

static

Definition at line 48 of file LALHeap.c.

heap_resize()

static int heap_resize ( LALHeap *  h )

static

Definition at line 55 of file LALHeap.c.

heap_bubble_up()

static void heap_bubble_up ( LALHeap *  h, int  i  )

static

Definition at line 65 of file LALHeap.c.

heap_trickle_down()

static void heap_trickle_down ( LALHeap *  h, int  i  )

static

Definition at line 76 of file LALHeap.c.

heap_add_full()

static int heap_add_full ( LALHeap *  h, void **  x  )

static

Definition at line 101 of file LALHeap.c.

heap_add_not_full()

static int heap_add_not_full ( LALHeap *  h, void **  x  )

static

Definition at line 121 of file LALHeap.c.

heap_get_elems_visitor()

static int heap_get_elems_visitor ( void *  param, const void *  x  )

static

Definition at line 454 of file LALHeap.c.