src/basic/list.h

   1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
   2 #pragma once
   3
   4 /* The head of the linked list. Use this in the structure that shall
   5  * contain the head of the linked list */
   6 #define LIST_HEAD(t,name)                                               \
   7         t *name
   8
   9 /* The pointers in the linked list's items. Use this in the item structure */
  10 #define LIST_FIELDS(t,name)                                             \
  11         t *name##_next, *name##_prev
  12
  13 /* Initialize the list's head */
  14 #define LIST_HEAD_INIT(head)                                            \
  15         do {                                                            \
  16                 (head) = NULL;                                          \
  17         } while (false)
  18
  19 /* Initialize a list item */
  20 #define LIST_INIT(name,item)                                            \
  21         do {                                                            \
  22                 typeof(*(item)) *_item = (item);                        \
  23                 assert(_item);                                          \
  24                 _item->name##_prev = _item->name##_next = NULL;         \
  25         } while (false)
  26
  27 /* Prepend an item to the list */
  28 #define LIST_PREPEND(name,head,item)                                    \
  29         ({                                                              \
  30                 typeof(*(head)) **_head = &(head), *_item = (item);     \
  31                 assert(_item);                                          \
  32                 if ((_item->name##_next = *_head))                      \
  33                         _item->name##_next->name##_prev = _item;        \
  34                 _item->name##_prev = NULL;                              \
  35                 *_head = _item;                                         \
  36                 _item;                                                  \
  37         })
  38
  39 /* Append an item to the list */
  40 #define LIST_APPEND(name,head,item)                                     \
  41         ({                                                              \
  42                 typeof(*(head)) **_hhead = &(head), *_tail;             \
  43                 _tail = LIST_FIND_TAIL(name, *_hhead);                  \
  44                 LIST_INSERT_AFTER(name, *_hhead, _tail, item);          \
  45         })
  46
  47 /* Remove an item from the list */
  48 #define LIST_REMOVE(name,head,item)                                     \
  49         ({                                                              \
  50                 typeof(*(head)) **_head = &(head), *_item = (item);     \
  51                 assert(_item);                                          \
  52                 if (_item->name##_next)                                 \
  53                         _item->name##_next->name##_prev = _item->name##_prev; \
  54                 if (_item->name##_prev)                                 \
  55                         _item->name##_prev->name##_next = _item->name##_next; \
  56                 else {                                                  \
  57                         assert(*_head == _item);                        \
  58                         *_head = _item->name##_next;                    \
  59                 }                                                       \
  60                 _item->name##_next = _item->name##_prev = NULL;         \
  61                 _item;                                                  \
  62         })
  63
  64 /* Find the head of the list */
  65 #define LIST_FIND_HEAD(name,item)                                       \
  66         ({                                                              \
  67                 typeof(*(item)) *_item = (item);                        \
  68                 while (_item && _item->name##_prev)                     \
  69                         _item = _item->name##_prev;                     \
  70                 _item;                                                  \
  71         })
  72
  73 /* Find the tail of the list */
  74 #define LIST_FIND_TAIL(name,item)                                       \
  75         ({                                                              \
  76                 typeof(*(item)) *_item = (item);                        \
  77                 while (_item && _item->name##_next)                     \
  78                         _item = _item->name##_next;                     \
  79                 _item;                                                  \
  80         })
  81
  82 /* Insert an item after another one (a = where, b = what) */
  83 #define LIST_INSERT_AFTER(name,head,a,b)                                \
  84         ({                                                              \
  85                 typeof(*(head)) **_head = &(head), *_a = (a), *_b = (b); \
  86                 assert(_b);                                             \
  87                 if (!_a) {                                              \
  88                         if ((_b->name##_next = *_head))                 \
  89                                 _b->name##_next->name##_prev = _b;      \
  90                         _b->name##_prev = NULL;                         \
  91                         *_head = _b;                                    \
  92                 } else {                                                \
  93                         if ((_b->name##_next = _a->name##_next))        \
  94                                 _b->name##_next->name##_prev = _b;      \
  95                         _b->name##_prev = _a;                           \
  96                         _a->name##_next = _b;                           \
  97                 }                                                       \
  98                 _b;                                                     \
  99         })
 100
 101 /* Insert an item before another one (a = where, b = what) */
 102 #define LIST_INSERT_BEFORE(name,head,a,b)                               \
 103         ({                                                              \
 104                 typeof(*(head)) **_head = &(head), *_a = (a), *_b = (b); \
 105                 assert(_b);                                             \
 106                 if (!_a) {                                              \
 107                         if (!*_head) {                                  \
 108                                 _b->name##_next = NULL;                 \
 109                                 _b->name##_prev = NULL;                 \
 110                                 *_head = _b;                            \
 111                         } else {                                        \
 112                                 typeof(*(head)) *_tail = (head);        \
 113                                 while (_tail->name##_next)              \
 114                                         _tail = _tail->name##_next;     \
 115                                 _b->name##_next = NULL;                 \
 116                                 _b->name##_prev = _tail;                \
 117                                 _tail->name##_next = _b;                \
 118                         }                                               \
 119                 } else {                                                \
 120                         if ((_b->name##_prev = _a->name##_prev))        \
 121                                 _b->name##_prev->name##_next = _b;      \
 122                         else                                            \
 123                                 *_head = _b;                            \
 124                         _b->name##_next = _a;                           \
 125                         _a->name##_prev = _b;                           \
 126                 }                                                       \
 127                 _b;                                                     \
 128         })
 129
 130 #define LIST_JUST_US(name, item)                                        \
 131         ({                                                              \
 132                 typeof(*(item)) *_item = (item);                        \
 133                 !(_item)->name##_prev && !(_item)->name##_next;         \
 134         })
 135
 136 /* The type of the iterator 'i' is automatically determined by the type of 'head', and declared in the
 137  * loop. Hence, do not declare the same variable in the outer scope. Sometimes, we set 'head' through
 138  * hashmap_get(). In that case, you need to explicitly cast the result. */
 139 #define LIST_FOREACH_WITH_NEXT(name,i,n,head)                           \
 140         for (typeof(*(head)) *n, *i = (head); i && (n = i->name##_next, true); i = n)
 141
 142 #define LIST_FOREACH(name,i,head)                                       \
 143         LIST_FOREACH_WITH_NEXT(name, i, UNIQ_T(n, UNIQ), head)
 144
 145 #define _LIST_FOREACH_WITH_PREV(name,i,p,start)                         \
 146         for (typeof(*(start)) *p, *i = (start); i && (p = i->name##_prev, true); i = p)
 147
 148 #define LIST_FOREACH_BACKWARDS(name,i,start)                            \
 149         _LIST_FOREACH_WITH_PREV(name, i, UNIQ_T(p, UNIQ), start)
 150
 151 /* Iterate through all the members of the list p is included in, but skip over p */
 152 #define LIST_FOREACH_OTHERS(name,i,p)                                   \
 153         for (typeof(*(p)) *_p = (p), *i = ({                            \
 154                                 typeof(*_p) *_j = _p;                   \
 155                                 while (_j && _j->name##_prev)           \
 156                                         _j = _j->name##_prev;           \
 157                                 if (_j == _p)                           \
 158                                         _j = _p->name##_next;           \
 159                                 _j;                                     \
 160                         });                                             \
 161              i;                                                         \
 162              i = i->name##_next == _p ? _p->name##_next : i->name##_next)
 163
 164 /* Loop starting from p->next until p->prev. p can be adjusted meanwhile. */
 165 #define LIST_LOOP_BUT_ONE(name,i,head,p)                                \
 166         for (typeof(*(p)) *i = (p)->name##_next ? (p)->name##_next : (head); \
 167              i != (p);                                                  \
 168              i = i->name##_next ? i->name##_next : (head))
 169
 170 /* Join two lists tail to head: a->b, c->d to a->b->c->d and de-initialise second list */
 171 #define LIST_JOIN(name,a,b)                                             \
 172         ({                                                              \
 173                 assert(b);                                              \
 174                 if (!(a))                                               \
 175                         (a) = (b);                                      \
 176                 else {                                                  \
 177                         typeof(*(a)) *_head = (b), *_tail;              \
 178                         _tail = LIST_FIND_TAIL(name, (a));              \
 179                         _tail->name##_next = _head;                     \
 180                         _head->name##_prev = _tail;                     \
 181                 }                                                       \
 182                 (b) = NULL;                                             \
 183                 a;                                                      \
 184         })
 185
 186 #define LIST_POP(name, a)                                               \
 187         ({                                                              \
 188                 typeof(a)* _a = &(a);                                   \
 189                 typeof(a) _p = *_a;                                     \
 190                 if (_p)                                                 \
 191                         LIST_REMOVE(name, *_a, _p);                     \
 192                 _p;                                                     \
 193         })
 194
 195 #define LIST_CLEAR(name, head, free_func)       \
 196         _LIST_CLEAR(name, head, free_func, UNIQ_T(elem, UNIQ))
 197
 198 /* Clear the list, destroying each element with free_func */
 199 #define _LIST_CLEAR(name, head, free_func, elem)        \
 200         ({                                              \
 201                 typeof(head) elem;                      \
 202                 while ((elem = LIST_POP(name, head)))   \
 203                         free_func(elem);                \
 204                 head;                                   \
 205         })
 206
 207 /* Now include "macro.h", because we want our definition of assert() which the macros above use. We include
 208  * it down here instead of up top, since macro.h pulls in log.h which in turn needs our own definitions. */
 209 #include "macro.h"