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