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