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 Lesser 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 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser 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-2000. 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);
146 return _g_list_alloc ();
150 g_list_free (GList *list)
154 GList *last_node = list;
156 #ifdef ENABLE_GC_FRIENDLY
157 while (last_node->next)
159 last_node->data = NULL;
160 last_node->prev = NULL;
161 last_node = last_node->next;
163 last_node->data = NULL
164 last_node->prev = NULL
165 #else /* !ENABLE_GC_FRIENDLY */
166 list->data = list->next;
167 #endif /* ENABLE_GC_FRIENDLY */
169 G_LOCK (current_allocator);
170 last_node->next = current_allocator->free_lists;
171 current_allocator->free_lists = list;
172 G_UNLOCK (current_allocator);
177 _g_list_free_1 (GList *list)
183 #ifdef ENABLE_GC_FRIENDLY
185 #endif /* ENABLE_GC_FRIENDLY */
187 G_LOCK (current_allocator);
188 list->next = current_allocator->free_lists;
189 current_allocator->free_lists = list;
190 G_UNLOCK (current_allocator);
195 g_list_free_1 (GList *list)
197 _g_list_free_1 (list);
201 g_list_append (GList *list,
207 new_list = _g_list_alloc ();
208 new_list->data = data;
212 last = g_list_last (list);
213 /* g_assert (last != NULL); */
214 last->next = new_list;
215 new_list->prev = last;
224 g_list_prepend (GList *list,
229 new_list = _g_list_alloc ();
230 new_list->data = data;
236 list->prev->next = new_list;
237 new_list->prev = list->prev;
239 list->prev = new_list;
240 new_list->next = list;
247 g_list_insert (GList *list,
255 return g_list_append (list, data);
256 else if (position == 0)
257 return g_list_prepend (list, data);
259 tmp_list = g_list_nth (list, position);
261 return g_list_append (list, data);
263 new_list = _g_list_alloc ();
264 new_list->data = data;
268 tmp_list->prev->next = new_list;
269 new_list->prev = tmp_list->prev;
271 new_list->next = tmp_list;
272 tmp_list->prev = new_list;
274 if (tmp_list == list)
281 g_list_concat (GList *list1, GList *list2)
287 tmp_list = g_list_last (list1);
289 tmp_list->next = list2;
292 list2->prev = tmp_list;
299 g_list_remove (GList *list,
307 if (tmp->data != data)
312 tmp->prev->next = tmp->next;
314 tmp->next->prev = tmp->prev;
319 _g_list_free_1 (tmp);
328 _g_list_remove_link (GList *list,
334 link->prev->next = link->next;
336 link->next->prev = link->prev;
349 g_list_remove_link (GList *list,
352 return _g_list_remove_link (list, link);
356 g_list_delete_link (GList *list,
359 list = _g_list_remove_link (list, link);
360 _g_list_free_1 (link);
366 g_list_copy (GList *list)
368 GList *new_list = NULL;
374 new_list = _g_list_alloc ();
375 new_list->data = list->data;
380 last->next = _g_list_alloc ();
381 last->next->prev = last;
383 last->data = list->data;
392 g_list_reverse (GList *list)
401 last->next = last->prev;
409 g_list_nth (GList *list,
412 while ((n-- > 0) && list)
419 g_list_nth_data (GList *list,
422 while ((n-- > 0) && list)
425 return list ? list->data : NULL;
429 g_list_find (GList *list,
434 if (list->data == data)
443 g_list_find_custom (GList *list,
447 g_return_val_if_fail (func != NULL, list);
451 if (! func (list->data, data))
461 g_list_position (GList *list,
479 g_list_index (GList *list,
487 if (list->data == data)
497 g_list_last (GList *list)
509 g_list_first (GList *list)
521 g_list_length (GList *list)
536 g_list_foreach (GList *list,
542 (*func) (list->data, user_data);
549 g_list_insert_sorted (GList *list,
553 GList *tmp_list = list;
557 g_return_val_if_fail (func != NULL, list);
561 new_list = _g_list_alloc ();
562 new_list->data = data;
566 cmp = (*func) (data, tmp_list->data);
568 while ((tmp_list->next) && (cmp > 0))
570 tmp_list = tmp_list->next;
571 cmp = (*func) (data, tmp_list->data);
574 new_list = _g_list_alloc ();
575 new_list->data = data;
577 if ((!tmp_list->next) && (cmp > 0))
579 tmp_list->next = new_list;
580 new_list->prev = tmp_list;
586 tmp_list->prev->next = new_list;
587 new_list->prev = tmp_list->prev;
589 new_list->next = tmp_list;
590 tmp_list->prev = new_list;
592 if (tmp_list == list)
599 g_list_sort_merge (GList *l1,
605 GList list, *l, *lprev;
614 cmp = ((GCompareFuncData) compare_func) (l1->data, l2->data, user_data);
616 cmp = ((GCompareFunc) compare_func) (l1->data, l2->data);
635 l->next = l1 ? l1 : l2;
642 g_list_sort_real (GList *list,
657 while ((l2 = l2->next) != NULL)
659 if ((l2 = l2->next) == NULL)
666 return g_list_sort_merge (g_list_sort_real (list, compare_func, use_data, user_data),
667 g_list_sort_real (l2, compare_func, use_data, user_data),
674 g_list_sort (GList *list,
675 GCompareFunc compare_func)
677 return g_list_sort_real (list, (GFunc) compare_func, FALSE, NULL);
682 g_list_sort_with_data (GList *list,
683 GCompareFuncData compare_func,
686 return g_list_sort_real (list, (GFunc) compare_func, TRUE, user_data);
690 g_list_sort2 (GList *list,
691 GCompareFunc compare_func)
696 /* Degenerate case. */
697 if (!list) return NULL;
699 /* Assume: list = [12,2,4,11,2,4,6,1,1,12]. */
700 for (tmp = list; tmp; )
704 tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
707 runs = g_slist_append (runs, tmp);
711 /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]]. */
715 /* We have more than one run. Merge pairwise. */
716 GSList *dst, *src, *dstprev = NULL;
718 while (src && src->next)
720 dst->data = g_list_sort_merge (src->data,
722 (GFunc) compare_func,
726 src = src->next->next;
729 /* If number of runs was odd, just keep the last. */
732 dst->data = src->data;
737 dstprev->next = NULL;
741 /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]]. */
742 /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]]. */