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 /* All list functions abort() on memory allocation errors. */
  33
  34 /* Create a new, empty list. */
  35 struct list *list_new(void);
  36 /* Create a (shallow) copy of the given list. */
  37 struct list *list_copy(struct list *l);
  38
  39 /* Deallocate the given list and all items. */
  40 void list_free(struct list *l);
  41
  42 /* Calculate the number of items in the given list. */
  43 size_t list_length(struct list *l);
  44
  45 /* Create a new list item with the given data and add it to the end of the
  46  * list. */
  47 void list_append(struct list *l, void *data);
  48
  49 /* Remove the given item from the list.  Returns the item following the deleted
  50  * one or NULL if the given item was the last. */
  51 struct list_item *list_delete_item(struct list *l, struct list_item *item);
  52
  53 /* Remove the first item with the given data.  Does nothing if no item has this
  54  * data. */
  55 void list_delete(struct list *l, void *data);
  56
  57 /* Find the first item with the given data.  Returns NULL if no item has this
  58  * data. */
  59 struct list_item *list_find(struct list *l, void *data);
  60
  61 /* Generic list iteration macro. */
  62 #define list_for_each_from_increment(list, item, start, increment) \
  63   for (struct list_item *item = (start); item != NULL; (increment))
  64
  65 /* Iterate over the whole list. */
  66 #define list_for_each(list, item) \
  67   list_for_each_from_increment((list), item, (list)->first, item = item->next)
  68
  69 /* Iterate over the list while deleting every item after the iteration. */
  70 #define list_delete_for_each(list, item) \
  71   list_for_each_from_increment((list), item, (list)->first, item = list_delete_item((list), item))
  72
  73 /* Iterate over the list.  Incrementation must be done manually. */
  74 #define list_for_each_manual(list, item) \
  75   for (struct list_item *item = (list)->first; item != NULL;)
  76
  77 /* Iterate backwards over list from the given start. */
  78 #define list_for_each_reverse_from(list, item, start) \
  79   list_for_each_from_increment((list), item, (start), item = item->previous)
  80
  81 /* Iterate backwards over the whole list. */
  82 #define list_for_each_reverse(list, item) \
  83   list_for_each_reverse_from((list), item, (list)->last)
  84
  85 static inline bool list_is_empty(struct list *l)
  86 {
  87   return l->first == NULL;
  88 }