From b3661ca1bd38a964b1c14549fc25b3b4c9212687 Mon Sep 17 00:00:00 2001 From: Dana Jansens Date: Mon, 2 Nov 2009 10:43:33 -0500 Subject: [PATCH] Fix up g_tree_next_node() to create a new version of the node if needed, and then fix any incoming pointers to point to the new version (recursively applied to those nodes) --- glib/gtree.c | 162 ++++++++++++++++++++++++++++++++------------------- 1 file changed, 102 insertions(+), 60 deletions(-) diff --git a/glib/gtree.c b/glib/gtree.c index 3ea6f711..3a6daf89 100644 --- a/glib/gtree.c +++ b/glib/gtree.c @@ -544,82 +544,33 @@ g_tree_root_next_version (GTree *tree) } } -/* 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) +/* add a new version of pointers to a node. return TRUE if ok, and FALSE + if there is no room to do so. */ +static inline GTreeNode * +g_tree_node_add_version (GTree *tree, + GTreeNode *node) { if (!node) return NULL; - g_assert(node->version(NOW) <= tree->version); - + /* node already has the current 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) + return node; + /* if we filled the node's pointer table and need to make a new GTreeNode */ + else 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->v = g_slice_alloc(sizeof(GTreeNodeVersion) * (MAX_IN_DEGREE+1)); newnode->data = node->data; newnode->data->ref_count++; 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, tree->version); - next = g_tree_node_next (node, tree->version); - parent = node->parent(NOW); - left = node->left(NOW); - right = node->right(NOW); - - 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; } + /* there is space left in the node's pointer table for a new version */ 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]; @@ -628,6 +579,97 @@ g_tree_node_next_version (GTree *tree, } } +static inline void +g_tree_node_fix_incoming (GTree *tree, + GTreeNode *oldnode, + GTreeNode *newnode) +{ + GTreeNode *oldparent, *oldleft, *oldright; + GTreeNode *newparent, *newleft, *newright; + + if (oldnode == newnode) return; + + g_assert (oldnode != NULL); + g_assert (newnode != NULL); + + /* find incoming edges to the old version of the node */ + oldparent = newnode->parent(NOW); + if (oldparent && oldparent->left(NOW) != oldnode && + oldparent->right(NOW) != oldnode) + oldparent = NULL; + oldleft = newnode->left(NOW); + if (oldleft && oldleft->parent(NOW) != oldnode) + oldleft = NULL; + oldright = newnode->right(NOW); + if (oldright && oldright->parent(NOW) != oldnode) + oldright = NULL; + + /* add new pointers for nodes that point to me, possibly creating new + versions of the nodes */ + newparent = g_tree_node_add_version (tree, oldparent); + newleft = g_tree_node_add_version (tree, oldleft); + newright = g_tree_node_add_version (tree, oldright); + + /* 1. update my pointers to point to the new versions (if a prev node + points to me, then i'm its next node, and its my parent or + it is the rightmost node in my left subtree. case a, i update my + pointer to it already. case b, if it's my left child i update + my pointer to it already, otherwise i don't have a pointer to it, + because i do have a left subtree. + */ + if (newparent != oldparent) + newnode->v[0].parent = newparent; + if (newleft != oldleft) + newnode->v[0].left = newleft; + if (newright != oldright) + newnode->v[0].right = newright; + + /* 2. update my incoming nodes to point back to the new version of me */ + if (newparent) + { + if (newparent->left(NOW) == oldnode) + newparent->v[0].left = newnode; + else + newparent->v[0].right = newnode; + } + if (newleft) + newleft->v[0].parent = newnode; + if (newright) + newright->v[0].parent = newnode; + + /* 3. recurse on each of the incoming nodes if they had to create a new + version */ + g_tree_node_fix_incoming (tree, oldparent, newparent); + g_tree_node_fix_incoming (tree, oldleft, newleft); + g_tree_node_fix_incoming (tree, oldright, newright); + + /* 4. if this was the root node, then the root pointer into the tree needs + be updated */ + if (tree->root(NOW) == oldnode) + { + g_tree_root_next_version (tree); + tree->roots[0].root = newnode; + } +} + +/* 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 *oldnode) +{ + GTreeNode *newnode; + + if (!oldnode) + return NULL; + + g_assert(oldnode->version(NOW) <= tree->version); + + newnode = g_tree_node_add_version (tree, oldnode); + g_tree_node_fix_incoming (tree, oldnode, newnode); + return newnode; +} + /** * g_tree_insert: * @tree: a #GTree. -- 2.34.1