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

[Tim Peters]

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

Modified Files:
	BTreeTemplate.c BucketTemplate.c 
Log Message:
Moving closer to exclusive range searches.  Bucket_findRangeEnd() grew a
new exclude_equal Boolean argument, and the guts changed to "do the
right thing" with it.  For now, all its callers were changed to pass
exclude_equal=0, which *should* (if I didn't screw up the logic) yield
results identical to what we've been getting all along, in all cases.

Part of the point to checking this in now is to be sure it really is
semantically neutral this way; most of the point is so that if I don't
finish the rest this afternoon, I can get at this key & delicate change
from home via CVS.


=== Zope3/src/zodb/btrees/BTreeTemplate.c 1.3 => 1.4 ===
--- Zope3/src/zodb/btrees/BTreeTemplate.c:1.3	Fri Feb 21 12:33:01 2003
+++ Zope3/src/zodb/btrees/BTreeTemplate.c	Fri Feb 21 16:47:15 2003
@@ -1219,7 +1219,7 @@
     }
 
     /* Search the bucket for a suitable key. */
-    i = Bucket_findRangeEnd(pbucket, keyarg, low, offset);
+    i = Bucket_findRangeEnd(pbucket, keyarg, low, 0, offset);
     if (i < 0)
         goto Done;
     if (i > 0) {


=== Zope3/src/zodb/btrees/BucketTemplate.c 1.5 => 1.6 ===
--- Zope3/src/zodb/btrees/BucketTemplate.c:1.5	Fri Feb 21 14:07:14 2003
+++ Zope3/src/zodb/btrees/BucketTemplate.c	Fri Feb 21 16:47:15 2003
@@ -598,6 +598,9 @@
  Arguments:     self        The bucket
                 keyarg      The key to match against
                 low         Boolean; true for low end of range, false for high
+                exclude_equal  Boolean; if true, don't accept an exact match,
+                	       and if there is one then move right if low and
+                	       left if !low.
                 offset      The output offset
 
  If low true, *offset <- index of the smallest item >= key,
@@ -609,9 +612,9 @@
       1     The correct index was stored into *offset
      -1     Error
 
- Example:  Suppose the keys are [2, 4].  Searching for 2 sets *offset to 0 and
- returns 1 regardless of low.  Searching for 4 sets *offset to 1 and returns
- 1 regardless of low.
+ Example:  Suppose the keys are [2, 4], and exclude_equal is false.  Searching
+ for 2 sets *offset to 0 and returns 1 regardless of low.  Searching for 4
+ sets *offset to 1 and returns 1 regardless of low.
  Searching for 1:
      If low true, sets *offset to 0, returns 1.
      If low false, returns 0.
@@ -621,9 +624,12 @@
  Searching for 5:
      If low true, returns 0.
      If low false, sets *offset to 1, returns 1.
+
+ The 1, 3 and 5 examples are the same when exclude_equal is true.
  */
 static int
-Bucket_findRangeEnd(Bucket *self, PyObject *keyarg, int low, int *offset)
+Bucket_findRangeEnd(Bucket *self, PyObject *keyarg, int low, int exclude_equal,
+		    int *offset)
 {
     int i, cmp;
     int result = -1;    /* until proven innocent */
@@ -638,18 +644,24 @@
         return -1;
 
     BUCKET_SEARCH(i, cmp, self, key, goto Done);
-    if (cmp == 0)   /* exact match at index i */
-        result = 1;
-
-    /* Else keys[i-1] < key < keys[i], picturing infinities at OOB indices */
-    else if (low)   /* i has the smallest item > key, unless i is OOB */
-        result = i < self->len;
-
-    else {          /* i-1 has the largest item < key, unless i-1 is 0OB */
-        --i;
-        result = i >= 0;
+    if (cmp == 0) {
+    	/* exact match at index i */
+    	if (exclude_equal) {
+	    /* but we don't want an exact match */
+            if (low)
+                ++i;
+            else
+                --i;
+        }
     }
+    /* Else keys[i-1] < key < keys[i], picturing infinities at OOB indices,
+     * and i has the smallest item > key, which is correct for low.
+     */
+    else if (! low)
+        /* i-1 has the largest item < key (unless i-1 is 0OB) */
+        --i;
 
+    result = 0 <= i && i < self->len;
     if (result)
         *offset = i;
 
@@ -674,7 +686,7 @@
   /* Find the low range */
   if (key)
     {
-      if ((rc = Bucket_findRangeEnd(self, key, min, &offset)) <= 0)
+      if ((rc = Bucket_findRangeEnd(self, key, min, 0, &offset)) <= 0)
         {
           if (rc < 0) return NULL;
           goto empty;
@@ -726,7 +738,7 @@
   /* Find the low range */
   if (f && f != Py_None)
     {
-      UNLESS (rc = Bucket_findRangeEnd(self, f, 1, low))
+      UNLESS (rc = Bucket_findRangeEnd(self, f, 1, 0, low))
         {
           if (rc < 0) return -1;
           goto empty;
@@ -737,7 +749,7 @@
   /* Find the high range */
   if (l && l != Py_None)
     {
-      UNLESS (rc = Bucket_findRangeEnd(self, l, 0, high))
+      UNLESS (rc = Bucket_findRangeEnd(self, l, 0, 0, high))
         {
           if (rc < 0) return -1;
           goto empty;