From 470a23d12305f6272799e852af4919f28ed1c1bf Mon Sep 17 00:00:00 2001 From: Dana Jansens Date: Fri, 30 Oct 2009 10:14:41 -0400 Subject: [PATCH] Move the g_tree_(node|root)_next_version functions down where they belong. --- glib/gtree.c | 207 +++++++++++++++++++++++++-------------------------- 1 file changed, 102 insertions(+), 105 deletions(-) diff --git a/glib/gtree.c b/glib/gtree.c index 5b3878eb..5285fb6f 100644 --- a/glib/gtree.c +++ b/glib/gtree.c @@ -107,9 +107,6 @@ struct _GTreeNode static GTreeNode* g_tree_node_new (GTree *tree, gpointer key, gpointer value); -static void g_tree_root_next_version (GTree *tree); -static GTreeNode* g_tree_node_next_version (GTree *tree, - GTreeNode *node); static guint g_tree_priority (GTreeNode *node); static void g_tree_insert_internal (GTree *tree, gpointer key, @@ -171,108 +168,6 @@ g_tree_node_new (GTree *tree, return node; } -static void -g_tree_root_next_version (GTree *tree) -{ - g_assert(tree->rootversion(NOW) <= tree->version); - - if (tree->rootversion(NOW) < tree->version) - { - /* add a new version of the root */ - tree->nroots++; - tree->roots = g_renew(GTreeRoot, tree->roots, tree->nroots); - /* copy the latest version from roots[0] */ - tree->roots[tree->nroots-1] = tree->roots[0]; - tree->roots[0].version = tree->version; - } -} - -/* You must call this on a node before you start changing its pointers, - or you might be changing an old (permanent) version of the node */ -static GTreeNode* -g_tree_node_next_version (GTree *tree, - GTreeNode *node) -{ - g_assert(node->version(NOW) <= tree->version); - - if (node->version(NOW) == tree->version) - return node; /* node already has the current version */ - - /* if the current version is 0, then it's the first time we're making a new - pointer version for this node, and so its pointer table only has size - one (and thus is full) */ - if (node->version(NOW) == 0 || node->nv == MAX_IN_DEGREE+1) - { - GTreeNode *prev, *next, *parent, *left, *right; - - /* we filled the node's pointer table and need to make a new GTreeNode */ - GTreeNode *newnode = g_slice_new(GTreeNode); - newnode->data = node->data; - newnode->v[0] = node->v[0]; /* copy the latest version to here */ - newnode->v[0].version = tree->version; - newnode->nv = 1; - - /* 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); - parent = node->parent(NOW); - if (node->left_child(NOW)) - left = node->left(NOW); - else - left = NULL; - if (node->right_child(NOW)) - right = node->right(NOW); - else - right = NULL; - - if (prev && prev->right(NOW) == node) - { - g_tree_node_next_version (tree, prev); - prev->v[0].right = newnode; - } - if (next && next->left(NOW) == node) - { - g_tree_node_next_version (tree, next); - next->v[0].left = newnode; - } - if (parent) - { - g_assert(parent->right(NOW) == node || - parent->left(NOW) == node); - g_tree_node_next_version (tree, parent); - if (parent->left(NOW) == node) - parent->v[0].left = newnode; - else - parent->v[0].right = newnode; - } - if (left) - { - g_assert (left->parent(NOW) == node); - g_tree_node_next_version (tree, left); - left->v[0].parent = newnode; - } - if (right) - { - g_assert (right->parent(NOW) == node); - g_tree_node_next_version (tree, right); - right->v[0].parent = newnode; - } - - return newnode; - } - else - { - /* add a new version to the node's table */ - node->nv++; - /* copy the latest version from v[0] */ - node->v[node->nv-1] = node->v[0]; - node->v[0].version = tree->version; - return node; - } -} - /** * g_tree_new: * @key_compare_func: the function used to order the nodes in the #GTree. @@ -528,6 +423,108 @@ g_tree_next_version (GTree *tree) return ++tree->version; } +static void +g_tree_root_next_version (GTree *tree) +{ + g_assert(tree->rootversion(NOW) <= tree->version); + + if (tree->rootversion(NOW) < tree->version) + { + /* add a new version of the root */ + tree->nroots++; + tree->roots = g_renew(GTreeRoot, tree->roots, tree->nroots); + /* copy the latest version from roots[0] */ + tree->roots[tree->nroots-1] = tree->roots[0]; + tree->roots[0].version = tree->version; + } +} + +/* You must call this on a node before you start changing its pointers, + or you might be changing an old (permanent) version of the node */ +static GTreeNode* +g_tree_node_next_version (GTree *tree, + GTreeNode *node) +{ + g_assert(node->version(NOW) <= tree->version); + + if (node->version(NOW) == tree->version) + return node; /* node already has the current version */ + + /* if the current version is 0, then it's the first time we're making a new + pointer version for this node, and so its pointer table only has size + one (and thus is full) */ + if (node->version(NOW) == 0 || node->nv == MAX_IN_DEGREE+1) + { + GTreeNode *prev, *next, *parent, *left, *right; + + /* we filled the node's pointer table and need to make a new GTreeNode */ + GTreeNode *newnode = g_slice_new(GTreeNode); + newnode->data = node->data; + newnode->v[0] = node->v[0]; /* copy the latest version to here */ + newnode->v[0].version = tree->version; + newnode->nv = 1; + + /* 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); + parent = node->parent(NOW); + if (node->left_child(NOW)) + left = node->left(NOW); + else + left = NULL; + if (node->right_child(NOW)) + right = node->right(NOW); + else + right = NULL; + + if (prev && prev->right(NOW) == node) + { + g_tree_node_next_version (tree, prev); + prev->v[0].right = newnode; + } + if (next && next->left(NOW) == node) + { + g_tree_node_next_version (tree, next); + next->v[0].left = newnode; + } + if (parent) + { + g_assert(parent->right(NOW) == node || + parent->left(NOW) == node); + g_tree_node_next_version (tree, parent); + if (parent->left(NOW) == node) + parent->v[0].left = newnode; + else + parent->v[0].right = newnode; + } + if (left) + { + g_assert (left->parent(NOW) == node); + g_tree_node_next_version (tree, left); + left->v[0].parent = newnode; + } + if (right) + { + g_assert (right->parent(NOW) == node); + g_tree_node_next_version (tree, right); + right->v[0].parent = newnode; + } + + return newnode; + } + else + { + /* add a new version to the node's table */ + node->nv++; + /* copy the latest version from v[0] */ + node->v[node->nv-1] = node->v[0]; + node->v[0].version = tree->version; + return node; + } +} + /** * g_tree_insert: * @tree: a #GTree. -- 2.34.1