lib/list.c

   1 /*
   2     list.c -- functions to deal with double linked lists
   3     Copyright (C) 2000,2001 Ivo Timmermans <ivo@o2w.nl>
   4                   2000,2001 Guus Sliepen <guus@sliepen.eu.org>
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19
  20     $Id: list.c,v 1.1.2.12 2002/09/09 21:49:16 guus Exp $
  21 */
  22
  23 #include "config.h"
  24
  25 #include <stdlib.h>
  26
  27 #include <xalloc.h>
  28 #include <system.h>
  29
  30 #include "list.h"
  31
  32 /* (De)constructors */
  33
  34 list_t *list_alloc(list_action_t delete)
  35 {
  36         list_t *list;
  37
  38         list = xmalloc_and_zero(sizeof(list_t));
  39         list->delete = delete;
  40
  41         return list;
  42 }
  43
  44 void list_free(list_t * list)
  45 {
  46         free(list);
  47 }
  48
  49 list_node_t *list_alloc_node(void)
  50 {
  51         return (list_node_t *)xmalloc_and_zero(sizeof(list_node_t));
  52 }
  53
  54 void list_free_node(list_t * list, list_node_t * node)
  55 {
  56         if(node->data && list->delete)
  57                 list->delete(node->data);
  58
  59         free(node);
  60 }
  61
  62 /* Insertion and deletion */
  63
  64 list_node_t *list_insert_head(list_t * list, void *data)
  65 {
  66         list_node_t *node;
  67
  68         node = list_alloc_node();
  69
  70         node->data = data;
  71         node->prev = NULL;
  72         node->next = list->head;
  73         list->head = node;
  74
  75         if(node->next)
  76                 node->next->prev = node;
  77         else
  78                 list->tail = node;
  79
  80         list->count++;
  81
  82         return node;
  83 }
  84
  85 list_node_t *list_insert_tail(list_t * list, void *data)
  86 {
  87         list_node_t *node;
  88
  89         node = list_alloc_node();
  90
  91         node->data = data;
  92         node->next = NULL;
  93         node->prev = list->tail;
  94         list->tail = node;
  95
  96         if(node->prev)
  97                 node->prev->next = node;
  98         else
  99                 list->head = node;
 100
 101         list->count++;
 102
 103         return node;
 104 }
 105
 106 void list_unlink_node(list_t * list, list_node_t * node)
 107 {
 108         if(node->prev)
 109                 node->prev->next = node->next;
 110         else
 111                 list->head = node->next;
 112
 113         if(node->next)
 114                 node->next->prev = node->prev;
 115         else
 116                 list->tail = node->prev;
 117
 118         list->count--;
 119 }
 120
 121 void list_delete_node(list_t * list, list_node_t * node)
 122 {
 123         list_unlink_node(list, node);
 124         list_free_node(list, node);
 125 }
 126
 127 void list_delete_head(list_t * list)
 128 {
 129         list_delete_node(list, list->head);
 130 }
 131
 132 void list_delete_tail(list_t * list)
 133 {
 134         list_delete_node(list, list->tail);
 135 }
 136
 137 /* Head/tail lookup */
 138
 139 void *list_get_head(list_t * list)
 140 {
 141         if(list->head)
 142                 return list->head->data;
 143         else
 144                 return NULL;
 145 }
 146
 147 void *list_get_tail(list_t * list)
 148 {
 149         if(list->tail)
 150                 return list->tail->data;
 151         else
 152                 return NULL;
 153 }
 154
 155 /* Fast list deletion */
 156
 157 void list_delete_list(list_t * list)
 158 {
 159         list_node_t *node, *next;
 160
 161         for(node = list->head; node; node = next) {
 162                 next = node->next;
 163                 list_free_node(list, node);
 164         }
 165
 166         list_free(list);
 167 }
 168
 169 /* Traversing */
 170
 171 void list_foreach_node(list_t * list, list_action_node_t action)
 172 {
 173         list_node_t *node, *next;
 174
 175         for(node = list->head; node; node = next) {
 176                 next = node->next;
 177                 action(node);
 178         }
 179 }
 180
 181 void list_foreach(list_t * list, list_action_t action)
 182 {
 183         list_node_t *node, *next;
 184
 185         for(node = list->head; node; node = next) {
 186                 next = node->next;
 187                 if(node->data)
 188                         action(node->data);
 189         }
 190 }