* Boston, MA 02111-1307, USA.
*/
-#include <config.h>
+#include "config.h"
#include "gtkrbtree.h"
#include "gtkdebug.h"
-#include "gtkalias.h"
-static void _gtk_rbnode_validate_allocator (GAllocator *allocator);
static GtkRBNode * _gtk_rbnode_new (GtkRBTree *tree,
gint height);
static void _gtk_rbnode_free (GtkRBNode *node);
GtkRBNode *node);
static void _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
GtkRBNode *node);
-static gint _count_nodes (GtkRBTree *tree,
- GtkRBNode *node);
static inline void _fixup_validation (GtkRBTree *tree,
GtkRBNode *node);
static inline void _fixup_parity (GtkRBTree *tree,
-/* node allocation
- */
-struct _GAllocator /* from gmem.c */
-{
- gchar *name;
- guint16 n_preallocs;
- guint is_unused : 1;
- guint type : 4;
- GAllocator *last;
- GMemChunk *mem_chunk;
- GtkRBNode *free_nodes; /* implementation specific */
-};
-
-
-G_LOCK_DEFINE_STATIC (current_allocator);
-static GAllocator *current_allocator = NULL;
-
-
-/* HOLDS: current_allocator_lock */
-static void
-_gtk_rbnode_validate_allocator (GAllocator *allocator)
-{
- g_return_if_fail (allocator != NULL);
- g_return_if_fail (allocator->is_unused == TRUE);
-
- 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 (GtkRBNode),
- sizeof (GtkRBNode) * allocator->n_preallocs,
- G_ALLOC_ONLY);
- allocator->free_nodes = NULL;
- }
-
- allocator->is_unused = FALSE;
-}
-
static GtkRBNode *
_gtk_rbnode_new (GtkRBTree *tree,
gint height)
{
- GtkRBNode *node;
-
- G_LOCK (current_allocator);
- if (!current_allocator)
- {
- GAllocator *allocator = g_allocator_new ("GTK+ default GtkRBNode allocator",
- 128);
- _gtk_rbnode_validate_allocator (allocator);
- allocator->last = NULL;
- current_allocator = allocator;
- }
- if (!current_allocator->free_nodes)
- node = g_chunk_new (GtkRBNode, current_allocator->mem_chunk);
- else
- {
- node = current_allocator->free_nodes;
- current_allocator->free_nodes = node->left;
- }
- G_UNLOCK (current_allocator);
+ GtkRBNode *node = g_slice_new (GtkRBNode);
node->left = tree->nil;
node->right = tree->nil;
static void
_gtk_rbnode_free (GtkRBNode *node)
{
- G_LOCK (current_allocator);
- node->left = current_allocator->free_nodes;
- current_allocator->free_nodes = node;
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
{
- /* unfortunately node->left has to continue to point to
- * a node...
- */
+ node->left = (gpointer) 0xdeadbeef;
node->right = (gpointer) 0xdeadbeef;
node->parent = (gpointer) 0xdeadbeef;
node->offset = 56789;
node->count = 56789;
node->flags = 0;
}
- G_UNLOCK (current_allocator);
+ g_slice_free (GtkRBNode, node);
}
static void
GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);
}
-/* Public functions */
-void
-_gtk_rbnode_push_allocator (GAllocator *allocator)
-{
- G_LOCK (current_allocator);
- _gtk_rbnode_validate_allocator ( allocator );
- allocator->last = current_allocator;
- current_allocator = allocator;
- G_UNLOCK (current_allocator);
-}
-
-void
-_gtk_rbnode_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);
-}
-
GtkRBTree *
_gtk_rbtree_new (void)
{
GtkRBTree *retval;
- retval = (GtkRBTree *) g_new (GtkRBTree, 1);
+ retval = g_new (GtkRBTree, 1);
retval->parent_tree = NULL;
retval->parent_node = NULL;
- retval->nil = g_new0 (GtkRBNode, 1);
+ retval->nil = g_slice_new (GtkRBNode);
retval->nil->left = NULL;
retval->nil->right = NULL;
retval->nil->parent = NULL;
gint height = tree->root->offset;
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
_gtk_rbtree_test (G_STRLOC, tree);
#endif
_gtk_rbtree_free (tree);
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
_gtk_rbtree_test (G_STRLOC, tmp_tree);
#endif
}
GtkRBTree *tmp_tree;
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
{
g_print ("\n\n_gtk_rbtree_insert_after: %p\n", current);
_gtk_rbtree_debug_spew (tree);
_gtk_rbtree_insert_fixup (tree, node);
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
{
g_print ("_gtk_rbtree_insert_after finished...\n");
_gtk_rbtree_debug_spew (tree);
GtkRBTree *tmp_tree;
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
{
g_print ("\n\n_gtk_rbtree_insert_before: %p\n", current);
_gtk_rbtree_debug_spew (tree);
_gtk_rbtree_insert_fixup (tree, node);
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
{
g_print ("_gtk_rbtree_insert_before finished...\n");
_gtk_rbtree_debug_spew (tree);
}
}
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
_gtk_rbtree_test (G_STRLOC, tree);
#endif
}
void
_gtk_rbtree_set_fixed_height (GtkRBTree *tree,
- gint height)
+ gint height,
+ gboolean mark_valid)
{
GtkRBNode *node;
do
{
if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
- _gtk_rbtree_node_set_height (tree, node, height);
+ {
+ _gtk_rbtree_node_set_height (tree, node, height);
+ if (mark_valid)
+ _gtk_rbtree_node_mark_valid (tree, node);
+ }
if (node->children)
- _gtk_rbtree_set_fixed_height (node->children, height);
+ _gtk_rbtree_set_fixed_height (node->children, height, mark_valid);
}
while ((node = _gtk_rbtree_next (tree, node)) != NULL);
}
GtkRBNode *x, *y;
GtkRBTree *tmp_tree;
GtkRBNode *tmp_node;
- gint node_height;
gint y_height;
g_return_if_fail (tree != NULL);
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
{
g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
_gtk_rbtree_debug_spew (tree);
g_return_if_fail (x == tree->root);
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
_gtk_rbtree_test (G_STRLOC, tree);
#endif
/* offsets and parity adjust all the way up through parent trees */
y_height = GTK_RBNODE_GET_HEIGHT (y);
- node_height = GTK_RBNODE_GET_HEIGHT (node) + (node->children?node->children->root->offset:0);
tmp_tree = tree;
tmp_node = y;
_gtk_rbnode_free (y);
#ifdef G_ENABLE_DEBUG
- if (gtk_debug_flags & GTK_DEBUG_TREE)
+ if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
{
g_print ("_gtk_rbtree_remove_node finished...\n");
_gtk_rbtree_debug_spew (tree);
}
}
-static gint
-_count_nodes (GtkRBTree *tree,
- GtkRBNode *node)
-{
- gint res;
- if (node == tree->nil)
- return 0;
-
- g_assert (node->left);
- g_assert (node->right);
-
- res = (_count_nodes (tree, node->left) +
- _count_nodes (tree, node->right) + 1);
-
- if (res != node->count)
- g_print ("Tree failed\n");
- return res;
-}
-
static inline
void _fixup_validation (GtkRBTree *tree,
GtkRBNode *node)
g_print ("parity incorrect for node\n");
if (get_parity (node) != 1)
- g_error ("Node has incorrect parity %d", get_parity (node));
+ g_error ("Node has incorrect parity %u", get_parity (node));
return res;
}
+static gint
+_count_nodes (GtkRBTree *tree,
+ GtkRBNode *node)
+{
+ gint res;
+ if (node == tree->nil)
+ return 0;
+
+ g_assert (node->left);
+ g_assert (node->right);
+
+ res = (_count_nodes (tree, node->left) +
+ _count_nodes (tree, node->right) + 1);
+
+ if (res != node->count)
+ g_print ("Tree failed\n");
+ return res;
+}
+
static void
_gtk_rbtree_test_height (GtkRBTree *tree,
GtkRBNode *node)
g_assert (tree->root->parent == tree->nil);
_gtk_rbtree_test_structure_helper (tree, tree->root);
}
-
+
void
_gtk_rbtree_test (const gchar *where,
GtkRBTree *tree)
projects / ~andy / gtk / blobdiff