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

Tim Peters tim.one@comcast.net
Wed, 19 Jun 2002 19:34:40 -0400


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

Modified Files:
	BTreeTemplate.c TreeSetTemplate.c 
Log Message:
BTrees and TreeSets have a new ._check() method.  This does a thorough job
of verifying that BTree invariants are satisfied, raising AssertionError
if they're not.  Nothing calls this method by magic; it's for debugging.


=== Zope3/lib/python/Persistence/BTrees/BTreeTemplate.c 1.30 => 1.31 ===
 #define BTREETEMPLATE_C "$Id$\n"
 
+/* Sanity-check a BTree.  This is a private helper for BTree_check.  Return:
+ *      -1         Error.  If it's an internal inconsistency in the BTree,
+ *                 AssertionError is set.
+ *       0         No problem found.
+ *
+ * nextbucket is the bucket "one beyond the end" of the BTree; the last bucket
+ * directly reachable from following right child pointers *should* be linked
+ * to nextbucket (and this is checked).
+ */
+static int
+BTree_check_inner(BTree *self, Bucket *nextbucket)
+{
+    int i;
+    Bucket *bucketafter;
+    Sized *child;
+    char *errormsg = "internal error";  /* someone should have overriden */
+    Sized *activated_child = NULL;
+    int result = -1;    /* until proved innocent */
+
+#define CHECK(CONDITION, ERRORMSG)          \
+    if (!(CONDITION)) {                     \
+        errormsg = (ERRORMSG);              \
+        goto Error;                         \
+    }
+
+    PER_USE_OR_RETURN(self, -1);
+    CHECK(self->len >= 0, "BTree len < 0");
+    CHECK(self->len <= self->size, "BTree len > size");
+    if (self->len == 0) {
+        /* Empty BTree. */
+        CHECK(self->firstbucket == NULL,
+              "Empty BTree has non-NULL firstbucket");
+        result = 0;
+        goto Done;
+    }
+    /* Non-empty BTree. */
+    CHECK(self->firstbucket != NULL, "Non-empty BTree has NULL firstbucket");
+    CHECK(self->firstbucket->ob_refcnt >= 2,
+          "Non-empty BTree firstbucket has refcount < 2");
+    for (i = 0; i < self->len; ++i) {
+        CHECK(self->data[i].child != NULL, "BTree has NULL child");
+    }
+    if (SameType_Check(self, self->data[0].child)) {
+        /* Our children are also BTrees. */
+        child = self->data[0].child;
+        UNLESS (PER_USE(child)) goto Done;
+        activated_child = child;
+        CHECK(self->firstbucket == BTREE(child)->firstbucket,
+               "BTree has firstbucket different than "
+               "its first child's firstbucket");
+        PER_ALLOW_DEACTIVATION(child);
+        activated_child = NULL;
+        for (i = 0; i < self->len; ++i) {
+            child = self->data[i].child;
+            CHECK(SameType_Check(self, child),
+                  "BTree children have different types");
+            if (i == self->len - 1)
+                bucketafter = nextbucket;
+            else {
+                BTree *child2 = BTREE(self->data[i+1].child);
+                UNLESS (PER_USE(child2)) goto Done;
+                bucketafter = child2->firstbucket;
+                PER_ALLOW_DEACTIVATION(child2);
+            }
+            if (BTree_check_inner(BTREE(child), bucketafter) < 0) goto Done;
+        }
+    }
+    else {
+        /* Our children are buckets. */
+        CHECK(self->firstbucket == BUCKET(self->data[0].child),
+              "Bottom-level BTree node has inconsistent firstbucket belief");
+        for (i = 0; i < self->len; ++i) {
+            child = self->data[i].child;
+            UNLESS (PER_USE(child)) goto Done;
+            activated_child = child;
+            CHECK(!SameType_Check(self, child),
+                  "BTree children have different types");
+            CHECK(child->len >= 1, "Bucket length < 1"); /* no empty buckets! */
+            CHECK(child->len <= child->size, "Bucket len > size");
+            CHECK(child->ob_refcnt >= 2, "Bucket has refcount < 2");
+            if (i == self->len - 1)
+                bucketafter = nextbucket;
+            else
+                bucketafter = BUCKET(self->data[i+1].child);
+            CHECK(BUCKET(child)->next == bucketafter,
+                  "Bucket next pointer is damaged");
+            PER_ALLOW_DEACTIVATION(child);
+            activated_child = NULL;
+        }
+    }
+    result = 0;
+    goto Done;
+
+Error:
+    PyErr_SetString(PyExc_AssertionError, errormsg);
+    result = -1;
+Done:
+    /* No point updating access time -- this isn't a "real" use. */
+    PER_ALLOW_DEACTIVATION(self);
+    if (activated_child) {
+        PER_ALLOW_DEACTIVATION(activated_child);
+    }
+    return result;
+
+#undef CHECK
+}
+
+/* Sanity-check a BTree.  This is the ._check() method.  Return:
+ *      NULL       Error.  If it's an internal inconsistency in the BTree,
+ *                 AssertionError is set.
+ *      Py_None    No problem found.
+ */
+static PyObject*
+BTree_check(BTree *self)
+{
+    PyObject *result = NULL;
+    int i = BTree_check_inner(self, NULL);
+
+    if (i >= 0) {
+        result = Py_None;
+        Py_INCREF(result);
+    }
+    return result;
+}
+
 /*
 ** _BTree_get
 **
@@ -815,10 +940,10 @@
     if (len < 0)
 	return -1;
     len = (len + 1) / 2;
-    
+
     assert(len > 0); /* If the BTree is empty, it's state is None. */
     assert(self->size == 0); /* We called _BTree_clear(). */
-    
+
     self->data = BTree_Malloc(sizeof(BTreeItem) * len);
     if (self->data == NULL)
 	return -1;
@@ -853,10 +978,10 @@
 	}
 	l++;
     }
-    
+
     if (!firstbucket)
 	firstbucket = (PyObject *)self->data->child;
-	
+
     if (!PyObject_IsInstance(firstbucket, (PyObject *)
 			     (noval ? &SetType : &BucketType))) {
 	PyErr_SetString(PyExc_TypeError,
@@ -1551,6 +1676,8 @@
      "added, or 0 otherwise."},
     {"update",	(PyCFunction) Mapping_update,	METH_O,
      "update(collection)\n\n Add the items from the given collection."},
+    {"_check", (PyCFunction) BTree_check,       METH_NOARGS,
+     "Perform sanity check on BTree, and raise exception if flawed."},
 #ifdef PERSISTENT
     {"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict,
      METH_VARARGS,


=== Zope3/lib/python/Persistence/BTrees/TreeSetTemplate.c 1.3 => 1.4 ===
   {"remove",	(PyCFunction)TreeSet_remove,	METH_VARARGS,
    "remove(id) -- Remove a key from the set"},
+  {"_check", (PyCFunction) BTree_check,       METH_NOARGS,
+   "Perform sanity check on TreeSet, and raise exception if flawed."},
 #ifdef PERSISTENT
   {"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict, METH_VARARGS,
    "_p_resolveConflict() -- Reinitialize from a newly created copy"},