[Zodb-checkins] CVS: Zope3/src/zodb/btrees - BTreeTemplate.c:1.6 BucketTemplate.c:1.8

Tim Peters tim.one@comcast.net
Fri, 21 Feb 2003 18:24:15 -0500


Update of /cvs-repository/Zope3/src/zodb/btrees
In directory cvs.zope.org:/tmp/cvs-serv30188/src/zodb/btrees

Modified Files:
	BTreeTemplate.c BucketTemplate.c 
Log Message:
BTree_findRangeEnd() also needed to grow an exclude_equal boolean arg.
Added that, and fiddled its callers to pass false for now.  As before,
there should *still* be no change in what range searches do yet.
Also added XXX comments at several non-obvious places that are also
going to need changing.


=== Zope3/src/zodb/btrees/BTreeTemplate.c 1.5 => 1.6 ===
--- Zope3/src/zodb/btrees/BTreeTemplate.c:1.5	Fri Feb 21 17:17:33 2003
+++ Zope3/src/zodb/btrees/BTreeTemplate.c	Fri Feb 21 18:24:14 2003
@@ -1127,6 +1127,10 @@
  If low, return bucket and index of the smallest item >= key,
  otherwise return bucket and index of the largest item <= key.
 
+ If exclude_equal, exact matches aren't acceptable; if one is found,
+ move right if low, or left if !low (this is for range searches exclusive
+ of an endpoint).
+
  Return:
     -1      Error; offset and bucket unchanged
      0      Not found; offset and bucket unchanged
@@ -1172,7 +1176,7 @@
        at first.  This is clumsy to get at, but efficient.
 */
 static int
-BTree_findRangeEnd(BTree *self, PyObject *keyarg, int low,
+BTree_findRangeEnd(BTree *self, PyObject *keyarg, int low, int exclude_equal,
                    Bucket **bucket, int *offset) {
     Sized *deepest_smaller = NULL;      /* last possibility to move left */
     int deepest_smaller_is_btree = 0;   /* Boolean; if false, it's a bucket */
@@ -1219,7 +1223,7 @@
     }
 
     /* Search the bucket for a suitable key. */
-    i = Bucket_findRangeEnd(pbucket, keyarg, low, 0, offset);
+    i = Bucket_findRangeEnd(pbucket, keyarg, low, exclude_equal, offset);
     if (i < 0)
         goto Done;
     if (i > 0) {
@@ -1296,7 +1300,7 @@
 
   if (key)
     {
-      if ((rc = BTree_findRangeEnd(self, key, min, &bucket, &offset)) <= 0)
+      if ((rc = BTree_findRangeEnd(self, key, min, 0, &bucket, &offset)) <= 0)
         {
           if (rc < 0) goto err;
           goto empty;
@@ -1401,7 +1405,7 @@
   /* Find the low range */
   if (min != Py_None)
     {
-      if ((rc = BTree_findRangeEnd(self, min, 1,
+      if ((rc = BTree_findRangeEnd(self, min, 1, 0,
       				   &lowbucket, &lowoffset)) <= 0)
         {
           if (rc < 0) goto err;
@@ -1413,12 +1417,13 @@
       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,
+      if ((rc = BTree_findRangeEnd(self, max, 0, 0,
       				   &highbucket, &highoffset)) <= 0)
         {
           Py_DECREF(lowbucket);
@@ -1428,6 +1433,7 @@
     }
   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))


=== Zope3/src/zodb/btrees/BucketTemplate.c 1.7 => 1.8 ===
--- Zope3/src/zodb/btrees/BucketTemplate.c:1.7	Fri Feb 21 17:17:33 2003
+++ Zope3/src/zodb/btrees/BucketTemplate.c	Fri Feb 21 18:24:14 2003
@@ -745,7 +745,7 @@
           goto empty;
         }
     }
-  else *low = 0;
+  else *low = 0;	/* XXX if excludemin, get rid of first elt */
 
   /* Find the high range */
   if (max != Py_None)
@@ -756,7 +756,7 @@
           goto empty;
         }
     }
-  else *high = self->len - 1;
+  else *high = self->len - 1;	/* XXX if excludemax, get rid of last elt */
 
   /* If min < max to begin with, it's quite possible that low > high now. */
   if (*low <= *high)