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
,
601 GCompareFunc compare_func
)
603 GList list
, *l
, *lprev
;
610 if (compare_func (l1
->data
, l2
->data
) < 0)
627 l
->next
= l1
? l1
: l2
;
634 g_list_sort (GList
*list
,
635 GCompareFunc compare_func
)
647 while ((l2
= l2
->next
) != NULL
)
649 if ((l2
= l2
->next
) == NULL
)
656 return g_list_sort_merge (g_list_sort (list
, compare_func
),
657 g_list_sort (l2
, compare_func
),
662 g_list_sort2 (GList
*list
,
663 GCompareFunc compare_func
)
668 /* Degenerate case. */
669 if (!list
) return NULL
;
671 /* Assume: list = [12,2,4,11,2,4,6,1,1,12]. */
672 for (tmp
= list
; tmp
; )
676 tmp2
->next
&& compare_func (tmp2
->data
, tmp2
->next
->data
) <= 0;
679 runs
= g_slist_append (runs
, tmp
);
683 /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]]. */
687 /* We have more than one run. Merge pairwise. */
688 GSList
*dst
, *src
, *dstprev
= NULL
;
690 while (src
&& src
->next
)
692 dst
->data
= g_list_sort_merge (src
->data
,
697 src
= src
->next
->next
;
700 /* If number of runs was odd, just keep the last. */
703 dst
->data
= src
->data
;
708 dstprev
->next
= NULL
;
712 /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]]. */
713 /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]]. */