/* qPriDeltaLib.c - priority queue with relative priority sorting library *//* Copyright 1984-1992 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history--------------------01h,19jul92,pme  made qPriDeltaRemove 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 null routine for calibrateRtn field in Q_CLASS.01b,26jun90,jcf	 fixed queue class definition.01a,14jun89,jcf	 written.*//*DESCRIPTIONThis library contains routines to manage a priority queue.  The queue ismaintained in priority order with each node key a priority delta to the nodeahead of it.  This queue performs a qPriDeltaPut() operation preportional intime with number of nodes in the queue.  This queue is used for timer queues.This queue complies with the multi-way queue data structures and thus may beutilized by any multi-way queue.  The priority delta multi-way queueclass is accessed by the global id qPriDeltaClassId.SEE ALSO: qLib.*/#include "vxWorks.h"#include "qClass.h"#include "qPriDeltaLib.h"#include "stdlib.h"IMPORT ULONG vxTicks;		/* current time in ticks *//* forward static functions */static STATUS qPriDeltaNullRtn (void);/* locals */LOCAL Q_CLASS qPriDeltaClass =    {    (FUNCPTR)qPriDeltaCreate,    (FUNCPTR)qPriDeltaInit,    (FUNCPTR)qPriDeltaDelete,    (FUNCPTR)qPriDeltaTerminate,    (FUNCPTR)qPriDeltaPut,    (FUNCPTR)qPriDeltaGet,    (FUNCPTR)qPriDeltaRemove,    (FUNCPTR)qPriDeltaResort,    (FUNCPTR)qPriDeltaAdvance,    (FUNCPTR)qPriDeltaGetExpired,    (FUNCPTR)qPriDeltaKey,    (FUNCPTR)qPriDeltaNullRtn,    (FUNCPTR)qPriDeltaInfo,    (FUNCPTR)qPriDeltaEach,    &qPriDeltaClass    };/* globals */Q_CLASS_ID qPriDeltaClassId = &qPriDeltaClass;/******************************************************************************** qPriDeltaCreate - allocate and initialize a priority delta queue** This routine allocates and initializes a priority delta 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 *qPriDeltaCreate (void)    {    Q_PRI_HEAD *pQPriHead = (Q_PRI_HEAD *) malloc (sizeof (Q_PRI_HEAD));    if (pQPriHead == NULL)	return (NULL);    qPriDeltaInit (pQPriHead);    return (pQPriHead);    }/******************************************************************************** qPriDeltaInit - initialize a priority delta queue** This routine initializes the specified priority delta queue.*/STATUS qPriDeltaInit    (    Q_PRI_HEAD *pQPriHead    )    {    dllInit (pQPriHead);	 /* initialize doubly linked list */    return (OK);    }/******************************************************************************** qPriDeltaDelete - delete a priority delta queue** This routine deallocates memory associated with the queue.  All queued* nodes are lost.** RETURNS:*  OK, or*  ERROR if memory cannot be deallocated.*/STATUS qPriDeltaDelete    (    Q_PRI_HEAD *pQPriHead    )    {    free ((char *) pQPriHead);    return OK;    }/******************************************************************************** qPriDeltaTerminate - terminate a priority delta queue** This routine terminates a priority delta queue.  All queued nodes are lost.** ARGSUSED*/STATUS qPriDeltaTerminate    (    Q_PRI_HEAD *pQPriHead    )    {    return (OK);    }/********************************************************************************* qPriDeltaPut - insert a node into a priority delta queue** This routine inserts a node into a priority delta queue.  The insertion is* based on the priority key.  Lower key values are higher in priority.*/void qPriDeltaPut    (    Q_PRI_HEAD  *pQPriHead,    Q_PRI_NODE  *pQPriNode,    ULONG       key    )    {    FAST Q_PRI_NODE *pQNode = (Q_PRI_NODE *) DLL_FIRST (pQPriHead);    pQPriNode->key = key - vxTicks;	/* relative queue keeps delta time */    while (pQNode != NULL)		/* empty list? */        {	if (pQPriNode->key < pQNode->key)	    {	    /* We've reached the place in the delta queue to insert this task */	    dllInsert (pQPriHead, DLL_PREVIOUS (&pQNode->node),		       &pQPriNode->node);	    /* Now decrement the delta key of the guy behind us. */	    pQNode->key -= pQPriNode->key;	    return;				/* we're done */	    }	pQPriNode->key -= pQNode->key;	pQNode = (Q_PRI_NODE *) DLL_NEXT (&pQNode->node);	}    /* if we fall through, add to end of delta q */    dllInsert (pQPriHead, (DL_NODE *) DLL_LAST (pQPriHead), &pQPriNode->node);    }/********************************************************************************* qPriDeltaGet - remove and return first node in priority delta queue** This routine removes and returns the first node in a priority delta 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 *qPriDeltaGet    (    Q_PRI_HEAD *pQPriHead    )    {    if (DLL_EMPTY (pQPriHead))	return (NULL);    return ((Q_PRI_NODE *) dllGet (pQPriHead));    }/********************************************************************************* qPriDeltaRemove - remove a node from a priority delta queue** This routine removes a node from the specified priority delta queue.*/STATUS qPriDeltaRemove    (    Q_PRI_HEAD *pQPriHead,    Q_PRI_NODE *pQPriNode    )    {    Q_PRI_NODE *pNextNode = (Q_PRI_NODE *) DLL_NEXT (&pQPriNode->node);    if (pNextNode != NULL)	pNextNode->key += pQPriNode->key; /* add key to next node */    dllRemove (pQPriHead, &pQPriNode->node);    return (OK);    }/********************************************************************************* qPriDeltaResort - 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 priority key.*/void qPriDeltaResort    (    Q_PRI_HEAD *pQPriHead,    Q_PRI_NODE *pQPriNode,    ULONG       newKey    )    {    qPriDeltaRemove (pQPriHead, pQPriNode);    qPriDeltaPut (pQPriHead, pQPriNode, newKey);    }/********************************************************************************* qPriDeltaAdvance - advance a queues concept of time** Priority delta queues keep nodes prioritized by time-to-fire.  The library* utilizes this routine to advance time.  It is usually called from within a* clock-tick interrupt service routine.*/void qPriDeltaAdvance    (    Q_PRI_HEAD *pQPriHead    )    {    FAST Q_PRI_NODE *pQPriNode = (Q_PRI_NODE *) DLL_FIRST (pQPriHead);    if (pQPriNode != NULL)	pQPriNode->key --;    }/********************************************************************************* qPriDeltaGetExpired - return a time-to-fire expired node** This routine returns a time-to-fire expired node in a priority delta timer* queue.  Expired nodes result from a qPriDeltaAdvance(2) advancing a node* beyond its delay.  As many nodes may expire on a single qPriDeltaAdvance(2),* this routine should be called within 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 *qPriDeltaGetExpired    (    Q_PRI_HEAD *pQPriHead    )    {    FAST Q_PRI_NODE *pQPriNode = (Q_PRI_NODE *) DLL_FIRST (pQPriHead);    if (pQPriNode != NULL)	{	if (pQPriNode->key != 0)	    pQPriNode = NULL;	else	    qPriDeltaRemove (pQPriHead, pQPriNode);	/* get off delay list */	}    return (pQPriNode);    }/********************************************************************************* qPriDeltaKey - return the key of a node** This routine returns the key of a node currently in a priority delta queue.** RETURNS*  Node's key.** ARGSUSED*/ULONG qPriDeltaKey    (    Q_PRI_NODE  *pQPriNode      /* node to get key for */    )    {    FAST ULONG sum = 0;    while (pQPriNode != NULL)        {	sum += pQPriNode->key;	pQPriNode = (Q_PRI_NODE *) DLL_PREVIOUS (&pQPriNode->node);	}    return (sum);	/* return key */    }/********************************************************************************* qPriDeltaInfo - gather information on a priority delta queue** This routine fills up to maxNodes elements of a nodeArray with nodes* currently in a multi-way 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 delta 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 qPriDeltaInfo    (    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 */    }/********************************************************************************* qPriDeltaEach - 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 qPriDeltaEach (2) is to* continue calling it for each entry, or FALSE if it is done and* qPriDeltaEach can exit.** RETURNS: NULL if traversed whole queue, or pointer to Q_PRI_NODE that*          qPriDeltaEach stopped on.*/Q_PRI_NODE *qPriDeltaEach    (    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 */    }/********************************************************************************* qPriDeltaNullRtn - nop that returns OK** This routine does nothing and returns OK.  It is used to by the queue class* structure for unsupported functions.*/LOCAL STATUS qPriDeltaNullRtn (void)    {    return (OK);    }