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.
21 * Modified by the GLib Team and others 1997-1999. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
34 struct _GAllocator /* from gmem.c */
42 GList *free_lists; /* implementation specific */
45 static GAllocator *current_allocator = NULL;
46 G_LOCK_DEFINE_STATIC (current_allocator);
48 /* HOLDS: current_allocator_lock */
50 g_list_validate_allocator (GAllocator *allocator)
52 g_return_if_fail (allocator != NULL);
53 g_return_if_fail (allocator->is_unused == TRUE);
55 if (allocator->type != G_ALLOCATOR_LIST)
57 allocator->type = G_ALLOCATOR_LIST;
58 if (allocator->mem_chunk)
60 g_mem_chunk_destroy (allocator->mem_chunk);
61 allocator->mem_chunk = NULL;
65 if (!allocator->mem_chunk)
67 allocator->mem_chunk = g_mem_chunk_new (allocator->name,
69 sizeof (GList) * allocator->n_preallocs,
71 allocator->free_lists = NULL;
74 allocator->is_unused = FALSE;
78 g_list_push_allocator(GAllocator *allocator)
80 G_LOCK (current_allocator);
81 g_list_validate_allocator ( allocator );
82 allocator->last = current_allocator;
83 current_allocator = allocator;
84 G_UNLOCK (current_allocator);
88 g_list_pop_allocator (void)
90 G_LOCK (current_allocator);
91 if (current_allocator)
93 GAllocator *allocator;
95 allocator = current_allocator;
96 current_allocator = allocator->last;
97 allocator->last = NULL;
98 allocator->is_unused = TRUE;
100 G_UNLOCK (current_allocator);
108 G_LOCK (current_allocator);
109 if (!current_allocator)
111 GAllocator *allocator = g_allocator_new ("GLib default GList allocator",
113 g_list_validate_allocator (allocator);
114 allocator->last = NULL;
115 current_allocator = allocator;
117 if (!current_allocator->free_lists)
119 list = g_chunk_new (GList, current_allocator->mem_chunk);
124 if (current_allocator->free_lists->data)
126 list = current_allocator->free_lists->data;
127 current_allocator->free_lists->data = list->next;
132 list = current_allocator->free_lists;
133 current_allocator->free_lists = list->next;
136 G_UNLOCK (current_allocator);
144 g_list_free (GList *list)
148 list->data = list->next;
149 G_LOCK (current_allocator);
150 list->next = current_allocator->free_lists;
151 current_allocator->free_lists = list;
152 G_UNLOCK (current_allocator);
157 g_list_free_1 (GList *list)
162 G_LOCK (current_allocator);
163 list->next = current_allocator->free_lists;
164 current_allocator->free_lists = list;
165 G_UNLOCK (current_allocator);
170 g_list_append (GList *list,
176 new_list = g_list_alloc ();
177 new_list->data = data;
181 last = g_list_last (list);
182 /* g_assert (last != NULL); */
183 last->next = new_list;
184 new_list->prev = last;
193 g_list_prepend (GList *list,
198 new_list = g_list_alloc ();
199 new_list->data = data;
205 list->prev->next = new_list;
206 new_list->prev = list->prev;
208 list->prev = new_list;
209 new_list->next = list;
216 g_list_insert (GList *list,
224 return g_list_append (list, data);
225 else if (position == 0)
226 return g_list_prepend (list, data);
228 tmp_list = g_list_nth (list, position);
230 return g_list_append (list, data);
232 new_list = g_list_alloc ();
233 new_list->data = data;
237 tmp_list->prev->next = new_list;
238 new_list->prev = tmp_list->prev;
240 new_list->next = tmp_list;
241 tmp_list->prev = new_list;
243 if (tmp_list == list)
250 g_list_concat (GList *list1, GList *list2)
256 tmp_list = g_list_last (list1);
258 tmp_list->next = list2;
261 list2->prev = tmp_list;
268 g_list_remove (GList *list,
276 if (tmp->data != data)
281 tmp->prev->next = tmp->next;
283 tmp->next->prev = tmp->prev;
297 g_list_remove_link (GList *list,
303 link->prev->next = link->next;
305 link->next->prev = link->prev;
319 g_list_delete (GList *list, GList *link)
321 list = g_list_remove_link (list, link);
322 g_list_free_1 (link);
329 g_list_copy (GList *list)
331 GList *new_list = NULL;
337 new_list = g_list_alloc ();
338 new_list->data = list->data;
343 last->next = g_list_alloc ();
344 last->next->prev = last;
346 last->data = list->data;
355 g_list_reverse (GList *list)
364 last->next = last->prev;
372 g_list_nth (GList *list,
375 while ((n-- > 0) && list)
382 g_list_nth_data (GList *list,
385 while ((n-- > 0) && list)
388 return list ? list->data : NULL;
392 g_list_find (GList *list,
397 if (list->data == data)
406 g_list_find_custom (GList *list,
410 g_return_val_if_fail (func != NULL, list);
414 if (! func (list->data, data))
424 g_list_position (GList *list,
442 g_list_index (GList *list,
450 if (list->data == data)
460 g_list_last (GList *list)
472 g_list_first (GList *list)
484 g_list_length (GList *list)
499 g_list_foreach (GList *list,
505 (*func) (list->data, user_data);
512 g_list_insert_sorted (GList *list,
516 GList *tmp_list = list;
520 g_return_val_if_fail (func != NULL, list);
524 new_list = g_list_alloc();
525 new_list->data = data;
529 cmp = (*func) (data, tmp_list->data);
531 while ((tmp_list->next) && (cmp > 0))
533 tmp_list = tmp_list->next;
534 cmp = (*func) (data, tmp_list->data);
537 new_list = g_list_alloc();
538 new_list->data = data;
540 if ((!tmp_list->next) && (cmp > 0))
542 tmp_list->next = new_list;
543 new_list->prev = tmp_list;
549 tmp_list->prev->next = new_list;
550 new_list->prev = tmp_list->prev;
552 new_list->next = tmp_list;
553 tmp_list->prev = new_list;
555 if (tmp_list == list)
562 g_list_sort_merge (GList *l1,
564 GCompareFunc compare_func)
566 GList list, *l, *lprev;
573 if (compare_func (l1->data, l2->data) < 0)
590 l->next = l1 ? l1 : l2;
597 g_list_sort (GList *list,
598 GCompareFunc compare_func)
610 while ((l2 = l2->next) != NULL)
612 if ((l2 = l2->next) == NULL)
619 return g_list_sort_merge (g_list_sort (list, compare_func),
620 g_list_sort (l2, compare_func),
625 g_list_sort2 (GList *list,
626 GCompareFunc compare_func)
631 /* Degenerate case. */
632 if (!list) return NULL;
634 /* Assume: list = [12,2,4,11,2,4,6,1,1,12]. */
635 for (tmp = list; tmp; )
639 tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
642 runs = g_slist_append (runs, tmp);
646 /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]]. */
650 /* We have more than one run. Merge pairwise. */
651 GSList *dst, *src, *dstprev = NULL;
653 while (src && src->next)
655 dst->data = g_list_sort_merge (src->data,
660 src = src->next->next;
663 /* If number of runs was odd, just keep the last. */
666 dst->data = src->data;
671 dstprev->next = NULL;
675 /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]]. */
676 /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]]. */