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

[Tim Peters]

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

Modified Files:
	BTreeTemplate.c 
Log Message:
BTree_rangeSearch():  Writing an exhaustive range-search test against
a degenerate BTree turned up lots of other holes in this driver.  Worst,
if you do tree.keys(lo, hi), the true range may be empty even if lo < hi,
and there are keys >= lo in the tree, and keys <= hi in the tree (all of
that does *not* imply there's a key with lo <= key <= hi!).

For xample, if lo=2 and hi=3, 2 and 3 aren't in the tree, but 1 and 4 are.
Then the low-end search for 2 finds 4, the high-end search for 3 finds 1,
but they're "in the wrong order", and since they may not even be in the
same bucket, there's no simple way to determine whether that's the case.
This introduces a constant-time method to resolve such ambiguities,


=== Zope3/lib/python/Persistence/BTrees/BTreeTemplate.c 1.17 => 1.18 ===
   UNLESS (self->data && self->len) goto empty;
 
-  /* If f and l were both passed in, ensure f <= l. */
-  if (f && f != Py_None && l && l != Py_None)
-    {
-      int cmp;
-      KEY_TYPE first;
-      KEY_TYPE last;
-      int copied = 1;
-
-      COPY_KEY_FROM_ARG(first, f, copied);
-      UNLESS (copied) goto err;
-      COPY_KEY_FROM_ARG(last, l, copied);
-      UNLESS (copied) goto err;
-
-      TEST_KEY_SET_OR(cmp, first, last) goto err;
-      if (cmp > 0) goto empty;
-    }
-
   /* Find the low range */
 
   if (f && f != Py_None)
@@ -1241,18 +1224,62 @@
       PyPersist_SetATime(highbucket);
     }
 
+  /* It's still possible that the range is empty, even if f < l.  For
+   * example, if f=3 and l=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 (f && f != Py_None             /* both args user-supplied */
+      && l && l != Py_None
+      && 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);
 
-  f=newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
+  f = newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
   Py_DECREF(lowbucket);
   Py_DECREF(highbucket);
   return f;
 
+ err_and_decref_buckets:
+  Py_DECREF(lowbucket);
+  Py_DECREF(highbucket);
+
  err:
   PyPersist_DECREF(self);
   PyPersist_SetATime(self);
   return NULL;
+
+ empty_and_decref_buckets:
+  Py_DECREF(lowbucket);
+  Py_DECREF(highbucket);
 
  empty:
   PyPersist_DECREF(self);