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