xref: /illumos-gate/usr/src/tools/smatch/src/ptrlist.h (revision c85f09cc)
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