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 static list_node_t *list_alloc_node(void) {
  39         return xzalloc(sizeof(list_node_t));
  40 }
  41
  42 static 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 static void list_unlink_node(list_t *list, list_node_t *node) {
  91         assert(list->count);
  92         assert(node->prev || list->head == node);
  93         assert(node->next || list->tail == node);
  94
  95         if(node->prev) {
  96                 node->prev->next = node->next;
  97         } else {
  98                 list->head = node->next;
  99         }
 100
 101         if(node->next) {
 102                 node->next->prev = node->prev;
 103         } else {
 104                 list->tail = node->prev;
 105         }
 106
 107         list->count--;
 108 }
 109
 110 void list_delete_node(list_t *list, list_node_t *node) {
 111         list_unlink_node(list, node);
 112         list_free_node(list, node);
 113 }
 114
 115 void list_delete_head(list_t *list) {
 116         list_delete_node(list, list->head);
 117 }
 118
 119 void list_delete_tail(list_t *list) {
 120         list_delete_node(list, list->tail);
 121 }
 122
 123 void list_delete(list_t *list, const void *data) {
 124         for(list_node_t *node = list->head, *next; next = node ? node->next : NULL, node; node = next) {
 125                 if(node->data == data) {
 126                         list_delete_node(list, node);
 127                 }
 128         }
 129 }
 130
 131 /* Head/tail lookup */
 132
 133 void *list_get_head(list_t *list) {
 134         if(list->head) {
 135                 return list->head->data;
 136         } else {
 137                 return NULL;
 138         }
 139 }
 140
 141 void *list_get_tail(list_t *list) {
 142         if(list->tail) {
 143                 return list->tail->data;
 144         } else {
 145                 return NULL;
 146         }
 147 }
 148
 149 /* Fast list deletion */
 150
 151 void list_delete_list(list_t *list) {
 152         for(list_node_t *node = list->head, *next; next = node ? node->next : NULL, node; node = next) {
 153                 list_free_node(list, node);
 154                 list->count--;
 155         }
 156
 157         assert(!list->count);
 158
 159         list_free(list);
 160 }
 161
 162 /* Traversing */
 163
 164 void list_foreach_node(list_t *list, list_action_node_t action) {
 165         for(list_node_t *node = list->head, *next; next = node ? node->next : NULL, node; node = next) {
 166                 action(node);
 167         }
 168 }
 169
 170 void list_foreach(list_t *list, list_action_t action) {
 171         for(list_node_t *node = list->head, *next; next = node ? node->next : NULL, node; node = next) {
 172                 if(node->data) {
 173                         action(node->data);
 174                 }
 175         }
 176 }