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 memory 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 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 General Public License for more details.
18
19 You should have received a copy of the GNU Lesser General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22
23 */
24
25 #ifndef __jack_jslist_h__
26 #define __jack_jslist_h__
27
28 #include <stdlib.h>
29 #include <jack/systemdeps.h>
30
31 #ifdef sun
32 #define __inline__
33 #endif
34
35 typedef struct _JSList JSList;
36
37 typedef int (*JCompareFunc) (void* a, void* b);
38 struct _JSList
39 {
40 void *data;
41 JSList *next;
42 };
43
44 static __inline__
45 JSList*
jack_slist_alloc(void)46 jack_slist_alloc (void)
47 {
48 JSList *new_list;
49
50 new_list = (JSList*)malloc(sizeof(JSList));
51 if (new_list) {
52 new_list->data = NULL;
53 new_list->next = NULL;
54 }
55
56 return new_list;
57 }
58
59 static __inline__
60 JSList*
jack_slist_prepend(JSList * list,void * data)61 jack_slist_prepend (JSList* list, void* data)
62 {
63 JSList *new_list;
64
65 new_list = (JSList*)malloc(sizeof(JSList));
66 if (new_list) {
67 new_list->data = data;
68 new_list->next = list;
69 }
70
71 return new_list;
72 }
73
74 #define jack_slist_next(slist) ((slist) ? (((JSList *)(slist))->next) : NULL)
75 static __inline__
76 JSList*
jack_slist_last(JSList * list)77 jack_slist_last (JSList *list)
78 {
79 if (list) {
80 while (list->next)
81 list = list->next;
82 }
83
84 return list;
85 }
86
87 static __inline__
88 JSList*
jack_slist_remove_link(JSList * list,JSList * link)89 jack_slist_remove_link (JSList *list,
90 JSList *link)
91 {
92 JSList *tmp;
93 JSList *prev;
94
95 prev = NULL;
96 tmp = list;
97
98 while (tmp) {
99 if (tmp == link) {
100 if (prev)
101 prev->next = tmp->next;
102 if (list == tmp)
103 list = list->next;
104
105 tmp->next = NULL;
106 break;
107 }
108
109 prev = tmp;
110 tmp = tmp->next;
111 }
112
113 return list;
114 }
115
116 static __inline__
117 void
jack_slist_free(JSList * list)118 jack_slist_free (JSList *list)
119 {
120 while (list) {
121 JSList *next = list->next;
122 free(list);
123 list = next;
124 }
125 }
126
127 static __inline__
128 void
jack_slist_free_1(JSList * list)129 jack_slist_free_1 (JSList *list)
130 {
131 if (list) {
132 free(list);
133 }
134 }
135
136 static __inline__
137 JSList*
jack_slist_remove(JSList * list,void * data)138 jack_slist_remove (JSList *list,
139 void *data)
140 {
141 JSList *tmp;
142 JSList *prev;
143
144 prev = NULL;
145 tmp = list;
146
147 while (tmp) {
148 if (tmp->data == data) {
149 if (prev)
150 prev->next = tmp->next;
151 if (list == tmp)
152 list = list->next;
153
154 tmp->next = NULL;
155 jack_slist_free (tmp);
156
157 break;
158 }
159
160 prev = tmp;
161 tmp = tmp->next;
162 }
163
164 return list;
165 }
166
167 static __inline__
168 unsigned int
jack_slist_length(JSList * list)169 jack_slist_length (JSList *list)
170 {
171 unsigned int length;
172
173 length = 0;
174 while (list) {
175 length++;
176 list = list->next;
177 }
178
179 return length;
180 }
181
182 static __inline__
183 JSList*
jack_slist_find(JSList * list,void * data)184 jack_slist_find (JSList *list,
185 void *data)
186 {
187 while (list) {
188 if (list->data == data)
189 break;
190 list = list->next;
191 }
192
193 return list;
194 }
195
196 static __inline__
197 JSList*
jack_slist_copy(JSList * list)198 jack_slist_copy (JSList *list)
199 {
200 JSList *new_list = NULL;
201
202 if (list) {
203 JSList *last;
204
205 new_list = jack_slist_alloc ();
206 new_list->data = list->data;
207 last = new_list;
208 list = list->next;
209 while (list) {
210 last->next = jack_slist_alloc ();
211 last = last->next;
212 last->data = list->data;
213 list = list->next;
214 }
215 }
216
217 return new_list;
218 }
219
220 static __inline__
221 JSList*
jack_slist_append(JSList * list,void * data)222 jack_slist_append (JSList *list,
223 void *data)
224 {
225 JSList *new_list;
226 JSList *last;
227
228 new_list = jack_slist_alloc ();
229 new_list->data = data;
230
231 if (list) {
232 last = jack_slist_last (list);
233 last->next = new_list;
234
235 return list;
236 } else
237 return new_list;
238 }
239
240 static __inline__
241 JSList*
jack_slist_sort_merge(JSList * l1,JSList * l2,JCompareFunc compare_func)242 jack_slist_sort_merge (JSList *l1,
243 JSList *l2,
244 JCompareFunc compare_func)
245 {
246 JSList list, *l;
247
248 l = &list;
249
250 while (l1 && l2) {
251 if (compare_func(l1->data, l2->data) < 0) {
252 l = l->next = l1;
253 l1 = l1->next;
254 } else {
255 l = l->next = l2;
256 l2 = l2->next;
257 }
258 }
259 l->next = l1 ? l1 : l2;
260
261 return list.next;
262 }
263
264 static __inline__
265 JSList*
jack_slist_sort(JSList * list,JCompareFunc compare_func)266 jack_slist_sort (JSList *list,
267 JCompareFunc compare_func)
268 {
269 JSList *l1, *l2;
270
271 if (!list)
272 return NULL;
273 if (!list->next)
274 return list;
275
276 l1 = list;
277 l2 = list->next;
278
279 while ((l2 = l2->next) != NULL) {
280 if ((l2 = l2->next) == NULL)
281 break;
282 l1 = l1->next;
283 }
284 l2 = l1->next;
285 l1->next = NULL;
286
287 return jack_slist_sort_merge (jack_slist_sort (list, compare_func),
288 jack_slist_sort (l2, compare_func),
289 compare_func);
290 }
291
292 #endif /* __jack_jslist_h__ */
293
294