[Zope-Checkins] CVS: Zope2 - BTreeItemsTemplate.c:1.3.6.1 BTreeModuleTemplate.c:1.4.6.1 BTreeTemplate.c:1.9.6.1 BucketTemplate.c:1.6.6.1 IIBTree.c:1.6.6.1 IOBTree.c:1.6.6.1 Interfaces.py:1.4.6.1 Length.py:1.1.4.1 MergeTemplate.c:1.1.4.1 OIBTree.c:1.5.6.1 OOBTree.c:1.5.6.1 SetOpTemplate.c:1.3.6.1 SetTemplate.c:1.6.6.1 Setup:1.5.6.1 TreeSetTemplate.c:1.5.6.1 __init__.py:1.2.6.1 config.c:1.1.4.1 convert.py:1.1.4.1 intkeymacros.h:1.2.6.1 intvaluemacros.h:1.3.6.1 objectkeymacros.h:1.1.6.1 objectvaluemacros.h:1.2.6.1

Jim Fulton jim@digiciool.com
Thu, 15 Mar 2001 08:10:30 -0500 (EST)


Update of /cvs-repository/Zope2/lib/python/BTrees
In directory korak:/home/jim/atmp/merge/2.3/lib/python/BTrees

Added Files:
      Tag: zope-2_3-branch
	BTreeItemsTemplate.c BTreeModuleTemplate.c BTreeTemplate.c 
	BucketTemplate.c IIBTree.c IOBTree.c Interfaces.py Length.py 
	MergeTemplate.c OIBTree.c OOBTree.c SetOpTemplate.c 
	SetTemplate.c Setup TreeSetTemplate.c __init__.py config.c 
	convert.py intkeymacros.h intvaluemacros.h objectkeymacros.h 
	objectvaluemacros.h 
Log Message:
Merged changes from Catalog-BTrees-Integration branch.


--- Added File BTreeItemsTemplate.c in package Zope2 ---
/*****************************************************************************
  
  Zope Public License (ZPL) Version 1.0
  -------------------------------------
  
  Copyright (c) Digital Creations.  All rights reserved.
  
  This license has been certified as Open Source(tm).
  
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met:
  
  1. Redistributions in source code must retain the above copyright
     notice, this list of conditions, and the following disclaimer.
  
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions, and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
  
  3. Digital Creations requests that attribution be given to Zope
     in any manner possible. Zope includes a "Powered by Zope"
     button that is installed by default. While it is not a license
     violation to remove this button, it is requested that the
     attribution remain. A significant investment has been put
     into Zope, and this effort will continue if the Zope community
     continues to grow. This is one way to assure that growth.
  
  4. All advertising materials and documentation mentioning
     features derived from or use of this software must display
     the following acknowledgement:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     In the event that the product being advertised includes an
     intact Zope distribution (with copyright and license included)
     then this clause is waived.
  
  5. Names associated with Zope or Digital Creations must not be used to
     endorse or promote products derived from this software without
     prior written permission from Digital Creations.
  
  6. Modified redistributions of any form whatsoever must retain
     the following acknowledgment:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     Intact (re-)distributions of any official Zope release do not
     require an external acknowledgement.
  
  7. Modifications are encouraged but must be packaged separately as
     patches to official Zope releases.  Distributions that do not
     clearly separate the patches from the original work must be clearly
     labeled as unofficial distributions.  Modifications which do not
     carry the name Zope may be packaged in any form, as long as they
     conform to all of the clauses above.
  
  
  Disclaimer
  
    THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
    EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
  
  
  This software consists of contributions made by Digital Creations and
  many individuals on behalf of Digital Creations.  Specific
  attributions are listed in the accompanying credits file.
  
 ****************************************************************************/

typedef struct {
  PyObject_HEAD
  Bucket *firstbucket;			/* First bucket known		*/
  Bucket *currentbucket;		/* Current bucket position	*/
  Bucket *lastbucket;			/* Last bucket position		*/
  int currentoffset;			/* Start count of current bucket*/
  int pseudoindex;			/* Its an indicator		*/
  int first, last;
  char kind;
} BTreeItems;

#define ITEMS(O)((BTreeItems*)(O))

static PyObject *
newBTreeItems(char kind, 
              Bucket *lowbucket, int lowoffset,
              Bucket *highbucket, int highoffset);

static void
BTreeItems_dealloc(BTreeItems *self)
{
  Py_XDECREF(self->firstbucket);
  Py_XDECREF(self->lastbucket);
  Py_XDECREF(self->currentbucket);
  PyMem_DEL(self);
}

static int 
BTreeItems_length_or_nonzero(BTreeItems *self, int nonzero)
{
  int r;
  Bucket *b, *next;

  b=self->firstbucket;
  UNLESS(b) return 0;

  r=self->last + 1 - self->first;

  if (nonzero && r > 0) 
    /* Short-circuit if all we care about is nonempty */
    return 1;

  if (b == self->lastbucket) return r;

  Py_INCREF(b);
  PER_USE_OR_RETURN(b, -1);
  while ((next=b->next)) 
    {
      r += b->len;
      if (nonzero && r > 0) 
        /* Short-circuit if all we care about is nonempty */
        break;

      if (next == self->lastbucket) 
        break; /* we already counted the last bucket */

      Py_INCREF(next);
      PER_ALLOW_DEACTIVATION(b);
      Py_DECREF(b);
      b=next;
      PER_USE_OR_RETURN(b, -1);
    }
  PER_ALLOW_DEACTIVATION(b);
  Py_DECREF(b);

  return r >= 0 ? r : 0;
}

static int
BTreeItems_length( BTreeItems *self)
{                              
  return BTreeItems_length_or_nonzero(self, 0);
}

/*
** BTreeItems_seek
**
** Find the ith position in the BTreeItems.  Pseudoindex is used to
** determine motion relative to the current bucket.
**
** Arguments:  	self		The BTree
**		i		the index to seek to, positive for a forward
**				index (0..n) or negative (-m..-1) (m=n+1)
**
**
** Returns 0 if successful, -1 on failure to seek
*/
static int
BTreeItems_seek(BTreeItems *self, int i) 
{
  int delta, pseudoindex, currentoffset;
  Bucket *b, *currentbucket;

  currentbucket=self->currentbucket;
  UNLESS(currentbucket)
    {
      IndexError(i);
      return -1;
    }

  pseudoindex=self->pseudoindex;
  Py_INCREF(currentbucket);
  currentoffset=self->currentoffset;

  /* Make sure that the index and psuedoindex have the same sign */
  if (pseudoindex < 0 && i >=0) 
    {                                
      /* Position to the start of the sequence. */
      ASSIGNB(currentbucket, self->firstbucket);
      Py_INCREF(currentbucket);
      currentoffset = self->first;

      UNLESS (PER_USE(currentbucket)) goto err;

      /* We need to be careful that we have a valid offset! */
      if (currentoffset >= currentbucket->len)
        {
          switch (firstBucketOffset(&currentbucket, &currentoffset))
            {
            case 0: goto no_match;
            case -1: goto err;
            }
        }
      pseudoindex = 0;
    } 
  else if (self->pseudoindex >= 0 && i < 0) 
    {
      /* Position to the end of the sequence. */
      ASSIGNBC(currentbucket, self->lastbucket);
      currentoffset = self->last;
      UNLESS (PER_USE(currentbucket)) goto err;
      
      /* We need to be careful that we have a valid offset! */
      if (currentoffset >= currentbucket->len)
        {
          switch (lastBucketOffset(&currentbucket, &currentoffset,
                                   self->firstbucket, i))
            {
            case 0: goto no_match;
            case -1: goto err;
            }
        }
      pseudoindex = -1;
    }
  else
    {
      UNLESS (PER_USE(currentbucket)) goto err;
      
      /* We need to be careful that we have a valid offset! */
      if (currentoffset >= currentbucket->len) goto no_match;
    }
                                
  /* Whew, we got here so we have a valid offset! */

  delta = i - pseudoindex;
  if (delta)
    while (delta)
      {
        if (delta < 0) 
          {
            /* First, would we drop below zero? */
            if (pseudoindex >= 0 && pseudoindex + delta < 0) goto no_match;
      
            /* Next, do we have to backup a bucket? */
            if (currentoffset + delta < 0) 
              {
                if (currentbucket == self->firstbucket) goto no_match;
              
                b=PreviousBucket(currentbucket, self->firstbucket, i);
                if (b==NULL) goto no_match;
              
                PER_ALLOW_DEACTIVATION(currentbucket);
                ASSIGNB(currentbucket, b);
                UNLESS (PER_USE(currentbucket)) goto err;

                delta += currentoffset;
                pseudoindex -= currentoffset + 1;

                if ((currentoffset = currentbucket->len - 1) < 0)
                  /* We backed into an empty bucket. Fix the psuedo index */
                  if (++pseudoindex == 0) goto no_match;
              }
            else 
              {	/* Local adjustment */
                pseudoindex += delta;
                currentoffset += delta;
              }

            if (currentbucket == self->firstbucket &&
                currentoffset < self->first) goto no_match;

          } 
        else if (delta > 0)
          {
          
            /* Simple backwards range check */
            if (pseudoindex < 0 && pseudoindex + delta >= 0) 
              goto no_match;
          
            /* Next, do we go forward a bucket? */
            if (currentoffset + delta >= currentbucket->len) 
              {
                while (1)
                  {
                    if (currentbucket == self->lastbucket) goto no_match;

                    if ((b=currentbucket->next) == NULL) goto no_match;
                    delta -= currentbucket->len - currentoffset;
                    pseudoindex += (currentbucket->len - currentoffset);
                    Py_INCREF(b);
                    PER_ALLOW_DEACTIVATION(currentbucket);
                    ASSIGNB(currentbucket, b);
                    UNLESS (PER_USE(currentbucket)) goto err;
                    currentoffset = 0;
                    if (currentbucket->len) break;
                  } 
              }
            else
              {	/* Local adjustment */
                pseudoindex += delta;
                currentoffset += delta;
              }
            if (currentbucket == self->lastbucket &&
                currentoffset > self->last) goto no_match;
          
          }

        delta = i - pseudoindex;
      }
  else
    {                           /* Sanity check current bucket/offset */
      if (currentbucket == self->firstbucket &&currentoffset < self->first)
        goto no_match;
      if (currentbucket == self->lastbucket && currentoffset > self->last)
        goto no_match;
    }

  PER_ALLOW_DEACTIVATION(currentbucket);

  if (currentbucket==self->currentbucket) Py_DECREF(currentbucket);
  else ASSIGNB(self->currentbucket, currentbucket);

  self->pseudoindex=pseudoindex;
  self->currentoffset=currentoffset;
  
  return 0;

 no_match:

  IndexError(i);
  
  PER_ALLOW_DEACTIVATION(currentbucket);

 err:
  Py_XDECREF(currentbucket);
  return -1;
}


/*
** BTreeItems_item
**
** Arguments:	self	a BTreeItems structure
**		i	Which item to inspect
**
** Returns:	the BTreeItems_item_BTree of self->kind, i
**		(ie pulls the ith item out)
*/
static PyObject *
BTreeItems_item(BTreeItems *self, int i)
{
  PyObject *r, *k=0, *v=0;
  
  if (BTreeItems_seek(self, i) < 0) return NULL;

  PER_USE_OR_RETURN(self->currentbucket, NULL);

  switch(self->kind) {

  case 'v': 
    COPY_VALUE_TO_OBJECT(r, self->currentbucket->values[self->currentoffset]);
    break;

  case 'i':
    COPY_KEY_TO_OBJECT(k, self->currentbucket->keys[self->currentoffset]);
    UNLESS (k) return NULL;
      
    COPY_VALUE_TO_OBJECT(v, self->currentbucket->values[self->currentoffset]);
    UNLESS (v) return NULL;

    UNLESS (r=PyTuple_New(2)) goto err;

    PyTuple_SET_ITEM(r, 0, k);
    PyTuple_SET_ITEM(r, 1, v);
    break;

  default:
    COPY_KEY_TO_OBJECT(r, self->currentbucket->keys[self->currentoffset]);
    break;
  }

  PER_ALLOW_DEACTIVATION(self->currentbucket);
  return r;

 err:
  Py_DECREF(k);
  Py_XDECREF(v);
  PER_ALLOW_DEACTIVATION(self->currentbucket);
  return NULL;
}

/*
** BTreeItems_slice
**
** Creates a new BTreeItems structure representing the slice
** between the low and high range
**
** Arguments:	self	The old BTreeItems structure
**		ilow	The start index
**		ihigh	The end index
**
** Returns:	BTreeItems item 
*/
static PyObject *
BTreeItems_slice(BTreeItems *self, int ilow, int ihigh)
{
  Bucket *lowbucket;
  Bucket *highbucket;
  int lowoffset;
  int highoffset;
  

  if (BTreeItems_seek(self, ilow) < 0) return NULL;
  
  lowbucket = self->currentbucket;
  lowoffset = self->currentoffset;
  
  if (BTreeItems_seek(self, ihigh) < 0) return NULL;
  
  highbucket = self->currentbucket;
  highoffset = self->currentoffset;
  
  return newBTreeItems(self->kind, 
                       lowbucket, lowoffset, highbucket, highoffset);
}

static PySequenceMethods BTreeItems_as_sequence = {
  (inquiry) BTreeItems_length,
  (binaryfunc)0,
  (intargfunc)0,
  (intargfunc) BTreeItems_item,
  (intintargfunc) BTreeItems_slice,
};

/* Number Method items (just for nb_nonzero!) */

static int
BTreeItems_nonzero(BTreeItems *self)
{
  return BTreeItems_length_or_nonzero(self, 1);
}

static PyNumberMethods BTreeItems_as_number_for_nonzero = {
  0,0,0,0,0,0,0,0,0,0,
   (inquiry)BTreeItems_nonzero};

static PyTypeObject BTreeItemsType = {
  PyObject_HEAD_INIT(NULL)
  0,					/*ob_size*/
  PREFIX "BTreeItems",	        /*tp_name*/
  sizeof(BTreeItems),		        /*tp_basicsize*/
  0,					/*tp_itemsize*/
  /* methods */
  (destructor) BTreeItems_dealloc,	/*tp_dealloc*/
  (printfunc)0,				/*tp_print*/
  (getattrfunc)0,			/*obsolete tp_getattr*/
  (setattrfunc)0,			/*obsolete tp_setattr*/
  (cmpfunc)0,				/*tp_compare*/
  (reprfunc)0,				/*tp_repr*/
  &BTreeItems_as_number_for_nonzero,	/*tp_as_number*/
  &BTreeItems_as_sequence,		/*tp_as_sequence*/
  0,					/*tp_as_mapping*/
  (hashfunc)0,				/*tp_hash*/
  (ternaryfunc)0,			/*tp_call*/
  (reprfunc)0,				/*tp_str*/
  0,					/*tp_getattro*/
  0,					/*tp_setattro*/
  
  /* Space for future expansion */
  0L,0L,
  "Sequence type used to iterate over BTree items." /* Documentation string */
};

static PyObject *
newBTreeItems(char kind, 
              Bucket *lowbucket, int lowoffset,
              Bucket *highbucket, int highoffset)
{
  BTreeItems *self;
	
  UNLESS (self = PyObject_NEW(BTreeItems, &BTreeItemsType)) return NULL;
  self->kind=kind;

  self->first=lowoffset;
  self->last=highoffset;

  if (! lowbucket || (lowbucket==highbucket && lowoffset > highoffset))
    {
      self->firstbucket   = 0;
      self->lastbucket    = 0;
      self->currentbucket = 0;
    }
  else
    {
      Py_INCREF(lowbucket);
      self->firstbucket = lowbucket;
      Py_XINCREF(highbucket);
      self->lastbucket = highbucket;
      Py_XINCREF(lowbucket);
      self->currentbucket = lowbucket;
    }

  self->currentoffset = lowoffset;
  self->pseudoindex = 0;

  return OBJECT(self);
}

static int 
nextBTreeItems(SetIteration *i)
{
  if (i->position >= 0)
    {
      if (i->position)
        {
          DECREF_KEY(i->key);
          DECREF_VALUE(i->value);
        }
      
      if (BTreeItems_seek(ITEMS(i->set), i->position) >= 0)
        {
          Bucket *currentbucket;

          currentbucket = BUCKET(ITEMS(i->set)->currentbucket);

          UNLESS(PER_USE(currentbucket)) return -1;

          COPY_KEY(i->key, currentbucket->keys[ITEMS(i->set)->currentoffset]);
          INCREF_KEY(i->key);

          COPY_VALUE(i->value, 
                     currentbucket->values[ITEMS(i->set)->currentoffset]);
          COPY_VALUE(i->value, 
                   BUCKET(ITEMS(i->set)->currentbucket)
                   ->values[ITEMS(i->set)->currentoffset]);
          INCREF_VALUE(i->value);

          i->position ++;

          PER_ALLOW_DEACTIVATION(currentbucket);
        }
      else
        {
          i->position = -1;
          PyErr_Clear();
        }
    }
  return 0;
}

static int 
nextTreeSetItems(SetIteration *i)
{
  if (i->position >= 0)
    {
      if (i->position)
        {
          DECREF_KEY(i->key);
        }
      
      if (BTreeItems_seek(ITEMS(i->set), i->position) >= 0)
        {
          Bucket *currentbucket;

          currentbucket = BUCKET(ITEMS(i->set)->currentbucket);

          UNLESS(PER_USE(currentbucket)) return -1;

          COPY_KEY(i->key, currentbucket->keys[ITEMS(i->set)->currentoffset]);
          INCREF_KEY(i->key);

          i->position ++;

          PER_ALLOW_DEACTIVATION(currentbucket);
        }
      else
        {
          i->position = -1;
          PyErr_Clear();
        }
    }
  return 0;
}

--- Added File BTreeModuleTemplate.c in package Zope2 ---
/*****************************************************************************
  
  Zope Public License (ZPL) Version 1.0
  -------------------------------------
  
  Copyright (c) Digital Creations.  All rights reserved.
  
  This license has been certified as Open Source(tm).
  
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met:
  
  1. Redistributions in source code must retain the above copyright
     notice, this list of conditions, and the following disclaimer.
  
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions, and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
  
  3. Digital Creations requests that attribution be given to Zope
     in any manner possible. Zope includes a "Powered by Zope"
     button that is installed by default. While it is not a license
     violation to remove this button, it is requested that the
     attribution remain. A significant investment has been put
     into Zope, and this effort will continue if the Zope community
     continues to grow. This is one way to assure that growth.
  
  4. All advertising materials and documentation mentioning
     features derived from or use of this software must display
     the following acknowledgement:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     In the event that the product being advertised includes an
     intact Zope distribution (with copyright and license included)
     then this clause is waived.
  
  5. Names associated with Zope or Digital Creations must not be used to
     endorse or promote products derived from this software without
     prior written permission from Digital Creations.
  
  6. Modified redistributions of any form whatsoever must retain
     the following acknowledgment:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     Intact (re-)distributions of any official Zope release do not
     require an external acknowledgement.
  
  7. Modifications are encouraged but must be packaged separately as
     patches to official Zope releases.  Distributions that do not
     clearly separate the patches from the original work must be clearly
     labeled as unofficial distributions.  Modifications which do not
     carry the name Zope may be packaged in any form, as long as they
     conform to all of the clauses above.
  
  
  Disclaimer
  
    THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
    EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
  
  
  This software consists of contributions made by Digital Creations and
  many individuals on behalf of Digital Creations.  Specific
  attributions are listed in the accompanying credits file.
  
 ****************************************************************************/

static char BTree_module_documentation[] = 
""
"\n$Id: BTreeModuleTemplate.c,v 1.4.6.1 2001/03/15 13:10:28 jim Exp $"
;

#ifdef PERSISTENT
#include "cPersistence.h"

/***************************************************************
   The following are macros that ought to be in cPersistence.h */
#ifndef PER_USE 

#define PER_USE(O) \
(((O)->state != cPersistent_GHOST_STATE \
  || (cPersistenceCAPI->setstate((PyObject*)(O)) >= 0)) \
 ? (((O)->state==cPersistent_UPTODATE_STATE) \
    ? ((O)->state=cPersistent_STICKY_STATE) : 1) : 0)

