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