src/compiler/glsl/list.h

   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 */