1 /* gslist.c: Minimal replacement for GSList
2 Copyright (c) 2001-2004 Matan Ziv-Av, Philip Kendall, Marek Januszewski
3
4 $Id: gslist.c 4695 2012-05-07 02:03:10Z fredm $
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 Author contact information:
21
22 E-mail: philip-fuse@shadowmagic.org.uk
23
24 */
25
26 #include <config.h>
27
28 #ifndef HAVE_LIB_GLIB /* Use this iff we're not using the
29 `proper' glib */
30
31 #include <stdlib.h>
32
33 #include "internals.h"
34
35 static
36 gint first_function (gconstpointer a,
37 gconstpointer b);
38
39 static
40 gint last_function (gconstpointer a,
41 gconstpointer b);
42
43 static int FREE_LIST_ALLOCATE_CHUNK = 1024;
44
45 GSList * free_list = NULL;
46 GSList * allocated_list = NULL;
47
48 static
allocate_free(void)49 void allocate_free ( void ) {
50 if(!free_list) {
51 int i;
52 free_list=libspectrum_malloc(FREE_LIST_ALLOCATE_CHUNK*sizeof(GSList));
53 allocated_list = free_list;
54 for(i=0;i<FREE_LIST_ALLOCATE_CHUNK-1;i++)
55 free_list[i].next=&free_list[i+1];
56 free_list[FREE_LIST_ALLOCATE_CHUNK-1].next=NULL;
57 }
58 }
59
60
g_slist_insert(GSList * list,gpointer data,gint position)61 GSList* g_slist_insert (GSList *list,
62 gpointer data,
63 gint position) {
64
65 GSList *prev_list;
66 GSList *tmp_list;
67 GSList *new_list;
68
69 if (position < 0)
70 return g_slist_append (list, data);
71 else if (position == 0)
72 return g_slist_prepend (list, data);
73
74 allocate_free();
75
76 new_list = free_list;
77 free_list=free_list->next;
78 new_list->data = data;
79 new_list->next=NULL;
80
81 if (!list)
82 {
83 return new_list;
84 }
85
86 prev_list = NULL;
87 tmp_list = list;
88
89 while ((position-- > 0) && tmp_list)
90 {
91 prev_list = tmp_list;
92 tmp_list = tmp_list->next;
93 }
94
95 if (prev_list)
96 {
97 new_list->next = prev_list->next;
98 prev_list->next = new_list;
99 }
100 else
101 {
102 new_list->next = list;
103 list = new_list;
104 }
105
106 return list;
107 }
108
g_slist_insert_sorted(GSList * list,gpointer data,GCompareFunc func)109 GSList* g_slist_insert_sorted (GSList *list,
110 gpointer data,
111 GCompareFunc func) {
112
113 GSList *tmp_list = list;
114 GSList *prev_list = NULL;
115 GSList *new_list;
116 gint cmp;
117
118 allocate_free();
119
120 if(!func) return list;
121
122 if (!list)
123 {
124 new_list = free_list;
125 free_list=free_list->next;
126 new_list->data = data;
127 new_list->next=NULL;
128 return new_list;
129 }
130
131 cmp = (*func) (data, tmp_list->data);
132
133 while ((tmp_list->next) && (cmp > 0))
134 {
135 prev_list = tmp_list;
136 tmp_list = tmp_list->next;
137 cmp = (*func) (data, tmp_list->data);
138 }
139
140 new_list = free_list;
141 free_list=free_list->next;
142 new_list->data = data;
143
144 if ((!tmp_list->next) && (cmp > 0))
145 {
146 tmp_list->next = new_list;
147 new_list->next=NULL;
148 return list;
149 }
150
151 if (prev_list)
152 {
153 prev_list->next = new_list;
154 new_list->next = tmp_list;
155 return list;
156 }
157 else
158 {
159 new_list->next = list;
160 return new_list;
161 }
162 }
163
g_slist_append(GSList * list,gpointer data)164 GSList* g_slist_append (GSList *list,
165 gpointer data) {
166
167 return g_slist_insert_sorted(list, data, last_function);
168 }
169
g_slist_prepend(GSList * list,gpointer data)170 GSList* g_slist_prepend (GSList *list,
171 gpointer data) {
172
173 return g_slist_insert_sorted(list, data, first_function);
174 }
175
176 static
first_function(gconstpointer a,gconstpointer b)177 gint first_function (gconstpointer a,
178 gconstpointer b) {
179
180 return -1;
181 }
182
183 static
last_function(gconstpointer a,gconstpointer b)184 gint last_function (gconstpointer a,
185 gconstpointer b) {
186
187 return 1;
188 }
189
g_slist_remove(GSList * list,gconstpointer data)190 GSList* g_slist_remove (GSList *list,
191 gconstpointer data) {
192
193 GSList *tmp;
194 GSList *prev;
195
196 prev = NULL;
197 tmp = list;
198
199 while (tmp)
200 {
201 if (tmp->data == data)
202 {
203 if (prev)
204 prev->next = tmp->next;
205 if (list == tmp)
206 list = list->next;
207
208 tmp->next = NULL;
209 g_slist_free (tmp);
210
211 break;
212 }
213
214 prev = tmp;
215 tmp = tmp->next;
216 }
217
218 return list;
219 }
220
g_slist_delete_link(GSList * list,GSList * link)221 GSList* g_slist_delete_link (GSList *list,
222 GSList *link) {
223
224 GSList *tmp;
225 GSList *prev;
226
227 prev = NULL;
228 tmp = list;
229
230 while (tmp)
231 {
232 if (tmp == link)
233 {
234 if (prev)
235 prev->next = tmp->next;
236 if (list == tmp)
237 list = list->next;
238
239 tmp->next = NULL;
240 g_slist_free (tmp);
241 break;
242 }
243
244 prev = tmp;
245 tmp = tmp->next;
246 }
247
248 return list;
249 }
250
251 GSList*
g_slist_last(GSList * list)252 g_slist_last (GSList *list)
253 {
254 if (list)
255 {
256 while (list->next)
257 list = list->next;
258 }
259
260 return list;
261 }
262
263 guint
g_slist_length(GSList * list)264 g_slist_length (GSList *list)
265 {
266 guint length;
267
268 length = 0;
269 while (list)
270 {
271 length++;
272 list = list->next;
273 }
274
275 return length;
276 }
277
g_slist_foreach(GSList * list,GFunc func,gpointer user_data)278 void g_slist_foreach (GSList *list,
279 GFunc func,
280 gpointer user_data) {
281
282 while (list)
283 {
284 (*func) (list->data, user_data);
285 list = list->next;
286 }
287 }
288
g_slist_free(GSList * list)289 void g_slist_free (GSList *list) {
290 if (list)
291 {
292 GSList *last_node = list;
293
294 while( last_node->next )
295 last_node = last_node->next;
296
297 last_node->next = free_list;
298 free_list = list;
299 }
300 }
301
302 GSList*
g_slist_reverse(GSList * list)303 g_slist_reverse (GSList *list)
304 {
305 GSList *prev = NULL;
306
307 while (list)
308 {
309 GSList *next = list->next;
310
311 list->next = prev;
312
313 prev = list;
314 list = next;
315 }
316
317 return prev;
318 }
319
g_slist_nth(GSList * list,guint n)320 GSList* g_slist_nth (GSList *list,
321 guint n) {
322 for( ; n; n-- ) {
323 if( list == NULL ) return NULL;
324 list = list->next;
325 }
326
327 return list;
328 }
329
g_slist_find_custom(GSList * list,gconstpointer data,GCompareFunc func)330 GSList* g_slist_find_custom (GSList *list,
331 gconstpointer data,
332 GCompareFunc func ) {
333 while (list)
334 {
335 if (!(*func) (list->data, data)) return list;
336 list = list->next;
337 }
338
339 return NULL;
340 }
341
g_slist_position(GSList * list,GSList * llink)342 gint g_slist_position (GSList *list,
343 GSList *llink) {
344 int n;
345
346 n = 0;
347
348 while( list ) {
349 if( list == llink ) return n;
350 list = list->next;
351 n++;
352 }
353
354 return -1;
355 }
356
357 void
libspectrum_slist_cleanup(void)358 libspectrum_slist_cleanup( void )
359 {
360 libspectrum_free( allocated_list );
361 allocated_list = NULL;
362 free_list = NULL;
363 }
364
365 #endif /* #ifndef HAVE_LIB_GLIB */
366