ptrlist.h

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