| /** |
| * 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_ |