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