1 /**
2 * Copyright (c) 2019, The Linux Foundation. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above
10 * copyright notice, this list of conditions and the following
11 * disclaimer in the documentation and/or other materials provided
12 * with the distribution.
13 * * Neither the name of The Linux Foundation nor the names of its
14 * contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
18 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
21 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
24 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
25 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
26 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
27 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 /*===========================================================================
31
32 FILE: AEEQList.h
33
34 GENERAL DESCRIPTION: Doubly-linked circular list implementation
35
36 ===========================================================================*/
37 #ifndef _AEEQLIST_H_
38 #define _AEEQLIST_H_
39
40
41 typedef struct QNode QNode;
42 struct QNode {
43 QNode *pNext;
44 QNode *pPrev;
45 };
46
47 #define QLIST_DEFINE_INIT(f) QList f = { { &f.n, &f.n } }
48
49 typedef struct QList QList;
50 struct QList {
51 QNode n;
52 };
53
54
55
QNode_InsPrev(QNode * me,QNode * pn)56 static __inline void QNode_InsPrev(QNode *me, QNode *pn)
57 {
58 QNode *pPrev = me->pPrev;
59
60 pn->pNext = me;
61 pn->pPrev = pPrev;
62 pPrev->pNext = pn;
63 me->pPrev = pn;
64 }
65
66
QNode_InsNext(QNode * me,QNode * pn)67 static __inline void QNode_InsNext(QNode *me, QNode *pn)
68 {
69 QNode *pNext = me->pNext;
70
71 pn->pPrev = me;
72 pn->pNext = pNext;
73 pNext->pPrev = pn;
74 me->pNext = pn;
75 }
76
77
78
QNode_Dequeue(QNode * me)79 static __inline void QNode_Dequeue(QNode *me)
80 {
81 QNode *pNext = me->pNext;
82 QNode *pPrev = me->pPrev;
83
84 pPrev->pNext = pNext;
85 pNext->pPrev = pPrev;
86 }
87
QNode_CtorZ(QNode * me)88 static __inline void QNode_CtorZ(QNode *me)
89 {
90 me->pNext = me->pPrev = 0;
91 }
92
QNode_IsQueuedZ(QNode * me)93 static __inline int QNode_IsQueuedZ(QNode *me)
94 {
95 return (0 != me->pNext);
96 }
97
QNode_DequeueZ(QNode * me)98 static __inline void QNode_DequeueZ(QNode *me)
99 {
100 if (QNode_IsQueuedZ(me)) {
101 QNode_Dequeue(me);
102 me->pNext = me->pPrev = 0;
103 }
104 }
105
106 //--------------------------------------------------------------------
107 //-- QList functions ----------------------------------------------
108 //--------------------------------------------------------------------
109
110
QList_Zero(QList * me)111 static __inline void QList_Zero(QList *me)
112 {
113 me->n.pNext = me->n.pPrev = &me->n;
114 }
115
116
QList_Ctor(QList * me)117 static __inline void QList_Ctor(QList *me)
118 {
119 QList_Zero(me);
120 }
121
122
QList_IsEmpty(QList * me)123 static __inline int QList_IsEmpty(QList *me)
124 {
125 return me->n.pNext == &me->n;
126 }
127
QList_IsNull(QList * me)128 static __inline int QList_IsNull(QList *me)
129 {
130 return ((0 == me->n.pNext) && (0 == me->n.pPrev));
131 }
132
133
QList_AppendNode(QList * me,QNode * pn)134 static __inline void QList_AppendNode(QList *me, QNode *pn)
135 {
136 QNode_InsPrev(&me->n, pn);
137 }
138
139
QList_PrependNode(QList * me,QNode * pn)140 static __inline void QList_PrependNode(QList *me, QNode *pn)
141 {
142 QNode_InsNext(&me->n, pn);
143 }
144
145
QList_CtorFrom(QList * me,QList * psrc)146 static __inline void QList_CtorFrom(QList *me, QList *psrc)
147 {
148 QNode *s = &psrc->n;
149 QNode *d = &me->n;
150
151 s->pNext->pPrev = d;
152 d->pPrev = s->pPrev;
153 d->pNext = s->pNext;
154 s->pPrev->pNext = d;
155
156 QList_Zero(psrc);
157 }
158
159
160
QList_AppendList(QList * me,QList * psrc)161 static __inline void QList_AppendList(QList *me, QList *psrc)
162 {
163 QNode *s = &psrc->n;
164 QNode *d = &me->n;
165 QNode *dp = d->pPrev;
166 QNode *sn = s->pNext;
167 QNode *sp;
168
169 sn->pPrev = dp;
170 dp->pNext = sn;
171 d->pPrev = (sp = s->pPrev);
172 sp->pNext = d;
173
174 QList_Zero(psrc);
175 }
176
177
178 #define QLIST_FOR_ALL(pList, pNode) \
179 for ((pNode) = (pList)->n.pNext; \
180 (pNode) != &(pList)->n; \
181 (pNode) = (pNode)->pNext)
182
183 #define QLIST_FOR_REST(pList, pNode) \
184 for (; \
185 (pNode) != &(pList)->n; \
186 (pNode) = (pNode)->pNext)
187
188 #define QLIST_REV_FOR_ALL(pList, pNode) \
189 for ((pNode) = (pList)->n.pPrev; \
190 (pNode) != &(pList)->n; \
191 (pNode) = (pNode)->pPrev)
192
193 #define QLIST_REV_FOR_REST(pList, pNode) \
194 for (; \
195 (pNode) != &(pList)->n; \
196 (pNode) = (pNode)->pPrev)
197
198 /* Allows dequeing QNodes during iteration */
199 #define QLIST_NEXTSAFE_FOR_ALL(pList, pNode, pNodeNext) \
200 for ((pNode) = (pList)->n.pNext, (pNodeNext) = (pNode)->pNext; \
201 (pNode) != &(pList)->n; \
202 (pNode) = (pNodeNext), (pNodeNext) = (pNode)->pNext)
203
QList_GetFirst(QList * me)204 static __inline QNode *QList_GetFirst(QList *me)
205 {
206 QNode *pn = me->n.pNext;
207
208 return (pn == &me->n ? 0 : pn);
209 }
210
QList_GetLast(QList * me)211 static __inline QNode *QList_GetLast(QList *me)
212 {
213 QNode *pn = me->n.pPrev;
214
215 return (pn == &me->n ? 0 : pn);
216 }
217
QList_Pop(QList * me)218 static __inline QNode *QList_Pop(QList *me)
219 {
220 QNode *pn = me->n.pNext;
221 QNode *pnn = pn->pNext;
222
223 me->n.pNext = pnn;
224 pnn->pPrev = &me->n;
225
226 return (pn == &me->n ? 0 : pn);
227 }
228
QList_PopZ(QList * me)229 static __inline QNode *QList_PopZ(QList *me)
230 {
231 QNode *pn = QList_Pop(me);
232 if (0 != pn) {
233 QNode_CtorZ(pn);
234 }
235 return pn;
236 }
237
QList_PopLast(QList * me)238 static __inline QNode *QList_PopLast(QList *me)
239 {
240 QNode *pp = me->n.pPrev;
241 QNode *ppp = pp->pPrev;
242
243 me->n.pPrev = ppp;
244 ppp->pNext = &me->n;
245
246 return (pp == &me->n ? 0 : pp);
247 }
248
QList_PopLastZ(QList * me)249 static __inline QNode *QList_PopLastZ(QList *me)
250 {
251 QNode *pn = QList_PopLast(me);
252 if (0 != pn) {
253 QNode_CtorZ(pn);
254 }
255 return pn;
256 }
257
258 /*=====================================================================
259 =======================================================================
260 DATA STRUCTURE DOCUMENTATION
261 =======================================================================
262
263 QNode
264
265 Description:
266 Qnode is the structure that is queued. One or more Qnodes may be
267 embedded in other structures. An object can contain multiple QNodes if
268 it needs to be in different lists at the same time.
269
270 Definition:
271
272 typedef struct QNode QNode;
273 struct QNode {
274 QNode *pNext;
275 QNode *pPrev;
276 };
277
278 Members:
279
280 See Also:
281
282 =======================================================================
283
284 QList
285
286 Description:
287 QList keeps a doubly-linked list of QNode structures.
288 Each queue is represented by a 'head' node, not a head pointer,
289 simplifying and streamlining many operations.
290 Because it is doubly-linked it permits constant-time insertion or removal
291 of items or of entire queues.
292 Because it is circular it permits constant-time operations at both the
293 tail and the head of the queue. Circularity also streamlines some
294 operations by eliminating conditional branches.
295
296 General rules:
297 QLists are always in a defined state; they should be constructed
298 before use, using one of the supplied Ctor...() functions.
299 QNodes do not track queued vs. unqueued state. The client should
300 never dequeue an un-queued node or queue an already-queued node.
301 When not queued, QNode internal state is undefined. A client may
302 implement marking and assertion externally.
303
304 Definition:
305
306 typedef struct QList QList;
307 struct QList {
308 QNode n;
309 };
310
311 Members:
312
313 See Also:
314
315 =======================================================================
316 INTERFACE DOCUMENTATION
317 =======================================================================
318 QNode Interface
319
320 QNode is a statically-linked interface.
321
322 =======================================================================
323 QNode_CtorZ()
324
325 Description:
326 Zero initialize a QNode.
327
328 Prototype:
329
330 void QNode_CtorZ(QNode *me);
331
332 Parameters:
333 me: the QNode
334
335 Return Value:
336 None
337
338 Comments:
339 None
340
341 Side Effects:
342 None
343
344 See Also:
345 QNode_IsQueued(), QNode_DequeueZ(), QList_PopZ()
346
347 =======================================================================
348 QNode_IsQueuedZ()
349
350 Description:
351 Whether a QNode belongs in a Queue.
352
353 Prototype:
354
355 int QNode_IsQueuedZ(QNode *me);
356
357 Parameters:
358 me: the QNode
359
360 Return Value:
361 None
362
363 Comments:
364 None
365
366 Side Effects:
367 Does not work if a node needs to live at address 0x0.
368
369 See Also:
370 QNode_CtorZ(), QNode_DequeueZ(), QList_PopZ()
371
372 =======================================================================
373 QNode_DequeueZ()
374
375 Description:
376 Dequeue a QNode if it is in a queue. Idempotent operation.
377
378 Prototype:
379
380 void QNode_DequeueZ(QNode *me);
381
382 Parameters:
383 me: the QNode
384
385 Return Value:
386 None
387
388 Comments:
389 None
390
391 Side Effects:
392 None
393
394 See Also:
395 QNode_CtorZ(), QNode_IsQueued(), QList_PopZ()
396
397 =======================================================================
398
399 QNode_InsPrev()
400
401 Description:
402 insert a node before this one.
403
404 Prototype:
405 static __inline void QNode_InsPrev(QNode *me, QNode *pn)
406
407 Parameters:
408 me: the QNode
409 pn: the node to be inserted.
410 Return Value:
411 None
412
413 Comments:
414 None
415
416 Side Effects:
417 None
418
419 See Also:
420 None
421
422 =======================================================================
423
424 QNode_InsNext()
425
426 Description:
427 insert a node after this one.
428
429 Prototype:
430 static __inline void QNode_InsNext(QNode *me, QNode *pn)
431
432 Parameters:
433 me: the QNode
434 pn: the node to be inserted.
435
436 Return Value:
437 None
438
439 Comments:
440 None
441
442 Side Effects:
443 None
444
445 See Also:
446 None
447
448 =======================================================================
449 QNode_Dequeue()
450
451 Description:
452 dequeue this node.
453
454 Prototype:
455 static __inline void QNode_Dequeue(QNode *me)
456
457 Parameters:
458 me: the QNode to be dequeued
459
460 Return Value:
461 None
462
463 Comments:
464 None
465
466 Side Effects:
467 None
468
469 See Also:
470 None
471
472 =======================================================================
473 QList Interface
474
475 QList is a statically-linked interface. It provides a Queue of
476 doubly linked nodes.
477
478 =======================================================================
479 QList_Zero()
480
481 Description:
482 discard all queued nodes.
483
484 Prototype:
485
486 void QList_Zero(QList *me)
487
488 Parameters:
489 me: the QList
490
491 Return Value:
492 None
493
494 Comments:
495 None
496
497 Side Effects:
498 None
499
500 See Also:
501 None
502
503 =======================================================================
504 QList_Ctor()
505
506 Description:
507 Initialize a queue to an empty state
508
509 Prototype:
510
511 void QList_Ctor(QList *me)
512
513 Parameters:
514 me: the QList
515
516 Return Value:
517 None
518
519 Comments:
520 None
521
522 Side Effects:
523 None
524
525 See Also:
526 None
527
528 =======================================================================
529 QList_IsEmpty()
530
531 Description:
532 Check whether queue is empty.
533
534 Prototype:
535
536 int QList_IsEmpty(QList *me)
537
538 Parameters:
539 me: the QList
540
541 Return Value:
542 TRUE if queue is empty.
543
544 Comments:
545 None
546
547 Side Effects:
548 None
549
550 See Also:
551 None
552
553 =======================================================================
554 QList_AppendNode()
555
556 Description:
557 Append the node to the queue. Make it the last 'next' (and the
558 first 'prev')
559
560 Prototype:
561
562 void QList_AppendNode(QList *me, QNode *pn)
563
564 Parameters:
565 me: the QList
566 pn: the node to append.
567
568 Return Value:
569 None
570
571 Comments:
572 None
573
574 Side Effects:
575 None
576
577 See Also:
578 None
579
580 =======================================================================
581 QList_PrependNode()
582
583 Description:
584 Prepend a node to the queue. Make it the first 'next' (and the
585 last 'prev').
586
587 Prototype:
588
589 void QList_PrependNode(QList *me, QNode *pn)
590
591 Parameters:
592 me: the QList
593 pn: the node to prepend.
594
595 Return Value:
596 None
597
598 Comments:
599 None
600
601 Side Effects:
602 None
603
604 See Also:
605 None
606
607 =======================================================================
608 QList_CtorFrom()
609
610 Description:
611 Move nodes from one queue to a newly constructed queue.
612 Weird aliasing voodoo allows this to work without conditional branches, even
613 when psrc is empty. In that case, "s->pNext->pPrev = d" overwrites s->pPrev with d,
614 so that "s->pPrev->pNext = d" will later overwrite d->pNext with d.
615
616 Prototype:
617
618 void QList_CtorFrom(QList *me, QList *psrc)
619
620 Parameters:
621 me: the QList
622 psrc: the Qlist from
623
624 Return Value:
625 None
626
627 Comments:
628 None
629
630 Side Effects:
631 None
632
633 See Also:
634 None
635
636 =======================================================================
637 QList_AppendList()
638
639 Description:
640 Move all nodes from a source queue to the end of this queue.
641 Note that weird aliasing voodoo allows this to work without conditional
642 branches when psrc is empty. A summary:
643
644 SNP = DP => SP = DP, because SNP aliases SP
645 DPN = SN => DPN = S
646 DP = SP => DP = DP, because SP was overwritten with DP
647 SPN = D => DPN = D
648
649 Prototype:
650
651 void QList_AppendList(QList *me, QList *psrc)
652
653 Parameters:
654 me: the QList
655 psrc: the source Qlist.
656
657 Return Value:
658 None
659
660 Comments:
661 None
662
663 Side Effects:
664 None
665
666 See Also:
667 None
668
669 =======================================================================
670 QList_GetFirst()
671
672 Description:
673 Get the first item on the queue
674
675 Prototype:
676
677 QNode *QList_GetFirst(QList *me)
678
679 Parameters:
680 me: the QList
681
682 Return Value:
683 pointer to QNode or 0 if queue is empty.
684
685 Comments:
686 None
687
688 Side Effects:
689 None
690
691 See Also:
692 QList_GetLast
693
694 =======================================================================
695 QList_GetLast()
696
697 Description:
698 Get the last item on the queue
699
700 Prototype:
701
702 QNode *QList_GetLast(QList *me)
703
704 Parameters:
705 me: the QList
706
707 Return Value:
708 pointer to QNode or 0 if queue is empty.
709
710 Comments:
711 None
712
713 Side Effects:
714 None
715
716 See Also:
717 QList_GetFirst
718
719 =======================================================================
720 QList_Pop()
721
722 Description:
723 Remove and return the first item on the queue (FIFO).
724
725 Prototype:
726
727 QNode *QList_Pop(QList *me)
728
729 Parameters:
730 me: the QList
731
732 Return Value:
733 pointer to QNode or 0 if queue is empty
734
735 Comments:
736 None
737
738 Side Effects:
739 None
740
741 See Also:
742 QNode_PopZ, QNode_PopLast(), QNode_PopLastZ, QNode_CtorZ(), QNode_IsQueued(),
743 QNode_DequeueZ()
744
745 =======================================================================
746 QList_PopZ()
747
748 Description:
749 Remove and return the first item on the queue (FIFO). Same as QList_Pop(),
750 except the node retured is zero-initialized.
751
752 Prototype:
753
754 QNode *QList_PopZ(QList *me)
755
756 Parameters:
757 me: the QList
758
759 Return Value:
760 pointer to QNode or 0 if queue is empty
761
762 Comments:
763 None
764
765 Side Effects:
766 None
767
768 See Also:
769 QNode_Pop, QNode_PopLast(), QNode_PopLastZ, QNode_CtorZ(), QNode_IsQueued(),
770 QNode_DequeueZ()
771
772 =======================================================================
773 QList_PopLast()
774
775 Description:
776 Remove and return the first item on the queue (FILO).
777
778 Prototype:
779
780 QNode *QList_PopLast(QList *me)
781
782 Parameters:
783 me: the QList
784
785 Return Value:
786 pointer to QNode or 0 if queue is empty
787
788 Comments:
789 None
790
791 Side Effects:
792 None
793
794 See Also:
795 QNode_PopLastZ, QNode_Pop(), QNode_PopZ, QNode_CtorZ(), QNode_IsQueued(),
796 QNode_DequeueZ()
797
798 =======================================================================
799
800 QList_IsNull()
801
802 Description:
803 Checks if the QList is null or not.
804
805 Prototype:
806 static __inline int QList_IsNull(QList *me)
807
808 Parameters:
809 me: the QList
810
811 Return Value:
812 True or False.
813
814 Comments:
815 None
816
817 Side Effects:
818 None
819
820 See Also:
821 None
822
823 =======================================================================
824
825 QList_PopLastZ()
826
827 Description:
828 Remove and return the first item on the queue (FILO).
829 Same as QList_PopLast(), except the node retured is zero-initialized.
830
831 Prototype:
832
833 QNode *QList_PopLastZ(QList *me)
834
835 Parameters:
836 me: the QList
837
838 Return Value:
839 pointer to QNode or 0 if queue is empty
840
841 Comments:
842 None
843
844 Side Effects:
845 None
846
847 See Also:
848 QNode_Pop(), QNode_PopZ, QNode_CtorZ(), QNode_IsQueued(), QNode_DequeueZ()
849
850 =====================================================================*/
851 #endif // _AEEQLIST_H_
852