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

Tim Peters tim.one@comcast.net
Mon, 17 Jun 2002 16:02:50 -0400


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

Modified Files:
	BTreeTemplate.c 
Log Message:
_BTree_clear():  Made the Zope2 and Zope3 versions as similar as possible.


=== Zope3/lib/python/Persistence/BTrees/BTreeTemplate.c 1.22 => 1.23 ===
 ** _BTree_clear
 **
-** Clears out all of the values in the BTree
+** Clears out all of the values in the BTree (firstbucket, keys, and children);
+** leaving self an empty BTree.
 **
 ** Arguments:	self	The BTree
 **
 ** Returns:	 0	on success
 **		-1	on failure
-*/
+**
+** Internal:  Deallocation order is important.  The danger is that a long
+** list of buckets may get freed "at once" via decref'ing the first bucket,
+** in which case a chain of consequenct Py_DECREF calls may blow the stack.
+** Luckily, every bucket has a refcount of at least two, one due to being a
+** BTree node's child, and another either because it's not the first bucket in
+** the chain (so the preceding bucket points to it), or because firstbucket
+** points to it.  By clearing in the natural depth-first, left-to-right
+** order, the BTree->bucket child pointers prevent Py_DECREF(bucket->next)
+** calls from freeing bucket->next, and the maximum stack depth is equal
+** to the height of the tree.
+**/
 static int
 _BTree_clear(BTree *self)
 {
     const int len = self->len;
 
-    self->len = self->size = 0;
-
-    /* The order in which we deallocate, from "top to bottom" is
-       critical to prevent memory errors when the deallocation stack
-       becomes huge when dealocating use linked lists of buckets.
-       XXX I don't understand that comment; there doesn't appear to be
-       XXX anything special in this code wrt deallocation order.  I
-       XXX suspect it might help to decref children in *reverse* order,
-       XXX to get the rightmost buckets cleared first.
-    */
-
     if (self->firstbucket) {
 	ASSERT(self->firstbucket->ob_refcnt > 1,
 	       "Invalid firstbucket pointer", -1);
@@ -645,6 +646,7 @@
 	self->data = NULL;
     }
 
+    self->len = self->size = 0;
     return 0;
 }