[Zope-Checkins] CVS: Zope3/lib/python/Persistence/BTrees - BTreeTemplate.c:1.38

Tim Peters tim.one@comcast.net
Tue, 25 Jun 2002 12:30:31 -0400


Update of /cvs-repository/Zope3/lib/python/Persistence/BTrees
In directory cvs.zope.org:/tmp/cvs-serv18668

Modified Files:
	BTreeTemplate.c 
Log Message:
BTree_clone():  Renamed to BTree_split_root(), and greatly simplified
the algorithm in a way I believe Jim suggested a few weeks ago (but that
I didn't understand then).


=== Zope3/lib/python/Persistence/BTrees/BTreeTemplate.c 1.37 => 1.38 ===
 }
 
-/* Split out data among two newly created BTrees, which become
-   out children.
-*/
+
+/* Fwd decl -- BTree_grow and BTree_split_root reference each other. */
+static int BTree_grow(BTree *self, int index, int noval);
+
+/* Split the root.  This is a little special because the root isn't a child
+ * of anything else, and the root needs to retain its object identity.  So
+ * this routine moves the root's data into a new child, and splits the
+ * latter.  This leaves the root with two children.
+ *
+ * Return:
+ *      0   OK
+ *     -1   error
+ *
+ * CAUTION:  The caller must call PER_CHANGED on self.
+ */
 static int
-BTree_clone(BTree *self)
+BTree_split_root(BTree *self, int noval)
 {
-  /* We've grown really big without anybody splitting us.
-     We should split ourselves.
-   */
-  BTree *n1 = NULL, *n2 = NULL;
-  BTreeItem *d = NULL;
-
-  /* Create two BTrees to hold ourselves after split */
-  n1 = (BTree *)PyObject_CallObject((PyObject *)self->ob_type, NULL);
-  if (n1 == NULL)
-      return -1;
-  n2 = (BTree *)PyObject_CallObject((PyObject *)self->ob_type, NULL);
-  if (n2 == NULL)
-      goto err;
-
-  /* Create a new data buffer to hold two BTrees */
-  d = BTree_Malloc(sizeof(BTreeItem)*2);
-  if (d == NULL)
-      goto err;
-
-  /* Split ourself */
-  if (BTree_split(self, -1, n2) < 0)
-      goto err;
-
-  /* Move our data to new BTree */
-  n1->size = self->size;
-  n1->len = self->len;
-  n1->data = self->data;
-  n1->firstbucket = self->firstbucket;
-  Py_XINCREF(n1->firstbucket);
-
-  /* Initialize our data to hold split data */
-  self->data = d;
-  self->len = 2;
-  self->size = 2;
-  self->data->child = (Sized *)n1;
-  COPY_KEY(self->data[1].key, n2->data->key);
-
-  /* We take the unused reference from n2, so there's no reason to INCREF! */
-  /* INCREF_KEY(self->data[1].key); */
-
-  self->data[1].child = (Sized *)n2;
-
-  return 0;
-
-err:
-  Py_XDECREF(n1);
-  Py_XDECREF(n2);
-  if (d)
-      free(d);
-  return -1;
+    BTree *child;
+    BTreeItem *d;
+
+    /* Create a child BTree, and a new data vector for self. */
+    child = BTREE(PyObject_CallObject(OBJECT(self->ob_type), NULL));
+    if (!child) return -1;
+
+    d = BTree_Malloc(sizeof(BTreeItem) * 2);
+    if (!d) {
+        Py_DECREF(child);
+        return -1;
+    }
+
+    /* Move our data to new BTree. */
+    child->size = self->size;
+    child->len = self->len;
+    child->data = self->data;
+    child->firstbucket = self->firstbucket;
+    Py_INCREF(child->firstbucket);
+
+    /* Point self to child and split the child. */
+    self->data = d;
+    self->len = 1;
+    self->size = 2;
+    self->data[0].child = SIZED(child); /* transfers reference ownership */
+    return BTree_grow(self, 0, noval);
 }
 
 /*
@@ -435,8 +423,8 @@
       d->child = e;
       self->len++;
 
-      if (self->len >= MAX_BTREE_SIZE(self) * 2)
-	  return BTree_clone(self);
+      if (self->len >= MAX_BTREE_SIZE(self) * 2)    /* the root is huge */
+	  return BTree_split_root(self, noval);
   }
   else {
       /* The BTree is empty.  Create an empty bucket.  See CAUTION in