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