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 * Do note that this means that the list nodes will contain pointers into the
55 * list structure itself and as a result you may not \c realloc() an \c
56 * exec_list or any structure in which an \c exec_list is embedded.
58 * To anyone familiar with "exec lists" on the Amiga, this structure should
59 * be immediately recognizable. See the following link for the original Amiga
60 * operating system documentation on the subject.
62 * http://www.natami.net/dev/Libraries_Manual_guide/node02D7.html
64 * \author Ian Romanick <ian.d.romanick@intel.com>
68 #ifndef LIST_CONTAINER_H
69 #define LIST_CONTAINER_H
76 #include "util/ralloc.h"
79 struct exec_node
*next
;
80 struct exec_node
*prev
;
83 DECLARE_RALLOC_CXX_OPERATORS(exec_node
)
85 exec_node() : next(NULL
), prev(NULL
)
90 const exec_node
*get_next() const;
91 exec_node
*get_next();
93 const exec_node
*get_prev() const;
94 exec_node
*get_prev();
99 * Link a node with itself
101 * This creates a sort of degenerate list that is occasionally useful.
106 * Insert a node in the list after the current node
108 void insert_after(exec_node
*after
);
110 * Insert a node in the list before the current node
112 void insert_before(exec_node
*before
);
115 * Insert another list in the list before the current node
117 void insert_before(struct exec_list
*before
);
120 * Replace the current node with the given node.
122 void replace_with(exec_node
*replacement
);
125 * Is this the sentinel at the tail of the list?
127 bool is_tail_sentinel() const;
130 * Is this the sentinel at the head of the list?
132 bool is_head_sentinel() const;
137 exec_node_init(struct exec_node
*n
)
143 static inline const struct exec_node
*
144 exec_node_get_next_const(const struct exec_node
*n
)
149 static inline struct exec_node
*
150 exec_node_get_next(struct exec_node
*n
)
155 static inline const struct exec_node
*
156 exec_node_get_prev_const(const struct exec_node
*n
)
161 static inline struct exec_node
*
162 exec_node_get_prev(struct exec_node
*n
)
168 exec_node_remove(struct exec_node
*n
)
170 n
->next
->prev
= n
->prev
;
171 n
->prev
->next
= n
->next
;
177 exec_node_self_link(struct exec_node
*n
)
184 exec_node_insert_after(struct exec_node
*n
, struct exec_node
*after
)
186 after
->next
= n
->next
;
189 n
->next
->prev
= after
;
194 exec_node_insert_node_before(struct exec_node
*n
, struct exec_node
*before
)
197 before
->prev
= n
->prev
;
199 n
->prev
->next
= before
;
204 exec_node_replace_with(struct exec_node
*n
, struct exec_node
*replacement
)
206 replacement
->prev
= n
->prev
;
207 replacement
->next
= n
->next
;
209 n
->prev
->next
= replacement
;
210 n
->next
->prev
= replacement
;
214 exec_node_is_tail_sentinel(const struct exec_node
*n
)
216 return n
->next
== NULL
;
220 exec_node_is_head_sentinel(const struct exec_node
*n
)
222 return n
->prev
== NULL
;
226 inline const exec_node
*exec_node::get_next() const
228 return exec_node_get_next_const(this);
231 inline exec_node
*exec_node::get_next()
233 return exec_node_get_next(this);
236 inline const exec_node
*exec_node::get_prev() const
238 return exec_node_get_prev_const(this);
241 inline exec_node
*exec_node::get_prev()
243 return exec_node_get_prev(this);
246 inline void exec_node::remove()
248 exec_node_remove(this);
251 inline void exec_node::self_link()
253 exec_node_self_link(this);
256 inline void exec_node::insert_after(exec_node
*after
)
258 exec_node_insert_after(this, after
);
261 inline void exec_node::insert_before(exec_node
*before
)
263 exec_node_insert_node_before(this, before
);
266 inline void exec_node::replace_with(exec_node
*replacement
)
268 exec_node_replace_with(this, replacement
);
271 inline bool exec_node::is_tail_sentinel() const
273 return exec_node_is_tail_sentinel(this);
276 inline bool exec_node::is_head_sentinel() const
278 return exec_node_is_head_sentinel(this);
283 /* This macro will not work correctly if `t' uses virtual inheritance. If you
284 * are using virtual inheritance, you deserve a slow and painful death. Enjoy!
286 #define exec_list_offsetof(t, f, p) \
287 (((char *) &((t *) p)->f) - ((char *) p))
289 #define exec_list_offsetof(t, f, p) offsetof(t, f)
293 * Get a pointer to the structure containing an exec_node
295 * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
296 * the containing structure.
298 * \param type Base type of the structure containing the node
299 * \param node Pointer to the \c exec_node
300 * \param field Name of the field in \c type that is the embedded \c exec_node
302 #define exec_node_data(type, node, field) \
303 ((type *) (((char *) node) - exec_list_offsetof(type, field, node)))
310 struct exec_node
*head
;
311 struct exec_node
*tail
;
312 struct exec_node
*tail_pred
;
315 DECLARE_RALLOC_CXX_OPERATORS(exec_list
)
324 bool is_empty() const;
326 const exec_node
*get_head() const;
327 exec_node
*get_head();
329 const exec_node
*get_tail() const;
330 exec_node
*get_tail();
332 unsigned length() const;
334 void push_head(exec_node
*n
);
335 void push_tail(exec_node
*n
);
336 void push_degenerate_list_at_head(exec_node
*n
);
339 * Remove the first node from a list and return it
342 * The first node in the list or \c NULL if the list is empty.
344 * \sa exec_list::get_head
346 exec_node
*pop_head();
349 * Move all of the nodes from this list to the target list
351 void move_nodes_to(exec_list
*target
);
354 * Append all nodes from the source list to the end of the target list
356 void append_list(exec_list
*source
);
359 * Prepend all nodes from the source list to the beginning of the target
362 void prepend_list(exec_list
*source
);
367 exec_list_make_empty(struct exec_list
*list
)
369 list
->head
= (struct exec_node
*) & list
->tail
;
371 list
->tail_pred
= (struct exec_node
*) & list
->head
;
375 exec_list_is_empty(const struct exec_list
*list
)
377 /* There are three ways to test whether a list is empty or not.
379 * - Check to see if the \c head points to the \c tail.
380 * - Check to see if the \c tail_pred points to the \c head.
381 * - Check to see if the \c head is the sentinel node by test whether its
382 * \c next pointer is \c NULL.
384 * The first two methods tend to generate better code on modern systems
385 * because they save a pointer dereference.
387 return list
->head
== (struct exec_node
*) &list
->tail
;
390 static inline const struct exec_node
*
391 exec_list_get_head_const(const struct exec_list
*list
)
393 return !exec_list_is_empty(list
) ? list
->head
: NULL
;
396 static inline struct exec_node
*
397 exec_list_get_head(struct exec_list
*list
)
399 return !exec_list_is_empty(list
) ? list
->head
: NULL
;
402 static inline const struct exec_node
*
403 exec_list_get_tail_const(const struct exec_list
*list
)
405 return !exec_list_is_empty(list
) ? list
->tail_pred
: NULL
;
408 static inline struct exec_node
*
409 exec_list_get_tail(struct exec_list
*list
)
411 return !exec_list_is_empty(list
) ? list
->tail_pred
: NULL
;
414 static inline unsigned
415 exec_list_length(const struct exec_list
*list
)
418 struct exec_node
*node
;
420 for (node
= list
->head
; node
->next
!= NULL
; node
= node
->next
) {
428 exec_list_push_head(struct exec_list
*list
, struct exec_node
*n
)
430 n
->next
= list
->head
;
431 n
->prev
= (struct exec_node
*) &list
->head
;
438 exec_list_push_tail(struct exec_list
*list
, struct exec_node
*n
)
440 n
->next
= (struct exec_node
*) &list
->tail
;
441 n
->prev
= list
->tail_pred
;
448 exec_list_push_degenerate_list_at_head(struct exec_list
*list
, struct exec_node
*n
)
450 assert(n
->prev
->next
== n
);
452 n
->prev
->next
= list
->head
;
453 list
->head
->prev
= n
->prev
;
454 n
->prev
= (struct exec_node
*) &list
->head
;
458 static inline struct exec_node
*
459 exec_list_pop_head(struct exec_list
*list
)
461 struct exec_node
*const n
= exec_list_get_head(list
);
469 exec_list_move_nodes_to(struct exec_list
*list
, struct exec_list
*target
)
471 if (exec_list_is_empty(list
)) {
472 exec_list_make_empty(target
);
474 target
->head
= list
->head
;
476 target
->tail_pred
= list
->tail_pred
;
478 target
->head
->prev
= (struct exec_node
*) &target
->head
;
479 target
->tail_pred
->next
= (struct exec_node
*) &target
->tail
;
481 exec_list_make_empty(list
);
486 exec_list_append(struct exec_list
*list
, struct exec_list
*source
)
488 if (exec_list_is_empty(source
))
491 /* Link the first node of the source with the last node of the target list.
493 list
->tail_pred
->next
= source
->head
;
494 source
->head
->prev
= list
->tail_pred
;
496 /* Make the tail of the source list be the tail of the target list.
498 list
->tail_pred
= source
->tail_pred
;
499 list
->tail_pred
->next
= (struct exec_node
*) &list
->tail
;
501 /* Make the source list empty for good measure.
503 exec_list_make_empty(source
);
507 exec_list_prepend(struct exec_list
*list
, struct exec_list
*source
)
509 exec_list_append(source
, list
);
510 exec_list_move_nodes_to(source
, list
);
514 exec_node_insert_list_before(struct exec_node
*n
, struct exec_list
*before
)
516 if (exec_list_is_empty(before
))
519 before
->tail_pred
->next
= n
;
520 before
->head
->prev
= n
->prev
;
522 n
->prev
->next
= before
->head
;
523 n
->prev
= before
->tail_pred
;
525 exec_list_make_empty(before
);
529 exec_list_validate(const struct exec_list
*list
)
531 const struct exec_node
*node
;
533 assert(list
->head
->prev
== (const struct exec_node
*) &list
->head
);
534 assert(list
->tail
== NULL
);
535 assert(list
->tail_pred
->next
== (const struct exec_node
*) &list
->tail
);
537 /* We could try to use one of the interators below for this but they all
538 * either require C++ or assume the exec_node is embedded in a structure
539 * which is not the case for this function.
541 for (node
= list
->head
; node
->next
!= NULL
; node
= node
->next
) {
542 assert(node
->next
->prev
== node
);
543 assert(node
->prev
->next
== node
);
548 inline void exec_list::make_empty()
550 exec_list_make_empty(this);
553 inline bool exec_list::is_empty() const
555 return exec_list_is_empty(this);
558 inline const exec_node
*exec_list::get_head() const
560 return exec_list_get_head_const(this);
563 inline exec_node
*exec_list::get_head()
565 return exec_list_get_head(this);
568 inline const exec_node
*exec_list::get_tail() const
570 return exec_list_get_tail_const(this);
573 inline exec_node
*exec_list::get_tail()
575 return exec_list_get_tail(this);
578 inline unsigned exec_list::length() const
580 return exec_list_length(this);
583 inline void exec_list::push_head(exec_node
*n
)
585 exec_list_push_head(this, n
);
588 inline void exec_list::push_tail(exec_node
*n
)
590 exec_list_push_tail(this, n
);
593 inline void exec_list::push_degenerate_list_at_head(exec_node
*n
)
595 exec_list_push_degenerate_list_at_head(this, n
);
598 inline exec_node
*exec_list::pop_head()
600 return exec_list_pop_head(this);
603 inline void exec_list::move_nodes_to(exec_list
*target
)
605 exec_list_move_nodes_to(this, target
);
608 inline void exec_list::append_list(exec_list
*source
)
610 exec_list_append(this, source
);
613 inline void exec_list::prepend_list(exec_list
*source
)
615 exec_list_prepend(this, source
);
618 inline void exec_node::insert_before(exec_list
*before
)
620 exec_node_insert_list_before(this, before
);
624 #define foreach_in_list(__type, __inst, __list) \
625 for (__type *(__inst) = (__type *)(__list)->head; \
626 !(__inst)->is_tail_sentinel(); \
627 (__inst) = (__type *)(__inst)->next)
629 #define foreach_in_list_reverse(__type, __inst, __list) \
630 for (__type *(__inst) = (__type *)(__list)->tail_pred; \
631 !(__inst)->is_head_sentinel(); \
632 (__inst) = (__type *)(__inst)->prev)
635 * This version is safe even if the current node is removed.
637 #define foreach_in_list_safe(__type, __node, __list) \
638 for (__type *__node = (__type *)(__list)->head, \
639 *__next = (__type *)__node->next; \
641 __node = __next, __next = (__type *)__next->next)
643 #define foreach_in_list_reverse_safe(__type, __node, __list) \
644 for (__type *__node = (__type *)(__list)->tail_pred, \
645 *__prev = (__type *)__node->prev; \
647 __node = __prev, __prev = (__type *)__prev->prev)
649 #define foreach_in_list_use_after(__type, __inst, __list) \
651 for ((__inst) = (__type *)(__list)->head; \
652 !(__inst)->is_tail_sentinel(); \
653 (__inst) = (__type *)(__inst)->next)
655 * Iterate through two lists at once. Stops at the end of the shorter list.
657 * This is safe against either current node being removed or replaced.
659 #define foreach_two_lists(__node1, __list1, __node2, __list2) \
660 for (struct exec_node * __node1 = (__list1)->head, \
661 * __node2 = (__list2)->head, \
662 * __next1 = __node1->next, \
663 * __next2 = __node2->next \
664 ; __next1 != NULL && __next2 != NULL \
665 ; __node1 = __next1, \
667 __next1 = __next1->next, \
668 __next2 = __next2->next)
670 #define foreach_list_typed(__type, __node, __field, __list) \
671 for (__type * __node = \
672 exec_node_data(__type, (__list)->head, __field); \
673 (__node)->__field.next != NULL; \
674 (__node) = exec_node_data(__type, (__node)->__field.next, __field))
676 #define foreach_list_typed_reverse(__type, __node, __field, __list) \
677 for (__type * __node = \
678 exec_node_data(__type, (__list)->tail_pred, __field); \
679 (__node)->__field.prev != NULL; \
680 (__node) = exec_node_data(__type, (__node)->__field.prev, __field))
682 #define foreach_list_typed_safe(__type, __node, __field, __list) \
683 for (__type * __node = \
684 exec_node_data(__type, (__list)->head, __field), \
686 exec_node_data(__type, (__node)->__field.next, __field); \
687 (__node)->__field.next != NULL; \
688 __node = __next, __next = \
689 exec_node_data(__type, (__next)->__field.next, __field))
691 #define foreach_list_typed_reverse_safe(__type, __node, __field, __list) \
692 for (__type * __node = \
693 exec_node_data(__type, (__list)->tail_pred, __field), \
695 exec_node_data(__type, (__node)->__field.prev, __field); \
696 (__node)->__field.prev != NULL; \
697 __node = __prev, __prev = \
698 exec_node_data(__type, (__prev)->__field.prev, __field))
700 #endif /* LIST_CONTAINER_H */