From 6d400d49e54c11be1b4f61ce57acede8f91d08f7 Mon Sep 17 00:00:00 2001
From: Dana Jansens <danakj@orodu.net>
Date: Fri, 30 Oct 2009 10:13:17 -0400
Subject: [PATCH] Fix incoming pointers to a node when its versioned-pointer
 table fills up and the node needs to be replaced by a new one.

---
 glib/gtree.c | 70 ++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 60 insertions(+), 10 deletions(-)

diff --git a/glib/gtree.c b/glib/gtree.c
index c11a6a4e..5b3878eb 100644
--- a/glib/gtree.c
+++ b/glib/gtree.c
@@ -107,6 +107,9 @@ 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,
@@ -200,15 +203,64 @@ g_tree_node_next_version (GTree     *tree,
      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 *n = g_slice_new(GTreeNode);
-      n->data = node->data;
-      n->v[0] = node->v[0]; /* copy the latest version to here */
-      n->v[0].version = tree->version;
-      n->nv = 1;
-      return n;
-
-      // XXX worry about incoming pointers
+      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
     {
@@ -218,8 +270,6 @@ g_tree_node_next_version (GTree     *tree,
       node->v[node->nv-1] = node->v[0];
       node->v[0].version = tree->version;
       return node;
-
-      // XXX worry about incoming pointers
     }
 }
 
-- 
2.34.1