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 #ifndef __cplusplus
  68 #include <stddef.h>
  69 #endif
  70 #include <assert.h>
  71
  72 struct exec_node {
  73    struct exec_node *next;
  74    struct exec_node *prev;
  75
  76 #ifdef __cplusplus
  77    exec_node() : next(NULL), prev(NULL)
  78    {
  79       /* empty */
  80    }
  81
  82    const exec_node *get_next() const
  83    {
  84       return next;
  85    }
  86
  87    exec_node *get_next()
  88    {
  89       return next;
  90    }
  91
  92    const exec_node *get_prev() const
  93    {
  94       return prev;
  95    }
  96
  97    exec_node *get_prev()
  98    {
  99       return prev;
 100    }
 101
 102    void remove()
 103    {
 104       next->prev = prev;
 105       prev->next = next;
 106       next = NULL;
 107       prev = NULL;
 108    }
 109
 110    /**
 111     * Link a node with itself
 112     *
 113     * This creates a sort of degenerate list that is occasionally useful.
 114     */
 115    void self_link()
 116    {
 117       next = this;
 118       prev = this;
 119    }
 120
 121    /**
 122     * Insert a node in the list after the current node
 123     */
 124    void insert_after(exec_node *after)
 125    {
 126       after->next = this->next;
 127       after->prev = this;
 128
 129       this->next->prev = after;
 130       this->next = after;
 131    }
 132    /**
 133     * Insert a node in the list before the current node
 134     */
 135    void insert_before(exec_node *before)
 136    {
 137       before->next = this;
 138       before->prev = this->prev;
 139
 140       this->prev->next = before;
 141       this->prev = before;
 142    }
 143 #endif
 144 };
 145
 146
 147 #ifdef __cplusplus
 148 /* This macro will not work correctly if `t' uses virtual inheritance.  If you
 149  * are using virtual inheritance, you deserve a slow and painful death.  Enjoy!
 150  */
 151 #define exec_list_offsetof(t, f, p) \
 152    (((char *) &((t *) p)->f) - ((char *) p))
 153 #else
 154 #define exec_list_offsetof(t, f, p) offsetof(t, f)
 155 #endif
 156
 157 /**
 158  * Get a pointer to the structure containing an exec_node
 159  *
 160  * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
 161  * the containing structure.
 162  *
 163  * \param type  Base type of the structure containing the node
 164  * \param node  Pointer to the \c exec_node
 165  * \param field Name of the field in \c type that is the embedded \c exec_node
 166  */
 167 #define exec_node_data(type, node, field) \
 168    ((type *) (((char *) node) - exec_list_offsetof(type, field, node)))
 169
 170 #ifdef __cplusplus
 171 struct exec_node;
 172
 173 class iterator {
 174 public:
 175    void next()
 176    {
 177    }
 178
 179    void *get()
 180    {
 181       return NULL;
 182    }
 183
 184    bool has_next() const
 185    {
 186       return false;
 187    }
 188 };
 189
 190 class exec_list_iterator : public iterator {
 191 public:
 192    exec_list_iterator(exec_node *n) : node(n), _next(n->next)
 193    {
 194       /* empty */
 195    }
 196
 197    void next()
 198    {
 199       node = _next;
 200       _next = node->next;
 201    }
 202
 203    void remove()
 204    {
 205       node->remove();
 206    }
 207
 208    exec_node *get()
 209    {
 210       return node;
 211    }
 212
 213    bool has_next() const
 214    {
 215       return _next != NULL;
 216    }
 217
 218 private:
 219    exec_node *node;
 220    exec_node *_next;
 221 };
 222
 223 #define foreach_iter(iter_type, iter, container) \
 224    for (iter_type iter = (container) . iterator(); iter.has_next(); iter.next())
 225 #endif
 226
 227
 228 struct exec_list {
 229    struct exec_node *head;
 230    struct exec_node *tail;
 231    struct exec_node *tail_pred;
 232
 233 #ifdef __cplusplus
 234    exec_list()
 235    {
 236       make_empty();
 237    }
 238
 239    void make_empty()
 240    {
 241       head = (exec_node *) & tail;
 242       tail = NULL;
 243       tail_pred = (exec_node *) & head;
 244    }
 245
 246    bool is_empty() const
 247    {
 248       /* There are three ways to test whether a list is empty or not.
 249        *
 250        * - Check to see if the \c head points to the \c tail.
 251        * - Check to see if the \c tail_pred points to the \c head.
 252        * - Check to see if the \c head is the sentinal node by test whether its
 253        *   \c next pointer is \c NULL.
 254        *
 255        * The first two methods tend to generate better code on modern systems
 256        * because they save a pointer dereference.
 257        */
 258       return head == (exec_node *) &tail;
 259    }
 260
 261    const exec_node *get_head() const
 262    {
 263       return !is_empty() ? head : NULL;
 264    }
 265
 266    exec_node *get_head()
 267    {
 268       return !is_empty() ? head : NULL;
 269    }
 270
 271    const exec_node *get_tail() const
 272    {
 273       return !is_empty() ? tail_pred : NULL;
 274    }
 275
 276    exec_node *get_tail()
 277    {
 278       return !is_empty() ? tail_pred : NULL;
 279    }
 280
 281    void push_head(exec_node *n)
 282    {
 283       n->next = head;
 284       n->prev = (exec_node *) &head;
 285
 286       n->next->prev = n;
 287       head = n;
 288    }
 289
 290    void push_tail(exec_node *n)
 291    {
 292       n->next = (exec_node *) &tail;
 293       n->prev = tail_pred;
 294
 295       n->prev->next = n;
 296       tail_pred = n;
 297    }
 298
 299    void push_degenerate_list_at_head(exec_node *n)
 300    {
 301       assert(n->prev->next == n);
 302
 303       n->prev->next = head;
 304       head->prev = n->prev;
 305       n->prev = (exec_node *) &head;
 306       head = n;
 307    }
 308
 309    /**
 310     * Move all of the nodes from this list to the target list
 311     */
 312    void move_nodes_to(exec_list *target)
 313    {
 314       if (is_empty()) {
 315          target->make_empty();
 316       } else {
 317          target->head = head;
 318          target->tail = NULL;
 319          target->tail_pred = tail_pred;
 320
 321          target->head->prev = (exec_node *) &target->head;
 322          target->tail_pred->next = (exec_node *) &target->tail;
 323
 324          make_empty();
 325       }
 326    }
 327
 328    exec_list_iterator iterator()
 329    {
 330       return exec_list_iterator(head);
 331    }
 332
 333    exec_list_iterator iterator() const
 334    {
 335       return exec_list_iterator((exec_node *) head);
 336    }
 337 #endif
 338 };
 339
 340 #endif /* LIST_CONTAINER_H */