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 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.
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
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:
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 * 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
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
75 struct exec_node
*next
;
76 struct exec_node
*prev
;
79 DECLARE_RALLOC_CXX_OPERATORS(exec_node
)
81 exec_node() : next(NULL
), prev(NULL
)
86 const exec_node
*get_next() const
96 const exec_node
*get_prev() const
101 exec_node
*get_prev()
115 * Link a node with itself
117 * This creates a sort of degenerate list that is occasionally useful.
126 * Insert a node in the list after the current node
128 void insert_after(exec_node
*after
)
130 after
->next
= this->next
;
133 this->next
->prev
= after
;
137 * Insert a node in the list before the current node
139 void insert_before(exec_node
*before
)
142 before
->prev
= this->prev
;
144 this->prev
->next
= before
;
149 * Insert another list in the list before the current node
151 void insert_before(struct exec_list
*before
);
154 * Replace the current node with the given node.
156 void replace_with(exec_node
*replacement
)
158 replacement
->prev
= this->prev
;
159 replacement
->next
= this->next
;
161 this->prev
->next
= replacement
;
162 this->next
->prev
= replacement
;
166 * Is this the sentinel at the tail of the list?
168 bool is_tail_sentinel() const
170 return this->next
== NULL
;
174 * Is this the sentinel at the head of the list?
176 bool is_head_sentinel() const
178 return this->prev
== NULL
;
185 /* This macro will not work correctly if `t' uses virtual inheritance. If you
186 * are using virtual inheritance, you deserve a slow and painful death. Enjoy!
188 #define exec_list_offsetof(t, f, p) \
189 (((char *) &((t *) p)->f) - ((char *) p))
191 #define exec_list_offsetof(t, f, p) offsetof(t, f)
195 * Get a pointer to the structure containing an exec_node
197 * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
198 * the containing structure.
200 * \param type Base type of the structure containing the node
201 * \param node Pointer to the \c exec_node
202 * \param field Name of the field in \c type that is the embedded \c exec_node
204 #define exec_node_data(type, node, field) \
205 ((type *) (((char *) node) - exec_list_offsetof(type, field, node)))
221 bool has_next() const
227 class exec_list_iterator
: public iterator
{
229 exec_list_iterator(exec_node
*n
) : node(n
), _next(n
->next
)
250 bool has_next() const
252 return _next
!= NULL
;
260 #define foreach_iter(iter_type, iter, container) \
261 for (iter_type iter = (container) . iterator(); iter.has_next(); iter.next())
266 struct exec_node
*head
;
267 struct exec_node
*tail
;
268 struct exec_node
*tail_pred
;
271 DECLARE_RALLOC_CXX_OPERATORS(exec_list
)
280 head
= (exec_node
*) & tail
;
282 tail_pred
= (exec_node
*) & head
;
285 bool is_empty() const
287 /* There are three ways to test whether a list is empty or not.
289 * - Check to see if the \c head points to the \c tail.
290 * - Check to see if the \c tail_pred points to the \c head.
291 * - Check to see if the \c head is the sentinel node by test whether its
292 * \c next pointer is \c NULL.
294 * The first two methods tend to generate better code on modern systems
295 * because they save a pointer dereference.
297 return head
== (exec_node
*) &tail
;
300 const exec_node
*get_head() const
302 return !is_empty() ? head
: NULL
;
305 exec_node
*get_head()
307 return !is_empty() ? head
: NULL
;
310 const exec_node
*get_tail() const
312 return !is_empty() ? tail_pred
: NULL
;
315 exec_node
*get_tail()
317 return !is_empty() ? tail_pred
: NULL
;
320 void push_head(exec_node
*n
)
323 n
->prev
= (exec_node
*) &head
;
329 void push_tail(exec_node
*n
)
331 n
->next
= (exec_node
*) &tail
;
338 void push_degenerate_list_at_head(exec_node
*n
)
340 assert(n
->prev
->next
== n
);
342 n
->prev
->next
= head
;
343 head
->prev
= n
->prev
;
344 n
->prev
= (exec_node
*) &head
;
349 * Remove the first node from a list and return it
352 * The first node in the list or \c NULL if the list is empty.
354 * \sa exec_list::get_head
356 exec_node
*pop_head()
358 exec_node
*const n
= this->get_head();
366 * Move all of the nodes from this list to the target list
368 void move_nodes_to(exec_list
*target
)
371 target
->make_empty();
375 target
->tail_pred
= tail_pred
;
377 target
->head
->prev
= (exec_node
*) &target
->head
;
378 target
->tail_pred
->next
= (exec_node
*) &target
->tail
;
385 * Append all nodes from the source list to the target list
388 append_list(exec_list
*source
)
390 if (source
->is_empty())
393 /* Link the first node of the source with the last node of the target list.
395 this->tail_pred
->next
= source
->head
;
396 source
->head
->prev
= this->tail_pred
;
398 /* Make the tail of the source list be the tail of the target list.
400 this->tail_pred
= source
->tail_pred
;
401 this->tail_pred
->next
= (exec_node
*) &this->tail
;
403 /* Make the source list empty for good measure.
405 source
->make_empty();
408 exec_list_iterator
iterator()
410 return exec_list_iterator(head
);
413 exec_list_iterator
iterator() const
415 return exec_list_iterator((exec_node
*) head
);
422 inline void exec_node::insert_before(exec_list
*before
)
424 if (before
->is_empty())
427 before
->tail_pred
->next
= this;
428 before
->head
->prev
= this->prev
;
430 this->prev
->next
= before
->head
;
431 this->prev
= before
->tail_pred
;
433 before
->make_empty();
438 * This version is safe even if the current node is removed.
440 #define foreach_list_safe(__node, __list) \
441 for (exec_node * __node = (__list)->head, * __next = __node->next \
443 ; __node = __next, __next = __next->next)
445 #define foreach_list(__node, __list) \
446 for (exec_node * __node = (__list)->head \
447 ; (__node)->next != NULL \
448 ; (__node) = (__node)->next)
450 #define foreach_list_const(__node, __list) \
451 for (const exec_node * __node = (__list)->head \
452 ; (__node)->next != NULL \
453 ; (__node) = (__node)->next)
455 #define foreach_list_typed(__type, __node, __field, __list) \
456 for (__type * __node = \
457 exec_node_data(__type, (__list)->head, __field); \
458 (__node)->__field.next != NULL; \
459 (__node) = exec_node_data(__type, (__node)->__field.next, __field))
461 #define foreach_list_typed_const(__type, __node, __field, __list) \
462 for (const __type * __node = \
463 exec_node_data(__type, (__list)->head, __field); \
464 (__node)->__field.next != NULL; \
465 (__node) = exec_node_data(__type, (__node)->__field.next, __field))
467 #endif /* LIST_CONTAINER_H */