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 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, __rname##new, \
  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, __name##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, __name##ptr,  PTR_ENTRY_UNTAG)
 101
 102 #define END_FOR_EACH_PTR(ptr) \
 103         DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr, __name##ptr)
 104
 105 #define FOR_EACH_PTR_REVERSE(head, ptr) \
 106         DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, __rname##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, __rname##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, __rname##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, __name, PTR_ENTRY) do {    \
 188         __typeof__(head) __head = (head);                               \
 189         __typeof__(head) __list = __head;                               \
 190         __typeof__(head) __name = __head;                               \
 191         int __nr;                                                       \
 192         if (!__head)                                                    \
 193                 break;                                                  \
 194         do {                                                            \
 195                 for (__nr = 0; __nr < __list->nr; __nr++) {             \
 196                         ptr = PTR_ENTRY(__list,__nr);                   \
 197                         if (__list->rm && !ptr)                         \
 198                                 continue;                               \
 199
 200 #define DO_END_FOR_EACH(ptr, __head, __list, __nr, __name)              \
 201                 }                                                       \
 202         } while ((__list = __list->next) != __head);                    \
 203         (void) __name;                                          \
 204 } while (0)
 205
 206 #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, __name, PTR_ENTRY) do { \
 207         __typeof__(head) __head = (head);                               \
 208         __typeof__(head) __list = __head;                               \
 209         __typeof__(head) __name = __head;                               \
 210         int __nr;                                                       \
 211         if (!head)                                                      \
 212                 break;                                                  \
 213         do {                                                            \
 214                 __list = __list->prev;                                  \
 215                 __nr = __list->nr;                                      \
 216                 while (--__nr >= 0) {                                   \
 217                         ptr = PTR_ENTRY(__list,__nr);                   \
 218                         if (__list->rm && !ptr)                         \
 219                                 continue;                               \
 220
 221
 222 #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr, __name)      \
 223                 }                                                       \
 224         } while (__list != __head);                                     \
 225         (void) __name;                                                  \
 226 } while (0)
 227
 228 #define DO_REVERSE(ptr, __head, __list, __nr, __name, new, __newhead,   \
 229                    __newlist, __newnr, PTR_ENTRY) do {                  \
 230         __typeof__(__head) __newhead = __head;                          \
 231         __typeof__(__head) __newlist = __list;                          \
 232         __typeof__(__head) __name = __list;                             \
 233         int __newnr = __nr;                                             \
 234         new = ptr;                                                      \
 235         goto __inside##new;                                             \
 236         do {                                                            \
 237                 __newlist = __newlist->prev;                            \
 238                 __newnr = __newlist->nr;                                \
 239         __inside##new:                                                  \
 240                 while (--__newnr >= 0) {                                \
 241                         new = PTR_ENTRY(__newlist,__newnr);             \
 242
 243 #define DO_THIS_ADDRESS(ptr, __head, __list, __nr)                      \
 244         (&__list->list[__nr])
 245
 246
 247 extern void split_ptr_list_head(struct ptr_list *);
 248
 249 #define DO_INSERT_CURRENT(new, __head, __list, __nr) do {               \
 250         TYPEOF(__head) __this, __last;                                  \
 251         if (__list->nr == LIST_NODE_NR) {                               \
 252                 split_ptr_list_head((struct ptr_list*)__list);          \
 253                 if (__nr >= __list->nr) {                               \
 254                         __nr -= __list->nr;                             \
 255                         __list = __list->next;                          \
 256                 }                                                       \
 257         }                                                               \
 258         __this = __list->list + __nr;                                   \
 259         __last = __list->list + __list->nr - 1;                         \
 260         while (__last >= __this) {                                      \
 261                 __last[1] = __last[0];                                  \
 262                 __last--;                                               \
 263         }                                                               \
 264         *__this = (new);                                                \
 265         __list->nr++;                                                   \
 266 } while (0)
 267
 268 #define DO_DELETE_CURRENT(__head, __list, __nr) do {                    \
 269         TYPEOF(__head) __this = __list->list + __nr;                    \
 270         TYPEOF(__head) __last = __list->list + __list->nr - 1;          \
 271         while (__this < __last) {                                       \
 272                 __this[0] = __this[1];                                  \
 273                 __this++;                                               \
 274         }                                                               \
 275         *__this = (void *)0xf0f0f0f0;                                   \
 276         __list->nr--; __nr--;                                           \
 277 } while (0)
 278
 279
 280 #define DO_MARK_CURRENT_DELETED(ptr, __list) do {                       \
 281                 REPLACE_CURRENT_PTR(ptr, NULL);                         \
 282                 __list->rm++;                                           \
 283         } while (0)
 284
 285
 286 static inline void update_tag(void *p, unsigned long tag)
 287 {
 288         unsigned long *ptr = p;
 289         *ptr = tag | (~3UL & *ptr);
 290 }
 291
 292 static inline void *tag_ptr(void *ptr, unsigned long tag)
 293 {
 294         return (void *)(tag | (unsigned long)ptr);
 295 }
 296
 297 #endif /* PTR_LIST_H */