/* qPriListLib.c - priority ordered linked list queue library *//* Copyright 1984-1992 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history--------------------01h,19jul92,pme  made qPriListRemove return STATUS.01g,26may92,rrr  the tree shuffle01f,19nov91,rrr  shut up some ansi warnings.01e,04oct91,rrr  passed through the ansification filter                  -changed functions to ansi style		  -changed VOID to void		  -changed copyright notice01d,28sep90,jcf	 documentation.01c,05jul90,jcf  added qPriListCalibrate().01b,26jun90,jcf	 fixed qPriListResort();01a,14jun89,jcf	 written.*//*DESCRIPTIONThis library contains routines to manage a priority queue.  The queue ismaintained in priority order with simple priority insertion into a linked list.This queue performs a qPriListPut() operation preportional in time with numberof nodes in the queue.  This general purpose priority queue has many usesincluding the basis for priority semaphore queues.This queue complies with the multi-way queue data structures and thus may beutilized by any multi-way queue.  The priority list multi-way queueclass is accessed by the global id qPriListClassId.SEE ALSO: qLib.*/#include "vxWorks.h"#include "qClass.h"#include "qPriListLib.h"#include "stdlib.h"IMPORT ULONG vxTicks;		/* current time in ticks *//* locals */LOCAL Q_CLASS qPriListClass =    {    (FUNCPTR)qPriListCreate,    (FUNCPTR)qPriListInit,    (FUNCPTR)qPriListDelete,    (FUNCPTR)qPriListTerminate,    (FUNCPTR)qPriListPut,    (FUNCPTR)qPriListGet,    (FUNCPTR)qPriListRemove,    (FUNCPTR)qPriListResort,    (FUNCPTR)qPriListAdvance,    (FUNCPTR)qPriListGetExpired,    (FUNCPTR)qPriListKey,    (FUNCPTR)qPriListCalibrate,    (FUNCPTR)qPriListInfo,    (FUNCPTR)qPriListEach,    &qPriListClass    };LOCAL Q_CLASS qPriListFromTailClass =    {    (FUNCPTR)qPriListCreate,    (FUNCPTR)qPriListInit,    (FUNCPTR)qPriListDelete,    (FUNCPTR)qPriListTerminate,    (FUNCPTR)qPriListPutFromTail,    (FUNCPTR)qPriListGet,    (FUNCPTR)qPriListRemove,    (FUNCPTR)qPriListResort,    (FUNCPTR)qPriListAdvance,    (FUNCPTR)qPriListGetExpired,    (FUNCPTR)qPriListKey,    (FUNCPTR)qPriListCalibrate,    (FUNCPTR)qPriListInfo,    (FUNCPTR)qPriListEach,    &qPriListFromTailClass    };/* globals */Q_CLASS_ID qPriListClassId	   = &qPriListClass;Q_CLASS_ID qPriListFromTailClassId = &qPriListFromTailClass;/******************************************************************************** qPriListCreate - allocate and initialize a priority list queue** This routine allocates and initializes a priority list queue by allocating a* Q_PRI_HEAD structure from the free memory pool.** RETURNS:*  Pointer to a Q_PRI_HEAD, or*  NULL if out of memory.*/Q_PRI_HEAD *qPriListCreate (void)    {    Q_PRI_HEAD *pQPriHead = (Q_PRI_HEAD *) malloc (sizeof (Q_PRI_HEAD));    if (pQPriHead == NULL)	return (NULL);    qPriListInit (pQPriHead);    return (pQPriHead);    }/******************************************************************************** qPriListInit - initialize a priority list queue** This routine initializes the specified priority list queue.*/STATUS qPriListInit    (    Q_PRI_HEAD *pQPriHead    )    {    dllInit (pQPriHead);	 /* initialize doubly linked list */    return (OK);    }/******************************************************************************** qPriListDelete - delete a priority list queue** This routine deallocates memory associated with the queue.  All queued* nodes are lost.** RETURNS:*  OK, or*  ERROR if memory cannot be deallocated.*/STATUS qPriListDelete    (    Q_PRI_HEAD *pQPriHead    )    {    free ((char *) pQPriHead);    return OK;    }/******************************************************************************** qPriListTerminate - terminate a priority list queue** This routine terminates a priority list queue.  All queued nodes will be lost.** ARGSUSED*/STATUS qPriListTerminate    (    Q_PRI_HEAD *pQPriHead    )    {    return (OK);    }/********************************************************************************* qPriListPut - insert a node into a priority list queue** This routine inserts a node into a priority list queue.  The insertion is* based on the specified prioriyt key.  The lower the key the higher the* priority.*/void qPriListPut    (    Q_PRI_HEAD  *pQPriHead,    Q_PRI_NODE  *pQPriNode,    ULONG        key    )    {    FAST Q_PRI_NODE *pQNode = (Q_PRI_NODE *) DLL_FIRST (pQPriHead);    pQPriNode->key = key;    while (pQNode != NULL)        {	if (key < pQNode->key)		/* it will be last of same priority */	    {	    dllInsert (pQPriHead, DLL_PREVIOUS (&pQNode->node),		       &pQPriNode->node);	    return;	    }	pQNode = (Q_PRI_NODE *) DLL_NEXT (&pQNode->node);	}    dllInsert (pQPriHead, (DL_NODE *) DLL_LAST (pQPriHead), &pQPriNode->node);    }/********************************************************************************* qPriListPutFromTail - insert a node into a priority list queue from tail** This routine inserts a node into a priority list queue.  The insertion is* based on the specified prioriyt key.  The lower the key the higher the* priority.  Unlike qPriListPut(2), this routine searches for the correct* position in the queue from the queue's tail.  This is useful if the* caller has a priori knowledge that the key is of low priority.*/void qPriListPutFromTail    (    Q_PRI_HEAD  *pQPriHead,    Q_PRI_NODE  *pQPriNode,    ULONG        key    )    {    FAST Q_PRI_NODE *pQNode = (Q_PRI_NODE *) DLL_LAST (pQPriHead);    pQPriNode->key = key;    while (pQNode != NULL)        {	if (key >= pQNode->key)		/* it will be last of same priority */	    {	    dllInsert (pQPriHead, &pQNode->node, &pQPriNode->node);	    return;	    }	pQNode = (Q_PRI_NODE *) DLL_PREVIOUS (&pQNode->node);	}    dllInsert (pQPriHead, (DL_NODE *)NULL, &pQPriNode->node);    }/********************************************************************************* qPriListGet - remove and return first node in priority list queue** This routine removes and returns the first node in a priority list 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_NODE *qPriListGet    (    Q_PRI_HEAD *pQPriHead    )    {    if (DLL_EMPTY (pQPriHead))	return (NULL);    return ((Q_PRI_NODE *) dllGet (pQPriHead));    }/********************************************************************************* qPriListRemove - remove a node from a priority list queue** This routine removes a node from the specified priority list queue.*/STATUS qPriListRemove    (    Q_PRI_HEAD *pQPriHead,    Q_PRI_NODE *pQPriNode    )    {    dllRemove (pQPriHead, &pQPriNode->node);    return (OK);    }/********************************************************************************* qPriListResort - resort a node to a new position based on a new key** This routine resorts a node to a new position based on a new key.*/void qPriListResort    (    FAST Q_PRI_HEAD *pQPriHead,    FAST Q_PRI_NODE *pQPriNode,    FAST ULONG       newKey    )    {    FAST Q_PRI_NODE *pPrev = (Q_PRI_NODE *)DLL_PREVIOUS (&pQPriNode->node);    FAST Q_PRI_NODE *pNext = (Q_PRI_NODE *)DLL_NEXT (&pQPriNode->node);    if (((pPrev == NULL) || (newKey >= pPrev->key)) &&	((pNext == NULL) || (newKey <= pNext->key)))	{	pQPriNode->key = newKey;	}    else	{	qPriListRemove (pQPriHead, pQPriNode);	qPriListPut (pQPriHead, pQPriNode, newKey);	}    }/********************************************************************************* qPriListAdvance - advance a queues concept of time** Priority list queues need not keep track of time because nodes contain time of* expiration.  So this routine is a NOP.** NOMANUAL* ARGSUSED*/void qPriListAdvance    (    Q_PRI_HEAD *pQPriHead    )    {    /* Absolute queue so advancing key of lead node unnecessary */    }/********************************************************************************* qPriListGetExpired - return a time-to-fire expired node** This routine returns a time-to-fire expired node in a priority list 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_NODE *qPriListGetExpired    (    Q_PRI_HEAD *pQPriHead    )    {    FAST Q_PRI_NODE *pQPriNode = (Q_PRI_NODE *) DLL_FIRST (pQPriHead);    if ((pQPriNode != NULL) && (pQPriNode->key <= vxTicks))	return ((Q_PRI_NODE *) dllGet (pQPriHead));    else	return (NULL);    }/********************************************************************************* qPriListCalibrate - offset every node in a queue by some delta** This routine offsets every node in a priority list queue by some delta.  The* offset may either by positive or negative.*/void qPriListCalibrate    (    Q_PRI_HEAD *pQHead,         /* queue head of queue to calibrate nodes for */    ULONG       keyDelta        /* offset to add to each node's key */    )    {    FAST Q_PRI_NODE *pQPriNode;    for (pQPriNode = (Q_PRI_NODE *) DLL_FIRST (pQHead);         pQPriNode != NULL;	 pQPriNode = (Q_PRI_NODE *) DLL_NEXT (&pQPriNode->node))	{        pQPriNode->key += keyDelta;			/* offset key */	}    }/********************************************************************************* qPriListKey - return the key of a node** This routine returns the key of a node currently in a priority list queue.** RETURNS*  Node's key.*/ULONG qPriListKey    (    Q_PRI_NODE *pQPriNode,    int         keyType                 /* 0 = normal; 1 = time queue */    )    {    if (keyType == 0)	return (pQPriNode->key);    else	return (pQPriNode->key - vxTicks);    }/********************************************************************************* qPriListInfo - gather information on a priority list queue** This routine fills up to maxNodes elements of a nodeArray with nodes* currently in a priority list 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 list queue is returned.** RETURNS*  Number of node pointers copied into the nodeArray, or*  Number of nodes in priority list queue if nodeArray is NULL*/int qPriListInfo    (    Q_PRI_HEAD *pQPriHead,      /* priority queue to gather list for */    FAST int nodeArray[],       /* array of node pointers to be filled in */    FAST int maxNodes           /* max node pointers nodeArray can accomodate */    )    {    FAST Q_PRI_NODE *pQNode = (Q_PRI_NODE *) DLL_FIRST (pQPriHead);    FAST int *pElement  = nodeArray;    if (nodeArray == NULL)		/* NULL node array means return count */	return (dllCount (pQPriHead));    while ((pQNode != NULL) && (--maxNodes >= 0))	{	*(pElement++) = (int)pQNode;			/* fill in table */	pQNode = (Q_PRI_NODE *) DLL_NEXT (&pQNode->node);	/* next node */	}    return (pElement - nodeArray);	/* return count of active tasks */    }/********************************************************************************* qPriListEach - 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_NODE *pQNode;	/@ pointer to a queue node          @/*      int	  arg;		/@ arbitrary user-supplied argument @/* .CE* The user-supplied routine should return TRUE if qPriListEach (2) is to* continue calling it for each entry, or FALSE if it is done and* qPriListEach can exit.** RETURNS: NULL if traversed whole queue, or pointer to Q_PRI_NODE that*          qPriListEach stopped on.*/Q_PRI_NODE *qPriListEach    (    Q_PRI_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 Q_PRI_NODE *pQNode = (Q_PRI_NODE *) DLL_FIRST (pQHead);    while ((pQNode != NULL) && ((* routine) (pQNode, routineArg)))	pQNode = (Q_PRI_NODE *) DLL_NEXT (&pQNode->node);    return (pQNode);			/* return node we ended with */    }