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 "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 const struct exec_node *
 133 exec_node_get_next_const(const struct exec_node *n)
 134 {
 135    return n->next;
 136 }
 137
 138 static inline struct exec_node *
 139 exec_node_get_next(struct exec_node *n)
 140 {
 141    return n->next;
 142 }
 143
 144 static inline const struct exec_node *
 145 exec_node_get_prev_const(const struct exec_node *n)
 146 {
 147    return n->prev;
 148 }
 149
 150 static inline struct exec_node *
 151 exec_node_get_prev(struct exec_node *n)
 152 {
 153    return n->prev;
 154 }
 155
 156 static inline void
 157 exec_node_remove(struct exec_node *n)
 158 {
 159    n->next->prev = n->prev;
 160    n->prev->next = n->next;
 161    n->next = NULL;
 162    n->prev = NULL;
 163 }
 164
 165 static inline void
 166 exec_node_self_link(struct exec_node *n)
 167 {
 168    n->next = n;
 169    n->prev = n;
 170 }
 171
 172 static inline void
 173 exec_node_insert_after(struct exec_node *n, struct exec_node *after)
 174 {
 175    after->next = n->next;
 176    after->prev = n;
 177
 178    n->next->prev = after;
 179    n->next = after;
 180 }
 181
 182 static inline void
 183 exec_node_insert_node_before(struct exec_node *n, struct exec_node *before)
 184 {
 185    before->next = n;
 186    before->prev = n->prev;
 187
 188    n->prev->next = before;
 189    n->prev = before;
 190 }
 191
 192 static inline void
 193 exec_node_replace_with(struct exec_node *n, struct exec_node *replacement)
 194 {
 195    replacement->prev = n->prev;
 196    replacement->next = n->next;
 197
 198    n->prev->next = replacement;
 199    n->next->prev = replacement;
 200 }
 201
 202 static inline bool
 203 exec_node_is_tail_sentinel(const struct exec_node *n)
 204 {
 205    return n->next == NULL;
 206 }
 207
 208 static inline bool
 209 exec_node_is_head_sentinel(const struct exec_node *n)
 210 {
 211    return n->prev == NULL;
 212 }
 213
 214 #ifdef __cplusplus
 215 inline const exec_node *exec_node::get_next() const
 216 {
 217    return exec_node_get_next_const(this);
 218 }
 219
 220 inline exec_node *exec_node::get_next()
 221 {
 222    return exec_node_get_next(this);
 223 }
 224
 225 inline const exec_node *exec_node::get_prev() const
 226 {
 227    return exec_node_get_prev_const(this);
 228 }
 229
 230 inline exec_node *exec_node::get_prev()
 231 {
 232    return exec_node_get_prev(this);
 233 }
 234
 235 inline void exec_node::remove()
 236 {
 237    exec_node_remove(this);
 238 }
 239
 240 inline void exec_node::self_link()
 241 {
 242    exec_node_self_link(this);
 243 }
 244
 245 inline void exec_node::insert_after(exec_node *after)
 246 {
 247    exec_node_insert_after(this, after);
 248 }
 249
 250 inline void exec_node::insert_before(exec_node *before)
 251 {
 252    exec_node_insert_node_before(this, before);
 253 }
 254
 255 inline void exec_node::replace_with(exec_node *replacement)
 256 {
 257    exec_node_replace_with(this, replacement);
 258 }
 259
 260 inline bool exec_node::is_tail_sentinel() const
 261 {
 262    return exec_node_is_tail_sentinel(this);
 263 }
 264
 265 inline bool exec_node::is_head_sentinel() const
 266 {
 267    return exec_node_is_head_sentinel(this);
 268 }
 269 #endif
 270
 271 #ifdef __cplusplus
 272 /* This macro will not work correctly if `t' uses virtual inheritance.  If you
 273  * are using virtual inheritance, you deserve a slow and painful death.  Enjoy!
 274  */
 275 #define exec_list_offsetof(t, f, p) \
 276    (((char *) &((t *) p)->f) - ((char *) p))
 277 #else
 278 #define exec_list_offsetof(t, f, p) offsetof(t, f)
 279 #endif
 280
 281 /**
 282  * Get a pointer to the structure containing an exec_node
 283  *
 284  * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
 285  * the containing structure.
 286  *
 287  * \param type  Base type of the structure containing the node
 288  * \param node  Pointer to the \c exec_node
 289  * \param field Name of the field in \c type that is the embedded \c exec_node
 290  */
 291 #define exec_node_data(type, node, field) \
 292    ((type *) (((char *) node) - exec_list_offsetof(type, field, node)))
 293
 294 #ifdef __cplusplus
 295 struct exec_node;
 296 #endif
 297
 298 struct exec_list {
 299    struct exec_node *head;
 300    struct exec_node *tail;
 301    struct exec_node *tail_pred;
 302
 303 #ifdef __cplusplus
 304    DECLARE_RALLOC_CXX_OPERATORS(exec_list)
 305
 306    exec_list()
 307    {
 308       make_empty();
 309    }
 310
 311    void make_empty();
 312
 313    bool is_empty() const;
 314
 315    const exec_node *get_head() const;
 316    exec_node *get_head();
 317
 318    const exec_node *get_tail() const;
 319    exec_node *get_tail();
 320
 321    void push_head(exec_node *n);
 322    void push_tail(exec_node *n);
 323    void push_degenerate_list_at_head(exec_node *n);
 324
 325    /**
 326     * Remove the first node from a list and return it
 327     *
 328     * \return
 329     * The first node in the list or \c NULL if the list is empty.
 330     *
 331     * \sa exec_list::get_head
 332     */
 333    exec_node *pop_head();
 334
 335    /**
 336     * Move all of the nodes from this list to the target list
 337     */
 338    void move_nodes_to(exec_list *target);
 339
 340    /**
 341     * Append all nodes from the source list to the target list
 342     */
 343    void append_list(exec_list *source);
 344 #endif
 345 };
 346
 347 static inline void
 348 exec_list_make_empty(struct exec_list *list)
 349 {
 350    list->head = (struct exec_node *) & list->tail;
 351    list->tail = NULL;
 352    list->tail_pred = (struct exec_node *) & list->head;
 353 }
 354
 355 static inline bool
 356 exec_list_is_empty(const struct exec_list *list)
 357 {
 358    /* There are three ways to test whether a list is empty or not.
 359     *
 360     * - Check to see if the \c head points to the \c tail.
 361     * - Check to see if the \c tail_pred points to the \c head.
 362     * - Check to see if the \c head is the sentinel node by test whether its
 363     *   \c next pointer is \c NULL.
 364     *
 365     * The first two methods tend to generate better code on modern systems
 366     * because they save a pointer dereference.
 367     */
 368    return list->head == (struct exec_node *) &list->tail;
 369 }
 370
 371 static inline const struct exec_node *
 372 exec_list_get_head_const(const struct exec_list *list)
 373 {
 374    return !exec_list_is_empty(list) ? list->head : NULL;
 375 }
 376
 377 static inline struct exec_node *
 378 exec_list_get_head(struct exec_list *list)
 379 {
 380    return !exec_list_is_empty(list) ? list->head : NULL;
 381 }
 382
 383 static inline const struct exec_node *
 384 exec_list_get_tail_const(const struct exec_list *list)
 385 {
 386    return !exec_list_is_empty(list) ? list->tail_pred : NULL;
 387 }
 388
 389 static inline struct exec_node *
 390 exec_list_get_tail(struct exec_list *list)
 391 {
 392    return !exec_list_is_empty(list) ? list->tail_pred : NULL;
 393 }
 394
 395 static inline void
 396 exec_list_push_head(struct exec_list *list, struct exec_node *n)
 397 {
 398    n->next = list->head;
 399    n->prev = (struct exec_node *) &list->head;
 400
 401    n->next->prev = n;
 402    list->head = n;
 403 }
 404
 405 static inline void
 406 exec_list_push_tail(struct exec_list *list, struct exec_node *n)
 407 {
 408    n->next = (struct exec_node *) &list->tail;
 409    n->prev = list->tail_pred;
 410
 411    n->prev->next = n;
 412    list->tail_pred = n;
 413 }
 414
 415 static inline void
 416 exec_list_push_degenerate_list_at_head(struct exec_list *list, struct exec_node *n)
 417 {
 418    assert(n->prev->next == n);
 419
 420    n->prev->next = list->head;
 421    list->head->prev = n->prev;
 422    n->prev = (struct exec_node *) &list->head;
 423    list->head = n;
 424 }
 425
 426 static inline struct exec_node *
 427 exec_list_pop_head(struct exec_list *list)
 428 {
 429    struct exec_node *const n = exec_list_get_head(list);
 430    if (n != NULL)
 431       exec_node_remove(n);
 432
 433    return n;
 434 }
 435
 436 static inline void
 437 exec_list_move_nodes_to(struct exec_list *list, struct exec_list *target)
 438 {
 439    if (exec_list_is_empty(list)) {
 440       exec_list_make_empty(target);
 441    } else {
 442       target->head = list->head;
 443       target->tail = NULL;
 444       target->tail_pred = list->tail_pred;
 445
 446       target->head->prev = (struct exec_node *) &target->head;
 447       target->tail_pred->next = (struct exec_node *) &target->tail;
 448
 449       exec_list_make_empty(list);
 450    }
 451 }
 452
 453 static inline void
 454 exec_list_append(struct exec_list *list, struct exec_list *source)
 455 {
 456    if (exec_list_is_empty(source))
 457       return;
 458
 459    /* Link the first node of the source with the last node of the target list.
 460     */
 461    list->tail_pred->next = source->head;
 462    source->head->prev = list->tail_pred;
 463
 464    /* Make the tail of the source list be the tail of the target list.
 465     */
 466    list->tail_pred = source->tail_pred;
 467    list->tail_pred->next = (struct exec_node *) &list->tail;
 468
 469    /* Make the source list empty for good measure.
 470     */
 471    exec_list_make_empty(source);
 472 }
 473
 474 static inline void
 475 exec_node_insert_list_before(struct exec_node *n, struct exec_list *before)
 476 {
 477    if (exec_list_is_empty(before))
 478       return;
 479
 480    before->tail_pred->next = n;
 481    before->head->prev = n->prev;
 482
 483    n->prev->next = before->head;
 484    n->prev = before->tail_pred;
 485
 486    exec_list_make_empty(before);
 487 }
 488
 489 #ifdef __cplusplus
 490 inline void exec_list::make_empty()
 491 {
 492    exec_list_make_empty(this);
 493 }
 494
 495 inline bool exec_list::is_empty() const
 496 {
 497    return exec_list_is_empty(this);
 498 }
 499
 500 inline const exec_node *exec_list::get_head() const
 501 {
 502    return exec_list_get_head_const(this);
 503 }
 504
 505 inline exec_node *exec_list::get_head()
 506 {
 507    return exec_list_get_head(this);
 508 }
 509
 510 inline const exec_node *exec_list::get_tail() const
 511 {
 512    return exec_list_get_tail_const(this);
 513 }
 514
 515 inline exec_node *exec_list::get_tail()
 516 {
 517    return exec_list_get_tail(this);
 518 }
 519
 520 inline void exec_list::push_head(exec_node *n)
 521 {
 522    exec_list_push_head(this, n);
 523 }
 524
 525 inline void exec_list::push_tail(exec_node *n)
 526 {
 527    exec_list_push_tail(this, n);
 528 }
 529
 530 inline void exec_list::push_degenerate_list_at_head(exec_node *n)
 531 {
 532    exec_list_push_degenerate_list_at_head(this, n);
 533 }
 534
 535 inline exec_node *exec_list::pop_head()
 536 {
 537    return exec_list_pop_head(this);
 538 }
 539
 540 inline void exec_list::move_nodes_to(exec_list *target)
 541 {
 542    exec_list_move_nodes_to(this, target);
 543 }
 544
 545 inline void exec_list::append_list(exec_list *source)
 546 {
 547    exec_list_append(this, source);
 548 }
 549
 550 inline void exec_node::insert_before(exec_list *before)
 551 {
 552    exec_node_insert_list_before(this, before);
 553 }
 554 #endif
 555
 556 /**
 557  * This version is safe even if the current node is removed.
 558  */
 559 #define foreach_list_safe(__node, __list)                                       \
 560    for (struct exec_node * __node = (__list)->head, * __next = __node->next     \
 561         ; __next != NULL                                                        \
 562         ; __node = __next, __next = __next->next)
 563
 564 #define foreach_list(__node, __list)                    \
 565    for (struct exec_node * __node = (__list)->head      \
 566         ; (__node)->next != NULL                        \
 567         ; (__node) = (__node)->next)
 568
 569 /**
 570  * Iterate through two lists at once.  Stops at the end of the shorter list.
 571  *
 572  * This is safe against either current node being removed or replaced.
 573  */
 574 #define foreach_two_lists(__node1, __list1, __node2, __list2) \
 575    for (struct exec_node * __node1 = (__list1)->head,         \
 576                          * __node2 = (__list2)->head,         \
 577                          * __next1 = __node1->next,           \
 578                          * __next2 = __node2->next            \
 579         ; __next1 != NULL && __next2 != NULL                  \
 580         ; __node1 = __next1,                                  \
 581           __node2 = __next2,                                  \
 582           __next1 = __next1->next,                            \
 583           __next2 = __next2->next)
 584
 585 #define foreach_list_const(__node, __list)                      \
 586    for (const struct exec_node * __node = (__list)->head        \
 587         ; (__node)->next != NULL                                \
 588         ; (__node) = (__node)->next)
 589
 590 #define foreach_list_typed(__type, __node, __field, __list)             \
 591    for (__type * __node =                                               \
 592            exec_node_data(__type, (__list)->head, __field);             \
 593         (__node)->__field.next != NULL;                                 \
 594         (__node) = exec_node_data(__type, (__node)->__field.next, __field))
 595
 596 #define foreach_list_typed_const(__type, __node, __field, __list)       \
 597    for (const __type * __node =                                         \
 598            exec_node_data(__type, (__list)->head, __field);             \
 599         (__node)->__field.next != NULL;                                 \
 600         (__node) = exec_node_data(__type, (__node)->__field.next, __field))
 601
 602 #endif /* LIST_CONTAINER_H */