1 #ifndef PTR_LIST_H
2 #define PTR_LIST_H
3
4 #include <stdlib.h>
5 #include <stdbool.h>
6
7 /*
8 * Generic pointer list manipulation code.
9 *
10 * (C) Copyright Linus Torvalds 2003-2005
11 */
12
13 /* Silly type-safety check ;) */
14 #define CHECK_TYPE(head,ptr) (void)(&(ptr) == &(head)->list[0])
15 #define PTRLIST_TYPE(head) __typeof__((head)->list[0])
16 #define VRFY_PTR_LIST(head) (void)(sizeof((head)->list[0]))
17
18 #define LIST_NODE_NR (13)
19
20 #define DECLARE_PTR_LIST(listname, type) \
21 struct listname { \
22 int nr:8; \
23 int rm:8; \
24 struct listname *prev; \
25 struct listname *next; \
26 type *list[LIST_NODE_NR]; \
27 }
28
29 DECLARE_PTR_LIST(ptr_list, void);
30
31
32 void * undo_ptr_list_last(struct ptr_list **head);
33 void * delete_ptr_list_last(struct ptr_list **head);
34 int delete_ptr_list_entry(struct ptr_list **, void *, int);
35 int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
36 bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry);
37 extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));
38
39 extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
40 extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t);
41 extern int ptr_list_size(struct ptr_list *);
42 extern bool ptr_list_empty(const struct ptr_list *head);
43 extern bool ptr_list_multiple(const struct ptr_list *head);
44 extern int linearize_ptr_list(struct ptr_list *, void **, int);
45 extern void *first_ptr_list(struct ptr_list *);
46 extern void *last_ptr_list(struct ptr_list *);
47 extern void *ptr_list_nth_entry(struct ptr_list *, unsigned int idx);
48 extern void pack_ptr_list(struct ptr_list **);
49
50 /*
51 * Hey, who said that you can't do overloading in C?
52 *
53 * You just have to be creative, and use some gcc
54 * extensions..
55 */
56 extern void **__add_ptr_list(struct ptr_list **, void *);
57 extern void **__add_ptr_list_tag(struct ptr_list **, void *, unsigned long);
58
59 #define add_ptr_list(list, ptr) ({ \
60 struct ptr_list** head = (struct ptr_list**)(list); \
61 CHECK_TYPE(*(list),ptr); \
62 (__typeof__(&(ptr))) __add_ptr_list(head, ptr); \
63 })
64 #define add_ptr_list_tag(list, ptr, tag) ({ \
65 struct ptr_list** head = (struct ptr_list**)(list); \
66 CHECK_TYPE(*(list),ptr); \
67 (__typeof__(&(ptr))) __add_ptr_list_tag(head, ptr, tag);\
68 })
69
70 #define pop_ptr_list(l) ({ \
71 PTRLIST_TYPE(*(l)) ptr; \
72 ptr = delete_ptr_list_last((struct ptr_list**)(l)); \
73 ptr; \
74 })
75
76 extern void __free_ptr_list(struct ptr_list **);
77 #define free_ptr_list(list) do { \
78 VRFY_PTR_LIST(*(list)); \
79 __free_ptr_list((struct ptr_list **)(list)); \
80 } while (0)
81
82 #define ptr_list_nth(lst, nth) ({ \
83 struct ptr_list* head = (struct ptr_list*)(lst); \
84 (PTRLIST_TYPE(lst)) ptr_list_nth_entry(head, nth);\
85 })
86
87 #define ptr_list_to_array(list, array, size) ({ \
88 struct ptr_list* head = (struct ptr_list*)(list); \
89 CHECK_TYPE(list, *array); \
90 linearize_ptr_list(head, (void**)array, size); \
91 })
92
93 ////////////////////////////////////////////////////////////////////////
94 // API
95 #define PREPARE_PTR_LIST(head, ptr) \
96 DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
97
98 #define NEXT_PTR_LIST(ptr) \
99 DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
100
101 #define RESET_PTR_LIST(ptr) \
102 DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
103
104 #define FINISH_PTR_LIST(ptr) \
105 DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
106
107 #define RECURSE_PTR_REVERSE(ptr, new) \
108 DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##new, \
109 new, __head##new, __list##new, __nr##new, PTR_ENTRY_UNTAG)
110
111
112 #define FOR_EACH_PTR(head, ptr) \
113 DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __name##ptr, PTR_ENTRY_NOTAG)
114
115 #define FOR_EACH_PTR_TAG(head, ptr) \
116 DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __name##ptr, PTR_ENTRY_UNTAG)
117
118 #define END_FOR_EACH_PTR(ptr) \
119 DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr, __name##ptr)
120
121 #define FOR_EACH_PTR_REVERSE(head, ptr) \
122 DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##ptr, PTR_ENTRY_NOTAG)
123
124 #define FOR_EACH_PTR_REVERSE_TAG(head, ptr) \
125 DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##ptr, PTR_ENTRY_UNTAG)
126
127 #define END_FOR_EACH_PTR_REVERSE(ptr) \
128 DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##ptr)
129
130 #define THIS_ADDRESS(ptr) \
131 DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
132
133 #define INSERT_CURRENT(new, ptr) \
134 DO_INSERT_CURRENT(new, __head##ptr, __list##ptr, __nr##ptr)
135
136 #define DELETE_CURRENT_PTR(ptr) \
137 DO_DELETE_CURRENT(__head##ptr, __list##ptr, __nr##ptr)
138
139 #define REPLACE_CURRENT_PTR(ptr, new_ptr) \
140 do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
141
142 // This replace the current element by a null-pointer.
143 // It's used when an element of the list must be removed
144 // but the address of the other elements must not be changed.
145 #define MARK_CURRENT_DELETED(ptr) \
146 DO_MARK_CURRENT_DELETED(ptr, __list##ptr)
147
148 #define PACK_PTR_LIST(x) \
149 pack_ptr_list((struct ptr_list **)(x))
150
151 #define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))
152 #define TAG_CURRENT(ptr,val) update_tag(THIS_ADDRESS(ptr),val)
153
154 // backward compatibility for smatch
155 #define FOR_EACH_PTR_NOTAG(list, ptr) FOR_EACH_PTR(list, ptr)
156 #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
157
158 ////////////////////////////////////////////////////////////////////////
159 // Implementation
160 #define PTR_UNTAG(p) ((void*)(~3UL & (unsigned long)(p)))
161 #define PTR_ENTRY_NOTAG(h,i) ((h)->list[i])
162 #define PTR_ENTRY_UNTAG(h,i) PTR_UNTAG((h)->list[i])
163
164
165 #define PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \
166 do { \
167 if (__nr < __list->nr) { \
168 ptr = PTR_ENTRY(__list,__nr); \
169 __nr++; \
170 break; \
171 } \
172 ptr = NULL; \
173 __nr = 0; \
174 } while ((__list = __list->next) != __head) \
175
176 #define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY) \
177 do { \
178 __typeof__(head) __head = (head); \
179 __typeof__(head) __list = __head; \
180 int __nr = 0; \
181 ptr = NULL; \
182 if (__head) { \
183 PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
184 } \
185
186 #define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \
187 if (ptr) { \
188 PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
189 }
190
191 #define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY) \
192 do { \
193 __nr = 0; \
194 __list = __head; \
195 if (__head) \
196 PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
197 } while (0)
198
199 #define DO_FINISH(ptr, __head, __list, __nr) \
200 VRFY_PTR_LIST(__head); /* Sanity-check nesting */ \
201 } while (0)
202
203 #define DO_FOR_EACH(head, ptr, __head, __list, __nr, __name, PTR_ENTRY) do { \
204 __typeof__(head) __head = (head); \
205 __typeof__(head) __list = __head; \
206 __typeof__(head) __name = __head; \
207 int __nr; \
208 if (!__head) \
209 break; \
210 do { \
211 for (__nr = 0; __nr < __list->nr; __nr++) { \
212 ptr = PTR_ENTRY(__list,__nr); \
213 if (__list->rm && !ptr) \
214 continue; \
215
216 #define DO_END_FOR_EACH(ptr, __head, __list, __nr, __name) \
217 } \
218 } while ((__list = __list->next) != __head); \
219 (void) __name; \
220 } while (0)
221
222 #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, __name, PTR_ENTRY) do { \
223 __typeof__(head) __head = (head); \
224 __typeof__(head) __list = __head; \
225 __typeof__(head) __name = __head; \
226 int __nr; \
227 if (!head) \
228 break; \
229 do { \
230 __list = __list->prev; \
231 __nr = __list->nr; \
232 while (--__nr >= 0) { \
233 ptr = PTR_ENTRY(__list,__nr); \
234 if (__list->rm && !ptr) \
235 continue; \
236
237
238 #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr, __name) \
239 } \
240 } while (__list != __head); \
241 (void) __name; \
242 } while (0)
243
244 #define DO_REVERSE(ptr, __head, __list, __nr, __name, new, __newhead, \
245 __newlist, __newnr, PTR_ENTRY) do { \
246 __typeof__(__head) __newhead = __head; \
247 __typeof__(__head) __newlist = __list; \
248 __typeof__(__head) __name = __list; \
249 int __newnr = __nr; \
250 new = ptr; \
251 goto __inside##new; \
252 do { \
253 __newlist = __newlist->prev; \
254 __newnr = __newlist->nr; \
255 __inside##new: \
256 while (--__newnr >= 0) { \
257 new = PTR_ENTRY(__newlist,__newnr); \
258
259 #define DO_THIS_ADDRESS(ptr, __head, __list, __nr) \
260 (&__list->list[__nr])
261
262
263 extern void split_ptr_list_head(struct ptr_list *);
264
265 #define DO_INSERT_CURRENT(new, __head, __list, __nr) do { \
266 PTRLIST_TYPE(__head) *__this, *__last; \
267 if (__list->nr == LIST_NODE_NR) { \
268 split_ptr_list_head((struct ptr_list*)__list); \
269 if (__nr >= __list->nr) { \
270 __nr -= __list->nr; \
271 __list = __list->next; \
272 } \
273 } \
274 __this = __list->list + __nr; \
275 __last = __list->list + __list->nr - 1; \
276 while (__last >= __this) { \
277 __last[1] = __last[0]; \
278 __last--; \
279 } \
280 *__this = (new); \
281 __list->nr++; \
282 } while (0)
283
284 #define DO_DELETE_CURRENT(__head, __list, __nr) do { \
285 PTRLIST_TYPE(__head) *__this = __list->list + __nr; \
286 PTRLIST_TYPE(__head) *__last = __list->list + __list->nr - 1; \
287 while (__this < __last) { \
288 __this[0] = __this[1]; \
289 __this++; \
290 } \
291 *__this = (void *)0xf0f0f0f0; \
292 __list->nr--; __nr--; \
293 } while (0)
294
295
296 #define DO_MARK_CURRENT_DELETED(ptr, __list) do { \
297 REPLACE_CURRENT_PTR(ptr, NULL); \
298 __list->rm++; \
299 } while (0)
300
301
update_tag(void * p,unsigned long tag)302 static inline void update_tag(void *p, unsigned long tag)
303 {
304 unsigned long *ptr = p;
305 *ptr = tag | (~3UL & *ptr);
306 }
307
tag_ptr(void * ptr,unsigned long tag)308 static inline void *tag_ptr(void *ptr, unsigned long tag)
309 {
310 return (void *)(tag | (unsigned long)ptr);
311 }
312
313 #endif /* PTR_LIST_H */
314