From 014f63484ed6f75c761acf3f49752209cc221a6d Mon Sep 17 00:00:00 2001
From: Dana Jansens <danakj@orodu.net>
Date: Thu, 29 Oct 2009 11:34:24 -0400
Subject: [PATCH] Introduce g_tree_node_modify and g_tree_root_modify, which
 are used to change the tree in a version-friendly way

---
 glib/gtree.c | 72 +++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 57 insertions(+), 15 deletions(-)

diff --git a/glib/gtree.c b/glib/gtree.c
index ac076e85..a92ec676 100644
--- a/glib/gtree.c
+++ b/glib/gtree.c
@@ -90,9 +90,9 @@ struct _GTreeNode
 #define left_child(i)  v[i].left_child
 #define right_child(i) v[i].right_child
 
-static GTreeNode* g_tree_node_new                   (gpointer         key,
-						     gpointer         value,
-                                                     guint            version);
+static GTreeNode* g_tree_node_new                   (GTree           *tree,
+                                                     gpointer         key,
+						     gpointer         value);
 static guint      g_tree_priority                   (GTreeNode       *node);
 static void       g_tree_insert_internal            (GTree           *tree,
 						     gpointer         key,
@@ -125,9 +125,9 @@ static void       g_tree_node_check                 (GTreeNode       *node);
 #endif
 
 static GTreeNode*
-g_tree_node_new (gpointer key,
-		 gpointer value,
-                 guint    version)
+g_tree_node_new (GTree   *tree,
+                 gpointer key,
+		 gpointer value)
 {
   GTreeNode *node = g_slice_new (GTreeNode);
 
@@ -139,10 +139,10 @@ g_tree_node_new (gpointer key,
      so that we don't use a lot more memory when persistence isn't even
      being used */
   node->v = g_slice_alloc(sizeof(GTreeNodeVersion) *
-                          (version == 0 ? 1 : MAX_IN_DEGREE + 1));
+                          (tree->version == 0 ? 1 : MAX_IN_DEGREE + 1));
   node->nv = 1;
 
-  node->v[0].version = version;
+  node->v[0].version = tree->version;
   node->v[0].left = NULL;
   node->v[0].right = NULL;
   node->v[0].parent = NULL;
@@ -152,6 +152,48 @@ g_tree_node_new (gpointer key,
   return node;
 }
 
+static GTreeNode*
+g_tree_root_modify (GTree     *tree,
+                    GTreeNode *root)
+{
+  tree->root = root;
+  return root;
+}
+
+static GTreeNode*
+g_tree_node_modify (GTree     *tree,
+                    GTreeNode *node,
+                    GTreeNode *left,
+                    GTreeNode *right,
+                    GTreeNode *parent,
+                    gboolean   left_child,
+                    gboolean   right_child)
+{
+  int i;
+
+  for (i = 0; i < node->nv; ++i)
+    if (node->version(i) == tree->version)
+      break;
+  if (i == node->nv)
+    {
+      /* we filled the node's pointer table and need to make a new GTreeNode */
+      GTreeNode *n = g_slice_new(GTreeNode);
+      n->data = node->data;
+      i = 0;
+      n->v[i].version = tree->version;
+      n->nv = 1;
+      node = n;
+    }
+
+  node->v[i].left = left;
+  node->v[i].right = right;
+  node->v[i].parent = parent;
+  node->v[i].left_child = left_child;
+  node->v[i].right_child = right_child;
+
+  return node;
+}
+
 /**
  * g_tree_new:
  * @key_compare_func: the function used to order the nodes in the #GTree.
@@ -499,7 +541,7 @@ g_tree_insert_internal (GTree    *tree,
 
   if (!tree->root)
     {
-      tree->root = g_tree_node_new (key, value, tree->version);
+      g_tree_root_modify (tree, g_tree_node_new (tree, key, value));
       tree->nnodes++;
       return;
     }
@@ -540,7 +582,7 @@ g_tree_insert_internal (GTree    *tree,
               node = node->left(NOW);
           else
             {
-              child = g_tree_node_new (key, value, tree->version);
+              child = g_tree_node_new (tree, key, value);
 
               child->v[0].left = node->v[0].left;
               child->v[0].right = node;
@@ -560,7 +602,7 @@ g_tree_insert_internal (GTree    *tree,
               node = node->right(NOW);
           else
             {
-              child = g_tree_node_new (key, value, tree->version);
+              child = g_tree_node_new (tree, key, value);
 
               child->v[0].right = node->v[0].right;
               child->v[0].left = node;
@@ -589,7 +631,7 @@ g_tree_insert_internal (GTree    *tree,
         g_tree_node_rotate_left (p);
 
       if (!sp)
-        tree->root = node;
+        g_tree_root_modify (tree, node);
       else if (sp->left(NOW) == p)
         sp->left(NOW) = node;
       else
@@ -714,7 +756,7 @@ g_tree_remove_internal (GTree         *tree,
         {
           /* rotate the right child up */
           if (!parent)
-            parent = tree->root = g_tree_node_rotate_left (node);
+            parent = g_tree_root_modify (tree, g_tree_node_rotate_left (node));
           else if (is_leftchild)
             parent = parent->v[0].left = g_tree_node_rotate_left (node);
           else
@@ -725,7 +767,7 @@ g_tree_remove_internal (GTree         *tree,
         {
           /* rotate the left child up */
           if (!parent)
-            parent = tree->root = g_tree_node_rotate_right (node);
+            parent = g_tree_root_modify(tree, g_tree_node_rotate_right (node));
           else if (is_leftchild)
             parent = parent->v[0].left = g_tree_node_rotate_right (node);
           else
@@ -736,7 +778,7 @@ g_tree_remove_internal (GTree         *tree,
 
   /* remove any pointers to the node in the treap */
   if (!parent)
-    tree->root = NULL;
+    g_tree_root_modify(tree, NULL);
   else if (is_leftchild)
     {
       parent->v[0].left_child = FALSE;
-- 
2.34.1