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 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.
32 *
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.
36 *
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:
42 *
43 * - A \c head pointer that represents the \c next pointer of the
44 * head sentinel node.
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
49 * tail sentinel 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 #ifndef __cplusplus
68 #include <stddef.h>
69 #endif
70 #include <assert.h>
71
72 #include "util/ralloc.h"
73
74 struct exec_node {
75 struct exec_node *next;
76 struct exec_node *prev;
77
78 #ifdef __cplusplus
79 DECLARE_RALLOC_CXX_OPERATORS(exec_node)
80
exec_nodeexec_node81 exec_node() : next(NULL), prev(NULL)
82 {
83 /* empty */
84 }
85
86 const exec_node *get_next() const;
87 exec_node *get_next();
88
89 const exec_node *get_prev() const;
90 exec_node *get_prev();
91
92 void remove();
93
94 /**
95 * Link a node with itself
96 *
97 * This creates a sort of degenerate list that is occasionally useful.
98 */
99 void self_link();
100
101 /**
102 * Insert a node in the list after the current node
103 */
104 void insert_after(exec_node *after);
105 /**
106 * Insert a node in the list before the current node
107 */
108 void insert_before(exec_node *before);
109
110 /**
111 * Insert another list in the list before the current node
112 */
113 void insert_before(struct exec_list *before);
114
115 /**
116 * Replace the current node with the given node.
117 */
118 void replace_with(exec_node *replacement);
119
120 /**
121 * Is this the sentinel at the tail of the list?
122 */
123 bool is_tail_sentinel() const;
124
125 /**
126 * Is this the sentinel at the head of the list?
127 */
128 bool is_head_sentinel() const;
129 #endif
130 };
131
132 static inline void
exec_node_init(struct exec_node * n)133 exec_node_init(struct exec_node *n)
134 {
135 n->next = NULL;
136 n->prev = NULL;
137 }
138
139 static inline const struct exec_node *
exec_node_get_next_const(const struct exec_node * n)140 exec_node_get_next_const(const struct exec_node *n)
141 {
142 return n->next;
143 }
144
145 static inline struct exec_node *
exec_node_get_next(struct exec_node * n)146 exec_node_get_next(struct exec_node *n)
147 {
148 return n->next;
149 }
150
151 static inline const struct exec_node *
exec_node_get_prev_const(const struct exec_node * n)152 exec_node_get_prev_const(const struct exec_node *n)
153 {
154 return n->prev;
155 }
156
157 static inline struct exec_node *
exec_node_get_prev(struct exec_node * n)158 exec_node_get_prev(struct exec_node *n)
159 {
160 return n->prev;
161 }
162
163 static inline void
exec_node_remove(struct exec_node * n)164 exec_node_remove(struct exec_node *n)
165 {
166 if (n->next)
167 n->next->prev = n->prev;
168 if (n->prev)
169 n->prev->next = n->next;
170 n->next = NULL;
171 n->prev = NULL;
172 }
173
174 static inline void
exec_node_self_link(struct exec_node * n)175 exec_node_self_link(struct exec_node *n)
176 {
177 n->next = n;
178 n->prev = n;
179 }
180
181 static inline void
exec_node_insert_after(struct exec_node * n,struct exec_node * after)182 exec_node_insert_after(struct exec_node *n, struct exec_node *after)
183 {
184 after->next = n->next;
185 after->prev = n;
186
187 n->next->prev = after;
188 n->next = after;
189 }
190
191 static inline void
exec_node_insert_node_before(struct exec_node * n,struct exec_node * before)192 exec_node_insert_node_before(struct exec_node *n, struct exec_node *before)
193 {
194 before->next = n;
195 before->prev = n->prev;
196
197 n->prev->next = before;
198 n->prev = before;
199 }
200
201 static inline void
exec_node_replace_with(struct exec_node * n,struct exec_node * replacement)202 exec_node_replace_with(struct exec_node *n, struct exec_node *replacement)
203 {
204 replacement->prev = n->prev;
205 replacement->next = n->next;
206
207 n->prev->next = replacement;
208 n->next->prev = replacement;
209 }
210
211 static inline bool
exec_node_is_tail_sentinel(const struct exec_node * n)212 exec_node_is_tail_sentinel(const struct exec_node *n)
213 {
214 return n->next == NULL;
215 }
216
217 static inline bool
exec_node_is_head_sentinel(const struct exec_node * n)218 exec_node_is_head_sentinel(const struct exec_node *n)
219 {
220 return n->prev == NULL;
221 }
222
223 #ifdef __cplusplus
get_next()224 inline const exec_node *exec_node::get_next() const
225 {
226 return exec_node_get_next_const(this);
227 }
228
get_next()229 inline exec_node *exec_node::get_next()
230 {
231 return exec_node_get_next(this);
232 }
233
get_prev()234 inline const exec_node *exec_node::get_prev() const
235 {
236 return exec_node_get_prev_const(this);
237 }
238
get_prev()239 inline exec_node *exec_node::get_prev()
240 {
241 return exec_node_get_prev(this);
242 }
243
remove()244 inline void exec_node::remove()
245 {
246 exec_node_remove(this);
247 }
248
self_link()249 inline void exec_node::self_link()
250 {
251 exec_node_self_link(this);
252 }
253
insert_after(exec_node * after)254 inline void exec_node::insert_after(exec_node *after)
255 {
256 exec_node_insert_after(this, after);
257 }
258
insert_before(exec_node * before)259 inline void exec_node::insert_before(exec_node *before)
260 {
261 exec_node_insert_node_before(this, before);
262 }
263
replace_with(exec_node * replacement)264 inline void exec_node::replace_with(exec_node *replacement)
265 {
266 exec_node_replace_with(this, replacement);
267 }
268
is_tail_sentinel()269 inline bool exec_node::is_tail_sentinel() const
270 {
271 return exec_node_is_tail_sentinel(this);
272 }
273
is_head_sentinel()274 inline bool exec_node::is_head_sentinel() const
275 {
276 return exec_node_is_head_sentinel(this);
277 }
278 #endif
279
280 #ifdef __cplusplus
281 /* This macro will not work correctly if `t' uses virtual inheritance. If you
282 * are using virtual inheritance, you deserve a slow and painful death. Enjoy!
283 */
284 #define exec_list_offsetof(t, f, p) \
285 (((char *) &((t *) p)->f) - ((char *) p))
286 #else
287 #define exec_list_offsetof(t, f, p) offsetof(t, f)
288 #endif
289
290 /**
291 * Get a pointer to the structure containing an exec_node
292 *
293 * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
294 * the containing structure.
295 *
296 * \param type Base type of the structure containing the node
297 * \param node Pointer to the \c exec_node
298 * \param field Name of the field in \c type that is the embedded \c exec_node
299 */
300 #define exec_node_data(type, node, field) \
301 ((type *) (((char *) node) - exec_list_offsetof(type, field, node)))
302
303 #ifdef __cplusplus
304 struct exec_node;
305 #endif
306
307 struct exec_list {
308 struct exec_node *head;
309 struct exec_node *tail;
310 struct exec_node *tail_pred;
311
312 #ifdef __cplusplus
313 DECLARE_RALLOC_CXX_OPERATORS(exec_list)
314
exec_listexec_list315 exec_list()
316 {
317 make_empty();
318 }
319
320 void make_empty();
321
322 bool is_empty() const;
323
324 const exec_node *get_head() const;
325 exec_node *get_head();
326
327 const exec_node *get_tail() const;
328 exec_node *get_tail();
329
330 unsigned length() const;
331
332 void push_head(exec_node *n);
333 void push_tail(exec_node *n);
334 void push_degenerate_list_at_head(exec_node *n);
335
336 /**
337 * Remove the first node from a list and return it
338 *
339 * \return
340 * The first node in the list or \c NULL if the list is empty.
341 *
342 * \sa exec_list::get_head
343 */
344 exec_node *pop_head();
345
346 /**
347 * Move all of the nodes from this list to the target list
348 */
349 void move_nodes_to(exec_list *target);
350
351 /**
352 * Append all nodes from the source list to the end of the target list
353 */
354 void append_list(exec_list *source);
355
356 /**
357 * Prepend all nodes from the source list to the beginning of the target
358 * list
359 */
360 void prepend_list(exec_list *source);
361 #endif
362 };
363
364 static inline void
exec_list_make_empty(struct exec_list * list)365 exec_list_make_empty(struct exec_list *list)
366 {
367 list->head = (struct exec_node *) & list->tail;
368 list->tail = NULL;
369 list->tail_pred = (struct exec_node *) & list->head;
370 }
371
372 static inline bool
exec_list_is_empty(const struct exec_list * list)373 exec_list_is_empty(const struct exec_list *list)
374 {
375 /* There are three ways to test whether a list is empty or not.
376 *
377 * - Check to see if the \c head points to the \c tail.
378 * - Check to see if the \c tail_pred points to the \c head.
379 * - Check to see if the \c head is the sentinel node by test whether its
380 * \c next pointer is \c NULL.
381 *
382 * The first two methods tend to generate better code on modern systems
383 * because they save a pointer dereference.
384 */
385 return list->head == (struct exec_node *) &list->tail;
386 }
387
388 static inline const struct exec_node *
exec_list_get_head_const(const struct exec_list * list)389 exec_list_get_head_const(const struct exec_list *list)
390 {
391 return !exec_list_is_empty(list) ? list->head : NULL;
392 }
393
394 static inline struct exec_node *
exec_list_get_head(struct exec_list * list)395 exec_list_get_head(struct exec_list *list)
396 {
397 return !exec_list_is_empty(list) ? list->head : NULL;
398 }
399
400 static inline const struct exec_node *
exec_list_get_tail_const(const struct exec_list * list)401 exec_list_get_tail_const(const struct exec_list *list)
402 {
403 return !exec_list_is_empty(list) ? list->tail_pred : NULL;
404 }
405
406 static inline struct exec_node *
exec_list_get_tail(struct exec_list * list)407 exec_list_get_tail(struct exec_list *list)
408 {
409 return !exec_list_is_empty(list) ? list->tail_pred : NULL;
410 }
411
412 static inline unsigned
exec_list_length(const struct exec_list * list)413 exec_list_length(const struct exec_list *list)
414 {
415 unsigned size = 0;
416 struct exec_node *node;
417
418 for (node = list->head; node->next != NULL; node = node->next) {
419 size++;
420 }
421
422 return size;
423 }
424
425 static inline void
exec_list_push_head(struct exec_list * list,struct exec_node * n)426 exec_list_push_head(struct exec_list *list, struct exec_node *n)
427 {
428 n->next = list->head;
429 n->prev = (struct exec_node *) &list->head;
430
431 n->next->prev = n;
432 list->head = n;
433 }
434
435 static inline void
exec_list_push_tail(struct exec_list * list,struct exec_node * n)436 exec_list_push_tail(struct exec_list *list, struct exec_node *n)
437 {
438 n->next = (struct exec_node *) &list->tail;
439 n->prev = list->tail_pred;
440
441 n->prev->next = n;
442 list->tail_pred = n;
443 }
444
445 static inline void
exec_list_push_degenerate_list_at_head(struct exec_list * list,struct exec_node * n)446 exec_list_push_degenerate_list_at_head(struct exec_list *list, struct exec_node *n)
447 {
448 assert(n->prev->next == n);
449
450 n->prev->next = list->head;
451 list->head->prev = n->prev;
452 n->prev = (struct exec_node *) &list->head;
453 list->head = n;
454 }
455
456 static inline struct exec_node *
exec_list_pop_head(struct exec_list * list)457 exec_list_pop_head(struct exec_list *list)
458 {
459 struct exec_node *const n = exec_list_get_head(list);
460 if (n != NULL)
461 exec_node_remove(n);
462
463 return n;
464 }
465
466 static inline void
exec_list_move_nodes_to(struct exec_list * list,struct exec_list * target)467 exec_list_move_nodes_to(struct exec_list *list, struct exec_list *target)
468 {
469 if (exec_list_is_empty(list)) {
470 exec_list_make_empty(target);
471 } else {
472 target->head = list->head;
473 target->tail = NULL;
474 target->tail_pred = list->tail_pred;
475
476 target->head->prev = (struct exec_node *) &target->head;
477 target->tail_pred->next = (struct exec_node *) &target->tail;
478
479 exec_list_make_empty(list);
480 }
481 }
482
483 static inline void
exec_list_append(struct exec_list * list,struct exec_list * source)484 exec_list_append(struct exec_list *list, struct exec_list *source)
485 {
486 if (exec_list_is_empty(source))
487 return;
488
489 /* Link the first node of the source with the last node of the target list.
490 */
491 list->tail_pred->next = source->head;
492 source->head->prev = list->tail_pred;
493
494 /* Make the tail of the source list be the tail of the target list.
495 */
496 list->tail_pred = source->tail_pred;
497 list->tail_pred->next = (struct exec_node *) &list->tail;
498
499 /* Make the source list empty for good measure.
500 */
501 exec_list_make_empty(source);
502 }
503
504 static inline void
exec_list_prepend(struct exec_list * list,struct exec_list * source)505 exec_list_prepend(struct exec_list *list, struct exec_list *source)
506 {
507 exec_list_append(source, list);
508 exec_list_move_nodes_to(source, list);
509 }
510
511 static inline void
exec_node_insert_list_before(struct exec_node * n,struct exec_list * before)512 exec_node_insert_list_before(struct exec_node *n, struct exec_list *before)
513 {
514 if (exec_list_is_empty(before))
515 return;
516
517 before->tail_pred->next = n;
518 before->head->prev = n->prev;
519
520 n->prev->next = before->head;
521 n->prev = before->tail_pred;
522
523 exec_list_make_empty(before);
524 }
525
526 #ifdef __cplusplus
make_empty()527 inline void exec_list::make_empty()
528 {
529 exec_list_make_empty(this);
530 }
531
is_empty()532 inline bool exec_list::is_empty() const
533 {
534 return exec_list_is_empty(this);
535 }
536
get_head()537 inline const exec_node *exec_list::get_head() const
538 {
539 return exec_list_get_head_const(this);
540 }
541
get_head()542 inline exec_node *exec_list::get_head()
543 {
544 return exec_list_get_head(this);
545 }
546
get_tail()547 inline const exec_node *exec_list::get_tail() const
548 {
549 return exec_list_get_tail_const(this);
550 }
551
get_tail()552 inline exec_node *exec_list::get_tail()
553 {
554 return exec_list_get_tail(this);
555 }
556
length()557 inline unsigned exec_list::length() const
558 {
559 return exec_list_length(this);
560 }
561
push_head(exec_node * n)562 inline void exec_list::push_head(exec_node *n)
563 {
564 exec_list_push_head(this, n);
565 }
566
push_tail(exec_node * n)567 inline void exec_list::push_tail(exec_node *n)
568 {
569 exec_list_push_tail(this, n);
570 }
571
push_degenerate_list_at_head(exec_node * n)572 inline void exec_list::push_degenerate_list_at_head(exec_node *n)
573 {
574 exec_list_push_degenerate_list_at_head(this, n);
575 }
576
pop_head()577 inline exec_node *exec_list::pop_head()
578 {
579 return exec_list_pop_head(this);
580 }
581
move_nodes_to(exec_list * target)582 inline void exec_list::move_nodes_to(exec_list *target)
583 {
584 exec_list_move_nodes_to(this, target);
585 }
586
append_list(exec_list * source)587 inline void exec_list::append_list(exec_list *source)
588 {
589 exec_list_append(this, source);
590 }
591
prepend_list(exec_list * source)592 inline void exec_list::prepend_list(exec_list *source)
593 {
594 exec_list_prepend(this, source);
595 }
596
insert_before(exec_list * before)597 inline void exec_node::insert_before(exec_list *before)
598 {
599 exec_node_insert_list_before(this, before);
600 }
601 #endif
602
603 #define foreach_in_list(__type, __inst, __list) \
604 for (__type *(__inst) = (__type *)(__list)->head; \
605 !(__inst)->is_tail_sentinel(); \
606 (__inst) = (__type *)(__inst)->next)
607
608 #define foreach_in_list_reverse(__type, __inst, __list) \
609 for (__type *(__inst) = (__type *)(__list)->tail_pred; \
610 !(__inst)->is_head_sentinel(); \
611 (__inst) = (__type *)(__inst)->prev)
612
613 /**
614 * This version is safe even if the current node is removed.
615 */
616 #define foreach_in_list_safe(__type, __node, __list) \
617 for (__type *__node = (__type *)(__list)->head, \
618 *__next = (__type *)__node->next; \
619 __next != NULL; \
620 __node = __next, __next = (__type *)__next->next)
621
622 #define foreach_in_list_use_after(__type, __inst, __list) \
623 __type *(__inst); \
624 for ((__inst) = (__type *)(__list)->head; \
625 !(__inst)->is_tail_sentinel(); \
626 (__inst) = (__type *)(__inst)->next)
627 /**
628 * Iterate through two lists at once. Stops at the end of the shorter list.
629 *
630 * This is safe against either current node being removed or replaced.
631 */
632 #define foreach_two_lists(__node1, __list1, __node2, __list2) \
633 for (struct exec_node * __node1 = (__list1)->head, \
634 * __node2 = (__list2)->head, \
635 * __next1 = __node1->next, \
636 * __next2 = __node2->next \
637 ; __next1 != NULL && __next2 != NULL \
638 ; __node1 = __next1, \
639 __node2 = __next2, \
640 __next1 = __next1->next, \
641 __next2 = __next2->next)
642
643 #define foreach_list_typed(__type, __node, __field, __list) \
644 for (__type * __node = \
645 exec_node_data(__type, (__list)->head, __field); \
646 (__node)->__field.next != NULL; \
647 (__node) = exec_node_data(__type, (__node)->__field.next, __field))
648
649 #define foreach_list_typed_safe(__type, __node, __field, __list) \
650 for (__type * __node = \
651 exec_node_data(__type, (__list)->head, __field), \
652 * __next = \
653 exec_node_data(__type, (__node)->__field.next, __field); \
654 __next != NULL; \
655 __node = __next, __next = \
656 exec_node_data(__type, (__next)->__field.next, __field))
657
658 #endif /* LIST_CONTAINER_H */
659