src/basic/list.h

   1 #pragma once
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2010 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 /* The head of the linked list. Use this in the structure that shall
  23  * contain the head of the linked list */
  24 #define LIST_HEAD(t,name)                                               \
  25         t *name
  26
  27 /* The pointers in the linked list's items. Use this in the item structure */
  28 #define LIST_FIELDS(t,name)                                             \
  29         t *name##_next, *name##_prev
  30
  31 /* Initialize the list's head */
  32 #define LIST_HEAD_INIT(head)                                            \
  33         do {                                                            \
  34                 (head) = NULL; }                                        \
  35         while (false)
  36
  37 /* Initialize a list item */
  38 #define LIST_INIT(name,item)                                            \
  39         do {                                                            \
  40                 typeof(*(item)) *_item = (item);                        \
  41                 assert(_item);                                          \
  42                 _item->name##_prev = _item->name##_next = NULL;         \
  43         } while (false)
  44
  45 /* Prepend an item to the list */
  46 #define LIST_PREPEND(name,head,item)                                    \
  47         do {                                                            \
  48                 typeof(*(head)) **_head = &(head), *_item = (item);     \
  49                 assert(_item);                                          \
  50                 if ((_item->name##_next = *_head))                      \
  51                         _item->name##_next->name##_prev = _item;        \
  52                 _item->name##_prev = NULL;                              \
  53                 *_head = _item;                                         \
  54         } while (false)
  55
  56 /* Append an item to the list */
  57 #define LIST_APPEND(name,head,item)                                     \
  58         do {                                                            \
  59                 typeof(*(head)) *_tail;                                 \
  60                 LIST_FIND_TAIL(name,head,_tail);                        \
  61                 LIST_INSERT_AFTER(name,head,_tail,item);                \
  62         } while (false)
  63
  64 /* Remove an item from the list */
  65 #define LIST_REMOVE(name,head,item)                                     \
  66         do {                                                            \
  67                 typeof(*(head)) **_head = &(head), *_item = (item);     \
  68                 assert(_item);                                          \
  69                 if (_item->name##_next)                                 \
  70                         _item->name##_next->name##_prev = _item->name##_prev; \
  71                 if (_item->name##_prev)                                 \
  72                         _item->name##_prev->name##_next = _item->name##_next; \
  73                 else {                                                  \
  74                         assert(*_head == _item);                        \
  75                         *_head = _item->name##_next;                    \
  76                 }                                                       \
  77                 _item->name##_next = _item->name##_prev = NULL;         \
  78         } while (false)
  79
  80 /* Find the head of the list */
  81 #define LIST_FIND_HEAD(name,item,head)                                  \
  82         do {                                                            \
  83                 typeof(*(item)) *_item = (item);                        \
  84                 if (!_item)                                             \
  85                         (head) = NULL;                                  \
  86                 else {                                                  \
  87                         while (_item->name##_prev)                      \
  88                                 _item = _item->name##_prev;             \
  89                         (head) = _item;                                 \
  90                 }                                                       \
  91         } while (false)
  92
  93 /* Find the tail of the list */
  94 #define LIST_FIND_TAIL(name,item,tail)                                  \
  95         do {                                                            \
  96                 typeof(*(item)) *_item = (item);                        \
  97                 if (!_item)                                             \
  98                         (tail) = NULL;                                  \
  99                 else {                                                  \
 100                         while (_item->name##_next)                      \
 101                                 _item = _item->name##_next;             \
 102                         (tail) = _item;                                 \
 103                 }                                                       \
 104         } while (false)
 105
 106 /* Insert an item after another one (a = where, b = what) */
 107 #define LIST_INSERT_AFTER(name,head,a,b)                                \
 108         do {                                                            \
 109                 typeof(*(head)) **_head = &(head), *_a = (a), *_b = (b); \
 110                 assert(_b);                                             \
 111                 if (!_a) {                                              \
 112                         if ((_b->name##_next = *_head))                 \
 113                                 _b->name##_next->name##_prev = _b;      \
 114                         _b->name##_prev = NULL;                         \
 115                         *_head = _b;                                    \
 116                 } else {                                                \
 117                         if ((_b->name##_next = _a->name##_next))        \
 118                                 _b->name##_next->name##_prev = _b;      \
 119                         _b->name##_prev = _a;                           \
 120                         _a->name##_next = _b;                           \
 121                 }                                                       \
 122         } while (false)
 123
 124 /* Insert an item before another one (a = where, b = what) */
 125 #define LIST_INSERT_BEFORE(name,head,a,b)                               \
 126         do {                                                            \
 127                 typeof(*(head)) **_head = &(head), *_a = (a), *_b = (b); \
 128                 assert(_b);                                             \
 129                 if (!_a) {                                              \
 130                         if (!*_head) {                                  \
 131                                 _b->name##_next = NULL;                 \
 132                                 _b->name##_prev = NULL;                 \
 133                                 *_head = _b;                            \
 134                         } else {                                        \
 135                                 typeof(*(head)) *_tail = (head);        \
 136                                 while (_tail->name##_next)              \
 137                                         _tail = _tail->name##_next;     \
 138                                 _b->name##_next = NULL;                 \
 139                                 _b->name##_prev = _tail;                \
 140                                 _tail->name##_next = _b;                \
 141                         }                                               \
 142                 } else {                                                \
 143                         if ((_b->name##_prev = _a->name##_prev))        \
 144                                 _b->name##_prev->name##_next = _b;      \
 145                         else                                            \
 146                                 *_head = _b;                            \
 147                         _b->name##_next = _a;                           \
 148                         _a->name##_prev = _b;                           \
 149                 }                                                       \
 150         } while (false)
 151
 152 #define LIST_JUST_US(name,item)                                         \
 153         (!(item)->name##_prev && !(item)->name##_next)                  \
 154
 155 #define LIST_FOREACH(name,i,head)                                       \
 156         for ((i) = (head); (i); (i) = (i)->name##_next)
 157
 158 #define LIST_FOREACH_SAFE(name,i,n,head)                                \
 159         for ((i) = (head); (i) && (((n) = (i)->name##_next), 1); (i) = (n))
 160
 161 #define LIST_FOREACH_BEFORE(name,i,p)                                   \
 162         for ((i) = (p)->name##_prev; (i); (i) = (i)->name##_prev)
 163
 164 #define LIST_FOREACH_AFTER(name,i,p)                                    \
 165         for ((i) = (p)->name##_next; (i); (i) = (i)->name##_next)
 166
 167 /* Iterate through all the members of the list p is included in, but skip over p */
 168 #define LIST_FOREACH_OTHERS(name,i,p)                                   \
 169         for (({                                                         \
 170                 (i) = (p);                                              \
 171                 while ((i) && (i)->name##_prev)                         \
 172                         (i) = (i)->name##_prev;                         \
 173                 if ((i) == (p))                                         \
 174                         (i) = (p)->name##_next;                         \
 175              });                                                        \
 176              (i);                                                       \
 177              (i) = (i)->name##_next == (p) ? (p)->name##_next : (i)->name##_next)
 178
 179 /* Loop starting from p->next until p->prev.
 180    p can be adjusted meanwhile. */
 181 #define LIST_LOOP_BUT_ONE(name,i,head,p)                                \
 182         for ((i) = (p)->name##_next ? (p)->name##_next : (head);        \
 183              (i) != (p);                                                \
 184              (i) = (i)->name##_next ? (i)->name##_next : (head))