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.
27 struct _GAllocator /* from gmem.c */
35 GSList *free_lists; /* implementation specific */
38 G_LOCK_DECLARE_STATIC (current_allocator);
39 static GAllocator *current_allocator = NULL;
41 /* HOLDS: current_allocator_lock */
43 g_slist_validate_allocator (GAllocator *allocator)
45 g_return_if_fail (allocator != NULL);
46 g_return_if_fail (allocator->is_unused == TRUE);
48 if (allocator->type != G_ALLOCATOR_SLIST)
50 allocator->type = G_ALLOCATOR_SLIST;
51 if (allocator->mem_chunk)
53 g_mem_chunk_destroy (allocator->mem_chunk);
54 allocator->mem_chunk = NULL;
58 if (!allocator->mem_chunk)
60 allocator->mem_chunk = g_mem_chunk_new (allocator->name,
62 sizeof (GSList) * allocator->n_preallocs,
64 allocator->free_lists = NULL;
67 allocator->is_unused = FALSE;
71 g_slist_push_allocator (GAllocator *allocator)
73 G_LOCK (current_allocator);
74 g_slist_validate_allocator (allocator);
75 allocator->last = current_allocator;
76 current_allocator = allocator;
77 G_UNLOCK (current_allocator);
81 g_slist_pop_allocator (void)
83 G_LOCK (current_allocator);
84 if (current_allocator)
86 GAllocator *allocator;
88 allocator = current_allocator;
89 current_allocator = allocator->last;
90 allocator->last = NULL;
91 allocator->is_unused = TRUE;
93 G_UNLOCK (current_allocator);
101 G_LOCK (current_allocator);
102 if (!current_allocator)
104 GAllocator *allocator = g_allocator_new ("GLib default GSList allocator",
106 g_slist_validate_allocator (allocator);
107 allocator->last = NULL;
108 current_allocator = allocator;
110 if (!current_allocator->free_lists)
112 list = g_chunk_new (GSList, current_allocator->mem_chunk);
117 if (current_allocator->free_lists->data)
119 list = current_allocator->free_lists->data;
120 current_allocator->free_lists->data = list->next;
125 list = current_allocator->free_lists;
126 current_allocator->free_lists = list->next;
129 G_UNLOCK (current_allocator);
137 g_slist_free (GSList *list)
141 list->data = list->next;
142 G_LOCK (current_allocator);
143 list->next = current_allocator->free_lists;
144 current_allocator->free_lists = list;
145 G_UNLOCK (current_allocator);
150 g_slist_free_1 (GSList *list)
155 G_LOCK (current_allocator);
156 list->next = current_allocator->free_lists;
157 current_allocator->free_lists = list;
158 G_UNLOCK (current_allocator);
163 g_slist_append (GSList *list,
169 new_list = g_slist_alloc ();
170 new_list->data = data;
174 last = g_slist_last (list);
175 /* g_assert (last != NULL); */
176 last->next = new_list;
185 g_slist_prepend (GSList *list,
190 new_list = g_slist_alloc ();
191 new_list->data = data;
192 new_list->next = list;
198 g_slist_insert (GSList *list,
207 return g_slist_append (list, data);
208 else if (position == 0)
209 return g_slist_prepend (list, data);
211 new_list = g_slist_alloc ();
212 new_list->data = data;
220 while ((position-- > 0) && tmp_list)
222 prev_list = tmp_list;
223 tmp_list = tmp_list->next;
228 new_list->next = prev_list->next;
229 prev_list->next = new_list;
233 new_list->next = list;
241 g_slist_concat (GSList *list1, GSList *list2)
246 g_slist_last (list1)->next = list2;
255 g_slist_remove (GSList *list,
266 if (tmp->data == data)
269 prev->next = tmp->next;
287 g_slist_remove_link (GSList *list,
301 prev->next = tmp->next;
317 g_slist_copy (GSList *list)
319 GSList *new_list = NULL;
325 new_list = g_slist_alloc ();
326 new_list->data = list->data;
331 last->next = g_slist_alloc ();
333 last->data = list->data;
342 g_slist_reverse (GSList *list)
366 g_slist_nth (GSList *list,
369 while ((n-- > 0) && list)
376 g_slist_nth_data (GSList *list,
379 while ((n-- > 0) && list)
382 return list ? list->data : NULL;
386 g_slist_find (GSList *list,
391 if (list->data == data)
400 g_slist_find_custom (GSList *list,
404 g_return_val_if_fail (func != NULL, list);
408 if (! func (list->data, data))
417 g_slist_position (GSList *list,
435 g_slist_index (GSList *list,
443 if (list->data == data)
453 g_slist_last (GSList *list)
465 g_slist_length (GSList *list)
480 g_slist_foreach (GSList *list,
486 (*func) (list->data, user_data);
492 g_slist_insert_sorted (GSList *list,
496 GSList *tmp_list = list;
497 GSList *prev_list = NULL;
501 g_return_val_if_fail (func != NULL, list);
505 new_list = g_slist_alloc();
506 new_list->data = data;
510 cmp = (*func) (data, tmp_list->data);
512 while ((tmp_list->next) && (cmp > 0))
514 prev_list = tmp_list;
515 tmp_list = tmp_list->next;
516 cmp = (*func) (data, tmp_list->data);
519 new_list = g_slist_alloc();
520 new_list->data = data;
522 if ((!tmp_list->next) && (cmp > 0))
524 tmp_list->next = new_list;
530 prev_list->next = new_list;
531 new_list->next = tmp_list;
536 new_list->next = list;
542 g_slist_sort_merge (GSList *l1,
544 GCompareFunc compare_func)
552 if (compare_func(l1->data,l2->data) < 0)
563 l->next= l1 ? l1 : l2;
569 g_slist_sort (GSList *list,
570 GCompareFunc compare_func)
582 while ((l2 = l2->next) != NULL)
584 if ((l2 = l2->next) == NULL)
591 return g_slist_sort_merge (g_slist_sort (list, compare_func),
592 g_slist_sort (l2, compare_func),