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