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