2 * Copyright © 2008, 2010 Intel Corporation
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:
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
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.
26 * \brief Doubly-linked list abstract container type.
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.
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
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:
43 * - A \c head pointer that represents the \c next pointer of the
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
51 * Therefore, if \c head->next is \c NULL or \c tail_prev->prev is \c NULL,
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.
58 * http://www.natami.net/dev/Libraries_Manual_guide/node02D7.html
60 * \author Ian Romanick <ian.d.romanick@intel.com>
64 #ifndef LIST_CONTAINER_H
65 #define LIST_CONTAINER_H
70 struct exec_node *next;
71 struct exec_node *prev;
74 exec_node() : next(NULL), prev(NULL)
79 const exec_node *get_next() const
89 const exec_node *get_prev() const
108 * Link a node with itself
110 * This creates a sort of degenerate list that is occasionally useful.
119 * Insert a node in the list after the current node
121 void insert_after(exec_node *after)
123 after->next = this->next;
126 this->next->prev = after;
146 bool has_next() const
152 class exec_list_iterator : public iterator {
154 exec_list_iterator(exec_node *n) : node(n), _next(n->next)
175 bool has_next() const
177 return _next != NULL;
185 #define foreach_iter(iter_type, iter, container) \
186 for (iter_type iter = (container) . iterator(); iter.has_next(); iter.next())
191 struct exec_node *head;
192 struct exec_node *tail;
193 struct exec_node *tail_pred;
203 head = (exec_node *) & tail;
205 tail_pred = (exec_node *) & head;
208 bool is_empty() const
210 /* There are three ways to test whether a list is empty or not.
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.
217 * The first two methods tend to generate better code on modern systems
218 * because they save a pointer dereference.
220 return head == (exec_node *) &tail;
223 const exec_node *get_head() const
225 return !is_empty() ? head : NULL;
228 exec_node *get_head()
230 return !is_empty() ? head : NULL;
233 const exec_node *get_tail() const
235 return !is_empty() ? tail_pred : NULL;
238 exec_node *get_tail()
240 return !is_empty() ? tail_pred : NULL;
243 void push_head(exec_node *n)
246 n->prev = (exec_node *) &head;
252 void push_tail(exec_node *n)
254 n->next = (exec_node *) &tail;
261 void push_degenerate_list_at_head(exec_node *n)
263 assert(n->prev->next == n);
265 n->prev->next = head;
266 head->prev = n->prev;
267 n->prev = (exec_node *) &head;
272 * Move all of the nodes from this list to the target list
274 void move_nodes_to(exec_list *target)
278 target->tail_pred = tail_pred;
280 target->head->prev = (exec_node *) &target->head;
281 target->tail_pred->next = (exec_node *) &target->tail;
286 exec_list_iterator iterator()
288 return exec_list_iterator(head);
291 exec_list_iterator iterator() const
293 return exec_list_iterator((exec_node *) head);
298 #endif /* LIST_CONTAINER_H */