1 #ifndef _LINUX_LIST_H_
2 #define _LINUX_LIST_H_
3
4 struct list_head {
5 struct list_head *next, *prev;
6 };
7
8 #define LIST_HEAD_INIT(name) { &(name), &(name) }
9
10 #undef LIST_HEAD
11 #define LIST_HEAD(name) \
12 struct list_head name = LIST_HEAD_INIT(name)
13
14 static inline void
INIT_LIST_HEAD(struct list_head * list)15 INIT_LIST_HEAD(struct list_head *list)
16 {
17 list->next = list;
18 list->prev = list;
19 }
20
21 static inline void
__list_add(struct list_head * new,struct list_head * prev,struct list_head * next)22 __list_add(struct list_head *new,
23 struct list_head *prev,
24 struct list_head *next)
25 {
26 next->prev = new;
27 new->next = next;
28 new->prev = prev;
29 prev->next = new;
30 }
31
32 static inline void
list_add(struct list_head * new,struct list_head * head)33 list_add(struct list_head *new, struct list_head *head)
34 {
35 __list_add(new, head, head->next);
36 }
37
38 static inline void
list_add_tail(struct list_head * new,struct list_head * head)39 list_add_tail(struct list_head *new, struct list_head *head)
40 {
41 __list_add(new, head->prev, head);
42 }
43
44 static inline bool
__list_add_valid(struct list_head * new,struct list_head * prev,struct list_head * next)45 __list_add_valid(struct list_head *new,
46 struct list_head *prev,
47 struct list_head *next)
48 {
49 return true;
50 }
51
52 static inline bool
__list_del_entry_valid(struct list_head * entry)53 __list_del_entry_valid(struct list_head *entry)
54 {
55 return true;
56 }
57
58 static inline void
__list_del(struct list_head * prev,struct list_head * next)59 __list_del(struct list_head *prev, struct list_head *next)
60 {
61 next->prev = prev;
62 prev->next = next;
63 }
64
65 static inline void
__list_del_entry(struct list_head * entry)66 __list_del_entry(struct list_head *entry)
67 {
68 __list_del(entry->prev, entry->next);
69 }
70
71 static inline void
list_del(struct list_head * entry)72 list_del(struct list_head *entry)
73 {
74 __list_del(entry->prev, entry->next);
75 entry->next = NULL;
76 entry->prev = NULL;
77 }
78
79 static inline void
list_replace(struct list_head * old,struct list_head * new)80 list_replace(struct list_head *old,
81 struct list_head *new)
82 {
83 new->next = old->next;
84 new->next->prev = new;
85 new->prev = old->prev;
86 new->prev->next = new;
87 }
88
89 static inline void
list_replace_init(struct list_head * old,struct list_head * new)90 list_replace_init(struct list_head *old,
91 struct list_head *new)
92 {
93 list_replace(old, new);
94 INIT_LIST_HEAD(old);
95 }
96
97 static inline void
list_del_init(struct list_head * entry)98 list_del_init(struct list_head *entry)
99 {
100 __list_del(entry->prev, entry->next);
101 INIT_LIST_HEAD(entry);
102 }
103
104 static inline void
list_move(struct list_head * list,struct list_head * head)105 list_move(struct list_head *list, struct list_head *head)
106 {
107 __list_del(list->prev, list->next);
108 list_add(list, head);
109 }
110
111 static inline void
list_move_tail(struct list_head * list,struct list_head * head)112 list_move_tail(struct list_head *list,
113 struct list_head *head)
114 {
115 __list_del(list->prev, list->next);
116 list_add_tail(list, head);
117 }
118
119 static inline int
list_is_last(const struct list_head * list,const struct list_head * head)120 list_is_last(const struct list_head *list,
121 const struct list_head *head)
122 {
123 return list->next == head;
124 }
125
126 static inline int
list_empty(const struct list_head * head)127 list_empty(const struct list_head *head)
128 {
129 return head->next == head;
130 }
131
132 static inline int
list_empty_careful(const struct list_head * head)133 list_empty_careful(const struct list_head *head)
134 {
135 struct list_head *next = head->next;
136
137 return (next == head) && (next == head->prev);
138 }
139
140 static inline int
list_is_singular(const struct list_head * head)141 list_is_singular(const struct list_head *head)
142 {
143 return !list_empty(head) && (head->next == head->prev);
144 }
145
146 static inline void
__list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)147 __list_cut_position(struct list_head *list,
148 struct list_head *head, struct list_head *entry)
149 {
150 struct list_head *new_first = entry->next;
151
152 list->next = head->next;
153 list->next->prev = list;
154 list->prev = entry;
155 entry->next = list;
156 head->next = new_first;
157 new_first->prev = head;
158 }
159
160 static inline void
list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)161 list_cut_position(struct list_head *list,
162 struct list_head *head, struct list_head *entry)
163 {
164 if (list_empty(head))
165 return;
166 if (list_is_singular(head) &&
167 (head->next != entry && head != entry))
168 return;
169 if (entry == head)
170 INIT_LIST_HEAD(list);
171 else
172 __list_cut_position(list, head, entry);
173 }
174
175 static inline void
__list_splice(const struct list_head * list,struct list_head * prev,struct list_head * next)176 __list_splice(const struct list_head *list,
177 struct list_head *prev,
178 struct list_head *next)
179 {
180 struct list_head *first = list->next;
181 struct list_head *last = list->prev;
182
183 first->prev = prev;
184 prev->next = first;
185
186 last->next = next;
187 next->prev = last;
188 }
189
190 static inline void
list_splice(const struct list_head * list,struct list_head * head)191 list_splice(const struct list_head *list,
192 struct list_head *head)
193 {
194 if (!list_empty(list))
195 __list_splice(list, head, head->next);
196 }
197
198 static inline void
list_splice_tail(struct list_head * list,struct list_head * head)199 list_splice_tail(struct list_head *list,
200 struct list_head *head)
201 {
202 if (!list_empty(list))
203 __list_splice(list, head->prev, head);
204 }
205
206 static inline void
list_splice_init(struct list_head * list,struct list_head * head)207 list_splice_init(struct list_head *list,
208 struct list_head *head)
209 {
210 if (!list_empty(list)) {
211 __list_splice(list, head, head->next);
212 INIT_LIST_HEAD(list);
213 }
214 }
215
216 static inline void
list_splice_tail_init(struct list_head * list,struct list_head * head)217 list_splice_tail_init(struct list_head *list,
218 struct list_head *head)
219 {
220 if (!list_empty(list)) {
221 __list_splice(list, head->prev, head);
222 INIT_LIST_HEAD(list);
223 }
224 }
225
226 #define list_entry(ptr, type, member) \
227 container_of(ptr, type, member)
228
229 #define list_first_entry(ptr, type, member) \
230 list_entry((ptr)->next, type, member)
231
232 #define list_next_entry(pos, member) \
233 list_entry((pos)->member.next, typeof(*(pos)), member)
234
235 #define list_last_entry(ptr, type, member) \
236 list_entry((ptr)->prev, type, member)
237
238 #define list_first_entry_or_null(ptr, type, member) \
239 (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
240
241 #define list_for_each(pos, head) \
242 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
243 pos = pos->next)
244
245 #define __list_for_each(pos, head) \
246 for (pos = (head)->next; pos != (head); pos = pos->next)
247
248 #define list_for_each_prev(pos, head) \
249 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
250 pos = pos->prev)
251
252 #define list_for_each_safe(pos, n, head) \
253 for (pos = (head)->next, n = pos->next; pos != (head); \
254 pos = n, n = pos->next)
255
256 #define list_for_each_prev_safe(pos, n, head) \
257 for (pos = (head)->prev, n = pos->prev; \
258 prefetch(pos->prev), pos != (head); \
259 pos = n, n = pos->prev)
260
261 #define list_for_each_entry(pos, head, member) \
262 for (pos = list_entry((head)->next, typeof(*pos), member); \
263 prefetch(pos->member.next), &pos->member != (head); \
264 pos = list_entry(pos->member.next, typeof(*pos), member))
265
266 #define list_for_each_entry_reverse(pos, head, member) \
267 for (pos = list_entry((head)->prev, typeof(*pos), member); \
268 prefetch(pos->member.prev), &pos->member != (head); \
269 pos = list_entry(pos->member.prev, typeof(*pos), member))
270
271 #define list_prepare_entry(pos, head, member) \
272 ((pos) ? : list_entry(head, typeof(*pos), member))
273
274 #define list_for_each_entry_continue(pos, head, member) \
275 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
276 prefetch(pos->member.next), &pos->member != (head); \
277 pos = list_entry(pos->member.next, typeof(*pos), member))
278
279 #define list_for_each_entry_continue_reverse(pos, head, member) \
280 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
281 prefetch(pos->member.prev), &pos->member != (head); \
282 pos = list_entry(pos->member.prev, typeof(*pos), member))
283
284 #define list_for_each_entry_from(pos, head, member) \
285 for (; prefetch(pos->member.next), &pos->member != (head); \
286 pos = list_entry(pos->member.next, typeof(*pos), member))
287
288 #define list_for_each_entry_safe(pos, n, head, member) \
289 for (pos = list_entry((head)->next, typeof(*pos), member), \
290 n = list_entry(pos->member.next, typeof(*pos), member); \
291 &pos->member != (head); \
292 pos = n, n = list_entry(n->member.next, typeof(*n), member))
293
294 #define list_for_each_entry_safe_continue(pos, n, head, member) \
295 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
296 n = list_entry(pos->member.next, typeof(*pos), member); \
297 &pos->member != (head); \
298 pos = n, n = list_entry(n->member.next, typeof(*n), member))
299
300 #define list_for_each_entry_safe_from(pos, n, head, member) \
301 for (n = list_entry(pos->member.next, typeof(*pos), member); \
302 &pos->member != (head); \
303 pos = n, n = list_entry(n->member.next, typeof(*n), member))
304
305 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
306 for (pos = list_entry((head)->prev, typeof(*pos), member), \
307 n = list_entry(pos->member.prev, typeof(*pos), member); \
308 &pos->member != (head); \
309 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
310
311 struct hlist_head {
312 struct hlist_node *first;
313 };
314
315 struct hlist_node {
316 struct hlist_node *next, **pprev;
317 };
318
319 #define HLIST_HEAD_INIT { .first = NULL }
320 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
321 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
322 static inline void
INIT_HLIST_NODE(struct hlist_node * h)323 INIT_HLIST_NODE(struct hlist_node *h)
324 {
325 h->next = NULL;
326 h->pprev = NULL;
327 }
328
329 static inline int
hlist_unhashed(const struct hlist_node * h)330 hlist_unhashed(const struct hlist_node *h)
331 {
332 return !h->pprev;
333 }
334
335 static inline int
hlist_empty(const struct hlist_head * h)336 hlist_empty(const struct hlist_head *h)
337 {
338 return !h->first;
339 }
340
341 static inline void
__hlist_del(struct hlist_node * n)342 __hlist_del(struct hlist_node *n)
343 {
344 struct hlist_node *next = n->next;
345 struct hlist_node **pprev = n->pprev;
346
347 *pprev = next;
348 if (next)
349 next->pprev = pprev;
350 }
351
352 static inline void
hlist_del(struct hlist_node * n)353 hlist_del(struct hlist_node *n)
354 {
355 __hlist_del(n);
356 n->next = NULL;
357 n->pprev = NULL;
358 }
359
360 static inline void
hlist_del_init(struct hlist_node * n)361 hlist_del_init(struct hlist_node *n)
362 {
363 if (!hlist_unhashed(n)) {
364 __hlist_del(n);
365 INIT_HLIST_NODE(n);
366 }
367 }
368
369 static inline void
hlist_add_head(struct hlist_node * n,struct hlist_head * h)370 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
371 {
372 struct hlist_node *first = h->first;
373
374 n->next = first;
375 if (first)
376 first->pprev = &n->next;
377 h->first = n;
378 n->pprev = &h->first;
379 }
380
381 static inline void
hlist_add_before(struct hlist_node * n,struct hlist_node * next)382 hlist_add_before(struct hlist_node *n,
383 struct hlist_node *next)
384 {
385 n->pprev = next->pprev;
386 n->next = next;
387 next->pprev = &n->next;
388 *(n->pprev) = n;
389 }
390
391 static inline void
hlist_add_after(struct hlist_node * n,struct hlist_node * next)392 hlist_add_after(struct hlist_node *n,
393 struct hlist_node *next)
394 {
395 next->next = n->next;
396 n->next = next;
397 next->pprev = &n->next;
398
399 if (next->next)
400 next->next->pprev = &next->next;
401 }
402
403 static inline void
hlist_move_list(struct hlist_head * old,struct hlist_head * new)404 hlist_move_list(struct hlist_head *old,
405 struct hlist_head *new)
406 {
407 new->first = old->first;
408 if (new->first)
409 new->first->pprev = &new->first;
410 old->first = NULL;
411 }
412
413 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
414
415 #define hlist_for_each(pos, head) \
416 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
417 pos = pos->next)
418
419 #define hlist_for_each_safe(pos, n, head) \
420 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
421 pos = n)
422
423 #define hlist_for_each_entry(tpos, pos, head, member) \
424 for (pos = (head)->first; \
425 pos && ({ prefetch(pos->next); 1;}) && \
426 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
427 pos = pos->next)
428
429 #define hlist_for_each_entry_continue(tpos, pos, member) \
430 for (pos = (pos)->next; \
431 pos && ({ prefetch(pos->next); 1;}) && \
432 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
433 pos = pos->next)
434
435 #define hlist_for_each_entry_from(tpos, pos, member) \
436 for (; pos && ({ prefetch(pos->next); 1;}) && \
437 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
438 pos = pos->next)
439
440 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
441 for (pos = (head)->first; \
442 pos && ({ n = pos->next; 1; }) && \
443 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
444 pos = n)
445
446 #endif /* _LINUX_LIST_H_ */
447