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