aboutsummaryrefslogtreecommitdiffstats
path: root/ptrlist.h
blob: dae0906f63557bb4edc34605ac3970da44aaee0f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
#ifndef PTR_LIST_H
#define PTR_LIST_H

/*
 * Generic pointer list manipulation code. 
 *
 * (C) Copyright Linus Torvalds 2003-2005
 */

#define container(ptr, type, member) \
	(type *)((void *)(ptr) - offsetof(type, member))

/* Silly type-safety check ;) */
#define DECLARE_PTR_LIST(listname,type)	struct listname { type *list[1]; }
#define CHECK_TYPE(head,ptr)		(void)(&(ptr) == &(head)->list[0])
#define TYPEOF(head)			__typeof__(&(head)->list[0])
#define VRFY_PTR_LIST(head)		(void)(sizeof((head)->list[0]))

/*
 * The "unnecessary" statement expression is there to shut up a totally 
 * bogus gcc warning about unused expressions, brought on by the fact
 * that we cast the result to the proper type.
 */
#define MKTYPE(head,expr)		({ (TYPEOF(head))(expr); })

#define LIST_NODE_NR (29)

struct ptr_list {
	int nr;
	struct ptr_list *prev;
	struct ptr_list *next;
	void *list[LIST_NODE_NR];
};

#define ptr_list_empty(x) ((x) == NULL)

void * undo_ptr_list_last(struct ptr_list **head);
void * delete_ptr_list_last(struct ptr_list **head);
int delete_ptr_list_entry(struct ptr_list **, void *, int);
int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));

extern void **__add_ptr_list(struct ptr_list **, void *, unsigned long);
extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
extern void __free_ptr_list(struct ptr_list **);
extern int ptr_list_size(struct ptr_list *);
extern int linearize_ptr_list(struct ptr_list *, void **, int);

/*
 * Hey, who said that you can't do overloading in C?
 *
 * You just have to be creative, and use some gcc
 * extensions..
 */
#define add_ptr_list_tag(list,entry,tag) \
	MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), (entry), (tag))))
#define add_ptr_list_notag(list,entry)										\
	MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list),			\
								    (void *)((unsigned long)(entry) & ~3UL), 	\
								    (unsigned long)(entry) & 3)))
#define add_ptr_list(list,entry) \
	add_ptr_list_tag(list,entry,0)
#define free_ptr_list(list) \
	do { VRFY_PTR_LIST(*(list)); __free_ptr_list((struct ptr_list **)(list)); } while (0)

#define PTR_ENTRY_NOTAG(h,i)	((h)->list[i])
#define PTR_ENTRY(h,i)	(void *)(~3UL & (unsigned long)PTR_ENTRY_NOTAG(h,i))

static inline void *first_ptr_list(struct ptr_list *list)
{
	if (!list)
		return NULL;
	return PTR_ENTRY(list, 0);
}

static inline void *last_ptr_list(struct ptr_list *list)
{

	if (!list)
		return NULL;
	list = list->prev;
	return PTR_ENTRY(list, list->nr-1);
}

#define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY)				\
	do {										\
		struct ptr_list *__head = (struct ptr_list *) (head);			\
		struct ptr_list *__list = __head;					\
		int __nr = 0;								\
		CHECK_TYPE(head,ptr);							\
		if (__head) ptr = PTR_ENTRY(__head, 0);					\
		else ptr = NULL

#define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY)					\
		if (ptr) {								\
			if (++__nr < __list->nr) {					\
				ptr = PTR_ENTRY(__list,__nr);				\
			} else {							\
				__list = __list->next;					\
				ptr = NULL;						\
				if (__list != __head) {					\
					__nr = 0;					\
					ptr = PTR_ENTRY(__list,0);			\
				}							\
			}								\
		}

#define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY)					\
	do {										\
		__nr = 0;								\
		__list = __head;							\
		if (__head) ptr = PTR_ENTRY(__head, 0);					\
	} while (0)

#define DO_FINISH(ptr, __head, __list, __nr)						\
		(void)(__nr); /* Sanity-check nesting */				\
	} while (0)

#define PREPARE_PTR_LIST(head, ptr) \
	DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)

#define NEXT_PTR_LIST(ptr) \
	DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)

#define RESET_PTR_LIST(ptr) \
	DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)

#define FINISH_PTR_LIST(ptr) \
	DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)

