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    /* Callers of this ralloc-based new need not call delete. It's
  80     * easier to just ralloc_free 'ctx' (or any of its ancestors). */
  81    static void* operator new(size_t size, void *ctx)
  82    {
  83       void *node;
  84
  85       node = ralloc_size(ctx, size);
  86       assert(node != NULL);
  87
  88       return node;
  89    }
  90
  91    /* If the user *does* call delete, that's OK, we will just
  92     * ralloc_free in that case. */
  93    static void operator delete(void *node)
  94    {
  95       ralloc_free(node);
  96    }
  97
  98    exec_node() : next(NULL), prev(NULL)
  99    {
 100       /* empty */
 101    }
 102
 103    const exec_node *get_next() const
 104    {
 105       return next;
 106    }
 107
 108    exec_node *get_next()
 109    {
 110       return next;
 111    }
 112
 113    const exec_node *get_prev() const
 114    {
 115       return prev;
 116    }
 117
 118    exec_node *get_prev()
 119    {
 120       return prev;
 121    }
 122
 123    void remove()
 124    {
 125       next->prev = prev;
 126       prev->next = next;
 127       next = NULL;
 128       prev = NULL;
 129    }
 130
 131    /**
 132     * Link a node with itself
 133     *
 134     * This creates a sort of degenerate list that is occasionally useful.
 135     */
 136    void self_link()
 137    {
 138       next = this;
 139       prev = this;
 140    }
 141
 142    /**
 143     * Insert a node in the list after the current node
 144     */
 145    void insert_after(exec_node *after)
 146    {
 147       after->next = this->next;
 148       after->prev = this;
 149
 150       this->next->prev = after;
 151       this->next = after;
 152    }
 153    /**
 154     * Insert a node in the list before the current node
 155     */
 156    void insert_before(exec_node *before)
 157    {
 158       before->next = this;
 159       before->prev = this->prev;
 160
 161       this->prev->next = before;
 162       this->prev = before;
 163    }
 164
 165    /**
 166     * Insert another list in the list before the current node
 167     */
 168    void insert_before(struct exec_list *before);
 169
 170    /**
 171     * Replace the current node with the given node.
 172     */
 173    void replace_with(exec_node *replacement)
 174    {
 175       replacement->prev = this->prev;
 176       replacement->next = this->next;
 177
 178       this->prev->next = replacement;
 179       this->next->prev = replacement;
 180    }
 181
 182    /**
 183     * Is this the sentinel at the tail of the list?
 184     */
 185    bool is_tail_sentinel() const
 186    {
 187       return this->next == NULL;
 188    }
 189
 190    /**
 191     * Is this the sentinel at the head of the list?
 192     */
 193    bool is_head_sentinel() const
 194    {
 195       return this->prev == NULL;
 196    }
 197 #endif
 198 };
 199
 200
 201 #ifdef __cplusplus
 202 /* This macro will not work correctly if `t' uses virtual inheritance.  If you
 203  * are using virtual inheritance, you deserve a slow and painful death.  Enjoy!
 204  */
 205 #define exec_list_offsetof(t, f, p) \
 206    (((char *) &((t *) p)->f) - ((char *) p))
 207 #else
 208 #define exec_list_offsetof(t, f, p) offsetof(t, f)
 209 #endif
 210
 211 /**
 212  * Get a pointer to the structure containing an exec_node
 213  *
 214  * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
 215  * the containing structure.
 216  *
 217  * \param type  Base type of the structure containing the node
 218  * \param node  Pointer to the \c exec_node
 219  * \param field Name of the field in \c type that is the embedded \c exec_node
 220  */
 221 #define exec_node_data(type, node, field) \
 222    ((type *) (((char *) node) - exec_list_offsetof(type, field, node)))
 223
 224 #ifdef __cplusplus
 225 struct exec_node;
 226
 227 class iterator {
 228 public:
 229    void next()
 230    {
 231    }
 232
 233    void *get()
 234    {
 235       return NULL;
 236    }
 237
 238    bool has_next() const
 239    {
 240       return false;
 241    }
 242 };
 243
 244 class exec_list_iterator : public iterator {
 245 public:
 246    exec_list_iterator(exec_node *n) : node(n), _next(n->next)
 247    {
 248       /* empty */
 249    }
 250
 251    void next()
 252    {
 253       node = _next;
 254       _next = node->next;
 255    }
 256
 257    void remove()
 258    {
 259       node->remove();
 260    }
 261
 262    exec_node *get()
 263    {
 264       return node;
 265    }
 266
 267    bool has_next() const
 268    {
 269       return _next != NULL;
 270    }
 271
 272 private:
 273    exec_node *node;
 274    exec_node *_next;
 275 };
 276
 277 #define foreach_iter(iter_type, iter, container) \
 278    for (iter_type iter = (container) . iterator(); iter.has_next(); iter.next())
 279 #endif
 280
 281
 282 struct exec_list {
 283    struct exec_node *head;
 284    struct exec_node *tail;
 285    struct exec_node *tail_pred;
 286
 287 #ifdef __cplusplus
 288    /* Callers of this ralloc-based new need not call delete. It's
 289     * easier to just ralloc_free 'ctx' (or any of its ancestors). */
 290    static void* operator new(size_t size, void *ctx)
 291    {
 292       void *node;
 293
 294       node = ralloc_size(ctx, size);
 295       assert(node != NULL);
 296
 297       return node;
 298    }
 299
 300    /* If the user *does* call delete, that's OK, we will just
 301     * ralloc_free in that case. */
 302    static void operator delete(void *node)
 303    {
 304       ralloc_free(node);
 305    }
 306
 307    exec_list()
 308    {
 309       make_empty();
 310    }
 311
 312    void make_empty()
 313    {
 314       head = (exec_node *) & tail;
 315       tail = NULL;
 316       tail_pred = (exec_node *) & head;
 317    }
 318
 319    bool is_empty() const
 320    {
 321       /* There are three ways to test whether a list is empty or not.
 322        *
 323        * - Check to see if the \c head points to the \c tail.
 324        * - Check to see if the \c tail_pred points to the \c head.
 325        * - Check to see if the \c head is the sentinel node by test whether its
 326        *   \c next pointer is \c NULL.
 327        *
 328        * The first two methods tend to generate better code on modern systems
 329        * because they save a pointer dereference.
 330        */
 331       return head == (exec_node *) &tail;
 332    }
 333
 334    const exec_node *get_head() const
 335    {
 336       return !is_empty() ? head : NULL;
 337    }
 338
 339    exec_node *get_head()
 340    {
 341       return !is_empty() ? head : NULL;
 342    }
 343
 344    const exec_node *get_tail() const
 345    {
 346       return !is_empty() ? tail_pred : NULL;
 347    }
 348
 349    exec_node *get_tail()
 350    {
 351       return !is_empty() ? tail_pred : NULL;
 352    }
 353
 354    void push_head(exec_node *n)
 355    {
 356       n->next = head;
 357       n->prev = (exec_node *) &head;
 358
 359       n->next->prev = n;
 360       head = n;
 361    }
 362
 363    void push_tail(exec_node *n)
 364    {
 365       n->next = (exec_node *) &tail;
 366       n->prev = tail_pred;
 367
 368       n->prev->next = n;
 369       tail_pred = n;
 370    }
 371
 372    void push_degenerate_list_at_head(exec_node *n)
 373    {
 374       assert(n->prev->next == n);
 375
 376       n->prev->next = head;
 377       head->prev = n->prev;
 378       n->prev = (exec_node *) &head;
 379       head = n;
 380    }
 381
 382    /**
 383     * Remove the first node from a list and return it
 384     *
 385     * \return
 386     * The first node in the list or \c NULL if the list is empty.
 387     *
 388     * \sa exec_list::get_head
 389     */
 390    exec_node *pop_head()
 391    {
 392       exec_node *const n = this->get_head();
 393       if (n != NULL)
 394          n->remove();
 395
 396       return n;
 397    }
 398
 399    /**
 400     * Move all of the nodes from this list to the target list
 401     */
 402    void move_nodes_to(exec_list *target)
 403    {
 404       if (is_empty()) {
 405          target->make_empty();
 406       } else {
 407          target->head = head;
 408          target->tail = NULL;
 409          target->tail_pred = tail_pred;
 410
 411          target->head->prev = (exec_node *) &target->head;
 412          target->tail_pred->next = (exec_node *) &target->tail;
 413
 414          make_empty();
 415       }
 416    }
 417
 418    /**
 419     * Append all nodes from the source list to the target list
 420     */
 421    void
 422    append_list(exec_list *source)
 423    {
 424       if (source->is_empty())
 425          return;
 426
 427       /* Link the first node of the source with the last node of the target list.
 428        */
 429       this->tail_pred->next = source->head;
 430       source->head->prev = this->tail_pred;
 431
 432       /* Make the tail of the source list be the tail of the target list.
 433        */
 434       this->tail_pred = source->tail_pred;
 435       this->tail_pred->next = (exec_node *) &this->tail;
 436
 437       /* Make the source list empty for good measure.
 438        */
 439       source->make_empty();
 440    }
 441
 442    exec_list_iterator iterator()
 443    {
 444       return exec_list_iterator(head);
 445    }
 446
 447    exec_list_iterator iterator() const
 448    {
 449       return exec_list_iterator((exec_node *) head);
 450    }
 451 #endif
 452 };
 453
 454
 455 #ifdef __cplusplus
 456 inline void exec_node::insert_before(exec_list *before)
 457 {
 458    if (before->is_empty())
 459       return;
 460
 461    before->tail_pred->next = this;
 462    before->head->prev = this->prev;
 463
 464    this->prev->next = before->head;
 465    this->prev = before->tail_pred;
 466
 467    before->make_empty();
 468 }
 469 #endif
 470
 471 /**
 472  * This version is safe even if the current node is removed.
 473  */
 474 #define foreach_list_safe(__node, __list)                            \
 475    for (exec_node * __node = (__list)->head, * __next = __node->next \
 476         ; __next != NULL                                             \
 477         ; __node = __next, __next = __next->next)
 478
 479 #define foreach_list(__node, __list)                    \
 480    for (exec_node * __node = (__list)->head             \
 481         ; (__node)->next != NULL                        \
 482         ; (__node) = (__node)->next)
 483
 484 #define foreach_list_const(__node, __list)              \
 485    for (const exec_node * __node = (__list)->head       \
 486         ; (__node)->next != NULL                        \
 487         ; (__node) = (__node)->next)
 488
 489 #define foreach_list_typed(__type, __node, __field, __list)             \
 490    for (__type * __node =                                               \
 491            exec_node_data(__type, (__list)->head, __field);             \
 492         (__node)->__field.next != NULL;                                 \
 493         (__node) = exec_node_data(__type, (__node)->__field.next, __field))
 494
 495 #define foreach_list_typed_const(__type, __node, __field, __list)       \
 496    for (const __type * __node =                                         \
 497            exec_node_data(__type, (__list)->head, __field);             \
 498         (__node)->__field.next != NULL;                                 \
 499         (__node) = exec_node_data(__type, (__node)->__field.next, __field))
 500
 501 #endif /* LIST_CONTAINER_H */