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
);
146 return _g_list_alloc ();
150 g_list_free (GList
*list
)
154 list
->data
= list
->next
;
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_list_free_1 (GList
*list
)
168 G_LOCK (current_allocator
);
169 list
->next
= current_allocator
->free_lists
;
170 current_allocator
->free_lists
= list
;
171 G_UNLOCK (current_allocator
);
176 g_list_free_1 (GList
*list
)
178 _g_list_free_1 (list
);
182 g_list_append (GList
*list
,
188 new_list
= _g_list_alloc ();
189 new_list
->data
= data
;
193 last
= g_list_last (list
);
194 /* g_assert (last != NULL); */
195 last
->next
= new_list
;
196 new_list
->prev
= last
;
205 g_list_prepend (GList
*list
,
210 new_list
= _g_list_alloc ();
211 new_list
->data
= data
;
217 list
->prev
->next
= new_list
;
218 new_list
->prev
= list
->prev
;
220 list
->prev
= new_list
;
221 new_list
->next
= list
;
228 g_list_insert (GList
*list
,
236 return g_list_append (list
, data
);
237 else if (position
== 0)
238 return g_list_prepend (list
, data
);
240 tmp_list
= g_list_nth (list
, position
);
242 return g_list_append (list
, data
);
244 new_list
= _g_list_alloc ();
245 new_list
->data
= data
;
249 tmp_list
->prev
->next
= new_list
;
250 new_list
->prev
= tmp_list
->prev
;
252 new_list
->next
= tmp_list
;
253 tmp_list
->prev
= new_list
;
255 if (tmp_list
== list
)
262 g_list_concat (GList
*list1
, GList
*list2
)
268 tmp_list
= g_list_last (list1
);
270 tmp_list
->next
= list2
;
273 list2
->prev
= tmp_list
;
280 g_list_remove (GList
*list
,
288 if (tmp
->data
!= data
)
293 tmp
->prev
->next
= tmp
->next
;
295 tmp
->next
->prev
= tmp
->prev
;
300 _g_list_free_1 (tmp
);
309 _g_list_remove_link (GList
*list
,
315 link
->prev
->next
= link
->next
;
317 link
->next
->prev
= link
->prev
;
330 g_list_remove_link (GList
*list
,
333 return _g_list_remove_link (list
, link
);
337 g_list_delete_link (GList
*list
,
340 list
= _g_list_remove_link (list
, link
);
341 _g_list_free_1 (link
);
347 g_list_copy (GList
*list
)
349 GList
*new_list
= NULL
;
355 new_list
= _g_list_alloc ();
356 new_list
->data
= list
->data
;
361 last
->next
= _g_list_alloc ();
362 last
->next
->prev
= last
;
364 last
->data
= list
->data
;
373 g_list_reverse (GList
*list
)
382 last
->next
= last
->prev
;
390 g_list_nth (GList
*list
,
393 while ((n
-- > 0) && list
)
400 g_list_nth_data (GList
*list
,
403 while ((n
-- > 0) && list
)
406 return list
? list
->data
: NULL
;
410 g_list_find (GList
*list
,
415 if (list
->data
== data
)
424 g_list_find_custom (GList
*list
,
428 g_return_val_if_fail (func
!= NULL
, list
);
432 if (! func (list
->data
, data
))
442 g_list_position (GList
*list
,
460 g_list_index (GList
*list
,
468 if (list
->data
== data
)
478 g_list_last (GList
*list
)
490 g_list_first (GList
*list
)
502 g_list_length (GList
*list
)
517 g_list_foreach (GList
*list
,
523 (*func
) (list
->data
, user_data
);
530 g_list_insert_sorted (GList
*list
,
534 GList
*tmp_list
= list
;
538 g_return_val_if_fail (func
!= NULL
, list
);
542 new_list
= _g_list_alloc ();
543 new_list
->data
= data
;
547 cmp
= (*func
) (data
, tmp_list
->data
);
549 while ((tmp_list
->next
) && (cmp
> 0))
551 tmp_list
= tmp_list
->next
;
552 cmp
= (*func
) (data
, tmp_list
->data
);
555 new_list
= _g_list_alloc ();
556 new_list
->data
= data
;
558 if ((!tmp_list
->next
) && (cmp
> 0))
560 tmp_list
->next
= new_list
;
561 new_list
->prev
= tmp_list
;
567 tmp_list
->prev
->next
= new_list
;
568 new_list
->prev
= tmp_list
->prev
;
570 new_list
->next
= tmp_list
;
571 tmp_list
->prev
= new_list
;
573 if (tmp_list
== list
)
580 g_list_sort_merge (GList
*l1
,
582 GCompareFunc compare_func
)
584 GList list
, *l
, *lprev
;
591 if (compare_func (l1
->data
, l2
->data
) < 0)
608 l
->next
= l1
? l1
: l2
;
615 g_list_sort (GList
*list
,
616 GCompareFunc compare_func
)
628 while ((l2
= l2
->next
) != NULL
)
630 if ((l2
= l2
->next
) == NULL
)
637 return g_list_sort_merge (g_list_sort (list
, compare_func
),
638 g_list_sort (l2
, compare_func
),
643 g_list_sort2 (GList
*list
,
644 GCompareFunc compare_func
)
649 /* Degenerate case. */
650 if (!list
) return NULL
;
652 /* Assume: list = [12,2,4,11,2,4,6,1,1,12]. */
653 for (tmp
= list
; tmp
; )
657 tmp2
->next
&& compare_func (tmp2
->data
, tmp2
->next
->data
) <= 0;
660 runs
= g_slist_append (runs
, tmp
);
664 /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]]. */
668 /* We have more than one run. Merge pairwise. */
669 GSList
*dst
, *src
, *dstprev
= NULL
;
671 while (src
&& src
->next
)
673 dst
->data
= g_list_sort_merge (src
->data
,
678 src
= src
->next
->next
;
681 /* If number of runs was odd, just keep the last. */
684 dst
->data
= src
->data
;
689 dstprev
->next
= NULL
;
693 /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]]. */
694 /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]]. */