1 /*
2 * Circular doubly linked list implementation.
3 *
4 * Copyright (c) 2007 Marko Kreen, Skype Technologies OÜ
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 /**
20 * @file
21 * Circular doubly linked list.
22 */
23
24 #ifndef _USUAL_LIST_H_
25 #define _USUAL_LIST_H_
26
27 #include <usual/base.h>
28
29 /**
30 * Structure for both list nodes and heads.
31 *
32 * It is meant to be embedded in parent structure,
33 * which can be acquired with container_of().
34 */
35 struct List {
36 /** Pointer to next node or head. */
37 struct List *next;
38 /** Pointer to previous node or head. */
39 struct List *prev;
40 };
41
42 /** Define and initialize emtpy list head */
43 #define LIST(var) struct List var = { &var, &var }
44
45 /** Initialize empty list head. */
list_init(struct List * list)46 static inline void list_init(struct List *list)
47 {
48 list->next = list->prev = list;
49 }
50
51 /** Is list empty? */
list_empty(const struct List * list)52 static inline int list_empty(const struct List *list)
53 {
54 return list->next == list;
55 }
56
57 /** Add item to the start of the list */
list_prepend(struct List * list,struct List * item)58 static inline struct List *list_prepend(struct List *list, struct List *item)
59 {
60 item->next = list->next;
61 item->prev = list;
62 list->next->prev = item;
63 list->next = item;
64 return item;
65 }
66
67 /** Add item to the end of the list */
list_append(struct List * list,struct List * item)68 static inline struct List *list_append(struct List *list, struct List *item)
69 {
70 item->next = list;
71 item->prev = list->prev;
72 list->prev->next = item;
73 list->prev = item;
74 return item;
75 }
76
77 /** Remove item from list */
list_del(struct List * item)78 static inline struct List *list_del(struct List *item)
79 {
80 item->prev->next = item->next;
81 item->next->prev = item->prev;
82 item->next = item->prev = item;
83 return item;
84 }
85
86 /** Remove first from list and return */
list_pop(struct List * list)87 static inline struct List *list_pop(struct List *list)
88 {
89 if (list_empty(list))
90 return NULL;
91 return list_del(list->next);
92 }
93
94 /** Get first elem from list */
list_first(const struct List * list)95 static inline struct List *list_first(const struct List *list)
96 {
97 if (list_empty(list))
98 return NULL;
99 return list->next;
100 }
101
102 /** Get last elem from list */
list_last(const struct List * list)103 static inline struct List *list_last(const struct List *list)
104 {
105 if (list_empty(list))
106 return NULL;
107 return list->prev;
108 }
109
110 /** Remove first elem from list and return with casting */
111 #define list_pop_type(list, typ, field) \
112 (list_empty(list) ? NULL \
113 : container_of(list_del((list)->next), typ, field))
114
115 /** Loop over list */
116 #define list_for_each(item, list) \
117 for ((item) = (list)->next; \
118 (item) != (list); \
119 (item) = (item)->next)
120
121 /** Loop over list backwards */
122 #define list_for_each_reverse(item, list) \
123 for ((item) = (list)->prev; \
124 (item) != (list); \
125 (item) = (item)->prev)
126
127 /** Loop over list and allow removing item */
128 #define list_for_each_safe(item, list, tmp) \
129 for ((item) = (list)->next, (tmp) = (list)->next->next; \
130 (item) != (list); \
131 (item) = (tmp), (tmp) = (tmp)->next)
132
133 /** Loop over list backwards and allow removing item */
134 #define list_for_each_reverse_safe(item, list, tmp) \
135 for ((item) = (list)->prev, (tmp) = (list)->prev->prev; \
136 (item) != (list); \
137 (item) = (tmp), (tmp) = (tmp)->prev)
138
139 /** Comparator function signature for list_sort() */
140 typedef int (*list_cmp_f)(const struct List *a, const struct List *b);
141
142 /**
143 * Sort list.
144 *
145 * This implementation uses stable merge sort which operates in-place.
146 */
147 void list_sort(struct List *list, list_cmp_f cmp_func);
148
149 #endif
150