You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
852 lines
16 KiB
852 lines
16 KiB
/**
|
|
* Copyright (c) 2019, The Linux Foundation. All rights reserved.
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions are
|
|
* met:
|
|
* * Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
* * Redistributions in binary form must reproduce the above
|
|
* copyright notice, this list of conditions and the following
|
|
* disclaimer in the documentation and/or other materials provided
|
|
* with the distribution.
|
|
* * Neither the name of The Linux Foundation nor the names of its
|
|
* contributors may be used to endorse or promote products derived
|
|
* from this software without specific prior written permission.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
|
|
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
|
|
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
|
|
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
|
|
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
|
|
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
|
|
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
|
|
* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
|
|
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
|
|
* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
|
|
* IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
*/
|
|
|
|
/*===========================================================================
|
|
|
|
FILE: AEEQList.h
|
|
|
|
GENERAL DESCRIPTION: Doubly-linked circular list implementation
|
|
|
|
===========================================================================*/
|
|
#ifndef _AEEQLIST_H_
|
|
#define _AEEQLIST_H_
|
|
|
|
|
|
typedef struct QNode QNode;
|
|
struct QNode {
|
|
QNode *pNext;
|
|
QNode *pPrev;
|
|
};
|
|
|
|
#define QLIST_DEFINE_INIT(f) QList f = { { &f.n, &f.n } }
|
|
|
|
typedef struct QList QList;
|
|
struct QList {
|
|
QNode n;
|
|
};
|
|
|
|
|
|
|
|
static __inline void QNode_InsPrev(QNode *me, QNode *pn)
|
|
{
|
|
QNode *pPrev = me->pPrev;
|
|
|
|
pn->pNext = me;
|
|
pn->pPrev = pPrev;
|
|
pPrev->pNext = pn;
|
|
me->pPrev = pn;
|
|
}
|
|
|
|
|
|
static __inline void QNode_InsNext(QNode *me, QNode *pn)
|
|
{
|
|
QNode *pNext = me->pNext;
|
|
|
|
pn->pPrev = me;
|
|
pn->pNext = pNext;
|
|
pNext->pPrev = pn;
|
|
me->pNext = pn;
|
|
}
|
|
|
|
|
|
|
|
static __inline void QNode_Dequeue(QNode *me)
|
|
{
|
|
QNode *pNext = me->pNext;
|
|
QNode *pPrev = me->pPrev;
|
|
|
|
pPrev->pNext = pNext;
|
|
pNext->pPrev = pPrev;
|
|
}
|
|
|
|
static __inline void QNode_CtorZ(QNode *me)
|
|
{
|
|
me->pNext = me->pPrev = 0;
|
|
}
|
|
|
|
static __inline int QNode_IsQueuedZ(QNode *me)
|
|
{
|
|
return (0 != me->pNext);
|
|
}
|
|
|
|
static __inline void QNode_DequeueZ(QNode *me)
|
|
{
|
|
if (QNode_IsQueuedZ(me)) {
|
|
QNode_Dequeue(me);
|
|
me->pNext = me->pPrev = 0;
|
|
}
|
|
}
|
|
|
|
//--------------------------------------------------------------------
|
|
//-- QList functions ----------------------------------------------
|
|
//--------------------------------------------------------------------
|
|
|
|
|
|
static __inline void QList_Zero(QList *me)
|
|
{
|
|
me->n.pNext = me->n.pPrev = &me->n;
|
|
}
|
|
|
|
|
|
static __inline void QList_Ctor(QList *me)
|
|
{
|
|
QList_Zero(me);
|
|
}
|
|
|
|
|
|
static __inline int QList_IsEmpty(QList *me)
|
|
{
|
|
return me->n.pNext == &me->n;
|
|
}
|
|
|
|
static __inline int QList_IsNull(QList *me)
|
|
{
|
|
return ((0 == me->n.pNext) && (0 == me->n.pPrev));
|
|
}
|
|
|
|
|
|
static __inline void QList_AppendNode(QList *me, QNode *pn)
|
|
{
|
|
QNode_InsPrev(&me->n, pn);
|
|
}
|
|
|
|
|
|
static __inline void QList_PrependNode(QList *me, QNode *pn)
|
|
{
|
|
QNode_InsNext(&me->n, pn);
|
|
}
|
|
|
|
|
|
static __inline void QList_CtorFrom(QList *me, QList *psrc)
|
|
{
|
|
QNode *s = &psrc->n;
|
|
QNode *d = &me->n;
|
|
|
|
s->pNext->pPrev = d;
|
|
d->pPrev = s->pPrev;
|
|
d->pNext = s->pNext;
|
|
s->pPrev->pNext = d;
|
|
|
|
QList_Zero(psrc);
|
|
}
|
|
|
|
|
|
|
|
static __inline void QList_AppendList(QList *me, QList *psrc)
|
|
{
|
|
QNode *s = &psrc->n;
|
|
QNode *d = &me->n;
|
|
QNode *dp = d->pPrev;
|
|
QNode *sn = s->pNext;
|
|
QNode *sp;
|
|
|
|
sn->pPrev = dp;
|
|
dp->pNext = sn;
|
|
d->pPrev = (sp = s->pPrev);
|
|
sp->pNext = d;
|
|
|
|
QList_Zero(psrc);
|
|
}
|
|
|
|
|
|
#define QLIST_FOR_ALL(pList, pNode) \
|
|
for ((pNode) = (pList)->n.pNext; \
|
|
(pNode) != &(pList)->n; \
|
|
(pNode) = (pNode)->pNext)
|
|
|
|
#define QLIST_FOR_REST(pList, pNode) \
|
|
for (; \
|
|
(pNode) != &(pList)->n; \
|
|
(pNode) = (pNode)->pNext)
|
|
|
|
#define QLIST_REV_FOR_ALL(pList, pNode) \
|
|
for ((pNode) = (pList)->n.pPrev; \
|
|
(pNode) != &(pList)->n; \
|
|
(pNode) = (pNode)->pPrev)
|
|
|
|
#define QLIST_REV_FOR_REST(pList, pNode) \
|
|
for (; \
|
|
(pNode) != &(pList)->n; \
|
|
(pNode) = (pNode)->pPrev)
|
|
|
|
/* Allows dequeing QNodes during iteration */
|
|
#define QLIST_NEXTSAFE_FOR_ALL(pList, pNode, pNodeNext) \
|
|
for ((pNode) = (pList)->n.pNext, (pNodeNext) = (pNode)->pNext; \
|
|
(pNode) != &(pList)->n; \
|
|
(pNode) = (pNodeNext), (pNodeNext) = (pNode)->pNext)
|
|
|
|
static __inline QNode *QList_GetFirst(QList *me)
|
|
{
|
|
QNode *pn = me->n.pNext;
|
|
|
|
return (pn == &me->n ? 0 : pn);
|
|
}
|
|
|
|
static __inline QNode *QList_GetLast(QList *me)
|
|
{
|
|
QNode *pn = me->n.pPrev;
|
|
|
|
return (pn == &me->n ? 0 : pn);
|
|
}
|
|
|
|
static __inline QNode *QList_Pop(QList *me)
|
|
{
|
|
QNode *pn = me->n.pNext;
|
|
QNode *pnn = pn->pNext;
|
|
|
|
me->n.pNext = pnn;
|
|
pnn->pPrev = &me->n;
|
|
|
|
return (pn == &me->n ? 0 : pn);
|
|
}
|
|
|
|
static __inline QNode *QList_PopZ(QList *me)
|
|
{
|
|
QNode *pn = QList_Pop(me);
|
|
if (0 != pn) {
|
|
QNode_CtorZ(pn);
|
|
}
|
|
return pn;
|
|
}
|
|
|
|
static __inline QNode *QList_PopLast(QList *me)
|
|
{
|
|
QNode *pp = me->n.pPrev;
|
|
QNode *ppp = pp->pPrev;
|
|
|
|
me->n.pPrev = ppp;
|
|
ppp->pNext = &me->n;
|
|
|
|
return (pp == &me->n ? 0 : pp);
|
|
}
|
|
|
|
static __inline QNode *QList_PopLastZ(QList *me)
|
|
{
|
|
QNode *pn = QList_PopLast(me);
|
|
if (0 != pn) {
|
|
QNode_CtorZ(pn);
|
|
}
|
|
return pn;
|
|
}
|
|
|
|
/*=====================================================================
|
|
=======================================================================
|
|
DATA STRUCTURE DOCUMENTATION
|
|
=======================================================================
|
|
|
|
QNode
|
|
|
|
Description:
|
|
Qnode is the structure that is queued. One or more Qnodes may be
|
|
embedded in other structures. An object can contain multiple QNodes if
|
|
it needs to be in different lists at the same time.
|
|
|
|
Definition:
|
|
|
|
typedef struct QNode QNode;
|
|
struct QNode {
|
|
QNode *pNext;
|
|
QNode *pPrev;
|
|
};
|
|
|
|
Members:
|
|
|
|
See Also:
|
|
|
|
=======================================================================
|
|
|
|
QList
|
|
|
|
Description:
|
|
QList keeps a doubly-linked list of QNode structures.
|
|
Each queue is represented by a 'head' node, not a head pointer,
|
|
simplifying and streamlining many operations.
|
|
Because it is doubly-linked it permits constant-time insertion or removal
|
|
of items or of entire queues.
|
|
Because it is circular it permits constant-time operations at both the
|
|
tail and the head of the queue. Circularity also streamlines some
|
|
operations by eliminating conditional branches.
|
|
|
|
General rules:
|
|
QLists are always in a defined state; they should be constructed
|
|
before use, using one of the supplied Ctor...() functions.
|
|
QNodes do not track queued vs. unqueued state. The client should
|
|
never dequeue an un-queued node or queue an already-queued node.
|
|
When not queued, QNode internal state is undefined. A client may
|
|
implement marking and assertion externally.
|
|
|
|
Definition:
|
|
|
|
typedef struct QList QList;
|
|
struct QList {
|
|
QNode n;
|
|
};
|
|
|
|
Members:
|
|
|
|
See Also:
|
|
|
|
=======================================================================
|
|
INTERFACE DOCUMENTATION
|
|
=======================================================================
|
|
QNode Interface
|
|
|
|
QNode is a statically-linked interface.
|
|
|
|
=======================================================================
|
|
QNode_CtorZ()
|
|
|
|
Description:
|
|
Zero initialize a QNode.
|
|
|
|
Prototype:
|
|
|
|
void QNode_CtorZ(QNode *me);
|
|
|
|
Parameters:
|
|
me: the QNode
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
QNode_IsQueued(), QNode_DequeueZ(), QList_PopZ()
|
|
|
|
=======================================================================
|
|
QNode_IsQueuedZ()
|
|
|
|
Description:
|
|
Whether a QNode belongs in a Queue.
|
|
|
|
Prototype:
|
|
|
|
int QNode_IsQueuedZ(QNode *me);
|
|
|
|
Parameters:
|
|
me: the QNode
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
Does not work if a node needs to live at address 0x0.
|
|
|
|
See Also:
|
|
QNode_CtorZ(), QNode_DequeueZ(), QList_PopZ()
|
|
|
|
=======================================================================
|
|
QNode_DequeueZ()
|
|
|
|
Description:
|
|
Dequeue a QNode if it is in a queue. Idempotent operation.
|
|
|
|
Prototype:
|
|
|
|
void QNode_DequeueZ(QNode *me);
|
|
|
|
Parameters:
|
|
me: the QNode
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
QNode_CtorZ(), QNode_IsQueued(), QList_PopZ()
|
|
|
|
=======================================================================
|
|
|
|
QNode_InsPrev()
|
|
|
|
Description:
|
|
insert a node before this one.
|
|
|
|
Prototype:
|
|
static __inline void QNode_InsPrev(QNode *me, QNode *pn)
|
|
|
|
Parameters:
|
|
me: the QNode
|
|
pn: the node to be inserted.
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
|
|
QNode_InsNext()
|
|
|
|
Description:
|
|
insert a node after this one.
|
|
|
|
Prototype:
|
|
static __inline void QNode_InsNext(QNode *me, QNode *pn)
|
|
|
|
Parameters:
|
|
me: the QNode
|
|
pn: the node to be inserted.
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QNode_Dequeue()
|
|
|
|
Description:
|
|
dequeue this node.
|
|
|
|
Prototype:
|
|
static __inline void QNode_Dequeue(QNode *me)
|
|
|
|
Parameters:
|
|
me: the QNode to be dequeued
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QList Interface
|
|
|
|
QList is a statically-linked interface. It provides a Queue of
|
|
doubly linked nodes.
|
|
|
|
=======================================================================
|
|
QList_Zero()
|
|
|
|
Description:
|
|
discard all queued nodes.
|
|
|
|
Prototype:
|
|
|
|
void QList_Zero(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QList_Ctor()
|
|
|
|
Description:
|
|
Initialize a queue to an empty state
|
|
|
|
Prototype:
|
|
|
|
void QList_Ctor(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QList_IsEmpty()
|
|
|
|
Description:
|
|
Check whether queue is empty.
|
|
|
|
Prototype:
|
|
|
|
int QList_IsEmpty(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
TRUE if queue is empty.
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QList_AppendNode()
|
|
|
|
Description:
|
|
Append the node to the queue. Make it the last 'next' (and the
|
|
first 'prev')
|
|
|
|
Prototype:
|
|
|
|
void QList_AppendNode(QList *me, QNode *pn)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
pn: the node to append.
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QList_PrependNode()
|
|
|
|
Description:
|
|
Prepend a node to the queue. Make it the first 'next' (and the
|
|
last 'prev').
|
|
|
|
Prototype:
|
|
|
|
void QList_PrependNode(QList *me, QNode *pn)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
pn: the node to prepend.
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QList_CtorFrom()
|
|
|
|
Description:
|
|
Move nodes from one queue to a newly constructed queue.
|
|
Weird aliasing voodoo allows this to work without conditional branches, even
|
|
when psrc is empty. In that case, "s->pNext->pPrev = d" overwrites s->pPrev with d,
|
|
so that "s->pPrev->pNext = d" will later overwrite d->pNext with d.
|
|
|
|
Prototype:
|
|
|
|
void QList_CtorFrom(QList *me, QList *psrc)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
psrc: the Qlist from
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QList_AppendList()
|
|
|
|
Description:
|
|
Move all nodes from a source queue to the end of this queue.
|
|
Note that weird aliasing voodoo allows this to work without conditional
|
|
branches when psrc is empty. A summary:
|
|
|
|
SNP = DP => SP = DP, because SNP aliases SP
|
|
DPN = SN => DPN = S
|
|
DP = SP => DP = DP, because SP was overwritten with DP
|
|
SPN = D => DPN = D
|
|
|
|
Prototype:
|
|
|
|
void QList_AppendList(QList *me, QList *psrc)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
psrc: the source Qlist.
|
|
|
|
Return Value:
|
|
None
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
QList_GetFirst()
|
|
|
|
Description:
|
|
Get the first item on the queue
|
|
|
|
Prototype:
|
|
|
|
QNode *QList_GetFirst(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
pointer to QNode or 0 if queue is empty.
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
QList_GetLast
|
|
|
|
=======================================================================
|
|
QList_GetLast()
|
|
|
|
Description:
|
|
Get the last item on the queue
|
|
|
|
Prototype:
|
|
|
|
QNode *QList_GetLast(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
pointer to QNode or 0 if queue is empty.
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
QList_GetFirst
|
|
|
|
=======================================================================
|
|
QList_Pop()
|
|
|
|
Description:
|
|
Remove and return the first item on the queue (FIFO).
|
|
|
|
Prototype:
|
|
|
|
QNode *QList_Pop(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
pointer to QNode or 0 if queue is empty
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
QNode_PopZ, QNode_PopLast(), QNode_PopLastZ, QNode_CtorZ(), QNode_IsQueued(),
|
|
QNode_DequeueZ()
|
|
|
|
=======================================================================
|
|
QList_PopZ()
|
|
|
|
Description:
|
|
Remove and return the first item on the queue (FIFO). Same as QList_Pop(),
|
|
except the node retured is zero-initialized.
|
|
|
|
Prototype:
|
|
|
|
QNode *QList_PopZ(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
pointer to QNode or 0 if queue is empty
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
QNode_Pop, QNode_PopLast(), QNode_PopLastZ, QNode_CtorZ(), QNode_IsQueued(),
|
|
QNode_DequeueZ()
|
|
|
|
=======================================================================
|
|
QList_PopLast()
|
|
|
|
Description:
|
|
Remove and return the first item on the queue (FILO).
|
|
|
|
Prototype:
|
|
|
|
QNode *QList_PopLast(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
pointer to QNode or 0 if queue is empty
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
QNode_PopLastZ, QNode_Pop(), QNode_PopZ, QNode_CtorZ(), QNode_IsQueued(),
|
|
QNode_DequeueZ()
|
|
|
|
=======================================================================
|
|
|
|
QList_IsNull()
|
|
|
|
Description:
|
|
Checks if the QList is null or not.
|
|
|
|
Prototype:
|
|
static __inline int QList_IsNull(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
True or False.
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
None
|
|
|
|
=======================================================================
|
|
|
|
QList_PopLastZ()
|
|
|
|
Description:
|
|
Remove and return the first item on the queue (FILO).
|
|
Same as QList_PopLast(), except the node retured is zero-initialized.
|
|
|
|
Prototype:
|
|
|
|
QNode *QList_PopLastZ(QList *me)
|
|
|
|
Parameters:
|
|
me: the QList
|
|
|
|
Return Value:
|
|
pointer to QNode or 0 if queue is empty
|
|
|
|
Comments:
|
|
None
|
|
|
|
Side Effects:
|
|
None
|
|
|
|
See Also:
|
|
QNode_Pop(), QNode_PopZ, QNode_CtorZ(), QNode_IsQueued(), QNode_DequeueZ()
|
|
|
|
=====================================================================*/
|
|
#endif // _AEEQLIST_H_
|