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