#endif
/***************************************************************/
#else
#include "ExtensionClass.h"
#define PER_USE_OR_RETURN(self, NULL)
#define PER_ALLOW_DEACTIVATION(self)
#define PER_PREVENT_DEACTIVATION(self)
#define PER_DEL(self)
#define PER_USE(O) 1
#define PER_CHANGED(O) 0
#endif

static PyObject *sort_str, *reverse_str, *items_str, *__setstate___str;

static void PyVar_Assign(PyObject **v, PyObject *e) { Py_XDECREF(*v); *v=e;}
#define ASSIGN(V,E) PyVar_Assign(&(V),(E))
#define ASSIGNC(V,E) (Py_INCREF((E)), PyVar_Assign(&(V),(E)))
#define UNLESS(E) if (!(E))
#define UNLESS_ASSIGN(V,E) ASSIGN(V,E); UNLESS(V)
#define LIST(O) ((PyListObject*)(O))
#define OBJECT(O) ((PyObject*)(O))

#define MIN_BUCKET_ALLOC 16
#define MAX_BTREE_SIZE(B) DEFAULT_MAX_BTREE_SIZE
#define MAX_BUCKET_SIZE(B) DEFAULT_MAX_BUCKET_SIZE

#define SameType_Check(O1, O2) ((O1)->ob_type==(O2)->ob_type)

#define ASSERT(C, S, R) if (! (C)) { \
  PyErr_SetString(PyExc_AssertionError, (S)); return (R); }

typedef struct BTreeItemStruct {
  KEY_TYPE key;
  PyObject *value;
} BTreeItem;

typedef struct Bucket_s {
#ifdef PERSISTENT
  cPersistent_HEAD
#else
  PyObject_HEAD
#endif
  int size, len;
  struct Bucket_s *next;
  KEY_TYPE *keys;
  VALUE_TYPE *values;
} Bucket;

#define BUCKET(O) ((Bucket*)(O))

static void PyVar_AssignB(Bucket **v, Bucket *e) { Py_XDECREF(*v); *v=e;}
#define ASSIGNB(V,E) PyVar_AssignB(&(V),(E))
#define ASSIGNBC(V,E) (Py_INCREF((E)), PyVar_AssignB(&(V),(E)))

typedef struct {
#ifdef PERSISTENT
  cPersistent_HEAD
#else
  PyObject_HEAD
#endif
  int size, len;
  Bucket *firstbucket;
  BTreeItem *data;
} BTree;

staticforward PyExtensionClass BTreeType;


#define BTREE(O) ((BTree*)(O))

typedef struct SetIteration_s 
{
  PyObject *set;
  int position;
  int hasValue;
  KEY_TYPE key;
  VALUE_TYPE value;
  int (*next)(struct SetIteration_s*);
} SetIteration;

static PyObject *
IndexError(int i)
{                              
  PyObject *v;

  v=PyInt_FromLong(i);
  UNLESS (v) {
    v=Py_None;
    Py_INCREF(v);
  }
  PyErr_SetObject(PyExc_IndexError, v);
  Py_DECREF(v);
  return NULL;
}

static Bucket *
PreviousBucket(Bucket *current, Bucket *first, int i)
{
  if (! first) return NULL;
  if (first==current)
    {
      IndexError(i);
      return NULL;
    }

  Py_INCREF(first);
  while (1)
    {
      PER_USE_OR_RETURN(first,NULL);
      if (first->next==current) 
        {
          PER_ALLOW_DEACTIVATION(first);
          return first;
        }
      else if (first->next)
        {
          Bucket *next = first->next;
          Py_INCREF(next);
          PER_ALLOW_DEACTIVATION(first);
          Py_DECREF(first);
          first=next;
        }
      else
        {
          PER_ALLOW_DEACTIVATION(first);
          Py_DECREF(first);
          IndexError(i);
          return NULL;
        }
    }
}

static int 
firstBucketOffset(Bucket **bucket, int *offset)
{
  Bucket *b;

  *offset = (*bucket)->len - 1;
  while ((*bucket)->len < 1)
    {
      b=(*bucket)->next;
      if (b==NULL) return 0;
      Py_INCREF(b);
      PER_ALLOW_DEACTIVATION((*bucket));
      ASSIGNB((*bucket), b);
      UNLESS (PER_USE(*bucket)) return -1;
      *offset = 0;
    }
}

static int 
lastBucketOffset(Bucket **bucket, int *offset, Bucket *firstbucket, int i)
{
  Bucket *b;

  *offset = (*bucket)->len - 1;
  while ((*bucket)->len < 1)
    {
      b=PreviousBucket((*bucket), firstbucket, i);
      if (b==NULL) return 0;
      PER_ALLOW_DEACTIVATION((*bucket));
      ASSIGNB((*bucket), b);
      UNLESS (PER_USE(*bucket)) return -1;
      *offset = (*bucket)->len - 1;
    }
}

static void *
PyMalloc(size_t sz)
{
  void *r;

  ASSERT(sz > 0, "non-positive size malloc", NULL);

  if (r=malloc(sz)) return r;

  PyErr_NoMemory();
  return NULL;
}

static void *
PyRealloc(void *p, size_t sz)
{
  void *r;

  ASSERT(sz > 0, "non-positive size realloc", NULL);

  if (p) r=realloc(p,sz);
  else r=malloc(sz);

  UNLESS (r) PyErr_NoMemory();

  return r;
}

#include "BTreeItemsTemplate.c"
#include "BucketTemplate.c"
#include "SetTemplate.c"
#include "BTreeTemplate.c"
#include "TreeSetTemplate.c"
#include "SetOpTemplate.c"
#include "MergeTemplate.c"

static struct PyMethodDef module_methods[] = {
  {"difference", (PyCFunction) difference_m,	METH_VARARGS,
   "difference(o1, o2) -- "
   "compute the difference between o1 and o2"
  },
  {"union", (PyCFunction) union_m,	METH_VARARGS,
   "union(o1, o2) -- compute the union of o1 and o2\n"
  },
  {"intersection", (PyCFunction) intersection_m,	METH_VARARGS,
   "intersection(o1, o2) -- "
   "compute the intersection of o1 and o2"
  },
#ifdef MERGE
  {"weightedUnion", (PyCFunction) wunion_m,	METH_VARARGS,
   "weightedUnion(o1, o2 [, w1, w2]) -- compute the union of o1 and o2\n"
   "\nw1 and w2 are weights."
  },
  {"weightedIntersection", (PyCFunction) wintersection_m,	METH_VARARGS,
   "weightedIntersection(o1, o2 [, w1, w2]) -- "
   "compute the intersection of o1 and o2\n"
   "\nw1 and w2 are weights."
  },
#endif
  {NULL,		NULL}		/* sentinel */
};

void 
INITMODULE ()
{
  PyObject *m, *d;

  UNLESS (sort_str=PyString_FromString("sort")) return;
  UNLESS (reverse_str=PyString_FromString("reverse")) return;
  UNLESS (items_str=PyString_FromString("items")) return;
  UNLESS (__setstate___str=PyString_FromString("__setstate__")) return;

  UNLESS (PyExtensionClassCAPI=PyCObject_Import("ExtensionClass","CAPI"))
      return;

#ifdef PERSISTENT
  if (cPersistenceCAPI=PyCObject_Import("cPersistence","CAPI"))
    {
	BucketType.methods.link=cPersistenceCAPI->methods;
	BucketType.tp_getattro=cPersistenceCAPI->getattro;
	BucketType.tp_setattro=cPersistenceCAPI->setattro;

	SetType.methods.link=cPersistenceCAPI->methods;
	SetType.tp_getattro=cPersistenceCAPI->getattro;
	SetType.tp_setattro=cPersistenceCAPI->setattro;

	BTreeType.methods.link=cPersistenceCAPI->methods;
	BTreeType.tp_getattro=cPersistenceCAPI->getattro;
	BTreeType.tp_setattro=cPersistenceCAPI->setattro;

	TreeSetType.methods.link=cPersistenceCAPI->methods;
	TreeSetType.tp_getattro=cPersistenceCAPI->getattro;
	TreeSetType.tp_setattro=cPersistenceCAPI->setattro;
    }
  else return;
#else
  BTreeType.tp_getattro=PyExtensionClassCAPI->getattro;
  BucketType.tp_getattro=PyExtensionClassCAPI->getattro;
  SetType.tp_getattro=PyExtensionClassCAPI->getattro;
  TreeSetType.tp_getattro=PyExtensionClassCAPI->getattro;
#endif

  BTreeItemsType.ob_type=&PyType_Type;

#ifdef INTSET_H
  UNLESS(d = PyImport_ImportModule("intSet")) return;
  UNLESS(intSetType = PyObject_GetAttrString (d, "intSet")) return;
  Py_DECREF (d); 
#endif

  /* Create the module and add the functions */
  m = Py_InitModule4(PREFIX "BTree", module_methods,
		     BTree_module_documentation,
		     (PyObject*)NULL,PYTHON_API_VERSION);

  /* Add some symbolic constants to the module */
  d = PyModule_GetDict(m);

  PyDict_SetItemString(d, "__version__",
		       PyString_FromString("$Revision: 1.4.6.1 $"));

  PyExtensionClass_Export(d,PREFIX "Bucket", BucketType);
  PyExtensionClass_Export(d,PREFIX "BTree", BTreeType);
  PyExtensionClass_Export(d,PREFIX "Set", SetType);
  PyExtensionClass_Export(d,PREFIX "TreeSet", TreeSetType);
 
  /* Check for errors */
  if (PyErr_Occurred())
    Py_FatalError("can't initialize module " PREFIX "BTree");
}

--- Added File BTreeTemplate.c in package Zope2 ---
/*****************************************************************************
  
  Zope Public License (ZPL) Version 1.0
  -------------------------------------
  
  Copyright (c) Digital Creations.  All rights reserved.
  
  This license has been certified as Open Source(tm).
  
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met:
  
  1. Redistributions in source code must retain the above copyright
     notice, this list of conditions, and the following disclaimer.
  
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions, and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
  
  3. Digital Creations requests that attribution be given to Zope
     in any manner possible. Zope includes a "Powered by Zope"
     button that is installed by default. While it is not a license
     violation to remove this button, it is requested that the
     attribution remain. A significant investment has been put
     into Zope, and this effort will continue if the Zope community
     continues to grow. This is one way to assure that growth.
  
  4. All advertising materials and documentation mentioning
     features derived from or use of this software must display
     the following acknowledgement:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     In the event that the product being advertised includes an
     intact Zope distribution (with copyright and license included)
     then this clause is waived.
  
  5. Names associated with Zope or Digital Creations must not be used to
     endorse or promote products derived from this software without
     prior written permission from Digital Creations.
  
  6. Modified redistributions of any form whatsoever must retain
     the following acknowledgment:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     Intact (re-)distributions of any official Zope release do not
     require an external acknowledgement.
  
  7. Modifications are encouraged but must be packaged separately as
     patches to official Zope releases.  Distributions that do not
     clearly separate the patches from the original work must be clearly
     labeled as unofficial distributions.  Modifications which do not
     carry the name Zope may be packaged in any form, as long as they
     conform to all of the clauses above.
  
  
  Disclaimer
  
    THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
    EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
  
  
  This software consists of contributions made by Digital Creations and
  many individuals on behalf of Digital Creations.  Specific
  attributions are listed in the accompanying credits file.
  
 ****************************************************************************/

/*
** _BTree_get
**
*/
static PyObject *
_BTree_get(BTree *self, PyObject *keyarg, int has_key)
{
  int min, max, i, cmp, copied=1;
  PyObject *r;
  KEY_TYPE key;
  
  COPY_KEY_FROM_ARG(key, keyarg, &copied);
  UNLESS (copied) return NULL;

  PER_USE_OR_RETURN(self, NULL);

  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].value)) 
        r=_BTree_get( BTREE(self->data[min].value), keyarg, 
                      has_key ? has_key + 1: 0);
      else
        r=_bucket_get(BUCKET(self->data[min].value), keyarg, 
                      has_key ? has_key + 1: 0);
    }
  else
    {  /* No data */
      UNLESS (has_key) 
        {
          PyErr_SetObject(PyExc_KeyError, keyarg);
          r=NULL;
        }
      else
        r=PyInt_FromLong(0);
    }

  PER_ALLOW_DEACTIVATION(self);
  return r;
}    

static PyObject *
BTree_get(BTree *self, PyObject *key)
{
  return _BTree_get(self, key, 0);
}

/*
  Copy data from the current BTree to the newly created BTree, next. 
  Reset length to reflect the fact that we've given up some data. 
*/
static int
BTree_split(BTree *self, int index, BTree *next)
{
  int next_size;
  ASSERT(self->len > 1, "split of empty tree", -1);

  if (index < 0 || index >= self->len) index=self->len/2;
  
  next_size=self->len-index;
  ASSERT(next_size > 0, "split creates empty tree", -1);
  
  UNLESS (next->data=PyMalloc(sizeof(BTreeItem)*next_size)) return -1;
  memcpy(next->data, self->data+index, sizeof(BTreeItem)*next_size);
  next->size=next->len=next_size;
  
  self->len = index;

  if (SameType_Check(self, next->data->value)) 
    {
      PER_USE_OR_RETURN(BTREE(next->data->value), -1);
      next->firstbucket = BTREE(next->data->value)->firstbucket;
      Py_XINCREF(next->firstbucket);
      PER_ALLOW_DEACTIVATION(BTREE(next->data->value));
    }
  else
    {
      next->firstbucket = BUCKET(next->data->value);
      Py_XINCREF(next->firstbucket);
    }
  
  return 0;
}

/* Split out data among two newly created BTrees, which become
   out children. 
*/
static int
BTree_clone(BTree *self)
{
  /* We've grown really big without anybody splitting us.
     We should split ourselves.
   */
  BTree *n1=0, *n2=0;
  BTreeItem *d=0;
  
  /* Create two BTrees to hold ourselves after split */
  UNLESS (n1=BTREE(PyObject_CallObject(OBJECT(self->ob_type), NULL))) 
    return -1;
  UNLESS (n2=BTREE(PyObject_CallObject(OBJECT(self->ob_type), NULL))) 
    goto err;

  /* Create a new data buffer to hold two BTrees */
  UNLESS (d=PyMalloc(sizeof(BTreeItem)*2)) goto err;

  /* Split ourself */
  if (BTree_split(self,-1,n2) < 0) goto err;
  
  /* Move our data to new BTree */
  n1->size=self->size;
  n1->len=self->len;
  n1->data=self->data;
  n1->firstbucket = self->firstbucket;
  Py_XINCREF(n1->firstbucket);
  
  /* Initialize our data to hold split data */
  self->data=d;
  self->len=2;
  self->size=2;
  self->data->value=OBJECT(n1);
  COPY_KEY(self->data[1].key, n2->data->key);

  /* We take the unused reference from n2, so there's no reason to INCREF! */
  /* INCREF_KEY(self->data[1].key); */

  self->data[1].value=OBJECT(n2);

  return 0;

err:
  Py_XDECREF(n1);
  Py_XDECREF(n2);
  if (d) free(d);
  return -1;
}

/*
** BTree_grow
**
** Grow a BTree 
**
** Arguments:	self	The BTree
**		index	the index item to insert at
**
** Returns:	 0	on success
**		-1	on failure
*/
static int 
BTree_grow(BTree *self, int index, int noval)
{
  int i;
  PyObject *v, *e=0;
  BTreeItem *d;

  if (self->len == self->size)
    {
      if (self->size)
        {
          UNLESS (d=PyRealloc(self->data, sizeof(BTreeItem)*self->size*2))
            return -1;
          self->data=d;
          self->size *= 2;
        }
      else
        {
          UNLESS (d=PyMalloc(sizeof(BTreeItem)*2))
            return -1;
          self->data=d;
          self->size = 2;
        }
    }
     
  d=self->data+index;
  if (self->len)
    {
      v=d->value;
      /* Create a new object of the same type as the target value */
      UNLESS (e=PyObject_CallObject(OBJECT(v->ob_type), NULL)) return -1;

      PER_USE_OR_RETURN(BUCKET(v), -1);


      /* Now split between the original (v) and the new (e) at the midpoint*/
      if (SameType_Check(self, v))
        {
          i=BTree_split(  BTREE(v), -1,   BTREE(e));
        }
      else
        {
          i=bucket_split(BUCKET(v), -1, BUCKET(e));
        }

      PER_ALLOW_DEACTIVATION(BUCKET(v));

      if (i < 0)
        {
          Py_DECREF(e);
          return -1;
        }

      index++;
      d++;
      if (self->len > index)	/* Shift up the old values one array slot */
        memmove(d+1, d, sizeof(BTreeItem)*(self->len-index));

      if (SameType_Check(self, v))
        {
          COPY_KEY(d->key, BTREE(e)->data->key);

          /* We take the unused reference from e, so there's no
             reason to INCREF! 
          */
          /* INCREF_KEY(self->data[1].key); */
        }
      else
        {
          COPY_KEY(d->key, BUCKET(e)->keys[0]);
          INCREF_KEY(d->key);
        }
      d->value=e;

      self->len++;

      if (self->len >= MAX_BTREE_SIZE(self) * 2) return BTree_clone(self);
    }
  else
    {
      if (noval)
        {
          UNLESS (d->value=PyObject_CallObject(OBJECT(&SetType), NULL))
            return -1;
        }
      else
        {
          UNLESS (d->value=PyObject_CallObject(OBJECT(&BucketType), NULL))
            return -1;
        }
      self->len=1;
      Py_INCREF(d->value);
      self->firstbucket = BUCKET(d->value);
    }     
  
  return 0;
}

static Bucket *
BTree_lastBucket(BTree *self) 
{
  PyObject *o;

  UNLESS (self->data && self->len) 
    {
      IndexError(-1); /*XXX*/
      return NULL;
    }

  o=self->data[self->len - 1].value;
  Py_INCREF(o);

  UNLESS (SameType_Check(self, o)) return BUCKET(o);

  self=BTREE(o);

  PER_USE_OR_RETURN(self, NULL);
  ASSIGN(o, OBJECT(BTree_lastBucket(self)));
  PER_ALLOW_DEACTIVATION(self);
  
  return BUCKET(o);
}

static int
BTree_deleteNextBucket(BTree *self)
{
  Bucket *b;

  PER_USE_OR_RETURN(self, -1);

  UNLESS (b=BTree_lastBucket(self)) goto err;
  if (Bucket_deleteNextBucket(b) < 0) goto err;
  
  return 0;

 err:
  PER_ALLOW_DEACTIVATION(self);
  return -1;
}

