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);
581f5207b7SJohn 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); \
631f5207b7SJohn 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 })
69*c85f09ccSJohn 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)); \
74*c85f09ccSJohn Levon } while (0)
75*c85f09ccSJohn Levon
76*c85f09ccSJohn Levon
77*c85f09ccSJohn Levon ////////////////////////////////////////////////////////////////////////
78*c85f09ccSJohn Levon // API
79*c85f09ccSJohn Levon #define PREPARE_PTR_LIST(head, ptr) \
80*c85f09ccSJohn Levon DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
81*c85f09ccSJohn Levon
82*c85f09ccSJohn Levon #define NEXT_PTR_LIST(ptr) \
83*c85f09ccSJohn Levon DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
84*c85f09ccSJohn Levon
85*c85f09ccSJohn Levon #define RESET_PTR_LIST(ptr) \
86*c85f09ccSJohn Levon DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
87*c85f09ccSJohn Levon
88*c85f09ccSJohn Levon #define FINISH_PTR_LIST(ptr) \
89*c85f09ccSJohn Levon DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
90*c85f09ccSJohn 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)
94*c85f09ccSJohn Levon
95*c85f09ccSJohn Levon
96*c85f09ccSJohn 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)
101*c85f09ccSJohn Levon
102*c85f09ccSJohn Levon #define END_FOR_EACH_PTR(ptr) \
103*c85f09ccSJohn Levon DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)
104*c85f09ccSJohn Levon
105*c85f09ccSJohn 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)
110*c85f09ccSJohn Levon
111*c85f09ccSJohn Levon #define END_FOR_EACH_PTR_REVERSE(ptr) \
112*c85f09ccSJohn Levon DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)
113*c85f09ccSJohn Levon
114*c85f09ccSJohn Levon #define THIS_ADDRESS(ptr) \
115*c85f09ccSJohn Levon DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
116*c85f09ccSJohn Levon
117*c85f09ccSJohn Levon #define INSERT_CURRENT(new, ptr) \
118*c85f09ccSJohn Levon DO_INSERT_CURRENT(new, __head##ptr, __list##ptr, __nr##ptr)
119*c85f09ccSJohn 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))
134*c85f09ccSJohn 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) \
1591f5207b7SJohn Levon
1601f5207b7SJohn Levon #define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY) \
1611f5207b7SJohn Levon do { \
162*c85f09ccSJohn Levon __typeof__(head) __head = (head); \
163*c85f09ccSJohn Levon __typeof__(head) __list = __head; \
1641f5207b7SJohn 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 } \
1691f5207b7SJohn Levon
1701f5207b7SJohn Levon #define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \
1711f5207b7SJohn Levon if (ptr) { \
172*c85f09ccSJohn Levon PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
1731f5207b7SJohn Levon }
1741f5207b7SJohn Levon
1751f5207b7SJohn Levon #define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY) \
1761f5207b7SJohn Levon do { \
1771f5207b7SJohn Levon __nr = 0; \
1781f5207b7SJohn Levon __list = __head; \
179*c85f09ccSJohn Levon if (__head) \
180*c85f09ccSJohn Levon PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
1811f5207b7SJohn Levon } while (0)
1821f5207b7SJohn Levon
1831f5207b7SJohn Levon #define DO_FINISH(ptr, __head, __list, __nr) \
184*c85f09ccSJohn Levon VRFY_PTR_LIST(__head); /* Sanity-check nesting */ \
1851f5207b7SJohn Levon } while (0)
1861f5207b7SJohn Levon
1871f5207b7SJohn 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; \
1931f5207b7SJohn Levon do { \
194*c85f09ccSJohn Levon for (__nr = 0; __nr < __list->nr; __nr++) { \
1951f5207b7SJohn Levon ptr = PTR_ENTRY(__list,__nr); \
1961f5207b7SJohn Levon if (__list->rm && !ptr) \
1971f5207b7SJohn Levon continue; \
1981f5207b7SJohn Levon
1991f5207b7SJohn Levon #define DO_END_FOR_EACH(ptr, __head, __list, __nr) \
2001f5207b7SJohn Levon } \
2011f5207b7SJohn Levon } while ((__list = __list->next) != __head); \
2021f5207b7SJohn Levon } while (0)
2031f5207b7SJohn Levon
2041f5207b7SJohn 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 { \
2111f5207b7SJohn Levon __list = __list->prev; \
2121f5207b7SJohn Levon __nr = __list->nr; \
2131f5207b7SJohn Levon while (--__nr >= 0) { \
2141f5207b7SJohn Levon ptr = PTR_ENTRY(__list,__nr); \
2151f5207b7SJohn Levon if (__list->rm && !ptr) \
2161f5207b7SJohn Levon continue; \
2171f5207b7SJohn Levon
2181f5207b7SJohn Levon
2191f5207b7SJohn Levon #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \
2201f5207b7SJohn Levon } \
2211f5207b7SJohn Levon } while (__list != __head); \
2221f5207b7SJohn Levon } while (0)
2231f5207b7SJohn Levon
2241f5207b7SJohn Levon #define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead, \
2251f5207b7SJohn Levon __newlist, __newnr, PTR_ENTRY) do { \
226*c85f09ccSJohn Levon __typeof__(__head) __newhead = __head; \
227*c85f09ccSJohn Levon __typeof__(__head) __newlist = __list; \
2281f5207b7SJohn Levon int __newnr = __nr; \
2291f5207b7SJohn Levon new = ptr; \
2301f5207b7SJohn Levon goto __inside##new; \
2311f5207b7SJohn Levon do { \
2321f5207b7SJohn Levon __newlist = __newlist->prev; \
2331f5207b7SJohn Levon __newnr = __newlist->nr; \
2341f5207b7SJohn Levon __inside##new: \
2351f5207b7SJohn Levon while (--__newnr >= 0) { \
2361f5207b7SJohn Levon new = PTR_ENTRY(__newlist,__newnr); \
2371f5207b7SJohn Levon
2381f5207b7SJohn Levon #define DO_THIS_ADDRESS(ptr, __head, __list, __nr) \
239*c85f09ccSJohn Levon (&__list->list[__nr])
2401f5207b7SJohn Levon
2411f5207b7SJohn Levon
2421f5207b7SJohn Levon extern void split_ptr_list_head(struct ptr_list *);
2431f5207b7SJohn 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); \
2481f5207b7SJohn Levon if (__nr >= __list->nr) { \
2491f5207b7SJohn Levon __nr -= __list->nr; \
2501f5207b7SJohn Levon __list = __list->next; \
251*c85f09ccSJohn Levon } \
252*c85f09ccSJohn Levon } \
2531f5207b7SJohn Levon __this = __list->list + __nr; \
2541f5207b7SJohn Levon __last = __list->list + __list->nr - 1; \
2551f5207b7SJohn Levon while (__last >= __this) { \
2561f5207b7SJohn Levon __last[1] = __last[0]; \
2571f5207b7SJohn Levon __last--; \
2581f5207b7SJohn Levon } \
2591f5207b7SJohn Levon *__this = (new); \
2601f5207b7SJohn Levon __list->nr++; \
2611f5207b7SJohn Levon } while (0)
2621f5207b7SJohn 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; \
2661f5207b7SJohn Levon while (__this < __last) { \
2671f5207b7SJohn Levon __this[0] = __this[1]; \
2681f5207b7SJohn Levon __this++; \
2691f5207b7SJohn Levon } \
2701f5207b7SJohn Levon *__this = (void *)0xf0f0f0f0; \
2711f5207b7SJohn Levon __list->nr--; __nr--; \
2721f5207b7SJohn Levon } while (0)
2731f5207b7SJohn Levon
2741f5207b7SJohn Levon
2751f5207b7SJohn Levon #define DO_MARK_CURRENT_DELETED(ptr, __list) do { \
2761f5207b7SJohn Levon REPLACE_CURRENT_PTR(ptr, NULL); \
2771f5207b7SJohn Levon __list->rm++; \
2781f5207b7SJohn Levon } while (0)
2791f5207b7SJohn 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