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 #endif
 130 };
 131
 132 #ifdef __cplusplus
 133 struct exec_node;
 134
 135 class iterator {
 136 public:
 137    void next()
 138    {
 139    }
 140
 141    void *get()
 142    {
 143       return NULL;
 144    }
 145
 146    bool has_next() const
 147    {
 148       return false;
 149    }
 150 };
 151
 152 class exec_list_iterator : public iterator {
 153 public:
 154    exec_list_iterator(exec_node *n) : node(n), _next(n->next)
 155    {
 156       /* empty */
 157    }
 158
 159    void next()
 160    {
 161       node = _next;
 162       _next = node->next;
 163    }
 164
 165    void remove()
 166    {
 167       node->remove();
 168    }
 169
 170    exec_node *get()
 171    {
 172       return node;
 173    }
 174
 175    bool has_next() const
 176    {
 177       return _next != NULL;
 178    }
 179
 180 private:
 181    exec_node *node;
 182    exec_node *_next;
 183 };
 184
 185 #define foreach_iter(iter_type, iter, container) \
 186    for (iter_type iter = (container) . iterator(); iter.has_next(); iter.next())
 187 #endif
 188
 189
 190 struct exec_list {
 191    struct exec_node *head;
 192    struct exec_node *tail;
 193    struct exec_node *tail_pred;
 194
 195 #ifdef __cplusplus
 196    exec_list()
 197    {
 198       make_empty();
 199    }
 200
 201    void make_empty()
 202    {
 203       head = (exec_node *) & tail;
 204       tail = NULL;
 205       tail_pred = (exec_node *) & head;
 206    }
 207
 208    bool is_empty() const
 209    {
 210       /* There are three ways to test whether a list is empty or not.
 211        *
 212        * - Check to see if the \c head points to the \c tail.
 213        * - Check to see if the \c tail_pred points to the \c head.
 214        * - Check to see if the \c head is the sentinal node by test whether its
 215        *   \c next pointer is \c NULL.
 216        *
 217        * The first two methods tend to generate better code on modern systems
 218        * because they save a pointer dereference.
 219        */
 220       return head == (exec_node *) &tail;
 221    }
 222
 223    const exec_node *get_head() const
 224    {
 225       return !is_empty() ? head : NULL;
 226    }
 227
 228    exec_node *get_head()
 229    {
 230       return !is_empty() ? head : NULL;
 231    }
 232
 233    const exec_node *get_tail() const
 234    {
 235       return !is_empty() ? tail_pred : NULL;
 236    }
 237
 238    exec_node *get_tail()
 239    {
 240       return !is_empty() ? tail_pred : NULL;
 241    }
 242
 243    void push_head(exec_node *n)
 244    {
 245       n->next = head;
 246       n->prev = (exec_node *) &head;
 247
 248       n->next->prev = n;
 249       head = n;
 250    }
 251
 252    void push_tail(exec_node *n)
 253    {
 254       n->next = (exec_node *) &tail;
 255       n->prev = tail_pred;
 256
 257       n->prev->next = n;
 258       tail_pred = n;
 259    }
 260
 261    void push_degenerate_list_at_head(exec_node *n)
 262    {
 263       assert(n->prev->next == n);
 264
 265       n->prev->next = head;
 266       head->prev = n->prev;
 267       n->prev = (exec_node *) &head;
 268       head = n;
 269    }
 270
 271    /**
 272     * Move all of the nodes from this list to the target list
 273     */
 274    void move_nodes_to(exec_list *target)
 275    {
 276       target->head = head;
 277       target->tail = NULL;
 278       target->tail_pred = tail_pred;
 279
 280       target->head->prev = (exec_node *) &target->head;
 281       target->tail_pred->next = (exec_node *) &target->tail;
 282
 283       make_empty();
 284    }
 285
 286    exec_list_iterator iterator()
 287    {
 288       return exec_list_iterator(head);
 289    }
 290
 291    exec_list_iterator iterator() const
 292    {
 293       return exec_list_iterator((exec_node *) head);
 294    }
 295 #endif
 296 };
 297
 298 #endif /* LIST_CONTAINER_H */