/*
  Set (value != 0) or delete (value=0) a tree item.  

  If unique is non-zero, then only change if the key is
  new.

  If noval is non-zero, then don't set a value (the tree
  is a set).

  Return 1 on successful change, 0 is no change, -1 on error.
*/
static int
_BTree_set(BTree *self, PyObject *keyarg, PyObject *value, 
           int unique, int noval)
{
  int i, min, max, cmp, grew, copied=1, changed=0, bchanged=0;
  BTreeItem *d;
  KEY_TYPE key;

  COPY_KEY_FROM_ARG(key, keyarg, &copied);
  UNLESS (copied) return -1;

  PER_USE_OR_RETURN(self, -1);

  UNLESS (self->len)
    {
      if (value) 
        {
          if (BTree_grow(self, 0, noval) < 0) return -1;
        }
      else 
        {
          PyErr_SetObject(PyExc_KeyError, keyarg);
          return -1;
        }
    }

  /* 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;
  if (SameType_Check(self, d->value))
    grew= _BTree_set( BTREE(d->value), keyarg, value, unique, noval);
  else
    grew=_bucket_set(BUCKET(d->value), keyarg, value, unique, noval, 
                     &bchanged);
  if (grew < 0) goto err;

  if (grew)
    {
      bchanged=1;               /* A bucket changed size */
      if (value)			/* got bigger */
	{
          if (SameType_Check(self, d->value))
            {
              if (BTREE(d->value)->len > MAX_BTREE_SIZE(d->value))
                {
                  if (BTree_grow(self, min, noval) < 0) goto err;
                  changed=1;
                }
            }          
          else
            {
              if (BUCKET(d->value)->len > MAX_BUCKET_SIZE(d->value))
                {
                  if (BTree_grow(self, min, noval) < 0) goto err;
                  changed=1;
                }
            }          
	}
      else			/* got smaller */
	{
          if (min && grew > 1)
            { /* Somebody below us deleted their first bucket and */
              /* and an intermediate tree couldn't handle it.     */
              if (BTree_deleteNextBucket(BTREE(d[-1].value)) < 0)
                goto err;
              grew=1; /* Reset flag, since we handled it */
            }
          
          if (BUCKET(d->value)->len == 0)
            {                   /* Got empty */
              
              if (! SameType_Check(self, d->value))
                {  /* We are about to delete a bucket. */ 
                  if (min)
                    {  /*If it's not our first bucket, we can tell the
                         previous bucket to adjust it's reference to
                         it. */
                      if (Bucket_deleteNextBucket(BUCKET(d[-1].value)) < 0)
                        goto err;
                    }
                  else
                    { /* If it's the first bucket, we can't adjust the
                         reference to it ourselves, so we'll just
                         increment the grew flag to indicate to a
                         parent node that it's last bucket should
                         adjust its reference. If there is no parent,
                         then there's nothing to do. */
                      grew++;
                    }
                }
              self->len--;
              Py_DECREF(d->value);
              if (min) DECREF_KEY(d->key);
              if (min < self->len)
                memmove(d, d+1, (self->len-min)*sizeof(BTreeItem));

              if (! min) 
                if (self->len)
                  { /* We just deleted our first child, so we need to
                       adjust our first bucket. */
                    if (SameType_Check(self, self->data->value))
                      {
                        UNLESS (PER_USE(BTREE(self->data->value))) goto err;
                        ASSIGNB(self->firstbucket, 
                                BTREE(self->data->value)->firstbucket);
                        Py_XINCREF(self->firstbucket);
                        PER_ALLOW_DEACTIVATION(BTREE(self->data->value));
                      }
                    else
                      {
                        ASSIGNB(self->firstbucket, BUCKET(self->data->value));
                        Py_INCREF(self->firstbucket);
                      }
                    /* We can toss our first key now */
                    DECREF_KEY(self->data->key);
                  }
                else 
                  {
                    Py_XDECREF(self->firstbucket);
                    self->firstbucket = 0;
                  }
              changed=1;
            }
        }
    }

#ifdef PERSISTENT
  if (changed 
      || (bchanged                                     /* The bucket changed */
          && self->len == 1                            /* We have only one   */
          && ! SameType_Check(self, self->data->value) /* It's our child     */
          && BUCKET(self->data->value)->oid == NULL    /* It's in our record */
          )
      ) 
    if (PER_CHANGED(self) < 0) 
      goto err;
#endif
          
  
  PER_ALLOW_DEACTIVATION(self);
  return grew;

err:
  PER_ALLOW_DEACTIVATION(self);
  return -1;
}

/*
** BTree_setitem
**
** wrapper for _BTree_set
**
** Arguments:	self	The BTree
**		key	The key to insert
**		v	The value to insert
**
** Returns	-1	on failure
**		 0	on success
*/
static int
BTree_setitem(BTree *self, PyObject *key, PyObject *v)
{
  if (_BTree_set(self, key, v, 0, 0) < 0) return -1;
  return 0;
}

/*
** _BTree_clear
**
** Clears out all of the values in the BTree
**
** Arguments:	self	The BTree
**
** Returns:	 0	on success
**		-1	on failure
*/  
static int
_BTree_clear(BTree *self)
{
  int i, l;

  /* The order in which we dealocate, from "top to bottom" is critical
     to prevent memory memory errors when the deallocation stack
     becomes huge when dealocating use linked lists of buckets.
  */

  if (self->firstbucket)
    {
      ASSERT(self->firstbucket->ob_refcnt > 1, 
             "Invalid firstbucket pointer", -1);
      Py_DECREF(self->firstbucket);
      self->firstbucket=NULL;
    }

  for (l=self->len, i=0; i < l; i++)
    {
      if (i) DECREF_KEY(self->data[i].key);
      Py_DECREF(self->data[i].value);
    }
  self->len=0;

  if (self->data)
    {
      free(self->data);
      self->data=0;
      self->size=0;
    }
  
  return 0;
}

#ifdef PERSISTENT
static PyObject *
BTree__p_deactivate(BTree *self, PyObject *args)
{
  if (self->state==cPersistent_UPTODATE_STATE && self->jar)
    {
      if (_BTree_clear(self) < 0) return NULL;
      self->state=cPersistent_GHOST_STATE;
    }

  Py_INCREF(Py_None);
  return Py_None;
}
#endif

static PyObject *
BTree_clear(BTree *self, PyObject *args)
{
  PER_USE_OR_RETURN(self, NULL);

  if (self->len)
    {
      if (_BTree_clear(self) < 0) goto err;
      if (PER_CHANGED(self) < 0) goto err;
    }

  PER_ALLOW_DEACTIVATION(self);

  Py_INCREF(Py_None); 
  return Py_None;

err:
  PER_ALLOW_DEACTIVATION(self);
  return NULL;
}

static PyObject *
BTree_getstate(BTree *self, PyObject *args)
{
  PyObject *r=0, *o;
  int i, l;

  PER_USE_OR_RETURN(self, NULL);

  if (self->len)
    {
      UNLESS (r=PyTuple_New(self->len*2-1)) goto err;

      if (self->len == 1 
          && self->data->value->ob_type != self->ob_type
#ifdef PERSISTENT
          && BUCKET(self->data->value)->oid == NULL
#endif
          )
        {
          /* We have just one bucket. Save it's data directly. */
          UNLESS(o=bucket_getstate(BUCKET(self->data->value), NULL)) goto err;
          PyTuple_SET_ITEM(r,0,o);
          ASSIGN(r, Py_BuildValue("(O)", r));
        }
      else
        {
          for (i=0, l=0; i < self->len; i++)
            {
              if (i)
                {
                  COPY_KEY_TO_OBJECT(o, self->data[i].key);
                  PyTuple_SET_ITEM(r,l,o);
                  l++;
                }
              o=self->data[i].value;
              Py_INCREF(o);
              PyTuple_SET_ITEM(r,l,o);
              l++;
            }
          ASSIGN(r, Py_BuildValue("OO", r, self->firstbucket));
        }

    }
  else
    {
      r = Py_None;
      Py_INCREF(r);
    }  

  PER_ALLOW_DEACTIVATION(self);

  return r;

err:
  PER_ALLOW_DEACTIVATION(self);
  return NULL;
}

static int
_BTree_setstate(BTree *self, PyObject *state, int noval)
{
  PyObject *items, *o, *firstbucket=0;
  BTreeItem *d;
  int len, l, i, r, copied=1;

  if (_BTree_clear(self) < 0) return -1;

  if (state != Py_None)
    {

      if (!PyArg_ParseTuple(state,"O|O",&items, &firstbucket))
        return -1;

      if ((len=PyTuple_Size(items)) < 0) return -1;
      len=(len+1)/2;

      if (len > self->size)
        {
          UNLESS (d=PyRealloc(self->data, sizeof(BTreeItem)*len)) return -1;
          self->data=d;
          self->size=len;
        }

      for (i=0, d=self->data, l=0; i < len; i++, d++)
        {          
          if (i) 
            {
              COPY_KEY_FROM_ARG(d->key, PyTuple_GET_ITEM(items,l), &copied);
              l++;
              UNLESS (&copied) return -1;
              INCREF_KEY(d->key);
            }
          d->value=PyTuple_GET_ITEM(items,l);
          if (PyTuple_Check(d->value))
            {
              if (noval)
                {
                  UNLESS (d->value=PyObject_CallObject(OBJECT(&SetType), 
                                                       NULL))
                    return -1;
                  if (_set_setstate(BUCKET(d->value), 
                                    PyTuple_GET_ITEM(items,l))
                      < 0) return -1;
                }
              else
                {
                  UNLESS (d->value=PyObject_CallObject(OBJECT(&BucketType), 
                                                       NULL))
                    return -1;
                  if (_bucket_setstate(BUCKET(d->value), 
                                       PyTuple_GET_ITEM(items,l))
                      < 0) return -1;
                }
            }
          else
            {
              Py_INCREF(d->value);
            }
          l++;
        }

      if (len)
        {
          if (! firstbucket) firstbucket=self->data->value;

          UNLESS (ExtensionClassSubclassInstance_Check(
                    firstbucket, 
                    noval ? &SetType : &BucketType))
            {
              PyErr_SetString(PyExc_TypeError, 
                              "No firstbucket in non-empty BTree");
              return -1;
            }

          self->firstbucket = BUCKET(firstbucket);
          Py_INCREF(firstbucket);
        }

      self->len=len;
    }

  return 0;
}

static PyObject *
BTree_setstate(BTree *self, PyObject *args)
{
  int r;

  if (!PyArg_ParseTuple(args,"O",&args)) return NULL;
 
  PER_PREVENT_DEACTIVATION(self); 
  r=_BTree_setstate(self, args, 0);
  PER_ALLOW_DEACTIVATION(self);

  if (r < 0) return NULL;
  Py_INCREF(Py_None);
  return Py_None;
}

#ifdef PERSISTENT
static PyObject *
BTree__p_resolveConflict(BTree *self, PyObject *args)
{
  PyObject *s[3], *r;
  int i;

  UNLESS (PyArg_ParseTuple(args, "OOO", s, s+1, s+2)) return NULL;

                                /* for each state, detuplefy it twice */
  for (i=0; i < 3; i++)
    UNLESS (s[i]==Py_None || PyArg_ParseTuple(s[i], "O", s+i)) return NULL;
  for (i=0; i < 3; i++)
    UNLESS (s[i]==Py_None || PyArg_ParseTuple(s[i], "O", s+i)) return NULL;

  for (i=0; i < 3; i++)         /* Now make sure detupled thing is a tuple */
    UNLESS (s[i]==Py_None || PyTuple_Check(s[i]))
      return merge_error(-100, -100, -100, -100);

  if (ExtensionClassSubclassInstance_Check(self, &BTreeType))
      r = _bucket__p_resolveConflict(OBJECT(&BucketType), s);
  else
      r = _bucket__p_resolveConflict(OBJECT(&SetType), s);

  if (r) ASSIGN(r, Py_BuildValue("((O))", r));

  return r;
}
#endif

/*
 BTree_findRangeEnd -- Find one end, expressed as a bucket and
 position, for a range search. Used by BTree_rangeSearch below.

 If low, return bucket and index of the smallest item >= key,
 otherwise return bucket and index of the largest item <= key.

 Return: 0 -- Not found, 1 -- found, -1 -- error.
*/
static int
BTree_findRangeEnd(BTree *self, PyObject *keyarg, int low, 
                   Bucket **bucket, int *offset) {
  int min, max, i=0, cmp, copied=1;
  KEY_TYPE key;

  COPY_KEY_FROM_ARG(key, keyarg, &copied);
  UNLESS (copied) return -1;

  /* We don't need to: PER_USE_OR_RETURN(self, -1);
     because the caller does. */
  
  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;
    }

  if (SameType_Check(self, self->data[min].value)) 
    {
      self=BTREE(self->data[min].value);
      PER_USE_OR_RETURN(self, -1);
      i = BTree_findRangeEnd(self, keyarg, low, bucket, offset);
      PER_ALLOW_DEACTIVATION(self);
    }
  else
    {
      *bucket = BUCKET(self->data[min].value);
      if ((i=Bucket_findRangeEnd(*bucket, keyarg, low, offset)))
        Py_INCREF(*bucket);
    }

  return i;
}    

static PyObject *
BTree_maxminKey(BTree *self, PyObject *args, int min)
{
  PyObject *key=0;
  Bucket *bucket = NULL;
  int offset, rc;
  
  UNLESS (PyArg_ParseTuple(args, "|O", &key)) return NULL;
  
  PER_USE_OR_RETURN(self, NULL);

  UNLESS (self->data && self->len) goto empty;
  
  /* Find the  range */
  
  if (key) 
    {
      if ((rc = BTree_findRangeEnd(self, key, min, &bucket, &offset)) <= 0)
        {
          if (rc < 0) goto err;
          goto empty;
        } 
      PER_ALLOW_DEACTIVATION(self);
      PER_USE_OR_RETURN(bucket, NULL);
    }
  else if (min)
    {
      bucket = self->firstbucket;
      Py_INCREF(bucket);
      PER_ALLOW_DEACTIVATION(self);
      PER_USE_OR_RETURN(bucket, NULL);
      offset = 0;
      if (offset >= bucket->len)
        {
          switch (firstBucketOffset(&bucket, &offset))
            {
            case 0:  goto empty;
            case -1: goto err;
            }
        }
    }
  else
    {
      bucket = BTree_lastBucket(self);
      PER_ALLOW_DEACTIVATION(self);
      PER_USE_OR_RETURN(bucket, NULL);
      if (bucket->len)
        offset = bucket->len - 1; 
      else
        {
          switch (lastBucketOffset(&bucket, &offset, self->firstbucket, -1))
            {
            case 0:  goto empty;
            case -1: goto err;
            }
        }
    }
  
  COPY_KEY_TO_OBJECT(key, bucket->keys[offset]);
  PER_ALLOW_DEACTIVATION(bucket);
  Py_DECREF(bucket);

  return key;
  
 empty:
  PyErr_SetString(PyExc_ValueError, "empty tree");

 err:
  PER_ALLOW_DEACTIVATION(self);
  if (bucket)  
    {
      PER_ALLOW_DEACTIVATION(bucket);
      Py_DECREF(bucket);
    }
  return NULL;
}

static PyObject *
BTree_minKey(BTree *self, PyObject *args)
{
  return BTree_maxminKey(self, args, 1);
}

static PyObject *
BTree_maxKey(BTree *self, PyObject *args)
{
  return BTree_maxminKey(self, args, 0);
}

/*
** BTree_rangeSearch
**
** Generates a BTreeItems object based on the two indexes passed in,
** being the range between them.
**
*/
static PyObject *
BTree_rangeSearch(BTree *self, PyObject *args, char type)
{
  PyObject *f=0, *l=0;
  int rc;
  Bucket *lowbucket = NULL;
  Bucket *highbucket = NULL;
  int lowoffset;
  int highoffset;
  
  UNLESS (! args || PyArg_ParseTuple(args,"|OO",&f, &l)) return NULL;
  
  PER_USE_OR_RETURN(self, NULL);

  UNLESS (self->data && self->len) goto empty;

  /* Find the low range */
  
  if (f && f != Py_None) 
    {
      if ((rc = BTree_findRangeEnd(self, f, 1, &lowbucket, &lowoffset)) <= 0)
        {
          if (rc < 0) goto err;
          goto empty;
        }
    } 
  else 
    {
      lowbucket = self->firstbucket;
      Py_INCREF(lowbucket);
      lowoffset = 0;
    }
  
  /* Find the high range */
  
  if (l && l != Py_None) 
    {
      if ((rc = BTree_findRangeEnd(self, l, 0, &highbucket, &highoffset)) <= 0)
        {
          Py_DECREF(lowbucket);
          if (rc < 0) goto err;
          goto empty;
        } 
    }
  else 
    {
      highbucket = BTree_lastBucket(self);
      UNLESS (PER_USE(highbucket)) goto err;
      highoffset = highbucket->len - 1; 
      PER_ALLOW_DEACTIVATION(highbucket);      
    }
  
  PER_ALLOW_DEACTIVATION(self);
  
  f=newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
  Py_DECREF(lowbucket);
  Py_DECREF(highbucket);
  return f;
  
 err:
  PER_ALLOW_DEACTIVATION(self);
  return NULL;

 empty:
  PER_ALLOW_DEACTIVATION(self);
  return newBTreeItems(type, 0, 0, 0, 0);
}

/*
** BTree_keys
*/
static PyObject *
BTree_keys(BTree *self, PyObject *args)
{
  return BTree_rangeSearch(self,args, 'k');
}

/*
** BTree_values
*/
static PyObject *
BTree_values(BTree *self, PyObject *args)
{
  return BTree_rangeSearch(self,args,'v');
}

/*
** BTree_items
*/
static PyObject *
BTree_items(BTree *self, PyObject *args)
{
  return BTree_rangeSearch(self,args,'i');
}

static PyObject *
BTree_byValue(BTree *self, PyObject *args)
{
  PyObject *r=0, *o=0, *item=0, *omin;
  VALUE_TYPE min;
  VALUE_TYPE v;
  int i, l, copied=1;
  SetIteration it={0,0};

  PER_USE_OR_RETURN(self, NULL);

  UNLESS (PyArg_ParseTuple(args, "O", &omin)) return NULL;
  COPY_VALUE_FROM_ARG(min, omin, &copied);
  UNLESS(copied) return NULL;
    
  UNLESS (r=PyList_New(0)) goto err;

  it.set=BTree_rangeSearch(self, NULL, 'i');
  UNLESS(it.set) goto err;

  if (nextBTreeItems(&it) < 0) goto err;

  while (it.position >= 0)
    {
      if (TEST_VALUE(it.value, min) >= 0)
        {      
          UNLESS (item = PyTuple_New(2)) goto err;

          COPY_KEY_TO_OBJECT(o, it.key);
          UNLESS (o) goto err;
          PyTuple_SET_ITEM(item, 1, o);

          COPY_VALUE(v, it.value);
          NORMALIZE_VALUE(v, min);
          COPY_VALUE_TO_OBJECT(o, v);
          DECREF_VALUE(v);
          UNLESS (o) goto err;
          PyTuple_SET_ITEM(item, 0, o);
      
          if (PyList_Append(r, item) < 0) goto err;
          Py_DECREF(item);
          item = 0;
        }
      if (nextBTreeItems(&it) < 0) goto err;
    }

  item=PyObject_GetAttr(r,sort_str);
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_CallObject(item, NULL));
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_GetAttr(r, reverse_str));
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_CallObject(item, NULL));
  UNLESS (item) goto err;
  Py_DECREF(item);

  PER_ALLOW_DEACTIVATION(self);
  return r;

 err:
  PER_ALLOW_DEACTIVATION(self);
  Py_XDECREF(r);
  Py_XDECREF(it.set);
  Py_XDECREF(item);
  return NULL;
}

/*
** BTree_getm
*/
static PyObject *
BTree_getm(BTree *self, PyObject *args)
{
  PyObject *key, *d=Py_None, *r;

  UNLESS (PyArg_ParseTuple(args, "O|O", &key, &d)) return NULL;
  if ((r=_BTree_get(self, key, 0))) return r;
  PyErr_Clear();
  Py_INCREF(d);
  return d;
}

/*
** BTree_has_key
*/
static PyObject *
BTree_has_key(BTree *self, PyObject *args)
{
  PyObject *key;

  UNLESS (PyArg_ParseTuple(args,"O",&key)) return NULL;  
  return _BTree_get(self, key, 1);
}

static PyObject *
BTree_addUnique(BTree *self, PyObject *args)
{
  int grew;
  PyObject *key, *v;

  UNLESS (PyArg_ParseTuple(args, "OO", &key, &v)) return NULL;

  if ((grew=_BTree_set(self, key, v, 1, 0)) < 0) return NULL;
  return PyInt_FromLong(grew);
}


