* Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
*
* This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Library General Public
+ * modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Library General Public License for more details.
+ * Lesser General Public License for more details.
*
- * You should have received a copy of the GNU Library General Public
+ * You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
-#include "glib.h"
+/*
+ * Modified by the GLib Team and others 1997-2000. See the AUTHORS
+ * file for a list of people on the GLib Team. See the ChangeLog
+ * files for a list of changes. These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/.
+ */
-typedef struct _GRealListAllocator GRealListAllocator;
+/*
+ * MT safe
+ */
-struct _GRealListAllocator
+#include "glib.h"
+
+
+struct _GAllocator /* from gmem.c */
{
- GMemChunk *list_mem_chunk;
- GList *free_list;
+ gchar *name;
+ guint16 n_preallocs;
+ guint is_unused : 1;
+ guint type : 4;
+ GAllocator *last;
+ GMemChunk *mem_chunk;
+ GList *free_lists; /* implementation specific */
};
+static GAllocator *current_allocator = NULL;
+G_LOCK_DEFINE_STATIC (current_allocator);
-static GRealListAllocator *default_allocator = NULL;
-static GRealListAllocator *current_allocator = NULL;
+/* HOLDS: current_allocator_lock */
+static void
+g_list_validate_allocator (GAllocator *allocator)
+{
+ g_return_if_fail (allocator != NULL);
+ g_return_if_fail (allocator->is_unused == TRUE);
+ if (allocator->type != G_ALLOCATOR_LIST)
+ {
+ allocator->type = G_ALLOCATOR_LIST;
+ if (allocator->mem_chunk)
+ {
+ g_mem_chunk_destroy (allocator->mem_chunk);
+ allocator->mem_chunk = NULL;
+ }
+ }
-GListAllocator*
-g_list_allocator_new (void)
-{
- GRealListAllocator* allocator = g_new (GRealListAllocator, 1);
-
- allocator->list_mem_chunk = NULL;
- allocator->free_list = NULL;
-
- return (GListAllocator*) allocator;
+ if (!allocator->mem_chunk)
+ {
+ allocator->mem_chunk = g_mem_chunk_new (allocator->name,
+ sizeof (GList),
+ sizeof (GList) * allocator->n_preallocs,
+ G_ALLOC_ONLY);
+ allocator->free_lists = NULL;
+ }
+
+ allocator->is_unused = FALSE;
}
void
-g_list_allocator_free (GListAllocator* fallocator)
+g_list_push_allocator(GAllocator *allocator)
{
- GRealListAllocator* allocator = (GRealListAllocator *) fallocator;
-
- if (allocator && allocator->list_mem_chunk)
- g_mem_chunk_destroy (allocator->list_mem_chunk);
- if (allocator)
- g_free (allocator);
+ G_LOCK (current_allocator);
+ g_list_validate_allocator (allocator);
+ allocator->last = current_allocator;
+ current_allocator = allocator;
+ G_UNLOCK (current_allocator);
}
-GListAllocator*
-g_list_set_allocator (GListAllocator* fallocator)
+void
+g_list_pop_allocator (void)
{
- GRealListAllocator* allocator = (GRealListAllocator *) fallocator;
- GRealListAllocator* old_allocator = current_allocator;
-
- if (allocator)
- current_allocator = allocator;
- else
+ G_LOCK (current_allocator);
+ if (current_allocator)
{
- if (!default_allocator)
- default_allocator = (GRealListAllocator*) g_list_allocator_new ();
- current_allocator = default_allocator;
+ GAllocator *allocator;
+
+ allocator = current_allocator;
+ current_allocator = allocator->last;
+ allocator->last = NULL;
+ allocator->is_unused = TRUE;
}
-
- if (!current_allocator->list_mem_chunk)
- current_allocator->list_mem_chunk = g_mem_chunk_new ("list mem chunk",
- sizeof (GList),
- 1024,
- G_ALLOC_ONLY);
-
- return (GListAllocator*) (old_allocator == default_allocator ? NULL : old_allocator);
+ G_UNLOCK (current_allocator);
}
-
-GList*
-g_list_alloc (void)
+static inline GList*
+_g_list_alloc (void)
{
- GList *new_list;
-
- g_list_set_allocator (NULL);
- if (current_allocator->free_list)
+ GList *list;
+
+ G_LOCK (current_allocator);
+ if (!current_allocator)
+ {
+ GAllocator *allocator = g_allocator_new ("GLib default GList allocator",
+ 128);
+ g_list_validate_allocator (allocator);
+ allocator->last = NULL;
+ current_allocator = allocator;
+ }
+ if (!current_allocator->free_lists)
{
- new_list = current_allocator->free_list;
- current_allocator->free_list = current_allocator->free_list->next;
+ list = g_chunk_new (GList, current_allocator->mem_chunk);
+ list->data = NULL;
}
else
{
- new_list = g_chunk_new (GList, current_allocator->list_mem_chunk);
+ if (current_allocator->free_lists->data)
+ {
+ list = current_allocator->free_lists->data;
+ current_allocator->free_lists->data = list->next;
+ list->data = NULL;
+ }
+ else
+ {
+ list = current_allocator->free_lists;
+ current_allocator->free_lists = list->next;
+ }
}
+ G_UNLOCK (current_allocator);
+ list->next = NULL;
+ list->prev = NULL;
- new_list->data = NULL;
- new_list->next = NULL;
- new_list->prev = NULL;
-
- return new_list;
+ return list;
+}
+
+GList*
+g_list_alloc (void)
+{
+ return _g_list_alloc ();
}
void
g_list_free (GList *list)
{
- GList *last;
-
if (list)
{
- last = g_list_last (list);
- last->next = current_allocator->free_list;
- current_allocator->free_list = list;
+ GList *last_node = list;
+
+#ifdef ENABLE_GC_FRIENDLY
+ while (last_node->next)
+ {
+ last_node->data = NULL;
+ last_node->prev = NULL;
+ last_node = last_node->next;
+ }
+ last_node->data = NULL
+ last_node->prev = NULL
+#else /* !ENABLE_GC_FRIENDLY */
+ list->data = list->next;
+#endif /* ENABLE_GC_FRIENDLY */
+
+ G_LOCK (current_allocator);
+ last_node->next = current_allocator->free_lists;
+ current_allocator->free_lists = list;
+ G_UNLOCK (current_allocator);
}
}
-void
-g_list_free_1 (GList *list)
+static inline void
+_g_list_free_1 (GList *list)
{
if (list)
{
- list->next = current_allocator->free_list;
- current_allocator->free_list = list;
+ list->data = NULL;
+
+#ifdef ENABLE_GC_FRIENDLY
+ list->prev = NULL;
+#endif /* ENABLE_GC_FRIENDLY */
+
+ G_LOCK (current_allocator);
+ list->next = current_allocator->free_lists;
+ current_allocator->free_lists = list;
+ G_UNLOCK (current_allocator);
}
}
+void
+g_list_free_1 (GList *list)
+{
+ _g_list_free_1 (list);
+}
+
GList*
g_list_append (GList *list,
gpointer data)
GList *new_list;
GList *last;
- new_list = g_list_alloc ();
+ new_list = _g_list_alloc ();
new_list->data = data;
if (list)
{
GList *new_list;
- new_list = g_list_alloc ();
+ new_list = _g_list_alloc ();
new_list->data = data;
if (list)
if (!tmp_list)
return g_list_append (list, data);
- new_list = g_list_alloc ();
+ new_list = _g_list_alloc ();
new_list->data = data;
if (tmp_list->prev)
}
GList*
-g_list_remove (GList *list,
- gpointer data)
+g_list_remove (GList *list,
+ gconstpointer data)
{
GList *tmp;
if (list == tmp)
list = list->next;
- g_list_free_1 (tmp);
+ _g_list_free_1 (tmp);
break;
}
return list;
}
-GList*
-g_list_remove_link (GList *list,
- GList *link)
+static inline GList*
+_g_list_remove_link (GList *list,
+ GList *link)
{
if (link)
{
}
GList*
+g_list_remove_link (GList *list,
+ GList *link)
+{
+ return _g_list_remove_link (list, link);
+}
+
+GList*
+g_list_delete_link (GList *list,
+ GList *link)
+{
+ list = _g_list_remove_link (list, link);
+ _g_list_free_1 (link);
+
+ return list;
+}
+
+GList*
+g_list_copy (GList *list)
+{
+ GList *new_list = NULL;
+
+ if (list)
+ {
+ GList *last;
+
+ new_list = _g_list_alloc ();
+ new_list->data = list->data;
+ last = new_list;
+ list = list->next;
+ while (list)
+ {
+ last->next = _g_list_alloc ();
+ last->next->prev = last;
+ last = last->next;
+ last->data = list->data;
+ list = list->next;
+ }
+ }
+
+ return new_list;
+}
+
+GList*
g_list_reverse (GList *list)
{
GList *last;
}
GList*
-g_list_find (GList *list,
- gpointer data)
+g_list_find (GList *list,
+ gconstpointer data)
{
while (list)
{
}
GList*
-g_list_find_custom (GList *list,
- gpointer data,
- GCompareFunc func)
+g_list_find_custom (GList *list,
+ gconstpointer data,
+ GCompareFunc func)
{
g_return_val_if_fail (func != NULL, list);
}
gint
-g_list_index (GList *list,
- gpointer data)
+g_list_index (GList *list,
+ gconstpointer data)
{
gint i;
if (!list)
{
- new_list = g_list_alloc();
+ new_list = _g_list_alloc ();
new_list->data = data;
return new_list;
}
cmp = (*func) (data, tmp_list->data);
}
- new_list = g_list_alloc();
+ new_list = _g_list_alloc ();
new_list->data = data;
if ((!tmp_list->next) && (cmp > 0))
g_list_sort (l2, compare_func),
compare_func);
}
+
+GList*
+g_list_sort2 (GList *list,
+ GCompareFunc compare_func)
+{
+ GSList *runs = NULL;
+ GList *tmp;
+
+ /* Degenerate case. */
+ if (!list) return NULL;
+
+ /* Assume: list = [12,2,4,11,2,4,6,1,1,12]. */
+ for (tmp = list; tmp; )
+ {
+ GList *tmp2;
+ for (tmp2 = tmp;
+ tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
+ tmp2 = tmp2->next)
+ /* Nothing */;
+ runs = g_slist_append (runs, tmp);
+ tmp = tmp2->next;
+ tmp2->next = NULL;
+ }
+ /* Now: runs = [[12],[2,4,11],[2,4,6],[1,1,12]]. */
+
+ while (runs->next)
+ {
+ /* We have more than one run. Merge pairwise. */
+ GSList *dst, *src, *dstprev = NULL;
+ dst = src = runs;
+ while (src && src->next)
+ {
+ dst->data = g_list_sort_merge (src->data,
+ src->next->data,
+ compare_func);
+ dstprev = dst;
+ dst = dst->next;
+ src = src->next->next;
+ }
+
+ /* If number of runs was odd, just keep the last. */
+ if (src)
+ {
+ dst->data = src->data;
+ dstprev = dst;
+ dst = dst->next;
+ }
+
+ dstprev->next = NULL;
+ g_slist_free (dst);
+ }
+
+ /* After 1st loop: runs = [[2,4,11,12],[1,1,2,4,6,12]]. */
+ /* After 2nd loop: runs = [[1,1,2,2,4,4,6,11,12,12]]. */
+
+ list = runs->data;
+ g_slist_free (runs);
+ return list;
+}
projects / platform / upstream / glib.git / blobdiff