tinc-vpn.org Git - tinc/blob - src/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         list_t *list;
  30
  31         list = xmalloc_and_zero(sizeof(list_t));
  32         list->delete = delete;
  33
  34         return list;
  35 }
  36
  37 void list_free(list_t *list) {
  38         free(list);
  39 }
  40
  41 list_node_t *list_alloc_node(void) {
  42         return xmalloc_and_zero(sizeof(list_node_t));
  43 }
  44
  45 void list_free_node(list_t *list, list_node_t *node) {
  46         if(node->data && list->delete)
  47                 list->delete(node->data);
  48
  49         free(node);
  50 }
  51
  52 /* Insertion and deletion */
  53
  54 list_node_t *list_insert_head(list_t *list, void *data) {
  55         list_node_t *node;
  56
  57         node = list_alloc_node();
  58
  59         node->data = data;
  60         node->prev = NULL;
  61         node->next = list->head;
  62         list->head = node;
  63
  64         if(node->next)
  65                 node->next->prev = node;
  66         else
  67                 list->tail = node;
  68
  69         list->count++;
  70
  71         return node;
  72 }
  73
  74 list_node_t *list_insert_tail(list_t *list, void *data) {
  75         list_node_t *node;
  76
  77         node = list_alloc_node();
  78
  79         node->data = data;
  80         node->next = NULL;
  81         node->prev = list->tail;
  82         list->tail = node;
  83
  84         if(node->prev)
  85                 node->prev->next = node;
  86         else
  87                 list->head = node;
  88
  89         list->count++;
  90
  91         return node;
  92 }
  93
  94 list_node_t *list_insert_after(list_t *list, list_node_t *after, void *data) {
  95         list_node_t *node;
  96
  97         node = list_alloc_node();
  98
  99         node->data = data;
 100         node->next = after->next;
 101         node->prev = after;
 102         after->next = node;
 103
 104         if(node->next)
 105                 node->next->prev = node;
 106         else
 107                 list->tail = node;
 108
 109         list->count++;
 110
 111         return node;
 112 }
 113
 114 list_node_t *list_insert_before(list_t *list, list_node_t *before, void *data) {
 115         list_node_t *node;
 116
 117         node = list_alloc_node();
 118
 119         node->data = data;
 120         node->next = before;
 121         node->prev = before->prev;
 122         before->prev = node;
 123
 124         if(node->prev)
 125                 node->prev->next = node;
 126         else
 127                 list->head = node;
 128
 129         list->count++;
 130
 131         return node;
 132 }
 133
 134 void list_unlink_node(list_t *list, list_node_t *node) {
 135         if(node->prev)
 136                 node->prev->next = node->next;
 137         else
 138                 list->head = node->next;
 139
 140         if(node->next)
 141                 node->next->prev = node->prev;
 142         else
 143                 list->tail = node->prev;
 144
 145         list->count--;
 146 }
 147
 148 void list_delete_node(list_t *list, list_node_t *node) {
 149         list_unlink_node(list, node);
 150         list_free_node(list, node);
 151 }
 152
 153 void list_delete_head(list_t *list) {
 154         list_delete_node(list, list->head);
 155 }
 156
 157 void list_delete_tail(list_t *list) {
 158         list_delete_node(list, list->tail);
 159 }
 160
 161 /* Head/tail lookup */
 162
 163 void *list_get_head(list_t *list) {
 164         if(list->head)
 165                 return list->head->data;
 166         else
 167                 return NULL;
 168 }
 169
 170 void *list_get_tail(list_t *list) {
 171         if(list->tail)
 172                 return list->tail->data;
 173         else
 174                 return NULL;
 175 }
 176
 177 /* Fast list deletion */
 178
 179 void list_delete_list(list_t *list) {
 180         list_node_t *node, *next;
 181
 182         for(node = list->head; node; node = next) {
 183                 next = node->next;
 184                 list_free_node(list, node);
 185         }
 186
 187         list_free(list);
 188 }
 189
 190 /* Traversing */
 191
 192 void list_foreach_node(list_t *list, list_action_node_t action) {
 193         list_node_t *node, *next;
 194
 195         for(node = list->head; node; node = next) {
 196                 next = node->next;
 197                 action(node);
 198         }
 199 }
 200
 201 void list_foreach(list_t *list, list_action_t action) {
 202         list_node_t *node, *next;
 203
 204         for(node = list->head; node; node = next) {
 205                 next = node->next;
 206                 if(node->data)
 207                         action(node->data);
 208         }
 209 }