static struct PyMethodDef BTree_methods[] = {
  {"__getstate__", (PyCFunction) BTree_getstate,	METH_VARARGS,
   "__getstate__() -- Return the picklable state of the object"},
  {"__setstate__", (PyCFunction) BTree_setstate,	METH_VARARGS,
   "__setstate__() -- Set the state of the object"},
  {"has_key",	(PyCFunction) BTree_has_key,	METH_VARARGS,
     "has_key(key) -- Test whether the bucket contains the given key"},
  {"keys",	(PyCFunction) BTree_keys,	METH_VARARGS,
     "keys([min, max]) -- Return the keys"},
  {"values",	(PyCFunction) BTree_values,	METH_VARARGS,
     "values([min, max]) -- Return the values"},
  {"items",	(PyCFunction) BTree_items,	METH_VARARGS,
     "items([min, max]) -- Return the items"},
  {"byValue",	(PyCFunction) BTree_byValue,	METH_VARARGS,
   "byValue(min) -- "
   "Return value-keys with values >= min and reverse sorted by values"
  },
  {"get",	(PyCFunction) BTree_getm,	METH_VARARGS,
   "get(key[,default]) -- Look up a value\n\n"
   "Return the default (or None) if the key is not found."
  },
  {"maxKey", (PyCFunction) BTree_maxKey,	METH_VARARGS,
   "maxKey([key]) -- Fine the maximum key\n\n"
   "If an argument is given, find the maximum <= the argument"},
  {"minKey", (PyCFunction) BTree_minKey,	METH_VARARGS,
   "minKey([key]) -- Fine the minimum key\n\n"
   "If an argument is given, find the minimum >= the argument"},
  {"clear",	(PyCFunction) BTree_clear,	METH_VARARGS,
   "clear() -- Remove all of the items from the BTree"},  
  {"insert", (PyCFunction)BTree_addUnique, METH_VARARGS,
   "insert(key, value) -- Add an item if the key is not already used.\n\n"
   "Return 1 if the item was added, or 0 otherwise"
  },
  {"update",	(PyCFunction) Mapping_update,	METH_VARARGS,
   "update(collection) -- Add the items from the given collection"},
  {"__init__",	(PyCFunction) Mapping_update,	METH_VARARGS,
   "__init__(collection) -- Initialize with items from the given collection"},
#ifdef PERSISTENT
  {"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict, METH_VARARGS,
   "_p_resolveConflict() -- Reinitialize from a newly created copy"},
  {"_p_deactivate", (PyCFunction) BTree__p_deactivate,	METH_VARARGS,
   "_p_deactivate() -- Reinitialize from a newly created copy"},
#endif
  {NULL,		NULL}		/* sentinel */
};

static void
BTree_dealloc(BTree *self)
{
  _BTree_clear(self);

  PER_DEL(self);

  Py_DECREF(self->ob_type);
  PyMem_DEL(self);
}

static int
BTree_length_or_nonzero(BTree *self, int nonzero)
{
  int c=0;
  Bucket *b, *n;
  
  PER_USE_OR_RETURN(self, -1); 
  b = self->firstbucket;
  Py_XINCREF(b);
  PER_ALLOW_DEACTIVATION(self);

  while (b != NULL) 
    {
      PER_USE_OR_RETURN(b, -1); 
      c += b->len;
      if (nonzero && c)
        {
          /* Short-circuit if all we care about is nonempty */
          PER_ALLOW_DEACTIVATION(b);
          Py_DECREF(b);
          return 1;
        }
      n = b->next;
      Py_XINCREF(n);
      PER_ALLOW_DEACTIVATION(b);
      ASSIGNB(b, n);
    }

  return c;
}

static int
BTree_length( BTree *self)
{
  return BTree_length_or_nonzero(self, 0);
}

static PyMappingMethods BTree_as_mapping = {
  (inquiry)BTree_length,		/*mp_length*/
  (binaryfunc)BTree_get,		/*mp_subscript*/
  (objobjargproc)BTree_setitem,	        /*mp_ass_subscript*/
};

static int
BTree_nonzero( BTree *self)
{
  return BTree_length_or_nonzero(self, 1);
}

static PyNumberMethods BTree_as_number_for_nonzero = {
  0,0,0,0,0,0,0,0,0,0,
  (inquiry)BTree_nonzero};

static PyExtensionClass BTreeType = {
  PyObject_HEAD_INIT(NULL)
  0,				/*ob_size*/
  PREFIX "BTree",			/*tp_name*/
  sizeof(BTree),		/*tp_basicsize*/
  0,				/*tp_itemsize*/
  /************* methods ********************/
  (destructor) BTree_dealloc,/*tp_dealloc*/
  (printfunc)0,			/*tp_print*/
  (getattrfunc)0,		/*obsolete tp_getattr*/
  (setattrfunc)0,		/*obsolete tp_setattr*/
  (cmpfunc)0,			/*tp_compare*/
  (reprfunc)0,			/*tp_repr*/
  &BTree_as_number_for_nonzero,	/*tp_as_number*/
  0,				/*tp_as_sequence*/
  &BTree_as_mapping,	/*tp_as_mapping*/
  (hashfunc)0,			/*tp_hash*/
  (ternaryfunc)0,		/*tp_call*/
  (reprfunc)0,			/*tp_str*/
  (getattrofunc)0,
  0,				/*tp_setattro*/
  
  /* Space for future expansion */
  0L,0L,
  "Mapping type implemented as sorted list of items", 
  METHOD_CHAIN(BTree_methods),
  EXTENSIONCLASS_BASICNEW_FLAG 
#ifdef PERSISTENT
  | PERSISTENT_TYPE_FLAG 
#endif
  | EXTENSIONCLASS_NOINSTDICT_FLAG,
};

--- Added File BucketTemplate.c in package Zope2 ---
/*****************************************************************************
  
  Zope Public License (ZPL) Version 1.0
  -------------------------------------
  
  Copyright (c) Digital Creations.  All rights reserved.
  
  This license has been certified as Open Source(tm).
  
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met:
  
  1. Redistributions in source code must retain the above copyright
     notice, this list of conditions, and the following disclaimer.
  
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions, and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
  
  3. Digital Creations requests that attribution be given to Zope
     in any manner possible. Zope includes a "Powered by Zope"
     button that is installed by default. While it is not a license
     violation to remove this button, it is requested that the
     attribution remain. A significant investment has been put
     into Zope, and this effort will continue if the Zope community
     continues to grow. This is one way to assure that growth.
  
  4. All advertising materials and documentation mentioning
     features derived from or use of this software must display
     the following acknowledgement:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     In the event that the product being advertised includes an
     intact Zope distribution (with copyright and license included)
     then this clause is waived.
  
  5. Names associated with Zope or Digital Creations must not be used to
     endorse or promote products derived from this software without
     prior written permission from Digital Creations.
  
  6. Modified redistributions of any form whatsoever must retain
     the following acknowledgment:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     Intact (re-)distributions of any official Zope release do not
     require an external acknowledgement.
  
  7. Modifications are encouraged but must be packaged separately as
     patches to official Zope releases.  Distributions that do not
     clearly separate the patches from the original work must be clearly
     labeled as unofficial distributions.  Modifications which do not
     carry the name Zope may be packaged in any form, as long as they
     conform to all of the clauses above.
  
  
  Disclaimer
  
    THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
    EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
  
  
  This software consists of contributions made by Digital Creations and
  many individuals on behalf of Digital Creations.  Specific
  attributions are listed in the accompanying credits file.
  
 ****************************************************************************/

/*
** _bucket_get
**
** Get the bucket item with the matching key
**
** Arguments:	self	The bucket
**		key	The key to match against
**		has_key	Just return object "1" if key found, object "0" if not
**
** Returns:	object	matching object or 0/1 object
*/
static PyObject *
_bucket_get(Bucket *self, PyObject *keyarg, int has_key)
{
  int min, max, i, l, cmp, copied=1;
  PyObject *r;
  KEY_TYPE key;
  
  COPY_KEY_FROM_ARG(key, keyarg, &copied);
  UNLESS (copied) return NULL;

  PER_USE_OR_RETURN(self, NULL);

  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 (cmp < 0) min=i;
      else if (cmp == 0)
	{
	  if (has_key) r=PyInt_FromLong(has_key);
	  else
	    {
              COPY_VALUE_TO_OBJECT(r, self->values[i]);
	    }
	  PER_ALLOW_DEACTIVATION(self);
	  return r;
	}
      else max=i;
    }

  PER_ALLOW_DEACTIVATION(self);
  if (has_key) return PyInt_FromLong(0);
  PyErr_SetObject(PyExc_KeyError, keyarg);
  return NULL;
}

static PyObject *
bucket_getitem(Bucket *self, PyObject *key)
{
  return _bucket_get(self, key, 0);
}

static int 
Bucket_grow(Bucket *self, int noval)
{
  KEY_TYPE *keys;
  VALUE_TYPE *values;

  if (self->size)
    {
      UNLESS (keys=PyRealloc(self->keys, sizeof(KEY_TYPE)*self->size*2))
        return -1;
      
      UNLESS (noval)
        {
          UNLESS (values=PyRealloc(self->values,
                                   sizeof(VALUE_TYPE)*self->size*2))
            return -1;
          self->values=values;
        }
      self->keys=keys;
      self->size*=2;
    }
  else
    {
      UNLESS (self->keys=PyMalloc(sizeof(KEY_TYPE)*MIN_BUCKET_ALLOC))
        return -1;
      UNLESS (noval || 
              (self->values=PyMalloc(sizeof(VALUE_TYPE)*MIN_BUCKET_ALLOC))
              )
        return -1;
      self->size=MIN_BUCKET_ALLOC;
    }
  
  return 0;
}

/*
** _bucket_set
**
** Assign a value into a bucket
**
** Arguments:	self	The bucket
**		key	The key of the object to insert
**		v	The value of the object to insert
**              unique  Inserting a unique key
**
** Returns:	-1 	on error
**		 0	on success with a replacement
**		 1	on success with a new value (growth)
*/
static int
_bucket_set(Bucket *self, PyObject *keyarg, PyObject *v, 
            int unique, int noval, int *changed)
{
  int min, max, i, l, cmp, copied=1;
  KEY_TYPE key;
  
  COPY_KEY_FROM_ARG(key, keyarg, &copied);
  UNLESS(copied) return -1;

  PER_USE_OR_RETURN(self, -1);

  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;
      else if (cmp==0)
	{
	  if (v)			/* Assign value to key */
	    {
              if (! unique && ! noval && self->values)
                {
                  VALUE_TYPE value;

                  COPY_VALUE_FROM_ARG(value, v, &copied);
                  UNLESS(copied) return -1;

#ifdef VALUE_SAME
                  if (VALUE_SAME(self->values[i], value))
                    { /* short-circuit if no change */
                      PER_ALLOW_DEACTIVATION(self);
                      return 0;
                    }
#endif
                  if (changed) *changed=1;
                  DECREF_VALUE(self->values[i]);
                  COPY_VALUE(self->values[i], value);
                  INCREF_VALUE(self->values[i]);
                  if (PER_CHANGED(self) < 0) goto err;
                }
	      PER_ALLOW_DEACTIVATION(self);
	      return 0;
	    }
	  else			/* There's no value so remove the item */
	    {
	      self->len--;

	      DECREF_KEY(self->keys[i]);
	      if (i < self->len)	
                memmove(self->keys+i, self->keys+i+1,
                        sizeof(KEY_TYPE)*(self->len-i));

              if (self->values && ! noval)
                {
                  DECREF_VALUE(self->values[i]);
                  if (i < self->len)	
                    memmove(self->values+i, self->values+i+1,
                            sizeof(VALUE_TYPE)*(self->len-i));

                }
	      
              if (! self->len)
		{
		  self->size=0;
		  free(self->keys);
		  self->keys=NULL;
                  if (self->values)
                    {
                      free(self->values);
                      self->values=NULL;
                    }
		}

	      if (PER_CHANGED(self) < 0) goto err;
	      PER_ALLOW_DEACTIVATION(self);
	      return 1;
	    }
	}
      else max=i;
    }

  if (!v)
    {
      PyErr_SetObject(PyExc_KeyError, keyarg);
      goto err;
    }

  if (self->len==self->size && Bucket_grow(self, noval) < 0) goto err;

  if (max != i) i++;

  if (self->len > i)
    {
      memmove(self->keys+i+1, self->keys+i,
              sizeof(KEY_TYPE)*(self->len-i));
      UNLESS (noval)
        memmove(self->values+i+1, self->values+i,
                sizeof(VALUE_TYPE)*(self->len-i));
    }


  COPY_KEY(self->keys[i], key);
  INCREF_KEY(self->keys[i]);

  UNLESS (noval)
    {
      COPY_VALUE_FROM_ARG(self->values[i], v, &copied);
      UNLESS(copied) return -1;
      INCREF_VALUE(self->values[i]);
    }

  self->len++;

  if (PER_CHANGED(self) < 0) goto err;
  PER_ALLOW_DEACTIVATION(self);
  return 1;

err:
  PER_ALLOW_DEACTIVATION(self);
  return -1;
}

/*
** bucket_setitem
**
** wrapper for _bucket_setitem (eliminates +1 return code)
**
** Arguments:	self	The bucket
**		key	The key to insert under
**		v	The value to insert
**
** Returns	 0 	on success
**		-1	on failure
*/
static int
bucket_setitem(Bucket *self, PyObject *key, PyObject *v)
{
  if (_bucket_set(self, key, v, 0, 0, 0) < 0) return -1;
  return 0;
}

static PyObject *
Mapping_update(PyObject *self, PyObject *args)
{
  PyObject *seq=0, *o, *t, *v, *tb, *k;
  int i, n=0, ind;

  UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;

  if (seq)
    {

      if (PySequence_Check(seq))
        {
          Py_INCREF(seq);
        }
      else
        {
          seq=PyObject_GetAttr(seq, items_str);
          UNLESS(seq) return NULL;
          ASSIGN(seq, PyObject_CallObject(seq, NULL));
          UNLESS(seq) return NULL;
        }

      for (i=0; ; i++)
        {
          UNLESS (o=PySequence_GetItem(seq, i))
            {
              PyErr_Fetch(&t, &v, &tb);
              if (t != PyExc_IndexError)
                {
                  PyErr_Restore(t, v, tb);
                  goto err;
                }
              Py_XDECREF(t);
              Py_XDECREF(v);
              Py_XDECREF(tb);
              break;
            }
          ind=PyArg_ParseTuple(o, "OO;items must be 2-item tuples", &k, &v);
          if (ind)
            ind = PyObject_SetItem(self, k, v);
          else
            ind=-1;
          Py_DECREF(o);
          if (ind < 0) goto err;
        }
    }

  Py_INCREF(Py_None);
  return Py_None;

 err:
  Py_DECREF(seq);
  return NULL;
}


/*
** bucket_split
**
** Splits one bucket into two
**
** Arguments:	self	The bucket
**		index	the index of the key to split at (O.O.B use midpoint)
**		next	the new bucket to split into
**
** Returns:	 0	on success
**		-1	on failure
*/
static int
bucket_split(Bucket *self, int index, Bucket *next)
{
  int next_size;

  ASSERT(self->len > 1, "split of empty bucket", -1);

  if (index < 0 || index >= self->len) index=self->len/2;

  next_size=self->len-index;

  UNLESS (next->keys=PyMalloc(sizeof(KEY_TYPE)*next_size)) return -1;
  memcpy(next->keys, self->keys+index, sizeof(KEY_TYPE)*next_size);
  if (self->values)
    {
      UNLESS (next->values=PyMalloc(sizeof(VALUE_TYPE)*next_size))
        return -1;
      memcpy(next->values, self->values+index, sizeof(VALUE_TYPE)*next_size);
    }
  next->size = next_size;
  next->len= next_size;
  self->len=index;

  next->next = self->next;

  Py_INCREF(next);
  self->next = next;

  return 0;
}

static int
Bucket_nextBucket(Bucket *self, Bucket **r)
{
  PER_USE_OR_RETURN(self, -1);
  *r=self->next;
  Py_XINCREF(*r);
  PER_ALLOW_DEACTIVATION(self);
  return 0;
}

static int 
Bucket_deleteNextBucket(Bucket *self)
{
  PER_USE_OR_RETURN(self, -1);
  if (self->next)
    {
      Bucket *n;
      if (Bucket_nextBucket(self->next, &n) < 0) goto err;
      ASSIGNB(self->next, n);
      PER_CHANGED(self);
    }
  PER_ALLOW_DEACTIVATION(self);
  return 0;
 err:
  PER_ALLOW_DEACTIVATION(self);
  return -1;
}
/*
 Bucket_findRangeEnd -- Find the index of a range endpoint 
 (possibly) contained in a bucket.

 Arguments:	self		The bucket
		key		the key to match against
		low             end flag
                offset          The output offset
	

 If low, return bucket and index of the smallest item >= key,
 otherwise return bucket and index of the largest item <= key.

 Return: 0 -- Not found, 1 -- found, -1 -- error.
*/
static int
Bucket_findRangeEnd(Bucket *self, PyObject *keyarg, int low, int *offset)
{
  int min, max, i, l, cmp, copied=1;
  Bucket *chase;
  Bucket *release = NULL;
  KEY_TYPE key;

  COPY_KEY_FROM_ARG(key, keyarg, &copied);
  UNLESS (copied) return -1;

  PER_USE_OR_RETURN(self, -1);

  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 (cmp < 0)
	min=i;
      else if (cmp == 0)
        {
          PER_ALLOW_DEACTIVATION(self);
          *offset=i;
          return 1;
        } 
      else
        max=i;
  }

  /* OK, no matches, pick max or min, depending on whether
     we want an upper or low end.
  */
  if (low) 
    {
      if (max == self->len) i=0;
      else 
        {
          i=1;
          *offset=max;
        }
    }
  else
    {
      if (max == 0) i=0;
      else 
        {
          i=1;
          *offset=min;
        }
    }

  PER_ALLOW_DEACTIVATION(self);

  return i;
}

static PyObject *
Bucket_maxminKey(Bucket *self, PyObject *args, int min)
{
  PyObject *key=0;
  int rc, offset;
  
  if (args && ! PyArg_ParseTuple(args, "|O", &key)) return NULL;
    
  PER_USE_OR_RETURN(self, NULL);

  UNLESS (self->len) goto empty;
  
  /* Find the low range */  
  if (key) 
    {
      if ((rc = Bucket_findRangeEnd(self, key, min, &offset)) <= 0)
        {
          if (rc < 0) return NULL;
          goto empty;
        }
    }
  else if (min) offset = 0;
  else offset = self->len -1;

  COPY_KEY_TO_OBJECT(key, self->keys[offset]);
  PER_ALLOW_DEACTIVATION(self);

  return key;
  
 empty:
  PyErr_SetString(PyExc_ValueError, "empty bucket");

 err:
  PER_ALLOW_DEACTIVATION(self);
  return NULL;
}

static PyObject *
Bucket_minKey(Bucket *self, PyObject *args)
{
  return Bucket_maxminKey(self, args, 1);
}

static PyObject *
Bucket_maxKey(Bucket *self, PyObject *args)
{
  return Bucket_maxminKey(self, args, 0);
}

static int 
Bucket_rangeSearch(Bucket *self, PyObject *args, int *low, int *high)
{
  PyObject *f=0, *l=0;
  int rc;
  
  if (args && ! PyArg_ParseTuple(args,"|OO",&f, &l)) return -1;
    
  UNLESS (self->len) goto empty;
  
  /* Find the low range */  
  if (f && f != Py_None) 
    {
      UNLESS (rc = Bucket_findRangeEnd(self, f, 1, low))
        {
          if (rc < 0) return -1;
          goto empty;
        }
    } 
  else *low = 0;
  
  /* Find the high range */
  if (l && l != Py_None) 
    {
      UNLESS (rc = Bucket_findRangeEnd(self, l, 0, high))
        {
          if (rc < 0) return -1;
          goto empty;
        } 
    }
  else *high=self->len - 1;

  return 0;

 empty:
  *low=0;
  *high=-1;
  return 0;
}

/*
** bucket_keys
**
** Generate a list of all keys in the bucket
**
** Arguments:	self	The Bucket
**		args	(unused)
**
** Returns:	list of bucket keys
*/  
static PyObject *
bucket_keys(Bucket *self, PyObject *args)
{
  PyObject *r=0, *key;
  int i, low, high;
  
  PER_USE_OR_RETURN(self, NULL);

  if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;

  UNLESS (r=PyList_New(high-low+1)) goto err;

  for (i=low; i <= high; i++)
    {
      COPY_KEY_TO_OBJECT(key, self->keys[i]);
      if (PyList_SetItem(r, i, key) < 0) goto err;
    }

  PER_ALLOW_DEACTIVATION(self);
  return r;

 err:
  PER_ALLOW_DEACTIVATION(self);
  Py_XDECREF(r);
  return NULL;
}

