1 #ifndef PTR_LIST_H 2 #define PTR_LIST_H 3 4 #include <stdlib.h> 5 6 /* 7 * Generic pointer list manipulation code. 8 * 9 * (C) Copyright Linus Torvalds 2003-2005 10 */ 11 12 /* Silly type-safety check ;) */ 13 #define DECLARE_PTR_LIST(listname,type) struct listname { type *list[1]; } 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 /* 19 * The "unnecessary" statement expression is there to shut up a totally 20 * bogus gcc warning about unused expressions, brought on by the fact 21 * that we cast the result to the proper type. 22 */ 23 #define MKTYPE(head,expr) ({ (TYPEOF(head))(expr); }) 24 25 #define LIST_NODE_NR (29) 26 27 struct ptr_list { 28 int nr:8; 29 int rm:8; 30 struct ptr_list *prev; 31 struct ptr_list *next; 32 void *list[LIST_NODE_NR]; 33 }; 34 35 #define ptr_list_empty(x) ((x) == NULL) 36 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 *)); 42 43 extern void **__add_ptr_list(struct ptr_list **, void *, unsigned long); 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); 48 49 /* 50 * Hey, who said that you can't do overloading in C? 51 * 52 * You just have to be creative, and use some gcc 53 * extensions.. 54 */ 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_notag(list,entry) \ 58 MKTYPE(*(list), (CHECK_TYPE(*(list),(entry)),__add_ptr_list((struct ptr_list **)(list), \ 59 (void *)((unsigned long)(entry) & ~3UL), \ 60 (unsigned long)(entry) & 3))) 61 #define add_ptr_list(list,entry) \ 62 add_ptr_list_tag(list,entry,0) 63 #define free_ptr_list(list) \ 64 do { VRFY_PTR_LIST(*(list)); __free_ptr_list((struct ptr_list **)(list)); } while (0) 65 66 #define PTR_ENTRY_NOTAG(h,i) ((h)->list[i]) 67 #define PTR_ENTRY(h,i) (void *)(~3UL & (unsigned long)PTR_ENTRY_NOTAG(h,i)) 68 69 static inline void *first_ptr_list(struct ptr_list *list) 70 { 71 struct ptr_list *head = list; 72 73 if (!list) 74 return NULL; 75 76 while (list->nr == 0) { 77 list = list->next; 78 if (list == head) 79 return NULL; 80 } 81 return PTR_ENTRY(list, 0); 82 } 83 84 static inline void *last_ptr_list(struct ptr_list *list) 85 { 86 struct ptr_list *head = list; 87 88 if (!list) 89 return NULL; 90 list = list->prev; 91 while (list->nr == 0) { 92 if (list == head) 93 return NULL; 94 list = list->prev; 95 } 96 return PTR_ENTRY(list, list->nr-1); 97 } 98 99 #define PTR_DEREF(__head, idx, PTR_ENTRY) ({ \ 100 struct ptr_list *__list = __head; \ 101 while (__list && __list->nr == 0) { \ 102 __list = __list->next; \ 103 if (__list == __head) \ 104 __list = NULL; \ 105 } \ 106 __list ? PTR_ENTRY(__list, idx) : NULL; \ 107 }) 108 109 #define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY) \ 110 do { \ 111 struct ptr_list *__head = (struct ptr_list *) (head); \ 112 struct ptr_list *__list = __head; \ 113 int __nr = 0; \ 114 CHECK_TYPE(head,ptr); \ 115 ptr = PTR_DEREF(__head, 0, PTR_ENTRY); \ 116 117 #define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY) \ 118 if (ptr) { \ 119 if (++__nr < __list->nr) { \ 120 ptr = PTR_ENTRY(__list,__nr); \ 121 } else { \ 122 __list = __list->next; \ 123 ptr = NULL; \ 124 while (__list->nr == 0 && __list != __head) \ 125 __list = __list->next; \ 126 if (__list != __head) { \ 127 __nr = 0; \ 128 ptr = PTR_ENTRY(__list,0); \ 129 } \ 130 } \ 131 } 132 133 #define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY) \ 134 do { \ 135 __nr = 0; \ 136 __list = __head; \ 137 if (__head) ptr = PTR_DEREF(__head, 0, PTR_ENTRY); \ 138 } while (0) 139 140 #define DO_FINISH(ptr, __head, __list, __nr) \ 141 (void)(__nr); /* Sanity-check nesting */ \ 142 } while (0) 143 144 #define PREPARE_PTR_LIST(head, ptr) \ 145 DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY) 146 147 #define NEXT_PTR_LIST(ptr) \ 148 DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY) 149 150 #define RESET_PTR_LIST(ptr) \ 151 DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY) 152 153 #define FINISH_PTR_LIST(ptr) \ 154 DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr) 155 156 #define DO_FOR_EACH(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \ 157 struct ptr_list *__head = (struct ptr_list *) (head); \ 158 struct ptr_list *__list = __head; \ 159 CHECK_TYPE(head,ptr); \ 160 if (__head) { \ 161 do { int __nr; \ 162 for (__nr = 0; __nr < __list->nr; __nr++) { \ 163 do { \ 164 ptr = PTR_ENTRY(__list,__nr); \ 165 if (__list->rm && !ptr) \ 166 continue; \ 167 do { 168 169 #define DO_END_FOR_EACH(ptr, __head, __list, __nr) \ 170 } while (0); \ 171 } while (0); \ 172 } \ 173 } while ((__list = __list->next) != __head); \ 174 } \ 175 } while (0) 176 177 #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do { \ 178 struct ptr_list *__head = (struct ptr_list *) (head); \ 179 struct ptr_list *__list = __head; \ 180 CHECK_TYPE(head,ptr); \ 181 if (__head) { \ 182 do { int __nr; \ 183 __list = __list->prev; \ 184 __nr = __list->nr; \ 185 while (--__nr >= 0) { \ 186 do { \ 187 ptr = PTR_ENTRY(__list,__nr); \ 188 if (__list->rm && !ptr) \ 189 continue; \ 190 do { 191 192 193 #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr) \ 194 } while (0); \ 195 } while (0); \ 196 } \ 197 } while (__list != __head); \ 198 } \ 199 } while (0) 200 201 #define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead, \ 202 __newlist, __newnr, PTR_ENTRY) do { \ 203 struct ptr_list *__newhead = __head; \ 204 struct ptr_list *__newlist = __list; \ 205 int __newnr = __nr; \ 206 new = ptr; \ 207 goto __inside##new; \ 208 if (1) { \ 209 do { \ 210 __newlist = __newlist->prev; \ 211 __newnr = __newlist->nr; \ 212 __inside##new: \ 213 while (--__newnr >= 0) { \ 214 do { \ 215 new = PTR_ENTRY(__newlist,__newnr); \ 216 do { 217 218 #define RECURSE_PTR_REVERSE(ptr, new) \ 219 DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, \ 220 new, __head##new, __list##new, __nr##new, PTR_ENTRY) 221 222 #define DO_THIS_ADDRESS(ptr, __head, __list, __nr) \ 223 ((__typeof__(&(ptr))) (__list->list + __nr)) 224 225 #define FOR_EACH_PTR(head, ptr) \ 226 DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY) 227 228 #define END_FOR_EACH_PTR(ptr) \ 229 DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr) 230 231 #define FOR_EACH_PTR_NOTAG(head, ptr) \ 232 DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG) 233 234 #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr) 235 236 #define FOR_EACH_PTR_REVERSE(head, ptr) \ 237 DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY) 238 239 #define END_FOR_EACH_PTR_REVERSE(ptr) \ 240 DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr) 241 242 #define FOR_EACH_PTR_REVERSE_NOTAG(head, ptr) \ 243 DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG) 244 245 #define END_FOR_EACH_PTR_REVERSE_NOTAG(ptr) END_FOR_EACH_PTR_REVERSE(ptr) 246 247 #define THIS_ADDRESS(ptr) \ 248 DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr) 249 250 extern void split_ptr_list_head(struct ptr_list *); 251 252 #define DO_SPLIT(ptr, __head, __list, __nr) do { \ 253 split_ptr_list_head(__list); \ 254 if (__nr >= __list->nr) { \ 255 __nr -= __list->nr; \ 256 __list = __list->next; \ 257 }; \ 258 } while (0) 259 260 #define DO_INSERT_CURRENT(new, ptr, __head, __list, __nr) do { \ 261 void **__this, **__last; \ 262 if (__list->nr == LIST_NODE_NR) \ 263 DO_SPLIT(ptr, __head, __list, __nr); \ 264 __this = __list->list + __nr; \ 265 __last = __list->list + __list->nr - 1; \ 266 while (__last >= __this) { \ 267 __last[1] = __last[0]; \ 268 __last--; \ 269 } \ 270 *__this = (new); \ 271 __list->nr++; \ 272 } while (0) 273 274 #define INSERT_CURRENT(new, ptr) \ 275 DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr) 276 277 #define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do { \ 278 void **__this = __list->list + __nr; \ 279 void **__last = __list->list + __list->nr - 1; \ 280 while (__this < __last) { \ 281 __this[0] = __this[1]; \ 282 __this++; \ 283 } \ 284 *__this = (void *)0xf0f0f0f0; \ 285 __list->nr--; __nr--; \ 286 } while (0) 287 288 #define DELETE_CURRENT_PTR(ptr) \ 289 DO_DELETE_CURRENT(ptr, __head##ptr, __list##ptr, __nr##ptr) 290 291 #define REPLACE_CURRENT_PTR(ptr, new_ptr) \ 292 do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0) 293 294 #define DO_MARK_CURRENT_DELETED(ptr, __list) do { \ 295 REPLACE_CURRENT_PTR(ptr, NULL); \ 296 __list->rm++; \ 297 } while (0) 298 299 #define MARK_CURRENT_DELETED(ptr) \ 300 DO_MARK_CURRENT_DELETED(ptr, __list##ptr) 301 302 extern void pack_ptr_list(struct ptr_list **); 303 304 #define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x)) 305 306 static inline void update_tag(void *p, unsigned long tag) 307 { 308 unsigned long *ptr = p; 309 *ptr = tag | (~3UL & *ptr); 310 } 311 312 static inline void *tag_ptr(void *ptr, unsigned long tag) 313 { 314 return (void *)(tag | (unsigned long)ptr); 315 } 316 317 #define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr)) 318 #define TAG_CURRENT(ptr,val) update_tag(THIS_ADDRESS(ptr),val) 319 320 #endif /* PTR_LIST_H */ 321