[Zope-Checkins] CVS: Zope3/lib/python/Persistence/BTrees - .cvsignore:1.2 BTreeItemsTemplate.c:1.2 BTreeModuleTemplate.c:1.2 BTreeTemplate.c:1.2 BucketTemplate.c:1.2 Exception.py:1.2 IIBTree.py:1.2 IOBTree.py:1.2 Interfaces.py:1.2 Length.py:1.2 Maintainer.txt:1.2 MergeTemplate.c:1.2 OIBTree.py:1.2 OOBTree.py:1.2 SetOpTemplate.c:1.2 SetTemplate.c:1.2 TreeSetTemplate.c:1.2 _IIBTree.c:1.2 _IOBTree.c:1.2 _OIBTree.c:1.2 _OOBTree.c:1.2 __init__.py:1.2 _fsBTree.c:1.2 convert.py:1.2 intkeymacros.h:1.2 intvaluemacros.h:1.2 objectkeymacros.h:1.2 objectvaluemacros.h:1.2 sorters.c:1.2

Jim Fulton jim@zope.com
Mon, 10 Jun 2002 19:28:45 -0400


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

Added Files:
	.cvsignore BTreeItemsTemplate.c BTreeModuleTemplate.c 
	BTreeTemplate.c BucketTemplate.c Exception.py IIBTree.py 
	IOBTree.py Interfaces.py Length.py Maintainer.txt 
	MergeTemplate.c OIBTree.py OOBTree.py SetOpTemplate.c 
	SetTemplate.c TreeSetTemplate.c _IIBTree.c _IOBTree.c 
	_OIBTree.c _OOBTree.c __init__.py _fsBTree.c convert.py 
	intkeymacros.h intvaluemacros.h objectkeymacros.h 
	objectvaluemacros.h sorters.c 
Log Message:
Merged Zope-3x-branch into newly forked Zope3 CVS Tree.


=== Zope3/lib/python/Persistence/BTrees/.cvsignore 1.1 => 1.2 ===
+Makefile
+Makefile.pre
+Makefile.pre.in
+config.c


=== Zope3/lib/python/Persistence/BTrees/BTreeItemsTemplate.c 1.1 => 1.2 === (511/611 lines abridged)
+
+  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define BTREEITEMSTEMPLATE_C "$Id$\n"
+
+/* A BTreeItems struct is returned from calling .items(), .keys() or
+ * .values() on a BTree-based data structure, and is also the result of
+ * taking slices of those.  It represents a contiguous slice of a BTree.
+ *
+ * The start of the slice is in firstbucket, at offset first.  The end of
+ * the slice is in lastbucket, at offset last.  Both endpoints are inclusive.
+ * It should be possible to get from firstbucket to lastbucket via following
+ * bucket 'next' pointers zero or more times.  firstbucket, first, lastbucket,
+ * and last are readonly after initialization.  An empty slice is represented
+ * by [XXX (firstbucket == NULL) or (firstbucket == lastbucket and
+ * first > last) XXX].
+ *
+ * 'kind' determines whether this slice represents 'k'eys alone, 'v'alues
+ * alone, or 'i'items (key+value pairs).  'kind' is also readonly after
+ * initialization.
+ *
+ * [XXX currentoffset and currentbucket appear to be used to return function
+ *  results XXX]
+ *
+ * [XXX pseudoindex may be the index corresponding to the position identified
+ *  by the currentbucket+currenoffset pair.  Seems to be a kind of search
+ *  finger. XXX]
+ */
+typedef struct {
+  PyObject_HEAD
+  Bucket *firstbucket;		/* First bucket		        */
+  Bucket *currentbucket;	/* Current bucket	        */
+  Bucket *lastbucket;		/* Last bucket		        */
+  int currentoffset;		/* Offset in currentbucket      */
+  int pseudoindex;		/* It's an indicator (what?)    */
+  int first;                    /* Start offset in firstbucket  */
+  int last;                     /* End offset in lastbucket     */
+  char kind;                    /* 'k', 'v', 'i'                */
+} BTreeItems;
+

[-=- -=- -=- 511 lines omitted -=- -=- -=-]

+          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))
+            {
+              /* Mark iteration terminated, so that finiSetIteration doesn't
+               * try to redundantly decref the key and value
+               */
+              i->position = -1;
+              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;
+}


=== Zope3/lib/python/Persistence/BTrees/BTreeModuleTemplate.c 1.1 => 1.2 === (428/528 lines abridged)
+
+  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#include "Python.h"
+/* include structmember.h for offsetof */
+#include "structmember.h"
+
+#ifdef PERSISTENT
+#include "cPersistence.h"
+#include "cPersistenceAPI.h"
+#else
+#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_ACCESSED(O) 1
+#define PER_CHANGED(O) 0
+#endif
+
+/*
+  The tp_name slots of the various BTree types contain the fully
+  qualified names of the types, e.g. Persistence.BTrees.OOBTree.OOBTree.
+  The full name is usd to support pickling and because it is not
+  possible to modify the __module__ slot of a type dynamically.  (This
+  may be a bug in Python 2.2).
+*/
+
+#define MODULE_NAME "Persistence.BTrees." MOD_NAME_PREFIX "BTree."
+
+static PyObject *sort_str, *reverse_str, *__setstate___str;
+static PyObject *ConflictError = NULL;
+
+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))

[-=- -=- -=- 428 lines omitted -=- -=- -=-]

+  m = PyImport_ImportModule("Persistence.BTrees.Exception");
+  if (m != NULL) {
+  	c = PyObject_GetAttrString(m, "BTreesConflictError");
+  	if (c != NULL)
+  		ConflictError = c;
+	Py_DECREF(m);
+  }
+
+  if (ConflictError == NULL) {
+  	Py_INCREF(PyExc_ValueError);
+	ConflictError=PyExc_ValueError;
+  }
+
+#ifdef INTSET_H
+  UNLESS(d = PyImport_ImportModule("intSet")) return;
+  UNLESS(intSetType = PyObject_GetAttrString (d, "intSet")) return;
+  Py_DECREF (d);
+#endif
+
+  /* Initialize the PyPersist_C_API and the type objects. */
+  PyPersist_C_API = PyCObject_Import("Persistence.cPersistence", "C_API");
+  if (PyPersist_C_API == NULL)
+      return;
+
+  BTreeItemsType.ob_type = &PyType_Type;
+  init_persist_type(&BucketType);
+  init_persist_type(&BTreeType);
+  init_persist_type(&SetType);
+  init_persist_type(&TreeSetType);
+
+  /* Create the module and add the functions */
+  m = Py_InitModule4("_" MOD_NAME_PREFIX "BTree",
+		     module_methods, BTree_module_documentation,
+		     (PyObject *)NULL, PYTHON_API_VERSION);
+
+  /* Add some symbolic constants to the module */
+  d = PyModule_GetDict(m);
+  if (PyDict_SetItemString(d, MOD_NAME_PREFIX "Bucket",
+			   (PyObject *)&BucketType) < 0)
+      return;
+  if (PyDict_SetItemString(d, MOD_NAME_PREFIX "BTree",
+			   (PyObject *)&BTreeType) < 0)
+      return;
+  if (PyDict_SetItemString(d, MOD_NAME_PREFIX "Set",
+			   (PyObject *)&SetType) < 0)
+      return;
+  if (PyDict_SetItemString(d, MOD_NAME_PREFIX "TreeSet",
+			   (PyObject *)&TreeSetType) < 0)
+      return;
+}


