c80f776ae16b180cfef30d9a703e9c83718aa503
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
35 * sentinel. The head sentinel and tail sentinel nodes are allocated within the
38 * Do note that this means that the list nodes will contain pointers into the
39 * list structure itself and as a result you may not \c realloc() an \c
40 * exec_list or any structure in which an \c exec_list is embedded.
43 #ifndef LIST_CONTAINER_H
44 #define LIST_CONTAINER_H
51 #include "util/ralloc.h"
54 struct exec_node
*next
;
55 struct exec_node
*prev
;
58 DECLARE_RZALLOC_CXX_OPERATORS(exec_node
)
60 exec_node() : next(NULL
), prev(NULL
)
65 const exec_node
*get_next() const;
66 exec_node
*get_next();
68 const exec_node
*get_prev() const;
69 exec_node
*get_prev();
74 * Link a node with itself
76 * This creates a sort of degenerate list that is occasionally useful.
81 * Insert a node in the list after the current node
83 void insert_after(exec_node
*after
);
86 * Insert another list in the list after the current node
88 void insert_after(struct exec_list
*after
);
91 * Insert a node in the list before the current node
93 void insert_before(exec_node
*before
);
96 * Insert another list in the list before the current node
98 void insert_before(struct exec_list
*before
);
101 * Replace the current node with the given node.
103 void replace_with(exec_node
*replacement
);
106 * Is this the sentinel at the tail of the list?
108 bool is_tail_sentinel() const;
111 * Is this the sentinel at the head of the list?
113 bool is_head_sentinel() const;
118 exec_node_init(struct exec_node
*n
)
124 static inline const struct exec_node
*
125 exec_node_get_next_const(const struct exec_node
*n
)
130 static inline struct exec_node
*
131 exec_node_get_next(struct exec_node
*n
)
136 static inline const struct exec_node
*
137 exec_node_get_prev_const(const struct exec_node
*n
)
142 static inline struct exec_node
*
143 exec_node_get_prev(struct exec_node
*n
)
149 exec_node_remove(struct exec_node
*n
)
151 n
->next
->prev
= n
->prev
;
152 n
->prev
->next
= n
->next
;
158 exec_node_self_link(struct exec_node
*n
)
165 exec_node_insert_after(struct exec_node
*n
, struct exec_node
*after
)
167 after
->next
= n
->next
;
170 n
->next
->prev
= after
;
175 exec_node_insert_node_before(struct exec_node
*n
, struct exec_node
*before
)
178 before
->prev
= n
->prev
;
180 n
->prev
->next
= before
;
185 exec_node_replace_with(struct exec_node
*n
, struct exec_node
*replacement
)
187 replacement
->prev
= n
->prev
;
188 replacement
->next
= n
->next
;
190 n
->prev
->next
= replacement
;
191 n
->next
->prev
= replacement
;
195 exec_node_is_tail_sentinel(const struct exec_node
*n
)
197 return n
->next
== NULL
;
201 exec_node_is_head_sentinel(const struct exec_node
*n
)
203 return n
->prev
== NULL
;
207 inline const exec_node
*exec_node::get_next() const
209 return exec_node_get_next_const(this);
212 inline exec_node
*exec_node::get_next()
214 return exec_node_get_next(this);
217 inline const exec_node
*exec_node::get_prev() const
219 return exec_node_get_prev_const(this);
222 inline exec_node
*exec_node::get_prev()
224 return exec_node_get_prev(this);
227 inline void exec_node::remove()
229 exec_node_remove(this);
232 inline void exec_node::self_link()
234 exec_node_self_link(this);
237 inline void exec_node::insert_after(exec_node
*after
)
239 exec_node_insert_after(this, after
);
242 inline void exec_node::insert_before(exec_node
*before
)
244 exec_node_insert_node_before(this, before
);
247 inline void exec_node::replace_with(exec_node
*replacement
)
249 exec_node_replace_with(this, replacement
);
252 inline bool exec_node::is_tail_sentinel() const
254 return exec_node_is_tail_sentinel(this);
257 inline bool exec_node::is_head_sentinel() const
259 return exec_node_is_head_sentinel(this);
264 /* This macro will not work correctly if `t' uses virtual inheritance. If you
265 * are using virtual inheritance, you deserve a slow and painful death. Enjoy!
267 #define exec_list_offsetof(t, f, p) \
268 (((char *) &((t *) p)->f) - ((char *) p))
270 #define exec_list_offsetof(t, f, p) offsetof(t, f)
274 * Get a pointer to the structure containing an exec_node
276 * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
277 * the containing structure.
279 * \param type Base type of the structure containing the node
280 * \param node Pointer to the \c exec_node
281 * \param field Name of the field in \c type that is the embedded \c exec_node
283 #define exec_node_data(type, node, field) \
284 ((type *) (((uintptr_t) node) - exec_list_offsetof(type, field, node)))
291 struct exec_node head_sentinel
;
292 struct exec_node tail_sentinel
;
295 DECLARE_RALLOC_CXX_OPERATORS(exec_list
)
304 bool is_empty() const;
306 const exec_node
*get_head() const;
307 exec_node
*get_head();
308 const exec_node
*get_head_raw() const;
309 exec_node
*get_head_raw();
311 const exec_node
*get_tail() const;
312 exec_node
*get_tail();
313 const exec_node
*get_tail_raw() const;
314 exec_node
*get_tail_raw();
316 unsigned length() const;
318 void push_head(exec_node
*n
);
319 void push_tail(exec_node
*n
);
320 void push_degenerate_list_at_head(exec_node
*n
);
323 * Remove the first node from a list and return it
326 * The first node in the list or \c NULL if the list is empty.
328 * \sa exec_list::get_head
330 exec_node
*pop_head();
333 * Move all of the nodes from this list to the target list
335 void move_nodes_to(exec_list
*target
);
338 * Append all nodes from the source list to the end of the target list
340 void append_list(exec_list
*source
);
343 * Prepend all nodes from the source list to the beginning of the target
346 void prepend_list(exec_list
*source
);
351 exec_list_make_empty(struct exec_list
*list
)
353 list
->head_sentinel
.next
= &list
->tail_sentinel
;
354 list
->head_sentinel
.prev
= NULL
;
355 list
->tail_sentinel
.next
= NULL
;
356 list
->tail_sentinel
.prev
= &list
->head_sentinel
;
360 exec_list_is_empty(const struct exec_list
*list
)
362 /* There are three ways to test whether a list is empty or not.
364 * - Check to see if the head sentinel's \c next is the tail sentinel.
365 * - Check to see if the tail sentinel's \c prev is the head sentinel.
366 * - Check to see if the head is the sentinel node by test whether its
367 * \c next pointer is \c NULL.
369 * The first two methods tend to generate better code on modern systems
370 * because they save a pointer dereference.
372 return list
->head_sentinel
.next
== &list
->tail_sentinel
;
376 exec_list_is_singular(const struct exec_list
*list
)
378 return !exec_list_is_empty(list
) &&
379 list
->head_sentinel
.next
->next
== &list
->tail_sentinel
;
382 static inline const struct exec_node
*
383 exec_list_get_head_const(const struct exec_list
*list
)
385 return !exec_list_is_empty(list
) ? list
->head_sentinel
.next
: NULL
;
388 static inline struct exec_node
*
389 exec_list_get_head(struct exec_list
*list
)
391 return !exec_list_is_empty(list
) ? list
->head_sentinel
.next
: NULL
;
394 static inline const struct exec_node
*
395 exec_list_get_head_raw_const(const struct exec_list
*list
)
397 return list
->head_sentinel
.next
;
400 static inline struct exec_node
*
401 exec_list_get_head_raw(struct exec_list
*list
)
403 return list
->head_sentinel
.next
;
406 static inline const struct exec_node
*
407 exec_list_get_tail_const(const struct exec_list
*list
)
409 return !exec_list_is_empty(list
) ? list
->tail_sentinel
.prev
: NULL
;
412 static inline struct exec_node
*
413 exec_list_get_tail(struct exec_list
*list
)
415 return !exec_list_is_empty(list
) ? list
->tail_sentinel
.prev
: NULL
;
418 static inline const struct exec_node
*
419 exec_list_get_tail_raw_const(const struct exec_list
*list
)
421 return list
->tail_sentinel
.prev
;
424 static inline struct exec_node
*
425 exec_list_get_tail_raw(struct exec_list
*list
)
427 return list
->tail_sentinel
.prev
;
430 static inline unsigned
431 exec_list_length(const struct exec_list
*list
)
434 struct exec_node
*node
;
436 for (node
= list
->head_sentinel
.next
; node
->next
!= NULL
; node
= node
->next
) {
444 exec_list_push_head(struct exec_list
*list
, struct exec_node
*n
)
446 n
->next
= list
->head_sentinel
.next
;
447 n
->prev
= &list
->head_sentinel
;
450 list
->head_sentinel
.next
= n
;
454 exec_list_push_tail(struct exec_list
*list
, struct exec_node
*n
)
456 n
->next
= &list
->tail_sentinel
;
457 n
->prev
= list
->tail_sentinel
.prev
;
460 list
->tail_sentinel
.prev
= n
;
464 exec_list_push_degenerate_list_at_head(struct exec_list
*list
, struct exec_node
*n
)
466 assert(n
->prev
->next
== n
);
468 n
->prev
->next
= list
->head_sentinel
.next
;
469 list
->head_sentinel
.next
->prev
= n
->prev
;
470 n
->prev
= &list
->head_sentinel
;
471 list
->head_sentinel
.next
= n
;
474 static inline struct exec_node
*
475 exec_list_pop_head(struct exec_list
*list
)
477 struct exec_node
*const n
= exec_list_get_head(list
);
485 exec_list_move_nodes_to(struct exec_list
*list
, struct exec_list
*target
)
487 if (exec_list_is_empty(list
)) {
488 exec_list_make_empty(target
);
490 target
->head_sentinel
.next
= list
->head_sentinel
.next
;
491 target
->head_sentinel
.prev
= NULL
;
492 target
->tail_sentinel
.next
= NULL
;
493 target
->tail_sentinel
.prev
= list
->tail_sentinel
.prev
;
495 target
->head_sentinel
.next
->prev
= &target
->head_sentinel
;
496 target
->tail_sentinel
.prev
->next
= &target
->tail_sentinel
;
498 exec_list_make_empty(list
);
503 exec_list_append(struct exec_list
*list
, struct exec_list
*source
)
505 if (exec_list_is_empty(source
))
508 /* Link the first node of the source with the last node of the target list.
510 list
->tail_sentinel
.prev
->next
= source
->head_sentinel
.next
;
511 source
->head_sentinel
.next
->prev
= list
->tail_sentinel
.prev
;
513 /* Make the tail of the source list be the tail of the target list.
515 list
->tail_sentinel
.prev
= source
->tail_sentinel
.prev
;
516 list
->tail_sentinel
.prev
->next
= &list
->tail_sentinel
;
518 /* Make the source list empty for good measure.
520 exec_list_make_empty(source
);
524 exec_node_insert_list_after(struct exec_node
*n
, struct exec_list
*after
)
526 if (exec_list_is_empty(after
))
529 after
->tail_sentinel
.prev
->next
= n
->next
;
530 after
->head_sentinel
.next
->prev
= n
;
532 n
->next
->prev
= after
->tail_sentinel
.prev
;
533 n
->next
= after
->head_sentinel
.next
;
535 exec_list_make_empty(after
);
539 exec_list_prepend(struct exec_list
*list
, struct exec_list
*source
)
541 exec_list_append(source
, list
);
542 exec_list_move_nodes_to(source
, list
);
546 exec_node_insert_list_before(struct exec_node
*n
, struct exec_list
*before
)
548 if (exec_list_is_empty(before
))
551 before
->tail_sentinel
.prev
->next
= n
;
552 before
->head_sentinel
.next
->prev
= n
->prev
;
554 n
->prev
->next
= before
->head_sentinel
.next
;
555 n
->prev
= before
->tail_sentinel
.prev
;
557 exec_list_make_empty(before
);
561 exec_list_validate(const struct exec_list
*list
)
563 const struct exec_node
*node
;
565 assert(list
->head_sentinel
.next
->prev
== &list
->head_sentinel
);
566 assert(list
->head_sentinel
.prev
== NULL
);
567 assert(list
->tail_sentinel
.next
== NULL
);
568 assert(list
->tail_sentinel
.prev
->next
== &list
->tail_sentinel
);
570 /* We could try to use one of the interators below for this but they all
571 * either require C++ or assume the exec_node is embedded in a structure
572 * which is not the case for this function.
574 for (node
= list
->head_sentinel
.next
; node
->next
!= NULL
; node
= node
->next
) {
575 assert(node
->next
->prev
== node
);
576 assert(node
->prev
->next
== node
);
581 inline void exec_list::make_empty()
583 exec_list_make_empty(this);
586 inline bool exec_list::is_empty() const
588 return exec_list_is_empty(this);
591 inline const exec_node
*exec_list::get_head() const
593 return exec_list_get_head_const(this);
596 inline exec_node
*exec_list::get_head()
598 return exec_list_get_head(this);
601 inline const exec_node
*exec_list::get_head_raw() const
603 return exec_list_get_head_raw_const(this);
606 inline exec_node
*exec_list::get_head_raw()
608 return exec_list_get_head_raw(this);
611 inline const exec_node
*exec_list::get_tail() const
613 return exec_list_get_tail_const(this);
616 inline exec_node
*exec_list::get_tail()
618 return exec_list_get_tail(this);
621 inline const exec_node
*exec_list::get_tail_raw() const
623 return exec_list_get_tail_raw_const(this);
626 inline exec_node
*exec_list::get_tail_raw()
628 return exec_list_get_tail_raw(this);
631 inline unsigned exec_list::length() const
633 return exec_list_length(this);
636 inline void exec_list::push_head(exec_node
*n
)
638 exec_list_push_head(this, n
);
641 inline void exec_list::push_tail(exec_node
*n
)
643 exec_list_push_tail(this, n
);
646 inline void exec_list::push_degenerate_list_at_head(exec_node
*n
)
648 exec_list_push_degenerate_list_at_head(this, n
);
651 inline exec_node
*exec_list::pop_head()
653 return exec_list_pop_head(this);
656 inline void exec_list::move_nodes_to(exec_list
*target
)
658 exec_list_move_nodes_to(this, target
);
661 inline void exec_list::append_list(exec_list
*source
)
663 exec_list_append(this, source
);
666 inline void exec_node::insert_after(exec_list
*after
)
668 exec_node_insert_list_after(this, after
);
671 inline void exec_list::prepend_list(exec_list
*source
)
673 exec_list_prepend(this, source
);
676 inline void exec_node::insert_before(exec_list
*before
)
678 exec_node_insert_list_before(this, before
);
682 #define foreach_in_list(__type, __inst, __list) \
683 for (__type *__inst = (__type *)(__list)->head_sentinel.next; \
684 !(__inst)->is_tail_sentinel(); \
685 (__inst) = (__type *)(__inst)->next)
687 #define foreach_in_list_reverse(__type, __inst, __list) \
688 for (__type *__inst = (__type *)(__list)->tail_sentinel.prev; \
689 !(__inst)->is_head_sentinel(); \
690 (__inst) = (__type *)(__inst)->prev)
693 * This version is safe even if the current node is removed.
695 #define foreach_in_list_safe(__type, __node, __list) \
696 for (__type *__node = (__type *)(__list)->head_sentinel.next, \
697 *__next = (__type *)__node->next; \
699 __node = __next, __next = (__type *)__next->next)
701 #define foreach_in_list_reverse_safe(__type, __node, __list) \
702 for (__type *__node = (__type *)(__list)->tail_sentinel.prev, \
703 *__prev = (__type *)__node->prev; \
705 __node = __prev, __prev = (__type *)__prev->prev)
707 #define foreach_in_list_use_after(__type, __inst, __list) \
709 for ((__inst) = (__type *)(__list)->head_sentinel.next; \
710 !(__inst)->is_tail_sentinel(); \
711 (__inst) = (__type *)(__inst)->next)
713 * Iterate through two lists at once. Stops at the end of the shorter list.
715 * This is safe against either current node being removed or replaced.
717 #define foreach_two_lists(__node1, __list1, __node2, __list2) \
718 for (struct exec_node * __node1 = (__list1)->head_sentinel.next, \
719 * __node2 = (__list2)->head_sentinel.next, \
720 * __next1 = __node1->next, \
721 * __next2 = __node2->next \
722 ; __next1 != NULL && __next2 != NULL \
723 ; __node1 = __next1, \
725 __next1 = __next1->next, \
726 __next2 = __next2->next)
728 #define foreach_list_typed(__type, __node, __field, __list) \
729 for (__type * __node = \
730 exec_node_data(__type, (__list)->head_sentinel.next, __field); \
731 (__node)->__field.next != NULL; \
732 (__node) = exec_node_data(__type, (__node)->__field.next, __field))
734 #define foreach_list_typed_from(__type, __node, __field, __list, __start) \
735 for (__type * __node = exec_node_data(__type, (__start), __field); \
736 (__node)->__field.next != NULL; \
737 (__node) = exec_node_data(__type, (__node)->__field.next, __field))
739 #define foreach_list_typed_reverse(__type, __node, __field, __list) \
740 for (__type * __node = \
741 exec_node_data(__type, (__list)->tail_sentinel.prev, __field); \
742 (__node)->__field.prev != NULL; \
743 (__node) = exec_node_data(__type, (__node)->__field.prev, __field))
745 #define foreach_list_typed_safe(__type, __node, __field, __list) \
746 for (__type * __node = \
747 exec_node_data(__type, (__list)->head_sentinel.next, __field), \
749 exec_node_data(__type, (__node)->__field.next, __field); \
750 (__node)->__field.next != NULL; \
751 __node = __next, __next = \
752 exec_node_data(__type, (__next)->__field.next, __field))
754 #define foreach_list_typed_reverse_safe(__type, __node, __field, __list) \
755 for (__type * __node = \
756 exec_node_data(__type, (__list)->tail_sentinel.prev, __field), \
758 exec_node_data(__type, (__node)->__field.prev, __field); \
759 (__node)->__field.prev != NULL; \
760 __node = __prev, __prev = \
761 exec_node_data(__type, (__prev)->__field.prev, __field))
763 #endif /* LIST_CONTAINER_H */