]>
Commit | Line | Data |
---|---|---|
2fb975da TT |
1 | /* Linux kernel style list handling function |
2 | * | |
3 | * Written from scratch by Timo Teräs <timo.teras@iki.fi>, but modeled | |
4 | * after the linux kernel code. | |
5 | * | |
6 | * This file is free software: you may copy, redistribute and/or modify | |
7 | * it under the terms of the GNU General Public License as published by | |
8 | * the Free Software Foundation, either version 2 of the License, or | |
9 | * (at your option) any later version. | |
10 | */ | |
11 | ||
12 | #ifndef LIST_H | |
13 | #define LIST_H | |
14 | ||
15 | #ifndef NULL | |
16 | #define NULL 0L | |
17 | #endif | |
18 | ||
19 | #ifndef offsetof | |
20 | #ifdef __compiler_offsetof | |
21 | #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) | |
22 | #else | |
23 | #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) | |
24 | #endif | |
25 | #endif | |
26 | ||
27 | #ifndef container_of | |
996c9314 LB |
28 | #define container_of(ptr, type, member) \ |
29 | ({ \ | |
30 | const typeof(((type *)0)->member) *__mptr = (ptr); \ | |
31 | (type *)((char *)__mptr - offsetof(type, member)); \ | |
32 | }) | |
2fb975da TT |
33 | #endif |
34 | ||
35 | struct hlist_head { | |
36 | struct hlist_node *first; | |
37 | }; | |
38 | ||
39 | struct hlist_node { | |
40 | struct hlist_node *next; | |
41 | struct hlist_node **pprev; | |
42 | }; | |
43 | ||
44 | static inline int hlist_empty(const struct hlist_head *h) | |
45 | { | |
46 | return !h->first; | |
47 | } | |
48 | ||
49 | static inline int hlist_hashed(const struct hlist_node *n) | |
50 | { | |
51 | return n->pprev != NULL; | |
52 | } | |
53 | ||
54 | static inline void hlist_del(struct hlist_node *n) | |
55 | { | |
56 | struct hlist_node *next = n->next; | |
57 | struct hlist_node **pprev = n->pprev; | |
58 | ||
59 | *pprev = next; | |
60 | if (next) | |
61 | next->pprev = pprev; | |
62 | ||
63 | n->next = NULL; | |
64 | n->pprev = NULL; | |
65 | } | |
66 | ||
67 | static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) | |
68 | { | |
69 | struct hlist_node *first = h->first; | |
70 | ||
71 | n->next = first; | |
72 | if (first) | |
73 | first->pprev = &n->next; | |
74 | n->pprev = &h->first; | |
75 | h->first = n; | |
76 | } | |
77 | ||
996c9314 LB |
78 | static inline void hlist_add_after(struct hlist_node *n, |
79 | struct hlist_node *prev) | |
2fb975da TT |
80 | { |
81 | n->next = prev->next; | |
82 | n->pprev = &prev->next; | |
83 | prev->next = n; | |
84 | } | |
85 | ||
86 | static inline struct hlist_node **hlist_tail_ptr(struct hlist_head *h) | |
87 | { | |
88 | struct hlist_node *n = h->first; | |
89 | if (n == NULL) | |
90 | return &h->first; | |
91 | while (n->next != NULL) | |
92 | n = n->next; | |
93 | return &n->next; | |
94 | } | |
95 | ||
96 | #define hlist_entry(ptr, type, member) container_of(ptr,type,member) | |
97 | ||
996c9314 | 98 | #define hlist_for_each(pos, head) \ |
2fb975da TT |
99 | for (pos = (head)->first; pos; pos = pos->next) |
100 | ||
996c9314 LB |
101 | #define hlist_for_each_safe(pos, n, head) \ |
102 | for (pos = (head)->first; pos && ({ \ | |
103 | n = pos->next; \ | |
104 | 1; \ | |
105 | }); \ | |
106 | pos = n) | |
2fb975da | 107 | |
996c9314 LB |
108 | #define hlist_for_each_entry(tpos, pos, head, member) \ |
109 | for (pos = (head)->first; \ | |
110 | pos && ({ \ | |
111 | tpos = hlist_entry(pos, typeof(*tpos), member); \ | |
112 | 1; \ | |
113 | }); \ | |
2fb975da TT |
114 | pos = pos->next) |
115 | ||
996c9314 LB |
116 | #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \ |
117 | for (pos = (head)->first; \ | |
118 | pos && ({ \ | |
119 | n = pos->next; \ | |
120 | 1; \ | |
121 | }) \ | |
122 | && ({ \ | |
123 | tpos = hlist_entry(pos, typeof(*tpos), member); \ | |
124 | 1; \ | |
125 | }); \ | |
2fb975da TT |
126 | pos = n) |
127 | ||
128 | ||
129 | struct list_head { | |
130 | struct list_head *next, *prev; | |
131 | }; | |
132 | ||
133 | #define LIST_INITIALIZER(l) { .next = &l, .prev = &l } | |
134 | ||
135 | static inline void list_init(struct list_head *list) | |
136 | { | |
137 | list->next = list; | |
138 | list->prev = list; | |
139 | } | |
140 | ||
996c9314 | 141 | static inline void __list_add(struct list_head *new, struct list_head *prev, |
2fb975da TT |
142 | struct list_head *next) |
143 | { | |
144 | next->prev = new; | |
145 | new->next = next; | |
146 | new->prev = prev; | |
147 | prev->next = new; | |
148 | } | |
149 | ||
150 | static inline void list_add(struct list_head *new, struct list_head *head) | |
151 | { | |
152 | __list_add(new, head, head->next); | |
153 | } | |
154 | ||
155 | static inline void list_add_tail(struct list_head *new, struct list_head *head) | |
156 | { | |
157 | __list_add(new, head->prev, head); | |
158 | } | |
159 | ||
996c9314 | 160 | static inline void __list_del(struct list_head *prev, struct list_head *next) |
2fb975da TT |
161 | { |
162 | next->prev = prev; | |
163 | prev->next = next; | |
164 | } | |
165 | ||
166 | static inline void list_del(struct list_head *entry) | |
167 | { | |
168 | __list_del(entry->prev, entry->next); | |
169 | entry->next = NULL; | |
170 | entry->prev = NULL; | |
171 | } | |
172 | ||
173 | static inline int list_hashed(const struct list_head *n) | |
174 | { | |
175 | return n->next != n && n->next != NULL; | |
176 | } | |
177 | ||
178 | static inline int list_empty(const struct list_head *n) | |
179 | { | |
180 | return !list_hashed(n); | |
181 | } | |
182 | ||
996c9314 LB |
183 | #define list_next(ptr, type, member) \ |
184 | (list_hashed(ptr) ? container_of((ptr)->next, type, member) : NULL) | |
2fb975da TT |
185 | |
186 | #define list_entry(ptr, type, member) container_of(ptr,type,member) | |
187 | ||
996c9314 | 188 | #define list_for_each(pos, head) \ |
2fb975da TT |
189 | for (pos = (head)->next; pos != (head); pos = pos->next) |
190 | ||
996c9314 LB |
191 | #define list_for_each_safe(pos, n, head) \ |
192 | for (pos = (head)->next, n = pos->next; pos != (head); \ | |
193 | pos = n, n = pos->next) | |
2fb975da | 194 | |
996c9314 LB |
195 | #define list_for_each_entry(pos, head, member) \ |
196 | for (pos = list_entry((head)->next, typeof(*pos), member); \ | |
197 | &pos->member != (head); \ | |
2fb975da TT |
198 | pos = list_entry(pos->member.next, typeof(*pos), member)) |
199 | ||
996c9314 LB |
200 | #define list_for_each_entry_safe(pos, n, head, member) \ |
201 | for (pos = list_entry((head)->next, typeof(*pos), member), \ | |
202 | n = list_entry(pos->member.next, typeof(*pos), member); \ | |
203 | &pos->member != (head); \ | |
2fb975da TT |
204 | pos = n, n = list_entry(n->member.next, typeof(*n), member)) |
205 | ||
206 | #endif |