Header LALHeap.h

Detailed Description

Implementation of a generic heap, following Chapter 10.1 of [19] .

Author

Karl Wette

Prototypes
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...
const void **	XLALHeapElements (const LALHeap *h)
	Allocate and return an array containing all elements in the heap. More...

Typedefs
typedef void(*	LALHeapDtorFcn) (void *x)
	Function which free memory associated with heap element x More...
typedef int(*	LALHeapCmpFcn) (const void *x, const void *y)
	Function which compares heap elements x and y More...
typedef int(*	LALHeapCmpParamFcn) (void *param, const void *x, const void *y)
	Function which compares heap elements x and y, with a parameter param. More...
typedef int(*	LALHeapVisitFcn) (void *param, const void *x)
	Function to call when visiting heap element x, with a parameter param. More...
typedef int(*	LALHeapModifyFcn) (void *param, void *x)
	Function to call when visiting (and possibly modify) heap element x, with a parameter param. More...

Function Documentation

XLALHeapCreate()

LALHeap * XLALHeapCreate	(	LALHeapDtorFcn	dtor,
		int	max_size,
		int	min_or_max_heap,
		LALHeapCmpFcn	cmp
	)

Create a heap.

Parameters

[in]	dtor	Heap element destructor function, if required
[in]	max_size	Maximum size of the heap; if zero, heap has unlimited size
[in]	min_or_max_heap	-1|+1 if root of heap is minimum|maximum element
	cmp	[in[ Heap element comparison function

Definition at line 146 of file LALHeap.c.

XLALHeapCreate2()

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.

Parameters

[in]	dtor	Heap element destructor function, if required
[in]	max_size	Maximum size of the heap; if zero, heap has unlimited size
[in]	min_or_max_heap	-1|+1 if root of heap is minimum|maximum element
[in]	cmp	Parameterised heap element comparison function
[in]	cmp_param	Parameter to pass to comparison function

Definition at line 162 of file LALHeap.c.

XLALHeapDestroy()

void XLALHeapDestroy

(

LALHeap *

h

)

Destroy a heap and its elements.

Parameters

[in]

h

Pointer to heap

Definition at line 192 of file LALHeap.c.

XLALHeapClear()

int XLALHeapClear

(

LALHeap *

h

)

Clear a heap.

Parameters

[in]

h

Pointer to heap

Definition at line 209 of file LALHeap.c.

XLALHeapSize()

int XLALHeapSize

(

const LALHeap *

h

)

Return the size of a heap.

Parameters

[in]

h

Pointer to heap

Definition at line 235 of file LALHeap.c.

XLALHeapMaxSize()

int XLALHeapMaxSize

(

const LALHeap *

h

)

Return the maximum size of a heap.

Parameters

[in]

h

Pointer to heap

Definition at line 243 of file LALHeap.c.

XLALHeapIsFull()

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.

Parameters

[in]

h

Pointer to heap

Definition at line 251 of file LALHeap.c.

XLALHeapRoot()

const void * XLALHeapRoot

(

const LALHeap *

h

)

Return the root element of a heap.

Parameters

[in]

h

Pointer to heap

Definition at line 259 of file LALHeap.c.

XLALHeapResize()

int XLALHeapResize	(	LALHeap *	h,
		int	max_size
	)

Change the maximum size of a heap; if the heap is contracted, excess elements are destroyed.

Parameters

[in]	h	Pointer to heap
[in]	max_size	New maximum size of the heap; if zero, heap has unlimited size

Definition at line 267 of file LALHeap.c.

XLALHeapAdd()

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.

Parameters

[in]	h	Pointer to heap
	x	[in/out] Pointer to new element. If the root element is removed, it is returned in *x; otherwise *x is set to NULL

Definition at line 289 of file LALHeap.c.

XLALHeapExtractRoot()

void * XLALHeapExtractRoot

(

LALHeap *

h

)

Remove the root element of a heap.

Parameters

[in]

h

Pointer to heap

Definition at line 305 of file LALHeap.c.

XLALHeapRemoveRoot()

int XLALHeapRemoveRoot

(

LALHeap *

h

)

Remove and destroy the root element of a heap.

Parameters

[in]

h

Pointer to heap

Definition at line 333 of file LALHeap.c.

XLALHeapExchangeRoot()

int XLALHeapExchangeRoot	(	LALHeap *	h,
		void **	x
	)

Exchange the root element of a non-empty heap with the new element in *x

Parameters

[in]	h	Pointer to heap
	x	[in/out] Pointer to new element. On return, contains root element

Definition at line 355 of file LALHeap.c.

XLALHeapVisit()

int XLALHeapVisit	(	const LALHeap *	h,
		LALHeapVisitFcn	visit,
		void *	visit_param
	)

Visit each element in the heap in the order given by the comparison function.

Parameters

[in]	h	Pointer to heap
[in]	visit	Visitor function to call for each heap element
[in]	visit_param	Parameter to pass to visitor function

Definition at line 374 of file LALHeap.c.

XLALHeapModify()

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.

Parameters

[in]	h	Pointer to heap
[in]	modify	Modifier function to call for each heap element
[in]	modify_param	Parameter to pass to modifier function

Definition at line 409 of file LALHeap.c.

XLALHeapElements()

const void ** XLALHeapElements

(

const LALHeap *

h

)

Allocate and return an array containing all elements in the heap.

Parameters

[in]

h

Pointer to heap

Definition at line 465 of file LALHeap.c.

Typedef Documentation

LALHeapDtorFcn

typedef void(* LALHeapDtorFcn) (void *x)

Function which free memory associated with heap element x

Definition at line 45 of file LALHeap.h.

LALHeapCmpFcn

typedef int(* LALHeapCmpFcn) (const void *x, const void *y)

Function which compares heap elements x and y

Definition at line 50 of file LALHeap.h.

LALHeapCmpParamFcn

typedef int(* LALHeapCmpParamFcn) (void *param, const void *x, const void *y)

Function which compares heap elements x and y, with a parameter param.

Definition at line 55 of file LALHeap.h.

LALHeapVisitFcn

typedef int(* LALHeapVisitFcn) (void *param, const void *x)

Function to call when visiting heap element x, with a parameter param.

Return XLAL_SUCCESS if successful, or XLAL_FAILURE otherwise.

Definition at line 61 of file LALHeap.h.

LALHeapModifyFcn

typedef int(* LALHeapModifyFcn) (void *param, void *x)

Function to call when visiting (and possibly modify) heap element x, with a parameter param.

Return XLAL_SUCCESS if successful, or XLAL_FAILURE otherwise.

Definition at line 67 of file LALHeap.h.