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