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 sentinal head and tail node.  These nodes
  29  * contain no data.  The head sentinal can be identified by its \c prev
  30  * pointer being \c NULL.  The tail sentinal can be identified by its
  31  * \c next pointer being \c NULL.
  32  *
  33  * A list is empty if either the head sentinal's \c next pointer points to the
  34  * tail sentinal or the tail sentinal's \c prev poiner points to the head
  35  * sentinal.
  36  *
  37  * Instead of tracking two separate \c node structures and a \c list structure
  38  * that points to them, the sentinal nodes are in a single structure.  Noting
  39  * that each sentinal 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 sentinal node.
  45  *   - A \c tail pointer that represents the \c prev pointer of the head
  46  *     sentinal node and the \c next pointer of the tail sentinal 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 sentinal 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 #include <assert.h>
  68
  69 struct exec_node {
  70    struct exec_node *next;
  71    struct exec_node *prev;
  72
  73 #ifdef __cplusplus
  74    exec_node() : next(NULL), prev(NULL)
  75    {
  76       /* empty */
  77    }
  78
  79    const exec_node *get_next() const
  80    {
  81       return next;
  82    }
  83
  84    exec_node *get_next()
  85    {
  86       return next;
  87    }
  88
  89    const exec_node *get_prev() const
  90    {
  91       return prev;
  92    }
  93
  94    exec_node *get_prev()
  95    {
  96       return prev;
  97    }
  98
  99    void remove()
 100    {
 101       next->prev = prev;
 102       prev->next = next;
 103       next = NULL;
 104       prev = NULL;
 105    }
 106
 107    /**
 108     * Link a node with itself
 109     *
 110     * This creates a sort of degenerate list that is occasionally useful.
 111     */
 112    void self_link()
 113    {
 114       next = this;
 115       prev = this;
 116    }
 117
 118    /**
 119     * Insert a node in the list after the current node
 120     */
 121    void insert_after(exec_node *after)
 122    {
 123       after->next = this->next;
 124       after->prev = this;
 125
 126       this->next->prev = after;
 127       this->next = after;
 128    }
 129    /**
 130     * Insert a node in the list before the current node
 131     */
 132    void insert_before(exec_node *before)
 133    {
 134       before->next = this;
 135       before->prev = this->prev;
 136
 137       this->prev->next = before;
 138       this->prev = before;
 139    }
 140 #endif
 141 };
 142
 143 #ifdef __cplusplus
 144 struct exec_node;
 145
 146 class iterator {
 147 public:
 148    void next()
 149    {
 150    }
 151
 152    void *get()
 153    {
 154       return NULL;
 155    }
 156
 157    bool has_next() const
 158    {
 159       return false;
 160    }
 161 };
 162
 163 class exec_list_iterator : public iterator {
 164 public:
 165    exec_list_iterator(exec_node *n) : node(n), _next(n->next)
 166    {
 167       /* empty */
 168    }
 169
 170    void next()
 171    {
 172       node = _next;
 173       _next = node->next;
 174    }
 175
 176    void remove()
 177    {
 178       node->remove();
 179    }
 180
 181    exec_node *get()
 182    {
 183       return node;
 184    }
 185
 186    bool has_next() const
 187    {
 188       return _next != NULL;
 189    }
 190
 191 private:
 192    exec_node *node;
 193    exec_node *_next;
 194 };
 195
 196 #define foreach_iter(iter_type, iter, container) \
 197    for (iter_type iter = (container) . iterator(); iter.has_next(); iter.next())
 198 #endif
 199
 200
 201 struct exec_list {
 202    struct exec_node *head;
 203    struct exec_node *tail;
 204    struct exec_node *tail_pred;
 205
 206 #ifdef __cplusplus
 207    exec_list()
 208    {
 209       make_empty();
 210    }
 211
 212    void make_empty()
 213    {
 214       head = (exec_node *) & tail;
 215       tail = NULL;
 216       tail_pred = (exec_node *) & head;
 217    }
 218
 219    bool is_empty() const
 220    {
 221       /* There are three ways to test whether a list is empty or not.
 222        *
 223        * - Check to see if the \c head points to the \c tail.
 224        * - Check to see if the \c tail_pred points to the \c head.
 225        * - Check to see if the \c head is the sentinal node by test whether its
 226        *   \c next pointer is \c NULL.
 227        *
 228        * The first two methods tend to generate better code on modern systems
 229        * because they save a pointer dereference.
 230        */
 231       return head == (exec_node *) &tail;
 232    }
 233
 234    const exec_node *get_head() const
 235    {
 236       return !is_empty() ? head : NULL;
 237    }
 238
 239    exec_node *get_head()
 240    {
 241       return !is_empty() ? head : NULL;
 242    }
 243
 244    const exec_node *get_tail() const
 245    {
 246       return !is_empty() ? tail_pred : NULL;
 247    }
 248
 249    exec_node *get_tail()
 250    {
 251       return !is_empty() ? tail_pred : NULL;
 252    }
 253
 254    void push_head(exec_node *n)
 255    {
 256       n->next = head;
 257       n->prev = (exec_node *) &head;
 258
 259       n->next->prev = n;
 260       head = n;
 261    }
 262
 263    void push_tail(exec_node *n)
 264    {
 265       n->next = (exec_node *) &tail;
 266       n->prev = tail_pred;
 267
 268       n->prev->next = n;
 269       tail_pred = n;
 270    }
 271
 272    void push_degenerate_list_at_head(exec_node *n)
 273    {
 274       assert(n->prev->next == n);
 275
 276       n->prev->next = head;
 277       head->prev = n->prev;
 278       n->prev = (exec_node *) &head;
 279       head = n;
 280    }
 281
 282    /**
 283     * Move all of the nodes from this list to the target list
 284     */
 285    void move_nodes_to(exec_list *target)
 286    {
 287       if (is_empty()) {
 288          target->make_empty();
 289       } else {
 290          target->head = head;
 291          target->tail = NULL;
 292          target->tail_pred = tail_pred;
 293
 294          target->head->prev = (exec_node *) &target->head;
 295          target->tail_pred->next = (exec_node *) &target->tail;
 296
 297          make_empty();
 298       }
 299    }
 300
 301    exec_list_iterator iterator()
 302    {
 303       return exec_list_iterator(head);
 304    }
 305
 306    exec_list_iterator iterator() const
 307    {
 308       return exec_list_iterator((exec_node *) head);
 309    }
 310 #endif
 311 };
 312
 313 #endif /* LIST_CONTAINER_H */