1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library 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 GNU
12 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
22 typedef struct _GRealListAllocator GRealListAllocator;
24 struct _GRealListAllocator
26 GMemChunk *list_mem_chunk;
31 static GRealListAllocator *default_allocator = NULL;
32 static GRealListAllocator *current_allocator = NULL;
36 g_list_allocator_new (void)
38 GRealListAllocator* allocator = g_new (GRealListAllocator, 1);
40 allocator->list_mem_chunk = NULL;
41 allocator->free_list = NULL;
43 return (GListAllocator*) allocator;
47 g_list_allocator_free (GListAllocator* fallocator)
49 GRealListAllocator* allocator = (GRealListAllocator *) fallocator;
51 if (allocator && allocator->list_mem_chunk)
52 g_mem_chunk_destroy (allocator->list_mem_chunk);
58 g_list_set_allocator (GListAllocator* fallocator)
60 GRealListAllocator* allocator = (GRealListAllocator *) fallocator;
61 GRealListAllocator* old_allocator = current_allocator;
64 current_allocator = allocator;
67 if (!default_allocator)
68 default_allocator = (GRealListAllocator*) g_list_allocator_new ();
69 current_allocator = default_allocator;
72 if (!current_allocator->list_mem_chunk)
73 current_allocator->list_mem_chunk = g_mem_chunk_new ("list mem chunk",
78 return (GListAllocator*) (old_allocator == default_allocator ? NULL : old_allocator);
87 g_list_set_allocator (NULL);
88 if (current_allocator->free_list)
90 new_list = current_allocator->free_list;
91 current_allocator->free_list = current_allocator->free_list->next;
95 new_list = g_chunk_new (GList, current_allocator->list_mem_chunk);
98 new_list->data = NULL;
99 new_list->next = NULL;
100 new_list->prev = NULL;
106 g_list_free (GList *list)
112 last = g_list_last (list);
113 last->next = current_allocator->free_list;
114 current_allocator->free_list = list;
119 g_list_free_1 (GList *list)
123 list->next = current_allocator->free_list;
124 current_allocator->free_list = list;
129 g_list_append (GList *list,
135 new_list = g_list_alloc ();
136 new_list->data = data;
140 last = g_list_last (list);
141 /* g_assert (last != NULL); */
142 last->next = new_list;
143 new_list->prev = last;
152 g_list_prepend (GList *list,
157 new_list = g_list_alloc ();
158 new_list->data = data;
164 list->prev->next = new_list;
165 new_list->prev = list->prev;
167 list->prev = new_list;
168 new_list->next = list;
175 g_list_insert (GList *list,
183 return g_list_append (list, data);
184 else if (position == 0)
185 return g_list_prepend (list, data);
187 tmp_list = g_list_nth (list, position);
189 return g_list_append (list, data);
191 new_list = g_list_alloc ();
192 new_list->data = data;
196 tmp_list->prev->next = new_list;
197 new_list->prev = tmp_list->prev;
199 new_list->next = tmp_list;
200 tmp_list->prev = new_list;
202 if (tmp_list == list)
209 g_list_concat (GList *list1, GList *list2)
215 tmp_list = g_list_last (list1);
217 tmp_list->next = list2;
220 list2->prev = tmp_list;
227 g_list_remove (GList *list,
235 if (tmp->data != data)
240 tmp->prev->next = tmp->next;
242 tmp->next->prev = tmp->prev;
256 g_list_remove_link (GList *list,
262 link->prev->next = link->next;
264 link->next->prev = link->prev;
277 g_list_copy (GList *list)
279 GList *new_list = NULL;
285 new_list = g_list_alloc ();
286 new_list->data = list->data;
291 last->next = g_list_alloc ();
292 last->next->prev = last;
294 last->data = list->data;
303 g_list_reverse (GList *list)
312 last->next = last->prev;
320 g_list_nth (GList *list,
323 while ((n-- > 0) && list)
330 g_list_nth_data (GList *list,
333 while ((n-- > 0) && list)
336 return list ? list->data : NULL;
340 g_list_find (GList *list,
345 if (list->data == data)
354 g_list_find_custom (GList *list,
358 g_return_val_if_fail (func != NULL, list);
362 if (! func (list->data, data))
372 g_list_position (GList *list,
390 g_list_index (GList *list,
398 if (list->data == data)
408 g_list_last (GList *list)
420 g_list_first (GList *list)
432 g_list_length (GList *list)
447 g_list_foreach (GList *list,
453 (*func) (list->data, user_data);
460 g_list_insert_sorted (GList *list,
464 GList *tmp_list = list;
468 g_return_val_if_fail (func != NULL, list);
472 new_list = g_list_alloc();
473 new_list->data = data;
477 cmp = (*func) (data, tmp_list->data);
479 while ((tmp_list->next) && (cmp > 0))
481 tmp_list = tmp_list->next;
482 cmp = (*func) (data, tmp_list->data);
485 new_list = g_list_alloc();
486 new_list->data = data;
488 if ((!tmp_list->next) && (cmp > 0))
490 tmp_list->next = new_list;
491 new_list->prev = tmp_list;
497 tmp_list->prev->next = new_list;
498 new_list->prev = tmp_list->prev;
500 new_list->next = tmp_list;
501 tmp_list->prev = new_list;
503 if (tmp_list == list)
510 g_list_sort_merge (GList *l1,
512 GCompareFunc compare_func)
514 GList list, *l, *lprev;
521 if (compare_func (l1->data, l2->data) < 0)
538 l->next = l1 ? l1 : l2;
545 g_list_sort (GList *list,
546 GCompareFunc compare_func)
558 while ((l2 = l2->next) != NULL)
560 if ((l2 = l2->next) == NULL)
567 return g_list_sort_merge (g_list_sort (list, compare_func),
568 g_list_sort (l2, compare_func),