5 * Generic pointer list manipulation code.
7 * (C) Copyright Linus Torvalds 2003-2005
10 #define container(ptr, type, member) \
11 (type *)((void *)(ptr) - offsetof(type, member))
13 /* Silly type-safety check ;) */
14 #define DECLARE_PTR_LIST(listname,type) struct listname { type *list[1]; }
15 #define CHECK_TYPE(head,ptr) (void)(&(ptr) == &(head)->list[0])
16 #define TYPEOF(head) __typeof__(&(head)->list[0])
17 #define VRFY_PTR_LIST(head) (void)(sizeof((head)->list[0]))
20 * The "unnecessary" statement expression is there to shut up a totally
21 * bogus gcc warning about unused expressions, brought on by the fact
22 * that we cast the result to the proper type.
24 #define MKTYPE(head,expr) ({ (TYPEOF(head))(expr); })
26 #define LIST_NODE_NR (29)
30 struct ptr_list
*prev
;
31 struct ptr_list
*next
;
32 void *list
[LIST_NODE_NR
];
35 #define ptr_list_empty(x) ((x) == NULL)
37 void * undo_ptr_list_last(struct ptr_list
**head
);
38 void * delete_ptr_list_last(struct ptr_list
**head
);
39 int delete_ptr_list_entry(struct ptr_list
**, void *, int);
40 int replace_ptr_list_entry(struct ptr_list
**, void *old
, void *new, int);
41 extern void sort_list(struct ptr_list
**, int (*)(const void *, const void *));
43 extern void **__add_ptr_list(struct ptr_list
**, void *, unsigned long tag
);
44 extern void concat_ptr_list(struct ptr_list
*a
, struct ptr_list
**b
);
45 extern void __free_ptr_list(struct ptr_list
**);
46 extern int ptr_list_size(struct ptr_list
*);
47 extern int linearize_ptr_list(struct ptr_list
*, void **, int);
50 * Hey, who said that you can't do overloading in C?
52 * You just have to be creative, and use some gcc
55 #define add_ptr_list_tag(list,entry,tag) \
56 MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), (entry), (tag))))
57 #define add_ptr_list(list,entry) \
58 add_ptr_list_tag(list,entry,0)
59 #define free_ptr_list(list) \
60 do { VRFY_PTR_LIST(*(list)); __free_ptr_list((struct ptr_list **)(list)); } while (0)
62 #define PTR_ENTRY(h,i) (void *)(~3UL & (unsigned long)(h)->list[i])
64 static inline void *first_ptr_list(struct ptr_list
*list
)
68 return PTR_ENTRY(list
, 0);
71 static inline void *last_ptr_list(struct ptr_list
*list
)
77 return PTR_ENTRY(list
, list
->nr
-1);
80 #define DO_PREPARE(head, ptr, __head, __list, __nr) \
82 struct ptr_list *__head = (struct ptr_list *) (head); \
83 struct ptr_list *__list = __head; \
85 CHECK_TYPE(head,ptr); \
86 if (__head) ptr = PTR_ENTRY(__head, 0); \
89 #define DO_NEXT(ptr, __head, __list, __nr) \
91 if (++__nr < __list->nr) { \
92 ptr = PTR_ENTRY(__list,__nr); \
94 __list = __list->next; \
96 if (__list != __head) { \
98 ptr = PTR_ENTRY(__list,0); \
103 #define DO_RESET(ptr, __head, __list, __nr) \
107 if (__head) ptr = PTR_ENTRY(__head, 0); \
110 #define DO_FINISH(ptr, __head, __list, __nr) \
111 (void)(__nr); /* Sanity-check nesting */ \
114 #define PREPARE_PTR_LIST(head, ptr) \
115 DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr)
117 #define NEXT_PTR_LIST(ptr) \
118 DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr)
120 #define RESET_PTR_LIST(ptr) \
121 DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr)
123 #define FINISH_PTR_LIST(ptr) \
124 DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
126 #define DO_FOR_EACH(head, ptr, __head, __list, __nr) do { \
127 struct ptr_list *__head = (struct ptr_list *) (head); \
128 struct ptr_list *__list = __head; \
129 CHECK_TYPE(head,ptr); \
132 for (__nr = 0; __nr < __list->nr; __nr++) { \
134 ptr = PTR_ENTRY(__list,__nr); \
137 #define DO_END_FOR_EACH(ptr, __head, __list, __nr) \
141 } while ((__list = __list->next) != __head); \
145 #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr) do { \
146 struct ptr_list *__head = (struct ptr_list *) (head); \
147 struct ptr_list *__list = __head; \
148 CHECK_TYPE(head,ptr); \
151 __list = __list->prev; \
153 while (--__nr >= 0) { \
155 ptr = PTR_ENTRY(__list,__nr); \
159 #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \
163 } while (__list != __head); \
167 #define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead, __newlist, __newnr) do { \
168 struct ptr_list *__newhead = __head; \
169 struct ptr_list *__newlist = __list; \
170 int __newnr = __nr; \
172 goto __inside##new; \
175 __newlist = __newlist->prev; \
176 __newnr = __newlist->nr; \
178 while (--__newnr >= 0) { \
180 new = PTR_ENTRY(__newlist,__newnr); \
183 #define RECURSE_PTR_REVERSE(ptr, new) \
184 DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, \
185 new, __head##new, __list##new, __nr##new)
187 #define DO_THIS_ADDRESS(ptr, __head, __list, __nr) \
188 ((__typeof__(&(ptr))) (__list->list + __nr))
190 #define FOR_EACH_PTR(head, ptr) \
191 DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr)
193 #define END_FOR_EACH_PTR(ptr) \
194 DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)
196 #define FOR_EACH_PTR_REVERSE(head, ptr) \
197 DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr)
199 #define END_FOR_EACH_PTR_REVERSE(ptr) \
200 DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)
202 #define THIS_ADDRESS(ptr) \
203 DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
205 extern void split_ptr_list_head(struct ptr_list
*);
207 #define DO_SPLIT(ptr, __head, __list, __nr) do { \
208 split_ptr_list_head(__list); \
209 if (__nr >= __list->nr) { \
210 __nr -= __list->nr; \
211 __list = __list->next; \
215 #define DO_INSERT_CURRENT(new, ptr, __head, __list, __nr) do { \
216 void **__this, **__last; \
217 if (__list->nr == LIST_NODE_NR) \
218 DO_SPLIT(ptr, __head, __list, __nr); \
219 __this = __list->list + __nr; \
220 __last = __list->list + __list->nr - 1; \
221 while (__last >= __this) { \
222 __last[1] = __last[0]; \
229 #define INSERT_CURRENT(new, ptr) \
230 DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)
232 #define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do { \
233 void **__this = __list->list + __nr; \
234 void **__last = __list->list + __list->nr - 1; \
235 while (__this < __last) { \
236 __this[0] = __this[1]; \
239 *__this = (void *)0xf0f0f0f0; \
240 __list->nr--; __nr--; \
243 #define DELETE_CURRENT_PTR(ptr) \
244 DO_DELETE_CURRENT(ptr, __head##ptr, __list##ptr, __nr##ptr)
246 #define REPLACE_CURRENT_PTR(ptr, new_ptr) \
247 do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
249 extern void pack_ptr_list(struct ptr_list
**);
251 #define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x))
253 static inline void update_tag(void *p
, unsigned long tag
)
255 unsigned long *ptr
= p
;
256 *ptr
= tag
| (~3UL & *ptr
);
259 static inline void *tag_ptr(void *ptr
, unsigned long tag
)
261 return (void *)(tag
| (unsigned long)ptr
);
264 #define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))
265 #define TAG_CURRENT(ptr,val) update_tag(THIS_ADDRESS(ptr),val)
267 #endif /* PTR_LIST_H */