ptrlist.h

   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 PTRLIST_TYPE(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 #define pop_ptr_list(l) ({                                              \
  71                 PTRLIST_TYPE(*(l)) ptr;                                 \
  72                 ptr = delete_ptr_list_last((struct ptr_list**)(l));     \
  73                 ptr;                                                    \
  74         })
  75
  76 extern void __free_ptr_list(struct ptr_list **);
  77 #define free_ptr_list(list)     do {                                    \
  78                 VRFY_PTR_LIST(*(list));                                 \
  79                 __free_ptr_list((struct ptr_list **)(list));            \
  80         } while (0)
  81
  82 #define ptr_list_nth(lst, nth) ({                                       \
  83                 struct ptr_list* head = (struct ptr_list*)(lst);        \
  84                 (PTRLIST_TYPE(lst)) ptr_list_nth_entry(head, nth);\
  85         })
  86
  87 #define ptr_list_to_array(list, array, size) ({                         \
  88                 struct ptr_list* head = (struct ptr_list*)(list);       \
  89                 CHECK_TYPE(list, *array);                               \
  90                 linearize_ptr_list(head, (void**)array, size);          \
  91         })
  92
  93 ////////////////////////////////////////////////////////////////////////
  94 // API
  95 #define PREPARE_PTR_LIST(head, ptr) \
  96         DO_PREPARE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
  97
  98 #define NEXT_PTR_LIST(ptr) \
  99         DO_NEXT(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
 100
 101 #define RESET_PTR_LIST(ptr) \
 102         DO_RESET(ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_UNTAG)
 103
 104 #define FINISH_PTR_LIST(ptr) \
 105         DO_FINISH(ptr, __head##ptr, __list##ptr, __nr##ptr)
 106
 107 #define RECURSE_PTR_REVERSE(ptr, new)                                   \
 108         DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##new, \
 109                    new, __head##new, __list##new, __nr##new, PTR_ENTRY_UNTAG)
 110
 111
 112 #define FOR_EACH_PTR(head, ptr) \
 113         DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __name##ptr, PTR_ENTRY_NOTAG)
 114
 115 #define FOR_EACH_PTR_TAG(head, ptr) \
 116         DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __name##ptr,  PTR_ENTRY_UNTAG)
 117
 118 #define END_FOR_EACH_PTR(ptr) \
 119         DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr, __name##ptr)
 120
 121 #define FOR_EACH_PTR_REVERSE(head, ptr) \
 122         DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##ptr,  PTR_ENTRY_NOTAG)
 123
 124 #define FOR_EACH_PTR_REVERSE_TAG(head, ptr) \
 125         DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##ptr, PTR_ENTRY_UNTAG)
 126
 127 #define END_FOR_EACH_PTR_REVERSE(ptr) \
 128         DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##ptr)
 129
 130 #define THIS_ADDRESS(ptr) \
 131         DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
 132
 133 #define INSERT_CURRENT(new, ptr) \
 134         DO_INSERT_CURRENT(new, __head##ptr, __list##ptr, __nr##ptr)
 135
 136 #define DELETE_CURRENT_PTR(ptr) \
 137         DO_DELETE_CURRENT(__head##ptr, __list##ptr, __nr##ptr)
 138
 139 #define REPLACE_CURRENT_PTR(ptr, new_ptr)                               \
 140         do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
 141
 142 // This replace the current element by a null-pointer.
 143 // It's used when an element of the list must be removed
 144 // but the address of the other elements must not be changed.
 145 #define MARK_CURRENT_DELETED(ptr) \
 146         DO_MARK_CURRENT_DELETED(ptr, __list##ptr)
 147
 148 #define PACK_PTR_LIST(x) \
 149         pack_ptr_list((struct ptr_list **)(x))
 150
 151 #define CURRENT_TAG(ptr)        (3 & (unsigned long)*THIS_ADDRESS(ptr))
 152 #define TAG_CURRENT(ptr,val)    update_tag(THIS_ADDRESS(ptr),val)
 153
 154 // backward compatibility for smatch
 155 #define FOR_EACH_PTR_NOTAG(list, ptr)   FOR_EACH_PTR(list, ptr)
 156 #define END_FOR_EACH_PTR_NOTAG(ptr)     END_FOR_EACH_PTR(ptr)
 157
 158 ////////////////////////////////////////////////////////////////////////
 159 // Implementation
 160 #define PTR_UNTAG(p)            ((void*)(~3UL & (unsigned long)(p)))
 161 #define PTR_ENTRY_NOTAG(h,i)    ((h)->list[i])
 162 #define PTR_ENTRY_UNTAG(h,i)    PTR_UNTAG((h)->list[i])
 163
 164
 165 #define PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY)                  \
 166         do {                                                            \
 167                 if (__nr < __list->nr) {                                \
 168                         ptr = PTR_ENTRY(__list,__nr);                   \
 169                         __nr++;                                         \
 170                         break;                                          \
 171                 }                                                       \
 172                 ptr = NULL;                                             \
 173                 __nr = 0;                                               \
 174         } while ((__list = __list->next) != __head)                     \
 175
 176 #define DO_PREPARE(head, ptr, __head, __list, __nr, PTR_ENTRY)          \
 177         do {                                                            \
 178                 __typeof__(head) __head = (head);                       \
 179                 __typeof__(head) __list = __head;                       \
 180                 int __nr = 0;                                           \
 181                 ptr = NULL;                                             \
 182                 if (__head) {                                           \
 183                         PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
 184                 }                                                       \
 185
 186 #define DO_NEXT(ptr, __head, __list, __nr, PTR_ENTRY)                   \
 187                 if (ptr) {                                              \
 188                         PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
 189                 }
 190
 191 #define DO_RESET(ptr, __head, __list, __nr, PTR_ENTRY)                  \
 192         do {                                                            \
 193                 __nr = 0;                                               \
 194                 __list = __head;                                        \
 195                 if (__head)                                             \
 196                         PTR_NEXT(ptr, __head, __list, __nr, PTR_ENTRY); \
 197         } while (0)
 198
 199 #define DO_FINISH(ptr, __head, __list, __nr)                            \
 200                 VRFY_PTR_LIST(__head); /* Sanity-check nesting */       \
 201         } while (0)
 202
 203 #define DO_FOR_EACH(head, ptr, __head, __list, __nr, __name, PTR_ENTRY) do {    \
 204         __typeof__(head) __head = (head);                               \
 205         __typeof__(head) __list = __head;                               \
 206         __typeof__(head) __name = __head;                               \
 207         int __nr;                                                       \
 208         if (!__head)                                                    \
 209                 break;                                                  \
 210         do {                                                            \
 211                 for (__nr = 0; __nr < __list->nr; __nr++) {             \
 212                         ptr = PTR_ENTRY(__list,__nr);                   \
 213                         if (__list->rm && !ptr)                         \
 214                                 continue;                               \
 215
 216 #define DO_END_FOR_EACH(ptr, __head, __list, __nr, __name)              \
 217                 }                                                       \
 218         } while ((__list = __list->next) != __head);                    \
 219         (void) __name;                                          \
 220 } while (0)
 221
 222 #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, __name, PTR_ENTRY) do { \
 223         __typeof__(head) __head = (head);                               \
 224         __typeof__(head) __list = __head;                               \
 225         __typeof__(head) __name = __head;                               \
 226         int __nr;                                                       \
 227         if (!head)                                                      \
 228                 break;                                                  \
 229         do {                                                            \
 230                 __list = __list->prev;                                  \
 231                 __nr = __list->nr;                                      \
 232                 while (--__nr >= 0) {                                   \
 233                         ptr = PTR_ENTRY(__list,__nr);                   \
 234                         if (__list->rm && !ptr)                         \
 235                                 continue;                               \
 236
 237
 238 #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr, __name)      \
 239                 }                                                       \
 240         } while (__list != __head);                                     \
 241         (void) __name;                                                  \
 242 } while (0)
 243
 244 #define DO_REVERSE(ptr, __head, __list, __nr, __name, new, __newhead,   \
 245                    __newlist, __newnr, PTR_ENTRY) do {                  \
 246         __typeof__(__head) __newhead = __head;                          \
 247         __typeof__(__head) __newlist = __list;                          \
 248         __typeof__(__head) __name = __list;                             \
 249         int __newnr = __nr;                                             \
 250         new = ptr;                                                      \
 251         goto __inside##new;                                             \
 252         do {                                                            \
 253                 __newlist = __newlist->prev;                            \
 254                 __newnr = __newlist->nr;                                \
 255         __inside##new:                                                  \
 256                 while (--__newnr >= 0) {                                \
 257                         new = PTR_ENTRY(__newlist,__newnr);             \
 258
 259 #define DO_THIS_ADDRESS(ptr, __head, __list, __nr)                      \
 260         (&__list->list[__nr])
 261
 262
 263 extern void split_ptr_list_head(struct ptr_list *);
 264
 265 #define DO_INSERT_CURRENT(new, __head, __list, __nr) do {               \
 266         PTRLIST_TYPE(__head) *__this, *__last;                          \
 267         if (__list->nr == LIST_NODE_NR) {                               \
 268                 split_ptr_list_head((struct ptr_list*)__list);          \
 269                 if (__nr >= __list->nr) {                               \
 270                         __nr -= __list->nr;                             \
 271                         __list = __list->next;                          \
 272                 }                                                       \
 273         }                                                               \
 274         __this = __list->list + __nr;                                   \
 275         __last = __list->list + __list->nr - 1;                         \
 276         while (__last >= __this) {                                      \
 277                 __last[1] = __last[0];                                  \
 278                 __last--;                                               \
 279         }                                                               \
 280         *__this = (new);                                                \
 281         __list->nr++;                                                   \
 282 } while (0)
 283
 284 #define DO_DELETE_CURRENT(__head, __list, __nr) do {                    \
 285         PTRLIST_TYPE(__head) *__this = __list->list + __nr;             \
 286         PTRLIST_TYPE(__head) *__last = __list->list + __list->nr - 1;   \
 287         while (__this < __last) {                                       \
 288                 __this[0] = __this[1];                                  \
 289                 __this++;                                               \
 290         }                                                               \
 291         *__this = (void *)0xf0f0f0f0;                                   \
 292         __list->nr--; __nr--;                                           \
 293 } while (0)
 294
 295
 296 #define DO_MARK_CURRENT_DELETED(ptr, __list) do {                       \
 297                 REPLACE_CURRENT_PTR(ptr, NULL);                         \
 298                 __list->rm++;                                           \
 299         } while (0)
 300
 301
 302 static inline void update_tag(void *p, unsigned long tag)
 303 {
 304         unsigned long *ptr = p;
 305         *ptr = tag | (~3UL & *ptr);
 306 }
 307
 308 static inline void *tag_ptr(void *ptr, unsigned long tag)
 309 {
 310         return (void *)(tag | (unsigned long)ptr);
 311 }
 312
 313 #endif /* PTR_LIST_H */