xref: /illumos-gate/usr/src/uts/common/io/bnx/include/listq.h (revision eef4f27b270242808b43b4b23bd161df52839361) 
1 /*
2  * Copyright 2014-2017 Cavium, Inc.
3  * The contents of this file are subject to the terms of the Common Development
4  * and Distribution License, v.1,  (the "License").
5  *
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the License at available
9  * at http://opensource.org/licenses/CDDL-1.0
10  *
11  * See the License for the specific language governing permissions and
12  * limitations under the License.
13  */
14 
15 /*******************************************************************************
16  *
17  * Single link list routines:
18  *    void              s_list_init        (s_list_t *,  *head, *tail, cnt)
19  *    void              s_list_clear       (s_list_t *)
20  *    void              s_list_push_head   (s_list_t *,  s_list_entry_t *)
21  *    s_list_entry_t *  s_list_pop_head    (s_list_t *)
22  *    void              s_list_push_tail   (s_list_t *,  s_list_entry_t *)
23  *    s_list_entry_t *  s_list_peek_head   (s_list_t *)
24  *    s_list_entry_t *  s_list_peek_tail   (s_list_t *)
25  *    s_list_entry_t *  s_list_next_entry  (s_list_entry_t *)
26  *    unsigned long     s_list_entry_cnt   (s_list_t *)
27  *    char              s_list_is_empty    (s_list_t *)
28  *    void              s_list_add_head    (s_list_t *,  s_list_t *)
29  *    void              s_list_add_tail    (s_list_t *,  s_list_t *)
30  *    void              s_list_split       (d_list_t *,  d_list_t *, d_list_entry_t *, ulong)
31  *
32  * Double link list routines:
33  *    void              d_list_init        (d_list_t *,  *head, *tail, cnt)
34  *    void              d_list_clear       (d_list_t *)
35  *    void              d_list_push_head   (d_list_t *,  d_list_entry_t *)
36  *    d_list_entry_t *  d_list_pop_head    (d_list_t *)
37  *    void              d_list_push_tail   (d_list_t *,  d_list_entry_t *)
38  *    d_list_entry_t *  d_list_pop_tail    (d_list_t *)
39  *    d_list_entry_t *  d_list_peek_head   (d_list_t *)
40  *    d_list_entry_t *  d_list_peek_tail   (d_list_t *)
41  *    d_list_entry_t *  d_list_next_entry  (d_list_entry_t *)
42  *    void              d_list_remove_entry(d_list_t *,  d_list_entry_t *)
43  *    void              d_list_insert_entry(d_list_t *,  *prev, *next, *new)
44  *    d_list_entry_t *  d_list_prev_entry  (d_list_entry_t *)
45  *    unsigned long     d_list_entry_cnt   (d_list_t *)
46  *    char              d_list_is_empty    (d_list_t *)
47  *    void              d_list_add_head    (d_list_t *,  d_list_t *)
48  *    void              d_list_add_tail    (d_list_t *,  d_list_t *)
49  *
50  * Array list routines:
51  *    void              q_list_init        (q_list_t *,  q_list_entry *, ulong)
52  *    void              q_list_clear       (q_list_t *)
53  *    void              q_list_push_head   (q_list_t *,  q_list_entry_t)
54  *    q_list_entry_t    q_list_pop_head    (q_list_t *)
55  *    void              q_list_push_tail   (q_list_t *,  q_list_entry_t)
56  *    q_list_entry_t    q_list_pop_tail    (q_list_t *)
57  *    q_list_entry_t    q_list_peek_head   (q_list_t *)
58  *    q_list_entry_t    q_list_peek_tail   (q_list_t *)
59  *    unsigned long     q_list_entry_cnt   (q_list_t *)
60  *    char              q_list_is_empty    (q_list_t *)
61  *    char              q_list_is_full     (q_list_t *)
62  *
63  * History:
64  *    03/30/98 Hav Khauv                Initial version.
65  ******************************************************************************/
66 
67 #ifndef _listq_h_
68 #define _listq_h_
69 
70 
71 
72 /*******************************************************************************
73  * Single link list.
74  ******************************************************************************/
75 
76 typedef struct _s_list_entry_t
77 {
78     struct _s_list_entry_t *next;
79 } s_list_entry_t;
80 
81 #define S_LINK_CAST(_p)                 ((s_list_entry_t *) (_p))
82 
83 
84 typedef struct _s_list_t
85 {
86     s_list_entry_t *head;
87     s_list_entry_t *tail;
88     unsigned long cnt;
89 } s_list_t;
90 
91 
92 
93 #ifdef _INLINE_LISTQ_CALLS
94 
95 
96 __inline
97 void
98 s_list_init(
99     s_list_t *s_list,
100     s_list_entry_t *head_entry,
101     s_list_entry_t *tail_entry,
102     unsigned long entry_cnt)
103 {
104     s_list->head = head_entry;
105     s_list->tail = tail_entry;
106     s_list->cnt = entry_cnt;
107 }
108 
109 
110 __inline
111 void
112 s_list_clear(
113     s_list_t *s_list)
114 {
115     s_list->head = (s_list_entry_t *) 0;
116     s_list->tail = (s_list_entry_t *) 0;
117     s_list->cnt = 0;
118 }
119 
120 
121 __inline
122 void
123 s_list_push_head(
124     s_list_t *s_list,
125     s_list_entry_t *s_entry)
126 {
127     s_entry->next = s_list->head;
128 
129     if(s_list->tail == (s_list_entry_t *) 0)
130     {
131         s_list->tail = s_entry;
132     }
133     s_list->head = s_entry;
134 
135     s_list->cnt++;
136 }
137 
138 
139 __inline
140 s_list_entry_t *
141 s_list_pop_head(
142     s_list_t *s_list)
143 {
144     s_list_entry_t *s_entry;
145 
146     s_entry = s_list->head;
147     if(s_list->head)
148     {
149         s_list->head = s_list->head->next;
150         if(s_list->head == (s_list_entry_t *) 0)
151         {
152             s_list->tail = (s_list_entry_t *) 0;
153         }
154 
155         s_list->cnt--;
156     }
157 
158     return s_entry;
159 }
160 
161 
162 __inline
163 void
164 s_list_push_tail(
165     s_list_t *s_list,
166     s_list_entry_t *s_entry)
167 {
168     s_entry->next = (s_list_entry_t *) 0;
169 
170     if(s_list->tail)
171     {
172         s_list->tail->next = s_entry;
173     }
174     else
175     {
176         s_list->head = s_entry;
177     }
178     s_list->tail = s_entry;
179 
180     s_list->cnt++;
181 }
182 
183 
184 __inline
185 s_list_entry_t *
186 s_list_peek_head(
187     s_list_t *s_list)
188 {
189     return s_list->head;
190 }
191 
192 
193 __inline
194 s_list_entry_t *
195 s_list_peek_tail(
196     s_list_t *s_list)
197 {
198     return s_list->tail;
199 }
200 
201 
202 __inline
203 s_list_entry_t *
204 s_list_next_entry(
205     s_list_entry_t *s_entry)
206 {
207     return s_entry->next;
208 }
209 
210 
211 __inline
212 unsigned long
213 s_list_entry_cnt(
214     s_list_t *s_list)
215 {
216     return s_list->cnt;
217 }
218 
219 
220 __inline
221 char
222 s_list_is_empty(
223     s_list_t *s_list)
224 {
225     return s_list->cnt == 0;
226 }
227 
228 
229 __inline
230 void
231 s_list_add_head(
232     s_list_t *s_list,
233     s_list_t *s_list_head)
234 {
235     if(s_list->cnt == 0)
236     {
237         *s_list = *s_list_head;
238     }
239     else if(s_list_head->cnt)
240     {
241         s_list_head->tail->next = s_list->head;
242         s_list->head = s_list_head->head;
243         s_list->cnt += s_list_head->cnt;
244     }
245 }
246 
247 
248 __inline
249 void
250 s_list_add_tail(
251     s_list_t *s_list,
252     s_list_t *s_list_tail)
253 {
254     if(s_list->cnt == 0)
255     {
256         *s_list = *s_list_tail;
257     }
258     else if(s_list_tail->cnt)
259     {
260         s_list->tail->next = s_list_tail->head;
261         s_list->tail = s_list_tail->tail;
262         s_list->cnt += s_list_tail->cnt;
263     }
264 }
265 
266 __inline
267 void
268 s_list_split(
269     s_list_t * s_list,
270     s_list_t * s_list_head,
271     s_list_entry_t * split_entry,
272     unsigned long entry_cnt)
273 {
274     if (split_entry->next == NULL) {
275         s_list_head->head = s_list->head;
276         s_list_head->tail = split_entry;
277         s_list_head->cnt = entry_cnt;
278 
279         s_list->head = NULL;
280         s_list->tail = NULL;
281         s_list->cnt = 0;
282     } else {
283         s_list_head->head = s_list->head;
284         s_list_head->tail = split_entry;
285         s_list_head->cnt = entry_cnt;
286 
287         s_list->head = split_entry->next;
288         s_list->cnt = s_list->cnt - entry_cnt;
289         split_entry->next = NULL;
290 
291     }
292 }
293 
294 #else
295 
296 
297 #define s_list_init(_s_list, _head_entry, _tail_entry, _entry_cnt) \
298     (_s_list)->head = (_head_entry); \
299     (_s_list)->tail = (_tail_entry); \
300     (_s_list)->cnt = (_entry_cnt)
301 
302 
303 #define s_list_clear(_s_list) \
304     (_s_list)->head = (s_list_entry_t *) 0; \
305     (_s_list)->tail = (s_list_entry_t *) 0; \
306     (_s_list)->cnt = 0
307 
308 
309 #define s_list_push_head(_s_list, _s_entry) \
310     (_s_entry)->next = (_s_list)->head; \
311     if((_s_list)->tail == (s_list_entry_t *) 0) \
312     { \
313         (_s_list)->tail = (_s_entry); \
314     } \
315     (_s_list)->head = (_s_entry); \
316     (_s_list)->cnt++
317 
318 
319 #define s_list_pop_head(_s_list) \
320     (_s_list)->head; \
321     if((_s_list)->head) \
322     { \
323         (_s_list)->head = (_s_list)->head->next; \
324         if((_s_list)->head == (s_list_entry_t *) 0) \
325         { \
326             (_s_list)->tail = (s_list_entry_t *) 0; \
327         } \
328         (_s_list)->cnt--; \
329     }
330 
331 
332 #define s_list_push_tail(_s_list, _s_entry) \
333     (_s_entry)->next = (s_list_entry_t *) 0; \
334     if((_s_list)->tail) \
335     { \
336         (_s_list)->tail->next = (_s_entry); \
337     } \
338     else \
339     { \
340         (_s_list)->head = (_s_entry); \
341     } \
342     (_s_list)->tail = (_s_entry); \
343     (_s_list)->cnt++
344 
345 
346 #define s_list_peek_head(_s_list)       ((_s_list)->head)
347 
348 
349 #define s_list_peek_tail(_s_list)       ((_s_list)->tail)
350 
351 
352 #define s_list_next_entry(_s_entry)     ((_s_entry)->next)
353 
354 
355 #define s_list_entry_cnt(_s_list)       ((_s_list)->cnt)
356 
357 
358 #define s_list_is_empty(_s_list)        ((_s_list)->cnt == 0)
359 
360 
361 #define s_list_add_head(_s_list, _s_list_head) \
362     if((_s_list)->cnt == 0) \
363     { \
364         *(_s_list) = *(_s_list_head); \
365     } \
366     else if((_s_list_head)->cnt) \
367     { \
368         (_s_list_head)->tail->next = (_s_list)->head; \
369         (_s_list)->head = (_s_list_head)->head; \
370         (_s_list)->cnt += (_s_list_head)->cnt; \
371     }
372 
373 #define s_list_add_tail(_s_list, _s_list_tail) \
374     if((_s_list)->cnt == 0) \
375     { \
376         *(_s_list) = *(_s_list_tail); \
377     } \
378     else if((_s_list_tail)->cnt) \
379     { \
380         (_s_list)->tail->next = (_s_list_tail)->head; \
381         (_s_list)->tail = (_s_list_tail)->tail; \
382         (_s_list)->cnt += (_s_list_tail)->cnt; \
383     }
384 
385 #define s_list_split(_s_list, _s_list_head, _split_entry, _entry_cnt) \
386     if ((_split_entry)->next == NULL) { \
387         (_s_list_head)->head = (_s_list)->head; \
388         (_s_list_head)->tail = _split_entry; \
389         (_s_list_head)->cnt = _entry_cnt; \
390         (_s_list)->head = NULL; \
391         (_s_list)->tail = NULL; \
392         (_s_list)->cnt = 0; \
393     } else { \
394         (_s_list_head)->head = (_s_list)->head; \
395         (_s_list_head)->tail = _split_entry; \
396         (_s_list_head)->cnt = (_entry_cnt); \
397         (_s_list)->head = (_split_entry)->next; \
398         (_s_list)->cnt = (_s_list)->cnt - (_entry_cnt); \
399         (_split_entry)->next = NULL; \
400     }
401 
402 #endif
403 
404 
405 
406 /*******************************************************************************
407  * Double link list entry.
408  ******************************************************************************/
409 
410 typedef struct _d_list_entry_t
411 {
412     struct _d_list_entry_t *next;
413     struct _d_list_entry_t *prev;
414 } d_list_entry_t;
415 
416 #define D_LINK_CAST(_p)                 ((d_list_entry_t *) (_p))
417 
418 
419 typedef struct _d_list_t
420 {
421     d_list_entry_t *head;
422     d_list_entry_t *tail;
423     unsigned long cnt;
424 } d_list_t;
425 
426 
427 
428 #ifdef _INLINE_LISTQ_CALLS
429 
430 
431 __inline
432 void
433 d_list_init(
434     d_list_t *d_list,
435     d_list_entry_t *head_entry,
436     d_list_entry_t *tail_entry,
437     unsigned long entry_cnt)
438 {
439     d_list->head = head_entry;
440     d_list->tail = tail_entry;
441     d_list->cnt = entry_cnt;
442 }
443 
444 
445 __inline
446 void
447 d_list_clear(
448     d_list_t *d_list)
449 {
450     d_list->head = (d_list_entry_t *) 0;
451     d_list->tail = (d_list_entry_t *) 0;
452     d_list->cnt = 0;
453 }
454 
455 
456 __inline
457 void
458 d_list_push_head(
459     d_list_t *d_list,
460     d_list_entry_t *d_entry)
461 {
462     d_entry->prev = (d_list_entry_t *) 0;
463     d_entry->next = d_list->head;
464 
465     if(d_list->tail == (d_list_entry_t *) 0)
466     {
467         d_list->tail = d_entry;
468     }
469     else
470     {
471         d_list->head->prev = d_entry;
472     }
473 
474     d_list->head = d_entry;
475 
476     d_list->cnt++;
477 }
478 
479 
480 __inline
481 d_list_entry_t *
482 d_list_pop_head(
483     d_list_t *d_list)
484 {
485     d_list_entry_t *d_entry;
486 
487     d_entry = d_list->head;
488     if(d_list->head)
489     {
490         d_list->head = d_list->head->next;
491         if(d_list->head)
492         {
493             d_list->head->prev = (d_list_entry_t *) 0;
494         }
495         else
496         {
497             d_list->tail = (d_list_entry_t *) 0;
498         }
499 
500         d_list->cnt--;
501     }
502 
503     return d_entry;
504 }
505 
506 
507 __inline
508 void
509 d_list_push_tail(
510     d_list_t *d_list,
511     d_list_entry_t *d_entry)
512 {
513     d_entry->next = (d_list_entry_t *) 0;
514     d_entry->prev = d_list->tail;
515 
516     if(d_list->tail)
517     {
518         d_list->tail->next = d_entry;
519     }
520     else
521     {
522         d_list->head = d_entry;
523     }
524     d_list->tail = d_entry;
525 
526     d_list->cnt++;
527 }
528 
529 
530 __inline
531 d_list_entry_t *
532 d_list_pop_tail(
533     d_list_t *d_list)
534 {
535     d_list_entry_t *d_entry;
536 
537     d_entry = d_list->tail;
538 
539     if(d_list->tail)
540     {
541         d_list->tail = d_list->tail->prev;
542         if(d_list->tail)
543         {
544             d_list->tail->next = (d_list_entry_t *) 0;
545         }
546         else
547         {
548             d_list->head = (d_list_entry_t *) 0;
549         }
550 
551         d_list->cnt--;
552     }
553 
554     return d_entry;
555 }
556 
557 
558 __inline
559 d_list_entry_t *
560 d_list_peek_head(
561     d_list_t *d_list)
562 {
563     return d_list->head;
564 }
565 
566 
567 __inline
568 d_list_entry_t *
569 d_list_peek_tail(
570     d_list_t *d_list)
571 {
572     return d_list->tail;
573 }
574 
575 
576 __inline
577 d_list_entry_t *
578 d_list_next_entry(
579     d_list_entry_t *d_entry)
580 {
581     return d_entry->next;
582 }
583 
584 
585 __inline
586 void
587 d_list_remove_entry(
588     d_list_t *d_list,
589     d_list_entry_t *d_entry)
590 {
591     if(d_list->head == d_entry)
592     {
593         d_list_pop_head(d_list);
594     }
595     else if(d_list->tail == d_entry)
596     {
597         d_list_pop_tail(d_list);
598     }
599     else
600     {
601         d_entry->prev->next = d_entry->next;
602         d_entry->next->prev = d_entry->prev;
603         d_list->cnt--;
604     }
605 }
606 
607 __inline
608 void
609 d_list_insert_entry(
610     d_list_t *d_list,
611     d_list_entry_t *d_entry_prev,
612     d_list_entry_t *d_entry_next,
613     d_list_entry_t *d_entry)
614 {
615     if (d_entry_prev  == NULL)
616     {
617         d_list_push_head(d_list, d_entry);
618     }
619     else if (d_entry_next == NULL)
620     {
621         d_list_push_tail(d_list, d_entry);
622     }
623     else
624     {
625         d_entry->next = d_entry_next;
626         d_entry->prev = d_entry_prev;
627         d_entry_prev->next = d_entry;
628         d_entry_next->prev = d_entry;
629         d_list->cnt++;
630     }
631 }
632 
633 
634 __inline
635 d_list_entry_t *
636 d_list_prev_entry(
637     d_list_entry_t *d_entry)
638 {
639     return d_entry->prev;
640 }
641 
642 
643 __inline
644 unsigned long
645 d_list_entry_cnt(
646     d_list_t *d_list)
647 {
648     return d_list->cnt;
649 }
650 
651 
652 __inline
653 char
654 d_list_is_empty(
655     d_list_t *d_list)
656 {
657     return d_list->cnt == 0;
658 }
659 
660 
661 __inline
662 void
663 d_list_add_head(
664     d_list_t *d_list,
665     d_list_t *d_list_head)
666 {
667     d_list_head->tail->next = d_list->head;
668 
669     if(d_list->head)
670     {
671         d_list->head->prev = d_list_head->tail;
672     }
673     else
674     {
675         d_list->tail = d_list_head->tail;
676     }
677     d_list->head = d_list_head->head;
678 
679     d_list->cnt += d_list_head->cnt;
680 }
681 
682 
683 __inline
684 void
685 d_list_add_tail(
686     d_list_t *d_list,
687     d_list_t *d_list_tail)
688 {
689     d_list_tail->head->prev = d_list->tail;
690 
691     if(d_list->tail)
692     {
693         d_list->tail->next = d_list_tail->head;
694     }
695     else
696     {
697         d_list->head = d_list_tail->head;
698     }
699     d_list->tail = d_list_tail->tail;
700 
701     d_list->cnt += d_list_tail->cnt;
702 }
703 
704 
705 #else
706 
707 
708 #define d_list_init(_d_list, _head_entry, _tail_entry, _entry_cnt) \
709     (_d_list)->head = (_head_entry); \
710     (_d_list)->tail = (_tail_entry); \
711     (_d_list)->cnt = (_entry_cnt)
712 
713 
714 #define d_list_clear(_d_list) \
715     (_d_list)->head = (d_list_entry_t *) 0; \
716     (_d_list)->tail = (d_list_entry_t *) 0; \
717     (_d_list)->cnt = 0
718 
719 
720 #define d_list_push_head(_d_list, _d_entry) \
721     (_d_entry)->prev = (d_list_entry_t *) 0; \
722     (_d_entry)->next = (_d_list)->head; \
723     if((_d_list)->tail == (d_list_entry_t *) 0) \
724     { \
725         (_d_list)->tail = (_d_entry); \
726     } \
727     else \
728     { \
729         (_d_list)->head->prev = (_d_entry); \
730     } \
731     (_d_list)->head = (_d_entry); \
732     (_d_list)->cnt++
733 
734 
735 #define d_list_pop_head(_d_list) \
736     (_d_list)->head; \
737     if((_d_list)->head) \
738     { \
739         (_d_list)->head = (_d_list)->head->next; \
740         if((_d_list)->head) \
741         { \
742             (_d_list)->head->prev = (d_list_entry_t *) 0; \
743         } \
744         else \
745         { \
746             (_d_list)->tail = (d_list_entry_t *) 0; \
747         } \
748         (_d_list)->cnt--; \
749     }
750 
751 
752 #define d_list_push_tail(_d_list, _d_entry) \
753     (_d_entry)->next = (d_list_entry_t *) 0; \
754     (_d_entry)->prev = (_d_list)->tail; \
755     if((_d_list)->tail) \
756     { \
757         (_d_list)->tail->next = (_d_entry); \
758     } \
759     else \
760     { \
761         (_d_list)->head = (_d_entry); \
762     } \
763     (_d_list)->tail = (_d_entry); \
764     (_d_list)->cnt++
765 
766 
767 #define d_list_pop_tail(_d_list) \
768     (_d_list)->tail; \
769     if((_d_list)->tail) \
770     { \
771         (_d_list)->tail = (_d_list)->tail->prev; \
772         if((_d_list)->tail) \
773         { \
774             (_d_list)->tail->next = (d_list_entry_t *) 0; \
775         } \
776         else \
777         { \
778             (_d_list)->head = (d_list_entry_t *) 0; \
779         } \
780         (_d_list)->cnt--; \
781     }
782 
783 
784 #define d_list_peek_head(_d_list)       ((_d_list)->head)
785 
786 
787 #define d_list_peek_tail(_d_list)       ((_d_list)->tail)
788 
789 
790 #define d_list_next_entry(_d_entry)     ((_d_entry)->next)
791 
792 #define d_list_insert_entry(_d_list, _d_entry_prev, _d_entry_next, _d_entry) \
793     if (_d_entry_prev  == NULL ) \
794     { \
795         (_d_entry)->prev = (d_list_entry_t *) 0; \
796         (_d_entry)->next = (_d_list)->head; \
797         if((_d_list)->tail == (d_list_entry_t *) 0) \
798         { \
799             (_d_list)->tail = (_d_entry); \
800         } \
801         (_d_list)->head = (_d_entry); \
802         (_d_list)->cnt++; \
803     } \
804     else if (_d_entry_next == NULL ) \
805     { \
806         (_d_entry)->next = (d_list_entry_t *) 0; \
807         (_d_entry)->prev = (_d_list)->tail; \
808         if((_d_list)->tail) \
809         { \
810             (_d_list)->tail->next = (_d_entry); \
811         } \
812         else \
813         { \
814             (_d_list)->head = (_d_entry); \
815         } \
816         (_d_list)->tail = (_d_entry); \
817         (_d_list)->cnt++; \
818     } \
819     else \
820     { \
821         (_d_entry)->next = (_d_entry_next); \
822         (_d_entry)->prev = (_d_entry_prev); \
823         (_d_entry_prev)->next = (_d_entry); \
824         (_d_entry_next)->prev = (_d_entry); \
825         (_d_list)->cnt++; \
826     }
827 
828 #define d_list_remove_entry(_d_list, _d_entry) \
829     if((_d_list)->head == (_d_entry)) \
830     { \
831         if((_d_list)->head) \
832         { \
833             (_d_list)->head = (_d_list)->head->next; \
834             if((_d_list)->head) \
835             { \
836                 (_d_list)->head->prev = (d_list_entry_t *) 0; \
837             } \
838             else \
839             { \
840                 (_d_list)->tail = (d_list_entry_t *) 0; \
841             } \
842             (_d_list)->cnt--; \
843         } \
844     } \
845     else if((_d_list)->tail == (_d_entry)) \
846     { \
847         if((_d_list)->tail) \
848         { \
849             (_d_list)->tail = (_d_list)->tail->prev; \
850             if((_d_list)->tail) \
851             { \
852                 (_d_list)->tail->next = (d_list_entry_t *) 0; \
853             } \
854             else \
855             { \
856                 (_d_list)->head = (d_list_entry_t *) 0; \
857             } \
858             (_d_list)->cnt--; \
859         } \
860     } \
861     else \
862     { \
863         (_d_entry)->prev->next = (_d_entry)->next; \
864         (_d_entry)->next->prev = (_d_entry)->prev; \
865         (_d_list)->cnt--; \
866     }
867 
868 
869 #define d_list_prev_entry(_d_entry)     ((_d_entry)->prev)
870 
871 
872 #define d_list_entry_cnt(_d_list)       ((_d_list)->cnt)
873 
874 
875 #define d_list_is_empty(_d_list)        ((_d_list)->cnt == 0)
876 
877 
878 #define d_list_add_head(_d_list, _d_list_head) \
879     (_d_list_head)->tail->next = (_d_list)->head; \
880     if((_d_list)->head) \
881     { \
882         (_d_list)->head->prev = (_d_list_head)->tail; \
883     } \
884     else \
885     { \
886         (_d_list)->tail = (_d_list_head)->tail; \
887     } \
888     (_d_list)->head = (_d_list_head)->head; \
889     (_d_list)->cnt += (_d_list_head)->cnt
890 
891 
892 #define d_list_add_tail(_d_list, _d_list_tail) \
893     (_d_list_tail)->head->prev = (_d_list)->tail; \
894     if((_d_list)->tail) \
895     { \
896         (_d_list)->tail->next = (_d_list_tail)->head; \
897     } \
898     else \
899     { \
900         (_d_list)->head = (_d_list_tail)->head; \
901     } \
902     (_d_list)->tail = (_d_list_tail)->tail; \
903     (_d_list)->cnt += (_d_list_tail)->cnt
904 
905 
906 #endif
907 
908 
909 
910 /*******************************************************************************
911  * Array list.
912  ******************************************************************************/
913 
914 typedef void *q_list_entry_t;
915 
916 typedef struct _q_list_t
917 {
918     q_list_entry_t *head;
919     q_list_entry_t *tail;
920     unsigned long cnt;
921 
922     unsigned long max_cnt;
923     q_list_entry_t *first_entry_addr;
924     q_list_entry_t *last_entry_addr;
925 } q_list_t;
926 
927 
928 
929 #ifdef _INLINE_LISTQ_CALLS
930 
931 
932 __inline
933 void
934 q_list_init(
935     q_list_t *q_list,
936     q_list_entry_t q_list_arr[],
937     unsigned long max_cnt)
938 {
939     q_list->max_cnt = max_cnt;
940     q_list->first_entry_addr = q_list_arr;
941     q_list->last_entry_addr = q_list_arr + (max_cnt-1);
942 
943     q_list->head = q_list->first_entry_addr;
944     q_list->tail = q_list->first_entry_addr;
945     q_list->cnt = 0;
946 }
947 
948 
949 __inline
950 void
951 q_list_clear(
952     q_list_t *q_list)
953 {
954     q_list->head = q_list->first_entry_addr;
955     q_list->tail = q_list->first_entry_addr;
956     q_list->cnt = 0;
957 }
958 
959 
960 __inline
961 void
962 q_list_push_head(
963     q_list_t *q_list,
964     q_list_entry_t q_entry)
965 {
966     if(q_list->cnt < q_list->max_cnt)
967     {
968         if(q_list->head == q_list->first_entry_addr)
969         {
970             q_list->head = q_list->last_entry_addr;
971         }
972         else
973         {
974             q_list->head--;
975         }
976 
977         *(q_list->head) = q_entry;
978         q_list->cnt++;
979     }
980 }
981 
982 
983 __inline
984 q_list_entry_t
985 q_list_pop_head(
986     q_list_t *q_list)
987 {
988     q_list_entry_t q_entry;
989 
990     q_entry = q_list->cnt ? *q_list->head : (q_list_entry_t *) 0;
991     if(q_list->cnt)
992     {
993         if(q_list->head == q_list->last_entry_addr)
994         {
995             q_list->head = q_list->first_entry_addr;
996         }
997         else
998         {
999             q_list->head++;
1000         }
1001 
1002         q_list->cnt--;
1003     }
1004 
1005     return q_entry;
1006 }
1007 
1008 
1009 __inline
1010 void
1011 q_list_push_tail(
1012     q_list_t *q_list,
1013     q_list_entry_t q_entry)
1014 {
1015     if(q_list->cnt < q_list->max_cnt)
1016     {
1017         *q_list->tail = q_entry;
1018         if(q_list->tail == q_list->last_entry_addr)
1019         {
1020             q_list->tail = q_list->first_entry_addr;
1021         }
1022         else
1023         {
1024             q_list->tail++;
1025         }
1026 
1027         q_list->cnt++;
1028     }
1029 }
1030 
1031 
1032 __inline
1033 q_list_entry_t
1034 q_list_pop_tail(
1035     q_list_t *q_list)
1036 {
1037     q_list_entry_t q_entry;
1038 
1039     q_entry = q_list->cnt ?
1040         (q_list->tail == q_list->first_entry_addr ?
1041             *q_list->last_entry_addr : *(q_list->tail-1)) :
1042         (q_list_entry_t *) 0;
1043 
1044     if(q_list->cnt)
1045     {
1046         if(q_list->tail == q_list->first_entry_addr)
1047         {
1048             q_list->tail = q_list->last_entry_addr;
1049         }
1050         else
1051         {
1052             q_list->tail--;
1053         }
1054 
1055         q_list->cnt--;
1056     }
1057 
1058     return q_entry;
1059 }
1060 
1061 
1062 __inline
1063 q_list_entry_t
1064 q_list_peek_head(
1065     q_list_t *q_list)
1066 {
1067     q_list_entry_t q_entry;
1068 
1069     q_entry = q_list->cnt ? *q_list->head : (q_list_entry_t *) 0;
1070 
1071     return q_entry;
1072 }
1073 
1074 
1075 __inline
1076 q_list_entry_t
1077 q_list_peek_tail(
1078     q_list_t *q_list)
1079 {
1080     q_list_entry_t q_entry;
1081 
1082     q_entry = q_list->cnt ?
1083         (q_list->tail == q_list->first_entry_addr ?
1084             *q_list->last_entry_addr : *(q_list->tail - 1)) :
1085         (q_list_entry_t *) 0;
1086 
1087     return q_entry;
1088 }
1089 
1090 
1091 __inline
1092 unsigned long
1093 q_list_entry_cnt(
1094     q_list_t *q_list)
1095 {
1096     return q_list->cnt;
1097 }
1098 
1099 
1100 __inline
1101 char
1102 q_list_is_empty(
1103     q_list_t *q_list)
1104 {
1105     return q_list->cnt == 0;
1106 }
1107 
1108 
1109 __inline
1110 char
1111 q_list_is_full(
1112     q_list_t *q_list)
1113 {
1114     return q_list->cnt == q_list->max_cnt;
1115 }
1116 
1117 
1118 #else
1119 
1120 
1121 #define q_list_init(_q_list, _q_list_arr, _max_cnt) \
1122     (_q_list)->max_cnt = (_max_cnt); \
1123     (_q_list)->first_entry_addr = (_q_list_arr); \
1124     (_q_list)->last_entry_addr = (_q_list_arr) + ((_max_cnt) - 1); \
1125     (_q_list)->head = (_q_list)->first_entry_addr; \
1126     (_q_list)->tail = (_q_list)->first_entry_addr; \
1127     (_q_list)->cnt = 0
1128 
1129 
1130 #define q_list_clear(_q_list) \
1131     (_q_list)->head = (_q_list)->first_entry_addr; \
1132     (_q_list)->tail = (_q_list)->first_entry_addr; \
1133     (_q_list)->cnt = 0
1134 
1135 
1136 #define q_list_push_head(_q_list, _q_entry) \
1137     if((_q_list)->cnt < (_q_list)->max_cnt) \
1138     { \
1139         if((_q_list)->head == (_q_list)->first_entry_addr) \
1140         { \
1141             (_q_list)->head = (_q_list)->last_entry_addr; \
1142         } \
1143         else \
1144         { \
1145             (_q_list)->head--; \
1146         } \
1147         *((_q_list)->head) = (_q_entry); \
1148         (_q_list)->cnt++; \
1149     }
1150 
1151 
1152 #define q_list_pop_head(_q_list) \
1153     (_q_list)->cnt ? *(_q_list)->head : (q_list_entry_t *) 0; \
1154     if((_q_list)->cnt) \
1155     { \
1156         if((_q_list)->head == (_q_list)->last_entry_addr) \
1157         { \
1158             (_q_list)->head = (_q_list)->first_entry_addr; \
1159         } \
1160         else \
1161         { \
1162             (_q_list)->head++; \
1163         } \
1164         (_q_list)->cnt--; \
1165     }
1166 
1167 
1168 #define q_list_push_tail(_q_list, _q_entry) \
1169     if((_q_list)->cnt < (_q_list)->max_cnt) \
1170     { \
1171         *(_q_list)->tail = (_q_entry); \
1172         if((_q_list)->tail == (_q_list)->last_entry_addr) \
1173         { \
1174             (_q_list)->tail = (_q_list)->first_entry_addr; \
1175         } \
1176         else \
1177         { \
1178             (_q_list)->tail++; \
1179         } \
1180         (_q_list)->cnt++; \
1181     }
1182 
1183 
1184 #define q_list_pop_tail(_q_list) \
1185     (_q_list)->cnt ? ((_q_list)->tail == (_q_list)->first_entry_addr ? \
1186         *(_q_list)->last_entry_addr : *((_q_list)->tail-1)) : \
1187         (q_list_entry_t *) 0; \
1188     if((_q_list)->cnt) \
1189     { \
1190         if((_q_list)->tail == (_q_list)->first_entry_addr) \
1191         { \
1192             (_q_list)->tail = (_q_list)->last_entry_addr; \
1193         } \
1194         else \
1195         { \
1196             (_q_list)->tail--; \
1197         } \
1198         (_q_list)->cnt--; \
1199     } \
1200 
1201 
1202 #define q_list_peek_head(_q_list) \
1203     ((_q_list)->cnt ? *(_q_list)->head : (q_list_entry_t *) 0)
1204 
1205 
1206 #define q_list_peek_tail(_q_list) \
1207     ((_q_list)->cnt ? ((_q_list)->tail == (_q_list)->first_entry_addr ? \
1208         *(_q_list)->last_entry_addr : *((_q_list)->tail - 1)) : \
1209         (q_list_entry_t *) 0)
1210 
1211 
1212 #define q_list_entry_cnt(_q_list)   ((_q_list)->cnt)
1213 
1214 
1215 #define q_list_is_empty(_q_list)    ((_q_list)->cnt == 0)
1216 
1217 
1218 #define q_list_is_full(_q_list)     ((_q_list)->cnt == (_q_list)->max_cnt)
1219 
1220 
1221 #endif
1222 
1223 
1224 
1225 
1226 #endif /* _listq_h_ */
1227 
1228