1 /*-
2 * Copyright (c) 2010 Isilon Systems, Inc.
3 * Copyright (c) 2010 iX Systems, Inc.
4 * Copyright (c) 2010 Panasas, Inc.
5 * Copyright (c) 2013-2016 Mellanox Technologies, Ltd.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice unmodified, this list of conditions, and the following
13 * disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29 #ifndef _LINUX_LIST_H_
30 #define _LINUX_LIST_H_
31
32 #define container_of(ptr, type, member) \
33 ({ \
34 const __typeof(((type *)0)->member) *__p = (ptr); \
35 (type *)((uintptr_t)__p - offsetof(type, member)); \
36 })
37
38 #define LINUX_LIST_HEAD_INIT(name) { &(name), &(name) }
39
40 #define LINUX_LIST_HEAD(name) \
41 struct list_head name = LINUX_LIST_HEAD_INIT(name)
42
43 #ifndef LIST_HEAD_DEF
44 #define LIST_HEAD_DEF
45 struct list_head {
46 struct list_head *next;
47 struct list_head *prev;
48 };
49 #endif
50
51 #define barrier() __asm__ __volatile__("": : :"memory")
52
53
54 #define ACCESS_ONCE(x) (*(volatile __typeof(x) *)&(x))
55
56 #define WRITE_ONCE(x,v) do { \
57 barrier(); \
58 ACCESS_ONCE(x) = (v); \
59 barrier(); \
60 } while (0)
61
62 #define READ_ONCE(x) ({ \
63 __typeof(x) __var = ({ \
64 barrier(); \
65 ACCESS_ONCE(x); \
66 }); \
67 barrier(); \
68 __var; \
69 })
70
71 static inline void
INIT_LIST_HEAD(struct list_head * list)72 INIT_LIST_HEAD(struct list_head *list)
73 {
74
75 list->next = list->prev = list;
76 }
77
78 static inline int
list_empty(const struct list_head * head)79 list_empty(const struct list_head *head)
80 {
81
82 return (head->next == head);
83 }
84
85 static inline int
list_empty_careful(const struct list_head * head)86 list_empty_careful(const struct list_head *head)
87 {
88 struct list_head *next = head->next;
89
90 return ((next == head) && (next == head->prev));
91 }
92
93 static inline void
__list_del(struct list_head * prev,struct list_head * next)94 __list_del(struct list_head *prev, struct list_head *next)
95 {
96 next->prev = prev;
97 WRITE_ONCE(prev->next, next);
98 }
99
100 static inline void
__list_del_entry(struct list_head * entry)101 __list_del_entry(struct list_head *entry)
102 {
103
104 __list_del(entry->prev, entry->next);
105 }
106
107 static inline void
list_del(struct list_head * entry)108 list_del(struct list_head *entry)
109 {
110
111 __list_del(entry->prev, entry->next);
112 }
113
114 static inline void
list_replace(struct list_head * old,struct list_head * new)115 list_replace(struct list_head *old, struct list_head *new)
116 {
117 new->next = old->next;
118 new->next->prev = new;
119 new->prev = old->prev;
120 new->prev->next = new;
121 }
122
123 static inline void
list_replace_init(struct list_head * old,struct list_head * new)124 list_replace_init(struct list_head *old, struct list_head *new)
125 {
126 list_replace(old, new);
127 INIT_LIST_HEAD(old);
128 }
129
130 static inline void
linux_list_add(struct list_head * new,struct list_head * prev,struct list_head * next)131 linux_list_add(struct list_head *new, struct list_head *prev,
132 struct list_head *next)
133 {
134
135 next->prev = new;
136 new->next = next;
137 new->prev = prev;
138 prev->next = new;
139 }
140
141 static inline void
list_del_init(struct list_head * entry)142 list_del_init(struct list_head *entry)
143 {
144
145 list_del(entry);
146 INIT_LIST_HEAD(entry);
147 }
148
149 #define list_entry(ptr, type, field) container_of(ptr, type, field)
150
151 #define list_first_entry(ptr, type, member) \
152 list_entry((ptr)->next, type, member)
153
154 #define list_last_entry(ptr, type, member) \
155 list_entry((ptr)->prev, type, member)
156
157 #define list_first_entry_or_null(ptr, type, member) \
158 (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
159
160 #define list_next_entry(ptr, member) \
161 list_entry(((ptr)->member.next), typeof(*(ptr)), member)
162
163 #define list_safe_reset_next(ptr, n, member) \
164 (n) = list_next_entry(ptr, member)
165
166 #define list_prev_entry(ptr, member) \
167 list_entry(((ptr)->member.prev), typeof(*(ptr)), member)
168
169 #define list_for_each(p, head) \
170 for (p = (head)->next; p != (head); p = (p)->next)
171
172 #define list_for_each_safe(p, n, head) \
173 for (p = (head)->next, n = (p)->next; p != (head); p = n, n = (p)->next)
174
175 #define list_for_each_entry(p, h, field) \
176 for (p = list_entry((h)->next, typeof(*p), field); &(p)->field != (h); \
177 p = list_entry((p)->field.next, typeof(*p), field))
178
179 #define list_for_each_entry_safe(p, n, h, field) \
180 for (p = list_entry((h)->next, typeof(*p), field), \
181 n = list_entry((p)->field.next, typeof(*p), field); &(p)->field != (h);\
182 p = n, n = list_entry(n->field.next, typeof(*n), field))
183
184 #define list_for_each_entry_from(p, h, field) \
185 for ( ; &(p)->field != (h); \
186 p = list_entry((p)->field.next, typeof(*p), field))
187
188 #define list_for_each_entry_continue(p, h, field) \
189 for (p = list_next_entry((p), field); &(p)->field != (h); \
190 p = list_next_entry((p), field))
191
192 #define list_for_each_entry_safe_from(pos, n, head, member) \
193 for (n = list_entry((pos)->member.next, typeof(*pos), member); \
194 &(pos)->member != (head); \
195 pos = n, n = list_entry(n->member.next, typeof(*n), member))
196
197 #define list_for_each_entry_reverse(p, h, field) \
198 for (p = list_entry((h)->prev, typeof(*p), field); &(p)->field != (h); \
199 p = list_entry((p)->field.prev, typeof(*p), field))
200
201 #define list_for_each_entry_safe_reverse(p, n, h, field) \
202 for (p = list_entry((h)->prev, typeof(*p), field), \
203 n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
204 p = n, n = list_entry(n->field.prev, typeof(*n), field))
205
206 #define list_for_each_entry_continue_reverse(p, h, field) \
207 for (p = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \
208 p = list_entry((p)->field.prev, typeof(*p), field))
209
210 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = (p)->prev)
211
212 static inline void
list_add(struct list_head * new,struct list_head * head)213 list_add(struct list_head *new, struct list_head *head)
214 {
215
216 linux_list_add(new, head, head->next);
217 }
218
219 static inline void
list_add_tail(struct list_head * new,struct list_head * head)220 list_add_tail(struct list_head *new, struct list_head *head)
221 {
222
223 linux_list_add(new, head->prev, head);
224 }
225
226 static inline void
list_move(struct list_head * list,struct list_head * head)227 list_move(struct list_head *list, struct list_head *head)
228 {
229
230 list_del(list);
231 list_add(list, head);
232 }
233
234 static inline void
list_move_tail(struct list_head * entry,struct list_head * head)235 list_move_tail(struct list_head *entry, struct list_head *head)
236 {
237
238 list_del(entry);
239 list_add_tail(entry, head);
240 }
241
242 static inline void
linux_list_splice(const struct list_head * list,struct list_head * prev,struct list_head * next)243 linux_list_splice(const struct list_head *list, struct list_head *prev,
244 struct list_head *next)
245 {
246 struct list_head *first;
247 struct list_head *last;
248
249 if (list_empty(list))
250 return;
251 first = list->next;
252 last = list->prev;
253 first->prev = prev;
254 prev->next = first;
255 last->next = next;
256 next->prev = last;
257 }
258
259 static inline void
list_splice(const struct list_head * list,struct list_head * head)260 list_splice(const struct list_head *list, struct list_head *head)
261 {
262
263 linux_list_splice(list, head, head->next);
264 }
265
266 static inline void
list_splice_tail(struct list_head * list,struct list_head * head)267 list_splice_tail(struct list_head *list, struct list_head *head)
268 {
269
270 linux_list_splice(list, head->prev, head);
271 }
272
273 static inline void
list_splice_init(struct list_head * list,struct list_head * head)274 list_splice_init(struct list_head *list, struct list_head *head)
275 {
276
277 linux_list_splice(list, head, head->next);
278 INIT_LIST_HEAD(list);
279 }
280
281 static inline void
list_splice_tail_init(struct list_head * list,struct list_head * head)282 list_splice_tail_init(struct list_head *list, struct list_head *head)
283 {
284
285 linux_list_splice(list, head->prev, head);
286 INIT_LIST_HEAD(list);
287 }
288
289 #undef LIST_HEAD
290 #define LIST_HEAD(name) struct list_head name = { &(name), &(name) }
291
292
293 struct hlist_head {
294 struct hlist_node *first;
295 };
296
297 struct hlist_node {
298 struct hlist_node *next, **pprev;
299 };
300
301 #define HLIST_HEAD_INIT { }
302 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
303 #define INIT_HLIST_HEAD(head) (head)->first = NULL
304 #define INIT_HLIST_NODE(node) \
305 do { \
306 (node)->next = NULL; \
307 (node)->pprev = NULL; \
308 } while (0)
309
310 static inline int
hlist_unhashed(const struct hlist_node * h)311 hlist_unhashed(const struct hlist_node *h)
312 {
313
314 return !h->pprev;
315 }
316
317 static inline int
hlist_empty(const struct hlist_head * h)318 hlist_empty(const struct hlist_head *h)
319 {
320
321 return !h->first;
322 }
323
324 static inline void
hlist_del(struct hlist_node * n)325 hlist_del(struct hlist_node *n)
326 {
327
328 if (n->next)
329 n->next->pprev = n->pprev;
330 *n->pprev = n->next;
331 }
332
333 static inline void
hlist_del_init(struct hlist_node * n)334 hlist_del_init(struct hlist_node *n)
335 {
336
337 if (hlist_unhashed(n))
338 return;
339 hlist_del(n);
340 INIT_HLIST_NODE(n);
341 }
342
343 static inline void
hlist_add_head(struct hlist_node * n,struct hlist_head * h)344 hlist_add_head(struct hlist_node *n, struct hlist_head *h)
345 {
346
347 n->next = h->first;
348 if (h->first)
349 h->first->pprev = &n->next;
350 h->first = n;
351 n->pprev = &h->first;
352 }
353
354 static inline void
hlist_add_before(struct hlist_node * n,struct hlist_node * next)355 hlist_add_before(struct hlist_node *n, struct hlist_node *next)
356 {
357
358 n->pprev = next->pprev;
359 n->next = next;
360 next->pprev = &n->next;
361 *(n->pprev) = n;
362 }
363
364 static inline void
hlist_add_after(struct hlist_node * n,struct hlist_node * next)365 hlist_add_after(struct hlist_node *n, struct hlist_node *next)
366 {
367
368 next->next = n->next;
369 n->next = next;
370 next->pprev = &n->next;
371 if (next->next)
372 next->next->pprev = &next->next;
373 }
374
375 static inline void
hlist_move_list(struct hlist_head * old,struct hlist_head * new)376 hlist_move_list(struct hlist_head *old, struct hlist_head *new)
377 {
378
379 new->first = old->first;
380 if (new->first)
381 new->first->pprev = &new->first;
382 old->first = NULL;
383 }
384
list_is_singular(const struct list_head * head)385 static inline int list_is_singular(const struct list_head *head)
386 {
387 return !list_empty(head) && (head->next == head->prev);
388 }
389
__list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)390 static inline void __list_cut_position(struct list_head *list,
391 struct list_head *head, struct list_head *entry)
392 {
393 struct list_head *new_first = entry->next;
394 list->next = head->next;
395 list->next->prev = list;
396 list->prev = entry;
397 entry->next = list;
398 head->next = new_first;
399 new_first->prev = head;
400 }
401
list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)402 static inline void list_cut_position(struct list_head *list,
403 struct list_head *head, struct list_head *entry)
404 {
405 if (list_empty(head))
406 return;
407 if (list_is_singular(head) &&
408 (head->next != entry && head != entry))
409 return;
410 if (entry == head)
411 INIT_LIST_HEAD(list);
412 else
413 __list_cut_position(list, head, entry);
414 }
415
list_is_last(const struct list_head * list,const struct list_head * head)416 static inline int list_is_last(const struct list_head *list,
417 const struct list_head *head)
418 {
419 return list->next == head;
420 }
421
422 #define hlist_entry(ptr, type, field) container_of(ptr, type, field)
423
424 #define hlist_for_each(p, head) \
425 for (p = (head)->first; p; p = (p)->next)
426
427 #define hlist_for_each_safe(p, n, head) \
428 for (p = (head)->first; p && ({ n = (p)->next; 1; }); p = n)
429
430 #define hlist_entry_safe(ptr, type, member) \
431 ((ptr) ? hlist_entry(ptr, type, member) : NULL)
432
433 #define hlist_for_each_entry(pos, head, member) \
434 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
435 pos; \
436 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
437
438 #define hlist_for_each_entry_continue(pos, member) \
439 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member); \
440 (pos); \
441 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
442
443 #define hlist_for_each_entry_from(pos, member) \
444 for (; (pos); \
445 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
446
447 #define hlist_for_each_entry_safe(pos, n, head, member) \
448 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
449 (pos) && ({ n = (pos)->member.next; 1; }); \
450 pos = hlist_entry_safe(n, typeof(*(pos)), member))
451
452 extern void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv,
453 struct list_head *a, struct list_head *b));
454
455 #endif /* _LINUX_LIST_H_ */
456