From 3ab0e821cf3e7dd3cddb22c22dbf18b109557772 Mon Sep 17 00:00:00 2001 From: Dana Jansens Date: Fri, 30 Oct 2009 18:42:56 -0400 Subject: [PATCH] Update the debug testing code to check all versions of a persistent tree. --- glib/gtree.c | 162 ++++++++++++++++++++++++++++++++------------------- 1 file changed, 103 insertions(+), 59 deletions(-) diff --git a/glib/gtree.c b/glib/gtree.c index 6dde6ccb..fefc8e55 100644 --- a/glib/gtree.c +++ b/glib/gtree.c @@ -137,7 +137,8 @@ static GTreeNode* g_tree_node_rotate_left (GTree *tree, static GTreeNode* g_tree_node_rotate_right (GTree *tree, GTreeNode *node); #ifdef G_TREE_DEBUG -static void g_tree_node_check (GTreeNode *node); +static void g_tree_node_check (GTreeNode *node, + guint version); #endif static GTreeNode* @@ -309,45 +310,59 @@ g_tree_node_find_version(GTreeNode *node, } static inline GTreeNode * -g_tree_first_node (GTree *tree) +g_tree_first_node (GTree *tree, + guint version) { GTreeNode *tmp; + GTreeNodeVersion *tmpv; + GTreeRootVersion *rv; - if (!tree->root(NOW)) + rv = g_tree_root_find_version (tree, version); + if (!rv->root) return NULL; - tmp = tree->root(NOW); + tmpv = g_tree_node_find_version (tmp = rv->root, version); - while (tmp->left_child(NOW)) - tmp = tmp->left(NOW); + while (tmpv->left_child) + tmpv = g_tree_node_find_version (tmp = tmpv->left, version); return tmp; } static inline GTreeNode * -g_tree_node_previous (GTreeNode *node) +g_tree_node_previous (GTreeNode *node, + guint version) { GTreeNode *tmp; + GTreeNodeVersion *nodev, *tmpv; - tmp = node->left(NOW); + nodev = g_tree_node_find_version (node, version); + if (!nodev->left) + return NULL; + tmpv = g_tree_node_find_version (tmp = nodev->left, version); - if (node->left_child(NOW)) - while (tmp->right_child(NOW)) - tmp = tmp->right(NOW); + if (nodev->left_child) + while (tmpv->right_child) + tmpv = g_tree_node_find_version (tmp = tmpv->right, version); return tmp; } static inline GTreeNode * -g_tree_node_next (GTreeNode *node) +g_tree_node_next (GTreeNode *node, + guint version) { GTreeNode *tmp; + GTreeNodeVersion *nodev, *tmpv; - tmp = node->right(NOW); + nodev = g_tree_node_find_version (node, version); + if (!nodev->right) + return NULL; + tmpv = g_tree_node_find_version (tmp = nodev->right, version); - if (node->right_child(NOW)) - while (tmp->left_child(NOW)) - tmp = tmp->left(NOW); + if (nodev->right_child) + while (tmpv->left_child) + tmpv = g_tree_node_find_version (tmp = tmpv->left, version); return tmp; } @@ -362,11 +377,11 @@ g_tree_remove_all (GTree *tree) // XXX worry about removing all versions, not just the latest - node = g_tree_first_node (tree); + node = g_tree_first_node (tree, tree->version); while (node) { - next = g_tree_node_next (node); + next = g_tree_node_next (node, tree->version); if (tree->key_destroy_func) tree->key_destroy_func (node->data->key); @@ -525,8 +540,8 @@ g_tree_node_next_version (GTree *tree, /* update any incoming pointers to node, so that they can find the new version */ - prev = g_tree_node_previous (node); - next = g_tree_node_next (node); + prev = g_tree_node_previous (node, tree->version); + next = g_tree_node_next (node, tree->version); parent = node->parent(NOW); if (node->left_child(NOW)) left = node->left(NOW); @@ -608,7 +623,11 @@ g_tree_insert (GTree *tree, g_tree_insert_internal (tree, key, value, FALSE); #ifdef G_TREE_DEBUG - g_tree_node_check (tree->root); + { + guint i; + for (i = 0; i < tree->roots[0].version; ++i) + g_tree_node_check (g_tree_root_find_version (tree, i)->root, i); + } #endif } @@ -638,7 +657,11 @@ g_tree_replace (GTree *tree, g_tree_insert_internal (tree, key, value, TRUE); #ifdef G_TREE_DEBUG - g_tree_node_check (tree->root); + { + guint i; + for (i = 0; i < tree->roots[0].version; ++i) + g_tree_node_check (g_tree_root_find_version (tree, i)->root, i); + } #endif } @@ -823,7 +846,11 @@ g_tree_remove (GTree *tree, removed = g_tree_remove_internal (tree, key, FALSE); #ifdef G_TREE_DEBUG - g_tree_node_check (tree->root); + { + guint i; + for (i = 0; i < tree->roots[0].version; ++i) + g_tree_node_check (g_tree_root_find_version (tree, i)->root, i); + } #endif return removed; @@ -854,7 +881,11 @@ g_tree_steal (GTree *tree, removed = g_tree_remove_internal (tree, key, TRUE); #ifdef G_TREE_DEBUG - g_tree_node_check (tree->root); + { + guint i; + for (i = 0; i < tree->roots[0].version; ++i) + g_tree_node_check (g_tree_root_find_version (tree, i)->root, i); + } #endif return removed; @@ -1132,14 +1163,14 @@ g_tree_foreach (GTree *tree, if (!tree->root(NOW)) return; - node = g_tree_first_node (tree); + node = g_tree_first_node (tree, tree->version); while (node) { if ((*func) (node->data->key, node->data->value, user_data)) break; - node = g_tree_node_next (node); + node = g_tree_node_next (node, tree->version); } } @@ -1512,64 +1543,77 @@ g_tree_node_rotate_right (GTree *tree, #ifdef G_TREE_DEBUG static void -g_tree_node_check (GTreeNode *node) +g_tree_node_check (GTreeNode *node, + guint version) { - gint left_height; - gint right_height; GTreeNode *tmp; + GTreeNodeVersion *nv, *tmpv; if (node) { - if (node->left_child) + nv = g_tree_node_find_version (node, version); + + g_assert (nv->left == NULL || nv->left != nv->right); + + if (nv->left_child) { - tmp = g_tree_node_previous (node); - g_assert (tmp->right == node); + tmp = g_tree_node_previous (node, version); + g_assert (g_tree_node_find_version (tmp, version)->right == node); + + tmpv = g_tree_node_find_version (nv->left, version); + g_assert (tmpv->parent == node); } - if (node->right_child) + if (nv->right_child) { - tmp = g_tree_node_next (node); - g_assert (tmp->left == node); + tmp = g_tree_node_next (node, version); + g_assert (g_tree_node_find_version (tmp, version)->left == node); + + tmpv = g_tree_node_find_version (nv->right, version); + g_assert (tmpv->parent == node); } - left_height = 0; - right_height = 0; - - if (node->left_child) - left_height = g_tree_node_height (node->left); - if (node->right_child) - right_height = g_tree_node_height (node->right); - - if (node->left_child) - g_tree_node_check (node->left); - if (node->right_child) - g_tree_node_check (node->right); + if (nv->parent) + { + tmpv = g_tree_node_find_version (nv->parent, version); + g_assert (tmpv->left == node || tmpv->right == node); + } + + if (nv->left_child) + g_tree_node_check (nv->left, version); + if (nv->right_child) + g_tree_node_check (nv->right, version); } } static void -g_tree_node_dump (GTreeNode *node, +g_tree_node_dump (GTreeNode *node, + guint version, gint indent) { + GTreeNodeVersion *nv = g_tree_node_find_version (node, version); + g_print ("%*s%c\n", indent, "", *(char *)node->data->key); - if (node->left_child) - g_tree_node_dump (node->left, indent + 2); - else if (node->left) - g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->data->key); + if (nv->left_child) + g_tree_node_dump (nv->left, version, indent + 2); + else if (nv->left) + g_print ("%*s<%c\n", indent + 2, "", *(char *)nv->left->data->key); - if (node->right_child) - g_tree_node_dump (node->right, indent + 2); - else if (node->right) - g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->data->key); + if (nv->right_child) + g_tree_node_dump (nv->right, version, indent + 2); + else if (nv->right) + g_print ("%*s>%c\n", indent + 2, "", *(char *)nv->right->data->key); } void -g_tree_dump (GTree *tree) +g_tree_dump (GTree *tree, + guint version) { - if (tree->root) - g_tree_node_dump (tree->root, 0); + GTreeRootVersion *rv = g_tree_root_find_version (tree, version); + if (rv->root) + g_tree_node_dump (rv->root, version, 0); } #endif -- 2.34.1