src/list.c

   1 /* list.c -- doubly linked list routines 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 <stdlib.h>
  15 #include <stdio.h>
  16
  17 #include "util.h"
  18
  19 #include "list.h"
  20
  21 /* Create a new, empty list. */
  22 struct list *list_new(void)
  23 {
  24   struct list *l = ensure_malloc(sizeof *l);
  25   l->first = NULL;
  26   l->last = NULL;
  27   return l;
  28 }
  29
  30 /* Create a (shallow) copy of the given list. */
  31 struct list *list_copy(struct list *l)
  32 {
  33   struct list *new_list = list_new();
  34
  35   list_for_each(l, item)
  36     list_append(new_list, item->data);
  37
  38   return new_list;
  39 }
  40
  41 /* Deallocate the given list and all items. */
  42 void list_free(struct list *l)
  43 {
  44   list_for_each_manual(l, item) {
  45     struct list_item *tmp = item->next;
  46     free(item);
  47     item = tmp;
  48   }
  49
  50   free(l);
  51 }
  52
  53 /* Calculate the number of items in the given list. */
  54 size_t list_length(struct list *l)
  55 {
  56   size_t length = 0;
  57
  58   list_for_each(l, item)
  59     length++;
  60
  61   return length;
  62 }
  63
  64 /* Create a new list item with the given data and add it to the end of the
  65  * list. */
  66 void list_append(struct list *l, void *data)
  67 {
  68   struct list_item *item = ensure_malloc(sizeof *item);
  69
  70   item->data = data;
  71   item->previous = l->last;
  72   item->next = NULL;
  73
  74   if (l->last != NULL)
  75     l->last->next = item;
  76
  77   l->last = item;
  78
  79   if (l->first == NULL)
  80     l->first = item;
  81 }
  82
  83 /* Remove the given item from the list.  Returns the item following the deleted
  84  * one or NULL if the given item was the last. */
  85 struct list_item *list_delete_item(struct list *l, struct list_item *item)
  86 {
  87   struct list_item *next = item->next;
  88
  89   if (item->previous != NULL)
  90     item->previous->next = item->next;
  91
  92   if (item->next != NULL)
  93     item->next->previous = item->previous;
  94
  95   if (l->first == item)
  96     l->first = item->next;
  97
  98   if (l->last == item)
  99     l->last = item->previous;
 100
 101   free(item);
 102
 103   return next;
 104 }
 105
 106 /* Remove the first item with the given data.  Does nothing if no item has this
 107  * data. */
 108 void list_delete(struct list *l, void *data)
 109 {
 110   struct list_item *item = list_find(l, data);
 111
 112   if (item != NULL)
 113     (void) list_delete_item(l, item);
 114 }
 115
 116 /* Find the first item with the given data.  Returns NULL if no item has this
 117  * data. */
 118 struct list_item *list_find(struct list *l, void *data)
 119 {
 120   list_for_each(l, item)
 121     if (item->data == data)
 122       return item;
 123
 124   return NULL;
 125 }