1 /*
2 llist.c
3
4 Linked list functions
5
6 Copyright (C) 2003 Brian Koropoff
7
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License
10 as published by the Free Software Foundation; either version 2
11 of the License, or (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16
17 See the GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to:
21
22 Free Software Foundation, Inc.
23 59 Temple Place - Suite 330
24 Boston, MA 02111-1307, USA
25
26 */
27
28 #ifdef HAVE_CONFIG_H
29 # include "config.h"
30 #endif
31 #ifdef HAVE_STRING_H
32 # include <string.h>
33 #endif
34 #ifdef HAVE_STRINGS_H
35 # include <strings.h>
36 #endif
37
38 #include <stdlib.h>
39
40 #include "QF/llist.h"
41
42 static llist_node_t *
llist_newnode(llist_t * list,void * data)43 llist_newnode (llist_t *list, void *data)
44 {
45 llist_node_t *node = calloc (1, sizeof (llist_node_t));
46 node->parent = list;
47 node->data = data;
48
49 return node;
50 }
51
52 VISIBLE llist_t *
llist_new(void (* freedata)(void * element,void * userdata),qboolean (* cmpdata)(const void * element,const void * comparison,void * userdata),void * userdata)53 llist_new (void (*freedata)(void *element, void *userdata), qboolean (*cmpdata)(const void *element, const void *comparison, void *userdata), void *userdata)
54 {
55 llist_t *new = calloc (1, sizeof (llist_t));
56
57 new->freedata = freedata;
58 new->cmpdata = cmpdata;
59 new->userdata = userdata;
60
61 return new;
62 }
63
64 VISIBLE void
llist_flush(llist_t * list)65 llist_flush (llist_t *list)
66 {
67 llist_node_t *node, *next;
68
69 if (!list)
70 return;
71
72 for (node = list->start; node; node = next) {
73 next = node->next;
74 list->freedata (node->data, list->userdata);
75 free (node);
76 }
77 list->start = list->end = 0;
78 }
79
80 VISIBLE void
llist_delete(llist_t * list)81 llist_delete (llist_t *list)
82 {
83 if (!list)
84 return;
85
86 llist_flush (list);
87 free (list);
88 }
89
90 VISIBLE llist_node_t *
llist_append(llist_t * list,void * element)91 llist_append (llist_t *list, void *element)
92 {
93 llist_node_t *node = llist_newnode (list, element);
94
95 if (!list)
96 return 0;
97
98 if (list->end) {
99 list->end->next = node;
100 node->prev = list->end;
101 list->end = node;
102 } else
103 list->start = list->end = node;
104 return node;
105 }
106
107 VISIBLE llist_node_t *
llist_prefix(llist_t * list,void * element)108 llist_prefix (llist_t *list, void *element)
109 {
110 llist_node_t *node = llist_newnode (list, element);
111
112 if (!list)
113 return 0;
114
115 if (list->start) {
116 list->start->prev = node;
117 node->next = list->start;
118 list->start = node;
119 } else
120 list->start = list->end = node;
121
122 return node;
123 }
124
125 VISIBLE llist_node_t *
llist_getnode(llist_t * list,void * element)126 llist_getnode (llist_t *list, void *element)
127 {
128 llist_node_t *node;
129
130 if (!list)
131 return 0;
132
133 for (node = list->start; node; node = node->next)
134 if (node->data == element)
135 return node;
136 return 0;
137 }
138
139 VISIBLE llist_node_t *
llist_insertafter(llist_node_t * ref,void * element)140 llist_insertafter (llist_node_t *ref, void *element)
141 {
142 llist_node_t *node = llist_newnode (ref->parent, element);
143
144 if (!ref)
145 return 0;
146
147 if (ref->next)
148 ref->next->prev = node;
149 else
150 ref->parent->end = node;
151 node->prev = ref;
152 node->next = ref->next;
153 ref->next = node;
154
155 return node;
156 }
157
158 VISIBLE llist_node_t *
llist_insertbefore(llist_node_t * ref,void * element)159 llist_insertbefore (llist_node_t *ref, void *element)
160 {
161 llist_node_t *node = llist_newnode (ref->parent, element);
162
163 if (!ref)
164 return 0;
165
166 if (ref->prev)
167 ref->prev->next = node;
168 else
169 ref->parent->start = node;
170 node->next = ref;
171 node->prev = ref->prev;
172 ref->prev = node;
173
174 return node;
175 }
176
177 VISIBLE void *
llist_remove(llist_node_t * ref)178 llist_remove (llist_node_t *ref)
179 {
180 void *element;
181
182 if (!ref)
183 return 0;
184
185 if (ref == ref->parent->iter)
186 ref->parent->iter = ref->next;
187 if (ref->prev)
188 ref->prev->next = ref->next;
189 else
190 ref->parent->start = ref->next;
191 if (ref->next)
192 ref->next->prev = ref->prev;
193 else
194 ref->parent->end = ref->prev;
195
196 element = ref->data;
197 free (ref);
198 return element;
199 }
200
201 VISIBLE unsigned int
llist_size(llist_t * llist)202 llist_size (llist_t *llist)
203 {
204 unsigned int i;
205 llist_node_t *n;
206
207 if (!llist->start)
208 return 0;
209 else for (i = 0, n = llist->start; n; n = n->next, i++);
210
211 return i;
212 }
213
214 VISIBLE void
llist_iterate(llist_t * list,llist_iterator_t iterate)215 llist_iterate (llist_t *list, llist_iterator_t iterate)
216 {
217 llist_node_t *node;
218
219 if (!list || !list->start)
220 return;
221 for (node = list->start; node; node = list->iter) {
222 list->iter = node->next;
223 if (!iterate (node->data, node))
224 break;
225 }
226 list->iter = 0;
227 }
228
229 VISIBLE void *
llist_find(llist_t * list,void * comparison)230 llist_find (llist_t *list, void *comparison)
231 {
232 llist_node_t *node;
233
234 if (!list)
235 return 0;
236 for (node = list->start; node; node = node->next)
237 if (list->cmpdata (node->data, comparison, list->userdata))
238 return node->data;
239 return 0;
240 }
241
242 VISIBLE llist_node_t *
llist_findnode(llist_t * list,void * comparison)243 llist_findnode (llist_t *list, void *comparison)
244 {
245 llist_node_t *node;
246
247 if (!list || !list->cmpdata)
248 return 0;
249 for (node = list->start; node; node = node->next)
250 if (list->cmpdata (node->data, comparison, list->userdata))
251 return node;
252 return 0;
253 }
254
255 VISIBLE void *
llist_createarray(llist_t * list,size_t esize)256 llist_createarray (llist_t *list, size_t esize)
257 {
258 void *ptr, *array = malloc (llist_size (list) * esize);
259 llist_node_t *node;
260
261 for (ptr = array, node = list->start; node; node = node->next, ptr = (char*)ptr + esize)
262 memcpy (ptr, node->data, esize);
263
264 return array;
265 }
266