#define DO_FOR_EACH(head, ptr, __head, __list, __nr, PTR_ENTRY) do {			\
	struct ptr_list *__head = (struct ptr_list *) (head);				\
	struct ptr_list *__list = __head;						\
	CHECK_TYPE(head,ptr);								\
	if (__head) {									\
		do { int __nr;								\
			for (__nr = 0; __nr < __list->nr; __nr++) {			\
				do {							\
					ptr = PTR_ENTRY(__list,__nr);			\
					do {

#define DO_END_FOR_EACH(ptr, __head, __list, __nr)					\
					} while (0);					\
				} while (0);						\
			}								\
		} while ((__list = __list->next) != __head);				\
	}										\
} while (0)

#define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do {		\
	struct ptr_list *__head = (struct ptr_list *) (head);				\
	struct ptr_list *__list = __head;						\
	CHECK_TYPE(head,ptr);								\
	if (__head) {									\
		do { int __nr;								\
			__list = __list->prev;						\
			__nr = __list->nr;						\
			while (--__nr >= 0) {						\
				do {							\
					ptr = PTR_ENTRY(__list,__nr);			\
					do {


#define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr)				\
					} while (0);					\
				} while (0);						\
			}								\
		} while (__list != __head);						\
	}										\
} while (0)

#define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead,				\
		   __newlist, __newnr, PTR_ENTRY) do { 					\
	struct ptr_list *__newhead = __head;						\
	struct ptr_list *__newlist = __list;						\
	int __newnr = __nr;								\
	new = ptr;									\
	goto __inside##new;								\
	if (1) {									\
		do {									\
			__newlist = __newlist->prev;					\
			__newnr = __newlist->nr;					\
	__inside##new:									\
			while (--__newnr >= 0) {					\
				do {							\
					new = PTR_ENTRY(__newlist,__newnr);		\
					do {

#define RECURSE_PTR_REVERSE(ptr, new)							\
	DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr,				\
		   new, __head##new, __list##new, __nr##new, PTR_ENTRY)

#define DO_THIS_ADDRESS(ptr, __head, __list, __nr)					\
	((__typeof__(&(ptr))) (__list->list + __nr))

#define FOR_EACH_PTR(head, ptr) \
	DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)

#define END_FOR_EACH_PTR(ptr) \
	DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)

#define FOR_EACH_PTR_NOTAG(head, ptr) \
	DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)

#define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)

#define FOR_EACH_PTR_REVERSE(head, ptr) \
	DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)

#define END_FOR_EACH_PTR_REVERSE(ptr) \
	DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)

#define FOR_EACH_PTR_REVERSE_NOTAG(head, ptr) \
	DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)

#define END_FOR_EACH_PTR_REVERSE_NOTAG(ptr) END_FOR_EACH_PTR_REVERSE(ptr)

#define THIS_ADDRESS(ptr) \
	DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)

extern void split_ptr_list_head(struct ptr_list *);

#define DO_SPLIT(ptr, __head, __list, __nr) do {					\
	split_ptr_list_head(__list);							\
	if (__nr >= __list->nr) {							\
		__nr -= __list->nr;							\
		__list = __list->next;							\
	};										\
} while (0)

#define DO_INSERT_CURRENT(new, ptr, __head, __list, __nr) do {				\
	void **__this, **__last;							\
	if (__list->nr == LIST_NODE_NR)							\
		DO_SPLIT(ptr, __head, __list, __nr);					\
	__this = __list->list + __nr;							\
	__last = __list->list + __list->nr - 1;						\
	while (__last >= __this) {							\
		__last[1] = __last[0];							\
		__last--;								\
	}										\
	*__this = (new);								\
	__list->nr++;									\
} while (0)

#define INSERT_CURRENT(new, ptr) \
	DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)

#define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do {				\
	void **__this = __list->list + __nr;						\
	void **__last = __list->list + __list->nr - 1;					\
	while (__this < __last) {							\
		__this[0] = __this[1];							\
		__this++;								\
	}										\
	*__this = (void *)0xf0f0f0f0;							\
	__list->nr--; __nr--;								\
} while (0)

#define DELETE_CURRENT_PTR(ptr) \
	DO_DELETE_CURRENT(ptr, __head##ptr, __list##ptr, __nr##ptr)

#define REPLACE_CURRENT_PTR(ptr, new_ptr)						\
	do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)

extern void pack_ptr_list(struct ptr_list **);

#define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x))

static inline void update_tag(void *p, unsigned long tag)
{
	unsigned long *ptr = p;
	*ptr = tag | (~3UL & *ptr);
}

static inline void *tag_ptr(void *ptr, unsigned long tag)
{
	return (void *)(tag | (unsigned long)ptr);
}

#define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))
#define TAG_CURRENT(ptr,val)	update_tag(THIS_ADDRESS(ptr),val)

#endif /* PTR_LIST_H */