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