1 /* gslist.c: Minimal replacement for GSList
2 Copyright (c) 2001-2004 Matan Ziv-Av, Philip Kendall, Marek Januszewski
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17
18 Author contact information:
19
20 E-mail: philip-fuse@shadowmagic.org.uk
21
22 */
23
24 #include "config.h"
25
26 #ifndef HAVE_LIB_GLIB /* Use this iff we're not using the
27 `proper' glib */
28
29 #include <stdlib.h>
30
31 #include "internals.h"
32
33 static
34 gint first_function (gconstpointer a,
35 gconstpointer b);
36
37 static
38 gint last_function (gconstpointer a,
39 gconstpointer b);
40
41 static int FREE_LIST_ALLOCATE_CHUNK = 1024;
42
43 GSList * free_list = NULL;
44 GSList * allocated_list = NULL;
45
46 #ifdef HAVE_STDATOMIC_H
47
48 static atomic_char atomic_locker = ATOMIC_VAR_INIT(0);
49
50 #define lock() atomic_lock( &atomic_locker )
51 #define unlock() atomic_unlock( &atomic_locker )
52
53 #else /* #ifdef HAVE_STDATOMIC_H */
54
55 #define lock()
56 #define unlock()
57
58 #endif /* #ifdef HAVE_STDATOMIC_H */
59
60 static
allocate_free(void)61 void allocate_free ( void ) {
62 lock();
63 if(!free_list) {
64 int i;
65 free_list=libspectrum_malloc(FREE_LIST_ALLOCATE_CHUNK*sizeof(GSList));
66 allocated_list = free_list;
67 for(i=0;i<FREE_LIST_ALLOCATE_CHUNK-1;i++)
68 free_list[i].next=&free_list[i+1];
69 free_list[FREE_LIST_ALLOCATE_CHUNK-1].next=NULL;
70 }
71 unlock();
72 }
73
74
g_slist_insert(GSList * list,gpointer data,gint position)75 GSList* g_slist_insert (GSList *list,
76 gpointer data,
77 gint position) {
78
79 GSList *prev_list;
80 GSList *tmp_list;
81 GSList *new_list;
82
83 if (position < 0)
84 return g_slist_append (list, data);
85 else if (position == 0)
86 return g_slist_prepend (list, data);
87
88 allocate_free();
89
90 lock();
91 new_list = free_list;
92 free_list=free_list->next;
93 unlock();
94 new_list->data = data;
95 new_list->next=NULL;
96
97 if (!list)
98 {
99 return new_list;
100 }
101
102 prev_list = NULL;
103 tmp_list = list;
104
105 while ((position-- > 0) && tmp_list)
106 {
107 prev_list = tmp_list;
108 tmp_list = tmp_list->next;
109 }
110
111 if (prev_list)
112 {
113 new_list->next = prev_list->next;
114 prev_list->next = new_list;
115 }
116 else
117 {
118 new_list->next = list;
119 list = new_list;
120 }
121
122 return list;
123 }
124
g_slist_insert_sorted(GSList * list,gpointer data,GCompareFunc func)125 GSList* g_slist_insert_sorted (GSList *list,
126 gpointer data,
127 GCompareFunc func) {
128
129 GSList *tmp_list = list;
130 GSList *prev_list = NULL;
131 GSList *new_list;
132 gint cmp;
133
134 allocate_free();
135
136 if(!func) return list;
137
138 if (!list)
139 {
140 lock();
141 new_list = free_list;
142 free_list=free_list->next;
143 unlock();
144 new_list->data = data;
145 new_list->next=NULL;
146 return new_list;
147 }
148
149 cmp = (*func) (data, tmp_list->data);
150
151 while ((tmp_list->next) && (cmp > 0))
152 {
153 prev_list = tmp_list;
154 tmp_list = tmp_list->next;
155 cmp = (*func) (data, tmp_list->data);
156 }
157
158 lock();
159 new_list = free_list;
160 free_list=free_list->next;
161 unlock();
162 new_list->data = data;
163
164 if ((!tmp_list->next) && (cmp > 0))
165 {
166 tmp_list->next = new_list;
167 new_list->next=NULL;
168 return list;
169 }
170
171 if (prev_list)
172 {
173 prev_list->next = new_list;
174 new_list->next = tmp_list;
175 return list;
176 }
177 else
178 {
179 new_list->next = list;
180 return new_list;
181 }
182 }
183
g_slist_append(GSList * list,gpointer data)184 GSList* g_slist_append (GSList *list,
185 gpointer data) {
186
187 return g_slist_insert_sorted(list, data, last_function);
188 }
189
g_slist_prepend(GSList * list,gpointer data)190 GSList* g_slist_prepend (GSList *list,
191 gpointer data) {
192
193 return g_slist_insert_sorted(list, data, first_function);
194 }
195
196 static
first_function(gconstpointer a,gconstpointer b)197 gint first_function (gconstpointer a,
198 gconstpointer b) {
199
200 return -1;
201 }
202
203 static
last_function(gconstpointer a,gconstpointer b)204 gint last_function (gconstpointer a,
205 gconstpointer b) {
206
207 return 1;
208 }
209
g_slist_remove(GSList * list,gconstpointer data)210 GSList* g_slist_remove (GSList *list,
211 gconstpointer data) {
212
213 GSList *tmp;
214 GSList *prev;
215
216 prev = NULL;
217 tmp = list;
218
219 while (tmp)
220 {
221 if (tmp->data == data)
222 {
223 if (prev)
224 prev->next = tmp->next;
225 if (list == tmp)
226 list = list->next;
227
228 tmp->next = NULL;
229 g_slist_free (tmp);
230
231 break;
232 }
233
234 prev = tmp;
235 tmp = tmp->next;
236 }
237
238 return list;
239 }
240
g_slist_delete_link(GSList * list,GSList * link)241 GSList* g_slist_delete_link (GSList *list,
242 GSList *link) {
243
244 GSList *tmp;
245 GSList *prev;
246
247 prev = NULL;
248 tmp = list;
249
250 while (tmp)
251 {
252 if (tmp == link)
253 {
254 if (prev)
255 prev->next = tmp->next;
256 if (list == tmp)
257 list = list->next;
258
259 tmp->next = NULL;
260 g_slist_free (tmp);
261 break;
262 }
263
264 prev = tmp;
265 tmp = tmp->next;
266 }
267
268 return list;
269 }
270
271 GSList*
g_slist_last(GSList * list)272 g_slist_last (GSList *list)
273 {
274 if (list)
275 {
276 while (list->next)
277 list = list->next;
278 }
279
280 return list;
281 }
282
283 guint
g_slist_length(GSList * list)284 g_slist_length (GSList *list)
285 {
286 guint length;
287
288 length = 0;
289 while (list)
290 {
291 length++;
292 list = list->next;
293 }
294
295 return length;
296 }
297
g_slist_foreach(GSList * list,GFunc func,gpointer user_data)298 void g_slist_foreach (GSList *list,
299 GFunc func,
300 gpointer user_data) {
301
302 while (list)
303 {
304 (*func) (list->data, user_data);
305 list = list->next;
306 }
307 }
308
g_slist_free(GSList * list)309 void g_slist_free (GSList *list) {
310 if (list)
311 {
312 GSList *last_node = list;
313
314 while( last_node->next )
315 last_node = last_node->next;
316
317 lock();
318 last_node->next = free_list;
319 free_list = list;
320 unlock();
321 }
322 }
323
324 GSList*
g_slist_reverse(GSList * list)325 g_slist_reverse (GSList *list)
326 {
327 GSList *prev = NULL;
328
329 while (list)
330 {
331 GSList *next = list->next;
332
333 list->next = prev;
334
335 prev = list;
336 list = next;
337 }
338
339 return prev;
340 }
341
g_slist_nth(GSList * list,guint n)342 GSList* g_slist_nth (GSList *list,
343 guint n) {
344 for( ; n; n-- ) {
345 if( list == NULL ) return NULL;
346 list = list->next;
347 }
348
349 return list;
350 }
351
g_slist_find_custom(GSList * list,gconstpointer data,GCompareFunc func)352 GSList* g_slist_find_custom (GSList *list,
353 gconstpointer data,
354 GCompareFunc func ) {
355 while (list)
356 {
357 if (!(*func) (list->data, data)) return list;
358 list = list->next;
359 }
360
361 return NULL;
362 }
363
g_slist_position(GSList * list,GSList * llink)364 gint g_slist_position (GSList *list,
365 GSList *llink) {
366 int n;
367
368 n = 0;
369
370 while( list ) {
371 if( list == llink ) return n;
372 list = list->next;
373 n++;
374 }
375
376 return -1;
377 }
378
379 void
libspectrum_slist_cleanup(void)380 libspectrum_slist_cleanup( void )
381 {
382 lock();
383 libspectrum_free( allocated_list );
384 allocated_list = NULL;
385 free_list = NULL;
386 unlock();
387 }
388
389 #endif /* #ifndef HAVE_LIB_GLIB */
390