lib/list.c

   1 /*
   2     list.c -- functions to deal with double linked lists
   3     Copyright (C) 2000-2005 Ivo Timmermans
   4                   2000-2006 Guus Sliepen <guus@tinc-vpn.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 along
  17     with this program; if not, write to the Free Software Foundation, Inc.,
  18     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  19 */
  20
  21 #include "system.h"
  22
  23 #include "list.h"
  24 #include "xalloc.h"
  25
  26 /* (De)constructors */
  27
  28 list_t *list_alloc(list_action_t delete)
  29 {
  30         list_t *list;
  31
  32         list = xmalloc_and_zero(sizeof(list_t));
  33         list->delete = delete;
  34
  35         return list;
  36 }
  37
  38 void list_free(list_t *list)
  39 {
  40         free(list);
  41 }
  42
  43 list_node_t *list_alloc_node(void)
  44 {
  45         return xmalloc_and_zero(sizeof(list_node_t));
  46 }
  47
  48 void list_free_node(list_t *list, list_node_t *node)
  49 {
  50         if(node->data && list->delete)
  51                 list->delete(node->data);
  52
  53         free(node);
  54 }
  55
  56 /* Insertion and deletion */
  57
  58 list_node_t *list_insert_head(list_t *list, void *data)
  59 {
  60         list_node_t *node;
  61
  62         node = list_alloc_node();
  63
  64         node->data = data;
  65         node->prev = NULL;
  66         node->next = list->head;
  67         list->head = node;
  68
  69         if(node->next)
  70                 node->next->prev = node;
  71         else
  72                 list->tail = node;
  73
  74         list->count++;
  75
  76         return node;
  77 }
  78
  79 list_node_t *list_insert_tail(list_t *list, void *data)
  80 {
  81         list_node_t *node;
  82
  83         node = list_alloc_node();
  84
  85         node->data = data;
  86         node->next = NULL;
  87         node->prev = list->tail;
  88         list->tail = node;
  89
  90         if(node->prev)
  91                 node->prev->next = node;
  92         else
  93                 list->head = node;
  94
  95         list->count++;
  96
  97         return node;
  98 }
  99
 100 void list_unlink_node(list_t *list, list_node_t *node)
 101 {
 102         if(node->prev)
 103                 node->prev->next = node->next;
 104         else
 105                 list->head = node->next;
 106
 107         if(node->next)
 108                 node->next->prev = node->prev;
 109         else
 110                 list->tail = node->prev;
 111
 112         list->count--;
 113 }
 114
 115 void list_delete_node(list_t *list, list_node_t *node)
 116 {
 117         list_unlink_node(list, node);
 118         list_free_node(list, node);
 119 }
 120
 121 void list_delete_head(list_t *list)
 122 {
 123         list_delete_node(list, list->head);
 124 }
 125
 126 void list_delete_tail(list_t *list)
 127 {
 128         list_delete_node(list, list->tail);
 129 }
 130
 131 /* Head/tail lookup */
 132
 133 void *list_get_head(list_t *list)
 134 {
 135         if(list->head)
 136                 return list->head->data;
 137         else
 138                 return NULL;
 139 }
 140
 141 void *list_get_tail(list_t *list)
 142 {
 143         if(list->tail)
 144                 return list->tail->data;
 145         else
 146                 return NULL;
 147 }
 148
 149 /* Fast list deletion */
 150
 151 void list_delete_list(list_t *list)
 152 {
 153         list_node_t *node, *next;
 154
 155         for(node = list->head; node; node = next) {
 156                 next = node->next;
 157                 list_free_node(list, node);
 158         }
 159
 160         list_free(list);
 161 }
 162
 163 /* Traversing */
 164
 165 void list_foreach_node(list_t *list, list_action_node_t action)
 166 {
 167         list_node_t *node, *next;
 168
 169         for(node = list->head; node; node = next) {
 170                 next = node->next;
 171                 action(node);
 172         }
 173 }
 174
 175 void list_foreach(list_t *list, list_action_t action)
 176 {
 177         list_node_t *node, *next;
 178
 179         for(node = list->head; node; node = next) {
 180                 next = node->next;
 181                 if(node->data)
 182                         action(node->data);
 183         }
 184 }