lib/quickHeap.c File Reference

#include "common.h"
#include "quickHeap.h"

Include dependency graph for quickHeap.c:

Go to the source code of this file.

Functions
quickHeap *	newQuickHeap (int initSize, int(*compare)(const void *elem1, const void *elem2))
void	freeQuickHeap (struct quickHeap **pH)
static void	expandQuickHeap (struct quickHeap *h)
void	addToQuickHeap (struct quickHeap *h, void *elem)
static void	quickHeapBalanceWithChildren (struct quickHeap *h, int n)
void	quickHeapTopChanged (struct quickHeap *h)
boolean	quickHeapEmpty (struct quickHeap *h)
static void	removeFromQuickHeapN (struct quickHeap *h, int n)
static int	findElemInQuickHeap (struct quickHeap *h, void *elem)
boolean	removeFromQuickHeapByElem (struct quickHeap *h, void *elem)
void *	peekQuickHeapTop (struct quickHeap *h)
void *	removeQuickHeapTop (struct quickHeap *h)
Variables
static char const	rcsid [] = "$Id: quickHeap.c,v 1.1 2005/10/21 05:36:08 galt Exp $"

---

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:

static void expandQuickHeap

(

struct quickHeap *

h

)

[static]

Definition at line 58 of file quickHeap.c.

References ExpandArray, quickHeap::heap, and quickHeap::heapMax.

Referenced by addToQuickHeap().

{
int newSize = h->heapMax * 2;
ExpandArray(h->heap, h->heapMax, newSize);
h->heapMax = newSize;
}

Here is the caller graph for this function:

static int findElemInQuickHeap	(	struct quickHeap *	h,
		void *	elem
	)			[static]

Definition at line 150 of file quickHeap.c.

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

Referenced by removeFromQuickHeapByElem().

{
int n = -1;
while (++n < h->heapCount)
    {
    if (h->heap[n] == elem)
        return n;
    }
return -1;    
}

Here is the caller 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];    
}

static void quickHeapBalanceWithChildren	(	struct quickHeap *	h,
		int	n
	)			[static]

Definition at line 87 of file quickHeap.c.

References compareFunc, errAbort(), quickHeap::heap, quickHeap::heapCount, and TRUE.

Referenced by quickHeapTopChanged(), and removeFromQuickHeapN().

{
int c1, c2, hc;   /* child1, child2, heapCount */
if (n < 0 || n >= h->heapCount)
    errAbort("attempt to quickHeapBalanceWithChildren with invalid value "
                "for n: %d, heapCount=%d", n, h->heapCount);
/* balance heap - swap node with biggest child until both children are 
 * either less or equal or hit end of heap (no more children) */
hc = h->heapCount;
c1 = 2*n+1;
c2 = 2*n+2;
while (TRUE)
    {
    void *temp = NULL;
    int bestc = n;
    if (c1 < hc && h->compareFunc(h->heap[c1], h->heap[bestc]) > 0)
        bestc = c1;
    if (c2 < hc && h->compareFunc(h->heap[c2], h->heap[bestc]) > 0)
        bestc = c2;
    if (bestc == n)
        break;
    temp = h->heap[bestc];
    h->heap[bestc] = h->heap[n];
    h->heap[n] = temp;
    n = bestc;
    c1 = 2*n+1;
    c2 = 2*n+2;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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:

static void removeFromQuickHeapN	(	struct quickHeap *	h,
		int	n
	)			[static]

Definition at line 133 of file quickHeap.c.

References errAbort(), quickHeap::heap, quickHeap::heapCount, and quickHeapBalanceWithChildren().

Referenced by removeFromQuickHeapByElem(), and removeQuickHeapTop().

{
if (n < 0 || n >= h->heapCount)
    errAbort("attempt to removeFromQuickHeapN with invalid value "
                "for n: %d, heapCount=%d", n, h->heapCount);
h->heap[n] = h->heap[--h->heapCount]; /* wipes out n by moving tail to it */
h->heap[h->heapCount] = NULL; /* not needed but clean */
/* balance heap - swap node with biggest child until both children are 
 * either less or equal or hit end of heap (no more children) */
if (n < h->heapCount)  /* i.e. true for all but when n was the tail */
    quickHeapBalanceWithChildren(h,n);
}

Here is the call graph for this function:

Here is the caller 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:

---

Variable Documentation

char const rcsid[] = "$Id: quickHeap.c,v 1.1 2005/10/21 05:36:08 galt Exp $" [static]

Definition at line 30 of file quickHeap.c.

---