inc/quickHeap.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	quickHeap
Functions
quickHeap *	newQuickHeap (int initSize, int(*compare)(const void *elem1, const void *elem2))
void	freeQuickHeap (struct quickHeap **pH)
void	addToQuickHeap (struct quickHeap *h, void *elem)
void	quickHeapTopChanged (struct quickHeap *h)
boolean	quickHeapEmpty (struct quickHeap *h)
boolean	removeFromQuickHeapByElem (struct quickHeap *h, void *elem)
void *	peekQuickHeapTop (struct quickHeap *h)
void *	removeQuickHeapTop (struct quickHeap *h)

---

Function Documentation

void addToQuickHeap	(	struct quickHeap *	h,
		void *	elem
	)

Definition at line 66 of file quickHeap.c.

References quickHeap::compareFunc, expandQuickHeap(), quickHeap::heap, quickHeap::heapCount, and quickHeap::heapMax.

{
int n, p;   /* node, parent */
if (h->heapCount >= h->heapMax)
    expandQuickHeap(h);
/* preserve heap property as it grows */
n = h->heapCount;
h->heap[h->heapCount++] = elem;
p = (n-1)/2;
while (n > 0 && h->compareFunc(h->heap[p], h->heap[n]) < 0)
    {
    void *temp = h->heap[p];
    h->heap[p] = h->heap[n];
    h->heap[n] = temp;
    n = p;
    p = (n-1)/2;
    }
}

Here is the call graph for this function:

void freeQuickHeap

(

struct quickHeap **

pH

)

Definition at line 50 of file quickHeap.c.

References freez(), and quickHeap::heap.

{
struct quickHeap *h = *pH;
freez(&h->heap);
freez(pH);
}

Here is the call graph for this function:

struct quickHeap* newQuickHeap	(	int	initSize,
		int(*)(const void *elem1, const void *elem2)	compare
	)			[read]

Definition at line 33 of file quickHeap.c.

References AllocN, AllocVar, quickHeap::compareFunc, errAbort(), quickHeap::heap, quickHeap::heapCount, and quickHeap::heapMax.

{
struct quickHeap *h;
if (initSize < 1)
    errAbort("invalid initial size for newQuickHeap: %d",initSize);
AllocVar(h);
h->heapCount=0;
h->heapMax = initSize;
h->heap = AllocN(void *,h->heapMax);
h->compareFunc = compare;
return h;
}

Here is the call graph for this function:

void* peekQuickHeapTop

(

struct quickHeap *

h

)

Definition at line 176 of file quickHeap.c.

References quickHeap::heap, and quickHeap::heapCount.

{
if (h->heapCount < 1) 
    return NULL;
return h->heap[0];    
}

boolean quickHeapEmpty

(

struct quickHeap *

h

)

Definition at line 127 of file quickHeap.c.

References quickHeap::heapCount.

{
return h->heapCount < 1;
}

void quickHeapTopChanged

(

struct quickHeap *

h

)

Definition at line 119 of file quickHeap.c.

References quickHeapBalanceWithChildren().

{
/* balance heap - swap node with biggest child until both children are 
 * either less or equal or hit end of heap (no more children) */
quickHeapBalanceWithChildren(h,0);
}

Here is the call graph for this function:

boolean removeFromQuickHeapByElem	(	struct quickHeap *	h,
		void *	elem
	)

Definition at line 164 of file quickHeap.c.

References FALSE, findElemInQuickHeap(), removeFromQuickHeapN(), and TRUE.

{
int n = findElemInQuickHeap(h, elem);
if (n < 0) 
    return FALSE;
removeFromQuickHeapN(h,n);
return TRUE;
}

Here is the call graph for this function:

void* removeQuickHeapTop

(

struct quickHeap *

h

)

Definition at line 184 of file quickHeap.c.

References quickHeap::heap, quickHeap::heapCount, and removeFromQuickHeapN().

{
void *result = h->heap[0]; 
/* this is ok, but depends on removeFromQuickHeapN NULLing as it empties */   
if (h->heapCount > 0) 
    {
    removeFromQuickHeapN(h,0);
    }
return result;
}

Here is the call graph for this function:

---