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 * Copyright (c) 2015-2017 François Tigeot
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice unmodified, this list of conditions, and the following
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 #ifndef _LINUX_LIST_H_
31 #define _LINUX_LIST_H_
34 * Since LIST_HEAD conflicts with the linux definition we must include any
35 * FreeBSD header which requires it here so it is resolved with the correct
36 * definition prior to the undef.
38 #include <linux/types.h>
40 #include <sys/param.h>
41 #include <sys/kernel.h>
42 #include <sys/queue.h>
45 #include <sys/mutex.h>
48 #include <sys/socket.h>
53 #include <net/if_var.h>
54 #include <net/if_types.h>
55 #include <net/if_media.h>
57 #include <netinet/in.h>
58 #include <netinet/in_pcb.h>
59 #include <netinet/in_var.h>
61 #include <netinet6/in6_var.h>
62 #include <netinet6/nd6.h>
65 #include <vm/vm_object.h>
70 struct list_head
*next
;
71 struct list_head
*prev
;
75 INIT_LIST_HEAD(struct list_head
*list
)
78 list
->next
= list
->prev
= list
;
81 static inline struct list_head
*
82 list_first(const struct list_head
*head
)
87 static inline struct list_head
*
88 list_last(const struct list_head
*head
)
94 list_empty(const struct list_head
*head
)
96 return (head
->next
== head
);
100 list_empty_careful(const struct list_head
*head
)
102 return (head
== head
->next
) && (head
== head
->prev
);
106 list_del(struct list_head
*entry
)
109 entry
->next
->prev
= entry
->prev
;
110 entry
->prev
->next
= entry
->next
;
113 static inline void list_replace(struct list_head
*old
,
114 struct list_head
*new)
116 new->next
= old
->next
;
117 new->next
->prev
= new;
118 new->prev
= old
->prev
;
119 new->prev
->next
= new;
122 static inline void list_replace_init(struct list_head
*old
,
123 struct list_head
*new)
125 list_replace(old
, new);
130 _list_add(struct list_head
*new, struct list_head
*prev
,
131 struct list_head
*next
)
141 list_del_init(struct list_head
*entry
)
145 INIT_LIST_HEAD(entry
);
148 #define list_entry(ptr, type, field) container_of(ptr, type, field)
150 #define list_first_entry(ptr, type, member) \
151 list_entry((ptr)->next, type, member)
153 #define list_first_entry_or_null(ptr, type, member) \
154 (list_empty(ptr) ? NULL: list_first_entry(ptr, type, member))
156 #define list_last_entry(ptr, type, field) \
157 list_entry(list_last((ptr)), type, field)
159 #define list_next_entry(ptr, member) \
160 list_entry(((ptr)->member.next), typeof(*(ptr)), member)
162 #define list_for_each(p, head) \
163 for (p = (head)->next; p != (head); p = p->next)
165 #define list_for_each_safe(p, n, head) \
166 for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)
168 #define list_for_each_entry(p, h, field) \
169 for (p = list_entry((h)->next, typeof(*p), field); &p->field != (h); \
170 p = list_entry(p->field.next, typeof(*p), field))
172 #define list_for_each_entry_safe(p, n, h, field) \
173 for (p = list_entry((h)->next, typeof(*p), field), \
174 n = list_entry(p->field.next, typeof(*p), field); &p->field != (h);\
175 p = n, n = list_entry(n->field.next, typeof(*n), field))
177 #define list_for_each_entry_continue(p, h, field) \
178 for (p = list_next_entry((p), field); &p->field != (h); \
179 p = list_next_entry((p), field))
181 #define list_for_each_entry_safe_from(pos, n, head, member) \
182 for (n = list_entry(pos->member.next, typeof(*pos), member); \
183 &pos->member != (head); \
184 pos = n, n = list_entry(n->member.next, typeof(*n), member))
186 #define list_for_each_entry_reverse(p, h, field) \
187 for (p = list_entry((h)->prev, typeof(*p), field); &p->field != (h); \
188 p = list_entry(p->field.prev, typeof(*p), field))
190 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = p->prev)
193 list_add(struct list_head
*new, struct list_head
*head
)
196 _list_add(new, head
, head
->next
);
200 list_add_tail(struct list_head
*new, struct list_head
*head
)
203 _list_add(new, head
->prev
, head
);
207 list_move(struct list_head
*list
, struct list_head
*head
)
211 list_add(list
, head
);
215 list_move_tail(struct list_head
*entry
, struct list_head
*head
)
219 list_add_tail(entry
, head
);
223 _list_splice(const struct list_head
*list
, struct list_head
*prev
,
224 struct list_head
*next
)
226 struct list_head
*first
;
227 struct list_head
*last
;
229 if (list_empty(list
))
240 list_splice(const struct list_head
*list
, struct list_head
*head
)
243 _list_splice(list
, head
, head
->next
);
247 list_splice_tail(struct list_head
*list
, struct list_head
*head
)
250 _list_splice(list
, head
->prev
, head
);
254 list_splice_init(struct list_head
*list
, struct list_head
*head
)
257 _list_splice(list
, head
, head
->next
);
258 INIT_LIST_HEAD(list
);
262 list_splice_tail_init(struct list_head
*list
, struct list_head
*head
)
265 _list_splice(list
, head
->prev
, head
);
266 INIT_LIST_HEAD(list
);
269 #define LINUX_LIST_HEAD(name) struct list_head name = { &(name), &(name) }
273 struct hlist_node
*first
;
277 struct hlist_node
*next
, **pprev
;
280 #define HLIST_HEAD_INIT { }
281 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
282 #define INIT_HLIST_HEAD(head) (head)->first = NULL
283 #define INIT_HLIST_NODE(node) \
285 (node)->next = NULL; \
286 (node)->pprev = NULL; \
290 hlist_unhashed(const struct hlist_node
*h
)
297 hlist_empty(const struct hlist_head
*h
)
304 hlist_del(struct hlist_node
*n
)
308 n
->next
->pprev
= n
->pprev
;
313 hlist_del_init(struct hlist_node
*n
)
316 if (hlist_unhashed(n
))
323 hlist_add_head(struct hlist_node
*n
, struct hlist_head
*h
)
328 h
->first
->pprev
= &n
->next
;
330 n
->pprev
= &h
->first
;
334 hlist_add_before(struct hlist_node
*n
, struct hlist_node
*next
)
337 n
->pprev
= next
->pprev
;
339 next
->pprev
= &n
->next
;
344 hlist_add_after(struct hlist_node
*n
, struct hlist_node
*next
)
347 next
->next
= n
->next
;
349 next
->pprev
= &n
->next
;
351 next
->next
->pprev
= &next
->next
;
355 hlist_move_list(struct hlist_head
*old
, struct hlist_head
*new)
358 new->first
= old
->first
;
360 new->first
->pprev
= &new->first
;
365 * list_is_singular - tests whether a list has just one entry.
366 * @head: the list to test.
368 static inline int list_is_singular(const struct list_head
*head
)
370 return !list_empty(head
) && (head
->next
== head
->prev
);
373 static inline void __list_cut_position(struct list_head
*list
,
374 struct list_head
*head
, struct list_head
*entry
)
376 struct list_head
*new_first
= entry
->next
;
377 list
->next
= head
->next
;
378 list
->next
->prev
= list
;
381 head
->next
= new_first
;
382 new_first
->prev
= head
;
386 * list_cut_position - cut a list into two
387 * @list: a new list to add all removed entries
388 * @head: a list with entries
389 * @entry: an entry within head, could be the head itself
390 * and if so we won't cut the list
392 * This helper moves the initial part of @head, up to and
393 * including @entry, from @head to @list. You should
394 * pass on @entry an element you know is on @head. @list
395 * should be an empty list or a list you do not care about
399 static inline void list_cut_position(struct list_head
*list
,
400 struct list_head
*head
, struct list_head
*entry
)
402 if (list_empty(head
))
404 if (list_is_singular(head
) &&
405 (head
->next
!= entry
&& head
!= entry
))
408 INIT_LIST_HEAD(list
);
410 __list_cut_position(list
, head
, entry
);
414 * list_is_last - tests whether @list is the last entry in list @head
415 * @list: the entry to test
416 * @head: the head of the list
418 static inline int list_is_last(const struct list_head
*list
,
419 const struct list_head
*head
)
421 return list
->next
== head
;
424 #define hlist_entry(ptr, type, field) container_of(ptr, type, field)
426 #define hlist_for_each(p, head) \
427 for (p = (head)->first; p; p = p->next)
429 #define hlist_for_each_safe(p, n, head) \
430 for (p = (head)->first; p && ({ n = p->next; 1; }); p = n)
432 #define hlist_entry_safe(ptr, type, member) \
433 (ptr) ? hlist_entry(ptr, type, member) : NULL
435 #define hlist_for_each_entry(pos, head, member) \
436 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
438 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
440 #define hlist_for_each_entry_continue(tp, p, field) \
441 for (p = (p)->next; \
442 p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next)
444 #define hlist_for_each_entry_from(tp, p, field) \
445 for (; p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next)
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))
452 void drm_list_sort(void *priv
, struct list_head
*head
, int (*cmp
)(void *priv
,
453 struct list_head
*a
, struct list_head
*b
));
455 #define hlist_add_head_rcu(n, h) hlist_add_head(n, h)
457 #define hlist_del_init_rcu(n) hlist_del_init(n)
459 #endif /* _LINUX_LIST_H_ */