/*
** bucket_values
**
** Generate a list of all values in the bucket
**
** Arguments:	self	The Bucket
**		args	(unused)
**
** Returns	list of values
*/
static PyObject *
bucket_values(Bucket *self, PyObject *args)
{
  PyObject *r=0, *v;
  int i, low, high;

  PER_USE_OR_RETURN(self, NULL);

  if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;

  UNLESS (r=PyList_New(high-low+1)) goto err;

  for (i=low; i <= high; i++)
    {
      COPY_KEY_TO_OBJECT(v, self->keys[i]);
      UNLESS (v) goto err;
      if (PyList_SetItem(r, i, v) < 0) goto err;
    }

  PER_ALLOW_DEACTIVATION(self);
  return r;

 err:
  PER_ALLOW_DEACTIVATION(self);
  Py_XDECREF(r);
  return NULL;
}

/*
** bucket_items
**
** Returns a list of all items in a bucket
**
** Arguments:	self	The Bucket
**		args	(unused)
**		
** Returns:	list of all items in the bucket
*/
static PyObject *
bucket_items(Bucket *self, PyObject *args)
{
  PyObject *r=0, *o=0, *item=0;
  int i, low, high;

  PER_USE_OR_RETURN(self, NULL);

  if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;

  UNLESS (r=PyList_New(high-low+1)) goto err;

  for (i=low; i <= high; i++)
    {
      UNLESS (item = PyTuple_New(2)) goto err;

      COPY_KEY_TO_OBJECT(o, self->keys[i]);
      UNLESS (o) goto err;
      PyTuple_SET_ITEM(item, 0, o);

      COPY_VALUE_TO_OBJECT(o, self->values[i]);
      UNLESS (o) goto err;
      PyTuple_SET_ITEM(item, 1, o);
      
      if (PyList_SetItem(r, i, item) < 0) goto err;

      item = 0;
    }

  PER_ALLOW_DEACTIVATION(self);
  return r;

 err:
  PER_ALLOW_DEACTIVATION(self);
  Py_XDECREF(r);
  Py_XDECREF(item);
  return NULL;
}

static PyObject *
bucket_byValue(Bucket *self, PyObject *args)
{
  PyObject *r=0, *o=0, *item=0, *omin;
  VALUE_TYPE min;
  VALUE_TYPE v;
  int i, l, copied=1;

  PER_USE_OR_RETURN(self, NULL);

  UNLESS (PyArg_ParseTuple(args, "O", &omin)) return NULL;
  COPY_VALUE_FROM_ARG(min, omin, &copied);
  UNLESS(copied) return NULL;

  for (i=0, l=0; i < self->len; i++) 
    if (TEST_VALUE(self->values[i], min) >= 0) 
      l++;
    
  UNLESS (r=PyList_New(l)) goto err;

  for (i=0, l=0; i < self->len; i++)
    {
      if (TEST_VALUE(self->values[i], min) < 0) continue;
      
      UNLESS (item = PyTuple_New(2)) goto err;

      COPY_KEY_TO_OBJECT(o, self->keys[i]);
      UNLESS (o) goto err;
      PyTuple_SET_ITEM(item, 1, o);

      COPY_VALUE(v, self->values[i]);
      NORMALIZE_VALUE(v, min);
      COPY_VALUE_TO_OBJECT(o, v);
      DECREF_VALUE(v);
      UNLESS (o) goto err;
      PyTuple_SET_ITEM(item, 0, o);
      
      if (PyList_SetItem(r, l, item) < 0) goto err;
      l++;

      item = 0;
    }

  item=PyObject_GetAttr(r,sort_str);
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_CallObject(item, NULL));
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_GetAttr(r, reverse_str));
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_CallObject(item, NULL));
  UNLESS (item) goto err;
  Py_DECREF(item);

  PER_ALLOW_DEACTIVATION(self);
  return r;

 err:
  PER_ALLOW_DEACTIVATION(self);
  Py_XDECREF(r);
  Py_XDECREF(item);
  return NULL;
}

static int
_bucket_clear(Bucket *self)
{
  int i;

  if (self->next) 
    {
      Py_DECREF(self->next);
      self->next=0;
    }

  for (i=self->len; --i >= 0; )
    {
      DECREF_KEY(self->keys[i]);
      if (self->values) DECREF_VALUE(self->values[i]);
    }
  self->len=0;
  if (self->values) 
    {
      free(self->values);
      self->values=0;
    }
  if (self->keys)
    {
      free(self->keys);
      self->keys=0;
    }
  self->size=0;

  return 0;
}

#ifdef PERSISTENT
static PyObject *
bucket__p_deactivate(Bucket *self, PyObject *args)
{
  if (self->state==cPersistent_UPTODATE_STATE && self->jar)
    {
      if (_bucket_clear(self) < 0) return NULL;
      self->state=cPersistent_GHOST_STATE;
    }

  Py_INCREF(Py_None);
  return Py_None;
}
#endif

static PyObject *
bucket_clear(Bucket *self, PyObject *args)
{
  int i;

  PER_USE_OR_RETURN(self, NULL);

  if (self->len)
    {
      if (_bucket_clear(self) < 0) return NULL;
      if (PER_CHANGED(self) < 0) goto err;
    }
  PER_ALLOW_DEACTIVATION(self);
  Py_INCREF(Py_None); 
  return Py_None;

err:
  PER_ALLOW_DEACTIVATION(self);
  return NULL;
}

static PyObject *
bucket_getstate(Bucket *self, PyObject *args)
{
  PyObject *o=0, *items=0;
  int i, len, l;

  if (args && ! PyArg_ParseTuple(args, "")) return NULL;

  PER_USE_OR_RETURN(self, NULL);

  len=self->len;

  if (self->values)
    {                           /* Bucket */
      UNLESS (items=PyTuple_New(len*2)) goto err;
      for (i=0, l=0; i < len; i++)
        {
          COPY_KEY_TO_OBJECT(o, self->keys[i]);
          UNLESS (o) goto err;
          PyTuple_SET_ITEM(items, l, o);
          l++;
          
          COPY_VALUE_TO_OBJECT(o, self->values[i]);
          UNLESS (o) goto err;
          PyTuple_SET_ITEM(items, l, o);
          l++;
        }
    }
  else
    {                           /* Set */
      UNLESS (items=PyTuple_New(len)) goto err;
      for (i=0; i < len; i++)
        {
          COPY_KEY_TO_OBJECT(o, self->keys[i]);
          UNLESS (o) goto err;
          PyTuple_SET_ITEM(items, i, o);
        }
    }

  if (self->next) 
    ASSIGN(items, Py_BuildValue("OO", items, self->next));
  else
    ASSIGN(items, Py_BuildValue("(O)", items));
  
  PER_ALLOW_DEACTIVATION(self);

  return items;

err:
  PER_ALLOW_DEACTIVATION(self);
  Py_XDECREF(items);
  return NULL;
}

static int
_bucket_setstate(Bucket *self, PyObject *args)
{
  PyObject *k, *v, *r, *items;
  Bucket *next=0;
  int i, l, len, copied=1;
  KEY_TYPE *keys;
  VALUE_TYPE *values;

  UNLESS (PyArg_ParseTuple(args, "O|O", &items, &next))
    return -1;

  if ((len=PyTuple_Size(items)) < 0) return -1;
  len /= 2;

  for (i=self->len; --i >= 0; )
    {
      DECREF_KEY(self->keys[i]);
      DECREF_VALUE(self->values[i]);
    }
  self->len=0;

  if (self->next)
    {
      Py_DECREF(self->next);
      self->next=0;
    }
  
  if (len > self->size)
    {
      UNLESS (keys=PyRealloc(self->keys, sizeof(KEY_TYPE)*len)) 
        return -1;
      UNLESS (values=PyRealloc(self->values, sizeof(KEY_TYPE)*len))
        return -1;
      self->keys=keys;
      self->values=values;
      self->size=len;
    }
  
  for (i=0, l=0; i<len; i++)
    {
      k=PyTuple_GET_ITEM(items, l);
      l++;
      v=PyTuple_GET_ITEM(items, l);
      l++;

      COPY_KEY_FROM_ARG(self->keys[i], k, &copied);
      UNLESS (copied) return -1;
      COPY_VALUE_FROM_ARG(self->values[i], v, &copied);
      UNLESS (copied) return -1;
      INCREF_KEY(self->keys[i]);
      INCREF_VALUE(self->values[i]);
    }

  self->len=len;

  if (next)
    {
      self->next=next;
      Py_INCREF(next);
    }

  PER_ALLOW_DEACTIVATION(self);

  return 0;
}

static PyObject *
bucket_setstate(Bucket *self, PyObject *args)
{
  int r;

  UNLESS (PyArg_ParseTuple(args, "O", &args)) return NULL;

  PER_PREVENT_DEACTIVATION(self); 
  r=_bucket_setstate(self, args);
  PER_ALLOW_DEACTIVATION(self);

  if (r < 0) return NULL;
  Py_INCREF(Py_None);
  return Py_None;
}

/*
** bucket_has_key
**
*/
static PyObject *
bucket_has_key(Bucket *self, PyObject *args)
{
  PyObject *key;

  UNLESS (PyArg_ParseTuple(args,"O",&key)) return NULL;
  return _bucket_get(self, key, 1);
}

/*
** bucket_getm
**
*/
static PyObject *
bucket_getm(Bucket *self, PyObject *args)
{
  PyObject *key, *d=Py_None, *r;

  UNLESS (PyArg_ParseTuple(args, "O|O", &key, &d)) return NULL;
  if ((r=_bucket_get(self, key, 0))) return r;
  PyErr_Clear();
  Py_INCREF(d);
  return d;
}

#ifdef PERSISTENT
static PyObject *merge_error(int p1, int p2, int p3, int reason);
static PyObject *bucket_merge(Bucket *s1, Bucket *s2, Bucket *s3);

static PyObject *
_bucket__p_resolveConflict(PyObject *ob_type, PyObject *s[3])
{
  PyObject *r=0, *a;
  Bucket *b[3];
  int i;
  
  for (i=0; i < 3; i++)
    {
      if (b[i]=(Bucket*)PyObject_CallObject(OBJECT(ob_type), NULL))
        {
          if (s[i] == Py_None)  /* None is equivalent to empty, for BTrees */
            continue;
          ASSIGN(r, PyObject_GetAttr(OBJECT(b[i]), __setstate___str));
          if (a=PyTuple_New(1))
            {
              if (r)
                {
                  PyTuple_SET_ITEM(a, 0, s[i]);
                  Py_INCREF(s[i]);
                  ASSIGN(r, PyObject_CallObject(r, a));
                }
              Py_DECREF(a);
              if (r) continue;
            }
        }
      Py_XDECREF(r);
      while (--i >= 0)
        {
          Py_DECREF(b[i]);
        }
      return NULL;
    }
  Py_DECREF(r);
  r=NULL;

  if (b[0]->next != b[1]->next || b[0]->next != b[2]->next)
    {
      merge_error(-1, -1, -1, -1);
      goto err;
    }

  r=bucket_merge(b[0], b[1], b[2]);

 err:
  Py_DECREF(b[0]);
  Py_DECREF(b[1]);
  Py_DECREF(b[2]);

  return r;
}

static PyObject *
bucket__p_resolveConflict(Bucket *self, PyObject *args)
{
  PyObject *s[3];

  UNLESS(PyArg_ParseTuple(args, "OOO", &s[0], &s[1], &s[2])) return NULL;

  return _bucket__p_resolveConflict(OBJECT(self->ob_type), s);
}
#endif

static struct PyMethodDef Bucket_methods[] = {
  {"__getstate__", (PyCFunction) bucket_getstate,	METH_VARARGS,
   "__getstate__() -- Return the picklable state of the object"},
  {"__setstate__", (PyCFunction) bucket_setstate,	METH_VARARGS,
   "__setstate__() -- Set the state of the object"},
  {"keys",	(PyCFunction) bucket_keys,	METH_VARARGS,
     "keys([min, max]) -- Return the keys"},
  {"has_key",	(PyCFunction) bucket_has_key,	METH_VARARGS,
     "has_key(key) -- Test whether the bucket contains the given key"},
  {"clear",	(PyCFunction) bucket_clear,	METH_VARARGS,
   "clear() -- Remove all of the items from the bucket"},
  {"update",	(PyCFunction) Mapping_update,	METH_VARARGS,
   "update(collection) -- Add the items from the given collection"},
  {"__init__",	(PyCFunction) Mapping_update,	METH_VARARGS,
   "__init__(collection) -- Initialize with items from the given collection"},
  {"maxKey", (PyCFunction) Bucket_maxKey,	METH_VARARGS,
   "maxKey([key]) -- Fine the maximum key\n\n"
   "If an argument is given, find the maximum <= the argument"},
  {"minKey", (PyCFunction) Bucket_minKey,	METH_VARARGS,
   "minKey([key]) -- Fine the minimum key\n\n"
   "If an argument is given, find the minimum >= the argument"},
  {"values",	(PyCFunction) bucket_values,	METH_VARARGS,
     "values([min, max]) -- Return the values"},
  {"items",	(PyCFunction) bucket_items,	METH_VARARGS,
     "items([min, max])) -- Return the items"},
  {"byValue",	(PyCFunction) bucket_byValue,	METH_VARARGS,
   "byValue(min) -- "
   "Return value-keys with values >= min and reverse sorted by values"
  },
  {"get",	(PyCFunction) bucket_getm,	METH_VARARGS,
   "get(key[,default]) -- Look up a value\n\n"
   "Return the default (or None) if the key is not found."
  },
#ifdef PERSISTENT
  {"_p_resolveConflict", (PyCFunction) bucket__p_resolveConflict, METH_VARARGS,
   "_p_resolveConflict() -- Reinitialize from a newly created copy"},
  {"_p_deactivate", (PyCFunction) bucket__p_deactivate, METH_VARARGS,
   "_p_deactivate() -- Reinitialize from a newly created copy"},
#endif
  {NULL,		NULL}		/* sentinel */
};

static void
Bucket_dealloc(Bucket *self)
{
  int i;

  _bucket_clear(self);

  PER_DEL(self);

  Py_DECREF(self->ob_type);
  PyMem_DEL(self);
}

/* Code to access Bucket objects as mappings */
static int
Bucket_length( Bucket *self)
{
  int r;
  PER_USE_OR_RETURN(self, -1);
  r=self->len;
  PER_ALLOW_DEACTIVATION(self);
  return r;
}

static PyMappingMethods Bucket_as_mapping = {
  (inquiry)Bucket_length,		/*mp_length*/
  (binaryfunc)bucket_getitem,		/*mp_subscript*/
  (objobjargproc)bucket_setitem,	/*mp_ass_subscript*/
};

static PyObject *
bucket_repr(Bucket *self)
{
  static PyObject *format;
  PyObject *r, *t;

  UNLESS (format) UNLESS (format=PyString_FromString(PREFIX "Bucket(%s)")) 
    return NULL;
  UNLESS (t=PyTuple_New(1)) return NULL;
  UNLESS (r=bucket_items(self,NULL)) goto err;
  PyTuple_SET_ITEM(t,0,r);
  r=t;
  ASSIGN(r,PyString_Format(format,r));
  return r;
err:
  Py_DECREF(t);
  return NULL;
}

static PyExtensionClass BucketType = {
  PyObject_HEAD_INIT(NULL)
  0,				/*ob_size*/
  PREFIX "Bucket",			/*tp_name*/
  sizeof(Bucket),		/*tp_basicsize*/
  0,				/*tp_itemsize*/
  /*********** methods ***********************/
  (destructor) Bucket_dealloc,	/*tp_dealloc*/
  (printfunc)0,			/*tp_print*/
  (getattrfunc)0,		/*obsolete tp_getattr*/
  (setattrfunc)0,		/*obsolete tp_setattr*/
  (cmpfunc)0,			/*tp_compare*/
  (reprfunc) bucket_repr,	/*tp_repr*/
  0,				/*tp_as_number*/
  0,				/*tp_as_sequence*/
  &Bucket_as_mapping,		/*tp_as_mapping*/
  (hashfunc)0,			/*tp_hash*/
  (ternaryfunc)0,		/*tp_call*/
  (reprfunc)0,			/*tp_str*/
  (getattrofunc)0,		/*tp_getattro*/
  0,				/*tp_setattro*/
  
  /* Space for future expansion */
  0L,0L,
  "Mapping type implemented as sorted list of items", 
  METHOD_CHAIN(Bucket_methods),
  EXTENSIONCLASS_BASICNEW_FLAG
#ifdef PERSISTENT
  | PERSISTENT_TYPE_FLAG 
#endif
  | EXTENSIONCLASS_NOINSTDICT_FLAG,
};


static int 
nextBucket(SetIteration *i)
{
  UNLESS(PER_USE(BUCKET(i->set))) return -1;
          
  if (i->position >= 0)
    {
      if (i->position)
        {
          DECREF_KEY(i->key);
          DECREF_VALUE(i->value);
        }

      if (i->position < BUCKET(i->set)->len)
        {
          COPY_KEY(i->key, BUCKET(i->set)->keys[i->position]);
          INCREF_KEY(i->key);
          COPY_VALUE(i->value, BUCKET(i->set)->values[i->position]);
          INCREF_VALUE(i->value);
          i->position ++;
        }
      else
        i->position = -1;
    }

  PER_ALLOW_DEACTIVATION(BUCKET(i->set));
          
  return 0;
}

--- Added File IIBTree.c in package Zope2 ---
/* Setup template macros */

#define PERSISTENT

#define PREFIX "II"
#define INITMODULE initIIBTree
#define DEFAULT_MAX_BUCKET_SIZE 120
#define DEFAULT_MAX_BTREE_SIZE 500
                
#include "intkeymacros.h"
#include "intvaluemacros.h"
#include "cPersistence.h"
#include "BTree/intSet.h"
#include "BTreeModuleTemplate.c"

--- Added File IOBTree.c in package Zope2 ---

#define PERSISTENT

#define PREFIX "IO"
#define DEFAULT_MAX_BUCKET_SIZE 60
#define DEFAULT_MAX_BTREE_SIZE 500
#define INITMODULE initIOBTree
                                
#include "intkeymacros.h"
#include "objectvaluemacros.h"
#include "cPersistence.h"
#include "BTree/intSet.h"
#include "BTreeModuleTemplate.c"

--- Added File Interfaces.py in package Zope2 ---
##############################################################################
# 
# Zope Public License (ZPL) Version 1.0
# -------------------------------------
# 
# Copyright (c) Digital Creations.  All rights reserved.
# 
# This license has been certified as Open Source(tm).
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
# 
# 1. Redistributions in source code must retain the above copyright
#    notice, this list of conditions, and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions, and the following disclaimer in
#    the documentation and/or other materials provided with the
#    distribution.
# 
# 3. Digital Creations requests that attribution be given to Zope
#    in any manner possible. Zope includes a "Powered by Zope"
#    button that is installed by default. While it is not a license
#    violation to remove this button, it is requested that the
#    attribution remain. A significant investment has been put
#    into Zope, and this effort will continue if the Zope community
#    continues to grow. This is one way to assure that growth.
# 
# 4. All advertising materials and documentation mentioning
#    features derived from or use of this software must display
#    the following acknowledgement:
# 
#      "This product includes software developed by Digital Creations
#      for use in the Z Object Publishing Environment
#      (http://www.zope.org/)."
# 
#    In the event that the product being advertised includes an
#    intact Zope distribution (with copyright and license included)
#    then this clause is waived.
# 
# 5. Names associated with Zope or Digital Creations must not be used to
#    endorse or promote products derived from this software without
#    prior written permission from Digital Creations.
# 
# 6. Modified redistributions of any form whatsoever must retain
#    the following acknowledgment:
# 
#      "This product includes software developed by Digital Creations
#      for use in the Z Object Publishing Environment
#      (http://www.zope.org/)."
# 
#    Intact (re-)distributions of any official Zope release do not
#    require an external acknowledgement.
# 
# 7. Modifications are encouraged but must be packaged separately as
#    patches to official Zope releases.  Distributions that do not
#    clearly separate the patches from the original work must be clearly
#    labeled as unofficial distributions.  Modifications which do not
#    carry the name Zope may be packaged in any form, as long as they
#    conform to all of the clauses above.
# 
# 
# Disclaimer
# 
#   THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
#   EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
#   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
#   PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
#   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
#   USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
#   ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
#   OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
#   OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
#   SUCH DAMAGE.
# 
# 
# This software consists of contributions made by Digital Creations and
# many individuals on behalf of Digital Creations.  Specific
# attributions are listed in the accompanying credits file.
# 
##############################################################################

