1/* drm_linux_list.h -- linux list functions for the BSDs.
2 * Created: Mon Apr 7 14:30:16 1999 by anholt@FreeBSD.org
3 */
4/*-
5 * Copyright 2003 Eric Anholt
6 * All Rights Reserved.
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a
9 * copy of this software and associated documentation files (the "Software"),
10 * to deal in the Software without restriction, including without limitation
11 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
12 * and/or sell copies of the Software, and to permit persons to whom the
13 * Software is furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice (including the next
16 * paragraph) shall be included in all copies or substantial portions of the
17 * Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
22 * VA LINUX SYSTEMS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
23 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
24 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
26 *
27 * Authors:
28 *    Eric Anholt <anholt@FreeBSD.org>
29 *
30 */
31
32#include <sys/cdefs.h>
33__FBSDID("$FreeBSD$");
34
35#ifndef _DRM_LINUX_LIST_H_
36#define _DRM_LINUX_LIST_H_
37
38struct list_head {
39	struct list_head *next, *prev;
40};
41
42#define list_entry(ptr, type, member) container_of(ptr,type,member)
43
44static __inline__ void
45INIT_LIST_HEAD(struct list_head *head) {
46	(head)->next = head;
47	(head)->prev = head;
48}
49
50#define LIST_HEAD_INIT(name) { &(name), &(name) }
51
52#define DRM_LIST_HEAD(name) \
53	struct list_head name = LIST_HEAD_INIT(name)
54
55static __inline__ int
56list_empty(const struct list_head *head) {
57	return (head)->next == head;
58}
59
60static __inline__ void
61list_add(struct list_head *new, struct list_head *head) {
62        (head)->next->prev = new;
63        (new)->next = (head)->next;
64        (new)->prev = head;
65        (head)->next = new;
66}
67
68static __inline__ void
69list_add_tail(struct list_head *entry, struct list_head *head) {
70	(entry)->prev = (head)->prev;
71	(entry)->next = head;
72	(head)->prev->next = entry;
73	(head)->prev = entry;
74}
75
76static __inline__ void
77list_del(struct list_head *entry) {
78	(entry)->next->prev = (entry)->prev;
79	(entry)->prev->next = (entry)->next;
80}
81
82static inline void list_replace(struct list_head *old,
83				struct list_head *new)
84{
85	new->next = old->next;
86	new->next->prev = new;
87	new->prev = old->prev;
88	new->prev->next = new;
89}
90
91static inline void list_move(struct list_head *list, struct list_head *head)
92{
93	list_del(list);
94	list_add(list, head);
95}
96
97static inline void list_move_tail(struct list_head *list,
98    struct list_head *head)
99{
100	list_del(list);
101	list_add_tail(list, head);
102}
103
104static __inline__ void
105list_del_init(struct list_head *entry) {
106	(entry)->next->prev = (entry)->prev;
107	(entry)->prev->next = (entry)->next;
108	INIT_LIST_HEAD(entry);
109}
110
111#define list_for_each(entry, head)				\
112    for (entry = (head)->next; entry != head; entry = (entry)->next)
113
114#define list_for_each_prev(entry, head) \
115        for (entry = (head)->prev; entry != (head); \
116                entry = entry->prev)
117
118#define list_for_each_safe(entry, temp, head)			\
119    for (entry = (head)->next, temp = (entry)->next;		\
120	entry != head; 						\
121	entry = temp, temp = entry->next)
122
123#define list_for_each_entry(pos, head, member)				\
124    for (pos = list_entry((head)->next, __typeof(*pos), member);	\
125	&pos->member != (head);					 	\
126	pos = list_entry(pos->member.next, __typeof(*pos), member))
127
128#define list_for_each_entry_continue_reverse(pos, head, member)         \
129        for (pos = list_entry(pos->member.prev, __typeof(*pos), member);  \
130             &pos->member != (head);    				\
131             pos = list_entry(pos->member.prev, __typeof(*pos), member))
132
133/**
134 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
135 * @pos:        the type * to use as a loop cursor.
136 * @n:          another type * to use as temporary storage
137 * @head:       the head for your list.
138 * @member:     the name of the list_struct within the struct.
139 */
140#define list_for_each_entry_safe(pos, n, head, member)			\
141	for (pos = list_entry((head)->next, __typeof(*pos), member),	\
142	    n = list_entry(pos->member.next, __typeof(*pos), member);	\
143	    &pos->member != (head);					\
144	    pos = n, n = list_entry(n->member.next, __typeof(*n), member))
145
146#define list_for_each_entry_safe_from(pos, n, head, member) 			\
147	for (n = list_entry(pos->member.next, __typeof(*pos), member);		\
148	     &pos->member != (head);						\
149	     pos = n, n = list_entry(n->member.next, __typeof(*n), member))
150
151#define list_first_entry(ptr, type, member) \
152	list_entry((ptr)->next, type, member)
153
154
155static inline void
156__list_splice(const struct list_head *list, struct list_head *prev,
157    struct list_head *next)
158{
159	struct list_head *first = list->next;
160	struct list_head *last = list->prev;
161
162	first->prev = prev;
163	prev->next = first;
164
165	last->next = next;
166	next->prev = last;
167}
168
169static inline void
170list_splice(const struct list_head *list, struct list_head *head)
171{
172	if (list_empty(list))
173		return;
174
175	__list_splice(list, head, head->next);
176}
177
178void drm_list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv,
179    struct list_head *a, struct list_head *b));
180
181/* hlist, copied from sys/dev/ofed/linux/list.h */
182
183struct hlist_head {
184	struct hlist_node *first;
185};
186
187struct hlist_node {
188	struct hlist_node *next, **pprev;
189};
190
191#define	HLIST_HEAD_INIT { }
192#define	HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT
193#define	INIT_HLIST_HEAD(head) (head)->first = NULL
194#define	INIT_HLIST_NODE(node)						\
195do {									\
196	(node)->next = NULL;						\
197	(node)->pprev = NULL;						\
198} while (0)
199
200static inline int
201hlist_unhashed(const struct hlist_node *h)
202{
203
204	return !h->pprev;
205}
206
207static inline int
208hlist_empty(const struct hlist_head *h)
209{
210
211	return !h->first;
212}
213
214static inline void
215hlist_del(struct hlist_node *n)
216{
217
218        if (n->next)
219                n->next->pprev = n->pprev;
220        *n->pprev = n->next;
221}
222
223static inline void
224hlist_del_init(struct hlist_node *n)
225{
226
227	if (hlist_unhashed(n))
228		return;
229	hlist_del(n);
230	INIT_HLIST_NODE(n);
231}
232
233static inline void
234hlist_add_head(struct hlist_node *n, struct hlist_head *h)
235{
236
237	n->next = h->first;
238	if (h->first)
239		h->first->pprev = &n->next;
240	h->first = n;
241	n->pprev = &h->first;
242}
243
244static inline void
245hlist_add_before(struct hlist_node *n, struct hlist_node *next)
246{
247
248	n->pprev = next->pprev;
249	n->next = next;
250	next->pprev = &n->next;
251	*(n->pprev) = n;
252}
253
254static inline void
255hlist_add_after(struct hlist_node *n, struct hlist_node *next)
256{
257
258	next->next = n->next;
259	n->next = next;
260	next->pprev = &n->next;
261	if (next->next)
262		next->next->pprev = &next->next;
263}
264
265static inline void
266hlist_move_list(struct hlist_head *old, struct hlist_head *new)
267{
268
269	new->first = old->first;
270	if (new->first)
271		new->first->pprev = &new->first;
272	old->first = NULL;
273}
274
275#define	hlist_entry(ptr, type, field)	container_of(ptr, type, field)
276
277#define	hlist_for_each(p, head)						\
278	for (p = (head)->first; p; p = p->next)
279
280#define	hlist_for_each_safe(p, n, head)					\
281	for (p = (head)->first; p && ({ n = p->next; 1; }); p = n)
282
283#define	hlist_for_each_entry(tp, p, head, field)			\
284	for (p = (head)->first;						\
285	    p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next)
286
287#define hlist_for_each_entry_continue(tp, p, field)			\
288	for (p = (p)->next;						\
289	    p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next)
290
291#define	hlist_for_each_entry_from(tp, p, field)				\
292	for (; p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next)
293
294#define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
295	for (pos = (head)->first;					 \
296	     (pos) != 0 && ({ n = (pos)->next; \
297		 tpos = hlist_entry((pos), typeof(*(tpos)), member); 1;}); \
298	     pos = (n))
299
300#endif /* _DRM_LINUX_LIST_H_ */
301