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                                         do {
 166
 167 #define DO_END_FOR_EACH(ptr, __head, __list, __nr)                                      \
 168                                         } while (0);                                    \
 169                                 } while (0);                                            \
 170                         }                                                               \
 171                 } while ((__list = __list->next) != __head);                            \
 172         }                                                                               \
 173 } while (0)
 174
 175 #define DO_FOR_EACH_REVERSE(head, ptr, __head, __list, __nr, PTR_ENTRY) do {            \
 176         struct ptr_list *__head = (struct ptr_list *) (head);                           \
 177         struct ptr_list *__list = __head;                                               \
 178         CHECK_TYPE(head,ptr);                                                           \
 179         if (__head) {                                                                   \
 180                 do { int __nr;                                                          \
 181                         __list = __list->prev;                                          \
 182                         __nr = __list->nr;                                              \
 183                         while (--__nr >= 0) {                                           \
 184                                 do {                                                    \
 185                                         ptr = PTR_ENTRY(__list,__nr);                   \
 186                                         do {
 187
 188
 189 #define DO_END_FOR_EACH_REVERSE(ptr, __head, __list, __nr)                              \
 190                                         } while (0);                                    \
 191                                 } while (0);                                            \
 192                         }                                                               \
 193                 } while (__list != __head);                                             \
 194         }                                                                               \
 195 } while (0)
 196
 197 #define DO_REVERSE(ptr, __head, __list, __nr, new, __newhead,                           \
 198                    __newlist, __newnr, PTR_ENTRY) do {                                  \
 199         struct ptr_list *__newhead = __head;                                            \
 200         struct ptr_list *__newlist = __list;                                            \
 201         int __newnr = __nr;                                                             \
 202         new = ptr;                                                                      \
 203         goto __inside##new;                                                             \
 204         if (1) {                                                                        \
 205                 do {                                                                    \
 206                         __newlist = __newlist->prev;                                    \
 207                         __newnr = __newlist->nr;                                        \
 208         __inside##new:                                                                  \
 209                         while (--__newnr >= 0) {                                        \
 210                                 do {                                                    \
 211                                         new = PTR_ENTRY(__newlist,__newnr);             \
 212                                         do {
 213
 214 #define RECURSE_PTR_REVERSE(ptr, new)                                                   \
 215         DO_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr,                            \
 216                    new, __head##new, __list##new, __nr##new, PTR_ENTRY)
 217
 218 #define DO_THIS_ADDRESS(ptr, __head, __list, __nr)                                      \
 219         ((__typeof__(&(ptr))) (__list->list + __nr))
 220
 221 #define FOR_EACH_PTR(head, ptr) \
 222         DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
 223
 224 #define END_FOR_EACH_PTR(ptr) \
 225         DO_END_FOR_EACH(ptr, __head##ptr, __list##ptr, __nr##ptr)
 226
 227 #define FOR_EACH_PTR_NOTAG(head, ptr) \
 228         DO_FOR_EACH(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
 229
 230 #define END_FOR_EACH_PTR_NOTAG(ptr) END_FOR_EACH_PTR(ptr)
 231
 232 #define FOR_EACH_PTR_REVERSE(head, ptr) \
 233         DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY)
 234
 235 #define END_FOR_EACH_PTR_REVERSE(ptr) \
 236         DO_END_FOR_EACH_REVERSE(ptr, __head##ptr, __list##ptr, __nr##ptr)
 237
 238 #define FOR_EACH_PTR_REVERSE_NOTAG(head, ptr) \
 239         DO_FOR_EACH_REVERSE(head, ptr, __head##ptr, __list##ptr, __nr##ptr, PTR_ENTRY_NOTAG)
 240
 241 #define END_FOR_EACH_PTR_REVERSE_NOTAG(ptr) END_FOR_EACH_PTR_REVERSE(ptr)
 242
 243 #define THIS_ADDRESS(ptr) \
 244         DO_THIS_ADDRESS(ptr, __head##ptr, __list##ptr, __nr##ptr)
 245
 246 extern void split_ptr_list_head(struct ptr_list *);
 247
 248 #define DO_SPLIT(ptr, __head, __list, __nr) do {                                        \
 249         split_ptr_list_head(__list);                                                    \
 250         if (__nr >= __list->nr) {                                                       \
 251                 __nr -= __list->nr;                                                     \
 252                 __list = __list->next;                                                  \
 253         };                                                                              \
 254 } while (0)
 255
 256 #define DO_INSERT_CURRENT(new, ptr, __head, __list, __nr) do {                          \
 257         void **__this, **__last;                                                        \
 258         if (__list->nr == LIST_NODE_NR)                                                 \
 259                 DO_SPLIT(ptr, __head, __list, __nr);                                    \
 260         __this = __list->list + __nr;                                                   \
 261         __last = __list->list + __list->nr - 1;                                         \
 262         while (__last >= __this) {                                                      \
 263                 __last[1] = __last[0];                                                  \
 264                 __last--;                                                               \
 265         }                                                                               \
 266         *__this = (new);                                                                \
 267         __list->nr++;                                                                   \
 268 } while (0)
 269
 270 #define INSERT_CURRENT(new, ptr) \
 271         DO_INSERT_CURRENT(new, ptr, __head##ptr, __list##ptr, __nr##ptr)
 272
 273 #define DO_DELETE_CURRENT(ptr, __head, __list, __nr) do {                               \
 274         void **__this = __list->list + __nr;                                            \
 275         void **__last = __list->list + __list->nr - 1;                                  \
 276         while (__this < __last) {                                                       \
 277                 __this[0] = __this[1];                                                  \
 278                 __this++;                                                               \
 279         }                                                                               \
 280         *__this = (void *)0xf0f0f0f0;                                                   \
 281         __list->nr--; __nr--;                                                           \
 282 } while (0)
 283
 284 #define DELETE_CURRENT_PTR(ptr) \
 285         DO_DELETE_CURRENT(ptr, __head##ptr, __list##ptr, __nr##ptr)
 286
 287 #define REPLACE_CURRENT_PTR(ptr, new_ptr)                                               \
 288         do { *THIS_ADDRESS(ptr) = (new_ptr); } while (0)
 289
 290 extern void pack_ptr_list(struct ptr_list **);
 291
 292 #define PACK_PTR_LIST(x) pack_ptr_list((struct ptr_list **)(x))
 293
 294 static inline void update_tag(void *p, unsigned long tag)
 295 {
 296         unsigned long *ptr = p;
 297         *ptr = tag | (~3UL & *ptr);
 298 }
 299
 300 static inline void *tag_ptr(void *ptr, unsigned long tag)
 301 {
 302         return (void *)(tag | (unsigned long)ptr);
 303 }
 304
 305 #define CURRENT_TAG(ptr) (3 & (unsigned long)*THIS_ADDRESS(ptr))
 306 #define TAG_CURRENT(ptr,val)    update_tag(THIS_ADDRESS(ptr),val)
 307
 308 #endif /* PTR_LIST_H */