import OOBTree, Interface

class ICollection(Interface.Base):

    def clear():
        """Remove all of the items from the collection"""

    def __nonzero__():
        """Check if the collection is non-empty.

        Return a true value if the collection is non-empty and a
        false otherwise.
        """

class ISized(ICollection):

    def __len__():
        """Return the number of items in the set"""

class IReadSequence(Interface.Base):

    def __getitem__(index):
        """Return an item for a given index."""

    def __getslice__(index1, index2):
        """Return a subsequence from the original sequence

        Such that the subsequence includes the items from index1 up
        to, but not including, index2.
        """

class IKeyed(ICollection):

    def has_key(key):
        """Check whether the object has an item with the given key"""

    def keys(min=None, max=None):
        """Return an IReadSequence containing the keys in the collection

        The type of the IReadSequence is not specified. It could be a
        list or a tuple or some other type.

        If a min is specified, then output is constrained to
        items having keys greater than or equal to the given min.
        A min value of None is ignored.

        If a max is specified, then output is constrained to
        items having keys less than or equal to the given min.
        A max value of None is ignored.
        """

    def maxKey(key=None):
        """Return the maximum key

        If a key argument if provided, return the largest key that is
        less than or equal to the argument.
        """

    def minKey(key=None):
        """Return the minimum key

        If a key argument if provided, return the smallest key that is
        greater than or equal to the argument.
        """

class ISetMutable(IKeyed):
    
    def insert(key):
        """Add the key (value) to the set.

        If the key was already in the set, return 0, otherwise return 1.
        """

    def remove(key):
        """Remove the key from the set."""
        
    def update(seq):
        """Add the items from the given sequence to the set"""

class IKeySequence(IKeyed, ISized):

    def __getitem__(index):
        """Return the key in the given index position

        This allows iteration with for loops and use in functions,
        like map and list, that read sequences.
        """

class ISet(IKeySequence, ISetMutable):
    pass

class ITreeSet(IKeyed, ISetMutable):
    pass
    

class IDictionaryIsh(IKeyed, ISized):

    def __getitem__(key):
        """Get the value for the given key

        Raise a key error if the key if not in the collection.
        """

    def get(key, default=None):
        """Get the value for the given key

        Raise a key error if the key if not in the collection and no
        default is specified.

        Return the default if specified and the key is not in the
        collection.
        """

    def __setitem__(key, value):
        """Set the value for the given key"""

    def __delitem__(key):
        """delete the value for the given key

        Raise a key error if the key if not in the collection."""

    def update(collection):
        """Add the items from the given collection object to the collection

        The input collection must be a sequence of key-value tuples,
        or an object with an 'items' method that returns a sequence of
        key-value tuples.
        """

    def values(min=None, max=None):
        """Return a IReadSequence containing the values in the collection

        The type of the IReadSequence is not specified. It could be a
        list or a tuple or some other type.

        If a min is specified, then output is constrained to
        items having keys greater than or equal to the given min.
        A min value of None is ignored.

        If a max is specified, then output is constrained to
        items having keys less than or equal to the given min.
        A max value of None is ignored.
        """

    def items(min=None, max=None):
        """Return a IReadSequence containing the items in the collection

        An item is a key-value tuple.

        The type of the IReadSequence is not specified. It could be a
        list or a tuple or some other type.

        If a min is specified, then output is constrained to
        items having keys greater than or equal to the given min.
        A min value of None is ignored.

        If a max is specified, then output is constrained to
        items having keys less than or equal to the given min.
        A max value of None is ignored.
        """

    def byValue(minValue):
        """Return a sequence of value-key pairs, sorted by value

        Values < min are ommitted and other values are "normalized" by
        the minimum value. This normalization may be a noop, but, for
        integer values, the normalization is division.
        """
    
class IBTree(IDictionaryIsh):

    def insert(key, value):
        """Insert a key and value into the collection.

        If the key was already in the collection, then there is no
        change and 0 is returned.

        If the key was not already in the collection, then the item is
        added and 1 is returned.

        This method is here to allow one to generate random keys and
        to insert and test whether the key was there in one operation.

        A standard idiom for generating new keys will be::

          key=generate_key()
          while not t.insert(key, value):
              key=generate_key()
        """

class IMerge(Interfaces.Base):
    """Object with methods for merging sets, buckets, and trees.

    These methods are supplied in modules that define collection
    classes with particular key and value types. The operations apply
    only to collections from the same module.  For example, the
    IIBTree.union can only be used with IIBTree.IIBTree,
    IIBTree.IIBucket, IIBTree.IISet, and IIBTree.IITreeSet.

    The implementing module has a value type. The IOBTree and OOBTree
    modules have object value type. The IIBTree and OIBTree modules
    have integer value tyoes. Other modules may be defined in the
    future that have other value types.

    The individual types are classified into set (Set and TreeSet) and
    mapping (Bucket and BTree) types.
    """

    def difference(c1, c2):
        """Return the keys or items in c1 for which there is no key in
        c2.

        If c1 is None, then None is returned.  If c2 is none, then c1
        is returned.
        """

    def union(c1, c2):
        """Compute the Union of c1 and c2.

        If c1 is None, then c2 is returned, otherwise, if c2 is None,
        then c1 is returned.

        The output is a Set containing keys from the input
        collections.
        """

    def intersection(c1, c2):
        """Compute the Union of c1 and c2.

        If c1 is None, then c2 is returned, otherwise, if c2 is None,
        then c1 is returned.

        The output is a Set containing matching keys from the input
        collections.
        """

class IIMerge(IMerge):
    """Merge collections with integer value type.

    A primary intent is to support operations with no or integer
    values, which are used as "scores" to rate indiviual keys. That
    is, in this context, a BTree or Bucket is viewed as a set with
    scored keys, using integer scores.
    """

    def weightedUnion(c1, c2, weight1=1, weight2=1):
        """Compute the weighted Union of c1 and c2.

        If c1 and c2 are None, the output is 0 and None

        if c1 is None and c2 is not None, the output is weight2 and
        c2.

        if c1 is not None and c2 not None, the output is weight1 and
        c1.

        If c1 and c2 are not None, the output is 1 and a Bucket
        such that the output values are::

          v1*weight1 + v2*weight2

          where:

            v1 is 0 if the key was not in c1. Otherwise, v1 is 1, if
            c1 is a set, or the value from c1.

            v2 is 0 if the key was not in c2. Otherwise, v2 is 2, if
            c2 is a set, or the value from c2.

        Note that c1 and c2 must be collections. None may not be
        passed as one of the collections.
        """

    def weightedIntersection(c1, c2, weight1=1, weight2=1):
        """Compute the weighted intersection of c1 and c2.

        If c1 and c2 are None, the output is None, None.

        if c1 is None and c2 is not None, the output is weight2 and
        c2.

        if c1 is not None and c2 not None, the output is weight1 and
        c1.

        If c1 and c2 are sets, the output is the sum of the weights
        and the (unweighted) intersection of the sets.

        If c1 and c2 are not None and not both sets, the output is 1
        and a Bucket such that the output values are::

          v1*weight1 + v2*weight2

          where:

            v1 is 0 if the key was not in c1. Otherwise, v1 is 1, if
            c1 is a set, or the value from c1.

            v2 is 0 if the key was not in c2. Otherwise, v2 is 2, if
            c2 is a set, or the value from c2.

        Note that c1 and c2 must be collections. None may not be
        passed as one of the collections.
        """

###############################################################
# IMPORTANT NOTE
#
# Getting the length of a BTree, TreeSet, or output of keys,
# values, or items of same is expensive. If you need to get the
# length, you need to maintain this separately.
#
# Eventually, I need to express this through the interfaces.
#
################################################################

    
Interface.assertTypeImplements(OOBTree.OOSet, ISet)
Interface.assertTypeImplements(OOBTree.OOTreeSet, ITreeSet)
Interface.assertTypeImplements(OOBTree.OOBucket, IDictionaryIsh)
Interface.assertTypeImplements(OOBTree.OOBTree, IBTree)



--- Added File Length.py in package Zope2 ---
##############################################################################
# 
# Zope Public License (ZPL) Version 1.0
# -------------------------------------
# 
# Copyright (c) Digital Creations.  All rights reserved.
# 
# This license has been certified as Open Source(tm).
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
# 
# 1. Redistributions in source code must retain the above copyright
#    notice, this list of conditions, and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions, and the following disclaimer in
#    the documentation and/or other materials provided with the
#    distribution.
# 
# 3. Digital Creations requests that attribution be given to Zope
#    in any manner possible. Zope includes a "Powered by Zope"
#    button that is installed by default. While it is not a license
#    violation to remove this button, it is requested that the
#    attribution remain. A significant investment has been put
#    into Zope, and this effort will continue if the Zope community
#    continues to grow. This is one way to assure that growth.
# 
# 4. All advertising materials and documentation mentioning
#    features derived from or use of this software must display
#    the following acknowledgement:
# 
#      "This product includes software developed by Digital Creations
#      for use in the Z Object Publishing Environment
#      (http://www.zope.org/)."
# 
#    In the event that the product being advertised includes an
#    intact Zope distribution (with copyright and license included)
#    then this clause is waived.
# 
# 5. Names associated with Zope or Digital Creations must not be used to
#    endorse or promote products derived from this software without
#    prior written permission from Digital Creations.
# 
# 6. Modified redistributions of any form whatsoever must retain
#    the following acknowledgment:
# 
#      "This product includes software developed by Digital Creations
#      for use in the Z Object Publishing Environment
#      (http://www.zope.org/)."
# 
#    Intact (re-)distributions of any official Zope release do not
#    require an external acknowledgement.
# 
# 7. Modifications are encouraged but must be packaged separately as
#    patches to official Zope releases.  Distributions that do not
#    clearly separate the patches from the original work must be clearly
#    labeled as unofficial distributions.  Modifications which do not
#    carry the name Zope may be packaged in any form, as long as they
#    conform to all of the clauses above.
# 
# 
# Disclaimer
# 
#   THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
#   EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
#   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
#   PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
#   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
#   USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
#   ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
#   OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
#   OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
#   SUCH DAMAGE.
# 
# 
# This software consists of contributions made by Digital Creations and
# many individuals on behalf of Digital Creations.  Specific
# attributions are listed in the accompanying credits file.
# 
##############################################################################

import Persistence

class Length(Persistence.Persistent):
    """BTree lengths aqre too expensive to compute

    Objects that use BTrees need to keep track of lengths themselves.
    This class provides an object for doing this.

    As a bonus, the object support application-level conflict resolution.
    """

    def __init__(self, v=0): self.value=v

    def __getstate__(self): return self.value

    def __setstate__(self, v): self.value=v

    def set(self, v): self.value=v

    def _p_resolveConflict(self, old, s1, s2): return s1 + s2 - old

    def _p_independent(self):
        # My state doesn't depend on or materially effect the state of
        # other objects.
        return 1

    def change(self, delta): self.value = self.value + delta

    def __call__(self, *args): return self.value

--- Added File MergeTemplate.c in package Zope2 ---
/*****************************************************************************
  
  Zope Public License (ZPL) Version 1.0
  -------------------------------------
  
  Copyright (c) Digital Creations.  All rights reserved.
  
  This license has been certified as Open Source(tm).
  
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met:
  
  1. Redistributions in source code must retain the above copyright
     notice, this list of conditions, and the following disclaimer.
  
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions, and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
  
  3. Digital Creations requests that attribution be given to Zope
     in any manner possible. Zope includes a "Powered by Zope"
     button that is installed by default. While it is not a license
     violation to remove this button, it is requested that the
     attribution remain. A significant investment has been put
     into Zope, and this effort will continue if the Zope community
     continues to grow. This is one way to assure that growth.
  
  4. All advertising materials and documentation mentioning
     features derived from or use of this software must display
     the following acknowledgement:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     In the event that the product being advertised includes an
     intact Zope distribution (with copyright and license included)
     then this clause is waived.
  
  5. Names associated with Zope or Digital Creations must not be used to
     endorse or promote products derived from this software without
     prior written permission from Digital Creations.
  
  6. Modified redistributions of any form whatsoever must retain
     the following acknowledgment:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     Intact (re-)distributions of any official Zope release do not
     require an external acknowledgement.
  
  7. Modifications are encouraged but must be packaged separately as
     patches to official Zope releases.  Distributions that do not
     clearly separate the patches from the original work must be clearly
     labeled as unofficial distributions.  Modifications which do not
     carry the name Zope may be packaged in any form, as long as they
     conform to all of the clauses above.
  
  
  Disclaimer
  
    THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
    EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
  
  
  This software consists of contributions made by Digital Creations and
  many individuals on behalf of Digital Creations.  Specific
  attributions are listed in the accompanying credits file.
  
 ****************************************************************************/

/****************************************************************************
 Set operations
 ****************************************************************************/

static int
merge_output(Bucket *r, SetIteration *i, int mapping)
{
  if(r->len >= r->size && Bucket_grow(r, ! mapping) < 0) return -1;
  COPY_KEY(r->keys[r->len], i->key);
  INCREF_KEY(r->keys[r->len]);
  if (mapping)
    {
      COPY_VALUE(r->values[r->len], i->value);
      INCREF_VALUE(r->values[r->len]);
    }
  r->len++;
  return 0;
}

static PyObject *
merge_error(int p1, int p2, int p3, int reason)
{
  PyObject *r;

  UNLESS (r=Py_BuildValue("iiii", p1, p2, p3, reason)) r=Py_None;
  PyErr_SetObject(PyExc_ValueError, r);
  if (r != Py_None) Py_DECREF(r);

  return NULL;
}

static PyObject *
bucket_merge(Bucket *s1, Bucket *s2, Bucket *s3)
{
  Bucket *r=0;
  PyObject *s;
  SetIteration i1 = {0,0,0}, i2 = {0,0,0}, i3 = {0,0,0}, it;
  int cmp12, cmp13, cmp23, mapping=0, set;

  if (initSetIteration(&i1, OBJECT(s1), 0, &mapping) < 0) return NULL;
  if (initSetIteration(&i2, OBJECT(s2), 0, &mapping) < 0) return NULL;
  if (initSetIteration(&i3, OBJECT(s3), 0, &mapping) < 0) return NULL;

  set = ! mapping;

  if (mapping)
    {
      UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&BucketType), NULL)))
        goto err;
    }
  else
    {
      UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&SetType), NULL)))
        goto err;
    }

  if (i1.next(&i1) < 0) return NULL;
  if (i2.next(&i2) < 0) return NULL;
  if (i3.next(&i3) < 0) return NULL;

  while (i1.position >= 0 && i2.position >= 0 && i3.position >= 0)
    {
      cmp12=TEST_KEY(i1.key, i2.key);
      cmp13=TEST_KEY(i1.key, i3.key);
      if (cmp12==0)
        {
          if (cmp13==0)
            {
              if (set || (TEST_VALUE(i1.value, i2.value) == 0))
                {               /* change in i3 or all same */
                  if (merge_output(r, &i3, mapping) < 0) goto err;
                }
              else if (set || (TEST_VALUE(i1.value, i3.value) == 0))
                {               /* change in i2 */
                  if (merge_output(r, &i2, mapping) < 0) goto err;
                }
              else
                {               /* conflicting changes in i2 and i3 */
                  merge_error(i1.position, i2.position, i3.position, 1);
                  goto err;
                }
              if (i1.next(&i1) < 0) goto err;
              if (i2.next(&i2) < 0) goto err;
              if (i3.next(&i3) < 0) goto err;
            }
          else if (cmp13 > 0)
            {                   /* insert i3 */
              if (merge_output(r, &i3, mapping) < 0) goto err;
              if (i3.next(&i3) < 0) goto err;
            }
          else if (set || (TEST_VALUE(i1.value, i2.value) == 0))
            {                   /* delete i3 */
              if (i1.next(&i1) < 0) goto err;
              if (i2.next(&i2) < 0) goto err;
            }
          else
            {                   /* conflicting del in i3 and change in i2 */
              merge_error(i1.position, i2.position, i3.position, 2);
              goto err;
            }
        }
      else if (cmp13 == 0)
        {
          if (cmp12 > 0)
            {                   /* insert i2 */
              if (merge_output(r, &i2, mapping) < 0) goto err;
              if (i2.next(&i2) < 0) goto err;
            }
          else if (set || (TEST_VALUE(i1.value, i3.value) == 0))
            {                   /* delete i2 */
              if (i1.next(&i1) < 0) goto err;
              if (i3.next(&i3) < 0) goto err;
            }
          else
            {                   /* conflicting del in i2 and change in i3 */
              merge_error(i1.position, i2.position, i3.position, 3);
              goto err;
            }
        }
      else
        {                       /* Both keys changed */
          cmp23=TEST_KEY(i2.key, i3.key);
          if (cmp23==0)
            {                   /* dualing inserts or deletes */
              merge_error(i1.position, i2.position, i3.position, 4);
              goto err;
            }
          if (cmp12 > 0)
            {                   /* insert i2 */
              if (cmp23 > 0)
                {               /* insert i3 first */
                  if (merge_output(r, &i3, mapping) < 0) goto err;
                  if (i3.next(&i3) < 0) goto err;
                }
              else
                {               /* insert i2 first */
                  if (merge_output(r, &i2, mapping) < 0) goto err;
                  if (i2.next(&i2) < 0) goto err;
                }
            }
          else if (cmp13 > 0)
            {                   /* Insert i3 */
              if (merge_output(r, &i3, mapping) < 0) goto err;
              if (i3.next(&i3) < 0) goto err;
            }
          else
            {                   /* Dueling deletes */
              merge_error(i1.position, i2.position, i3.position, 5);
              goto err;
            }
        }
    }

  while (i2.position >= 0 && i3.position >= 0)
    {                           /* New inserts */
      cmp23=TEST_KEY(i2.key, i3.key);
      if (cmp23==0)
        {                       /* dualing inserts */
          merge_error(i1.position, i2.position, i3.position, 6);
          goto err;
        }
      if (cmp23 > 0)
        {                       /* insert i3 */
          if (merge_output(r, &i3, mapping) < 0) goto err;
          if (i3.next(&i3) < 0) goto err;
        }
      else
        {                       /* insert i2 */
          if (merge_output(r, &i2, mapping) < 0) goto err;
          if (i2.next(&i2) < 0) goto err;
        }
    }

  while (i1.position >= 0 && i2.position >= 0)
    {                           /* deleting i3 */
      cmp12=TEST_KEY(i1.key, i2.key);
      if (cmp12 > 0)
        {                       /* insert i2 */
          if (merge_output(r, &i2, mapping) < 0) goto err;
          if (i2.next(&i2) < 0) goto err;
        }
      else if (cmp12==0 && (set || (TEST_VALUE(i1.value, i2.value) == 0)))
        {                       /* delete i3 */
          if (i1.next(&i1) < 0) goto err;
          if (i2.next(&i2) < 0) goto err;
        }
      else
        {                       /* Dualing deletes or delete and change */
          merge_error(i1.position, i2.position, i3.position, 7);
          goto err;
        }
    }

  while (i1.position >= 0 && i3.position >= 0)
    {                           /* deleting i2 */
      cmp13=TEST_KEY(i1.key, i3.key);
      if (cmp13 > 0)
        {                       /* insert i3 */
          if (merge_output(r, &i3, mapping) < 0) goto err;
          if (i3.next(&i3) < 0) goto err;
        }
      else if (cmp13==0 && (set || (TEST_VALUE(i1.value, i3.value) == 0)))
        {                       /* delete i2 */
          if (i1.next(&i1) < 0) goto err;
          if (i3.next(&i3) < 0) goto err;
        }
      else
        {                       /* Dualing deletes or delete and change */
          merge_error(i1.position, i2.position, i3.position, 8);
          goto err;
        }
    }

  if (i1.position >= 0)
    {                           /* Dueling deletes */
      merge_error(i1.position, i2.position, i3.position, 9);
      goto err;
    }

  while (i2.position >= 0)
    {                           /* Inserting i2 at end */
      if (merge_output(r, &i2, mapping) < 0) goto err;
      if (i2.next(&i2) < 0) goto err;
    }

  while (i3.position >= 0)
    {                           /* Inserting i2 at end */
      if (merge_output(r, &i3, mapping) < 0) goto err;
      if (i3.next(&i3) < 0) goto err;
    }
  
  Py_DECREF(i1.set);
  Py_DECREF(i2.set);
  Py_DECREF(i3.set);

  if (s1->next)
    {
      Py_INCREF(s1->next);
      r->next = s1->next;
    }
  s=bucket_getstate(r, NULL);
  Py_DECREF(r);

  return s;

