/* qPriHeapLib.c - heap priority queue management library *//* Copyright 1984-1998 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history--------------------01p,11nov01,dee  Add COLDFIRE support01o,04sep98,cdp  make ARM CPUs with ARM_THUMB==TRUE use portable routines.01n,22apr97,jpd  Added ARM to non-portable list.01m,19mar95,dvs  removed tron references.01l,19jul92,pme  made qPriHeapRemove return STATUS.01k,18jul92,smb  Changed errno.h to errnoLib.h.01j,26may92,rrr  the tree shuffle01i,19nov91,rrr  shut up some ansi warnings.01h,04oct91,rrr  passed through the ansification filter                  -changed functions to ansi style		  -changed includes to have absolute path from h/		  -changed VOID to void		  -changed copyright notice01g,23jul91,hdn  added conditional macro for optimized TRON codes.01f,24may91,wmd  added predeclarations to avoid compiler errors.01e,28sep90,jcf	 documentation.01d,05jul90,jcf	 added qPriHeapCalibrate().01c,26jun90,jcf	 add qPriHeapResort().01b,10may90,jcf	 fixed PORTABLE definition.01a,14jun89,jcf	 written.*//*DESCRIPTIONThis library contains routines to manage a priority queue.  The queue ismaintained in priority order in a binary tree.  This queue performs aqPriHeapPut() operation preportional in time with log base 2 of the number ofnodes in the queue.  This queue is used for timer queues.  The only restrictionis that the heap can only handle a static number of nodes as specified atcreation time.This queue complies with the multi-way queue data structures and thus may beutilized by any multi-way queue.  The priority heap multi-way queueclass is accessed by the global id qPriHeapClassId.SEE ALSO: qLib()*/#include "vxWorks.h"#include "qClass.h"#include "qPriHeapLib.h"#include "stdlib.h"#include "string.h"#include "errnoLib.h"#include "stdio.h"/* XXX should break out for each architecture *//* optimized version available for 680X0 and ARM */#if (defined(PORTABLE) || \     ((CPU_FAMILY != MC680X0) && (CPU_FAMILY != ARM) && (CPU_FAMILY != COLDFIRE)) || \     ((CPU_FAMILY == ARM) && ARM_THUMB))#define qPriHeapLib_PORTABLE#endif	/* (defined(PORTABLE) || (CPU_FAMILY != MC680X0)) *//* imports */IMPORT ULONG vxTicks;		/* current time in ticks *//* globals */LOCAL Q_CLASS qPriHeapClass =    {    (FUNCPTR)qPriHeapCreate,    (FUNCPTR)qPriHeapInit,    (FUNCPTR)qPriHeapDelete,    (FUNCPTR)qPriHeapTerminate,    (FUNCPTR)qPriHeapPut,    (FUNCPTR)qPriHeapGet,    (FUNCPTR)qPriHeapRemove,    (FUNCPTR)qPriHeapResort,    (FUNCPTR)qPriHeapAdvance,    (FUNCPTR)qPriHeapGetExpired,    (FUNCPTR)qPriHeapKey,    (FUNCPTR)qPriHeapCalibrate,    (FUNCPTR)qPriHeapInfo,    (FUNCPTR)qPriHeapEach,    &qPriHeapClass    };Q_CLASS_ID qPriHeapClassId = &qPriHeapClass;/* forward static functions */#ifdef qPriHeapLib_PORTABLEstatic void qPriHeapUp (Q_PRI_HEAP_HEAD *pQPriHeapHead, int index);static void qPriHeapDown (Q_PRI_HEAP_HEAD *pQPriHeapHead, int index);#elseextern void qPriHeapUp (Q_PRI_HEAP_HEAD *pQPriHeapHead, int index);extern void qPriHeapDown (Q_PRI_HEAP_HEAD *pQPriHeapHead, int index);#endif/******************************************************************************** qPriHeapArrayCreate - create and initialized a heap priority queue** Create a heap priority queue.  Initialize the specified queue header.** RETURNS: OK or ERROR if not enough memory to create queue.** SEE ALSO: qPriHeapInit (2)*/HEAP_ARRAY *qPriHeapArrayCreate    (    int heapSize    )    {    return ((HEAP_ARRAY *) malloc ((unsigned) 4 * heapSize));    }/******************************************************************************** qPriHeapArrayDelete - deallocate a heap array** This routine returns an allocated HEAP_ARRAY structure to the free memory* pool.** RETURNS:*  OK, or*  ERROR if could not deallocate heap array.*/STATUS qPriHeapArrayDelete    (    HEAP_ARRAY *pHeapArray    )    {    free ((char *) pHeapArray);    return OK;    }/******************************************************************************** qPriHeapCreate - create and initialized a heap priority queue** Create a heap priority queue.  Initialize the specified queue header.** RETURNS: OK or ERROR if not enough memory to create queue.** SEE ALSO: qPriHeapInit (2)*/Q_PRI_HEAP_HEAD *qPriHeapCreate    (    HEAP_ARRAY *pHeapArray    )    {    Q_PRI_HEAP_HEAD *pQPriHeapHead = (Q_PRI_HEAP_HEAD *)				     malloc (sizeof (Q_PRI_HEAP_HEAD));    if (pQPriHeapHead == NULL)	return (NULL);    if (qPriHeapInit (pQPriHeapHead, pHeapArray) != OK)	{	free ((char *)pQPriHeapHead);	return (NULL);	}    return (pQPriHeapHead);    }/******************************************************************************** qPriHeapInit - initialize a heap priority queue** Initialize the heap priority queue pointed to by the specified queue* header.** RETURNS:  OK, or ERROR if heap priority queue could not be initialized.** ERRNO: S_qPriHeapLib_NULL_HEAP_ARRAY**/STATUS qPriHeapInit    (    Q_PRI_HEAP_HEAD *pQPriHeapHead,    HEAP_ARRAY      *pHeapArray    )    {    if (pHeapArray == NULL)	{	errnoSet (S_qPriHeapLib_NULL_HEAP_ARRAY);	return (ERROR);	}    pQPriHeapHead->pHeapArray	= pHeapArray;	/* store bmap list pointer */    pQPriHeapHead->pHighNode	= NULL;		/* zero the highest node */    pQPriHeapHead->heapIndex	= 0;		/* initialize the heap index */    return (OK);    }/******************************************************************************** qPriHeapDelete - delete a priority heap queue** This routine deallocates memory associated with the queue.  All queued* nodes are lost.** RETURNS:*  OK, or*  ERROR if memory cannot be deallocated.*/STATUS qPriHeapDelete    (    Q_PRI_HEAP_HEAD *pQPriHeapHead    )    {    free ((char *) pQPriHeapHead);    return OK;    }/******************************************************************************** qPriHeapTerminate - terminate a heap priority queue** This routine terminates a heap priority queue.  All queued nodes will be lost.** ARGSUSED*/STATUS qPriHeapTerminate    (    Q_PRI_HEAP_HEAD *pQPriHeapHead    )    {    return (OK);    }/********************************************************************************* qPriHeapPut - insert a node into a heap priority queue** This routine inserts a node into a heap priority queue.  The insertion is* based on the priority key.  The lower the key the higher the priority.*/void qPriHeapPut    (    Q_PRI_HEAP_HEAD     *pQPriHeapHead,    Q_PRI_HEAP_NODE     *pQPriHeapNode,    ULONG                key    )    {    int index = pQPriHeapHead->heapIndex++;    pQPriHeapNode->key = key;    (*pQPriHeapHead->pHeapArray)[index] = pQPriHeapNode;    qPriHeapUp (pQPriHeapHead, index);    }/********************************************************************************* qPriHeapGet - remove and return first node in heap priority queue** This routine removes and returns the first node in a heap priority queue.  If* the queue is empty, NULL is returned.** RETURNS*  Pointer to first queue node in queue head, or*  NULL if queue is empty.*/Q_PRI_HEAP_NODE *qPriHeapGet    (    Q_PRI_HEAP_HEAD *pQPriHeapHead    )    {    FAST Q_PRI_HEAP_NODE **heapArray = *pQPriHeapHead->pHeapArray;    Q_PRI_HEAP_NODE *pQPriHeapNode = pQPriHeapHead->pHighNode;    if (pQPriHeapHead->heapIndex == 0)	return (NULL);    else if (pQPriHeapHead->heapIndex-- == 1)	pQPriHeapHead->pHighNode = NULL;    else	{	heapArray [0] = heapArray [pQPriHeapHead->heapIndex];	qPriHeapDown (pQPriHeapHead, 0);	}    return (pQPriHeapNode);    }/********************************************************************************* qPriHeapRemove - remove a node from a heap priority queue** This routine removes a node from the specified heap priority queue.*/STATUS qPriHeapRemove    (    Q_PRI_HEAP_HEAD *pQPriHeapHead,    Q_PRI_HEAP_NODE *pQPriHeapNode    )    {    FAST int index = pQPriHeapNode->index;    FAST Q_PRI_HEAP_NODE **heapArray = *pQPriHeapHead->pHeapArray;    int heapIndex = pQPriHeapHead->heapIndex;    if (--pQPriHeapHead->heapIndex == 0)	pQPriHeapHead->pHighNode = NULL;    else	{	heapArray [index] = heapArray [heapIndex - 1];	if ((index > 0) &&	    (heapArray [(index - 1) / 2]->key > heapArray [index]->key))	    qPriHeapUp (pQPriHeapHead, index);	else	    qPriHeapDown (pQPriHeapHead, index);	}    return (OK);    }/********************************************************************************* qPriHeapResort - resort a node to a new position based on a new key