[Zodb-checkins] CVS: Zope3/lib/python/Persistence/BTrees - BTreeTemplate.c:1.1.2.12 BucketTemplate.c:1.1.2.11 MergeTemplate.c:1.1.2.6 SetOpTemplate.c:1.1.2.6 _fsBTree.c:1.1.2.2 intkeymacros.h:1.1.2.3 objectkeymacros.h:1.1.2.2

Tim Peters tim.one@comcast.net
Tue, 4 Jun 2002 19:18:52 -0400


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

Modified Files:
      Tag: Zope-3x-branch
	BTreeTemplate.c BucketTemplate.c MergeTemplate.c 
	SetOpTemplate.c _fsBTree.c intkeymacros.h objectkeymacros.h 
Log Message:
This is the hardest merge.  While I was writing the BTREE_SEARCH macro,
somebody else checked in a widespread change to get rid of all uses of
the TEST_KEY macro, in favor of another macro that checks for errors
from compares.  Then that change and the BTREE_SEARCH change were wedded,
so both need to merged here.  Also added some more docs from the trunk.

CAUTION:  The TEST_KEY_SET_OR macro uses don't always do the "and now I'm
done with this persistent object" dance in error cases.  I don't know
whether that's buggy or not.  It's true on the trunk and on the branch
now.  Someone who thinks they understand what those macros do should
check all uses here and on the trunk (or just tell me if these are bugs,
and if so I'll fix them).


=== Zope3/lib/python/Persistence/BTrees/BTreeTemplate.c 1.1.2.11 => 1.1.2.12 ===
 ** _BTree_get
 **
+** Search a BTree.
+**
+** Arguments
+**      self        a pointer to a BTree
+**      keyarg      the key to search for, as a Python object
+**      has_key     true/false; when false, try to return the associated
+**                  value; when true, return a boolean
+** Return
+**      When has_key false:
+**          If key exists, its associated value.
+**          If key doesn't exist, NULL and KeyError is set.
+**      When has_key true:
+**          A Python int is returned in any case.
+**          If key exists, the depth of the bucket in which it was found.
+**          If key doesn't exist, 0.
 */
 static PyObject *
 _BTree_get(BTree *self, PyObject *keyarg, int has_key)
 {
-  int min, max, i, cmp, copied=1;
-  PyObject *r;
   KEY_TYPE key;
+  int min;              /* index of child to search */
+  PyObject *r = NULL;   /* result object */
+  int copied = 1;
   
   COPY_KEY_FROM_ARG(key, keyarg, copied);
   UNLESS (copied) return NULL;
@@ -32,20 +48,9 @@
   if (!PyPersist_IS_STICKY(self))
       return NULL;
 
+  BTREE_SEARCH(min, self, key, goto Error);
   if (self->len)
     {
-      for (min=0, max=self->len, i=max/2; max-min > 1; i=(min+max)/2)
-        {
-          cmp=TEST_KEY(self->data[i].key, key);
-          if (cmp < 0) min=i;
-          else if (cmp == 0)
-            {
-              min=i;
-              break;
-            }
-          else max=i;
-        }
-      
       if (SameType_Check(self, self->data[min].child)) 
         r=_BTree_get( BTREE(self->data[min].child), keyarg, 
                       has_key ? has_key + 1: 0);
@@ -64,6 +69,7 @@
         r=PyInt_FromLong(0);
     }
 
+Error:
   PyPersist_DECREF(self);
   PyPersist_SetATime(self);
   return r;
@@ -339,7 +345,7 @@
 _BTree_set(BTree *self, PyObject *keyarg, PyObject *value, 
            int unique, int noval)
 {
-    int i, min, max, cmp, grew, copied=1, changed=0, bchanged=0;
+    int min, grew, copied=1, changed=0, bchanged=0;
     BTreeItem *d;
     KEY_TYPE key;
 
@@ -361,21 +367,8 @@
 	}
     }
 
-    /* Binary search to find insertion point */
-    for (min=0, max=self->len, i=max/2; max-min > 1; i=(max+min)/2) {
-	d = self->data + i;
-	cmp = TEST_KEY(d->key, key);
-	if (cmp < 0) 
-	    min=i;
-	else if (cmp == 0) {
-	    min=i;
-	    break;
-	}
-	else 
-	    max=i;
-    }
-
-    d=self->data+min;
+    BTREE_SEARCH(min, self, key, goto err);
+    d = self->data + min;
     if (SameType_Check(self, d->child))
 	grew= _BTree_set((BTree *)d->child, keyarg, value, unique, noval);
     else
@@ -839,7 +832,7 @@
 static int
 BTree_findRangeEnd(BTree *self, PyObject *keyarg, int low, 
                    Bucket **bucket, int *offset) {
-  int min, max, i=0, cmp, copied=1;
+  int min, i, copied=1;
   KEY_TYPE key;
 
   COPY_KEY_FROM_ARG(key, keyarg, copied);
@@ -850,18 +843,7 @@
   
   UNLESS (self->data && self->len) return 0;
   
-  for (min=0, max=self->len, i=max/2; max-min > 1; i=(min+max)/2)
-    {
-      cmp=TEST_KEY(self->data[i].key, key);
-      if (cmp < 0) min=i;
-      else if (cmp == 0)
-	{
-	  min=i;
-	  break;
-	}
-      else max=i;
-    }
-
+  BTREE_SEARCH(min, self, key, return -1);
   if (SameType_Check(self, self->data[min].child)) 
     {
       self=BTREE(self->data[min].child);


=== Zope3/lib/python/Persistence/BTrees/BucketTemplate.c 1.1.2.10 => 1.1.2.11 ===
   for (min=0, max=self->len, i=max/2, l=max; i != l; l=i, i=(min+max)/2)
     {
-      cmp=TEST_KEY(self->keys[i], key);
-      if (PyErr_Occurred()) goto err;
+      TEST_KEY_SET_OR(cmp, self->keys[i], key) goto err;
 
       if (cmp < 0) min=i;
       else if (cmp == 0)
@@ -161,7 +160,8 @@
 
   for (min=0, max=l=self->len, i=max/2; i != l; l=i, i=(min+max)/2)
     {
-      if ((cmp=TEST_KEY(self->keys[i], key)) < 0) min=i;
+      TEST_KEY_SET_OR(cmp, self->keys[i], key) goto err;
+      if (cmp < 0) min=i;
       else if (cmp==0)
 	{
 	  if (v)			/* Assign value to key */
@@ -485,7 +485,10 @@
 
   for (min=0, max=self->len, i=max/2, l=max; i != l; l=i, i=(min+max)/2) 
     {
-      cmp=TEST_KEY(self->keys[i], key);
+      /* XXX should this do a PyPersist_I'm_Done dance on failure?
+       * XXX The trunk code doesn't, but it doesn't feel right there either.
+       */
+      TEST_KEY_SET_OR(cmp, self->keys[i], key) return -1;
       if (cmp < 0)
 	min=i;
       else if (cmp == 0)


=== Zope3/lib/python/Persistence/BTrees/MergeTemplate.c 1.1.2.5 => 1.1.2.6 ===
   while (i1.position >= 0 && i2.position >= 0 && i3.position >= 0)
     {
-      cmp12=TEST_KEY(i1.key, i2.key);
-      cmp13=TEST_KEY(i1.key, i3.key);
+      TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
+      TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
       if (cmp12==0)
         {
           if (cmp13==0)
@@ -144,7 +144,7 @@
         }
       else
         {                       /* Both keys changed */
-          cmp23=TEST_KEY(i2.key, i3.key);
+          TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
           if (cmp23==0)
             {                   /* dualing inserts or deletes */
               merge_error(i1.position, i2.position, i3.position, 4);
@@ -178,7 +178,7 @@
 
   while (i2.position >= 0 && i3.position >= 0)
     {                           /* New inserts */
-      cmp23=TEST_KEY(i2.key, i3.key);
+      TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
       if (cmp23==0)
         {                       /* dualing inserts */
           merge_error(i1.position, i2.position, i3.position, 6);
@@ -198,7 +198,7 @@
 
   while (i1.position >= 0 && i2.position >= 0)
     {                           /* deleting i3 */
-      cmp12=TEST_KEY(i1.key, i2.key);
+      TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
       if (cmp12 > 0)
         {                       /* insert i2 */
           if (merge_output(r, &i2, mapping) < 0) goto err;
@@ -218,7 +218,7 @@
 
   while (i1.position >= 0 && i3.position >= 0)
     {                           /* deleting i2 */
-      cmp13=TEST_KEY(i1.key, i3.key);
+      TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
       if (cmp13 > 0)
         {                       /* insert i3 */
           if (merge_output(r, &i3, mapping) < 0) goto err;


=== Zope3/lib/python/Persistence/BTrees/SetOpTemplate.c 1.1.2.5 => 1.1.2.6 ===
   while (i1.position >= 0 && i2.position >= 0)
     {
-      cmp=TEST_KEY(i1.key, i2.key);
+      TEST_KEY_SET_OR(cmp, i1.key, i2.key) goto err;
       if(cmp < 0)
 	{
 	  if(c1)


=== Zope3/lib/python/Persistence/BTrees/_fsBTree.c 1.1.2.1 => 1.1.2.2 ===
 #define KEY_TYPE char2
 #define KEY_CHECK(K) (PyString_Check(K) && PyString_GET_SIZE(K)==2)
-#define TEST_KEY(K, T) ((*(K) < *(T) || (*(K) == *(T) && (K)[1] < (T)[1])) ? -1 : ((*(K) == *(T) && (K)[1] == (T)[1]) ? 0 : 1))
+#define TEST_KEY_SET_OR(V, K, T) if ( ( (V) = ((*(K) < *(T) || (*(K) == *(T) && (K)[1] < (T)[1])) ? -1 : ((*(K) == *(T) && (K)[1] == (T)[1]) ? 0 : 1)) ), 0 )
 #define DECREF_KEY(KEY)
 #define INCREF_KEY(k)
 #define COPY_KEY(KEY, E) (*(KEY)=*(E), (KEY)[1]=(E)[1])


=== Zope3/lib/python/Persistence/BTrees/intkeymacros.h 1.1.2.2 => 1.1.2.3 ===
 #define KEY_TYPE int
 #define KEY_CHECK PyInt_Check
-#define TEST_KEY(K, T) (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0)) 
+#define TEST_KEY_SET_OR(V, K, T) if ( ( (V) = (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0)) ) , 0 )
 #define DECREF_KEY(KEY)
 #define INCREF_KEY(k)
 #define COPY_KEY(KEY, E) (KEY=(E))


=== Zope3/lib/python/Persistence/BTrees/objectkeymacros.h 1.1.2.1 => 1.1.2.2 ===
 #define KEY_TYPE PyObject *
-#define TEST_KEY(KEY, TARGET) PyObject_Compare((KEY),(TARGET))
+#define TEST_KEY_SET_OR(V, KEY, TARGET) if ( ( (V) = PyObject_Compare((KEY),(TARGET)) ), PyErr_Occurred() )
 #define INCREF_KEY(k) Py_INCREF(k)
 #define DECREF_KEY(KEY) Py_DECREF(KEY)
 #define COPY_KEY(KEY, E) KEY=(E)