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 #else /* LISTDEBUG */
  60
  61 #define LISTMAGIC1 ((void *) 0xdadababa)
  62 #define LISTMAGIC2 ((void *) 0xd0d0b0b0)
  63 #define LISTMAGIC3 ((void *) 0x25254545)
  64
  65 #define list_del_enforce(x) \
  66 do { \
  67         /* Little hack: we put LISTMAGIC3 in prev */ \
  68         /* and the line number in next. Debugging purpose. */ \
  69         (x)->prev = LISTMAGIC3; \
  70         (x)->next = (void *) ((unsigned int) __LINE__); \
  71 } while (0)
  72
  73
  74 #define list_magic_error(where,what) INTERNAL("[%s] %s - bad list magic", where, #what)
  75
  76
  77 #define list_magic_set(x) \
  78 do { \
  79         (x).magic1 = LISTMAGIC1; \
  80         (x).magic2 = LISTMAGIC2; \
  81 } while (0)
  82
  83
  84 /** Backend for list_magic_check() and list_magic_chkbool(). */
  85 #define list_magic_correct(x) ((x).magic1 == LISTMAGIC1 && (x).magic2 == LISTMAGIC2)
  86
  87 #define list_magic_check(x, where) \
  88 do { \
  89         if (!list_magic_correct(*(x))) \
  90                 list_magic_error(where, x); \
  91 } while (0)
  92
  93 #define list_magic_chkbool(x, where) (list_magic_correct(x) || (list_magic_error(where, x), 1))
  94
  95
  96 struct list_head {
  97         void *magic1;
  98         void *next;
  99         void *prev;
 100         void *magic2;
 101 };
 102
 103 struct xlist_head {
 104         void *magic1;
 105         struct xlist_head *next;
 106         struct xlist_head *prev;
 107         void *magic2;
 108 };
 109
 110
 111 #define NULL_LIST_HEAD LISTMAGIC1, NULL, NULL, LISTMAGIC2
 112 #define D_LIST_HEAD(x) LISTMAGIC1, &x, &x, LISTMAGIC2
 113 #define LIST_HEAD(x) void *magic1; x *next; x *prev; void *magic2
 114 #define LIST_SET_MAGIC(x) list_magic_set(*(x))
 115
 116 #endif /* LISTDEBUG */
 117
 118 /** A list intended to contain elements of a specific type.  The
 119  * @a element_T parameter currently serves as documentation only;
 120  * the compiler does not check that it matches.  Doxyfile defines
 121  * this macro differently in order to get better collaboration
 122  * diagrams.  */
 123 #define LIST_OF(element_T) struct list_head
 124
 125 /** Define and initialize a list variable.  The @a element_T parameter
 126  * currently serves as documentation only; the compiler does not check
 127  * that it matches.  */
 128 #define INIT_LIST_OF(element_T, x) LIST_OF(element_T) x = { D_LIST_HEAD(x) }
 129
 130 #ifdef HAVE_TYPEOF
 131 #define list_typeof(x) typeof(x)
 132 #else
 133 #define list_typeof(x) struct xlist_head *
 134 #endif /* HAVE_TYPEOF */
 135
 136
 137 #define init_list(x) \
 138 do { \
 139         list_magic_set(x); \
 140         do_not_optimize_here_gcc_3_x(&(x)); /* antialiasing ;) */ \
 141         (x).next = (x).prev = &(x); \
 142         do_not_optimize_here_gcc_3_x(&(x)); \
 143 } while (0)
 144
 145
 146 #define list_empty(x) (list_magic_chkbool(x, "list_empty") && (x).next == &(x))
 147
 148 #define list_is_singleton(x) \
 149         (list_magic_chkbool(x, "list_is_singleton") && (x).next == (x).prev)
 150
 151 #define list_has_prev(l,p) \
 152         (list_magic_chkbool(l, "list_has_prev") && (p)->prev !=  (void *) &(l))
 153
 154 #define list_has_next(l,p) \
 155         (list_magic_chkbool(l, "list_has_next") && (p)->next !=  (void *) &(l))
 156
 157 #define del_from_list(x) \
 158 do { \
 159         list_magic_check(x, "del_from_list"); \
 160         do_not_optimize_here_gcc_2_7(x); \
 161         ((struct list_head *) (x)->next)->prev = (x)->prev; \
 162         ((struct list_head *) (x)->prev)->next = (x)->next; \
 163         list_del_enforce(x); \
 164         do_not_optimize_here_gcc_2_7(x); \
 165 } while (0)
 166
 167 #define add_at_pos(p,x) \
 168 do { \
 169         list_magic_check(p, "add_at_pos"); \
 170         list_magic_set(*(x)); \
 171         do_not_optimize_here_gcc_2_7(p); \
 172         (x)->next = (p)->next; \
 173         (x)->prev = (p); \
 174         (p)->next = (x); \
 175         (x)->next->prev = (x); \
 176         do_not_optimize_here_gcc_2_7(p); \
 177 } while (0)
 178
 179
 180 #define add_to_list(l,x) \
 181         add_at_pos((list_typeof(x)) &(l), (list_typeof(x)) (x))
 182
 183 #define add_to_list_end(l,x) \
 184         add_at_pos((list_typeof(x)) (l).prev, (list_typeof(x)) (x))
 185
 186 #define foreach(e,l) \
 187         for ((e) = (l).next; \
 188              (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
 189              (e) = (e)->next)
 190
 191 #define foreachback(e,l) \
 192         for ((e) = (l).prev; \
 193              (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
 194              (e) = (e)->prev)
 195
 196 #define foreachsafe(e, n, l) \
 197         for ((e) = (l).next, (n) = (e)->next; \
 198              (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
 199              (e) = (n), (n) = (e)->next)
 200
 201 #define foreachbacksafe(e, p, l) \
 202         for ((e) = (l).prev, (p) = (e)->prev; \
 203              (list_typeof(e)) (e) != (list_typeof(e)) &(l); \
 204              (e) = (p), (p) = (e)->prev)
 205
 206 #define free_list(l) \
 207 do { \
 208         struct xlist_head *head, *next; \
 209 \
 210         list_magic_check(&(l), "free_list"); \
 211         do_not_optimize_here_gcc_2_7(&l); \
 212         foreach (head, (l)) do_not_optimize_here_gcc_3_x(head); /* AA */ \
 213         foreachback (head, (l)) do_not_optimize_here_gcc_3_x(head); /* AA */ \
 214         foreachsafe (head, next, l) { \
 215                 del_from_list(head); \
 216                 mem_free(head); \
 217         } \
 218         do_not_optimize_here_gcc_2_7(&l); \
 219 } while (0)
 220
 221 static inline int
 222 list_size(struct list_head *list)
 223 {
 224         struct list_head *item;
 225         int size = 0;
 226
 227         foreach (item, *list)
 228                 size++;
 229
 230         return size;
 231 }
 232
 233 #define move_to_top_of_list(list, item) do { \
 234         if ((item) != (list).next) { \
 235                 del_from_list(item); \
 236                 add_to_list(list, item); \
 237         } \
 238 } while (0)
 239
 240
 241 #endif /* EL__UTIL_LISTS_H */