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