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