392 lines
12 KiB
C
392 lines
12 KiB
C
/* qLib.h - multi-way queue library header */
|
|
|
|
/*
|
|
* Copyright (c) 1989-1993, 2004-2005 Wind River Systems, Inc.
|
|
*
|
|
* The right to copy, distribute, modify or otherwise make use
|
|
* of this software may be licensed only pursuant to the terms
|
|
* of an applicable Wind River license agreement.
|
|
*/
|
|
|
|
/*
|
|
modification history
|
|
--------------------
|
|
02j,29sep05,jln remove HIDDEN comments of Q_NODE and Q_HEAD
|
|
02i,30may05,jln Added qPxPriBMapClassId
|
|
02h,10mar05,yvp Moved MAX_ARGS defn from qLib.c. Added qNullRtn prototype.
|
|
02g,25may04,dbt Fixed Q_ADVANCEN to make sure key will never be less than 0
|
|
02f,30mar04,ans added 'attribute' semantics to Q_HEAD
|
|
02e,25mar04,hya added Q_ADVANCEN definition.
|
|
02d,15oct93,cd added #ifndef _ASMLANGUAGE.
|
|
02c,22sep92,rrr added support for c++
|
|
02b,19jul92,pme made qRemove return STATUS.
|
|
02a,04jul92,jcf cleaned up.
|
|
01i,26may92,rrr the tree shuffle
|
|
01h,04oct91,rrr passed through the ansification filter
|
|
-fixed #else and #endif
|
|
-changed copyright notice
|
|
01g,10jun91.del added pragma for gnu960 alignment.
|
|
01f,05apr91,gae added NOMANUAL to avoid fooling mangen.
|
|
01e,05oct90,shl added copyright notice.
|
|
made #endif ANSI style.
|
|
01d,02oct90,jcf removed nested comments.
|
|
01c,05jul90,jcf added Q_CALIBRATE.
|
|
01b,26jun90,jcf added definition of all queue class ids/types.
|
|
remove includes of all queue classes.
|
|
defined Q_NODE/Q_HEAD as independent structure.
|
|
added Q_RESORT().
|
|
01a,21oct89,jcf written.
|
|
*/
|
|
|
|
#ifndef __INCqLibh
|
|
#define __INCqLibh
|
|
|
|
#ifdef __cplusplus
|
|
extern "C" {
|
|
#endif
|
|
|
|
#include <vxWorks.h>
|
|
#include <vwModNum.h>
|
|
#include <qClass.h>
|
|
|
|
#define MAX_ARGS 10 /* number of variable arguments */
|
|
|
|
/* status codes */
|
|
|
|
#define S_qLib_Q_CLASS_ID_ERROR (M_qLib | 1)
|
|
|
|
#ifndef _ASMLANGUAGE
|
|
|
|
/* queue classes */
|
|
|
|
IMPORT Q_CLASS_ID qFifoClassId;
|
|
IMPORT Q_CLASS_ID qPriListClassId;
|
|
IMPORT Q_CLASS_ID qPriListFromTailClassId;
|
|
IMPORT Q_CLASS_ID qPriDeltaClassId;
|
|
IMPORT Q_CLASS_ID qPriHeapClassId;
|
|
IMPORT Q_CLASS_ID qPriBMapClassId;
|
|
IMPORT Q_CLASS_ID qPxPriBMapClassId;
|
|
|
|
/* queue types */
|
|
|
|
#define Q_FIFO qFifoClassId
|
|
#define Q_PRI_LIST qPriListClassId
|
|
#define Q_PRI_LIST_FROM_TAIL qPriListFromTailClassId
|
|
#define Q_PRI_DELTA qPriDeltaClassId
|
|
#define Q_PRI_HEAP qPriHeapClassId
|
|
#define Q_PRI_BMAP qPriBMapClassId
|
|
#define Q_PX_PRI_BMAP qPxPriBMapClassId
|
|
|
|
/* All queue class nodes must not exceed the sizeof (Q_NODE). If larger data
|
|
* structures must be used, use one of the private fields as pointer to provide
|
|
* a level on indirection so the size of Q_NODE is not exceeded.
|
|
*/
|
|
|
|
typedef struct /* Q_NODE */
|
|
{
|
|
UINT qPriv1; /* use is queue type dependent */
|
|
UINT qPriv2; /* use is queue type dependent */
|
|
UINT qPriv3; /* use is queue type dependent */
|
|
UINT qPriv4; /* use is queue type dependent */
|
|
} Q_NODE;
|
|
|
|
|
|
/* All queue classes must not exceed the sizeof (Q_HEAD). If larger data
|
|
* structures must be used, use one of the private fields as pointer to provide
|
|
* a level on indirection so the size of Q_HEAD is not exceeded.
|
|
*
|
|
* The first field in the Q_HEAD must contain the highest priority Q_NODE.
|
|
* The routine qFirst () makes this assumption. The scheduler does a qFirst
|
|
* on the ready queue as part of its scheduling.
|
|
*/
|
|
|
|
typedef struct /* Q_HEAD */
|
|
{
|
|
Q_NODE *pFirstNode; /* first node in queue based on key */
|
|
UINT qPriv1; /* use is queue type dependent */
|
|
UINT qPriv2; /* use is queue type dependent */
|
|
Q_CLASS *pQClass; /* pointer to queue class */
|
|
} Q_HEAD;
|
|
|
|
|
|
/*
|
|
* Queue can have attributes. The qPriv2 member of Q_HEAD represents the
|
|
* queue attribute. This imposes the restriction that only queue classes
|
|
* whose queue head are two words long can have attributes.
|
|
* The attributes supported are
|
|
* 1) Queue interruptibiliy
|
|
* QUEUE_INTERRUPTIBLE implies that the task pended on this queue can
|
|
* be made ready by a signal. QUEUE_NONINTERRUPTIBLE is the negate of
|
|
* QUEUE_INTERRUPTIBLE. By default, queue interrupt-ability attribute for
|
|
* a queue is QUEUE_NONINTERRUPTIBLE.
|
|
*
|
|
* Currently only Q_PRI_LIST , Q_FIFO_HEAD, Q_PRI_LIST_FROM_TAIL have
|
|
* the queue attribute support.
|
|
*/
|
|
|
|
#define QUEUE_INTERRUPTIBLE 1
|
|
#define QUEUE_NONINTERRUPTIBLE 0
|
|
#define QUEUE_ATTRIBUTE_MASK 0x1
|
|
|
|
#define Q_ATTRIBUTE_GET(qHead) (((Q_HEAD *)(qHead))->qPriv2)
|
|
#define Q_ATTRIBUTE_SET(qHead, value) (((Q_HEAD *)(qHead))->qPriv2 = \
|
|
(UINT)(value))
|
|
#define IS_Q_ATTRIBUTE_OK(value) ((value) == QUEUE_INTERRUPTIBLE || \
|
|
(value) == QUEUE_NONINTERRUPTIBLE)
|
|
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_FIRST - return first node in multi-way queue
|
|
*
|
|
* This routine returns a pointer to the first node in the specified multi-way
|
|
* queue head. If the queue is empty, NULL is returned.
|
|
*
|
|
* RETURNS
|
|
* Pointer to first queue node in queue head, or
|
|
* NULL if queue is empty.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_FIRST(pQHead) \
|
|
((Q_NODE *)(((Q_HEAD *)(pQHead))->pFirstNode))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_PUT - insert a node into a multi-way queue
|
|
*
|
|
* This routine inserts a node into a multi-way queue. The insertion is based
|
|
* on the key and the underlying queue class.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_PUT(pQHead,pQNode,key) \
|
|
(*(((Q_HEAD *)(pQHead))->pQClass->putRtn)) \
|
|
(((Q_HEAD *)(pQHead)), ((Q_NODE *)(pQNode)), (key))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_GET - remove and return first node in multi-way queue
|
|
*
|
|
* This routine removes and returns the first node in a multi-way queue. If
|
|
* the queue is empty, NULL is returned.
|
|
*
|
|
* RETURNS
|
|
* Pointer to first queue node in queue head, or
|
|
* NULL if queue is empty.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_GET(pQHead) \
|
|
((Q_NODE *)((*(((Q_HEAD *)(pQHead))->pQClass->getRtn)) \
|
|
((Q_HEAD *)(pQHead))))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_REMOVE - remove a node from a multi-way queue
|
|
*
|
|
* This routine removes a node from the specified multi-way queue.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_REMOVE(pQHead,pQNode) \
|
|
(*(((Q_HEAD *)(pQHead))->pQClass->removeRtn)) \
|
|
(((Q_HEAD *)(pQHead)), ((Q_NODE *)(pQNode)))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_RESORT - 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. It can
|
|
* be used to change the priority of a queued element, for instance.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_RESORT(pQHead,pQNode,newKey) \
|
|
(*(((Q_HEAD *)(pQHead))->pQClass->resortRtn)) \
|
|
(((Q_HEAD *)(pQHead)), ((Q_NODE *)(pQNode)), ((ULONG)(newKey)))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_ADVANCE - advance a queues concept of time (timer queues only)
|
|
*
|
|
* Multi-way queues that keep nodes prioritized by time-to-fire utilize this
|
|
* routine to advance time. It is usually called from within a clock-tick
|
|
* interrupt service routine.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_ADVANCE(pQHead) \
|
|
(*(((Q_HEAD *)(pQHead))->pQClass->advanceRtn)) \
|
|
(((Q_HEAD *)(pQHead)))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_ADVANCEN - advance a queues concept of time by N tick (timer queues only)
|
|
*
|
|
* Time queues that keep nodes prioritized by time-to-fire utilize this
|
|
* routine to advance time by N tick after e.g., a power save sleep.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_ADVANCEN(pQHead, n) \
|
|
if (((Q_HEAD *)pQHead)->pQClass->valid == qPriDeltaClassId && \
|
|
((Q_HEAD *)pQHead)->pFirstNode != NULL) \
|
|
{ \
|
|
if (n > ((Q_PRI_NODE *)((Q_HEAD *)pQHead)->pFirstNode)->key) \
|
|
((Q_PRI_NODE *)((Q_HEAD *)pQHead)->pFirstNode)->key = 0; \
|
|
else \
|
|
((Q_PRI_NODE *)((Q_HEAD *)pQHead)->pFirstNode)->key -= n; \
|
|
}
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_GET_EXPIRED - return a time-to-fire expired node
|
|
*
|
|
* This routine returns a time-to-fire expired node in a multi-way timer queue.
|
|
* Expired nodes result from a qAdvance(2) advancing a node beyond its delay.
|
|
* As many nodes may expire on a single qAdvance(2), 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.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_GET_EXPIRED(pQHead) \
|
|
((Q_NODE *)((*(((Q_HEAD *)(pQHead))->pQClass->getExpiredRtn)) \
|
|
((Q_HEAD *)(pQHead))))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_KEY - return the key of a node
|
|
*
|
|
* This routine returns the key of a node currently in a multi-way queue. The
|
|
* keyType determines key style on certain queue classes.
|
|
*
|
|
* RETURNS
|
|
* Node's key.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_KEY(pQHead,pQNode,keyType) \
|
|
(*(((Q_HEAD *)(pQHead))->pQClass->keyRtn)) \
|
|
(((Q_NODE *)(pQNode)), ((int)(keyType)))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_CALIBRATE - offset every node in a queue by some delta
|
|
*
|
|
* This routine offsets every node in a multi-way queue by some delta. The
|
|
* offset may either by positive or negative.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_CALIBRATE(pQHead,keyDelta) \
|
|
(*(((Q_HEAD *)(pQHead))->pQClass->calibrateRtn)) \
|
|
(((Q_HEAD *)(pQHead)), ((int)(keyDelta)))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_INFO - gather information on a multi-way 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 multi-way queue is returned.
|
|
*
|
|
* RETURNS
|
|
* Number of node pointers copied into the nodeArray, or
|
|
* Number of nodes in multi-way queue if nodeArray is NULL
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_INFO(pQHead,nodeArray,maxNodes) \
|
|
(*(((Q_HEAD *)(pQHead))->pQClass->infoRtn)) \
|
|
(((Q_HEAD *)(pQHead)),((int *)(nodeArray)),((int)(maxNodes)))
|
|
|
|
/*******************************************************************************
|
|
*
|
|
* Q_EACH - 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_NODE *pQNode; * pointer to a queue node *
|
|
* int arg; * arbitrary user-supplied argument *
|
|
* \ce
|
|
* The user-supplied routine should return TRUE if qEach (2) is to continue
|
|
* calling it for each entry, or FALSE if it is done and qEach can exit.
|
|
*
|
|
* RETURNS: NULL if traversed whole queue, or pointer to Q_NODE that
|
|
* qEach ended with.
|
|
*
|
|
* \NOMANUAL
|
|
*/
|
|
|
|
#define Q_EACH(pQHead,routine,routineArg) \
|
|
((Q_NODE *)((*(((Q_HEAD *)(pQHead))->pQClass->eachRtn)) \
|
|
(((Q_HEAD *)(pQHead)),((FUNCPTR)(routine)),((int)(routineArg)))))
|
|
|
|
#if defined(__STDC__) || defined(__cplusplus)
|
|
|
|
extern Q_HEAD * qCreate (Q_CLASS *pQClass, ...);
|
|
extern Q_NODE * qEach (Q_HEAD *pQHead, FUNCPTR routine, int routineArg);
|
|
extern Q_NODE * qFirst (Q_HEAD *pQHead);
|
|
extern Q_NODE * qGet (Q_HEAD *pQHead);
|
|
extern Q_NODE * qGetExpired (Q_HEAD *pQHead);
|
|
extern STATUS qDelete (Q_HEAD *pQHead);
|
|
extern STATUS qInit (Q_HEAD *pQHead, Q_CLASS *pQClass, ...);
|
|
extern STATUS qTerminate (Q_HEAD *pQHead);
|
|
extern ULONG qKey (Q_HEAD *pQHead, Q_NODE *pQNode, int keyType);
|
|
extern int qInfo (Q_HEAD *pQHead, Q_NODE *nodeArray [ ], int maxNodes);
|
|
extern void qAdvance (Q_HEAD *pQHead);
|
|
extern void qCalibrate (Q_HEAD *pQHead, ULONG keyDelta);
|
|
extern void qPut (Q_HEAD *pQHead, Q_NODE *pQNode, ULONG key);
|
|
extern STATUS qRemove (Q_HEAD *pQHead, Q_NODE *pQNode);
|
|
extern void qResort (Q_HEAD *pQHead, Q_NODE *pQNode, ULONG newKey);
|
|
extern STATUS qNullRtn (void);
|
|
|
|
#else /* __STDC__ */
|
|
|
|
extern Q_HEAD * qCreate ();
|
|
extern Q_NODE * qEach ();
|
|
extern Q_NODE * qFirst ();
|
|
extern Q_NODE * qGet ();
|
|
extern Q_NODE * qGetExpired ();
|
|
extern STATUS qDelete ();
|
|
extern STATUS qInit ();
|
|
extern STATUS qTerminate ();
|
|
extern ULONG qKey ();
|
|
extern int qInfo ();
|
|
extern void qAdvance ();
|
|
extern void qCalibrate ();
|
|
extern void qPut ();
|
|
extern STATUS qRemove ();
|
|
extern void qResort ();
|
|
extern STATUS qNullRtn ();
|
|
|
|
#endif /* __STDC__ */
|
|
|
|
#endif /* _ASMLANGUAGE */
|
|
|
|
#ifdef __cplusplus
|
|
}
|
|
#endif
|
|
|
|
#endif /* __INCqLibh */
|