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