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
76typedef 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
84typedef 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
97void
98s_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
111void
112s_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
122void
123s_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
140s_list_entry_t *
141s_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
163void
164s_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
185s_list_entry_t *
186s_list_peek_head(
187    s_list_t *s_list)
188{
189    return s_list->head;
190}
191
192
193__inline
194s_list_entry_t *
195s_list_peek_tail(
196    s_list_t *s_list)
197{
198    return s_list->tail;
199}
200
201
202__inline
203s_list_entry_t *
204s_list_next_entry(
205    s_list_entry_t *s_entry)
206{
207    return s_entry->next;
208}
209
210
211__inline
212unsigned long
213s_list_entry_cnt(
214    s_list_t *s_list)
215{
216    return s_list->cnt;
217}
218
219
220__inline
221char
222s_list_is_empty(
223    s_list_t *s_list)
224{
225    return s_list->cnt == 0;
226}
227
228
229__inline
230void
231s_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
249void
250s_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
267void
268s_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
410typedef 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
419typedef 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
432void
433d_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
446void
447d_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
457void
458d_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
481d_list_entry_t *
482d_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
508void
509d_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
531d_list_entry_t *
532d_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
559d_list_entry_t *
560d_list_peek_head(
561    d_list_t *d_list)
562{
563    return d_list->head;
564}
565
566
567__inline
568d_list_entry_t *
569d_list_peek_tail(
570    d_list_t *d_list)
571{
572    return d_list->tail;
573}
574
575
576__inline
577d_list_entry_t *
578d_list_next_entry(
579    d_list_entry_t *d_entry)
580{
581    return d_entry->next;
582}
583
584
585__inline
586void
587d_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
608void
609d_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
635d_list_entry_t *
636d_list_prev_entry(
637    d_list_entry_t *d_entry)
638{
639    return d_entry->prev;
640}
641
642
643__inline
644unsigned long
645d_list_entry_cnt(
646    d_list_t *d_list)
647{
648    return d_list->cnt;
649}
650
651
652__inline
653char
654d_list_is_empty(
655    d_list_t *d_list)
656{
657    return d_list->cnt == 0;
658}
659
660
661__inline
662void
663d_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
684void
685d_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
914typedef void *q_list_entry_t;
915
916typedef 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
933void
934q_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
950void
951q_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
961void
962q_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
984q_list_entry_t
985q_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
1010void
1011q_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
1033q_list_entry_t
1034q_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
1063q_list_entry_t
1064q_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
1076q_list_entry_t
1077q_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
1092unsigned long
1093q_list_entry_cnt(
1094    q_list_t *q_list)
1095{
1096    return q_list->cnt;
1097}
1098
1099
1100__inline
1101char
1102q_list_is_empty(
1103    q_list_t *q_list)
1104{
1105    return q_list->cnt == 0;
1106}
1107
1108
1109__inline
1110char
1111q_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