[Zodb-checkins] CVS: Zope/lib/python/BTrees - BucketTemplate.c:1.31 MergeTemplate.c:1.11 SetOpTemplate.c:1.15

Tim Peters tim.one@comcast.net
Fri, 31 May 2002 10:58:30 -0400


Update of /cvs-repository/Zope/lib/python/BTrees
In directory cvs.zope.org:/tmp/cvs-serv330

Modified Files:
	BucketTemplate.c MergeTemplate.c SetOpTemplate.c 
Log Message:
Bucket_grow():
+ Added interface docs.
+ Gave it a new "newsize" argument, for when the caller can gain speed
  by knowing in advance how many additional elements are needed.  This
  isn't used yet, but will be by multiunion and planned "lopsided merge"
  optimizations (the intent is to grow the bucket big enough in one
  shot, then memcpy a large slice into the bucket).
+ When doubling the size, now sets a MemoryError exception on int
  overflow.


=== Zope/lib/python/BTrees/BucketTemplate.c 1.30 => 1.31 ===
 }
 
+/*
+** Bucket_grow
+**
+** Resize a bucket.
+**
+** Arguments:   self    The bucket.
+**              newsize The new maximum capacity.  If < 0, double the
+**                      current size unless the bucket is currently empty,
+**                      in which case use MIN_BUCKET_ALLOC.
+**              noval   Boolean; if true, allocate only key space and not
+**                      value space
+**
+** Returns:     -1      on error, and MemoryError exception is set
+**               0      on success
+*/
 static int 
-Bucket_grow(Bucket *self, int noval)
+Bucket_grow(Bucket *self, int newsize, int noval)
 {
   KEY_TYPE *keys;
   VALUE_TYPE *values;
 
   if (self->size)
     {
-      UNLESS (keys=PyRealloc(self->keys, sizeof(KEY_TYPE)*self->size*2))
+      if (newsize < 0)
+        newsize = self->size * 2;
+      if (newsize < 0)    /* int overflow */
+        goto Overflow;
+      UNLESS (keys = PyRealloc(self->keys, sizeof(KEY_TYPE) * newsize))
         return -1;
-      
+
       UNLESS (noval)
         {
-          UNLESS (values=PyRealloc(self->values,
-                                   sizeof(VALUE_TYPE)*self->size*2))
+          UNLESS (values = PyRealloc(self->values,
+                                      sizeof(VALUE_TYPE) * newsize))
             return -1;
-          self->values=values;
+          self->values = values;
         }
-      self->keys=keys;
-      self->size*=2;
+      self->keys = keys;
     }
   else
     {
-      UNLESS (self->keys=PyMalloc(sizeof(KEY_TYPE)*MIN_BUCKET_ALLOC))
-        return -1;
-      UNLESS (noval || 
-              (self->values=PyMalloc(sizeof(VALUE_TYPE)*MIN_BUCKET_ALLOC))
-              )
+      if (newsize < 0)
+        newsize = MIN_BUCKET_ALLOC;
+      UNLESS (self->keys = PyMalloc(sizeof(KEY_TYPE) * newsize))
         return -1;
-      self->size=MIN_BUCKET_ALLOC;
+      UNLESS (noval)
+        {
+          UNLESS (self->values = PyMalloc(sizeof(VALUE_TYPE) * newsize))
+            return -1;
+        }
     }
-  
+  self->size = newsize;
   return 0;
+
+Overflow:
+  PyErr_NoMemory();
+  return -1;  
 }
 
 /*
@@ -213,7 +237,7 @@
       goto err;
     }
 
-  if (self->len==self->size && Bucket_grow(self, noval) < 0) goto err;
+  if (self->len==self->size && Bucket_grow(self, -1, noval) < 0) goto err;
 
   if (max != i) i++;
 


=== Zope/lib/python/BTrees/MergeTemplate.c 1.10 => 1.11 ===
 merge_output(Bucket *r, SetIteration *i, int mapping)
 {
-  if(r->len >= r->size && Bucket_grow(r, ! mapping) < 0) return -1;
+  if(r->len >= r->size && Bucket_grow(r, -1, ! mapping) < 0) return -1;
   COPY_KEY(r->keys[r->len], i->key);
   INCREF_KEY(r->keys[r->len]);
   if (mapping)


=== Zope/lib/python/BTrees/SetOpTemplate.c 1.14 => 1.15 ===
   while (i->position >= 0)
     {
-      if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) return -1;
+      if(r->len >= r->size && Bucket_grow(r, -1, ! merge) < 0) return -1;
       COPY_KEY(r->keys[r->len], i->key);
       INCREF_KEY(r->keys[r->len]);
 
@@ -228,7 +228,7 @@
 	{
 	  if(c1)
 	    {
-	      if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
+	      if(r->len >= r->size && Bucket_grow(r, -1, ! merge) < 0) goto err;
               COPY_KEY(r->keys[r->len], i1.key);
               INCREF_KEY(r->keys[r->len]);
               if (merge)
@@ -244,7 +244,7 @@
 	{
 	  if(c12)
 	    {
-	      if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
+	      if(r->len >= r->size && Bucket_grow(r, -1, ! merge) < 0) goto err;
               COPY_KEY(r->keys[r->len], i1.key);
               INCREF_KEY(r->keys[r->len]);
               if (merge)
@@ -265,7 +265,7 @@
 	{
 	  if(c2)
 	    {
-	      if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
+	      if(r->len >= r->size && Bucket_grow(r, -1, ! merge) < 0) goto err;
               COPY_KEY(r->keys[r->len], i2.key);
               INCREF_KEY(r->keys[r->len]);
               if (merge)
@@ -447,7 +447,7 @@
         if (setiter.next(&setiter) < 0)
             goto Error;
         while (setiter.position >= 0) {
-            if (result->len >= result->size && Bucket_grow(result, 1) < 0)
+            if (result->len >= result->size && Bucket_grow(result, -1, 1) < 0)
                 goto Error;
             COPY_KEY(result->keys[result->len], setiter.key);
             ++result->len;