granicus.if.org Git - strace/blob - list.h

   1 /*
   2  * Some simple implementation of lists similar to the one used in the kernel.
   3  *
   4  * Copyright (c) 2016-2019 The strace developers.
   5  * All rights reserved.
   6  *
   7  * SPDX-License-Identifier: LGPL-2.1-or-later
   8  */
   9
  10 #ifndef STRACE_LIST_H
  11 # define STRACE_LIST_H
  12
  13 /*
  14  * struct list_item and related macros and functions provide an interface
  15  * for manipulating and iterating linked lists.  In order to have list
  16  * associated with its payload, struct list_item has to be embedded into
  17  * a structure type representing payload, and (optionally) an additional
  18  * struct list_item should be added somewhere as a starting point for list
  19  * iteration (creating a list with a designated head). A situation where
  20  * no designated head exists, and each embedded struct list_head is considered
  21  * a head (i.e. starting point for list iteration), is also possible.
  22  *
  23  * List head has to be initialised with list_init() call. Statically allocated
  24  * list heads can also be defined with an EMPTY_LIST() macro.
  25  *
  26  * In order to get a pointer to list item from a struct list_item, list_elem
  27  * macro is used.
  28  *
  29  * When a designated head is used, list_head() and list_tail() can be used
  30  * for getting pointer to the first and the last list item, respectively.
  31  *
  32  * list_next() and list_prev() macros can be used for obtaining pointers
  33  * to the next and the previous items in the list, respectively.  Note that
  34  * they do not perform additional checks for the validity of these pointers,
  35  * so they have to be guarded with respective list_head/list_tail checks in case
  36  * of lists with designated heads (where the list's head is not embedded withing
  37  * a list item.
  38  *
  39  * list_{insert,append,remove,remove_tail,remove_head,replace} provide some
  40  * basic means of list manipulation.
  41  *
  42  * list_foreach() and list_foreach_safe() are wrapper macros for simplifying
  43  * iteration over a list, with the latter having an additional argument
  44  * for storing temporary pointer, thus allowing list manipulations during
  45  * its iteration.
  46  *
  47  * A simple example:
  48  *
  49  *     struct my_struct {
  50  *             int a;
  51  *             struct list_item l1;
  52  *             struct list_item l2;
  53  *     };
  54  *
  55  *     EMPTY_LIST(list_1);              <--- Defining a designated head for list
  56  *
  57  *     struct my_struct *item =
  58  *             calloc(1, sizeof(*item));
  59  *     list_init(&item->l2);            <--- Initialising structure field that
  60  *                                           is used for lists without designated
  61  *                                           head.
  62  *     list_insert(&list_1, &item->l1); <--- Inserting an item into the list
  63  *
  64  *     item = calloc(1, sizeof(*item));
  65  *     list_init(&item->l2);
  66  *
  67  *     list_append(&(list_head(list_1, struct my_struct, l1)->l2), &item->l2);
  68  *
  69  *     struct my_struct *cur = item;    <--- Iteration over a headless list
  70  *     do {
  71  *             printf("%d\n", cur->a);
  72  *     } while ((cur = list_next(&cur, l2)) != item);
  73  *
  74  *     struct my_struct *i;
  75  *     list_foreach(i, list_1, l1) {    <--- Iteration over list_1 without list
  76  *             printf("%d\n", i->a);         modification
  77  *     }
  78  *
  79  *     struct my_struct *tmp;           <--- Iteration with modification
  80  *     list_foreach_safe(i, list_1, l1, tmp) {
  81  *             list_remove(&i->l1);
  82  *             free(i);
  83  *     }
  84  *
  85  * See also:
  86  *     "Linux kernel design patterns - part 2", section "Linked Lists"
  87  *     https://lwn.net/Articles/336255/
  88  */
  89
  90 # include "macros.h"
  91
  92 struct list_item {
  93         struct list_item *prev;
  94         struct list_item *next;
  95 };
  96
  97 /**
  98  * Define an empty list head.
  99  *
 100  * @param l_ List head variable name.
 101  */
 102 # define EMPTY_LIST(l_) struct list_item l_ = { &l_, &l_ }
 103
 104 /** Initialise an empty list. */
 105 static inline void
 106 list_init(struct list_item *l)
 107 {
 108         l->prev = l;
 109         l->next = l;
 110 }
 111
 112 /** Check whether list is empty. */
 113 static inline bool
 114 list_is_empty(const struct list_item *l)
 115 {
 116         return ((l->next == l) && (l->prev == l))
 117                 /*
 118                  * XXX This could be the case when struct list_item hasn't been
 119                  *     initialised at all; we should probably also call some
 120                  *     errror_func_msg() in that case, as it looks like sloppy
 121                  *     programming.
 122                  */
 123                 || (!l->next && !l->prev);
 124 }
 125
 126 /**
 127  * Convert a pointer to a struct list_item to a pointer to a list item.
 128  *
 129  * @param var   Pointer to struct list_item.
 130  * @param type  Type of the list's item.
 131  * @param field Name of the field that holds the respective struct list_item.
 132  */
 133 # define list_elem(var, type, field) containerof((var), type, field)
 134
 135 /**
 136  * Get the first element in a list.
 137  *
 138  * @param head  Pointer to the list's head.
 139  * @param type  Type of the list's item.
 140  * @param field Name of the field that holds the respective struct list_item.
 141  */
 142 # define list_head(head, type, field) \
 143         (list_is_empty(head) ? NULL : list_elem((head)->next, type, field))
 144 /**
 145  * Get the last element in a list.
 146  *
 147  * @param head  Pointer to the list's head.
 148  * @param type  Type of the list's item.
 149  * @param field Name of the field that holds the respective struct list_item.
 150  */
 151 # define list_tail(head, type, field) \
 152         (list_is_empty(head) ? NULL : list_elem((head)->prev, type, field))
 153
 154 /**
 155  * Get the next element in a list.
 156  *
 157  * @param var   Pointer to a list item.
 158  * @param field Name of the field that holds the respective struct list_item.
 159  */
 160 # define list_next(var, field) \
 161         list_elem((var)->field.next, typeof(*(var)), field)
 162 /**
 163  * Get the previous element in a list.
 164  *
 165  * @param var   Pointer to a list item.
 166  * @param field Name of the field that holds the respective struct list_item.
 167  */
 168 # define list_prev(var, field) \
 169         list_elem((var)->field.prev, typeof(*(var)), field)
 170
 171 /**
 172  * Insert an item into a list. The item is placed as the next list item
 173  * to the head.
 174  */
 175 static inline void
 176 list_insert(struct list_item *head, struct list_item *item)
 177 {
 178         item->next = head->next;
 179         item->prev = head;
 180         head->next->prev = item;
 181         head->next = item;
 182 }
 183
 184 /**
 185  * Insert an item into a list. The item is placed as the previous list item
 186  * to the head.
 187  */
 188 static inline void
 189 list_append(struct list_item *head, struct list_item *item)
 190 {
 191         item->next = head;
 192         item->prev = head->prev;
 193         head->prev->next = item;
 194         head->prev = item;
 195 }
 196
 197 /**
 198  * Remove an item from a list.
 199  *
 200  * @param item Pointer to struct list_item of the item to be removed.
 201  * @return     Whether the action has been performed.
 202  */
 203 static inline bool
 204 list_remove(struct list_item *item)
 205 {
 206         if (!item->next || !item->prev || list_is_empty(item))
 207                 return false;
 208
 209         item->prev->next = item->next;
 210         item->next->prev = item->prev;
 211         item->next = item->prev = item;
 212
 213         return true;
 214 }
 215
 216 /**
 217  * Remove the last element of a list.
 218  *
 219  * @param head Pointer to the list's head.
 220  * @return     Pointer to struct list_item removed from the list;
 221  *             or NULL, if the list is empty.
 222  */
 223 static inline struct list_item *
 224 list_remove_tail(struct list_item *head)
 225 {
 226         struct list_item *t = list_is_empty(head) ? NULL : head->prev;
 227
 228         if (t)
 229                 list_remove(t);
 230
 231         return t;
 232 }
 233
 234 /**
 235  * Remove the first element of a list.
 236  *
 237  * @param head Pointer to the list's head.
 238  * @return     Pointer to struct list_item removed from the list;
 239  *             or NULL, if the list is empty.
 240  */
 241 static inline struct list_item *
 242 list_remove_head(struct list_item *head)
 243 {
 244         struct list_item *h = list_is_empty(head) ? NULL : head->next;
 245
 246         if (h)
 247                 list_remove(h);
 248
 249         return h;
 250 }
 251
 252 /**
 253  * Replace an old struct list_item in a list with the new one.
 254  *
 255  * @param old Pointer to struct list_item of the item to be replaced.
 256  * @param new Pointer to struct list_item of the item to be replaced with.
 257  * @return    Whether the replacement has been performed.
 258  */
 259 static inline bool
 260 list_replace(struct list_item *old, struct list_item *new)
 261 {
 262         if (!old->next || !old->prev || list_is_empty(old))
 263                 return false;
 264
 265         new->next = old->next;
 266         new->prev = old->prev;
 267         old->prev->next = new;
 268         old->next->prev = new;
 269         old->next = old->prev = old;
 270
 271         return true;
 272 }
 273
 274 /**
 275  * List iteration wrapper for non-destructive operations.
 276  *
 277  * @param var_   Variable holding pointer to a current list item.
 278  * @param head_  Pointer to the list's head.
 279  * @param field_ Name of the field containing the respective struct list_item
 280  *               inside list items.
 281  */
 282 # define list_foreach(var_, head_, field_) \
 283         for (var_ = list_elem((head_)->next, typeof(*var_), field_); \
 284             &(var_->field_) != (head_); var_ = list_next(var_, field_))
 285
 286 /**
 287  * List iteration wrapper for destructive operations.
 288  *
 289  * @param var_   Variable holding pointer to a current list item.
 290  * @param head_  Pointer to the list's head.
 291  * @param field_ Name of the field containing the respective struct list_item
 292  *               inside list items.
 293  * @param _tmp   Temporary variable for storing pointer to the next item.
 294  */
 295 # define list_foreach_safe(var_, head_, field_, _tmp) \
 296         for (var_ = list_elem((head_)->next, typeof(*var_), field_), \
 297             _tmp = list_elem((var_)->field_.next, typeof(*var_), field_); \
 298             &var_->field_ != head_; var_ = _tmp, _tmp = list_next(_tmp, field_))
 299
 300 #endif /* !STRACE_LIST_H */