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 /* Inspired by the doubly linked list code from glib:
  15  *
  16  * GLIB - Library of useful routines for C programming
  17  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
  18  *
  19  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  20  * file for a list of people on the GLib Team.  See the ChangeLog
  21  * files for a list of changes.  These files are distributed with
  22  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  23  */
  24
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27
  28 #include "util.h"
  29
  30 #include "list.h"
  31
  32 struct list *list_new(void)
  33 {
  34   struct list *l = ensure_malloc(sizeof *l);
  35   l->first = NULL;
  36   l->last = NULL;
  37   return l;
  38 }
  39
  40 void list_free(struct list *l, list_free_item_function free_item)
  41 {
  42   list_for_each(l, item) {
  43     if (free_item != NULL && item->previous != NULL)
  44       free_item(item->previous->data);
  45
  46     free(item->previous);
  47   }
  48
  49   if (free_item != NULL && l->last != NULL)
  50     free(l->last);
  51
  52   free(l->last);
  53   free(l);
  54 }
  55
  56 void list_append(struct list *l, void *data)
  57 {
  58   struct list_item *item = ensure_malloc(sizeof *item);
  59
  60   item->data = data;
  61   item->previous = l->last;
  62   item->next = NULL;
  63
  64   if (l->last != NULL)
  65     l->last->next = item;
  66
  67   l->last = item;
  68
  69   if (l->first == NULL)
  70     l->first = item;
  71 }
  72
  73 size_t list_length(struct list *l)
  74 {
  75   size_t length = 0;
  76
  77   list_for_each(l, item)
  78     length++;
  79
  80   return length;
  81 }
  82
  83 struct list_item *list_delete_item(struct list *l, struct list_item *item)
  84 {
  85   struct list_item *next = item->next;
  86
  87   if (item->previous != NULL)
  88     item->previous->next = item->next;
  89
  90   if (item->next != NULL)
  91     item->next->previous = item->previous;
  92
  93   if (l->first == item)
  94     l->first = item->next;
  95
  96   if (l->last == item)
  97     l->last = item->previous;
  98
  99   free(item);
 100
 101   return next;
 102 }
 103
 104 #if 0
 105 /* Like list_append() but returns the item that was added instead of the start
 106  * of the list. */
 107 static struct List *__list_append(struct List *list, void *data)
 108 {
 109   struct List *new_item = malloc(sizeof (struct List));
 110   struct List *last = list_last(list);
 111
 112   if (new_item == NULL) {
 113     fprintf(stderr, "%s:%d failed to allocate new list item\n", __FILE__,
 114             __LINE__);
 115     abort();
 116   }
 117
 118   new_item->data = data;
 119   new_item->next = NULL;
 120   new_item->previous = last;
 121
 122   if (last != NULL)
 123     last->next = new_item;
 124
 125   return new_item;
 126 }
 127
 128 struct List *list_append(struct List *list, void *data)
 129 {
 130   struct List *new_item = __list_append(list, data);
 131
 132   if (list != NULL)
 133     return list;
 134   else
 135     return new_item;
 136 }
 137
 138 struct List *list_copy(struct List *list)
 139 {
 140   struct List *new_list = NULL;
 141   struct List *last = NULL;
 142   struct List *item = list_first(list);
 143
 144   /* Make a copy of the first item.  It is now also the last item of the new
 145    * list. */
 146   if (item != NULL)
 147     last = new_list = list_append(new_list, item->data);
 148
 149   /* Append all further items to the first. */
 150   for (item = list_next(item); item != NULL; item = list_next(item))
 151     last = __list_append(last, item->data);
 152
 153   return list_first(new_list);
 154 }
 155
 156 struct List *list_first(struct List *list)
 157 {
 158   if (list != NULL) {
 159     while (list->previous != NULL)
 160       list = list->previous;
 161   }
 162
 163   return list;
 164 }
 165
 166 struct List *list_last(struct List *list)
 167 {
 168   if (list != NULL) {
 169     while (list->next != NULL)
 170       list = list->next;
 171   }
 172
 173   return list;
 174 }
 175
 176 struct List *list_next(struct List *list)
 177 {
 178   if (list == NULL)
 179     return NULL;
 180   else
 181     return list->next;
 182 }
 183
 184 struct List *list_previous(struct List *list)
 185 {
 186   if (list == NULL)
 187     return NULL;
 188   else
 189     return list->previous;
 190 }
 191
 192 struct List *list_find(struct List *list, void *data)
 193 {
 194   list_for_each(list, item) {
 195     if (item->data == data)
 196       return item;
 197   }
 198
 199   return NULL;
 200 }
 201
 202 struct List *list_delete_link(struct List *list, struct List *item)
 203 {
 204   if (item != NULL) {
 205     if (item->previous != NULL)
 206       item->previous->next = item->next;
 207     if (item->next != NULL)
 208       item->next->previous = item->previous;
 209     if (item == list) {
 210       if (item->next != NULL)
 211         list = item->next;
 212       else if (item->previous != NULL)
 213         list = item->previous;
 214       else
 215         list = NULL;
 216     }
 217
 218     free(item);
 219   }
 220
 221   return list;
 222 }
 223
 224 struct List *list_remove(struct List *list, void *data)
 225 {
 226   struct List *item = list_find(list, data);
 227   return list_delete_link(list, item);
 228 }
 229
 230 void list_free(struct List *list)
 231 {
 232   while (list != NULL)
 233     list = list_delete_link(list, list_first(list));
 234 }
 235 #endif