]> git.meshlink.io Git - meshlink/blob - src/list.c
Update the TODO list.
[meshlink] / 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 }