=== Zope3/lib/python/Persistence/BTrees/BTreeTemplate.c 1.1 => 1.2 === (1343/1443 lines abridged)
+
+  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define BTREETEMPLATE_C "$Id$\n"
+
+/*
+** _BTree_get
+**
+** Search a BTree.
+**
+** Arguments
+**      self        a pointer to a BTree
+**      keyarg      the key to search for, as a Python object
+**      has_key     true/false; when false, try to return the associated
+**                  value; when true, return a boolean
+** Return
+**      When has_key false:
+**          If key exists, its associated value.
+**          If key doesn't exist, NULL and KeyError is set.
+**      When has_key true:
+**          A Python int is returned in any case.
+**          If key exists, the depth of the bucket in which it was found.
+**          If key doesn't exist, 0.
+*/
+static PyObject *
+_BTree_get(BTree *self, PyObject *keyarg, int has_key)
+{
+  KEY_TYPE key;
+  int min;              /* index of child to search */
+  PyObject *r = NULL;   /* result object */
+  int copied = 1;
+
+  COPY_KEY_FROM_ARG(key, keyarg, copied);
+  UNLESS (copied) return NULL;
+
+  PyPersist_INCREF(self);
+  if (!PyPersist_IS_STICKY(self))
+      return NULL;
+
+  BTREE_SEARCH(min, self, key, goto Error);

[-=- -=- -=- 1343 lines omitted -=- -=- -=-]

+{
+  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 PyTypeObject BTreeType = {
+    PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+    0,					/* ob_size */
+    MODULE_NAME MOD_NAME_PREFIX "BTree",/* tp_name */
+    sizeof(BTree),			/* tp_basicsize */
+    0,					/* tp_itemsize */
+    (destructor)BTree_dealloc,		/* tp_dealloc */
+    0,					/* tp_print */
+    0,					/* tp_getattr */
+    0,					/* tp_setattr */
+    0,					/* tp_compare */
+    0,					/* tp_repr */
+    &BTree_as_number_for_nonzero,	/* tp_as_number */
+    0,					/* tp_as_sequence */
+    &BTree_as_mapping,			/* tp_as_mapping */
+    0,					/* tp_hash */
+    0,					/* tp_call */
+    0,					/* tp_str */
+    0,					/* tp_getattro */
+    0,					/* tp_setattro */
+    0,					/* tp_as_buffer */
+    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+	    Py_TPFLAGS_BASETYPE, 	/* tp_flags */
+    0,					/* tp_doc */
+    (traverseproc)BTree_traverse,	/* tp_traverse */
+    (inquiry)BTree_tp_clear,		/* tp_clear */
+    0,					/* tp_richcompare */
+    offsetof(BTree, po_weaklist),	/* tp_weaklistoffset */
+    0,					/* tp_iter */
+    0,					/* tp_iternext */
+    BTree_methods,			/* tp_methods */
+    0,					/* tp_members */
+    0,					/* tp_getset */
+    0,					/* tp_base */
+    0,					/* tp_dict */
+    0,					/* tp_descr_get */
+    0,					/* tp_descr_set */
+    0,					/* tp_dictoffset */
+    BTree_init,				/* tp_init */
+    0,					/* tp_alloc */
+    PyType_GenericNew,			/* tp_new */
+};


=== Zope3/lib/python/Persistence/BTrees/BucketTemplate.c 1.1 => 1.2 === (1310/1410 lines abridged)
+
+  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define BUCKETTEMPLATE_C "$Id$\n"
+
+/* Use BUCKET_SEARCH to find the index at which a key belongs.
+ * INDEX    An int lvalue to hold the index i such that KEY belongs at
+ *          SELF->keys[i].  Note that this will equal SELF->len if KEY
+ *          is larger than the bucket's largest key.  Else it's the
+ *          smallest i such that SELF->keys[i] >= KEY.
+ * ABSENT   An int lvalue to hold a Boolean result, true (!= 0) if the
+ *          key is absent, false (== 0) if the key is at INDEX.
+ * SELF     A pointer to a Bucket node.
+ * KEY      The key you're looking for, of type KEY_TYPE.
+ * ONERROR  What to do if key comparison raises an exception; for example,
+ *          perhaps 'return NULL'.
+ *
+ * See Maintainer.txt for discussion:  this is optimized in subtle ways.
+ * It's recommended that you call this at the start of a routine, waiting
+ * to check for self->len == 0 after (if an empty bucket is special in
+ * context; INDEX becomes 0 and ABSENT becomes true if this macro is run
+ * with an empty SELF, and that may be all the invoker needs to know).
+ */
+#define BUCKET_SEARCH(INDEX, ABSENT, SELF, KEY, ONERROR) {  \
+    int _lo = 0;                                            \
+    int _hi = (SELF)->len;                                  \
+    int _i;                                                 \
+    int _cmp = 1;                                           \
+    for (_i = _hi >> 1; _lo < _hi; _i = (_lo + _hi) >> 1) { \
+        TEST_KEY_SET_OR(_cmp, (SELF)->keys[_i], (KEY))      \
+            ONERROR;                                        \
+        if      (_cmp < 0)  _lo = _i + 1;                   \
+        else if (_cmp == 0) break;                          \
+        else                _hi = _i;                       \
+    }                                                       \
+    (INDEX) = _i;                                           \
+    (ABSENT) = _cmp;                                        \
+}
+
+/*

[-=- -=- -=- 1310 lines omitted -=- -=- -=-]

+    0,					/* tp_richcompare */
+    offsetof(Bucket, po_weaklist),	/* tp_weaklistoffset */
+    0,					/* tp_iter */
+    0,					/* tp_iternext */
+    Bucket_methods,			/* tp_methods */
+    0,					/* tp_members */
+    0,					/* tp_getset */
+    0,					/* tp_base */
+    0,					/* tp_dict */
+    0,					/* tp_descr_get */
+    0,					/* tp_descr_set */
+    0,					/* tp_dictoffset */
+    Bucket_init,			/* tp_init */
+    0,					/* tp_alloc */
+    PyType_GenericNew,			/* tp_new */
+};
+
+static int
+nextBucket(SetIteration *i)
+{
+  if (i->position >= 0)
+    {
+      UNLESS(PER_USE(BUCKET(i->set))) return -1;
+
+      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;
+          PyPersist_SetATime(BUCKET(i->set));
+        }
+
+      PyPersist_DECREF(BUCKET(i->set));
+    }
+
+
+  return 0;
+}


=== Zope3/lib/python/Persistence/BTrees/Exception.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+from Transaction.Exceptions import ConflictError
+
+class BTreesConflictError(ConflictError):
+
+    msgs = ['',
+            'Conflicting changes', # in i2 & i3
+            'Conflicting del and change', # in i3 & i2
+            'Conflicting del and change', # in i2 & i3
+            'Conflicting inserts or deletes',
+            'Conflicting deletes',
+            'Conflicting inserts',
+            'Conflicting deletes or delete and change',
+            'Conflicting deletes or delete and change',
+            ]
+
+    def __init__(self, p1, p2, p3, reason):
+        self.p1 = p1
+        self.p2 = p2
+        self.p3 = p3
+        self.reason = reason
+
+    def __repr__(self):
+        return "BTreesConflictError(%d, %d, %d, %d)" % (self.p1,
+                                                        self.p2,
+                                                        self.p3,
+                                                        self.reason)
+    def __str__(self):
+        return "BTrees conflict error at %d/%d/%d: %s" % (
+            self.p1, self.p2, self.p3, self.msgs[self.reason])
+    


