src/basic/list.h

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