[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"},