src/util/lists.h

   1 #ifndef EL__UTIL_LISTS_H
   2 #define EL__UTIL_LISTS_H
   3
   4 #include "util/error.h" /* do_not_optimize_here() */
   5
   6 /* BEWARE! You MAY NOT use ternary operator as parameter to there functions,
   7  * because they are likely to take & of the parameter. Worst of all, it will
   8  * work with gcc. But nowhere else (at least not w/ tcc). */
   9
  10 /* Note that this whole lists implementation code is severely broken. All of
  11  * it is a single huge violation of C aliasing rules, just accessing things
  12  * like we do here is totally prohibited and bound to generate segfaults in
  13  * proportion with rising optimization level and gcc version.
  14  *
  15  * Fixing this would be a nice and needed janitorial project. */
  16
  17 /* Lists debugging
  18  * Two unsigned int magic number will be put before and after the next and
  19  * prev pointers, these will be check on list operations.
  20  * Some pointers are set to specific values after action. */
  21 #ifdef CONFIG_DEBUG
  22 #define LISTDEBUG
  23 #endif
  24
  25
  26 /* Fix namespace clash with system headers (like FreeBSD's, all hail BSD!). */
  27 #undef LIST_HEAD
  28 #undef list_head
  29 #define list_head list_head_elinks
  30
  31
  32 #ifndef LISTDEBUG
  33
  34 #define list_del_enforce(x) /* better don't */
  35
  36 #define list_magic_error(where, what) /* no magic */
  37
  38 #define list_magic_set(x) /* no magic */
  39
  40 #define list_magic_correct(x) (1)
  41 #define list_magic_check(x, where) /* no magic */
  42 #define list_magic_chkbool(x, where) (1)
  43
  44 struct list_head {
  45         void *next;
  46         void *prev;
  47 };
  48
  49 struct xlist_head {
  50         struct xlist_head *next;
  51         struct xlist_head *prev;
  52 };
  53
  54 #define NULL_LIST_HEAD NULL, NULL
  55 #define D_LIST_HEAD(x) &x, &x
  56 #define LIST_HEAD(x) x *next; x *prev
  57 #define LIST_SET_MAGIC(x) list_magic_set(*(x))
  58
  59
  60 #else /* LISTDEBUG */
  61
  62 #define LISTMAGIC1 ((void *) 0xdadababa)
  63 #define LISTMAGIC2 ((void *) 0xd0d0b0b0)
  64 #define LISTMAGIC3 ((void *) 0x25254545)
  65
  66 #define list_del_enforce(x) \
  67 do { \
  68         /* Little hack: we put LISTMAGIC3 in prev */ \
  69         /* and the line number in next. Debugging purpose. */ \
  70         (x)->prev = LISTMAGIC3; \
  71         (x)->next = (void *) ((unsigned int) __LINE__); \
  72 } while (0)
  73
  74
  75 #define list_magic_error(where,what) INTERNAL("[%s] %s - bad list magic", where, #what)
  76
  77
  78 #define list_magic_set(x) \
  79 do { \
  80         (x).magic1 = LISTMAGIC1; \
  81         (x).magic2 = LISTMAGIC2; \
  82 } while (0)
  83
  84
  85 /* Backend for list_magic_check() and list_magic_chkbool(). */
  86 #define list_magic_correct(x) ((x).magic1 == LISTMAGIC1 && (x).magic2 == LISTMAGIC2)
  87
  88 #define list_magic_check(x, where) \
  89 do { \
  90         if (!list_magic_correct(*(x))) \
  91                 list_magic_error(where, x); \
  92 } while (0)
  93
  94 #define list_magic_chkbool(x, where) (list_magic_correct(x) || (list_magic_error(where, x), 1))
  95
  96
  97 struct list_head {
  98         void *magic1;
  99         void *next;
 100         void *prev;
 101         void *magic2;
 102 };
 103
 104 struct xlist_head {
 105         void *magic1;
 106         struct xlist_head *next;
 107         struct xlist_head *prev;
 108         void *magic2;
 109 };
 110
 111
 112 #define NULL_LIST_HEAD LISTMAGIC1, NULL, NULL, LISTMAGIC2
 113 #define D_LIST_HEAD(x) LISTMAGIC1, &x, &x, LISTMAGIC2
 114 #define LIST_HEAD(x) void *magic1; x *next; x *prev; void *magic2
 115 #define LIST_SET_MAGIC(x) list_magic_set(*(x))
 116
 117 #endif /* LISTDEBUG */
 118
 119 #define INIT_LIST_HEAD(x) struct list_head x = { D_LIST_HEAD(x) }
 120
 121 #ifdef HAVE_TYPEOF
 122 #define list_typeof(x) typeof(x)
 123 #else
 124 #define list_typeof(x) struct xlist_head *
 125 #endif /* HAVE_TYPEOF */
 126
 127
 128 #define init_list(x) \
 129 do { \
 130         list_magic_set(x); \
 131         do_not_optimize_here_gcc_3_x(&(x)); /* antialiasing ;) */ \
 132         (x).next = (x).prev = &(x); \
 133         do_not_optimize_here_gcc_3_x(&(x)); \
 134 } while (0)
 135
 136
 137 #define list_empty(x) (list_magic_chkbool(x, "list_empty") && (x).next == &(x))
 138
 139 #define list_is_singleton(x) \
 140         (list_magic_chkbool(x, "list_is_singleton") && (x).next == (x).prev)
 141
 142 #define list_has_prev(l,p) \
 143         (list_magic_chkbool(l, "list_has_prev") && (p)->prev !=  (void *) &(l))
 144
 145 #define list_has_next(l,p) \
 146         (list_magic_chkbool(l, "list_has_next") && (p)->next !=  (void *) &(l))
 147
 148 #define del_from_list(x) \
 149 do { \
 150         list_magic_check(x, "del_from_list"); \
 151         do_not_optimize_here_gcc_2_7(x); \
 152         ((struct list_head *) (x)->next)->prev = (x)->prev; \
 153         ((struct list_head *) (x)->prev)->next = (x)->next; \
 154         list_del_enforce(x); \
 155         do_not_optimize_here_gcc_2_7(x); \
 156 } while (0)
 157
 158 #define add_at_pos(p,x) \
 159 do { \
 160         list_magic_check(p, "add_at_pos"); \
 161         list_magic_set(*(x)); \
 162         do_not_optimize_here_gcc_2_7(p); \
 163         (x)->next = (p)->next; \
 164         (x)->prev = (p); \
 165         (p)->next = (x); \
 166         (x)->next->prev = (x); \
 167         do_not_optimize_here_gcc_2_7(p); \
 168 } while (0)
 169
 170
 171 #define add_to_list(l,x) \
 172         add_at_pos((list_typeof(x)) &(l), (list_typeof(x)) (x))
 173
 174 #define add_to_list_end(l,x) \
 175         add_at_pos((list_typeof(x)) (l).prev, (list_typeof(x)) (x))
 176
 177 #define foreach(e,l) \
 178         for ((e) = (l).next; \
 179              (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
 180              (e) = (e)->next)
 181
 182 #define foreachback(e,l) \
 183         for ((e) = (l).prev; \
 184              (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
 185              (e) = (e)->prev)
 186
 187 #define foreachsafe(e, n, l) \
 188         for ((e) = (l).next, (n) = (e)->next; \
 189              (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
 190              (e) = (n), (n) = (e)->next)
 191
 192 #define foreachbacksafe(e, p, l) \
 193         for ((e) = (l).prev, (p) = (e)->prev; \
 194              (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
 195              (e) = (p), (p) = (e)->prev)
 196
 197 #define free_list(l) \
 198 do { \
 199         struct xlist_head *head, *next; \
 200 \
 201         list_magic_check(&(l), "free_list"); \
 202         do_not_optimize_here_gcc_2_7(&l); \
 203         foreach (head, (l)) do_not_optimize_here_gcc_3_x(head); /* AA */ \
 204         foreachback (head, (l)) do_not_optimize_here_gcc_3_x(head); /* AA */ \
 205         foreachsafe (head, next, l) { \
 206                 del_from_list(head); \
 207                 mem_free(head); \
 208         } \
 209         do_not_optimize_here_gcc_2_7(&l); \
 210 } while (0)
 211
 212 static inline int
 213 list_size(struct list_head *list)
 214 {
 215         struct list_head *item;
 216         int size = 0;
 217
 218         foreach (item, *list)
 219                 size++;
 220
 221         return size;
 222 }
 223
 224 #define move_to_top_of_list(list, item) do { \
 225         if ((item) != (list).next) { \
 226                 del_from_list(item); \
 227                 add_to_list(list, item); \
 228         } \
 229 } while (0)
 230
 231
 232 #endif /* EL__UTIL_LISTS_H */