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
29DECLARE_PTR_LIST(ptr_list, void);
30
31
32void * undo_ptr_list_last(struct ptr_list **head);
33void * delete_ptr_list_last(struct ptr_list **head);
34int delete_ptr_list_entry(struct ptr_list **, void *, int);
35int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
36bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry);
37extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));
38
39extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
40extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t);
41extern int ptr_list_size(struct ptr_list *);
42extern bool ptr_list_empty(const struct ptr_list *head);
43extern bool ptr_list_multiple(const struct ptr_list *head);
44extern int linearize_ptr_list(struct ptr_list *, void **, int);
45extern void *first_ptr_list(struct ptr_list *);
46extern void *last_ptr_list(struct ptr_list *);
47extern void *ptr_list_nth_entry(struct ptr_list *, unsigned int idx);
48extern 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 */
56extern void **__add_ptr_list(struct ptr_list **, void *);
57extern 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
70extern 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
242extern 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
281static inline void update_tag(void *p, unsigned long tag)
282{
283	unsigned long *ptr = p;
284	*ptr = tag | (~3UL & *ptr);
285}
286
287static 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