[Zodb-checkins] CVS: Zope3/src/zodb/btrees - BTreeTemplate.c:1.8 BucketTemplate.c:1.10
Tim Peters
tim.one@comcast.net
Sat, 22 Feb 2003 01:00:48 -0500
Update of /cvs-repository/Zope3/src/zodb/btrees
In directory cvs.zope.org:/tmp/cvs-serv13181/src/zodb/btrees
Modified Files:
BTreeTemplate.c BucketTemplate.c
Log Message:
Exclusive range searches work now.
Dilemma: the DegenerateBTree test class runs expensive tests, and the
very expensive testDeletes() method in particular takes 4x longer now
(because there are 4x as many ways a range search can be specified now).
However, this test class has provoked every non-conflict-resolution BTree
bug I've seen, and also found nasty errors in the new implementation of
exclusive range searches (which turned out to be messy in some end cases
involving trees with multiple buckets having a single item per bucket --
which happens in real life after an unfortunate sequence of deletes).
So I'm loathe to weaken this test, but also loathe to spend so much time
in it too. Oh, well -- a bug in BTrees is deadly, so better safe than
sorry.
=== Zope3/src/zodb/btrees/BTreeTemplate.c 1.7 => 1.8 ===
--- Zope3/src/zodb/btrees/BTreeTemplate.c:1.7 Fri Feb 21 22:40:22 2003
+++ Zope3/src/zodb/btrees/BTreeTemplate.c Sat Feb 22 01:00:17 2003
@@ -1380,137 +1380,164 @@
static PyObject *
BTree_rangeSearch(BTree *self, PyObject *args, PyObject *kw, char type)
{
- PyObject *min = Py_None;
- PyObject *max = Py_None;
- int excludemin = 0;
- int excludemax = 0;
- int rc;
- Bucket *lowbucket = NULL;
- Bucket *highbucket = NULL;
- int lowoffset;
- int highoffset;
- PyObject *result;
-
- if (args) {
- if (! PyArg_ParseTupleAndKeywords(args, kw, "|OOii", search_keywords,
- &min,
- &max,
- &excludemin,
- &excludemax))
- return NULL;
- }
-
- PyPersist_INCREF(self);
- if (!PyPersist_IS_STICKY(self))
- return NULL;
-
- UNLESS (self->data && self->len) goto empty;
-
- /* Find the low range */
- if (min != Py_None)
- {
- if ((rc = BTree_findRangeEnd(self, min, 1, 0,
- &lowbucket, &lowoffset)) <= 0)
- {
- if (rc < 0) goto err;
- goto empty;
+ PyObject *min = Py_None;
+ PyObject *max = Py_None;
+ int excludemin = 0;
+ int excludemax = 0;
+ int rc;
+ Bucket *lowbucket = NULL;
+ Bucket *highbucket = NULL;
+ int lowoffset;
+ int highoffset;
+ PyObject *result;
+
+ if (args) {
+ if (! PyArg_ParseTupleAndKeywords(args, kw, "|OOii", search_keywords,
+ &min,
+ &max,
+ &excludemin,
+ &excludemax))
+ return NULL;
+ }
+
+ PyPersist_INCREF(self);
+ if (!PyPersist_IS_STICKY(self))
+ return NULL;
+
+ UNLESS (self->data && self->len) goto empty;
+
+ /* Find the low range */
+ if (min != Py_None) {
+ if ((rc = BTree_findRangeEnd(self, min, 1, excludemin,
+ &lowbucket, &lowoffset)) <= 0) {
+ if (rc < 0) goto err;
+ goto empty;
}
}
- else
- {
- lowbucket = self->firstbucket;
- Py_INCREF(lowbucket);
- lowoffset = 0;
- /* XXX If excludemin, goof around getting rid of the first element. */
- }
-
- /* Find the high range */
- if (max != Py_None)
- {
- if ((rc = BTree_findRangeEnd(self, max, 0, 0,
- &highbucket, &highoffset)) <= 0)
- {
- Py_DECREF(lowbucket);
- if (rc < 0) goto err;
- goto empty;
+ else {
+ lowbucket = self->firstbucket;
+ lowoffset = 0;
+ if (excludemin) {
+ int bucketlen;
+ UNLESS (PER_USE(lowbucket)) goto err;
+ bucketlen = lowbucket->len;
+ PER_UNUSE(lowbucket);
+ if (bucketlen > 1)
+ lowoffset = 1;
+ else if (self->len < 2)
+ goto empty;
+ else { /* move to first item in next bucket */
+ Bucket *next;
+ UNLESS (PER_USE(lowbucket)) goto err;
+ next = lowbucket->next;
+ PER_UNUSE(lowbucket);
+ assert(next != NULL);
+ lowbucket = next;
+ /* and lowoffset is still 0 */
+ assert(lowoffset == 0);
+ }
+ }
+ Py_INCREF(lowbucket);
+ }
+
+ /* Find the high range */
+ if (max != Py_None) {
+ if ((rc = BTree_findRangeEnd(self, max, 0, excludemax,
+ &highbucket, &highoffset)) <= 0) {
+ Py_DECREF(lowbucket);
+ if (rc < 0) goto err;
+ goto empty;
}
}
- else
- {
- /* XXX If excludemax, goof around getting rid of the last element. */
- highbucket = BTree_lastBucket(self);
- assert(highbucket != NULL); /* we know self isn't empty */
- UNLESS (PER_USE(highbucket))
- {
- Py_DECREF(lowbucket);
- Py_DECREF(highbucket);
- goto err;
+ else {
+ int bucketlen;
+ highbucket = BTree_lastBucket(self);
+ assert(highbucket != NULL); /* we know self isn't empty */
+ UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
+ bucketlen = highbucket->len;
+ PER_UNUSE(highbucket);
+ highoffset = bucketlen - 1;
+ if (excludemax) {
+ if (highoffset > 0)
+ --highoffset;
+ else if (self->len < 2)
+ goto empty_and_decref_buckets;
+ else { /* move to last item of preceding bucket */
+ int status;
+ assert(highbucket != self->firstbucket);
+ Py_DECREF(highbucket);
+ status = PreviousBucket(&highbucket, self->firstbucket);
+ if (status < 0) {
+ Py_DECREF(lowbucket);
+ goto err;
+ }
+ assert(status > 0);
+ Py_INCREF(highbucket);
+ UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
+ highoffset = highbucket->len - 1;
+ PER_UNUSE(highbucket);
+ }
}
- highoffset = highbucket->len - 1;
- PyPersist_DECREF(highbucket);
- PyPersist_SetATime(highbucket);
- }
-
- /* It's still possible that the range is empty, even if min < max. For
- * example, if min=3 and max=4, and 3 and 4 aren't in the BTree, but 2 and
- * 5 are, then the low position points to the 5 now and the high position
- * points to the 2 now. They're not necessarily even in the same bucket,
- * so there's no trick we can play with pointer compares to get out
- * cheap in general.
- */
- if (lowbucket == highbucket && lowoffset > highoffset)
- goto empty_and_decref_buckets; /* definitely empty */
-
- /* The buckets differ, or they're the same and the offsets show a non-
- * empty range.
- */
- if (min != Py_None && max != Py_None && /* both args user-supplied */
- lowbucket != highbucket) /* and different buckets */
- {
- KEY_TYPE first;
- KEY_TYPE last;
- int cmp;
-
- /* Have to check the hard way: see how the endpoints compare. */
- UNLESS (PER_USE(lowbucket)) goto err_and_decref_buckets;
- COPY_KEY(first, lowbucket->keys[lowoffset]);
- PER_ALLOW_DEACTIVATION(lowbucket);
- PER_ACCESSED(lowbucket);
-
- UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
- COPY_KEY(last, highbucket->keys[highoffset]);
- PER_ALLOW_DEACTIVATION(highbucket);
- PER_ACCESSED(highbucket);
-
- TEST_KEY_SET_OR(cmp, first, last) goto err_and_decref_buckets;
- if (cmp > 0) goto empty_and_decref_buckets;
- }
-
- PyPersist_DECREF(self);
- PyPersist_SetATime(self);
-
- result = newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
- Py_DECREF(lowbucket);
- Py_DECREF(highbucket);
- return result;
+ assert(highoffset >= 0);
+ }
+
+ /* It's still possible that the range is empty, even if min < max. For
+ * example, if min=3 and max=4, and 3 and 4 aren't in the BTree, but 2 and
+ * 5 are, then the low position points to the 5 now and the high position
+ * points to the 2 now. They're not necessarily even in the same bucket,
+ * so there's no trick we can play with pointer compares to get out
+ * cheap in general.
+ */
+ if (lowbucket == highbucket && lowoffset > highoffset)
+ goto empty_and_decref_buckets; /* definitely empty */
+
+ /* The buckets differ, or they're the same and the offsets show a non-
+ * empty range.
+ */
+ if (min != Py_None && max != Py_None && /* both args user-supplied */
+ lowbucket != highbucket) /* and different buckets */ {
+ KEY_TYPE first;
+ KEY_TYPE last;
+ int cmp;
+
+ /* Have to check the hard way: see how the endpoints compare. */
+ UNLESS (PER_USE(lowbucket)) goto err_and_decref_buckets;
+ COPY_KEY(first, lowbucket->keys[lowoffset]);
+ PER_UNUSE(lowbucket);
+
+ UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
+ COPY_KEY(last, highbucket->keys[highoffset]);
+ PER_UNUSE(highbucket);
+
+ TEST_KEY_SET_OR(cmp, first, last) goto err_and_decref_buckets;
+ if (cmp > 0) goto empty_and_decref_buckets;
+ }
+
+ PyPersist_DECREF(self);
+ PyPersist_SetATime(self);
+
+ result = newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
+ Py_DECREF(lowbucket);
+ Py_DECREF(highbucket);
+ return result;
err_and_decref_buckets:
- Py_DECREF(lowbucket);
- Py_DECREF(highbucket);
+ Py_DECREF(lowbucket);
+ Py_DECREF(highbucket);
err:
- PyPersist_DECREF(self);
- PyPersist_SetATime(self);
- return NULL;
+ PyPersist_DECREF(self);
+ PyPersist_SetATime(self);
+ return NULL;
empty_and_decref_buckets:
- Py_DECREF(lowbucket);
- Py_DECREF(highbucket);
+ Py_DECREF(lowbucket);
+ Py_DECREF(highbucket);
empty:
- PyPersist_DECREF(self);
- PyPersist_SetATime(self);
- return newBTreeItems(type, 0, 0, 0, 0);
+ PyPersist_DECREF(self);
+ PyPersist_SetATime(self);
+ return newBTreeItems(type, 0, 0, 0, 0);
}
/*
=== Zope3/src/zodb/btrees/BucketTemplate.c 1.9 => 1.10 ===
--- Zope3/src/zodb/btrees/BucketTemplate.c:1.9 Fri Feb 21 22:40:22 2003
+++ Zope3/src/zodb/btrees/BucketTemplate.c Sat Feb 22 01:00:17 2003
@@ -724,53 +724,63 @@
Bucket_rangeSearch(Bucket *self, PyObject *args, PyObject *kw,
int *low, int *high)
{
- PyObject *min = Py_None;
- PyObject *max = Py_None;
- int excludemin = 0;
- int excludemax = 0;
- int rc;
-
- if (args) {
- if (! PyArg_ParseTupleAndKeywords(args, kw, "|OOii", search_keywords,
- &min,
- &max,
- &excludemin,
- &excludemax))
- return -1;
- }
-
- UNLESS (self->len) goto empty;
-
- /* Find the low range */
- if (min != Py_None)
- {
- UNLESS (rc = Bucket_findRangeEnd(self, min, 1, 0, low))
- {
- if (rc < 0) return -1;
- goto empty;
- }
+ PyObject *min = Py_None;
+ PyObject *max = Py_None;
+ int excludemin = 0;
+ int excludemax = 0;
+ int rc;
+
+ if (args) {
+ if (! PyArg_ParseTupleAndKeywords(args, kw, "|OOii", search_keywords,
+ &min,
+ &max,
+ &excludemin,
+ &excludemax))
+ return -1;
}
- else *low = 0; /* XXX if excludemin, get rid of first elt */
- /* Find the high range */
- if (max != Py_None)
- {
- UNLESS (rc = Bucket_findRangeEnd(self, max, 0, 0, high))
- {
- if (rc < 0) return -1;
- goto empty;
+ UNLESS (self->len) goto empty;
+
+ /* Find the low range */
+ if (min != Py_None) {
+ UNLESS (rc = Bucket_findRangeEnd(self, min, 1, excludemin, low)) {
+ if (rc < 0) return -1;
+ goto empty;
}
}
- else *high = self->len - 1; /* XXX if excludemax, get rid of last elt */
+ else {
+ *low = 0;
+ if (excludemin) {
+ if (self->len < 2)
+ goto empty;
+ ++*low;
+ }
+ }
- /* If min < max to begin with, it's quite possible that low > high now. */
- if (*low <= *high)
- return 0;
+ /* Find the high range */
+ if (max != Py_None) {
+ UNLESS (rc = Bucket_findRangeEnd(self, max, 0, excludemax, high)) {
+ if (rc < 0) return -1;
+ goto empty;
+ }
+ }
+ else {
+ *high = self->len - 1;
+ if (excludemax) {
+ if (self->len < 2)
+ goto empty;
+ --*high;
+ }
+ }
+
+ /* If min < max to begin with, it's quite possible that low > high now. */
+ if (*low <= *high)
+ return 0;
empty:
- *low = 0;
- *high = -1;
- return 0;
+ *low = 0;
+ *high = -1;
+ return 0;
}
/*