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,            \
  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 */