git.meshlink.io Git - meshlink/blob - src/list.c

   1 /*
   2     list.c -- functions to deal with double linked lists
   3     Copyright (C) 2014 Guus Sliepen <guus@meshlink.io>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License along
  16     with this program; if not, write to the Free Software Foundation, Inc.,
  17     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "system.h"
  21
  22 #include "list.h"
  23 #include "xalloc.h"
  24
  25 /* (De)constructors */
  26
  27 list_t *list_alloc(list_action_t delete) {
  28         list_t *list = xzalloc(sizeof(list_t));
  29         list->delete = delete;
  30
  31         return list;
  32 }
  33
  34 void list_free(list_t *list) {
  35         free(list);
  36 }
  37
  38 list_node_t *list_alloc_node(void) {
  39         return xzalloc(sizeof(list_node_t));
  40 }
  41
  42 void list_free_node(list_t *list, list_node_t *node) {
  43         if(node->data && list->delete) {
  44                 list->delete(node->data);
  45         }
  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
  66         list->count++;
  67
  68         return node;
  69 }
  70
  71 list_node_t *list_insert_tail(list_t *list, void *data) {
  72         list_node_t *node = list_alloc_node();
  73
  74         node->data = data;
  75         node->next = NULL;
  76         node->prev = list->tail;
  77         list->tail = node;
  78
  79         if(node->prev) {
  80                 node->prev->next = node;
  81         } else {
  82                 list->head = node;
  83         }
  84
  85         list->count++;
  86
  87         return node;
  88 }
  89
  90 list_node_t *list_insert_after(list_t *list, list_node_t *after, void *data) {
  91         list_node_t *node = list_alloc_node();
  92
  93         node->data = data;
  94         node->next = after->next;
  95         node->prev = after;
  96         after->next = node;
  97
  98         if(node->next) {
  99                 node->next->prev = node;
 100         } else {
 101                 list->tail = node;
 102         }
 103
 104         list->count++;
 105
 106         return node;
 107 }
 108
 109 list_node_t *list_insert_before(list_t *list, list_node_t *before, void *data) {
 110         list_node_t *node;
 111
 112         node = list_alloc_node();
 113
 114         node->data = data;
 115         node->next = before;
 116         node->prev = before->prev;
 117         before->prev = node;
 118
 119         if(node->prev) {
 120                 node->prev->next = node;
 121         } else {
 122                 list->head = node;
 123         }
 124
 125         list->count++;
 126
 127         return node;
 128 }
 129
 130 void list_unlink_node(list_t *list, list_node_t *node) {
 131         if(node->prev) {
 132                 node->prev->next = node->next;
 133         } else {
 134                 list->head = node->next;
 135         }
 136
 137         if(node->next) {
 138                 node->next->prev = node->prev;
 139         } else {
 140                 list->tail = node->prev;
 141         }
 142
 143         list->count--;
 144 }
 145
 146 void list_delete_node(list_t *list, list_node_t *node) {
 147         list_unlink_node(list, node);
 148         list_free_node(list, node);
 149 }
 150
 151 void list_delete_head(list_t *list) {
 152         list_delete_node(list, list->head);
 153 }
 154
 155 void list_delete_tail(list_t *list) {
 156         list_delete_node(list, list->tail);
 157 }
 158
 159 void list_delete(list_t *list, const void *data) {
 160         for(list_node_t *node = list->head, *next; next = node ? node->next : NULL, node; node = next)
 161                 if(node->data == data) {
 162                         list_delete_node(list, node);
 163                 }
 164 }
 165
 166 /* Head/tail lookup */
 167
 168 void *list_get_head(list_t *list) {
 169         if(list->head) {
 170                 return list->head->data;
 171         } else {
 172                 return NULL;
 173         }
 174 }
 175
 176 void *list_get_tail(list_t *list) {
 177         if(list->tail) {
 178                 return list->tail->data;
 179         } else {
 180                 return NULL;
 181         }
 182 }
 183
 184 /* Fast list deletion */
 185
 186 void list_delete_list(list_t *list) {
 187         for(list_node_t *node = list->head, *next; next = node ? node->next : NULL, node; node = next) {
 188                 list_free_node(list, node);
 189                 list->count--;
 190         }
 191
 192         assert(!list->count);
 193
 194         list_free(list);
 195 }
 196
 197 /* Traversing */
 198
 199 void list_foreach_node(list_t *list, list_action_node_t action) {
 200         for(list_node_t *node = list->head, *next; next = node ? node->next : NULL, node; node = next) {
 201                 action(node);
 202         }
 203 }
 204
 205 void list_foreach(list_t *list, list_action_t action) {
 206         for(list_node_t *node = list->head, *next; next = node ? node->next : NULL, node; node = next)
 207                 if(node->data) {
 208                         action(node->data);
 209                 }
 210 }