* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
+
+/*
+ * Modified by the GLib Team and others 1997-1999. 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/.
+ */
+
+/*
+ * MT safe
+ */
+
#include "glib.h"
+/* node allocation
+ */
+struct _GAllocator /* from gmem.c */
+{
+ gchar *name;
+ guint16 n_preallocs;
+ guint is_unused : 1;
+ guint type : 4;
+ GAllocator *last;
+ GMemChunk *mem_chunk;
+ GNode *free_nodes; /* implementation specific */
+};
-#define KEEP_NODES (1024)
+G_LOCK_DEFINE_STATIC (current_allocator);
+static GAllocator *current_allocator = NULL;
+/* HOLDS: current_allocator_lock */
+static void
+g_node_validate_allocator (GAllocator *allocator)
+{
+ g_return_if_fail (allocator != NULL);
+ g_return_if_fail (allocator->is_unused == TRUE);
-/* --- variables --- */
-static GMemChunk *g_tree_node_chunk = NULL;
-static GNode *free_nodes = NULL;
-static guint n_free_nodes = 0;
+ if (allocator->type != G_ALLOCATOR_NODE)
+ {
+ allocator->type = G_ALLOCATOR_NODE;
+ if (allocator->mem_chunk)
+ {
+ g_mem_chunk_destroy (allocator->mem_chunk);
+ allocator->mem_chunk = NULL;
+ }
+ }
+
+ if (!allocator->mem_chunk)
+ {
+ allocator->mem_chunk = g_mem_chunk_new (allocator->name,
+ sizeof (GNode),
+ sizeof (GNode) * allocator->n_preallocs,
+ G_ALLOC_ONLY);
+ allocator->free_nodes = NULL;
+ }
+
+ allocator->is_unused = FALSE;
+}
+
+void
+g_node_push_allocator (GAllocator *allocator)
+{
+ G_LOCK (current_allocator);
+ g_node_validate_allocator ( allocator );
+ allocator->last = current_allocator;
+ current_allocator = allocator;
+ G_UNLOCK (current_allocator);
+}
+
+void
+g_node_pop_allocator (void)
+{
+ G_LOCK (current_allocator);
+ if (current_allocator)
+ {
+ GAllocator *allocator;
+
+ allocator = current_allocator;
+ current_allocator = allocator->last;
+ allocator->last = NULL;
+ allocator->is_unused = TRUE;
+ }
+ G_UNLOCK (current_allocator);
+}
/* --- functions --- */
GNode*
g_node_new (gpointer data)
{
- register GNode *node;
-
- if (!g_tree_node_chunk)
- g_tree_node_chunk = g_mem_chunk_create (GNode, 1024, G_ALLOC_AND_FREE);
-
- if (n_free_nodes)
+ GNode *node;
+
+ G_LOCK (current_allocator);
+ if (!current_allocator)
{
- node = free_nodes;
- free_nodes = free_nodes->next;
- n_free_nodes--;
+ GAllocator *allocator = g_allocator_new ("GLib default GNode allocator",
+ 128);
+ g_node_validate_allocator (allocator);
+ allocator->last = NULL;
+ current_allocator = allocator;
}
+ if (!current_allocator->free_nodes)
+ node = g_chunk_new (GNode, current_allocator->mem_chunk);
else
- node = g_chunk_new (GNode, g_tree_node_chunk);
+ {
+ node = current_allocator->free_nodes;
+ current_allocator->free_nodes = node->next;
+ }
+ G_UNLOCK (current_allocator);
- node->prev = NULL;
+ node->data = data;
node->next = NULL;
+ node->prev = NULL;
node->parent = NULL;
node->children = NULL;
- node->data = data;
return node;
}
static void
-g_node_free (GNode *parent)
+g_nodes_free (GNode *node)
{
- GNode *node;
-
- node = parent->children;
-
- while (node)
- {
- register GNode *free_node;
-
- free_node = node;
- node = free_node->next;
- g_node_free (free_node);
- }
+ GNode *parent;
- if (n_free_nodes < KEEP_NODES)
+ parent = node;
+ while (1)
{
- parent->next = free_nodes;
- free_nodes = parent;
- n_free_nodes++;
+ if (parent->children)
+ g_nodes_free (parent->children);
+ if (parent->next)
+ parent = parent->next;
+ else
+ break;
}
- else
- g_chunk_free (parent, g_tree_node_chunk);
+
+ G_LOCK (current_allocator);
+ parent->next = current_allocator->free_nodes;
+ current_allocator->free_nodes = node;
+ G_UNLOCK (current_allocator);
}
void
if (!G_NODE_IS_ROOT (root))
g_node_unlink (root);
- g_node_free (root);
+ g_nodes_free (root);
}
void
node->prev = NULL;
}
-void
+GNode*
+g_node_copy (GNode *node)
+{
+ GNode *new_node = NULL;
+
+ if (node)
+ {
+ GNode *child;
+
+ new_node = g_node_new (node->data);
+
+ for (child = g_node_last_child (node); child; child = child->prev)
+ g_node_prepend (new_node, g_node_copy (child));
+ }
+
+ return new_node;
+}
+
+GNode*
g_node_insert (GNode *parent,
gint position,
GNode *node)
{
- g_return_if_fail (parent != NULL);
- g_return_if_fail (node != NULL);
- g_return_if_fail (G_NODE_IS_ROOT (node));
+ g_return_val_if_fail (parent != NULL, node);
+ g_return_val_if_fail (node != NULL, node);
+ g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
if (position > 0)
- g_node_insert_before (parent,
- g_node_nth_child (parent, position),
- node);
+ return g_node_insert_before (parent,
+ g_node_nth_child (parent, position),
+ node);
else if (position == 0)
- g_node_prepend (parent, node);
- else if (position < 0)
- g_node_append (parent, node);
+ return g_node_prepend (parent, node);
+ else /* if (position < 0) */
+ return g_node_append (parent, node);
}
-void
+GNode*
g_node_insert_before (GNode *parent,
GNode *sibling,
GNode *node)
{
- g_return_if_fail (parent != NULL);
- g_return_if_fail (node != NULL);
- g_return_if_fail (G_NODE_IS_ROOT (node));
+ g_return_val_if_fail (parent != NULL, node);
+ g_return_val_if_fail (node != NULL, node);
+ g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
if (sibling)
- g_return_if_fail (sibling->parent == parent);
+ g_return_val_if_fail (sibling->parent == parent, node);
node->parent = parent;
else
node->parent->children = node;
}
+
+ return node;
}
-void
+GNode*
g_node_prepend (GNode *parent,
GNode *node)
{
- g_return_if_fail (parent != NULL);
+ g_return_val_if_fail (parent != NULL, node);
- g_node_insert_before (parent, parent->children, node);
+ return g_node_insert_before (parent, parent->children, node);
}
GNode*
{
g_return_val_if_fail (node != NULL, NULL);
+ if (node->parent)
+ return node->parent->children;
+
while (node->prev)
node = node->prev;
current = node;
node = current->next;
- if (G_NODE_IS_LEAF (node))
+ if (G_NODE_IS_LEAF (current))
{
if (flags & G_TRAVERSE_LEAFS)
func (current, data);