=== Zope3/lib/python/Persistence/BTrees/IIBTree.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+from _IIBTree import *


=== Zope3/lib/python/Persistence/BTrees/IOBTree.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+from _IOBTree import *


=== Zope3/lib/python/Persistence/BTrees/Interfaces.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+import OOBTree, Interface, Interface.Standard
+
+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 IReadSequence(Interface.Standard.Sequence):
+
+    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, Interface.Standard.Sized):
+
+    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, Interface.Standard.MinimalDictionary):
+
+    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(Interface.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.
+#
+################################################################
+
+OOBTree.OOSet.__implements__=ISet
+OOBTree.OOTreeSet.__implements__=ITreeSet
+OOBTree.OOBucket.__implements__=IDictionaryIsh
+OOBTree.OOBTree.__implements__=IBTree


=== Zope3/lib/python/Persistence/BTrees/Length.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+import Persistence
+
+class Length(Persistence.Persistent):
+    """BTree lengths are 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


=== Zope3/lib/python/Persistence/BTrees/Maintainer.txt 1.1 => 1.2 ===
+extend BTrees.
+
+Macros
+======
+BTrees are defined using a "template", roughly akin to a a C++
+template.  To create a new family of BTrees, create a source file that
+defines macros used to handle differences in key and value types:
+
+
+Configuration Macros
+
+MASTER_ID
+A string to hold an RCS/CVS Id key to be included in compiled binaries.
+
+MOD_NAME_PREFIX
+A string (like "IO" or "OO") that provides the prefix used for the
+module.  This gets used to generate type names and the internal module
+name string.
+
+DEFAULT_MAX_BUCKET_SIZE
+An int giving the maximum bucket size (number of key/value pairs).
+When a bucket gets larger than this due to an insertion *into a BTREE*,
+it splits.  Inserting into a bucket directly doesn't split, and
+functions that produce a bucket output (e.g., union()) also have no
+bound on how large a bucket may get.  Someday this will be tunable
+on BTree instances.
+
+DEFAULT_MAX_BTREE_SIZE
+An int giving the maximum size (number of children) of an internal
+btree node.  Someday this will be tunable on BTree instances.
+
+
+Macros for Keys
+
+KEY_TYPE
+The C type declaration for keys (e.g., int or PyObject*).
+
+KEY_TYPE_IS_PYOBJECT
+Define if KEY_TYPE is a PyObject*, else undef.
+
+KEY_CHECK(K)
+Tests whether the PyObject* K can be converted to the (C) key type
+(KEY_TYPE).  The macro should return a boolean (zero for false,
+non-zero for true).  When it returns false, its caller should probably
+set a TypeError exception.
+
+TEST_KEY_SET_OR(V, K, T)
+Like Python's cmp().  Compares K(ey) to T(arget), where K & T are C
+values of type KEY_TYPE.  V is assigned an int value depending on
+the outcome:
+   < 0 if K < T
+  == 0 if K == T
+   > 0 if K > T
+This macro acts like an 'if', where the following statement is
+executed only if a Python exception has been raised because the
+values could not be compared.
+
+DECREF_KEY(K)
+K is a value of KEY_TYPE.  If KEY_TYPE is a flavor of PyObject*, write
+this to do Py_DECREF(K).  Else (e.g., KEY_TYPE is int) make it a nop.
+
+INCREF_KEY(K)
+K is a value of KEY_TYPE.  If KEY_TYPE is a flavor of PyObject*, write
+this to do Py_INCREF(K).  Else (e.g., KEY_TYPE is int) make it a nop.
+
+COPY_KEY(K, E)
+Like K=E.  Copy a key from E to K, both of KEY_TYPE.  Note that this
+doesn't decref K or incref E when KEY_TYPE is a PyObject*; the caller
+is responsible for keeping refcounts straight.
+
+COPY_KEY_TO_OBJECT(O, K)
+Roughly like O=K.  O is a PyObject*, and the macro must build a Python
+object form of K, assign it to O, and ensure that O owns the reference
+to its new value.  It may do this by creating a new Python object based
+on K (e.g., PyInt_FromLong(K) when KEY_TYPE is int), or simply by doing
+Py_INCREF(K) if KEY_TYPE is a PyObject*.
+
+COPY_KEY_FROM_ARG(TARGET, ARG, STATUS)
+Copy an argument to the target without creating a new reference to ARG.
+ARG is a PyObject*, and TARGET is of type KEY_TYPE.  If this can't be
+done (for example, KEY_CHECK(ARG) returns false), set a Python error
+and set status to 0.  If there is no error, leave status alone.
+
+
+Macros for Values
+
+VALUE_TYPE
+The C type declaration for values (e.g., int or PyObject*).
+
+VALUE_TYPE_IS_PYOBJECT
+Define if VALUE_TYPE is a PyObject*, else undef.
+
+TEST_VALUE(X, Y)
+Like Python's cmp().  Compares X to Y, where X & Y are C values of
+type VALUE_TYPE.  The macro returns an int, with value
+   < 0 if X < Y
+  == 0 if X == Y
+   > 0 if X > Y
+XXX There is no provision for determining whether the comparison
+attempt failed (set a Python exception).
+
+DECREF_VALUE(K)
+Like DECREF_KEY, except applied to values of VALUE_TYPE.
+
+INCREF_VALUE(K)
+Like INCREF_KEY, except applied to values of VALUE_TYPE.
+
+COPY_VALUE(K, E)
+Like COPY_KEY, except applied to values of VALUE_TYPE.
+
+COPY_VALUE_TO_OBJECT(O, K)
+Like COPY_KEY_TO_OBJECT, except applied to values of VALUE_TYPE.
+
+COPY_VALUE_FROM_ARG(TARGET, ARG, STATUS)
+Like COPY_KEY_FROM_ARG, except applied to values of VALUE_TYPE.
+
+NORMALIZE_VALUE(V, MIN)
+Normalize the value, V, using the parameter MIN.  This is almost
+certainly a YAGNI.  It is a no op for most types. For integers, V is
+replaced by V/MIN only if MIN > 0.
+
+
+Macros for Set Operations
+
+MERGE_DEFAULT
+A value of VALUE_TYPE specifying the value to associate with set
+elements when sets are merged with mappings via weighed union or
+weighted intersection.
+
+MERGE(O1, w1, O2, w2)
+Performs a weighted merge of two values, O1 and O2, using weights w1
+and w2.  The result must be of VALUE_TYPE.  Note that weighted unions
+and weighted intersections are not enabled if this macro is left
+undefined.
+
+MERGE_WEIGHT(O, w)
+Computes a weighted value for O.  The result must be of VALUE_TYPE.
+This is used for "filling out" weighted unions, i.e. to compute a
+weighted value for keys that appear in only one of the input
+mappings.  If left undefined, MERGE_WEIGHT defaults to
+
+    #define MERGE_WEIGHT(O, w) (O)
+
+MULTI_INT_UNION
+The value doesn't matter.  If defined, SetOpTemplate.c compiles
+code for a multiunion() function (compute a union of many input sets
+at high speed).  This currently makes sense only for II sets, so
+only _IIBTree.c defines it.
+
+
+BTree Clues
+===========
+More or less random bits of helpful info.
+
++ In papers and textbooks, this flavor of BTree is usually called
+  a B+-Tree, where "+" is a superscript.
+
++ All keys and all values live in the bucket leaf nodes.  Keys in
+  interior (BTree) nodes merely serve to guide a search efficiently
+  toward the correct leaf.
+
++ When a key is deleted, it's physically removed from the bucket
+  it's in, but this doesn't propagate back up the tree:  since keys
+  in interior nodes only serve to guide searches, it's OK-- and
+  saves time --to leave "stale" keys in interior nodes.
+
++ No attempt is made to rebalance the tree after a deletion, unless
+  a bucket thereby becomes entirely empty.  "Classic BTrees" do
+  rebalance, keeping all buckets at least half full (provided there
+  are enough keys in the entire tree to fill half a bucket).  The
+  tradeoffs are murky.  Pathological cases in the presence of
+  deletion do exist.  Pathologies include trees tending toward only
+  one key per bucket, and buckets at differing depths (all buckets
+  are at the same depth in a classic BTree).
+
++ DEFAULT_MAX_BUCKET_SIZE and DEFAULT_MAX_BTREE_SIZE are chosen
+  mostly to "even out" pickle sizes in storage.  That's why, e.g.,
+  an IIBTree has larger values than an OOBTree:  pickles store ints
+  more efficiently than they can store arbitrary Python objects.
+
+
+The BTREE_SEARCH Macro
+======================
+For notational ease, consider a fixed BTree node x, and let
+
+    K(i) mean x->data.key[i]
+    C(i) mean all the keys reachable from x->data.child[i]
+
+For each i in 0 to x->len-1 inclusive,
+
+    K(i) <= C(i) < K(i+1)
+
+is a BTree node invariant, where we pretend that K(0) holds a key
+smaller than any possible key, and K(x->len) holds a key larger
+than any possible key.  (Note that K(x->len) doesn't actually exist,
+and K(0) is never used although space for it exists in non-empty
+BTree nodes.)
+
+When searching for a key k, then, the child pointer we want to follow
+is the one at index i such that K(i) <= k < K(i+1).  There can be
+at most one such i, since the K(i) are strictly increasing.  And there
+is at least one such i provided the tree isn't empty (so that 0 < len).
+For the moment, assume the tree isn't empty (we'll get back to that
+later).
+
+The macro's chief loop invariant is
+
+    K(lo) < k < K(hi)
+
+This holds trivially at the start, since lo is set to 0, and hi to
+x->len, and we pretend K(0) is minus infinity and K(len) is plus
+infinity.  Inside the loop, if K(i) < k we set lo to i, and if
+K(i) > k we set hi to i.  These obviously preserve the invariant.
+If K(i) == k, the loop breaks and sets the result to i, and since
+K(i) == k in that case i is obviously the correct result.
+
+Other cases depend on how i = floor((lo + hi)/2) works, exactly.
+Suppose lo + d = hi for some d >= 0.  Then i = floor((lo + lo + d)/2) =
+floor(lo + d/2) = lo + floor(d/2).  So:
+
+a. [d == 0] (lo == i == hi) if and only if (lo   == hi).
+b. [d == 1] (lo == i  < hi) if and only if (lo+1 == hi).
+c. [d  > 1] (lo  < i  < hi) if and only if (lo+1  < hi).
+
+If the node is empty (x->len == 0), then lo==i==hi==0 at the start,
+and the loop exits immediately (the first "i > lo" test fails),
+without entering the body.
+
+Else lo < hi at the start, and the invariant K(lo) < k < K(hi) holds.
+
+If lo+1 < hi, we're in case #c:  i is strictly between lo and hi,
+so the loop body is entered, and regardless of whether the body sets
+the new lo or the new hi to i, the new lo is strictly less than the
+new hi, and the difference between the new lo and new hi is strictly
+less than the difference between the old lo and old hi.  So long as
+the new lo + 1 remains < the new hi, we stay in this case.  We can't
+stay in this case forever, though:  because hi-lo decreases on each
+trip but remains > 0, lo+1 == hi must eventually become true.  (In
+fact, it becomes true quickly, in about log2(x->len) trips; the
+point is more that lo doesn't equal hi when the loop ends, it has to
+end with lo+1==hi and i==lo).
+
+Then we're in case #b:  i==lo==hi-1 then, and the loop exits.  The
+invariant still holds, with lo==i and hi==lo+1==i+1:
+
+    K(i) < k < K(i+1)
+
+so i is again the correct answer.
+
+Optimization points:
+
++ Division by 2 is done via shift rather via "/2".  These are
+  signed ints, and almost all C compilers treat signed int division
+  as truncating, and shifting is not the same as truncation for
+  signed int division.  The compiler has no way to know these values
+  aren't negative, so has to generate longer-winded code for "/2".
+  But we know these values aren't negative, and exploit it.
+
++ The order of _cmp comparisons matters.  We're in an interior
+  BTree node, and are looking at only a tiny fraction of all the
+  keys that exist.  So finding the key exactly in this node is
+  unlikely, and checking _cmp == 0 is a waste of time to the same
+  extent.  It doesn't matter whether we check for _cmp < 0 or
+  _cmp > 0 first, so long as we do both before worrying about
+  equality.
+
++ At the start of a routine, it's better to run this macro even
+  if x->len is 0 (check for that afterwards).  We just called a
+  function and so probably drained the pipeline.  If the first thing
+  we do then is read up self->len and check it against 0, we just
+  sit there waiting for the data to get read up, and then another
+  immediate test-and-branch, and for a very unlikely case (BTree
+  nodes are rarely empty).  It's better to get into the loop right
+  away so the normal case makes progress ASAP.
+
+
+The BUCKET_SEARCH Macro
+=======================
+This has a different job than BTREE_SEARCH:  the key 0 slot is
+legitimate in a bucket, and we want to find the index at which the
+key belongs.  If the key is larger than the bucket's largest key, a
+new slot at index len is where it belongs, else it belongs at the
+smallest i with keys[i] >= the key we're looking for.  We also need
+to know whether or not the key is present (BTREE_SEARCH didn't care;
+it only wanted to find the next node to search).
+
+The mechanics of the search are quite similar, though.  The primary
+loop invariant changes to (say we're searching for key k):
+
+    K(lo-1) < k < K(hi)
+
+where K(i) means keys[i], and we pretend K(-1) is minus infinity and
+K(len) is plus infinity.
+
+If the bucket is empty, lo=hi=i=0 at the start, the loop body is never
+entered, and the macro sets INDEX to 0 and ABSENT to true.  That's why
+_cmp is initialized to 1 (_cmp becomes ABSENT).
+
+Else the bucket is not empty, lo<hi at the start, and the loop body
+is entered.  The invariant is obviously satisfied then, as lo=0 and
+hi=len.
+
+If K[i]<k, lo is set to i+1, preserving that K(lo-1) = K[i] < k.
+If K[i]>k, hi is set to i, preserving that K[hi] = K[i] > k.
+If the loop exits after either of those, _cmp != 0, so ABSENT becomes
+true.
+If K[i]=k, the loop breaks, so that INDEX becomes i, and ABSENT
+becomes false (_cmp=0 in this case).
+
+The same case analysis for BTREE_SEARCH on lo and hi holds here:
+
+a. (lo == i == hi) if and only if (lo   == hi).
+b. (lo == i  < hi) if and only if (lo+1 == hi).
+c. (lo  < i  < hi) if and only if (lo+1  < hi).
+
+So long as lo+1 < hi, we're in case #c, and either break with
+equality (in which case the right results are obviously computed) or
+narrow the range.  If equality doesn't obtain, the range eventually
+narrows to cases #a or #b.
+
+To go from #c to #a, we must have lo+2==hi at the start, and
+K[i]=K[lo+1]<k.  Then the new lo gets set to i+1 = lo+2 = hi, and the
+loop exits with lo=hi=i and _cmp<0.  This is correct, because we
+know that k != K(i) (loop invariant! we actually know something
+stronger, that k < K(hi); since i=hi, this implies k != K(i)).
+
+Else #c eventually falls into case #b, lo+1==hi and i==lo.  The
+invariant tells us K(lo-1) < k < K(hi) = K(lo+1), so if the key
+is present it must be at K(lo).  i==lo in this case, so we test
+K(lo) against k.  As always, if equality obtains we do the right
+thing, else case #b becomes case #a.
+
+When #b becomes #a, the last comparison was non-equal, so _cmp is
+non-zero, and the loop exits because lo==hi==i in case #a.  The
+invariant then tells us K(lo-1) < k < K(lo), so the key is in fact
+not present, it's correct to exit with _cmp non-zero, and i==lo is
+again the index at which k belongs.
+
+Optimization points:
+
++ As for BTREE_SEARCH, shifting of signed ints is cheaper than
+  division.
+
++ Unlike as for BTREE_SEARCH, there's nothing special about searching
+  an empty bucket, and the macro computes thoroughly sensible results
+  in that case.
+
++ The order of _cmp comparisons differs from BTREE_SEARCH.  When
+  searching a bucket, it's much more likely (than when searching a
+  BTree node) that the key is present, so testing __cmp==0 isn't a
+  systematic waste of cycles.  At the extreme, if all searches are
+  successful (key present), on average this saves one comparison per
+  search, against leaving the determination of _cmp==0 implicit (as
+  BTREE_SEARCH does).  But even on successful searches, __cmp != 0 is
+  a more popular outcome than __cmp == 0 across iterations (unless
+  the bucket has only a few keys), so it's important to check one
+  of the inequality cases first.  It turns out it's better on average
+  to check K(i) < key (than to check K(i) > key), because when it
+  pays it narrows the range more (we get a little boost from setting
+  lo=i+1 in this case; the other case sets hi=i, which isn't as much
+  of a narrowing).


=== Zope3/lib/python/Persistence/BTrees/MergeTemplate.c 1.1 => 1.2 ===
+
+  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define MERGETEMPLATE_C "$Id$\n"
+
+/****************************************************************************
+ Set operations
+ ****************************************************************************/
+
+static int
+merge_output(Bucket *r, SetIteration *i, int mapping)
+{
+    if (r->len >= r->size && Bucket_grow(r, -1, !mapping) < 0)
+	return -1;
+    COPY_KEY(r->keys[r->len], i->key);
+    INCREF_KEY(r->keys[r->len]);
+    if (mapping) {
+	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;
+  if (ConflictError == NULL) {
+  	ConflictError = PyExc_ValueError;
+	Py_INCREF(ConflictError);
+  }
+  PyErr_SetObject(ConflictError, 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};
+  int cmp12, cmp13, cmp23, mapping=0, set;
+
+  if (initSetIteration(&i1, OBJECT(s1), 0, &mapping) < 0)
+      goto err;
+  if (initSetIteration(&i2, OBJECT(s2), 0, &mapping) < 0)
+      goto err;
+  if (initSetIteration(&i3, OBJECT(s3), 0, &mapping) < 0)
+      goto err;
+
+  set = !mapping;
+
+  if (mapping)
+      r = (Bucket *)PyObject_CallObject((PyObject *)&BucketType, NULL);
+  else
+      r = (Bucket *)PyObject_CallObject((PyObject *)&SetType, NULL);
+  if (r == NULL)
+      goto err;
+
+  if (i1.next(&i1) < 0)
+      goto err;
+  if (i2.next(&i2) < 0)
+      goto err;
+  if (i3.next(&i3) < 0)
+      goto err;
+
+  while (i1.position >= 0 && i2.position >= 0 && i3.position >= 0)
+    {
+      TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
+      TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
+      if (cmp12==0)
+        {
+          if (cmp13==0)
+            {
+              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 */
+          TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
+          if (cmp23==0)
+            {                   /* dualing inserts or deletes */
+              merge_error(i1.position, i2.position, i3.position, 4);
+              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 */
+      TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
+      if (cmp23==0)
+        {                       /* dualing inserts */
+          merge_error(i1.position, i2.position, i3.position, 6);
+          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 */
+      TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
+      if (cmp12 > 0)
+        {                       /* insert i2 */
+          if (merge_output(r, &i2, mapping) < 0) goto err;
+          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
+        {                       /* Dueling 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 */
+      TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
+      if (cmp13 > 0)
+        {                       /* insert i3 */
+          if (merge_output(r, &i3, mapping) < 0) goto err;
+          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
+        {                       /* Dueling 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;
+    }
+
+  finiSetIteration(&i1);
+  finiSetIteration(&i2);
+  finiSetIteration(&i3);
+
+  if (s1->next)
+    {
+      Py_INCREF(s1->next);
+      r->next = s1->next;
+    }
+  s = bucket_getstate(r);
+  Py_DECREF(r);
+
+  return s;
+
+ err:
+  finiSetIteration(&i1);
+  finiSetIteration(&i2);
+  finiSetIteration(&i3);
+  Py_XDECREF(r);
+  return NULL;
+}


=== Zope3/lib/python/Persistence/BTrees/OIBTree.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+from _OIBTree import *


=== Zope3/lib/python/Persistence/BTrees/OOBTree.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+from _OOBTree import *


=== Zope3/lib/python/Persistence/BTrees/SetOpTemplate.c 1.1 => 1.2 === (443/543 lines abridged)
+
+  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+/****************************************************************************
+ Set operations
+ ****************************************************************************/
+
+#define SETOPTEMPLATE_C "$Id$\n"
+
+#ifdef INTSET_H
+static int
+nextIntSet(SetIteration *i)
+{
+  if (i->position >= 0)
+    {
+      UNLESS(PER_USE(INTSET(i->set))) return -1;
+
+      if (i->position < INTSET(i->set)->len)
+        {
+          i->key = INTSET(i->set)->data[i->position];
+          i->position ++;
+        }
+      else
+        {
+          i->position = -1;
+          PyPersist_SetATime(INTSET(i->set));
+        }
+
+      PER_ALLOW_DEACTIVATION(INTSET(i->set));
+    }
+
+
+  return 0;
+}
+#endif
+
+#ifdef KEY_CHECK
+static int
+nextKeyAsSet(SetIteration *i)
+{

[-=- -=- -=- 443 lines omitted -=- -=- -=-]

+                    PER_ACCESSED(set);
+                    goto Error;
+                }
+            }
+            memcpy(result->keys + result->len,
+                   BUCKET(set)->keys,
+                   setsize * sizeof(KEY_TYPE));
+            result->len += setsize;
+            PER_ALLOW_DEACTIVATION(SIZED(set));
+            PER_ACCESSED(set);
+        }
+        else {
+            /* No cheap way:  iterate over set's elements one at a time. */
+            int merge;  /* dummy needed for initSetIteration */
+
+            if (initSetIteration(&setiter, set, -1, &merge) < 0) goto Error;
+            if (setiter.next(&setiter) < 0) goto Error;
+            while (setiter.position >= 0) {
+                if (result->len >= result->size && Bucket_grow(result, -1, 1) < 0)
+                    goto Error;
+                COPY_KEY(result->keys[result->len], setiter.key);
+                ++result->len;
+                /* We know the key is an int, so no need to incref it. */
+                if (setiter.next(&setiter) < 0) goto Error;
+            }
+            finiSetIteration(&setiter);
+        }
+        Py_DECREF(set);
+        set = NULL;
+    }
+
+    /* Combine, sort, remove duplicates, and reset the result's len.
+       If the set shrinks (which happens if and only if there are
+       duplicates), no point to realloc'ing the set smaller, as we
+       expect the result set to be short-lived.
+    */
+    if (result->len > 0) {
+        size_t newlen;          /* number of elements in final result set */
+        newlen = sort_int4_nodups(result->keys, (size_t)result->len);
+        result->len = (int)newlen;
+    }
+    return (PyObject *)result;
+
+Error:
+    Py_DECREF(result);
+    Py_XDECREF(set);
+    finiSetIteration(&setiter);
+    return NULL;
+}
+#endif


=== Zope3/lib/python/Persistence/BTrees/SetTemplate.c 1.1 => 1.2 ===
+
+  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+  
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+  
+ ****************************************************************************/
+
+#define SETTEMPLATE_C "$Id$\n"
+
+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);
+}
+
+/* _Set_update and _TreeSet_update are identical except for the
+   function they call to add the element to the set.
+*/
+
+static int
+_Set_update(Bucket *self, PyObject *seq)
+{
+    int n = -1;
+    PyObject *iter, *v;
+    int ind;
+
+    iter = PyObject_GetIter(seq);
+    if (iter == NULL)
+	return -1;
+
+    while (1) {
+	v = PyIter_Next(iter);
+	if (v == NULL) {
+	    if (PyErr_Occurred())
+		goto err;
+	    else
+		break;
+	}
+	ind = _bucket_set(self, v, Py_None, 1, 1, 0);
+	Py_DECREF(v);
+	if (ind < 0)
+	    goto err;
+	else
+	    n += ind;
+    }
+    /* n starts out at -1, which is the error return value.  If
+       this point is reached, then there is no error.  n must be
+       incremented to account for the initial value of -1 instead of
+       0.  
+    */
+    n++;
+
+ err:
+    Py_DECREF(iter);
+    return n;
+}
+
+static PyObject *
+Set_update(Bucket *self, PyObject *args)
+{
+    PyObject *seq = NULL;
+    int n = 0;
+
+    if (!PyArg_ParseTuple(args, "|O:update", &seq))
+	return NULL;
+
+    if (seq) {
+	n = _Set_update(self, seq);
+	if (n < 0)
+	    return NULL;
+    }
+
+    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;
+
+  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=BTree_Realloc(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);
+  PyPersist_SetATime(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_O,
+     "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"},
+  {"remove",	(PyCFunction)Set_remove,	METH_VARARGS,
+   "remove(id) -- Remove an id from the set"},
+
+  {NULL,		NULL}		/* sentinel */
+};
+
+static int
+Set_init(PyObject *self, PyObject *args, PyObject *kwds)
+{
+    PyObject *v = NULL;
+
+    if (!PyArg_ParseTuple(args, "|O:" MOD_NAME_PREFIX "Set", &v))
+	return -1;
+
+    if (v)
+	return _Set_update((Bucket *)self, v);
+    else
+	return 0;
+}
+
+
+
+static PyObject *
+set_repr(Bucket *self)
+{
+  static PyObject *format;
+  PyObject *r, *t;
+
+  UNLESS (format) UNLESS (format=PyString_FromString(MOD_NAME_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);
+  PyPersist_SetATime(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);
+  PyPersist_SetATime(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 PyTypeObject SetType = {
+    PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+    0,					/* ob_size */
+    MODULE_NAME MOD_NAME_PREFIX "Set",	/* tp_name */
+    sizeof(Bucket),			/* tp_basicsize */
+    0,					/* tp_itemsize */
+    (destructor)bucket_dealloc,		/* tp_dealloc */
+    0,					/* tp_print */
+    0,					/* tp_getattr */
+    0,					/* tp_setattr */
+    0,					/* tp_compare */
+    (reprfunc)set_repr,			/* tp_repr */
+    0,					/* tp_as_number */
+    &set_as_sequence,			/* tp_as_sequence */
+    0,					/* tp_as_mapping */
+    0,					/* tp_hash */
+    0,					/* tp_call */
+    0,					/* tp_str */
+    0,					/* tp_getattro */
+    0,					/* tp_setattro */
+    0,					/* tp_as_buffer */
+    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+	    Py_TPFLAGS_BASETYPE, 	/* tp_flags */
+    0,					/* tp_doc */
+    (traverseproc)bucket_traverse,	/* tp_traverse */
+    (inquiry)bucket_tp_clear,		/* tp_clear */
+    0,					/* tp_richcompare */
+    offsetof(Bucket, po_weaklist),	/* tp_weaklistoffset */
+    0,					/* tp_iter */
+    0,					/* tp_iternext */
+    Set_methods,			/* tp_methods */
+    0,					/* tp_members */
+    0,					/* tp_getset */
+    0,					/* tp_base */
+    0,					/* tp_dict */
+    0,					/* tp_descr_get */
+    0,					/* tp_descr_set */
+    0,					/* tp_dictoffset */
+    Set_init,				/* tp_init */
+    0,					/* tp_alloc */
+    PyType_GenericNew,			/* tp_new */
+};
+
+static int 
+nextSet(SetIteration *i)
+{
+          
+  if (i->position >= 0)
+    {
+      UNLESS(PER_USE(BUCKET(i->set))) return -1;
+
+      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;
+          PyPersist_SetATime(BUCKET(i->set));
+        }
+
+      PER_ALLOW_DEACTIVATION(BUCKET(i->set));
+    }
+
+          
+  return 0;
+}


=== Zope3/lib/python/Persistence/BTrees/TreeSetTemplate.c 1.1 => 1.2 ===
+
+  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+  
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+  
+ ****************************************************************************/
+
+#define TREESETTEMPLATE_C "$Id$\n"
+
+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);
+}
+
+/* _Set_update and _TreeSet_update are identical except for the
+   function they call to add the element to the set.
+*/
+
+static int
+_TreeSet_update(BTree *self, PyObject *seq)
+{
+    int n = -1;
+    PyObject *iter, *v;
+    int ind;
+
+    iter = PyObject_GetIter(seq);
+    if (iter == NULL)
+	return -1;
+
+    while (1) {
+	v = PyIter_Next(iter);
+	if (v == NULL) {
+	    if (PyErr_Occurred())
+		goto err;
+	    else
+		break;
+	}
+	ind = _BTree_set(self, v, Py_None, 1, 1);
+	Py_DECREF(v);
+	if (ind < 0)
+	    goto err;
+	else
+	    n += ind;
+    }
+    /* n starts out at -1, which is the error return value.  If
+       this point is reached, then there is no error.  n must be
+       incremented to account for the initial value of -1 instead of
+       0.  
+    */
+    n++;
+
+ err:
+    Py_DECREF(iter);
+    return n;
+}
+
+static PyObject *
+TreeSet_update(BTree *self, PyObject *args)
+{
+    PyObject *seq = NULL;
+    int n = 0;
+
+    if (!PyArg_ParseTuple(args, "|O:update", &seq))
+	return NULL;
+
+    if (seq) {
+	n = _TreeSet_update(self, seq);
+	if (n < 0)
+	    return NULL;
+    }
+
+    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);
+  PyPersist_SetATime(self);
+
+  if (r < 0) return NULL;
+  Py_INCREF(Py_None);
+  return Py_None;
+}
+
+static struct PyMethodDef TreeSet_methods[] = {
+  {"__getstate__", (PyCFunction) BTree_getstate,	METH_NOARGS,
+   "__getstate__() -> state\n\n"
+   "Return the picklable state of the TreeSet."},
+  {"__setstate__", (PyCFunction) TreeSet_setstate,	METH_VARARGS,
+   "__setstate__(state)\n\n"
+   "Set the state of the TreeSet."},
+  {"has_key",	(PyCFunction) BTree_has_key,	METH_O,
+   "has_key(key)\n\n"
+   "Return true if the TreeSet contains the given key."},
+  {"keys",	(PyCFunction) BTree_keys,	METH_VARARGS,
+   "keys([min, max]) -> list of keys\n\n"
+   "Returns the keys of the TreeSet.  If min and max are supplied, only\n"
+   "keys greater than min and less than max are returned."},
+  {"maxKey", (PyCFunction) BTree_maxKey,	METH_VARARGS,
+   "maxKey([max]) -> key\n\n"
+   "Return the largest key in the BTree.  If max is specified, return\n"
+   "the largest key <= max."},
+  {"minKey", (PyCFunction) BTree_minKey,	METH_VARARGS,
+   "minKey([mi]) -> key\n\n"
+   "Return the smallest key in the BTree.  If min is specified, return\n"
+   "the smallest key >= min."},
+  {"clear",	(PyCFunction) BTree_clear,	METH_NOARGS,
+   "clear()\n\nRemove 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(collection)\n\n Add the items from the given collection."},
+  {"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_NOARGS,
+   "_p_deactivate()\n\nReinitialize from a newly created copy."},
+#endif
+  {NULL,		NULL}		/* sentinel */
+};
+
+static PyMappingMethods TreeSet_as_mapping = {
+  (inquiry)BTree_length,		/*mp_length*/
+};
+
+static int
+TreeSet_init(PyObject *self, PyObject *args, PyObject *kwds)
+{
+    PyObject *v = NULL;
+
+    if (!PyArg_ParseTuple(args, "|O:" MOD_NAME_PREFIX "TreeSet", &v))
+	return -1;
+
+    if (v)
+	return _TreeSet_update((BTree *)self, v);
+    else
+	return 0;
+}
+
+static PyTypeObject TreeSetType = {
+    PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+    0,					/* ob_size */
+    MODULE_NAME MOD_NAME_PREFIX "TreeSet",/* tp_name */
+    sizeof(BTree),			/* tp_basicsize */
+    0,					/* tp_itemsize */
+    (destructor)BTree_dealloc,		/* tp_dealloc */
+    0,					/* tp_print */
+    0,					/* tp_getattr */
+    0,					/* tp_setattr */
+    0,					/* tp_compare */
+    0,					/* tp_repr */
+    &BTree_as_number_for_nonzero,	/* tp_as_number */
+    0,					/* tp_as_sequence */
+    &TreeSet_as_mapping,		/* tp_as_mapping */
+    0,					/* tp_hash */
+    0,					/* tp_call */
+    0,					/* tp_str */
+    0,					/* tp_getattro */
+    0,					/* tp_setattro */
+    0,					/* tp_as_buffer */
+    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | 
+	    Py_TPFLAGS_BASETYPE, 	/* tp_flags */
+    0,					/* tp_doc */
+    (traverseproc)BTree_traverse,	/* tp_traverse */
+    (inquiry)BTree_tp_clear,		/* tp_clear */
+    0,					/* tp_richcompare */
+    offsetof(BTree, po_weaklist),	/* tp_weaklistoffset */
+    0,					/* tp_iter */
+    0,					/* tp_iternext */
+    TreeSet_methods,			/* tp_methods */
+    0,					/* tp_members */
+    0,					/* tp_getset */
+    0,					/* tp_base */
+    0,					/* tp_dict */
+    0,					/* tp_descr_get */
+    0,					/* tp_descr_set */
+    0,					/* tp_dictoffset */
+    TreeSet_init,			/* tp_init */
+    0,					/* tp_alloc */
+    PyType_GenericNew,			/* tp_new */
+};


=== Zope3/lib/python/Persistence/BTrees/_IIBTree.c 1.1 => 1.2 ===
+
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "II"
+#define INITMODULE init_IIBTree
+#define DEFAULT_MAX_BUCKET_SIZE 120
+#define DEFAULT_MAX_BTREE_SIZE 500
+#define MULTI_INT_UNION 1
+
+#include "intkeymacros.h"
+#include "intvaluemacros.h"
+#ifndef EXCLUDE_INTSET_SUPPORT
+#include "BTree/intSet.h"
+#endif
+#include "BTreeModuleTemplate.c"


=== Zope3/lib/python/Persistence/BTrees/_IOBTree.c 1.1 => 1.2 ===
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "IO"
+#define DEFAULT_MAX_BUCKET_SIZE 60
+#define DEFAULT_MAX_BTREE_SIZE 500
+#define INITMODULE init_IOBTree
+                                
+#include "intkeymacros.h"
+#include "objectvaluemacros.h"
+#ifndef EXCLUDE_INTSET_SUPPORT
+#include "BTree/intSet.h"
+#endif
+#include "BTreeModuleTemplate.c"


=== Zope3/lib/python/Persistence/BTrees/_OIBTree.c 1.1 => 1.2 ===
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "OI"
+#define INITMODULE init_OIBTree
+#define DEFAULT_MAX_BUCKET_SIZE 60
+#define DEFAULT_MAX_BTREE_SIZE 250
+                                
+#include "objectkeymacros.h"
+#include "intvaluemacros.h"
+#include "BTreeModuleTemplate.c"


=== Zope3/lib/python/Persistence/BTrees/_OOBTree.c 1.1 => 1.2 ===
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "OO"
+#define INITMODULE init_OOBTree
+#define DEFAULT_MAX_BUCKET_SIZE 30
+#define DEFAULT_MAX_BTREE_SIZE 250
+                                
+#include "objectkeymacros.h"
+#include "objectvaluemacros.h"
+#include "BTreeModuleTemplate.c"


=== Zope3/lib/python/Persistence/BTrees/__init__.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+##import ZODB
+
+##try: import intSet
+##except: pass
+##else: del intSet
+
+### Register interfaces
+##try: import Interface
+##except ImportError: pass # Don't register interfaces if no scarecrow
+##else:
+##    import Interfaces
+##    del Interfaces
+##    del Interface


=== Zope3/lib/python/Persistence/BTrees/_fsBTree.c 1.1 => 1.2 ===
+
+   This BTree implments a mapping from 2-character strings
+   to six-character strings. This allows us to effieciently store
+   a FileStorage index as a nested mapping of 6-character oid prefix
+   to mapping of 2-character oid suffix to 6-character (byte) file
+   positions.
+*/
+
+#include <string.h>
+
+typedef unsigned char char2[2];
+typedef unsigned char char6[6];
+
+
+/* Setup template macros */
+
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "fs"
+#define INITMODULE init_fsBTree
+#define DEFAULT_MAX_BUCKET_SIZE 500
+#define DEFAULT_MAX_BTREE_SIZE 500
+                
+/*#include "intkeymacros.h"*/
+
+#define KEYMACROS_H "$Id$\n"
+#define KEY_TYPE char2
+#undef KEY_TYPE_IS_PYOBJECT
+#define KEY_CHECK(K) (PyString_Check(K) && PyString_GET_SIZE(K)==2)
+#define TEST_KEY_SET_OR(V, K, T) if ( ( (V) = ((*(K) < *(T) || (*(K) == *(T) && (K)[1] < (T)[1])) ? -1 : ((*(K) == *(T) && (K)[1] == (T)[1]) ? 0 : 1)) ), 0 )
+#define DECREF_KEY(KEY)
+#define INCREF_KEY(k)
+#define COPY_KEY(KEY, E) (*(KEY)=*(E), (KEY)[1]=(E)[1])
+#define COPY_KEY_TO_OBJECT(O, K) O=PyString_FromStringAndSize(K,2)
+#define COPY_KEY_FROM_ARG(TARGET, ARG, STATUS) \
+  if (KEY_CHECK(ARG)) memcpy(TARGET, PyString_AS_STRING(ARG), 2); else { \
+      PyErr_SetString(PyExc_TypeError, "expected two-character string key"); \
+      (STATUS)=0; } 
+
+/*#include "intvaluemacros.h"*/
+#define VALUEMACROS_H "$Id$\n"
+#define VALUE_TYPE char6
+#undef VALUE_TYPE_IS_PYOBJECT
+#define TEST_VALUE(K, T) strncmp(K,T,6)
+#define DECREF_VALUE(k)
+#define INCREF_VALUE(k)
+#define COPY_VALUE(V, E) (memcpy(V, E, 6))
+#define COPY_VALUE_TO_OBJECT(O, K) O=PyString_FromStringAndSize(K,6)
+#define COPY_VALUE_FROM_ARG(TARGET, ARG, STATUS) \
+  if ((PyString_Check(ARG) && PyString_GET_SIZE(ARG)==6)) \
+      memcpy(TARGET, PyString_AS_STRING(ARG), 6); else { \
+      PyErr_SetString(PyExc_TypeError, "expected six-character string key"); \
+      (STATUS)=0; } 
+  
+#define NORMALIZE_VALUE(V, MIN)
+#include "BTreeModuleTemplate.c"


=== Zope3/lib/python/Persistence/BTrees/convert.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+# 
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+# 
+##############################################################################
+def convert(old, new, threshold=200, f=None):
+    "Utility for converting old btree to 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)


=== Zope3/lib/python/Persistence/BTrees/intkeymacros.h 1.1 => 1.2 ===
+#define KEYMACROS_H "$Id$\n"
+
+#define KEY_TYPE int
+#undef KEY_TYPE_IS_PYOBJECT
+#define KEY_CHECK PyInt_Check
+#define TEST_KEY_SET_OR(V, K, T) if ( ( (V) = (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0)) ) , 0 )
+#define DECREF_KEY(KEY)
+#define INCREF_KEY(k)
+#define COPY_KEY(KEY, E) (KEY=(E))
+#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_AS_LONG(ARG); \
+    else { \
+	PyErr_Format(PyExc_TypeError, "expected integer key, found %s", \
+		     (ARG)->ob_type->tp_name); \
+	(STATUS) = 0; \
+	(TARGET) = 0; \
+    }


=== Zope3/lib/python/Persistence/BTrees/intvaluemacros.h 1.1 => 1.2 ===
+#define VALUEMACROS_H "$Id$\n"
+
+#define VALUE_TYPE int
+#undef VALUE_TYPE_IS_PYOBJECT
+
+#define TEST_VALUE(K, T) (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0))
+#define VALUE_SAME(VALUE, TARGET) ( (VALUE) == (TARGET) )
+#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; (TARGET)=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))


=== Zope3/lib/python/Persistence/BTrees/objectkeymacros.h 1.1 => 1.2 ===
+#define KEY_TYPE PyObject *
+#define KEY_TYPE_IS_PYOBJECT
+#define TEST_KEY_SET_OR(V, KEY, TARGET) if ( ( (V) = PyObject_Compare((KEY),(TARGET)) ), PyErr_Occurred() )
+#define INCREF_KEY(k) Py_INCREF(k)
+#define DECREF_KEY(KEY) Py_DECREF(KEY)
+#define COPY_KEY(KEY, E) KEY=(E)
+#define COPY_KEY_TO_OBJECT(O, K) O=(K); Py_INCREF(O)
+#define COPY_KEY_FROM_ARG(TARGET, ARG, S) TARGET=(ARG)


=== Zope3/lib/python/Persistence/BTrees/objectvaluemacros.h 1.1 => 1.2 ===
+#define VALUEMACROS_H "$Id$\n"
+
+#define VALUE_TYPE PyObject *
+#define VALUE_TYPE_IS_PYOBJECT
+#define TEST_VALUE(VALUE, TARGET) PyObject_Compare((VALUE),(TARGET))
+#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)


=== Zope3/lib/python/Persistence/BTrees/sorters.c 1.1 => 1.2 === (427/527 lines abridged)
+
+  Copyright (c) 2002 Zope Corporation and Contributors.
+  All Rights Reserved.
+
+  This software is subject to the provisions of the Zope Public License,
+  Version 2.0 (ZPL).  A copy of the ZPL should accompany this distribution.
+  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+  FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+/* Revision information: $Id$ */
+
+/* The only routine here intended to be used outside the file is
+   size_t sort_int4_nodups(int *p, size_t n)
+
+   Sort the array of n ints pointed at by p, in place, and also remove
+   duplicates.  Return the number of unique elements remaining, which occupy
+   a contiguous and monotonically increasing slice of the array starting at p.
+
+   Example:  If the input array is [3, 1, 2, 3, 1, 5, 2], sort_int4_nodups
+   returns 4, and the first 4 elements of the array are changed to
+   [1, 2, 3, 5].  The content of the remaining array positions is not defined.
+
+   Notes:
+
+   + This is specific to 4-byte signed ints, with endianness natural to the
+     platform.
+
+   + 4*n bytes of available heap memory are required for best speed.
+*/
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <malloc.h>
+#include <memory.h>
+#include <string.h>
+#include <assert.h>
+
+/* The type of array elements to be sorted.  Most of the routines don't
+   care about the type, and will work fine for any scalar C type (provided
+   they're recompiled with element_type appropriately redefined).  However,
+   the radix sort has to know everything about the type's internal
+   representation.
+*/
+typedef int element_type;
+
+/* The radixsort is faster than the quicksort for large arrays, but radixsort

[-=- -=- -=- 427 lines omitted -=- -=- -=-]

+		plo[1] = *pj;
+		*pj = pivot;
+
+		/* Subfiles are from plo to pj-1 inclusive, and pj+1 to phi
+		   inclusive.  Push the larger one, and loop back to do the
+		   smaller one directly.
+		*/
+		if (pj - plo >= phi - pj) {
+			PUSH(plo, pj-1);
+			plo = pj+1;
+		}
+		else {
+			PUSH(pj+1, phi);
+			phi = pj-1;
+		}
+	}
+
+#undef PUSH
+#undef SWAP
+}
+
+/* Sort p and remove duplicates, as fast as we can. */
+static size_t
+sort_int4_nodups(int *p, size_t n)
+{
+	size_t nunique;
+	element_type *work;
+
+	assert(sizeof(int) == sizeof(element_type));
+	assert(p);
+
+	/* Use quicksort if the array is small, OR if malloc can't find
+	   enough temp memory for radixsort.
+	*/
+	work = NULL;
+	if (n > QUICKSORT_BEATS_RADIXSORT)
+		work = (element_type *)malloc(n * sizeof(element_type));
+
+	if (work) {
+		element_type *out = radixsort_int4(p, work, n);
+		nunique = uniq(p, out, n);
+		free(work);
+	}
+	else {
+		quicksort(p, n);
+		nunique = uniq(p, p, n);
+	}
+
+	return nunique;
+}