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