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