1 /* 2 * Copyright 2008, 2010 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 24 /** 25 * \file list.h 26 * \brief Doubly-linked list abstract container type. 27 * 28 * Each doubly-linked list has a sentinel head and tail node. These nodes 29 * contain no data. The head sentinel can be identified by its \c prev 30 * pointer being \c NULL. The tail sentinel can be identified by its 31 * \c next pointer being \c NULL. 32 * 33 * A list is empty if either the head sentinel's \c next pointer points to the 34 * tail sentinel or the tail sentinel's \c prev poiner points to the head 35 * sentinel. The head sentinel and tail sentinel nodes are allocated within the 36 * list structure. 37 * 38 * Do note that this means that the list nodes will contain pointers into the 39 * list structure itself and as a result you may not \c realloc() an \c 40 * exec_list or any structure in which an \c exec_list is embedded. 41 */ 42 43 #ifndef LIST_CONTAINER_H 44 #define LIST_CONTAINER_H 45 46 #ifndef __cplusplus 47 #include <stddef.h> 48 #endif 49 #include <assert.h> 50 51 #include "util/ralloc.h" 52 53 struct exec_node { 54 struct exec_node *next; 55 struct exec_node *prev; 56 57 #ifdef __cplusplus 58 DECLARE_RZALLOC_CXX_OPERATORS(exec_node) 59 60 exec_node() : next(NULL), prev(NULL) 61 { 62 /* empty */ 63 } 64 65 const exec_node *get_next() const; 66 exec_node *get_next(); 67 68 const exec_node *get_prev() const; 69 exec_node *get_prev(); 70 71 void remove(); 72 73 /** 74 * Link a node with itself 75 * 76 * This creates a sort of degenerate list that is occasionally useful. 77 */ 78 void self_link(); 79 80 /** 81 * Insert a node in the list after the current node 82 */ 83 void insert_after(exec_node *after); 84 /** 85 * Insert a node in the list before the current node 86 */ 87 void insert_before(exec_node *before); 88 89 /** 90 * Insert another list in the list before the current node 91 */ 92 void insert_before(struct exec_list *before); 93 94 /** 95 * Replace the current node with the given node. 96 */ 97 void replace_with(exec_node *replacement); 98 99 /** 100 * Is this the sentinel at the tail of the list? 101 */ 102 bool is_tail_sentinel() const; 103 104 /** 105 * Is this the sentinel at the head of the list? 106 */ 107 bool is_head_sentinel() const; 108 #endif 109 }; 110 111 static inline void 112 exec_node_init(struct exec_node *n) 113 { 114 n->next = NULL; 115 n->prev = NULL; 116 } 117 118 static inline const struct exec_node * 119 exec_node_get_next_const(const struct exec_node *n) 120 { 121 return n->next; 122 } 123 124 static inline struct exec_node * 125 exec_node_get_next(struct exec_node *n) 126 { 127 return n->next; 128 } 129 130 static inline const struct exec_node * 131 exec_node_get_prev_const(const struct exec_node *n) 132 { 133 return n->prev; 134 } 135 136 static inline struct exec_node * 137 exec_node_get_prev(struct exec_node *n) 138 { 139 return n->prev; 140 } 141 142 static inline void 143 exec_node_remove(struct exec_node *n) 144 { 145 n->next->prev = n->prev; 146 n->prev->next = n->next; 147 n->next = NULL; 148 n->prev = NULL; 149 } 150 151 static inline void 152 exec_node_self_link(struct exec_node *n) 153 { 154 n->next = n; 155 n->prev = n; 156 } 157 158 static inline void 159 exec_node_insert_after(struct exec_node *n, struct exec_node *after) 160 { 161 after->next = n->next; 162 after->prev = n; 163 164 n->next->prev = after; 165 n->next = after; 166 } 167 168 static inline void 169 exec_node_insert_node_before(struct exec_node *n, struct exec_node *before) 170 { 171 before->next = n; 172 before->prev = n->prev; 173 174 n->prev->next = before; 175 n->prev = before; 176 } 177 178 static inline void 179 exec_node_replace_with(struct exec_node *n, struct exec_node *replacement) 180 { 181 replacement->prev = n->prev; 182 replacement->next = n->next; 183 184 n->prev->next = replacement; 185 n->next->prev = replacement; 186 } 187 188 static inline bool 189 exec_node_is_tail_sentinel(const struct exec_node *n) 190 { 191 return n->next == NULL; 192 } 193 194 static inline bool 195 exec_node_is_head_sentinel(const struct exec_node *n) 196 { 197 return n->prev == NULL; 198 } 199 200 #ifdef __cplusplus 201 inline const exec_node *exec_node::get_next() const 202 { 203 return exec_node_get_next_const(this); 204 } 205 206 inline exec_node *exec_node::get_next() 207 { 208 return exec_node_get_next(this); 209 } 210 211 inline const exec_node *exec_node::get_prev() const 212 { 213 return exec_node_get_prev_const(this); 214 } 215 216 inline exec_node *exec_node::get_prev() 217 { 218 return exec_node_get_prev(this); 219 } 220 221 inline void exec_node::remove() 222 { 223 exec_node_remove(this); 224 } 225 226 inline void exec_node::self_link() 227 { 228 exec_node_self_link(this); 229 } 230 231 inline void exec_node::insert_after(exec_node *after) 232 { 233 exec_node_insert_after(this, after); 234 } 235 236 inline void exec_node::insert_before(exec_node *before) 237 { 238 exec_node_insert_node_before(this, before); 239 } 240 241 inline void exec_node::replace_with(exec_node *replacement) 242 { 243 exec_node_replace_with(this, replacement); 244 } 245 246 inline bool exec_node::is_tail_sentinel() const 247 { 248 return exec_node_is_tail_sentinel(this); 249 } 250 251 inline bool exec_node::is_head_sentinel() const 252 { 253 return exec_node_is_head_sentinel(this); 254 } 255 #endif 256 257 #ifdef __cplusplus 258 /* This macro will not work correctly if `t' uses virtual inheritance. If you 259 * are using virtual inheritance, you deserve a slow and painful death. Enjoy! 260 */ 261 #define exec_list_offsetof(t, f, p) \ 262 (((char *) &((t *) p)->f) - ((char *) p)) 263 #else 264 #define exec_list_offsetof(t, f, p) offsetof(t, f) 265 #endif 266 267 /** 268 * Get a pointer to the structure containing an exec_node 269 * 270 * Given a pointer to an \c exec_node embedded in a structure, get a pointer to 271 * the containing structure. 272 * 273 * \param type Base type of the structure containing the node 274 * \param node Pointer to the \c exec_node 275 * \param field Name of the field in \c type that is the embedded \c exec_node 276 */ 277 #define exec_node_data(type, node, field) \ 278 ((type *) (((char *) node) - exec_list_offsetof(type, field, node))) 279 280 #ifdef __cplusplus 281 struct exec_node; 282 #endif 283 284 struct exec_list { 285 struct exec_node head_sentinel; 286 struct exec_node tail_sentinel; 287 288 #ifdef __cplusplus 289 DECLARE_RALLOC_CXX_OPERATORS(exec_list) 290 291 exec_list() 292 { 293 make_empty(); 294 } 295 296 void make_empty(); 297 298 bool is_empty() const; 299 300 const exec_node *get_head() const; 301 exec_node *get_head(); 302 const exec_node *get_head_raw() const; 303 exec_node *get_head_raw(); 304 305 const exec_node *get_tail() const; 306 exec_node *get_tail(); 307 const exec_node *get_tail_raw() const; 308 exec_node *get_tail_raw(); 309 310 unsigned length() const; 311 312 void push_head(exec_node *n); 313 void push_tail(exec_node *n); 314 void push_degenerate_list_at_head(exec_node *n); 315 316 /** 317 * Remove the first node from a list and return it 318 * 319 * \return 320 * The first node in the list or \c NULL if the list is empty. 321 * 322 * \sa exec_list::get_head 323 */ 324 exec_node *pop_head(); 325 326 /** 327 * Move all of the nodes from this list to the target list 328 */ 329 void move_nodes_to(exec_list *target); 330 331 /** 332 * Append all nodes from the source list to the end of the target list 333 */ 334 void append_list(exec_list *source); 335 336 /** 337 * Prepend all nodes from the source list to the beginning of the target 338 * list 339 */ 340 void prepend_list(exec_list *source); 341 #endif 342 }; 343 344 static inline void 345 exec_list_make_empty(struct exec_list *list) 346 { 347 list->head_sentinel.next = &list->tail_sentinel; 348 list->head_sentinel.prev = NULL; 349 list->tail_sentinel.next = NULL; 350 list->tail_sentinel.prev = &list->head_sentinel; 351 } 352 353 static inline bool 354 exec_list_is_empty(const struct exec_list *list) 355 { 356 /* There are three ways to test whether a list is empty or not. 357 * 358 * - Check to see if the head sentinel's \c next is the tail sentinel. 359 * - Check to see if the tail sentinel's \c prev is the head sentinel. 360 * - Check to see if the head is the sentinel node by test whether its 361 * \c next pointer is \c NULL. 362 * 363 * The first two methods tend to generate better code on modern systems 364 * because they save a pointer dereference. 365 */ 366 return list->head_sentinel.next == &list->tail_sentinel; 367 } 368 369 static inline const struct exec_node * 370 exec_list_get_head_const(const struct exec_list *list) 371 { 372 return !exec_list_is_empty(list) ? list->head_sentinel.next : NULL; 373 } 374 375 static inline struct exec_node * 376 exec_list_get_head(struct exec_list *list) 377 { 378 return !exec_list_is_empty(list) ? list->head_sentinel.next : NULL; 379 } 380 381 static inline const struct exec_node * 382 exec_list_get_head_raw_const(const struct exec_list *list) 383 { 384 return list->head_sentinel.next; 385 } 386 387 static inline struct exec_node * 388 exec_list_get_head_raw(struct exec_list *list) 389 { 390 return list->head_sentinel.next; 391 } 392 393 static inline const struct exec_node * 394 exec_list_get_tail_const(const struct exec_list *list) 395 { 396 return !exec_list_is_empty(list) ? list->tail_sentinel.prev : NULL; 397 } 398 399 static inline struct exec_node * 400 exec_list_get_tail(struct exec_list *list) 401 { 402 return !exec_list_is_empty(list) ? list->tail_sentinel.prev : NULL; 403 } 404 405 static inline const struct exec_node * 406 exec_list_get_tail_raw_const(const struct exec_list *list) 407 { 408 return list->tail_sentinel.prev; 409 } 410 411 static inline struct exec_node * 412 exec_list_get_tail_raw(struct exec_list *list) 413 { 414 return list->tail_sentinel.prev; 415 } 416 417 static inline unsigned 418 exec_list_length(const struct exec_list *list) 419 { 420 unsigned size = 0; 421 struct exec_node *node; 422 423 for (node = list->head_sentinel.next; node->next != NULL; node = node->next) { 424 size++; 425 } 426 427 return size; 428 } 429 430 static inline void 431 exec_list_push_head(struct exec_list *list, struct exec_node *n) 432 { 433 n->next = list->head_sentinel.next; 434 n->prev = &list->head_sentinel; 435 436 n->next->prev = n; 437 list->head_sentinel.next = n; 438 } 439 440 static inline void 441 exec_list_push_tail(struct exec_list *list, struct exec_node *n) 442 { 443 n->next = &list->tail_sentinel; 444 n->prev = list->tail_sentinel.prev; 445 446 n->prev->next = n; 447 list->tail_sentinel.prev = n; 448 } 449 450 static inline void 451 exec_list_push_degenerate_list_at_head(struct exec_list *list, struct exec_node *n) 452 { 453 assert(n->prev->next == n); 454 455 n->prev->next = list->head_sentinel.next; 456 list->head_sentinel.next->prev = n->prev; 457 n->prev = &list->head_sentinel; 458 list->head_sentinel.next = n; 459 } 460 461 static inline struct exec_node * 462 exec_list_pop_head(struct exec_list *list) 463 { 464 struct exec_node *const n = exec_list_get_head(list); 465 if (n != NULL) 466 exec_node_remove(n); 467 468 return n; 469 } 470 471 static inline void 472 exec_list_move_nodes_to(struct exec_list *list, struct exec_list *target) 473 { 474 if (exec_list_is_empty(list)) { 475 exec_list_make_empty(target); 476 } else { 477 target->head_sentinel.next = list->head_sentinel.next; 478 target->head_sentinel.prev = NULL; 479 target->tail_sentinel.next = NULL; 480 target->tail_sentinel.prev = list->tail_sentinel.prev; 481 482 target->head_sentinel.next->prev = &target->head_sentinel; 483 target->tail_sentinel.prev->next = &target->tail_sentinel; 484 485 exec_list_make_empty(list); 486 } 487 } 488 489 static inline void 490 exec_list_append(struct exec_list *list, struct exec_list *source) 491 { 492 if (exec_list_is_empty(source)) 493 return; 494 495 /* Link the first node of the source with the last node of the target list. 496 */ 497 list->tail_sentinel.prev->next = source->head_sentinel.next; 498 source->head_sentinel.next->prev = list->tail_sentinel.prev; 499 500 /* Make the tail of the source list be the tail of the target list. 501 */ 502 list->tail_sentinel.prev = source->tail_sentinel.prev; 503 list->tail_sentinel.prev->next = &list->tail_sentinel; 504 505 /* Make the source list empty for good measure. 506 */ 507 exec_list_make_empty(source); 508 } 509 510 static inline void 511 exec_list_prepend(struct exec_list *list, struct exec_list *source) 512 { 513 exec_list_append(source, list); 514 exec_list_move_nodes_to(source, list); 515 } 516 517 static inline void 518 exec_node_insert_list_before(struct exec_node *n, struct exec_list *before) 519 { 520 if (exec_list_is_empty(before)) 521 return; 522 523 before->tail_sentinel.prev->next = n; 524 before->head_sentinel.next->prev = n->prev; 525 526 n->prev->next = before->head_sentinel.next; 527 n->prev = before->tail_sentinel.prev; 528 529 exec_list_make_empty(before); 530 } 531 532 static inline void 533 exec_list_validate(const struct exec_list *list) 534 { 535 const struct exec_node *node; 536 537 assert(list->head_sentinel.next->prev == &list->head_sentinel); 538 assert(list->head_sentinel.prev == NULL); 539 assert(list->tail_sentinel.next == NULL); 540 assert(list->tail_sentinel.prev->next == &list->tail_sentinel); 541 542 /* We could try to use one of the interators below for this but they all 543 * either require C++ or assume the exec_node is embedded in a structure 544 * which is not the case for this function. 545 */ 546 for (node = list->head_sentinel.next; node->next != NULL; node = node->next) { 547 assert(node->next->prev == node); 548 assert(node->prev->next == node); 549 } 550 } 551 552 #ifdef __cplusplus 553 inline void exec_list::make_empty() 554 { 555 exec_list_make_empty(this); 556 } 557 558 inline bool exec_list::is_empty() const 559 { 560 return exec_list_is_empty(this); 561 } 562 563 inline const exec_node *exec_list::get_head() const 564 { 565 return exec_list_get_head_const(this); 566 } 567 568 inline exec_node *exec_list::get_head() 569 { 570 return exec_list_get_head(this); 571 } 572 573 inline const exec_node *exec_list::get_head_raw() const 574 { 575 return exec_list_get_head_raw_const(this); 576 } 577 578 inline exec_node *exec_list::get_head_raw() 579 { 580 return exec_list_get_head_raw(this); 581 } 582 583 inline const exec_node *exec_list::get_tail() const 584 { 585 return exec_list_get_tail_const(this); 586 } 587 588 inline exec_node *exec_list::get_tail() 589 { 590 return exec_list_get_tail(this); 591 } 592 593 inline const exec_node *exec_list::get_tail_raw() const 594 { 595 return exec_list_get_tail_raw_const(this); 596 } 597 598 inline exec_node *exec_list::get_tail_raw() 599 { 600 return exec_list_get_tail_raw(this); 601 } 602 603 inline unsigned exec_list::length() const 604 { 605 return exec_list_length(this); 606 } 607 608 inline void exec_list::push_head(exec_node *n) 609 { 610 exec_list_push_head(this, n); 611 } 612 613 inline void exec_list::push_tail(exec_node *n) 614 { 615 exec_list_push_tail(this, n); 616 } 617 618 inline void exec_list::push_degenerate_list_at_head(exec_node *n) 619 { 620 exec_list_push_degenerate_list_at_head(this, n); 621 } 622 623 inline exec_node *exec_list::pop_head() 624 { 625 return exec_list_pop_head(this); 626 } 627 628 inline void exec_list::move_nodes_to(exec_list *target) 629 { 630 exec_list_move_nodes_to(this, target); 631 } 632 633 inline void exec_list::append_list(exec_list *source) 634 { 635 exec_list_append(this, source); 636 } 637 638 inline void exec_list::prepend_list(exec_list *source) 639 { 640 exec_list_prepend(this, source); 641 } 642 643 inline void exec_node::insert_before(exec_list *before) 644 { 645 exec_node_insert_list_before(this, before); 646 } 647 #endif 648 649 #define foreach_in_list(__type, __inst, __list) \ 650 for (__type *(__inst) = (__type *)(__list)->head_sentinel.next; \ 651 !(__inst)->is_tail_sentinel(); \ 652 (__inst) = (__type *)(__inst)->next) 653 654 #define foreach_in_list_reverse(__type, __inst, __list) \ 655 for (__type *(__inst) = (__type *)(__list)->tail_sentinel.prev; \ 656 !(__inst)->is_head_sentinel(); \ 657 (__inst) = (__type *)(__inst)->prev) 658 659 /** 660 * This version is safe even if the current node is removed. 661 */ 662 #define foreach_in_list_safe(__type, __node, __list) \ 663 for (__type *__node = (__type *)(__list)->head_sentinel.next, \ 664 *__next = (__type *)__node->next; \ 665 __next != NULL; \ 666 __node = __next, __next = (__type *)__next->next) 667 668 #define foreach_in_list_reverse_safe(__type, __node, __list) \ 669 for (__type *__node = (__type *)(__list)->tail_sentinel.prev, \ 670 *__prev = (__type *)__node->prev; \ 671 __prev != NULL; \ 672 __node = __prev, __prev = (__type *)__prev->prev) 673 674 #define foreach_in_list_use_after(__type, __inst, __list) \ 675 __type *(__inst); \ 676 for ((__inst) = (__type *)(__list)->head_sentinel.next; \ 677 !(__inst)->is_tail_sentinel(); \ 678 (__inst) = (__type *)(__inst)->next) 679 /** 680 * Iterate through two lists at once. Stops at the end of the shorter list. 681 * 682 * This is safe against either current node being removed or replaced. 683 */ 684 #define foreach_two_lists(__node1, __list1, __node2, __list2) \ 685 for (struct exec_node * __node1 = (__list1)->head_sentinel.next, \ 686 * __node2 = (__list2)->head_sentinel.next, \ 687 * __next1 = __node1->next, \ 688 * __next2 = __node2->next \ 689 ; __next1 != NULL && __next2 != NULL \ 690 ; __node1 = __next1, \ 691 __node2 = __next2, \ 692 __next1 = __next1->next, \ 693 __next2 = __next2->next) 694 695 #define foreach_list_typed(__type, __node, __field, __list) \ 696 for (__type * __node = \ 697 exec_node_data(__type, (__list)->head_sentinel.next, __field); \ 698 (__node)->__field.next != NULL; \ 699 (__node) = exec_node_data(__type, (__node)->__field.next, __field)) 700 701 #define foreach_list_typed_from(__type, __node, __field, __list, __start) \ 702 for (__type * __node = exec_node_data(__type, (__start), __field); \ 703 (__node)->__field.next != NULL; \ 704 (__node) = exec_node_data(__type, (__node)->__field.next, __field)) 705 706 #define foreach_list_typed_reverse(__type, __node, __field, __list) \ 707 for (__type * __node = \ 708 exec_node_data(__type, (__list)->tail_sentinel.prev, __field); \ 709 (__node)->__field.prev != NULL; \ 710 (__node) = exec_node_data(__type, (__node)->__field.prev, __field)) 711 712 #define foreach_list_typed_safe(__type, __node, __field, __list) \ 713 for (__type * __node = \ 714 exec_node_data(__type, (__list)->head_sentinel.next, __field), \ 715 * __next = \ 716 exec_node_data(__type, (__node)->__field.next, __field); \ 717 (__node)->__field.next != NULL; \ 718 __node = __next, __next = \ 719 exec_node_data(__type, (__next)->__field.next, __field)) 720 721 #define foreach_list_typed_reverse_safe(__type, __node, __field, __list) \ 722 for (__type * __node = \ 723 exec_node_data(__type, (__list)->tail_sentinel.prev, __field), \ 724 * __prev = \ 725 exec_node_data(__type, (__node)->__field.prev, __field); \ 726 (__node)->__field.prev != NULL; \ 727 __node = __prev, __prev = \ 728 exec_node_data(__type, (__prev)->__field.prev, __field)) 729 730 #endif /* LIST_CONTAINER_H */ 731