src/list.h

   1 /* list.h -- doubly linked list header file for vlock,
   2  *           the VT locking program for linux
   3  *
   4  * This program is copyright (C) 2007 Frank Benkstein, and is free
   5  * software which is freely distributable under the terms of the
   6  * GNU General Public License version 2, included as the file COPYING in this
   7  * distribution.  It is NOT public domain software, and any
   8  * redistribution not permitted by the GNU General Public License is
   9  * expressly forbidden without prior written permission from
  10  * the author.
  11  *
  12  */
  13
  14 #include <stdbool.h>
  15 #include <stddef.h>
  16
  17 /* Single list item. */
  18 struct list_item
  19 {
  20   void *data;
  21   struct list_item *next;
  22   struct list_item *previous;
  23 };
  24
  25 /* Whole list. */
  26 struct list
  27 {
  28   struct list_item *first;
  29   struct list_item *last;
  30 };
  31
  32 /* Create a new, empty list. */
  33 struct list *list_new(void);
  34 /* Create a (shallow) copy of the given list. */
  35 struct list *list_copy(struct list *l);
  36
  37 /* Deallocate the given list and all items. */
  38 void list_free(struct list *l);
  39
  40 /* Calculate the number of items in the given list. */
  41 size_t list_length(struct list *l);
  42
  43 /* Create a new list item with the given data and add it to the end of the
  44  * list. */
  45 bool list_append(struct list *l, void *data);
  46
  47 /* Remove the given item from the list.  Returns the item following the deleted
  48  * one or NULL if the given item was the last. */
  49 struct list_item *list_delete_item(struct list *l, struct list_item *item);
  50
  51 /* Remove the first item with the given data.  Does nothing if no item has this
  52  * data. */
  53 void list_delete(struct list *l, void *data);
  54
  55 /* Find the first item with the given data.  Returns NULL if no item has this
  56  * data. */
  57 struct list_item *list_find(struct list *l, void *data);
  58
  59 /* Generic list iteration macro. */
  60 #define list_for_each_from_increment(list, item, start, increment) \
  61   for (struct list_item *item = (start); item != NULL; (increment))
  62
  63 /* Iterate over the whole list. */
  64 #define list_for_each(list, item) \
  65   list_for_each_from_increment((list), item, (list)->first, item = item->next)
  66
  67 /* Iterate over the list while deleting every item after the iteration. */
  68 #define list_delete_for_each(list, item) \
  69   list_for_each_from_increment((list), item, (list)->first, item = list_delete_item((list), item))
  70
  71 /* Iterate over the list.  Incrementation must be done manually. */
  72 #define list_for_each_manual(list, item) \
  73   for (struct list_item *item = (list)->first; item != NULL;)
  74
  75 /* Iterate backwards over list from the given start. */
  76 #define list_for_each_reverse_from(list, item, start) \
  77   list_for_each_from_increment((list), item, (start), item = item->previous)
  78
  79 /* Iterate backwards over the whole list. */
  80 #define list_for_each_reverse(list, item) \
  81   list_for_each_reverse_from((list), item, (list)->last)
  82
  83 static inline bool list_is_empty(struct list *l)
  84 {
  85   return l->first == NULL;
  86 }