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
s_list_init(s_list_t * s_list,s_list_entry_t * head_entry,s_list_entry_t * tail_entry,unsigned long entry_cnt)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
s_list_clear(s_list_t * s_list)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
s_list_push_head(s_list_t * s_list,s_list_entry_t * s_entry)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 *
s_list_pop_head(s_list_t * s_list)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
s_list_push_tail(s_list_t * s_list,s_list_entry_t * s_entry)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 *
s_list_peek_head(s_list_t * s_list)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 *
s_list_peek_tail(s_list_t * s_list)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 *
s_list_next_entry(s_list_entry_t * s_entry)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
s_list_entry_cnt(s_list_t * s_list)213 s_list_entry_cnt(
214 s_list_t *s_list)
215 {
216 return s_list->cnt;
217 }
218
219
220 __inline
221 char
s_list_is_empty(s_list_t * s_list)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
s_list_add_head(s_list_t * s_list,s_list_t * s_list_head)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
s_list_add_tail(s_list_t * s_list,s_list_t * s_list_tail)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
s_list_split(s_list_t * s_list,s_list_t * s_list_head,s_list_entry_t * split_entry,unsigned long entry_cnt)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
d_list_init(d_list_t * d_list,d_list_entry_t * head_entry,d_list_entry_t * tail_entry,unsigned long entry_cnt)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
d_list_clear(d_list_t * d_list)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
d_list_push_head(d_list_t * d_list,d_list_entry_t * d_entry)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 *
d_list_pop_head(d_list_t * d_list)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
d_list_push_tail(d_list_t * d_list,d_list_entry_t * d_entry)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 *
d_list_pop_tail(d_list_t * d_list)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 *
d_list_peek_head(d_list_t * d_list)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 *
d_list_peek_tail(d_list_t * d_list)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 *
d_list_next_entry(d_list_entry_t * d_entry)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
d_list_remove_entry(d_list_t * d_list,d_list_entry_t * d_entry)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
d_list_insert_entry(d_list_t * d_list,d_list_entry_t * d_entry_prev,d_list_entry_t * d_entry_next,d_list_entry_t * d_entry)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 *
d_list_prev_entry(d_list_entry_t * d_entry)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
d_list_entry_cnt(d_list_t * d_list)645 d_list_entry_cnt(
646 d_list_t *d_list)
647 {
648 return d_list->cnt;
649 }
650
651
652 __inline
653 char
d_list_is_empty(d_list_t * d_list)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
d_list_add_head(d_list_t * d_list,d_list_t * d_list_head)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
d_list_add_tail(d_list_t * d_list,d_list_t * d_list_tail)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
q_list_init(q_list_t * q_list,q_list_entry_t q_list_arr[],unsigned long max_cnt)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
q_list_clear(q_list_t * q_list)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
q_list_push_head(q_list_t * q_list,q_list_entry_t q_entry)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
q_list_pop_head(q_list_t * q_list)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
q_list_push_tail(q_list_t * q_list,q_list_entry_t q_entry)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
q_list_pop_tail(q_list_t * q_list)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
q_list_peek_head(q_list_t * q_list)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
q_list_peek_tail(q_list_t * q_list)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
q_list_entry_cnt(q_list_t * q_list)1093 q_list_entry_cnt(
1094 q_list_t *q_list)
1095 {
1096 return q_list->cnt;
1097 }
1098
1099
1100 __inline
1101 char
q_list_is_empty(q_list_t * q_list)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
q_list_is_full(q_list_t * q_list)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