invalid_set_operation:
  PyErr_SetString(PyExc_TypeError, "invalid set operation");
err:
  Py_XDECREF(i1.set);
  Py_XDECREF(i2.set);
  Py_XDECREF(i3.set);
  Py_XDECREF(r);
  return NULL;
}

--- Added File OIBTree.c in package Zope2 ---

#define PERSISTENT

#define PREFIX "OI"
#define INITMODULE initOIBTree
#define DEFAULT_MAX_BUCKET_SIZE 60
#define DEFAULT_MAX_BTREE_SIZE 250
                                
#include "objectkeymacros.h"
#include "intvaluemacros.h"
#include "BTreeModuleTemplate.c"

--- Added File OOBTree.c in package Zope2 ---

#define PERSISTENT

#define PREFIX "OO"
#define INITMODULE initOOBTree
#define DEFAULT_MAX_BUCKET_SIZE 30
#define DEFAULT_MAX_BTREE_SIZE 250
                                
#include "objectkeymacros.h"
#include "objectvaluemacros.h"
#include "BTreeModuleTemplate.c"

--- Added File SetOpTemplate.c in package Zope2 ---
/*****************************************************************************
  
  Zope Public License (ZPL) Version 1.0
  -------------------------------------
  
  Copyright (c) Digital Creations.  All rights reserved.
  
  This license has been certified as Open Source(tm).
  
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met:
  
  1. Redistributions in source code must retain the above copyright
     notice, this list of conditions, and the following disclaimer.
  
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions, and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
  
  3. Digital Creations requests that attribution be given to Zope
     in any manner possible. Zope includes a "Powered by Zope"
     button that is installed by default. While it is not a license
     violation to remove this button, it is requested that the
     attribution remain. A significant investment has been put
     into Zope, and this effort will continue if the Zope community
     continues to grow. This is one way to assure that growth.
  
  4. All advertising materials and documentation mentioning
     features derived from or use of this software must display
     the following acknowledgement:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     In the event that the product being advertised includes an
     intact Zope distribution (with copyright and license included)
     then this clause is waived.
  
  5. Names associated with Zope or Digital Creations must not be used to
     endorse or promote products derived from this software without
     prior written permission from Digital Creations.
  
  6. Modified redistributions of any form whatsoever must retain
     the following acknowledgment:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     Intact (re-)distributions of any official Zope release do not
     require an external acknowledgement.
  
  7. Modifications are encouraged but must be packaged separately as
     patches to official Zope releases.  Distributions that do not
     clearly separate the patches from the original work must be clearly
     labeled as unofficial distributions.  Modifications which do not
     carry the name Zope may be packaged in any form, as long as they
     conform to all of the clauses above.
  
  
  Disclaimer
  
    THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
    EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
  
  
  This software consists of contributions made by Digital Creations and
  many individuals on behalf of Digital Creations.  Specific
  attributions are listed in the accompanying credits file.
  
 ****************************************************************************/

/****************************************************************************
 Set operations
 ****************************************************************************/

#ifdef INTSET_H
static int 
nextIntSet(SetIteration *i)
{
  UNLESS(PER_USE(INTSET(i->set))) return -1;
          
  if (i->position >= 0)
    {
      if (i->position < INTSET(i->set)->len)
        {
          i->key = INTSET(i->set)->data[i->position];
          i->position ++;
        }
      else
        i->position = -1;
    }

  PER_ALLOW_DEACTIVATION(INTSET(i->set));
          
  return 0;
}
#endif

#ifdef KEY_CHECK
static int 
nextKeyAsSet(SetIteration *i)
{
  if (i->position >= 0)
    {
      if (i->position < 1)
        {
          i->position ++;
        }
      else
        i->position = -1;
    }
  return 0;
}
#endif

static int
initSetIteration(SetIteration *i, PyObject *s, int w, int *merge)
{
  i->position=0;

  if (ExtensionClassSubclassInstance_Check(s, &BucketType))
    {
      i->set = s;
      Py_INCREF(s);

      if (w >= 0) 
        {
          *merge=1;
          i->next=nextBucket;
        }
      else
        i->next=nextSet;

      i->hasValue=1;
    }
  else if (ExtensionClassSubclassInstance_Check(s, &SetType))
    {
      i->set = s;
      Py_INCREF(s);

      i->next=nextSet;
      i->hasValue=0;
    }
  else if (ExtensionClassSubclassInstance_Check(s, &BTreeType))
    {
      i->set=BTree_rangeSearch(BTREE(s), NULL, 'i');
      UNLESS(i->set) return -1;

      if (w >= 0) 
        {
          *merge=1;
          i->next=nextBTreeItems;
        }
      else
        i->next=nextTreeSetItems;
      i->hasValue=1;
    }
  else if (ExtensionClassSubclassInstance_Check(s, &TreeSetType))
    {
      i->set=BTree_rangeSearch(BTREE(s), NULL, 'k');
      UNLESS(i->set) return -1;

      i->next=nextTreeSetItems;
      i->hasValue=0;
    }
#ifdef INTSET_H
  else if (s->ob_type==(PyTypeObject*)intSetType)
    {
      i->set = s;
      Py_INCREF(s);

      i->next=nextIntSet;
      i->hasValue=0;
    }
#endif
#ifdef KEY_CHECK
  else if (KEY_CHECK(s))
    {
      int copied=1;

      i->set = s;
      Py_INCREF(s);
      i->next=nextKeyAsSet;
      i->hasValue=0;
      COPY_KEY_FROM_ARG(i->key, s, &copied);
      UNLESS (copied) return -1;
    }
#endif
  else
    {
      PyErr_SetString(PyExc_TypeError, "invalid argument");
      return -1;
    }

  return 0;
}

#ifndef MERGE_WEIGHT
#define MERGE_WEIGHT(O, w) (O)
#endif

static int 
copyRemaining(Bucket *r, SetIteration *i, int merge, int w)
{
  while (i->position >= 0)
    {
      if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) return -1;
      COPY_KEY(r->keys[r->len], i->key);
      INCREF_KEY(r->keys[r->len]);

      if (merge)
        {
          COPY_VALUE(r->values[r->len], MERGE_WEIGHT(i->value, w));
          INCREF_VALUE(r->values[r->len]);
        }
      r->len++;
      if (i->next(i) < 0) return -1;
    }

  return 0;
}

static PyObject *
set_operation(PyObject *s1, PyObject *s2, 
              int w1, int w2,
              int c1, int c12, int c2)
{
  Bucket *r=0;
  SetIteration i1 = {0,0,0}, i2 = {0,0,0};
  int cmp, merge=0;

  if (initSetIteration(&i1, s1, w1, &merge) < 0) return NULL;
  if (initSetIteration(&i2, s2, w2, &merge) < 0) return NULL;

  if (merge)
    {
#ifndef MERGE
      if (c12 && i1.hasValue && i2.hasValue) goto invalid_set_operation;
#endif
      if (! i1.hasValue && i2.hasValue)
        {
          SetIteration t;
          int i;

          t=i1; i1=i2; i2=t;
          i=c1; c1=c2; c2=i;
          i=w1; w1=w2; w2=i;
        }
#ifdef MERGE_DEFAULT
      i1.value=MERGE_DEFAULT;
      i2.value=MERGE_DEFAULT;
#else
      if (i1.hasValue)
        {
          if (! i2.hasValue && c2) goto invalid_set_operation;
        }
      else
        {
          if (c1 || c12) goto invalid_set_operation;
        }
#endif

      UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&BucketType), NULL)))
        goto err;
    }
  else
    {
      UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&SetType), NULL)))
        goto err;
    }

  if (i1.next(&i1) < 0) return NULL;
  if (i2.next(&i2) < 0) return NULL;

  while (i1.position >= 0 && i2.position >= 0)
    {
      cmp=TEST_KEY(i1.key, i2.key);
      if(cmp < 0)
	{
	  if(c1)
	    {
	      if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
              COPY_KEY(r->keys[r->len], i1.key);
              INCREF_KEY(r->keys[r->len]);
              if (merge)
                {
                  COPY_VALUE(r->values[r->len], MERGE_WEIGHT(i1.value, w1));
                  INCREF_VALUE(r->values[r->len]);
                }
	      r->len++;
	    }
          if (i1.next(&i1) < 0) goto err;
	}
      else if(cmp==0)
	{
	  if(c12)
	    {
	      if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
              COPY_KEY(r->keys[r->len], i1.key);
              INCREF_KEY(r->keys[r->len]);
              if (merge)
                {
#ifdef MERGE
                  r->values[r->len] = MERGE(i1.value, w1, i2.value, w2);
#else
                  COPY_VALUE(r->values[r->len], i1.value);
                  INCREF_VALUE(r->values[r->len]);
#endif                    
                }
	      r->len++;
	    }
          if (i1.next(&i1) < 0) goto err;
          if (i2.next(&i2) < 0) goto err;
	}
      else
	{
	  if(c2)
	    {
	      if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
              COPY_KEY(r->keys[r->len], i2.key);
              INCREF_KEY(r->keys[r->len]);
              if (merge)
                {
                  COPY_VALUE(r->values[r->len], MERGE_WEIGHT(i2.value, w2));
                  INCREF_VALUE(r->values[r->len]);
                }
	      r->len++;
	    }
          if (i2.next(&i2) < 0) goto err;
	}
    }
  if(c1 && copyRemaining(r, &i1, merge, w1) < 0) goto err;
  if(c2 && copyRemaining(r, &i2, merge, w2) < 0) goto err;

  Py_DECREF(i1.set);
  Py_DECREF(i2.set);

  return OBJECT(r);

invalid_set_operation:
  PyErr_SetString(PyExc_TypeError, "invalid set operation");
err:
  Py_XDECREF(i1.set);
  Py_XDECREF(i2.set);
  Py_XDECREF(r);
  return NULL;
}

static PyObject *
difference_m(PyObject *ignored, PyObject *args)
{
  PyObject *o1, *o2;

  UNLESS(PyArg_ParseTuple(args, "OO", &o1, &o2)) return NULL;


  if (o1==Py_None || o2==Py_None) 
    {
      Py_INCREF(o1);
      return Py_None;
    }
  
  return set_operation(o1, o2, 1, -1, 1, 0, 0);
}         

static PyObject *
union_m(PyObject *ignored, PyObject *args)
{
  PyObject *o1, *o2;

  UNLESS(PyArg_ParseTuple(args, "OO", &o1, &o2)) return NULL;

  if (o1==Py_None)
    {
      Py_INCREF(o2);
      return o2;
    }
  else if (o2==Py_None)
    {
      Py_INCREF(o1);
      return o1;
    }
  
  return set_operation(o1, o2, -1, -1, 1, 1, 1);
}         

static PyObject *
intersection_m(PyObject *ignored, PyObject *args)
{
  PyObject *o1, *o2;

  UNLESS(PyArg_ParseTuple(args, "OO", &o1, &o2)) return NULL;

  if (o1==Py_None)
    {
      Py_INCREF(o2);
      return o2;
    }
  else if (o2==Py_None)
    {
      Py_INCREF(o1);
      return o1;
    }
  
  return set_operation(o1, o2, -1, -1, 0, 1, 0);
}         

#ifdef MERGE

static PyObject *
wunion_m(PyObject *ignored, PyObject *args)
{
  PyObject *o1, *o2;
  int w1=1, w2=1;

  UNLESS(PyArg_ParseTuple(args, "OO|ii", &o1, &o2, &w1, &w2)) return NULL;

  if (o1==Py_None)
    return Py_BuildValue("iO", (o2==Py_None ? 0 : w2), o2);
  else if (o2==Py_None)
    return Py_BuildValue("iO", w1, o1);
  
  o1=set_operation(o1, o2, w1, w2, 1, 1, 1);
  if (o1) ASSIGN(o1, Py_BuildValue("iO", 1, o1));

  return o1;
}         

static PyObject *
wintersection_m(PyObject *ignored, PyObject *args)
{
  PyObject *o1, *o2;
  int w1=1, w2=1;

  UNLESS(PyArg_ParseTuple(args, "OO|ii", &o1, &o2, &w1, &w2)) return NULL;

  if (o1==Py_None)
    return Py_BuildValue("iO", (o2==Py_None ? 0 : w2), o2);
  else if (o2==Py_None)
    return Py_BuildValue("iO", w1, o1);
  
  o1=set_operation(o1, o2, w1, w2, 0, 1, 0);
  if (o1) 
    ASSIGN(o1, Py_BuildValue("iO", 
            ((o1->ob_type == (PyTypeObject*)(&SetType)) ? w2+w1 : 1),
                             o1));

  return o1;
}         

#endif

--- Added File SetTemplate.c in package Zope2 ---
/*****************************************************************************
  
  Zope Public License (ZPL) Version 1.0
  -------------------------------------
  
  Copyright (c) Digital Creations.  All rights reserved.
  
  This license has been certified as Open Source(tm).
  
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met:
  
  1. Redistributions in source code must retain the above copyright
     notice, this list of conditions, and the following disclaimer.
  
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions, and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
  
  3. Digital Creations requests that attribution be given to Zope
     in any manner possible. Zope includes a "Powered by Zope"
     button that is installed by default. While it is not a license
     violation to remove this button, it is requested that the
     attribution remain. A significant investment has been put
     into Zope, and this effort will continue if the Zope community
     continues to grow. This is one way to assure that growth.
  
  4. All advertising materials and documentation mentioning
     features derived from or use of this software must display
     the following acknowledgement:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     In the event that the product being advertised includes an
     intact Zope distribution (with copyright and license included)
     then this clause is waived.
  
  5. Names associated with Zope or Digital Creations must not be used to
     endorse or promote products derived from this software without
     prior written permission from Digital Creations.
  
  6. Modified redistributions of any form whatsoever must retain
     the following acknowledgment:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     Intact (re-)distributions of any official Zope release do not
     require an external acknowledgement.
  
  7. Modifications are encouraged but must be packaged separately as
     patches to official Zope releases.  Distributions that do not
     clearly separate the patches from the original work must be clearly
     labeled as unofficial distributions.  Modifications which do not
     carry the name Zope may be packaged in any form, as long as they
     conform to all of the clauses above.
  
  
  Disclaimer
  
    THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
    EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
  
  
  This software consists of contributions made by Digital Creations and
  many individuals on behalf of Digital Creations.  Specific
  attributions are listed in the accompanying credits file.
  
 ****************************************************************************/

static PyObject *
Set_insert(Bucket *self, PyObject *args)
{
  PyObject *key;
  int i;

  UNLESS (PyArg_ParseTuple(args, "O", &key)) return NULL;
  if ( (i=_bucket_set(self, key, Py_None, 1, 1, 0)) < 0) return NULL;
  return PyInt_FromLong(i);
}

static PyObject *
Set_update(Bucket *self, PyObject *args)
{
  PyObject *seq=0, *o, *t, *v, *tb;
  int i, n=0, ind;

  UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;

  if (seq)
    {
      for (i=0; ; i++)
        {
          UNLESS (o=PySequence_GetItem(seq, i))
            {
              PyErr_Fetch(&t, &v, &tb);
              if (t != PyExc_IndexError)
                {
                  PyErr_Restore(t, v, tb);
                  return NULL;
                }
              Py_XDECREF(t);
              Py_XDECREF(v);
              Py_XDECREF(tb);
              break;
            }
          ind=_bucket_set(self, o, Py_None, 1, 1, 0);
          Py_DECREF(o);
          if (ind < 0) return NULL;
          n += ind;
        }
    }

  return PyInt_FromLong(n);
}

static PyObject *
Set_remove(Bucket *self, PyObject *args)
{
  PyObject *key;

  UNLESS (PyArg_ParseTuple(args, "O", &key)) return NULL;
  if (_bucket_set(self, key, NULL, 0, 1, 0) < 0) return NULL;

  Py_INCREF(Py_None);
  return Py_None;
}

static int
_set_setstate(Bucket *self, PyObject *args)
{
  PyObject *k, *items;
  Bucket *next=0;
  int i, l, copied=1;
  KEY_TYPE *keys;
  VALUE_TYPE *values;

  UNLESS (PyArg_ParseTuple(args, "O|O", &items, &next))
    return -1;

  if ((l=PyTuple_Size(items)) < 0) return -1;

  for (i=self->len; --i >= 0; )
    {
      DECREF_KEY(self->keys[i]);
    }
  self->len=0;

  if (self->next)
    {
      Py_DECREF(self->next);
      self->next=0;
    }
  
  if (l > self->size)
    {
      UNLESS (keys=PyRealloc(self->keys, sizeof(KEY_TYPE)*l)) return -1;
      self->keys=keys;
      self->size=l;
    }
  
  for (i=0; i<l; i++)
    {
      k=PyTuple_GET_ITEM(items, i);
      COPY_KEY_FROM_ARG(self->keys[i], k, &copied);
      UNLESS (copied) return -1;
      INCREF_KEY(self->keys[i]);
    }

  self->len=l;

  if (next)
    {
      self->next=next;
      Py_INCREF(next);
    }

  return 0;
}

static PyObject *
set_setstate(Bucket *self, PyObject *args)
{
  int r;

  UNLESS (PyArg_ParseTuple(args, "O", &args)) return NULL;

  PER_PREVENT_DEACTIVATION(self); 
  r=_set_setstate(self, args);
  PER_ALLOW_DEACTIVATION(self);

  if (r < 0) return NULL;
  Py_INCREF(Py_None);
  return Py_None;
}

static struct PyMethodDef Set_methods[] = {
  {"__getstate__", (PyCFunction) bucket_getstate,	METH_VARARGS,
   "__getstate__() -- Return the picklable state of the object"},
  {"__setstate__", (PyCFunction) set_setstate,	METH_VARARGS,
   "__setstate__() -- Set the state of the object"},
  {"keys",	(PyCFunction) bucket_keys,	METH_VARARGS,
     "keys() -- Return the keys"},
  {"has_key",	(PyCFunction) bucket_has_key,	METH_VARARGS,
     "has_key(key) -- Test whether the bucket contains the given key"},
  {"clear",	(PyCFunction) bucket_clear,	METH_VARARGS,
   "clear() -- Remove all of the items from the bucket"},
  {"maxKey", (PyCFunction) Bucket_maxKey,	METH_VARARGS,
   "maxKey([key]) -- Fine the maximum key\n\n"
   "If an argument is given, find the maximum <= the argument"},
  {"minKey", (PyCFunction) Bucket_minKey,	METH_VARARGS,
   "minKey([key]) -- Fine the minimum key\n\n"
   "If an argument is given, find the minimum >= the argument"},
#ifdef PERSISTENT
  {"_p_resolveConflict", (PyCFunction) bucket__p_resolveConflict, METH_VARARGS,
   "_p_resolveConflict() -- Reinitialize from a newly created copy"},
  {"_p_deactivate", (PyCFunction) bucket__p_deactivate, METH_VARARGS,
   "_p_deactivate() -- Reinitialize from a newly created copy"},
#endif
  {"insert",	(PyCFunction)Set_insert,	METH_VARARGS,
   "insert(id,[ignored]) -- Add a key to the set"},
  {"update",	(PyCFunction)Set_update,	METH_VARARGS,
   "update(seq) -- Add the items from the given sequence to the set"},
  {"__init__",	(PyCFunction)Set_update,	METH_VARARGS,
   "__init__(seq) -- Initialize with  the items from the given sequence"},
  {"remove",	(PyCFunction)Set_remove,	METH_VARARGS,
   "remove(id) -- Remove an id from the set"},

