11f5207b7SJohn Levon #ifndef PTR_LIST_H
21f5207b7SJohn Levon #define PTR_LIST_H
31f5207b7SJohn Levon
41f5207b7SJohn Levon #include <stdlib.h>
5*c85f09ccSJohn Levon #include <stdbool.h>
61f5207b7SJohn Levon
71f5207b7SJohn Levon /*
81f5207b7SJohn Levon * Generic pointer list manipulation code.
91f5207b7SJohn Levon *
101f5207b7SJohn Levon * (C) Copyright Linus Torvalds 2003-2005
111f5207b7SJohn Levon */
121f5207b7SJohn Levon
131f5207b7SJohn Levon /* Silly type-safety check ;) */
141f5207b7SJohn Levon #define CHECK_TYPE(head,ptr) (void)(&(ptr) == &(head)->list[0])
151f5207b7SJohn Levon #define TYPEOF(head) __typeof__(&(head)->list[0])
161f5207b7SJohn Levon #define VRFY_PTR_LIST(head) (void)(sizeof((head)->list[0]))
171f5207b7SJohn Levon
18*c85f09ccSJohn Levon #define LIST_NODE_NR (13)
191f5207b7SJohn Levon
20*c85f09ccSJohn Levon #define DECLARE_PTR_LIST(listname, type) \
21*c85f09ccSJohn Levon struct listname { \
22*c85f09ccSJohn Levon int nr:8; \
23*c85f09ccSJohn Levon int rm:8; \
24*c85f09ccSJohn Levon struct listname *prev; \
25*c85f09ccSJohn Levon struct listname *next; \
26*c85f09ccSJohn Levon type *list[LIST_NODE_NR]; \
27*c85f09ccSJohn Levon }
281f5207b7SJohn Levon
29*c85f09ccSJohn Levon DECLARE_PTR_LIST(ptr_list, void);
301f5207b7SJohn Levon
311f5207b7SJohn Levon
321f5207b7SJohn Levon void * undo_ptr_list_last(struct ptr_list **head);
331f5207b7SJohn Levon void * delete_ptr_list_last(struct ptr_list **head);
341f5207b7SJohn Levon int delete_ptr_list_entry(struct ptr_list **, void *, int);
351f5207b7SJohn Levon int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
36*c85f09ccSJohn Levon bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry);
371f5207b7SJohn Levon extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));
381f5207b7SJohn Levon
391f5207b7SJohn Levon extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
40*c85f09ccSJohn Levon extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t);
411f5207b7SJohn Levon extern int ptr_list_size(struct ptr_list *);
42*c85f09ccSJohn Levon extern bool ptr_list_empty(const struct ptr_list *head);
43*c85f09ccSJohn Levon extern bool ptr_list_multiple(const struct ptr_list *head);
441f5207b7SJohn Levon extern int linearize_ptr_list(struct ptr_list *, void **, int);
45*c85f09ccSJohn Levon extern void *first_ptr_list(struct ptr_list *);
46*c85f09ccSJohn Levon extern void *last_ptr_list(struct ptr_list *);
47*c85f09ccSJohn Levon extern void *ptr_list_nth_entry(struct ptr_list *, unsigned int idx);
48*c85f09ccSJohn Levon extern void pack_ptr_list(struct ptr_list **);
491f5207b7SJohn Levon
501f5207b7SJohn Levon /*
511f5207b7SJohn Levon * Hey, who said that you can't do overloading in C?
521f5207b7SJohn Levon *
531f5207b7SJohn Levon * You just have to be creative, and use some gcc
541f5207b7SJohn Levon * extensions..
551f5207b7SJohn Levon */
56*c85f09ccSJohn Levon extern void **__add_ptr_list(struct ptr_list **, void *);
57*c85f09ccSJohn Levon extern void **__add_ptr_list_tag(struct ptr_list **, void *, unsigned long);
58*c85f09ccSJohn Levon
59*c85f09ccSJohn Levon #define add_ptr_list(list, ptr) ({ \
60*c85f09ccSJohn Levon struct ptr_list** head = (struct ptr_list**)(list); \
61*c85f09ccSJohn Levon CHECK_TYPE(*(list),ptr); \
62*c85f09ccSJohn Levon (__typeof__(&(ptr))) __add_ptr_list(head, ptr); \
63*c85f09ccSJohn Levon })
64*c85f09ccSJohn Levon #define add_ptr_list_tag(list, ptr, tag) ({ \
65*c85f09ccSJohn Levon struct ptr_list** head = (struct ptr_list**)(list); \
66*c85f09ccSJohn Levon CHECK_TYPE(*(list),ptr); \
67*c85f09ccSJohn Levon (__typeof__(&(ptr))) __add_ptr_list_tag(head, ptr, tag);\
68*c85f09ccSJohn Levon })
691f5207b7SJohn Levon
70*c85f09ccSJohn Levon extern void __free_ptr_list(struct ptr_list **);
71*c85f09ccSJohn Levon #define free_ptr_list(list) do { \
72*c85f09ccSJohn Levon VRFY_PTR_LIST(*(list)); \
73*c85f09ccSJohn Levon __free_ptr_list((struct ptr_list **)(list)); \
741f5207b7SJohn Levon } while (0)
751f5207b7SJohn Levon
761f5207b7SJohn Levon
77*c85f09ccSJohn Levon ////////////////////////////////////////////////////////////////////////
78*c85f09ccSJohn Levon // API
791f5207b7SJohn Levon #define PREPARE_PTR_LIST(head, ptr) \
80*c85f09ccSJohn Levon DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
811f5207b7SJohn Levon
821f5207b7SJohn Levon #define NEXT_PTR_LIST(ptr) \
83*c85f09ccSJohn Levon DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
841f5207b7SJohn Levon
851f5207b7SJohn Levon #define RESET_PTR_LIST(ptr) \
86*c85f09ccSJohn Levon DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
871f5207b7SJohn Levon
881f5207b7SJohn Levon #define FINISH_PTR_LIST(ptr) \
891f5207b7SJohn Levon DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
901f5207b7SJohn Levon
91*c85f09ccSJohn Levon #define RECURSE_PTR_REVERSE(ptr, new) \
92*c85f09ccSJohn Levon DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, \
93*c85f09ccSJohn Levon new, __head##new, __list##new, __nr##new, PTR_ENTRY_UNTAG)
941f5207b7SJohn Levon
951f5207b7SJohn Levon
961f5207b7SJohn Levon #define FOR_EACH_PTR(head, ptr) \
97*c85f09ccSJohn Levon DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
98*c85f09ccSJohn Levon
99*c85f09ccSJohn Levon #define FOR_EACH_PTR_TAG(head, ptr) \
100*c85f09ccSJohn Levon DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
1011f5207b7SJohn Levon
1021f5207b7SJohn Levon #define END_FOR_EACH_PTR(ptr) \
1031f5207b7SJohn Levon DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)
1041f5207b7SJohn Levon
1051f5207b7SJohn Levon #define FOR_EACH_PTR_REVERSE(head, ptr) \
106*c85f09ccSJohn Levon DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
107*c85f09ccSJohn Levon
108*c85f09ccSJohn Levon #define FOR_EACH_PTR_REVERSE_TAG(head, ptr) \
109*c85f09ccSJohn Levon DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
1101f5207b7SJohn Levon
1111f5207b7SJohn Levon #define END_FOR_EACH_PTR_REVERSE(ptr) \
1121f5207b7SJohn Levon DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)
1131f5207b7SJohn Levon
1141f5207b7SJohn Levon #define THIS_ADDRESS(ptr) \
1151f5207b7SJohn Levon DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
1161f5207b7SJohn Levon
117*c85f09ccSJohn Levon #define INSERT_CURRENT(new, ptr) \
118*c85f09ccSJohn Levon DO_INSERT_CURRENT(new, __head##ptr, __list##ptr, __nr##ptr)
1191f5207b7SJohn Levon
120*c85f09ccSJohn Levon #define DELETE_CURRENT_PTR(ptr) \
121*c85f09ccSJohn Levon DO_DELETE_CURRENT(__head##ptr, __list##ptr, __nr##ptr)
122*c85f09ccSJohn Levon
123*c85f09ccSJohn Levon #define REPLACE_CURRENT_PTR(ptr, new_ptr) \
124*c85f09ccSJohn Levon do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
125*c85f09ccSJohn Levon
126*c85f09ccSJohn Levon // This replace the current element by a null-pointer.
127*c85f09ccSJohn Levon // It's used when an element of the list must be removed
128*c85f09ccSJohn Levon // but the address of the other elements must not be changed.
129*c85f09ccSJohn Levon #define MARK_CURRENT_DELETED(ptr) \
130*c85f09ccSJohn Levon DO_MARK_CURRENT_DELETED(ptr, __list##ptr)
131*c85f09ccSJohn Levon
132*c85f09ccSJohn Levon #define PACK_PTR_LIST(x) \
133*c85f09ccSJohn Levon pack_ptr_list((struct ptr_list **)(x))
1341f5207b7SJohn Levon
135*c85f09ccSJohn Levon #define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))
136*c85f09ccSJohn Levon #define TAG_CURRENT(ptr,val) update_tag(THIS_ADDRESS(ptr),val)
137*c85f09ccSJohn Levon
138*c85f09ccSJohn Levon // backward compatibility for smatch
139*c85f09ccSJohn Levon #define FOR_EACH_PTR_NOTAG(list, ptr) FOR_EACH_PTR(list, ptr)
140*c85f09ccSJohn Levon #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
141*c85f09ccSJohn Levon
142*c85f09ccSJohn Levon ////////////////////////////////////////////////////////////////////////
143*c85f09ccSJohn Levon // Implementation
144*c85f09ccSJohn Levon #define PTR_UNTAG(p) ((void*)(~3UL & (unsigned long)(p)))
145*c85f09ccSJohn Levon #define PTR_ENTRY_NOTAG(h,i) ((h)->list[i])
146*c85f09ccSJohn Levon #define PTR_ENTRY_UNTAG(h,i) PTR_UNTAG((h)->list[i])
147*c85f09ccSJohn Levon
148*c85f09ccSJohn Levon
149*c85f09ccSJohn Levon #define PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \
150*c85f09ccSJohn Levon do { \
151*c85f09ccSJohn Levon if (__nr < __list->nr) { \
152*c85f09ccSJohn Levon ptr = PTR_ENTRY(__list,__nr); \
153*c85f09ccSJohn Levon __nr++; \
154*c85f09ccSJohn Levon break; \
155*c85f09ccSJohn Levon } \
156*c85f09ccSJohn Levon ptr = NULL; \
157*c85f09ccSJohn Levon __nr = 0; \
158*c85f09ccSJohn Levon } while ((__list = __list->next) != __head) \
159*c85f09ccSJohn Levon
160*c85f09ccSJohn Levon #define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY) \
161*c85f09ccSJohn Levon do { \
162*c85f09ccSJohn Levon __typeof__(head) __head = (head); \
163*c85f09ccSJohn Levon __typeof__(head) __list = __head; \
164*c85f09ccSJohn Levon int __nr = 0; \
165*c85f09ccSJohn Levon ptr = NULL; \
166*c85f09ccSJohn Levon if (__head) { \
167*c85f09ccSJohn Levon PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
168*c85f09ccSJohn Levon } \
169*c85f09ccSJohn Levon
170*c85f09ccSJohn Levon #define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \
171*c85f09ccSJohn Levon if (ptr) { \
172*c85f09ccSJohn Levon PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
173*c85f09ccSJohn Levon }
174*c85f09ccSJohn Levon
175*c85f09ccSJohn Levon #define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY) \
176*c85f09ccSJohn Levon do { \
177*c85f09ccSJohn Levon __nr = 0; \
178*c85f09ccSJohn Levon __list = __head; \
179*c85f09ccSJohn Levon if (__head) \
180*c85f09ccSJohn Levon PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
181*c85f09ccSJohn Levon } while (0)
182*c85f09ccSJohn Levon
183*c85f09ccSJohn Levon #define DO_FINISH(ptr, __head, __list, __nr) \
184*c85f09ccSJohn Levon VRFY_PTR_LIST(__head); /* Sanity-check nesting */ \
185*c85f09ccSJohn Levon } while (0)
186*c85f09ccSJohn Levon
187*c85f09ccSJohn Levon #define DO_FOR_EACH(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \
188*c85f09ccSJohn Levon __typeof__(head) __head = (head); \
189*c85f09ccSJohn Levon __typeof__(head) __list = __head; \
190*c85f09ccSJohn Levon int __nr; \
191*c85f09ccSJohn Levon if (!__head) \
192*c85f09ccSJohn Levon break; \
193*c85f09ccSJohn Levon do { \
194*c85f09ccSJohn Levon for (__nr = 0; __nr < __list->nr; __nr++) { \
195*c85f09ccSJohn Levon ptr = PTR_ENTRY(__list,__nr); \
196*c85f09ccSJohn Levon if (__list->rm && !ptr) \
197*c85f09ccSJohn Levon continue; \
198*c85f09ccSJohn Levon
199*c85f09ccSJohn Levon #define DO_END_FOR_EACH(ptr, __head, __list, __nr) \
200*c85f09ccSJohn Levon } \
201*c85f09ccSJohn Levon } while ((__list = __list->next) != __head); \
2021f5207b7SJohn Levon } while (0)
2031f5207b7SJohn Levon
204*c85f09ccSJohn Levon #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \
205*c85f09ccSJohn Levon __typeof__(head) __head = (head); \
206*c85f09ccSJohn Levon __typeof__(head) __list = __head; \
207*c85f09ccSJohn Levon int __nr; \
208*c85f09ccSJohn Levon if (!head) \
209*c85f09ccSJohn Levon break; \
210*c85f09ccSJohn Levon do { \
211*c85f09ccSJohn Levon __list = __list->prev; \
212*c85f09ccSJohn Levon __nr = __list->nr; \
213*c85f09ccSJohn Levon while (--__nr >= 0) { \
214*c85f09ccSJohn Levon ptr = PTR_ENTRY(__list,__nr); \
215*c85f09ccSJohn Levon if (__list->rm && !ptr) \
216*c85f09ccSJohn Levon continue; \
217*c85f09ccSJohn Levon
218*c85f09ccSJohn Levon
219*c85f09ccSJohn Levon #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \
220*c85f09ccSJohn Levon } \
221*c85f09ccSJohn Levon } while (__list != __head); \
2221f5207b7SJohn Levon } while (0)
2231f5207b7SJohn Levon
224*c85f09ccSJohn Levon #define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead, \
225*c85f09ccSJohn Levon __newlist, __newnr, PTR_ENTRY) do { \
226*c85f09ccSJohn Levon __typeof__(__head) __newhead = __head; \
227*c85f09ccSJohn Levon __typeof__(__head) __newlist = __list; \
228*c85f09ccSJohn Levon int __newnr = __nr; \
229*c85f09ccSJohn Levon new = ptr; \
230*c85f09ccSJohn Levon goto __inside##new; \
231*c85f09ccSJohn Levon do { \
232*c85f09ccSJohn Levon __newlist = __newlist->prev; \
233*c85f09ccSJohn Levon __newnr = __newlist->nr; \
234*c85f09ccSJohn Levon __inside##new: \
235*c85f09ccSJohn Levon while (--__newnr >= 0) { \
236*c85f09ccSJohn Levon new = PTR_ENTRY(__newlist,__newnr); \
2371f5207b7SJohn Levon
238*c85f09ccSJohn Levon #define DO_THIS_ADDRESS(ptr, __head, __list, __nr) \
239*c85f09ccSJohn Levon (&__list->list[__nr])
2401f5207b7SJohn Levon
2411f5207b7SJohn Levon
242*c85f09ccSJohn Levon extern void split_ptr_list_head(struct ptr_list *);
243*c85f09ccSJohn Levon
244*c85f09ccSJohn Levon #define DO_INSERT_CURRENT(new, __head, __list, __nr) do { \
245*c85f09ccSJohn Levon TYPEOF(__head) __this, __last; \
246*c85f09ccSJohn Levon if (__list->nr == LIST_NODE_NR) { \
247*c85f09ccSJohn Levon split_ptr_list_head((struct ptr_list*)__list); \
248*c85f09ccSJohn Levon if (__nr >= __list->nr) { \
249*c85f09ccSJohn Levon __nr -= __list->nr; \
250*c85f09ccSJohn Levon __list = __list->next; \
251*c85f09ccSJohn Levon } \
252*c85f09ccSJohn Levon } \
253*c85f09ccSJohn Levon __this = __list->list + __nr; \
254*c85f09ccSJohn Levon __last = __list->list + __list->nr - 1; \
255*c85f09ccSJohn Levon while (__last >= __this) { \
256*c85f09ccSJohn Levon __last[1] = __last[0]; \
257*c85f09ccSJohn Levon __last--; \
258*c85f09ccSJohn Levon } \
259*c85f09ccSJohn Levon *__this = (new); \
260*c85f09ccSJohn Levon __list->nr++; \
261*c85f09ccSJohn Levon } while (0)
262*c85f09ccSJohn Levon
263*c85f09ccSJohn Levon #define DO_DELETE_CURRENT(__head, __list, __nr) do { \
264*c85f09ccSJohn Levon TYPEOF(__head) __this = __list->list + __nr; \
265*c85f09ccSJohn Levon TYPEOF(__head) __last = __list->list + __list->nr - 1; \
266*c85f09ccSJohn Levon while (__this < __last) { \
267*c85f09ccSJohn Levon __this[0] = __this[1]; \
268*c85f09ccSJohn Levon __this++; \
269*c85f09ccSJohn Levon } \
270*c85f09ccSJohn Levon *__this = (void *)0xf0f0f0f0; \
271*c85f09ccSJohn Levon __list->nr--; __nr--; \
272*c85f09ccSJohn Levon } while (0)
2731f5207b7SJohn Levon
2741f5207b7SJohn Levon
275*c85f09ccSJohn Levon #define DO_MARK_CURRENT_DELETED(ptr, __list) do { \
276*c85f09ccSJohn Levon REPLACE_CURRENT_PTR(ptr, NULL); \
277*c85f09ccSJohn Levon __list->rm++; \
278*c85f09ccSJohn Levon } while (0)
279*c85f09ccSJohn Levon
2801f5207b7SJohn Levon
update_tag(void * p,unsigned long tag)2811f5207b7SJohn Levon static inline void update_tag(void *p, unsigned long tag)
2821f5207b7SJohn Levon {
2831f5207b7SJohn Levon unsigned long *ptr = p;
2841f5207b7SJohn Levon *ptr = tag | (~3UL & *ptr);
2851f5207b7SJohn Levon }
2861f5207b7SJohn Levon
tag_ptr(void * ptr,unsigned long tag)2871f5207b7SJohn Levon static inline void *tag_ptr(void *ptr, unsigned long tag)
2881f5207b7SJohn Levon {
2891f5207b7SJohn Levon return (void *)(tag | (unsigned long)ptr);
2901f5207b7SJohn Levon }
2911f5207b7SJohn Levon
2921f5207b7SJohn Levon #endif /* PTR_LIST_H */
293