1 /*
2 Based on gslist.c from glib-1.2.9 (LGPL).
3
4 Adaption to JACK, Copyright (C) 2002 Kai Vehmanen.
5 - replaced use of gtypes with normal ANSI C types
6 - glib's memery allocation routines replaced with
7 malloc/free calls
8
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU Lesser Lesser General Public License as published by
11 the Free Software Foundation; either version 2.1 of the License, or
12 (at your option) any later version.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU Lesser Lesser General Public License for more details.
18
19 You should have received a copy of the GNU Lesser Lesser General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22
23 $Id: list.h,v 1.1 2005/09/13 05:22:59 drobilla Exp $
24 */
25
26 /*
27 * Nicked from jack, with:
28 * s/jack_slist/lash_list/g
29 * s/JSList/lash_list_t/g
30 * s/malloc/lash_malloc/g
31 * - Bob Ham
32 */
33
34 #ifndef __LASH_LIST_H__
35 #define __LASH_LIST_H__
36
37 #include <lash/xmalloc.h>
38
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42
43 typedef struct _lash_list lash_list_t;
44
45 typedef int (*JCompareFunc) (void* a,
46 void* b);
47 struct _lash_list
48 {
49 void *data;
50 lash_list_t *next;
51 };
52
53 static __inline__
54 lash_list_t*
lash_list_alloc(void)55 lash_list_alloc (void)
56 {
57 lash_list_t *new_list;
58
59 new_list = (lash_list_t *) lash_malloc(sizeof(lash_list_t));
60 new_list->data = NULL;
61 new_list->next = NULL;
62
63 return new_list;
64 }
65
66 static __inline__
67 lash_list_t*
lash_list_prepend(lash_list_t * list,void * data)68 lash_list_prepend (lash_list_t *list,
69 void *data)
70 {
71 lash_list_t *new_list;
72
73 new_list = (lash_list_t *) lash_malloc(sizeof(lash_list_t));
74 new_list->data = data;
75 new_list->next = list;
76
77 return new_list;
78 }
79
80 #define lash_list_next(slist) ((slist) ? (((lash_list_t *)(slist))->next) : NULL)
81 static __inline__
82 lash_list_t*
lash_list_last(lash_list_t * list)83 lash_list_last (lash_list_t *list)
84 {
85 if (list)
86 {
87 while (list->next)
88 list = list->next;
89 }
90
91 return list;
92 }
93
94 static __inline__
95 lash_list_t*
lash_list_remove_link(lash_list_t * list,lash_list_t * link)96 lash_list_remove_link (lash_list_t *list,
97 lash_list_t *link)
98 {
99 lash_list_t *tmp;
100 lash_list_t *prev;
101
102 prev = NULL;
103 tmp = list;
104
105 while (tmp)
106 {
107 if (tmp == link)
108 {
109 if (prev)
110 prev->next = tmp->next;
111 if (list == tmp)
112 list = list->next;
113
114 tmp->next = NULL;
115 break;
116 }
117
118 prev = tmp;
119 tmp = tmp->next;
120 }
121
122 return list;
123 }
124
125 static __inline__
126 void
lash_list_free(lash_list_t * list)127 lash_list_free (lash_list_t *list)
128 {
129 while (list)
130 {
131 lash_list_t *next = list->next;
132 free(list);
133 list = next;
134 }
135 }
136
137 static __inline__
138 void
lash_list_free_1(lash_list_t * list)139 lash_list_free_1 (lash_list_t *list)
140 {
141 if (list)
142 {
143 free(list);
144 }
145 }
146
147 static __inline__
148 lash_list_t*
lash_list_remove(lash_list_t * list,void * data)149 lash_list_remove (lash_list_t *list,
150 void *data)
151 {
152 lash_list_t *tmp;
153 lash_list_t *prev;
154
155 prev = NULL;
156 tmp = list;
157
158 while (tmp)
159 {
160 if (tmp->data == data)
161 {
162 if (prev)
163 prev->next = tmp->next;
164 if (list == tmp)
165 list = list->next;
166
167 tmp->next = NULL;
168 lash_list_free (tmp);
169
170 break;
171 }
172
173 prev = tmp;
174 tmp = tmp->next;
175 }
176
177 return list;
178 }
179
180 static __inline__
181 unsigned int
lash_list_length(lash_list_t * list)182 lash_list_length (lash_list_t *list)
183 {
184 unsigned int length = 0;
185
186 while (list)
187 {
188 length++;
189 list = list->next;
190 }
191
192 return length;
193 }
194
195 static __inline__
196 lash_list_t*
lash_list_find(lash_list_t * list,void * data)197 lash_list_find (lash_list_t *list,
198 void *data)
199 {
200 while (list)
201 {
202 if (list->data == data)
203 break;
204 list = list->next;
205 }
206
207 return list;
208 }
209
210 static __inline__
211 lash_list_t*
lash_list_copy(lash_list_t * list)212 lash_list_copy (lash_list_t *list)
213 {
214 lash_list_t *new_list = NULL;
215
216 if (list)
217 {
218 lash_list_t *last;
219
220 new_list = lash_list_alloc ();
221 new_list->data = list->data;
222 last = new_list;
223 list = list->next;
224 while (list)
225 {
226 last->next = lash_list_alloc ();
227 last = last->next;
228 last->data = list->data;
229 list = list->next;
230 }
231 }
232
233 return new_list;
234 }
235
236 static __inline__
237 lash_list_t*
lash_list_append(lash_list_t * list,void * data)238 lash_list_append (lash_list_t *list,
239 void *data)
240 {
241 lash_list_t *new_list;
242 lash_list_t *last;
243
244 new_list = lash_list_alloc ();
245 new_list->data = data;
246
247 if (list)
248 {
249 last = lash_list_last (list);
250 last->next = new_list;
251
252 return list;
253 }
254 else
255 return new_list;
256 }
257
258 static __inline__
259 lash_list_t*
lash_list_sort_merge(lash_list_t * l1,lash_list_t * l2,JCompareFunc compare_func)260 lash_list_sort_merge (lash_list_t *l1,
261 lash_list_t *l2,
262 JCompareFunc compare_func)
263 {
264 lash_list_t list, *l;
265
266 l=&list;
267
268 while (l1 && l2)
269 {
270 if (compare_func(l1->data,l2->data) < 0)
271 {
272 l=l->next=l1;
273 l1=l1->next;
274 }
275 else
276 {
277 l=l->next=l2;
278 l2=l2->next;
279 }
280 }
281 l->next= l1 ? l1 : l2;
282
283 return list.next;
284 }
285
286 static __inline__
287 lash_list_t*
lash_list_sort(lash_list_t * list,JCompareFunc compare_func)288 lash_list_sort (lash_list_t *list,
289 JCompareFunc compare_func)
290 {
291 lash_list_t *l1, *l2;
292
293 if (!list)
294 return NULL;
295 if (!list->next)
296 return list;
297
298 l1 = list;
299 l2 = list->next;
300
301 while ((l2 = l2->next) != NULL)
302 {
303 if ((l2 = l2->next) == NULL)
304 break;
305 l1=l1->next;
306 }
307 l2 = l1->next;
308 l1->next = NULL;
309
310 return lash_list_sort_merge (lash_list_sort (list, compare_func),
311 lash_list_sort (l2, compare_func),
312 compare_func);
313 }
314
315 static __inline__
316 lash_list_t *
lash_list_concat(lash_list_t * list1,lash_list_t * list2)317 lash_list_concat (lash_list_t *list1, lash_list_t *list2)
318 {
319 if (list2)
320 {
321 if (list1)
322 lash_list_last (list1)->next = list2;
323 else
324 list1 = list2;
325 }
326
327 return list1;
328 }
329
330
331 #ifdef __cplusplus
332 }
333 #endif
334
335
336 #endif /* __LASH_LIST_H__ */
337