** This routine resorts a node to a new position based on a new key.*/void qPriHeapResort    (    Q_PRI_HEAP_HEAD *pQPriHeapHead,    Q_PRI_HEAP_NODE *pQPriHeapNode,    ULONG            newKey    )    {    FAST int index = pQPriHeapNode->index;    FAST Q_PRI_HEAP_NODE **heapArray = *pQPriHeapHead->pHeapArray;    pQPriHeapNode->key = newKey;    if ((index > 0) &&	(heapArray [(index - 1) / 2]->key > heapArray [index]->key))	qPriHeapUp (pQPriHeapHead, index);    else	qPriHeapDown (pQPriHeapHead, index);    }/********************************************************************************* qPriHeapAdvance - advance a queues concept of time** Heap queues need not keep track of time because nodes contain time of* expiration.  So this routine is a NOP.** NOMANUAL* ARGSUSED*/void qPriHeapAdvance    (    Q_PRI_HEAP_HEAD *pQPriHeapHead    )    {    /* Absolute queue so advancing key of lead node unnecessary */    }/********************************************************************************* qPriHeapGetExpired - return a time-to-fire expired node** This routine returns a time-to-fire expired node in a heap priority timer* queue.  Expired nodes result from a comparison with the global variable* vxTicks.  As many nodes may expire on a single advance of vxTicks, this* routine should be called inside a while loop until NULL is returned.  NULL* is returned when there are no expired nodes.** RETURNS*  Pointer to first queue node in queue head, or*  NULL if queue is empty.*/Q_PRI_HEAP_NODE *qPriHeapGetExpired    (    Q_PRI_HEAP_HEAD *pQPriHeapHead    )    {    Q_PRI_HEAP_NODE *pQPriHeapNode = pQPriHeapHead->pHighNode;    if ((pQPriHeapNode != NULL) && (pQPriHeapNode->key <= vxTicks))	return (qPriHeapGet (pQPriHeapHead));    else	return ((Q_PRI_HEAP_NODE *) NULL);    }/********************************************************************************* qPriHeapKey - return the key of a node** This routine returns the key of a node currently in a heap priority queue.* The keyType determines key style.  A normal key style returns the nodes* internal key.  A timer queue key type style returns the key as the* time-to-fire.** RETURNS*  Node's key, or*  node's time-to-fire.*/ULONG qPriHeapKey    (    Q_PRI_HEAP_NODE *pQPriHeapNode,    int              keyType            /* 0 = normal; 1 = time queue */    )    {    if (keyType == 0)	return (pQPriHeapNode->key);    else	return (pQPriHeapNode->key - vxTicks);    }/********************************************************************************* qPriHeapCalibrate - offset every node in a queue by some delta** This routine offsets every node in a heap priority queue by some delta.  The* offset may either by positive or negative.*/void qPriHeapCalibrate    (    Q_PRI_HEAP_HEAD *pQPriHeapHead,     /* queue to calibrate nodes for */    ULONG            keyDelta           /* offset to add to each node's key */    )    {    FAST int ix;    FAST Q_PRI_HEAP_NODE **heapArray = *pQPriHeapHead->pHeapArray;    for (ix = 0; ix < pQPriHeapHead->heapIndex; ix ++)	 heapArray[ix]->key += keyDelta;    }/********************************************************************************* qPriHeapInfo - gather information on a priority heap queue** This routine fills up to maxNodes elements of a nodeArray with nodes* currently in a priority heap queue.  The actual number of nodes copied to the* array is returned.  If the nodeArray is NULL, then the number of nodes in* the priority heap queue is returned.** RETURNS*  Number of node pointers copied into the nodeArray, or*  Number of nodes in multi-way queue if nodeArray is NULL*/int qPriHeapInfo    (    Q_PRI_HEAP_HEAD *pQPriHeapHead,     /* heap queue to gather list for */    FAST int nodeArray[],               /* array of node pointers for filling */    FAST int maxNodes                   /* max node pointers for nodeArray */    )    {    int numNodes = min (maxNodes, pQPriHeapHead->heapIndex);    if (nodeArray == NULL)		/* NULL node array means return count */	return (pQPriHeapHead->heapIndex);    bcopy ((char *)*pQPriHeapHead->pHeapArray, (char *)nodeArray, numNodes * 4);    return (numNodes);    }/********************************************************************************* qPriHeapEach - call a routine for each node in a queue** This routine calls a user-supplied routine once for each node in the* queue.  The routine should be declared as follows:* .CS*  BOOL routine (pQNode, arg)*      Q_PRI_HEAP_NODE	*pQNode;	/@ pointer to a queue node          @/*      int		arg;		/@ arbitrary user-supplied argument @/* .CE* The user-supplied routine should return TRUE if qPriHeapEach (2) is to* continue calling it for each entry, or FALSE if it is done and* qPriHeapEach can exit.** RETURNS: NULL if traversed whole queue, or pointer to Q_PRI_HEAP_NODE that*          qPriHeapEach stopped on.*/Q_PRI_HEAP_NODE *qPriHeapEach    (    Q_PRI_HEAP_HEAD *pQHead,    /* queue head of queue to call routine for */    FUNCPTR          routine,   /* the routine to call for each table entry */    int              routineArg /* arbitrary user-supplied argument */    )    {    FAST int ix;    for (ix = 0;	 (ix < pQHead->heapIndex) &&	 ((* routine) ((*pQHead->pHeapArray)[ix], routineArg));	 ix ++)	;    if (ix < pQHead->heapIndex)	return ((*pQHead->pHeapArray)[ix]);	/* return node we ended with */    else	return ((Q_PRI_HEAP_NODE *) NULL);	/* did all nodes */    }#ifdef qPriHeapLib_PORTABLE/********************************************************************************* qPriHeapUp - elevate a node to its proper place in the heap tree** This routine elevates a node to its proper place in the heap tree.*/LOCAL void qPriHeapUp    (    Q_PRI_HEAP_HEAD *pQPriHeapHead,    int index    )    {    int workIx   = index;    int parentIx = (workIx - 1) / 2;    Q_PRI_HEAP_NODE **heapArray = *pQPriHeapHead->pHeapArray;    Q_PRI_HEAP_NODE *workNode = heapArray [workIx];    while ((workIx > 0) && (heapArray [parentIx]->key > workNode->key))	{	heapArray [workIx] = heapArray [parentIx];	workIx = parentIx;	parentIx = (workIx - 1) / 2;	}    heapArray [workIx] = workNode;    pQPriHeapHead->pHighNode = heapArray [0];    }/********************************************************************************* qPriHeapDown - move a node down to its proper place in the heap tree** This routine moves a node down to its proper place in the heap tree.*/LOCAL void qPriHeapDown    (    Q_PRI_HEAP_HEAD *pQPriHeapHead,    int index    )    {    int workIx   = index;    int lesserChildIx;    int leftChildIx = 2 * workIx + 1;    int rightChildIx = leftChildIx + 1;    Q_PRI_HEAP_NODE **heapArray = *pQPriHeapHead->pHeapArray;    Q_PRI_HEAP_NODE *workNode = heapArray [workIx];    while (leftChildIx < pQPriHeapHead->heapIndex)	{	if ((rightChildIx >= pQPriHeapHead->heapIndex) ||	    (heapArray [leftChildIx]->key < heapArray [rightChildIx]->key))	    lesserChildIx = leftChildIx;	else	    lesserChildIx = rightChildIx;	if (heapArray [lesserChildIx]->key < workNode->key)	    {	    heapArray [workIx] = heapArray [lesserChildIx];	    workIx = lesserChildIx;	    }	else	    break;	leftChildIx  = 2 * workIx + 1;	rightChildIx = 2 * workIx + 2;	}    heapArray [workIx] = workNode;    pQPriHeapHead->pHighNode = heapArray [0];    }#endif	/* qPriHeapLib_PORTABLE *//********************************************************************************* qPriHeapShow - dump the heap in human readable form by key or node** This routine prints a humun readable representation of the heap to standard* out.  The two output formats are selected as: 0 node format, 1 key format.** CAVEATS* The output is only printed for the first 16 nodes, because beyond this the* output is unintelligible.*/void qPriHeapShow    (    Q_PRI_HEAP_HEAD *pHeap,     /* pointer to heap head to dump */    int format                  /* 0 - node format; 1 - key format */    )    {    int ix;    char gap[100];    char halfgap[100];    char *space = "                                               ";    int nodesPerLine = 1;    int endOfLine = 0;    int fmtlen = 3;    int limit = 15;    if (pHeap->heapIndex > 0)	printf ("First: %x\n", pHeap->pHighNode);    else	printf ("First: NULL\n");    if (format > 0)	{	limit = 7;	fmtlen = 8;	printf ("%24s"," ");	}    else	printf ("%29s"," ");    for (ix = 0; ix < min (pHeap->heapIndex, limit); ix ++)	{	if (ix == endOfLine)	    {	    strncpy (gap, space, 32 / nodesPerLine);	    gap [(32 / nodesPerLine) - fmtlen] = EOS;	    strncpy (halfgap, space, 16 / nodesPerLine);	    halfgap [(16 / nodesPerLine) - fmtlen] = EOS;	    nodesPerLine = nodesPerLine << 1;	    endOfLine += nodesPerLine;	    if (format > 0)		printf ("%8x\n%s", (*pHeap->pHeapArray)[ix], halfgap);	    else		printf ("%3d\n%s", (*pHeap->pHeapArray)[ix]->key, halfgap);	    }	else	    if (format > 0)		printf ("%8x%s", (*pHeap->pHeapArray)[ix], gap);	    else		printf ("%3d%s", (*pHeap->pHeapArray)[ix]->key, gap);	}    if (ix == limit)	printf ("\nTerminated at %d nodes because output gets ugly.\n", limit);    else	printf ("\n");    }