1 #ifndef EL__UTIL_LISTS_H
2 #define EL__UTIL_LISTS_H
3
4 #include "util/error.h" /* do_not_optimize_here() */
5
6 /* BEWARE! You MAY NOT use ternary operator as parameter to there functions,
7 * because they are likely to take & of the parameter. Worst of all, it will
8 * work with gcc. But nowhere else (at least not w/ tcc). */
9
10 /* Note that this whole lists implementation code is severely broken. All of
11 * it is a single huge violation of C aliasing rules, just accessing things
12 * like we do here is totally prohibited and bound to generate segfaults in
13 * proportion with rising optimization level and gcc version.
14 *
15 * Fixing this would be a nice and needed janitorial project. */
16
17 /* Lists debugging
18 * Two unsigned int magic number will be put before and after the next and
19 * prev pointers, these will be check on list operations.
20 * Some pointers are set to specific values after action. */
21 #ifdef CONFIG_DEBUG
22 #define LISTDEBUG
23 #endif
24
25
26 /* Fix namespace clash with system headers (like FreeBSD's, all hail BSD!). */
27 #undef LIST_HEAD
28 #undef list_head
29 #define list_head list_head_elinks
30
31
32 #ifndef LISTDEBUG
33
34 #define list_del_enforce(x) /* better don't */
35
36 #define list_magic_error(where, what) /* no magic */
37
38 #define list_magic_set(x) /* no magic */
39
40 #define list_magic_correct(x) (1)
41 #define list_magic_check(x, where) /* no magic */
42 #define list_magic_chkbool(x, where) (1)
43
44 struct list_head {
45 void *next;
46 void *prev;
47 };
48
49 struct xlist_head {
50 struct xlist_head *next;
51 struct xlist_head *prev;
52 };
53
54 #define NULL_LIST_HEAD NULL, NULL
55 #define D_LIST_HEAD(x) &x, &x
56 #define LIST_HEAD(x) x *next; x *prev
57 #define LIST_SET_MAGIC(x) list_magic_set(*(x))
58
59
60 #else /* LISTDEBUG */
61
62 #define LISTMAGIC1 ((void *) 0xdadababa)
63 #define LISTMAGIC2 ((void *) 0xd0d0b0b0)
64 #define LISTMAGIC3 ((void *) 0x25254545)
65
66 #define list_del_enforce(x) \
67 do { \
68 /* Little hack: we put LISTMAGIC3 in prev */ \
69 /* and the line number in next. Debugging purpose. */ \
70 (x)->prev = LISTMAGIC3; \
71 (x)->next = (void *) ((unsigned int) __LINE__); \
72 } while (0)
73
74
75 #define list_magic_error(where,what) INTERNAL("[%s] %s - bad list magic", where, #what)
76
77
78 #define list_magic_set(x) \
79 do { \
80 (x).magic1 = LISTMAGIC1; \
81 (x).magic2 = LISTMAGIC2; \
82 } while (0)
83
84
85 /* Backend for list_magic_check() and list_magic_chkbool(). */
86 #define list_magic_correct(x) ((x).magic1 == LISTMAGIC1 && (x).magic2 == LISTMAGIC2)
87
88 #define list_magic_check(x, where) \
89 do { \
90 if (!list_magic_correct(*(x))) \
91 list_magic_error(where, x); \
92 } while (0)
93
94 #define list_magic_chkbool(x, where) (list_magic_correct(x) || (list_magic_error(where, x), 1))
95
96
97 struct list_head {
98 void *magic1;
99 void *next;
100 void *prev;
101 void *magic2;
102 };
103
104 struct xlist_head {
105 void *magic1;
106 struct xlist_head *next;
107 struct xlist_head *prev;
108 void *magic2;
109 };
110
111
112 #define NULL_LIST_HEAD LISTMAGIC1, NULL, NULL, LISTMAGIC2
113 #define D_LIST_HEAD(x) LISTMAGIC1, &x, &x, LISTMAGIC2
114 #define LIST_HEAD(x) void *magic1; x *next; x *prev; void *magic2
115 #define LIST_SET_MAGIC(x) list_magic_set(*(x))
116
117 #endif /* LISTDEBUG */
118
119 #define INIT_LIST_HEAD(x) struct list_head x = { D_LIST_HEAD(x) }
120
121 #ifdef HAVE_TYPEOF
122 #define list_typeof(x) typeof(x)
123 #else
124 #define list_typeof(x) struct xlist_head *
125 #endif /* HAVE_TYPEOF */
126
127
128 #define init_list(x) \
129 do { \
130 list_magic_set(x); \
131 do_not_optimize_here_gcc_3_x(&(x)); /* antialiasing ;) */ \
132 (x).next = (x).prev = &(x); \
133 do_not_optimize_here_gcc_3_x(&(x)); \
134 } while (0)
135
136
137 #define list_empty(x) (list_magic_chkbool(x, "list_empty") && (x).next == &(x))
138
139 #define list_is_singleton(x) \
140 (list_magic_chkbool(x, "list_is_singleton") && (x).next == (x).prev)
141
142 #define list_has_prev(l,p) \
143 (list_magic_chkbool(l, "list_has_prev") && (p)->prev != (void *) &(l))
144
145 #define list_has_next(l,p) \
146 (list_magic_chkbool(l, "list_has_next") && (p)->next != (void *) &(l))
147
148 #define del_from_list(x) \
149 do { \
150 list_magic_check(x, "del_from_list"); \
151 do_not_optimize_here_gcc_2_7(x); \
152 ((struct list_head *) (x)->next)->prev = (x)->prev; \
153 ((struct list_head *) (x)->prev)->next = (x)->next; \
154 list_del_enforce(x); \
155 do_not_optimize_here_gcc_2_7(x); \
156 } while (0)
157
158 #define add_at_pos(p,x) \
159 do { \
160 list_magic_check(p, "add_at_pos"); \
161 list_magic_set(*(x)); \
162 do_not_optimize_here_gcc_2_7(p); \
163 (x)->next = (p)->next; \
164 (x)->prev = (p); \
165 (p)->next = (x); \
166 (x)->next->prev = (x); \
167 do_not_optimize_here_gcc_2_7(p); \
168 } while (0)
169
170
171 #define add_to_list(l,x) \
172 add_at_pos((list_typeof(x)) &(l), (list_typeof(x)) (x))
173
174 #define add_to_list_end(l,x) \
175 add_at_pos((list_typeof(x)) (l).prev, (list_typeof(x)) (x))
176
177 #define foreach(e,l) \
178 for ((e) = (l).next; \
179 (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
180 (e) = (e)->next)
181
182 #define foreachback(e,l) \
183 for ((e) = (l).prev; \
184 (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
185 (e) = (e)->prev)
186
187 #define foreachsafe(e, n, l) \
188 for ((e) = (l).next, (n) = (e)->next; \
189 (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
190 (e) = (n), (n) = (e)->next)
191
192 #define foreachbacksafe(e, p, l) \
193 for ((e) = (l).prev, (p) = (e)->prev; \
194 (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
195 (e) = (p), (p) = (e)->prev)
196
197 #define free_list(l) \
198 do { \
199 struct xlist_head *head, *next; \
200 \
201 list_magic_check(&(l), "free_list"); \
202 do_not_optimize_here_gcc_2_7(&l); \
203 foreach (head, (l)) do_not_optimize_here_gcc_3_x(head); /* AA */ \
204 foreachback (head, (l)) do_not_optimize_here_gcc_3_x(head); /* AA */ \
205 foreachsafe (head, next, l) { \
206 del_from_list(head); \
207 mem_free(head); \
208 } \
209 do_not_optimize_here_gcc_2_7(&l); \
210 } while (0)
211
212 static inline int
list_size(struct list_head * list)213 list_size(struct list_head *list)
214 {
215 struct list_head *item;
216 int size = 0;
217
218 foreach (item, *list)
219 size++;
220
221 return size;
222 }
223
224 #define move_to_top_of_list(list, item) do { \
225 if ((item) != (list).next) { \
226 del_from_list(item); \
227 add_to_list(list, item); \
228 } \
229 } while (0)
230
231
232 #endif /* EL__UTIL_LISTS_H */
233