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