  {NULL,		NULL}		/* sentinel */
};

static PyObject *
set_repr(Bucket *self)
{
  static PyObject *format;
  PyObject *r, *t;

  UNLESS (format) UNLESS (format=PyString_FromString(PREFIX "Set(%s)")) 
    return NULL;
  UNLESS (t=PyTuple_New(1)) return NULL;
  UNLESS (r=bucket_keys(self,NULL)) goto err;
  PyTuple_SET_ITEM(t,0,r);
  r=t;
  ASSIGN(r,PyString_Format(format,r));
  return r;
err:
  Py_DECREF(t);
  return NULL;
}

static int
set_length(Bucket *self) 
{
  int r;

  PER_USE_OR_RETURN(self, -1);
  r = self->len;
  PER_ALLOW_DEACTIVATION(self);

  return r;
}

static PyObject *
set_item(Bucket *self, int index)
{
  PyObject *r=0;

  PER_USE_OR_RETURN(self, NULL);
  if (index >= 0 && index < self->len)
    {
      COPY_KEY_TO_OBJECT(r, self->keys[index]);
    }
  else
    IndexError(index);

  PER_ALLOW_DEACTIVATION(self);

  return r;
}

static PySequenceMethods set_as_sequence = {
	(inquiry)set_length,		/*sq_length*/
	(binaryfunc)0,		/*sq_concat*/
	(intargfunc)0,		/*sq_repeat*/
	(intargfunc)set_item,		/*sq_item*/
	(intintargfunc)0,		/*sq_slice*/
	(intobjargproc)0,	/*sq_ass_item*/
	(intintobjargproc)0,	/*sq_ass_slice*/
};

static PyExtensionClass SetType = {
  PyObject_HEAD_INIT(NULL)
  0,				/*ob_size*/
  PREFIX "Set",			/*tp_name*/
  sizeof(Bucket),		/*tp_basicsize*/
  0,				/*tp_itemsize*/
  /*********** methods ***********************/
  (destructor) Bucket_dealloc,	/*tp_dealloc*/
  (printfunc)0,			/*tp_print*/
  (getattrfunc)0,		/*obsolete tp_getattr*/
  (setattrfunc)0,		/*obsolete tp_setattr*/
  (cmpfunc)0,			/*tp_compare*/
  (reprfunc) set_repr,		/*tp_repr*/
  0,				/*tp_as_number*/
  &set_as_sequence,		/*tp_as_sequence*/
  0,		                /*tp_as_mapping*/
  (hashfunc)0,			/*tp_hash*/
  (ternaryfunc)0,		/*tp_call*/
  (reprfunc)0,			/*tp_str*/
  (getattrofunc)0,		/*tp_getattro*/
  0,				/*tp_setattro*/
  
  /* Space for future expansion */
  0L,0L,
  "Set implemented as sorted keys", 
  METHOD_CHAIN(Set_methods),
  EXTENSIONCLASS_BASICNEW_FLAG 
#ifdef PERSISTENT
  | PERSISTENT_TYPE_FLAG 
#endif
  | EXTENSIONCLASS_NOINSTDICT_FLAG,
};

static int 
nextSet(SetIteration *i)
{
  UNLESS(PER_USE(BUCKET(i->set))) return -1;
          
  if (i->position >= 0)
    {
      if (i->position)
        {
          DECREF_KEY(i->key);
        }

      if (i->position < BUCKET(i->set)->len)
        {
          COPY_KEY(i->key, BUCKET(i->set)->keys[i->position]);
          INCREF_KEY(i->key);
          i->position ++;
        }
      else
        i->position = -1;
    }

  PER_ALLOW_DEACTIVATION(BUCKET(i->set));
          
  return 0;
}

--- Added File Setup in package Zope2 ---
*shared*
OOBTree OOBTree.c  -I../../Components/ExtensionClass/src -I../ZODB
OIBTree OIBTree.c  -I../../Components/ExtensionClass/src -I../ZODB
IIBTree IIBTree.c  -I../../Components/ExtensionClass/src -I../ZODB -I../../Components
IOBTree IOBTree.c  -I../../Components/ExtensionClass/src -I../ZODB -I../../Components

--- Added File TreeSetTemplate.c in package Zope2 ---
/*****************************************************************************
  
  Zope Public License (ZPL) Version 1.0
  -------------------------------------
  
  Copyright (c) Digital Creations.  All rights reserved.
  
  This license has been certified as Open Source(tm).
  
  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met:
  
  1. Redistributions in source code must retain the above copyright
     notice, this list of conditions, and the following disclaimer.
  
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions, and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution.
  
  3. Digital Creations requests that attribution be given to Zope
     in any manner possible. Zope includes a "Powered by Zope"
     button that is installed by default. While it is not a license
     violation to remove this button, it is requested that the
     attribution remain. A significant investment has been put
     into Zope, and this effort will continue if the Zope community
     continues to grow. This is one way to assure that growth.
  
  4. All advertising materials and documentation mentioning
     features derived from or use of this software must display
     the following acknowledgement:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     In the event that the product being advertised includes an
     intact Zope distribution (with copyright and license included)
     then this clause is waived.
  
  5. Names associated with Zope or Digital Creations must not be used to
     endorse or promote products derived from this software without
     prior written permission from Digital Creations.
  
  6. Modified redistributions of any form whatsoever must retain
     the following acknowledgment:
  
       "This product includes software developed by Digital Creations
       for use in the Z Object Publishing Environment
       (http://www.zope.org/)."
  
     Intact (re-)distributions of any official Zope release do not
     require an external acknowledgement.
  
  7. Modifications are encouraged but must be packaged separately as
     patches to official Zope releases.  Distributions that do not
     clearly separate the patches from the original work must be clearly
     labeled as unofficial distributions.  Modifications which do not
     carry the name Zope may be packaged in any form, as long as they
     conform to all of the clauses above.
  
  
  Disclaimer
  
    THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
    EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
    ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    SUCH DAMAGE.
  
  
  This software consists of contributions made by Digital Creations and
  many individuals on behalf of Digital Creations.  Specific
  attributions are listed in the accompanying credits file.
  
 ****************************************************************************/

static PyObject *
TreeSet_insert(BTree *self, PyObject *args)
{
  PyObject *key;
  int i;

  UNLESS (PyArg_ParseTuple(args, "O", &key)) return NULL;
  if ((i=_BTree_set(self, key, Py_None, 1, 1)) < 0) return NULL;
  return PyInt_FromLong(i);
}

static PyObject *
TreeSet_update(BTree *self, PyObject *args)
{
  PyObject *seq=0, *o, *t, *v, *tb;
  int i, n=0, ind;

  UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;

  if (seq)
    {
      for (i=0; ; i++)
        {
          UNLESS (o=PySequence_GetItem(seq, i))
            {
              PyErr_Fetch(&t, &v, &tb);
              if (t != PyExc_IndexError)
                {
                  PyErr_Restore(t, v, tb);
                  return NULL;
                }
              Py_XDECREF(t);
              Py_XDECREF(v);
              Py_XDECREF(tb);
              break;
            }
          ind=_BTree_set(self, o, Py_None, 1, 1);
          Py_DECREF(o);
          if (ind < 0) return NULL;
          n += ind;
        }
    }

  return PyInt_FromLong(n);
}


static PyObject *
TreeSet_remove(BTree *self, PyObject *args)
{
  PyObject *key;

  UNLESS (PyArg_ParseTuple(args, "O", &key)) return NULL;
  if (_BTree_set(self, key, NULL, 0, 1) < 0) return NULL;
  Py_INCREF(Py_None);
  return Py_None;
}

static PyObject *
TreeSet_setstate(BTree *self, PyObject *args)
{
  int r;

  if (!PyArg_ParseTuple(args,"O",&args)) return NULL;
 
  PER_PREVENT_DEACTIVATION(self); 
  r=_BTree_setstate(self, args, 1);
  PER_ALLOW_DEACTIVATION(self);

  if (r < 0) return NULL;
  Py_INCREF(Py_None);
  return Py_None;
}

static struct PyMethodDef TreeSet_methods[] = {
  {"__getstate__", (PyCFunction) BTree_getstate,	METH_VARARGS,
   "__getstate__() -- Return the picklable state of the object"},
  {"__setstate__", (PyCFunction) TreeSet_setstate,	METH_VARARGS,
   "__setstate__() -- Set the state of the object"},
  {"has_key",	(PyCFunction) BTree_has_key,	METH_VARARGS,
     "has_key(key) -- Test whether the bucket contains the given key"},
  {"keys",	(PyCFunction) BTree_keys,	METH_VARARGS,
     "keys() -- Return the keys"},
  {"maxKey", (PyCFunction) BTree_maxKey,	METH_VARARGS,
   "maxKey([key]) -- Fine the maximum key\n\n"
   "If an argument is given, find the maximum <= the argument"},
  {"minKey", (PyCFunction) BTree_minKey,	METH_VARARGS,
   "minKey([key]) -- Fine the minimum key\n\n"
   "If an argument is given, find the minimum >= the argument"},
  {"clear",	(PyCFunction) BTree_clear,	METH_VARARGS,
   "clear() -- Remove all of the items from the BTree"},  
  {"insert",	(PyCFunction)TreeSet_insert,	METH_VARARGS,
   "insert(id,[ignored]) -- Add an id to the set"},
  {"update",	(PyCFunction)TreeSet_update,	METH_VARARGS,
   "update(seq) -- Add the items from the given sequence to the set"},
  {"__init__",	(PyCFunction)TreeSet_update,	METH_VARARGS,
   "__init__(seq) -- Initialize with  the items from the given sequence"},
  {"remove",	(PyCFunction)TreeSet_remove,	METH_VARARGS,
   "remove(id) -- Remove a key from the set"},
#ifdef PERSISTENT
  {"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict, METH_VARARGS,
   "_p_resolveConflict() -- Reinitialize from a newly created copy"},
  {"_p_deactivate", (PyCFunction) BTree__p_deactivate,	METH_VARARGS,
   "_p_deactivate() -- Reinitialize from a newly created copy"},
#endif
  {NULL,		NULL}		/* sentinel */
};

static PyExtensionClass TreeSetType = {
  PyObject_HEAD_INIT(NULL)
  0,				/*ob_size*/
  PREFIX "TreeSet",		/*tp_name*/
  sizeof(BTree),		/*tp_basicsize*/
  0,				/*tp_itemsize*/
  /************* methods ********************/
  (destructor) BTree_dealloc,   /*tp_dealloc*/
  (printfunc)0,			/*tp_print*/
  (getattrfunc)0,		/*obsolete tp_getattr*/
  (setattrfunc)0,		/*obsolete tp_setattr*/
  (cmpfunc)0,			/*tp_compare*/
  (reprfunc)0,			/*tp_repr*/
  &BTree_as_number_for_nonzero,	/*tp_as_number*/
  0,				/*tp_as_sequence*/
  0,				/*tp_as_mapping*/
  (hashfunc)0,			/*tp_hash*/
  (ternaryfunc)0,		/*tp_call*/
  (reprfunc)0,			/*tp_str*/
  (getattrofunc)0,
  0,				/*tp_setattro*/
  
  /* Space for future expansion */
  0L,0L,
  "Set implemented as sorted tree of items", 
  METHOD_CHAIN(TreeSet_methods),
  EXTENSIONCLASS_BASICNEW_FLAG 
#ifdef PERSISTENT
  | PERSISTENT_TYPE_FLAG 
#endif
  | EXTENSIONCLASS_NOINSTDICT_FLAG,
};

--- Added File __init__.py in package Zope2 ---
import ZODB

try: import intSet
except: pass
else: del intSet

--- Added File config.c in package Zope2 ---
/* Generated automatically from /usr/local/python1.5.2/lib/python1.5/config/config.c.in by makesetup. */
/* -*- C -*- ***********************************************
Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
The Netherlands.

                        All Rights Reserved

Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in
supporting documentation, and that the names of Stichting Mathematisch
Centrum or CWI or Corporation for National Research Initiatives or
CNRI not be used in advertising or publicity pertaining to
distribution of the software without specific, written prior
permission.

While CWI is the initial source for this software, a modified version
is made available by the Corporation for National Research Initiatives
(CNRI) at the Internet address ftp://ftp.python.org.

STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.

******************************************************************/

/* Module configuration */

/* !!! !!! !!! This file is edited by the makesetup script !!! !!! !!! */

/* This file contains the table of built-in modules.
   See init_builtin() in import.c. */

#include "Python.h"


extern void initthread();
extern void initregex();
extern void initpcre();
extern void initposix();
extern void initsignal();
extern void initarray();
extern void initcmath();
extern void initmath();
extern void initstrop();
extern void initstruct();
extern void inittime();
extern void initoperator();
extern void initfcntl();
extern void initpwd();
extern void initgrp();
extern void initselect();
extern void initsocket();
extern void initerrno();
extern void initmd5();
extern void initsha();
extern void initrotor();
extern void initnew();
extern void initbinascii();
extern void initparser();
extern void initcStringIO();
extern void initcPickle();

/* -- ADDMODULE MARKER 1 -- */

extern void PyMarshal_Init();
extern void initimp();

struct _inittab _PyImport_Inittab[] = {

	{"thread", initthread},
	{"regex", initregex},
	{"pcre", initpcre},
	{"posix", initposix},
	{"signal", initsignal},
	{"array", initarray},
	{"cmath", initcmath},
	{"math", initmath},
	{"strop", initstrop},
	{"struct", initstruct},
	{"time", inittime},
	{"operator", initoperator},
	{"fcntl", initfcntl},
	{"pwd", initpwd},
	{"grp", initgrp},
	{"select", initselect},
	{"socket", initsocket},
	{"errno", initerrno},
	{"md5", initmd5},
	{"sha", initsha},
	{"rotor", initrotor},
	{"new", initnew},
	{"binascii", initbinascii},
	{"parser", initparser},
	{"cStringIO", initcStringIO},
	{"cPickle", initcPickle},

/* -- ADDMODULE MARKER 2 -- */

	/* This module "lives in" with marshal.c */
	{"marshal", PyMarshal_Init},

	/* This lives it with import.c */
	{"imp", initimp},

	/* These entries are here for sys.builtin_module_names */
	{"__main__", NULL},
	{"__builtin__", NULL},
	{"sys", NULL},

	/* Sentinel */
	{0, 0}
};

--- Added File convert.py in package Zope2 ---
##############################################################################
# 
# Zope Public License (ZPL) Version 1.0
# -------------------------------------
# 
# Copyright (c) Digital Creations.  All rights reserved.
# 
# This license has been certified as Open Source(tm).
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
# 
# 1. Redistributions in source code must retain the above copyright
#    notice, this list of conditions, and the following disclaimer.
# 
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions, and the following disclaimer in
#    the documentation and/or other materials provided with the
#    distribution.
# 
# 3. Digital Creations requests that attribution be given to Zope
#    in any manner possible. Zope includes a "Powered by Zope"
#    button that is installed by default. While it is not a license
#    violation to remove this button, it is requested that the
#    attribution remain. A significant investment has been put
#    into Zope, and this effort will continue if the Zope community
#    continues to grow. This is one way to assure that growth.
# 
# 4. All advertising materials and documentation mentioning
#    features derived from or use of this software must display
#    the following acknowledgement:
# 
#      "This product includes software developed by Digital Creations
#      for use in the Z Object Publishing Environment
#      (http://www.zope.org/)."
# 
#    In the event that the product being advertised includes an
#    intact Zope distribution (with copyright and license included)
#    then this clause is waived.
# 
# 5. Names associated with Zope or Digital Creations must not be used to
#    endorse or promote products derived from this software without
#    prior written permission from Digital Creations.
# 
# 6. Modified redistributions of any form whatsoever must retain
#    the following acknowledgment:
# 
#      "This product includes software developed by Digital Creations
#      for use in the Z Object Publishing Environment
#      (http://www.zope.org/)."
# 
#    Intact (re-)distributions of any official Zope release do not
#    require an external acknowledgement.
# 
# 7. Modifications are encouraged but must be packaged separately as
#    patches to official Zope releases.  Distributions that do not
#    clearly separate the patches from the original work must be clearly
#    labeled as unofficial distributions.  Modifications which do not
#    carry the name Zope may be packaged in any form, as long as they
#    conform to all of the clauses above.
# 
# 
# Disclaimer
# 
#   THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
#   EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
#   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
#   PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
#   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
#   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
#   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
#   USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
#   ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
#   OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
#   OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
#   SUCH DAMAGE.
# 
# 
# This software consists of contributions made by Digital Creations and
# many individuals on behalf of Digital Creations.  Specific
# attributions are listed in the accompanying credits file.
# 
##############################################################################

def convert(old, new, threshold=200, f=None, None=None):
    "Utility for converting old btree new new"
    n=0
    for k, v in old.items():
        if f is not None: v=f(v)
        new[k]=v
        n=n+1
        if n > threshold:
            get_transaction().commit(1)
            old._p_jar.cacheMinimize(3)
            n=0

    get_transaction().commit(1)
    old._p_jar.cacheMinimize(3)

--- Added File intkeymacros.h in package Zope2 ---
#define KEY_TYPE int
#define KEY_CHECK PyInt_Check
#define TEST_KEY(K, T) (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0)) 
#define DECREF_KEY(KEY)
#define INCREF_KEY(k)
#define COPY_KEY(KEY, E) (KEY=(E))
#define COPY_KEY_TO_OBJECT(O, K) O=PyInt_FromLong(K)
#define COPY_KEY_FROM_ARG(TARGET, ARG, STATUS) \
  if (PyInt_Check(ARG)) TARGET=PyInt_AsLong(ARG); else { \
      PyErr_SetString(PyExc_TypeError, "expected integer key"); \
      *(STATUS)=0; } 

--- Added File intvaluemacros.h in package Zope2 ---
#define VALUE_TYPE int
#define TEST_VALUE(K, T) (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0)) 
#define VALUE_SAME(VALUE, TARGET) ( (VALUE) == (TARGET) )
#define DECLARE_VALUE(NAME) VALUE_TYPE NAME
#define VALUE_PARSE "i"
#define DECREF_VALUE(k)
#define INCREF_VALUE(k)
#define COPY_VALUE(V, E) (V=(E))
#define COPY_VALUE_TO_OBJECT(O, K) O=PyInt_FromLong(K) 
#define COPY_VALUE_FROM_ARG(TARGET, ARG, STATUS) \
  if (PyInt_Check(ARG)) TARGET=PyInt_AsLong(ARG); else { \
      PyErr_SetString(PyExc_TypeError, "expected integer value"); \
      *(STATUS)=0; } 
  
#define NORMALIZE_VALUE(V, MIN) ((MIN) > 0) ? ((V)/=(MIN)) : 0

#define MERGE_DEFAULT 1
#define MERGE(O1, w1, O2, w2) ((O1)*(w1)+(O2)*(w2))
#define MERGE_WEIGHT(O, w) ((O)*(w))

--- Added File objectkeymacros.h in package Zope2 ---
#define KEY_TYPE PyObject *
#define TEST_KEY(KEY, TARGET) PyObject_Compare((KEY),(TARGET))
#define INCREF_KEY(k) Py_INCREF(k)
#define DECREF_KEY(KEY) Py_DECREF(KEY)
#define COPY_KEY(KEY, E) KEY=(E)
#define COPY_KEY_TO_OBJECT(O, K) O=(K); Py_INCREF(O)
#define COPY_KEY_FROM_ARG(TARGET, ARG, S) TARGET=(ARG)

--- Added File objectvaluemacros.h in package Zope2 ---
#define VALUE_TYPE PyObject *
#define TEST_VALUE(VALUE, TARGET) PyObject_Compare((VALUE),(TARGET))
#define DECLARE_VALUE(NAME) VALUE_TYPE NAME
#define INCREF_VALUE(k) Py_INCREF(k)
#define DECREF_VALUE(k) Py_DECREF(k)
#define COPY_VALUE(k,e) k=(e)
#define COPY_VALUE_TO_OBJECT(O, K) O=(K); Py_INCREF(O)
#define COPY_VALUE_FROM_ARG(TARGET, ARG, S) TARGET=(ARG)
#define NORMALIZE_VALUE(V, MIN) Py_INCREF(V)