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