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/.
38 #ifndef DISABLE_MEM_POOLS
39 struct _GAllocator
/* from gmem.c */
47 GList
*free_lists
; /* implementation specific */
50 static GAllocator
*current_allocator
= NULL
;
51 G_LOCK_DEFINE_STATIC (current_allocator
);
53 /* HOLDS: current_allocator_lock */
55 g_list_validate_allocator (GAllocator
*allocator
)
57 g_return_if_fail (allocator
!= NULL
);
58 g_return_if_fail (allocator
->is_unused
== TRUE
);
60 if (allocator
->type
!= G_ALLOCATOR_LIST
)
62 allocator
->type
= G_ALLOCATOR_LIST
;
63 if (allocator
->mem_chunk
)
65 g_mem_chunk_destroy (allocator
->mem_chunk
);
66 allocator
->mem_chunk
= NULL
;
70 if (!allocator
->mem_chunk
)
72 allocator
->mem_chunk
= g_mem_chunk_new (allocator
->name
,
74 sizeof (GList
) * allocator
->n_preallocs
,
76 allocator
->free_lists
= NULL
;
79 allocator
->is_unused
= FALSE
;
83 g_list_push_allocator(GAllocator
*allocator
)
85 G_LOCK (current_allocator
);
86 g_list_validate_allocator (allocator
);
87 allocator
->last
= current_allocator
;
88 current_allocator
= allocator
;
89 G_UNLOCK (current_allocator
);
93 g_list_pop_allocator (void)
95 G_LOCK (current_allocator
);
96 if (current_allocator
)
98 GAllocator
*allocator
;
100 allocator
= current_allocator
;
101 current_allocator
= allocator
->last
;
102 allocator
->last
= NULL
;
103 allocator
->is_unused
= TRUE
;
105 G_UNLOCK (current_allocator
);
113 G_LOCK (current_allocator
);
114 if (!current_allocator
)
116 GAllocator
*allocator
= g_allocator_new ("GLib default GList allocator",
118 g_list_validate_allocator (allocator
);
119 allocator
->last
= NULL
;
120 current_allocator
= allocator
;
122 if (!current_allocator
->free_lists
)
124 list
= g_chunk_new (GList
, current_allocator
->mem_chunk
);
129 if (current_allocator
->free_lists
->data
)
131 list
= current_allocator
->free_lists
->data
;
132 current_allocator
->free_lists
->data
= list
->next
;
137 list
= current_allocator
->free_lists
;
138 current_allocator
->free_lists
= list
->next
;
141 G_UNLOCK (current_allocator
);
151 return _g_list_alloc ();
155 g_list_free (GList
*list
)
159 GList
*last_node
= list
;
161 #ifdef ENABLE_GC_FRIENDLY
162 while (last_node
->next
)
164 last_node
->data
= NULL
;
165 last_node
->prev
= NULL
;
166 last_node
= last_node
->next
;
168 last_node
->data
= NULL
;
169 last_node
->prev
= NULL
;
170 #else /* !ENABLE_GC_FRIENDLY */
171 list
->data
= list
->next
;
172 #endif /* ENABLE_GC_FRIENDLY */
174 G_LOCK (current_allocator
);
175 last_node
->next
= current_allocator
->free_lists
;
176 current_allocator
->free_lists
= list
;
177 G_UNLOCK (current_allocator
);
182 _g_list_free_1 (GList
*list
)
188 #ifdef ENABLE_GC_FRIENDLY
190 #endif /* ENABLE_GC_FRIENDLY */
192 G_LOCK (current_allocator
);
193 list
->next
= current_allocator
->free_lists
;
194 current_allocator
->free_lists
= list
;
195 G_UNLOCK (current_allocator
);
200 g_list_free_1 (GList
*list
)
202 _g_list_free_1 (list
);
205 #else /* DISABLE_MEM_POOLS */
207 #define _g_list_alloc g_list_alloc
213 list
= g_new0 (GList
, 1);
219 g_list_free (GList
*list
)
231 #define _g_list_free_1 g_list_free_1
233 g_list_free_1 (GList
*list
)
241 g_list_append (GList
*list
,
247 new_list
= _g_list_alloc ();
248 new_list
->data
= data
;
252 last
= g_list_last (list
);
253 /* g_assert (last != NULL); */
254 last
->next
= new_list
;
255 new_list
->prev
= last
;
264 g_list_prepend (GList
*list
,
269 new_list
= _g_list_alloc ();
270 new_list
->data
= data
;
276 list
->prev
->next
= new_list
;
277 new_list
->prev
= list
->prev
;
279 list
->prev
= new_list
;
280 new_list
->next
= list
;
287 g_list_insert (GList
*list
,
295 return g_list_append (list
, data
);
296 else if (position
== 0)
297 return g_list_prepend (list
, data
);
299 tmp_list
= g_list_nth (list
, position
);
301 return g_list_append (list
, data
);
303 new_list
= _g_list_alloc ();
304 new_list
->data
= data
;
308 tmp_list
->prev
->next
= new_list
;
309 new_list
->prev
= tmp_list
->prev
;
311 new_list
->next
= tmp_list
;
312 tmp_list
->prev
= new_list
;
314 if (tmp_list
== list
)
321 g_list_concat (GList
*list1
, GList
*list2
)
327 tmp_list
= g_list_last (list1
);
329 tmp_list
->next
= list2
;
332 list2
->prev
= tmp_list
;
339 g_list_remove (GList
*list
,
347 if (tmp
->data
!= data
)
352 tmp
->prev
->next
= tmp
->next
;
354 tmp
->next
->prev
= tmp
->prev
;
359 _g_list_free_1 (tmp
);
368 g_list_remove_all (GList
*list
,
375 if (tmp
->data
!= data
)
379 GList
*next
= tmp
->next
;
382 tmp
->prev
->next
= next
;
386 next
->prev
= tmp
->prev
;
388 _g_list_free_1 (tmp
);
396 _g_list_remove_link (GList
*list
,
402 link
->prev
->next
= link
->next
;
404 link
->next
->prev
= link
->prev
;
417 g_list_remove_link (GList
*list
,
420 return _g_list_remove_link (list
, link
);
424 g_list_delete_link (GList
*list
,
427 list
= _g_list_remove_link (list
, link
);
428 _g_list_free_1 (link
);
434 g_list_copy (GList
*list
)
436 GList
*new_list
= NULL
;
442 new_list
= _g_list_alloc ();
443 new_list
->data
= list
->data
;
448 last
->next
= _g_list_alloc ();
449 last
->next
->prev
= last
;
451 last
->data
= list
->data
;
460 g_list_reverse (GList
*list
)
469 last
->next
= last
->prev
;
477 g_list_nth (GList
*list
,
480 while ((n
-- > 0) && list
)
487 g_list_nth_data (GList
*list
,
490 while ((n
-- > 0) && list
)
493 return list
? list
->data
: NULL
;
497 g_list_find (GList
*list
,
502 if (list
->data
== data
)
511 g_list_find_custom (GList
*list
,
515 g_return_val_if_fail (func
!= NULL
, list
);
519 if (! func (list
->data
, data
))
529 g_list_position (GList
*list
,
547 g_list_index (GList
*list
,
555 if (list
->data
== data
)
565 g_list_last (GList
*list
)
577 g_list_first (GList
*list
)
589 g_list_length (GList
*list
)
604 g_list_foreach (GList
*list
,
610 (*func
) (list
->data
, user_data
);
617 g_list_insert_sorted (GList
*list
,
621 GList
*tmp_list
= list
;
625 g_return_val_if_fail (func
!= NULL
, list
);
629 new_list
= _g_list_alloc ();
630 new_list
->data
= data
;
634 cmp
= (*func
) (data
, tmp_list
->data
);
636 while ((tmp_list
->next
) && (cmp
> 0))
638 tmp_list
= tmp_list
->next
;
639 cmp
= (*func
) (data
, tmp_list
->data
);
642 new_list
= _g_list_alloc ();
643 new_list
->data
= data
;
645 if ((!tmp_list
->next
) && (cmp
> 0))
647 tmp_list
->next
= new_list
;
648 new_list
->prev
= tmp_list
;
654 tmp_list
->prev
->next
= new_list
;
655 new_list
->prev
= tmp_list
->prev
;
657 new_list
->next
= tmp_list
;
658 tmp_list
->prev
= new_list
;
660 if (tmp_list
== list
)
667 g_list_sort_merge (GList
*l1
,
673 GList list
, *l
, *lprev
;
682 cmp
= ((GCompareDataFunc
) compare_func
) (l1
->data
, l2
->data
, user_data
);
684 cmp
= ((GCompareFunc
) compare_func
) (l1
->data
, l2
->data
);
703 l
->next
= l1
? l1
: l2
;
710 g_list_sort_real (GList
*list
,
725 while ((l2
= l2
->next
) != NULL
)
727 if ((l2
= l2
->next
) == NULL
)
734 return g_list_sort_merge (g_list_sort_real (list
, compare_func
, use_data
, user_data
),
735 g_list_sort_real (l2
, compare_func
, use_data
, user_data
),
742 g_list_sort (GList
*list
,
743 GCompareFunc compare_func
)
745 return g_list_sort_real (list
, (GFunc
) compare_func
, FALSE
, NULL
);
750 g_list_sort_with_data (GList
*list
,
751 GCompareDataFunc compare_func
,
754 return g_list_sort_real (list
, (GFunc
) compare_func
, TRUE
, user_data
);
758 g_list_sort2 (GList
*list
,
759 GCompareFunc compare_func
)
764 /* Degenerate case. */
765 if (!list
) return NULL
;
767 /* Assume: list = [12,2,4,11,2,4,6,1,1,12]. */
768 for (tmp
= list
; tmp
; )
772 tmp2
->next
&& compare_func (tmp2
->data
, tmp2
->next
->data
) <= 0;
775 runs
= g_slist_append (runs
, tmp
);
779 /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]]. */
783 /* We have more than one run. Merge pairwise. */
784 GSList
*dst
, *src
, *dstprev
= NULL
;
786 while (src
&& src
->next
)
788 dst
->data
= g_list_sort_merge (src
->data
,
790 (GFunc
) compare_func
,
794 src
= src
->next
->next
;
797 /* If number of runs was odd, just keep the last. */
800 dst
->data
= src
->data
;
805 dstprev
->next
= NULL
;
809 /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]]. */
810 /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]]. */