2 list.c -- functions to deal with double linked lists
3 Copyright (C) 2014 Guus Sliepen <guus@meshlink.io>
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.
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.
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.
25 /* (De)constructors */
27 list_t *list_alloc(list_action_t delete) {
28 list_t *list = xzalloc(sizeof(list_t));
29 list->delete = delete;
34 void list_free(list_t *list) {
38 static list_node_t *list_alloc_node(void) {
39 return xzalloc(sizeof(list_node_t));
42 static void list_free_node(list_t *list, list_node_t *node) {
43 if(node->data && list->delete) {
44 list->delete(node->data);
50 /* Insertion and deletion */
52 list_node_t *list_insert_head(list_t *list, void *data) {
53 list_node_t *node = list_alloc_node();
57 node->next = list->head;
61 node->next->prev = node;
71 list_node_t *list_insert_tail(list_t *list, void *data) {
72 list_node_t *node = list_alloc_node();
76 node->prev = list->tail;
80 node->prev->next = node;
90 static void list_unlink_node(list_t *list, list_node_t *node) {
92 assert(node->prev || list->head == node);
93 assert(node->next || list->tail == node);
96 node->prev->next = node->next;
98 list->head = node->next;
102 node->next->prev = node->prev;
104 list->tail = node->prev;
110 void list_delete_node(list_t *list, list_node_t *node) {
111 list_unlink_node(list, node);
112 list_free_node(list, node);
115 void list_delete_head(list_t *list) {
116 list_delete_node(list, list->head);
119 void list_delete_tail(list_t *list) {
120 list_delete_node(list, list->tail);
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);
131 /* Head/tail lookup */
133 void *list_get_head(list_t *list) {
135 return list->head->data;
141 void *list_get_tail(list_t *list) {
143 return list->tail->data;
149 /* Fast list deletion */
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);
157 assert(!list->count);
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) {
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) {