[Zope-Checkins] CVS: ZODB3/BTrees - BTreeItemsTemplate.c:1.19.16.1 BTreeModuleTemplate.c:1.37.92.2 BTreeTemplate.c:1.74.10.2 BucketTemplate.c:1.54.6.2 MergeTemplate.c:1.16.18.1 SetOpTemplate.c:1.29.92.1 SetTemplate.c:1.16.52.2 TreeSetTemplate.c:1.15.52.2 _IIBTree.c:1.7.92.1 _IOBTree.c:1.5.150.1 _OIBTree.c:1.2.268.1 _OOBTree.c:1.2.268.1 _fsBTree.c:1.6.10.1 sorters.c:1.4.94.1

Tim Peters tim.one@comcast.net
Thu, 3 Jul 2003 17:39:44 -0400


Update of /cvs-repository/ZODB3/BTrees
In directory cvs.zope.org:/tmp/cvs-serv23557/BTrees

Modified Files:
      Tag: zodb33-devel-branch
	BTreeItemsTemplate.c BTreeModuleTemplate.c BTreeTemplate.c 
	BucketTemplate.c MergeTemplate.c SetOpTemplate.c SetTemplate.c 
	TreeSetTemplate.c _IIBTree.c _IOBTree.c _OIBTree.c _OOBTree.c 
	_fsBTree.c sorters.c 
Log Message:
Massive mostly-mechanical edits of the ZODB4 BTree code, with files
renamed to the ZODB3 conventions.  This doesn't work at all yet, but
compiles and links without complaint under MSVC6 (Win2K).


=== ZODB3/BTrees/BTreeItemsTemplate.c 1.19 => 1.19.16.1 ===
--- ZODB3/BTrees/BTreeItemsTemplate.c:1.19	Sun Mar 16 16:42:29 2003
+++ ZODB3/BTrees/BTreeItemsTemplate.c	Thu Jul  3 17:38:59 2003
@@ -72,44 +72,45 @@
 static int
 BTreeItems_length_or_nonzero(BTreeItems *self, int nonzero)
 {
-  int r;
-  Bucket *b, *next;
+    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);
-      PER_ACCESSED(b);
-      Py_DECREF(b);
-      b=next;
-      PER_USE_OR_RETURN(b, -1);
-    }
-  PER_ALLOW_DEACTIVATION(b);
-  PER_ACCESSED(b);
-  Py_DECREF(b);
+    b = self->firstbucket;
+    if (b == NULL)
+	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);
+	PyPersist_SetATime(b);
+	Py_DECREF(b);
+	b = next;
+	PER_USE_OR_RETURN(b, -1);
+    }
+    PER_ALLOW_DEACTIVATION(b);
+    PyPersist_SetATime(b);
+    Py_DECREF(b);
 
-  return r >= 0 ? r : 0;
+    return r >= 0 ? r : 0;
 }
 
 static int
@@ -238,6 +239,61 @@
     return -1;
 }
 
+
+/* Return the right kind ('k','v','i') of entry from bucket b at offset i.
+ *  b must be activated.  Returns NULL on error.
+ */
+static PyObject *
+getBucketEntry(Bucket *b, int i, char kind)
+{
+    PyObject *result = NULL;
+
+    assert(b);
+    assert(0 <= i && i < b->len);
+
+    switch (kind) {
+
+        case 'k':
+            COPY_KEY_TO_OBJECT(result, b->keys[i]);
+            break;
+
+        case 'v':
+            COPY_VALUE_TO_OBJECT(result, b->values[i]);
+            break;
+
+        case 'i': {
+            PyObject *key;
+            PyObject *value;;
+
+            COPY_KEY_TO_OBJECT(key, b->keys[i]);
+            if (!key) break;
+
+            COPY_VALUE_TO_OBJECT(value, b->values[i]);
+            if (!value) {
+                Py_DECREF(key);
+                break;
+            }
+
+            result = PyTuple_New(2);
+            if (result) {
+                PyTuple_SET_ITEM(result, 0, key);
+                PyTuple_SET_ITEM(result, 1, value);
+            }
+            else {
+                Py_DECREF(key);
+                Py_DECREF(value);
+            }
+            break;
+        }
+
+        default:
+            PyErr_SetString(PyExc_AssertionError,
+                            "getBucketEntry: unknown kind");
+            break;
+    }
+    return result;
+}
+
 /*
 ** BTreeItems_item
 **
@@ -250,44 +306,15 @@
 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;
+    PyObject *result;
 
-    UNLESS (r=PyTuple_New(2)) goto err;
+    if (BTreeItems_seek(self, i) < 0) return NULL;
 
-    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_UNUSE(self->currentbucket);
-  return r;
-
- err:
-  Py_DECREF(k);
-  Py_XDECREF(v);
-  PER_UNUSE(self->currentbucket);
-  return NULL;
+    PER_USE_OR_RETURN(self->currentbucket, NULL);
+    result = getBucketEntry(self->currentbucket, self->currentoffset,
+                            self->kind);
+    PER_UNUSE(self->currentbucket);
+    return result;
 }
 
 /*
@@ -438,10 +465,10 @@
   BTreeItems *self;
 
   UNLESS (self = PyObject_NEW(BTreeItems, &BTreeItemsType)) return NULL;
-  self->kind = kind;
+  self->kind=kind;
 
-  self->first = lowoffset;
-  self->last = highoffset;
+  self->first=lowoffset;
+  self->last=highoffset;
 
   if (! lowbucket || ! highbucket
       || (lowbucket == highbucket && lowoffset > highoffset))
@@ -454,9 +481,9 @@
     {
       Py_INCREF(lowbucket);
       self->firstbucket = lowbucket;
-      Py_XINCREF(highbucket);
+      Py_INCREF(highbucket);
       self->lastbucket = highbucket;
-      Py_XINCREF(lowbucket);
+      Py_INCREF(lowbucket);
       self->currentbucket = lowbucket;
     }
 
@@ -550,3 +577,141 @@
     }
   return 0;
 }
+
+/* Support for the iteration protocol new in Python 2.2. */
+
+static PyTypeObject BTreeIter_Type;
+
+/* The type of iterator objects, returned by e.g. iter(IIBTree()). */
+typedef struct {
+    PyObject_HEAD
+    /* We use a BTreeItems object because it's convenient and flexible.
+     * We abuse it two ways:
+     *     1. We set currentbucket to NULL when the iteration is finished.
+     *     2. We don't bother keeping pseudoindex in synch.
+     */
+    BTreeItems *pitems;
+} BTreeIter;
+
+/* Return a new iterator object, to traverse the keys and/or values
+ * represented by pitems.  pitems must not be NULL.  Returns NULL if error.
+ */
+static BTreeIter *
+BTreeIter_new(BTreeItems *pitems)
+{
+    BTreeIter *result;
+
+    assert(pitems != NULL);
+    result = PyObject_New(BTreeIter, &BTreeIter_Type);
+    if (result) {
+        Py_INCREF(pitems);
+        result->pitems = pitems;
+    }
+    return result;
+}
+
+/* The iterator's tp_dealloc slot. */
+static void
+BTreeIter_dealloc(BTreeIter *bi)
+{
+	Py_DECREF(bi->pitems);
+	PyObject_Del(bi);
+}
+
+/* The implementation of the iterator's tp_iternext slot.  Returns "the next"
+ * item; returns NULL if error; returns NULL without setting an error if the
+ * iteration is exhausted (that's the way to terminate the iteration protocol).
+ */
+static PyObject *
+BTreeIter_next(BTreeIter *bi, PyObject *args)
+{
+	PyObject *result = NULL;        /* until proven innocent */
+        BTreeItems *items = bi->pitems;
+        int i = items->currentoffset;
+	Bucket *bucket = items->currentbucket;
+
+        if (bucket == NULL)	/* iteration termination is sticky */
+	    return NULL;
+
+        PER_USE_OR_RETURN(bucket, NULL);
+        if (i >= bucket->len) {
+            /* We never leave this routine normally with i >= len:  somebody
+             * else mutated the current bucket.
+             */
+	    PyErr_SetString(PyExc_RuntimeError,
+		            "the bucket being iterated changed size");
+	    /* Arrange for that this error is sticky too. */
+	    items->currentoffset = INT_MAX;
+	    goto Done;
+	}
+
+        /* Build the result object, from bucket at offset i. */
+        result = getBucketEntry(bucket, i, items->kind);
+
+        /* Advance position for next call. */
+        if (bucket == items->lastbucket && i >= items->last) {
+            /* Next call should terminate the iteration. */
+            Py_DECREF(items->currentbucket);
+            items->currentbucket = NULL;
+        }
+        else {
+            ++i;
+            if (i >= bucket->len) {
+                Py_XINCREF(bucket->next);
+                items->currentbucket = bucket->next;
+                Py_DECREF(bucket);
+                i = 0;
+            }
+            items->currentoffset = i;
+        }
+
+Done:
+    PER_UNUSE(bucket);
+    return result;
+}
+
+static PyObject *
+BTreeIter_getiter(PyObject *it)
+{
+    Py_INCREF(it);
+    return it;
+}
+
+static PyTypeObject BTreeIter_Type = {
+        PyObject_HEAD_INIT(NULL)
+	0,					/* ob_size */
+	MOD_NAME_PREFIX "-iterator",		/* tp_name */
+	sizeof(BTreeIter),			/* tp_basicsize */
+	0,					/* tp_itemsize */
+	/* methods */
+	(destructor)BTreeIter_dealloc,          /* tp_dealloc */
+	0,					/* tp_print */
+	0,					/* tp_getattr */
+	0,					/* tp_setattr */
+	0,					/* tp_compare */
+	0,					/* tp_repr */
+	0,					/* tp_as_number */
+	0,					/* tp_as_sequence */
+	0,					/* tp_as_mapping */
+	0,					/* tp_hash */
+	0,					/* tp_call */
+	0,					/* tp_str */
+	0, /*PyObject_GenericGetAttr,*/		/* tp_getattro */
+	0,					/* tp_setattro */
+	0,					/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT,			/* tp_flags */
+ 	0,					/* tp_doc */
+ 	0,					/* tp_traverse */
+ 	0,					/* tp_clear */
+	0,					/* tp_richcompare */
+	0,					/* tp_weaklistoffset */
+	(getiterfunc)BTreeIter_getiter,		/* tp_iter */
+	(iternextfunc)BTreeIter_next,	        /* tp_iternext */
+	0,					/* tp_methods */
+	0,					/* tp_members */
+	0,					/* tp_getset */
+	0,					/* tp_base */
+	0,					/* tp_dict */
+	0,					/* tp_descr_get */
+	0,					/* tp_descr_set */
+};


=== ZODB3/BTrees/BTreeModuleTemplate.c 1.37.92.1 => 1.37.92.2 ===
--- ZODB3/BTrees/BTreeModuleTemplate.c:1.37.92.1	Tue Jul  1 15:34:08 2003
+++ ZODB3/BTrees/BTreeModuleTemplate.c	Thu Jul  3 17:38:59 2003
@@ -12,37 +12,25 @@
 
  ****************************************************************************/
 
+#include "Python.h"
+/* include structmember.h for offsetof */
+#include "structmember.h"
+
 #ifdef PERSISTENT
 #include "cPersistence.h"
-#include "ExtensionClass.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)
-
-#define PER_ACCESSED(O) ((O)->atime=((long)(time(NULL)/3))%65536)
-
-
-#endif
-/***************************************************************/
-
+//#include "persistence/persistenceAPI.h"
 #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_ACCESSED(O) 1
-#define PER_CHANGED(O) 0
 #endif
 
+/* XXX Go back to using PER_USE everywhere. */
+#define PyPersist_SetATime PER_USE
+
 /* So sue me.  This pair gets used all over the place, so much so that it
  * interferes with understanding non-persistence parts of algorithms.
  * PER_UNUSE can be used after a successul PER_USE or PER_USE_OR_RETURN.
@@ -54,15 +42,23 @@
     PER_ACCESSED(OBJ);                  \
 } while (0)
 
-static PyObject *sort_str, *reverse_str, *items_str, *__setstate___str;
+/*
+  The tp_name slots of the various BTree types contain the fully
+  qualified names of the types, e.g. zodb.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 "zodb.btrees." MOD_NAME_PREFIX "BTree."
+
+static PyObject *sort_str, *reverse_str, *__setstate___str,
+    *_bucket_type_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))
 
 #define MIN_BUCKET_ALLOC 16
@@ -90,6 +86,8 @@
 #ifdef PERSISTENT
 #define sizedcontainer_HEAD         \
     cPersistent_HEAD                \
+    PyObject *po_serial;            \
+    PyObject *po_weaklist;          \
     int size;                       \
     int len;
 #else
@@ -151,7 +149,8 @@
   BTreeItem *data;
 } BTree;
 
-staticforward PyExtensionClass BTreeType;
+static PyTypeObject BTreeType;
+static PyTypeObject BucketType;
 
 #define BTREE(O) ((BTree*)(O))
 
@@ -253,16 +252,16 @@
 static PyObject *
 IndexError(int i)
 {
-  PyObject *v;
+    PyObject *v;
 
-  v=PyInt_FromLong(i);
-  UNLESS (v) {
-    v=Py_None;
-    Py_INCREF(v);
-  }
-  PyErr_SetObject(PyExc_IndexError, v);
-  Py_DECREF(v);
-  return NULL;
+    v = PyInt_FromLong(i);
+    if (!v) {
+	v = Py_None;
+	Py_INCREF(v);
+    }
+    PyErr_SetObject(PyExc_IndexError, v);
+    Py_DECREF(v);
+    return NULL;
 }
 
 /* Search for the bucket immediately preceding *current, in the bucket chain
@@ -301,33 +300,45 @@
 }
 
 static void *
-PyMalloc(size_t sz)
+BTree_Malloc(size_t sz)
 {
-  void *r;
+    void *r;
 
-  ASSERT(sz > 0, "non-positive size malloc", NULL);
+    ASSERT(sz > 0, "non-positive size malloc", NULL);
 
-  if ((r = malloc(sz))) return r;
+    r = malloc(sz);
+    if (r)
+	return r;
 
-  PyErr_NoMemory();
-  return NULL;
+    PyErr_NoMemory();
+    return NULL;
 }
 
 static void *
-PyRealloc(void *p, size_t sz)
+BTree_Realloc(void *p, size_t sz)
 {
-  void *r;
+    void *r;
 
-  ASSERT(sz > 0, "non-positive size realloc", NULL);
+    ASSERT(sz > 0, "non-positive size realloc", NULL);
 
-  if (p) r = realloc(p,sz);
-  else r = malloc(sz);
+    if (p)
+	r = realloc(p, sz);
+    else
+	r = malloc(sz);
 
-  UNLESS (r) PyErr_NoMemory();
+    UNLESS (r)
+	PyErr_NoMemory();
 
-  return r;
+    return r;
 }
 
+/* Shared keyword-argument list for BTree/Bucket
+ * (iter)?(keys|values|items)
+ */
+static char *search_keywords[] = {"min", "max",
+				  "excludemin", "excludemax",
+				  0};
+
 #include "BTreeItemsTemplate.c"
 #include "BucketTemplate.c"
 #include "SetTemplate.c"
@@ -386,77 +397,99 @@
 BTREEITEMSTEMPLATE_C
 ;
 
-void
-INITMODULE (void)
+int
+init_persist_type(PyTypeObject *type)
 {
-  PyObject *m, *d, *c;
-
-  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;
+    type->ob_type = &PyType_Type;
+    type->tp_base = cPersistenceCAPI->pertype;
 
-  UNLESS (PyExtensionClassCAPI=PyCObject_Import("ExtensionClass","CAPI"))
-      return;
-
-#ifdef PERSISTENT
-  if ((cPersistenceCAPI=PyCObject_Import("Persistence.cPersistence","CAPI")))
-    {
-	BucketType.tp_getattro=cPersistenceCAPI->getattro;
-	BucketType.tp_setattro=cPersistenceCAPI->setattro;
+    if (PyType_Ready(type) < 0)
+	return 0;
 
-	SetType.tp_getattro=cPersistenceCAPI->getattro;
-	SetType.tp_setattro=cPersistenceCAPI->setattro;
-
-	BTreeType.tp_getattro=cPersistenceCAPI->getattro;
-	BTreeType.tp_setattro=cPersistenceCAPI->setattro;
-
-	TreeSetType.tp_getattro=cPersistenceCAPI->getattro;
-	TreeSetType.tp_setattro=cPersistenceCAPI->setattro;
-    }
-  else return;
-
-  /* Grab the ConflictError class */
+    return 1;
+}
 
-  m = PyImport_ImportModule("ZODB.POSException");
+void
+INITMODULE (void)
+{
+    PyObject *m, *d, *c;
 
-  if (m != NULL) {
+    sort_str = PyString_InternFromString("sort");
+    if (!sort_str)
+	return;
+    reverse_str = PyString_InternFromString("reverse");
+    if (!reverse_str)
+	return;
+    __setstate___str = PyString_InternFromString("__setstate__");
+    if (!__setstate___str)
+	return;
+    _bucket_type_str = PyString_InternFromString("_bucket_type");
+    if (!_bucket_type_str)
+	return;
+
+    /* Grab the ConflictError class */
+    m = PyImport_ImportModule("zodb.btrees.interfaces");
+    if (m != NULL) {
   	c = PyObject_GetAttrString(m, "BTreesConflictError");
   	if (c != NULL)
-  		ConflictError = c;
+	    ConflictError = c;
 	Py_DECREF(m);
-  }
+    }
 
-  if (ConflictError == NULL) {
+    if (ConflictError == NULL) {
   	Py_INCREF(PyExc_ValueError);
 	ConflictError=PyExc_ValueError;
-  }
-
-#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
+    /* Initialize the PyPersist_C_API and the type objects. */
+    cPersistenceCAPI = PyCObject_Import("Persistence.cPersistence", "CAPI");
+    if (cPersistenceCAPI == NULL)
+	return;
+
+    BTreeItemsType.ob_type = &PyType_Type;
+    BTreeIter_Type.ob_type = &PyType_Type;
+    BTreeIter_Type.tp_getattro = PyObject_GenericGetAttr;
+    BucketType.tp_new = PyType_GenericNew;
+    SetType.tp_new = PyType_GenericNew;
+    BTreeType.tp_new = PyType_GenericNew;
+    TreeSetType.tp_new = PyType_GenericNew;
+    if (!init_persist_type(&BucketType))
+	return;
+    if (!init_persist_type(&BTreeType))
+	return;
+    if (!init_persist_type(&SetType))
+	return;
+    if (!init_persist_type(&TreeSetType))
+	return;
+
+    if (PyDict_SetItem(BTreeType.tp_dict, _bucket_type_str,
+		       (PyObject *)&BucketType) < 0) {
+	fprintf(stderr, "btree failed\n");
+	return;
+    }
+    if (PyDict_SetItem(TreeSetType.tp_dict, _bucket_type_str,
+		       (PyObject *)&SetType) < 0) {
+	fprintf(stderr, "bucket failed\n");
+	return;
+    }
 
-  /* 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);
-
-  PyExtensionClass_Export(d,MOD_NAME_PREFIX "Bucket", BucketType);
-  PyExtensionClass_Export(d,MOD_NAME_PREFIX "BTree", BTreeType);
-  PyExtensionClass_Export(d,MOD_NAME_PREFIX "Set", SetType);
-  PyExtensionClass_Export(d,MOD_NAME_PREFIX "TreeSet", TreeSetType);
+    /* Create the module and add the functions */
+    m = Py_InitModule4("_zodb_btrees_" 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;
 }


=== ZODB3/BTrees/BTreeTemplate.c 1.74.10.1 => 1.74.10.2 === (1185/1585 lines abridged)
--- ZODB3/BTrees/BTreeTemplate.c:1.74.10.1	Tue Jul  1 15:34:08 2003
+++ ZODB3/BTrees/BTreeTemplate.c	Thu Jul  3 17:38:59 2003
@@ -145,7 +145,7 @@
  *      Py_None    No problem found.
  */
 static PyObject*
-BTree_check(BTree *self, PyObject *args)
+BTree_check(BTree *self)
 {
     PyObject *result = NULL;
     int i = BTree_check_inner(self, NULL);
@@ -225,6 +225,30 @@
   return _BTree_get(self, key, 0);
 }
 
+/* Create a new bucket for the BTree or TreeSet using the class attribute
+   _bucket_type, which is normally initialized to BucketType or SetType
+   as appropriate.
+*/
+static Sized *
+BTree_newBucket(BTree *self)
+{
+    PyObject *factory;
+    Sized *result;
+
+    /* _bucket_type_str defined in BTreeModuleTemplate.c */
+    factory = PyObject_GetAttr((PyObject *)self->ob_type, _bucket_type_str);
+    if (factory == NULL)
+	return NULL;
+    /* XXX Should we check that the factory actually returns something
+       of the appropriate type? How?  The C code here is going to
+       depend on any custom bucket type having the same layout at the
+       C level.
+    */
+    result = SIZED(PyObject_CallObject(factory, NULL));
+    Py_DECREF(factory);
+    return result;
+}
+
 /*
  * Move data from the current BTree, from index onward, to the newly created
  * BTree 'next'.  self and next must both be activated.  If index is OOB (< 0
@@ -250,7 +274,7 @@
     ASSERT(index > 0, "split creates empty tree", -1);
     ASSERT(next_size > 0, "split creates empty tree", -1);
 
-    next->data = PyMalloc(sizeof(BTreeItem) * next_size);
+    next->data = BTree_Malloc(sizeof(BTreeItem) * next_size);
     if (!next->data)
 	return -1;
     memcpy(next->data, self->data + index, sizeof(BTreeItem) * next_size);
@@ -269,7 +293,7 @@
 
     next->len = next_size;
     self->len = index;
-    return PER_CHANGED(self) < 0 ? -1 : 0;
+    return PER_CHANGED(self) >= 0 ? 0 : -1;
 }
 
 
@@ -297,7 +321,7 @@
     child = BTREE(PyObject_CallObject(OBJECT(self->ob_type), NULL));
     if (!child) return -1;
 
-    d = PyMalloc(sizeof(BTreeItem) * 2);
+    d = BTree_Malloc(sizeof(BTreeItem) * 2);
     if (!d) {
         Py_DECREF(child);
         return -1;
@@ -344,104 +368,85 @@
   Sized *v, *e = 0;
   BTreeItem *d;
 
-  if (self->len == self->size)
-    {
-      if (self->size)
-        {
-          d = PyRealloc(self->data, sizeof(BTreeItem) * self->size * 2);
-          if (d == NULL)
-            return -1;
+  if (self->len == self->size) {
+      if (self->size) {
+          d = BTree_Realloc(self->data, sizeof(BTreeItem) * self->size * 2);
+	  if (d == NULL)
+	      return -1;
           self->data = d;
           self->size *= 2;
-        }
-      else
-        {
-          d = PyMalloc(sizeof(BTreeItem) * 2);
-          if (d == NULL)
-            return -1;
+      }
+      else {
+          d = BTree_Malloc(sizeof(BTreeItem) * 2);
+	  if (d == NULL)
+	      return -1;
           self->data = d;
           self->size = 2;
-        }
-    }
+      }
+  }
 
-  if (self->len)
-    {
+  if (self->len) {
       d = self->data + index;
       v = d->child;
       /* Create a new object of the same type as the target value */
-      e = SIZED(PyObject_CallObject(OBJECT(v->ob_type), NULL));
-      UNLESS (e) return -1;
+      e = (Sized *)PyObject_CallObject((PyObject *)v->ob_type, NULL);
+      if (e == NULL)
+	  return -1;
 
-      UNLESS(PER_USE(v))
-        {
+      UNLESS(PER_USE(v)) {
           Py_DECREF(e);
           return -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));
-        }
+          i = BTree_split((BTree *)v, -1, (BTree *)e);
       else
-        {
-          i = bucket_split(BUCKET(v), -1, BUCKET(e));
-        }
+          i = bucket_split((Bucket *)v, -1, (Bucket *)e);
       PER_ALLOW_DEACTIVATION(v);
 
-      if (i < 0)
-        {
+      if (i < 0) {
           Py_DECREF(e);
+	  assert(PyErr_Occurred());
           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));
+	  memmove(d+1, d, sizeof(BTreeItem)*(self->len-index));
 
-      if (SameType_Check(self, v))
-        {
+      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
-        {
+      }
+      else {
           COPY_KEY(d->key, BUCKET(e)->keys[0]);
           INCREF_KEY(d->key);
-        }
+      }
       d->child = e;
-
       self->len++;
 
       if (self->len >= MAX_BTREE_SIZE(self) * 2)    /* the root is huge */
-        return BTree_split_root(self, noval);
-    }
-  else
-    {
+	  return BTree_split_root(self, noval);
+  }
+  else {
       /* The BTree is empty.  Create an empty bucket.  See CAUTION in
        * the comments preceding.
        */
       assert(index == 0);
       d = self->data;
-      if (noval)
-        {
-          d->child = SIZED(PyObject_CallObject(OBJECT(&SetType), NULL));
-          UNLESS (d->child) return -1;
-        }
-      else
-        {
-          d->child = SIZED(PyObject_CallObject(OBJECT(&BucketType), NULL));
-          UNLESS (d->child) return -1;
-        }
+      d->child = BTree_newBucket(self);
+      if (d->child == NULL)

[-=- -=- -=- 1185 lines omitted -=- -=- -=-]

+    {"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict,
+     METH_VARARGS,
+     "_p_resolveConflict() -- Reinitialize from a newly created copy"},
+
+    {"_p_deactivate", (PyCFunction) BTree__p_deactivate,	METH_KEYWORDS,
+     "_p_deactivate()\n\nReinitialize from a newly created copy."},
 #endif
-  {NULL,		NULL}		/* sentinel */
+    {NULL, NULL}
 };
 
+static int
+BTree_init(PyObject *self, PyObject *args, PyObject *kwds)
+{
+    PyObject *v = NULL;
+
+    if (!PyArg_ParseTuple(args, "|O:" MOD_NAME_PREFIX "BTree", &v))
+	return -1;
+
+    if (v)
+	return update_from_seq(self, v);
+    else
+	return 0;
+}
+
 static void
 BTree_dealloc(BTree *self)
 {
-  if (self->state != cPersistent_GHOST_STATE)
-    _BTree_clear(self);
+    if (self->po_weaklist != NULL)
+        PyObject_ClearWeakRefs((PyObject *)self);
+    Py_XDECREF(self->jar);
+    Py_XDECREF(self->oid);
+    self->jar = NULL;
+    if (self->state != cPersistent_GHOST_STATE)
+	_BTree_clear(self);
+    PyObject_GC_Del(self);
+}
+
+static int
+BTree_traverse(BTree *self, visitproc visit, void *arg)
+{
+    int err = 0;
+    int i, len;
+
+#define VISIT(SLOT)                             \
+    if (SLOT) {                                 \
+        err = visit((PyObject *)(SLOT), arg);   \
+        if (err)                                \
+            goto Done;                          \
+    }
+
+    if (self->ob_type == &BTreeType)
+	assert(self->ob_type->tp_dictoffset == 0);
+
+    /* Per_traverse isn't implementated yet. */
+    /* err = PyPersist_TYPE->tp_traverse((PyObject *)self, visit, arg); */
+    if (err)
+	goto Done;
+
+    /* If this is registered with the persistence system, cleaning up cycles
+     * is the database's problem.  It would be horrid to unghostify BTree
+     * nodes here just to chase pointers every time gc runs.
+     */
+    if (self->state == cPersistent_GHOST_STATE)
+	goto Done;
+
+    len = self->len;
+#ifdef KEY_TYPE_IS_PYOBJECT
+    /* Keys are Python objects so need to be traversed.  Note that the
+     * key 0 slot is unused and should not be traversed.
+     */
+    for (i = 1; i < len; i++)
+        VISIT(self->data[i].key);
+#endif
+
+    /* Children are always pointers, and child 0 is legit. */
+    for (i = 0; i < len; i++)
+        VISIT(self->data[i].child);
 
-  PER_DEL(self);
+    VISIT(self->firstbucket);
+
+Done:
+    return err;
 
-  Py_DECREF(self->ob_type);
-  PyObject_Del(self);
+#undef VISIT
+}
+
+static int
+BTree_tp_clear(BTree *self)
+{
+    /* Per_clear isn't implementated yet. */
+    /* PyPersist_TYPE->tp_clear((PyObject *)self); */
+    if (self->state != cPersistent_GHOST_STATE)
+	_BTree_clear(self);
+    return 0;
 }
 
 /*
@@ -1722,8 +2029,21 @@
   (objobjargproc)BTree_setitem,	        /*mp_ass_subscript*/
 };
 
+static PySequenceMethods BTree_as_sequence = {
+    (inquiry)0,                     /* sq_length */
+    (binaryfunc)0,                  /* sq_concat */
+    (intargfunc)0,                  /* sq_repeat */
+    (intargfunc)0,                  /* sq_item */
+    (intintargfunc)0,               /* sq_slice */
+    (intobjargproc)0,               /* sq_ass_item */
+    (intintobjargproc)0,            /* sq_ass_slice */
+    (objobjproc)BTree_contains,     /* sq_contains */
+    0,                              /* sq_inplace_concat */
+    0,                              /* sq_inplace_repeat */
+};
+
 static int
-BTree_nonzero( BTree *self)
+BTree_nonzero(BTree *self)
 {
   return BTree_length_or_nonzero(self, 1);
 }
@@ -1732,32 +2052,45 @@
   0,0,0,0,0,0,0,0,0,0,
   (inquiry)BTree_nonzero};
 
-static PyExtensionClass BTreeType = {
-  PyObject_HEAD_INIT(NULL)
-  0,				/*ob_size*/
-  MOD_NAME_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
-  | EXTENSIONCLASS_NOINSTDICT_FLAG,
+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 */
+    &BTree_as_sequence,			/* 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 */
+    (getiterfunc)BTree_getiter,		/* tp_iter */
+    0,					/* tp_iternext */
+    BTree_methods,			/* tp_methods */
+    BTree_members,			/* 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 */
+    0, /*PyType_GenericNew,*/		/* tp_new */
 };


=== ZODB3/BTrees/BucketTemplate.c 1.54.6.1 => 1.54.6.2 === (1265/1665 lines abridged)
--- ZODB3/BTrees/BucketTemplate.c:1.54.6.1	Tue Jul  1 15:34:08 2003
+++ ZODB3/BTrees/BucketTemplate.c	Thu Jul  3 17:38:59 2003
@@ -65,7 +65,7 @@
 **         has_key itself as a Python int.  A BTree caller generally passes
 **         the depth of the bucket for has_key, so a true result returns
 **         the bucket depth then.
-**         Note that has_key should be tree when searching set buckets.
+**         Note that has_key should be true when searching set buckets.
 **     If not has_key:
 **         If the key is present, returns the associated value, and the
 **         caller owns the reference.  Else returns NULL and sets KeyError.
@@ -83,7 +83,7 @@
     COPY_KEY_FROM_ARG(key, keyarg, copied);
     UNLESS (copied) return NULL;
 
-    PER_USE_OR_RETURN(self, NULL);
+    UNLESS (PER_USE(self)) return NULL;
 
     BUCKET_SEARCH(i, cmp, self, key, goto Done);
     if (has_key)
@@ -97,9 +97,9 @@
     }
 
 Done:
-  PER_ALLOW_DEACTIVATION(self);
-  PER_ACCESSED(self);
-  return r;
+    PER_UNUSE(self);
+    return r;
+
 }
 
 static PyObject *
@@ -126,49 +126,43 @@
 static int
 Bucket_grow(Bucket *self, int newsize, int noval)
 {
-  KEY_TYPE *keys;
-  VALUE_TYPE *values;
+    KEY_TYPE *keys;
+    VALUE_TYPE *values;
 
-  if (self->size)
-    {
-      if (newsize < 0)
-        newsize = self->size * 2;
-      if (newsize < 0)    /* int overflow */
-        goto Overflow;
-      UNLESS (keys = PyRealloc(self->keys, sizeof(KEY_TYPE) * newsize))
-        return -1;
+    if (self->size) {
+        if (newsize < 0)
+            newsize = self->size * 2;
+        if (newsize < 0)    /* int overflow */
+            goto Overflow;
+        UNLESS (keys = BTree_Realloc(self->keys, sizeof(KEY_TYPE) * newsize))
+            return -1;
 
-      UNLESS (noval)
-        {
-          values = PyRealloc(self->values, sizeof(VALUE_TYPE) * newsize);
-          if (values == NULL)
-            {
-              free(keys);
-              return -1;
+        UNLESS (noval) {
+            values = BTree_Realloc(self->values, sizeof(VALUE_TYPE) * newsize);
+            if (values == NULL) {
+                free(keys);
+                return -1;
             }
-          self->values = values;
+            self->values = values;
         }
-      self->keys = keys;
+        self->keys = keys;
     }
-  else
-    {
-      if (newsize < 0)
-        newsize = MIN_BUCKET_ALLOC;
-      UNLESS (self->keys = PyMalloc(sizeof(KEY_TYPE) * newsize))
-        return -1;
-      UNLESS (noval)
-        {
-          self->values = PyMalloc(sizeof(VALUE_TYPE) * newsize);
-          if (self->values == NULL)
-            {
-              free(self->keys);
-              self->keys = NULL;
-              return -1;
+    else {
+        if (newsize < 0)
+            newsize = MIN_BUCKET_ALLOC;
+        UNLESS (self->keys = BTree_Malloc(sizeof(KEY_TYPE) * newsize))
+            return -1;
+        UNLESS (noval) {
+            self->values = BTree_Malloc(sizeof(VALUE_TYPE) * newsize);
+            if (self->values == NULL) {
+                free(self->keys);
+                self->keys = NULL;
+                return -1;
             }
         }
     }
-  self->size = newsize;
-  return 0;
+    self->size = newsize;
+    return 0;
 
 Overflow:
   PyErr_NoMemory();
@@ -325,7 +319,7 @@
     	UNLESS(copied) return -1;
     }
 
-    PER_USE_OR_RETURN(self, -1);
+    UNLESS (PER_USE(self)) return -1;
 
     BUCKET_SEARCH(i, cmp, self, key, goto Done);
     if (cmp == 0) {
@@ -402,11 +396,11 @@
         goto Done;
 
     if (self->len > i) {
-        memmove(self->keys + i+1, self->keys + i,
-                sizeof(KEY_TYPE)*(self->len - i));
+        memmove(self->keys + i + 1, self->keys + i,
+                sizeof(KEY_TYPE) * (self->len - i));
         if (self->values) {
-            memmove(self->values + i+1, self->values + i,
-                    sizeof(VALUE_TYPE)*(self->len - i));
+            memmove(self->values + i + 1, self->values + i,
+                    sizeof(VALUE_TYPE) * (self->len - i));
         }
     }
 
@@ -425,8 +419,7 @@
         result = 1;
 
 Done:
-    PER_ALLOW_DEACTIVATION(self);
-    PER_ACCESSED(self);
+    PER_UNUSE(self);
     return result;
 }
 
@@ -445,85 +438,78 @@
 static int
 bucket_setitem(Bucket *self, PyObject *key, PyObject *v)
 {
-  if (_bucket_set(self, key, v, 0, 0, 0) < 0) return -1;
-  return 0;
+    if (_bucket_set(self, key, v, 0, 0, 0) < 0)
+	return -1;
+    return 0;
 }
 
 /**
- ** Mapping_update()
- **
- ** Accepts a sequence of 2-tuples or any object with an items()
- ** method that returns a sequence of 2-tuples.
- **
+ ** Accepts a sequence of 2-tuples, or any object with an items()
+ ** method that returns an iterable object producing 2-tuples.
  */
-
-static PyObject *
-Mapping_update(PyObject *self, PyObject *args)
+static int
+update_from_seq(PyObject *map, PyObject *seq)
 {
-  PyObject *seq=0, *o, *t, *v, *tb, *k, *items = NULL;
-  int i;
-
-  UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;
-
-  if (!seq)
-    {
-      Py_INCREF(Py_None);
-      return Py_None;
-    }
-
-  if (!PySequence_Check(seq))
-    {
-      items = PyObject_GetAttr(seq, items_str);
-      UNLESS(items) return NULL;
-      ASSIGN(items, PyObject_CallObject(items, NULL));
-      UNLESS(items) return NULL;
-      /* items is DECREFed on exit, seq is not */
-      seq = items;
-    }
+    PyObject *iter, *o, *k, *v;
+    int err = -1;
 
-  for (i=0; ; i++)
-    {
-      o = PySequence_GetItem(seq, i);
-      UNLESS (o)

[-=- -=- -=- 1265 lines omitted -=- -=- -=-]

+    len = self->len;
+    (void)i;    /* if neither keys nor values are PyObject*, "i" is otherwise
+                   unreferenced and we get a nuisance compiler wng */
+#ifdef KEY_TYPE_IS_PYOBJECT
+    /* Keys are Python objects so need to be traversed. */
+    for (i = 0; i < len; i++)
+        VISIT(self->keys[i]);
+#endif
+
+#ifdef VALUE_TYPE_IS_PYOBJECT
+    if (self->values != NULL) {
+        /* self->values exists (this is a mapping bucket, not a set bucket),
+         * and are Python objects, so need to be traversed. */
+        for (i = 0; i < len; i++)
+            VISIT(self->values[i]);
+    }
+#endif
+
+    VISIT(self->next);
+
+Done:
+    return err;
+
+#undef VISIT
+}
+
+int
+bucket_tp_clear(Bucket *self)
+{
+    /* XXX Per_clear isn't implemented yet. */
+    /* PyPersist_TYPE->tp_clear((PyObject *)self); */
+    if (self->state != cPersistent_GHOST_STATE)
+	_bucket_clear(self);
+    return 0;
 }
 
 /* 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);
-  PER_ACCESSED(self);
-  return r;
+    int r;
+    UNLESS (PER_USE(self)) return -1;
+    r = self->len;
+    PER_UNUSE(self);
+    return r;
 }
 
 static PyMappingMethods Bucket_as_mapping = {
@@ -1391,55 +1603,102 @@
   (objobjargproc)bucket_setitem,	/*mp_ass_subscript*/
 };
 
+static PySequenceMethods Bucket_as_sequence = {
+    (inquiry)0,                     /* sq_length */
+    (binaryfunc)0,                  /* sq_concat */
+    (intargfunc)0,                  /* sq_repeat */
+    (intargfunc)0,                  /* sq_item */
+    (intintargfunc)0,               /* sq_slice */
+    (intobjargproc)0,               /* sq_ass_item */
+    (intintobjargproc)0,            /* sq_ass_slice */
+    (objobjproc)bucket_contains,    /* sq_contains */
+    0,                              /* sq_inplace_concat */
+    0,                              /* sq_inplace_repeat */
+};
+
 static PyObject *
 bucket_repr(Bucket *self)
 {
-  static PyObject *format;
-  PyObject *r, *t;
-
-  UNLESS (format) UNLESS (format=PyString_FromString(MOD_NAME_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;
+    PyObject *i, *r;
+    char repr[10000];
+    int rv;
+
+    i = bucket_items(self, NULL, NULL);
+    if (!i)
+	return NULL;
+    r = PyObject_Repr(i);
+    Py_DECREF(i);
+    if (!r) {
+	return NULL;
+    }
+    rv = PyOS_snprintf(repr, sizeof(repr),
+		       "%s(%s)", self->ob_type->tp_name,
+		       PyString_AS_STRING(r));
+    if (rv > 0 && rv < sizeof(repr)) {
+	Py_DECREF(r);
+	return PyString_FromStringAndSize(repr, strlen(repr));
+    }
+    else {
+	/* The static buffer wasn't big enough */
+	int size;
+	PyObject *s;
+
+	/* 3 for the parens and the null byte */
+	size = strlen(self->ob_type->tp_name) + PyString_GET_SIZE(r) + 3;
+	s = PyString_FromStringAndSize(NULL, size);
+	if (!s) {
+	    Py_DECREF(r);
+	    return r;
+	}
+	PyOS_snprintf(PyString_AS_STRING(s), size,
+		      "%s(%s)", self->ob_type->tp_name, PyString_AS_STRING(r));
+	Py_DECREF(r);
+	return s;
+    }
 }
 
-static PyExtensionClass BucketType = {
-  PyObject_HEAD_INIT(NULL)
-  0,				/*ob_size*/
-  MOD_NAME_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
-  | EXTENSIONCLASS_NOINSTDICT_FLAG,
+static PyTypeObject BucketType = {
+    PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+    0,					/* ob_size */
+    MODULE_NAME MOD_NAME_PREFIX "Bucket",/* 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)bucket_repr,		/* tp_repr */
+    0,					/* tp_as_number */
+    &Bucket_as_sequence,		/* tp_as_sequence */
+    &Bucket_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)bucket_traverse,	/* tp_traverse */
+    (inquiry)bucket_tp_clear,		/* tp_clear */
+    0,					/* tp_richcompare */
+    offsetof(Bucket, po_weaklist),	/* tp_weaklistoffset */
+    (getiterfunc)Bucket_getiter,	/* tp_iter */
+    0,					/* tp_iternext */
+    Bucket_methods,			/* tp_methods */
+    Bucket_members,			/* 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 */
+    0, /*PyType_GenericNew,*/		/* tp_new */
 };
-
 
 static int
 nextBucket(SetIteration *i)


=== ZODB3/BTrees/MergeTemplate.c 1.16 => 1.16.18.1 ===
--- ZODB3/BTrees/MergeTemplate.c:1.16	Fri Jan 17 12:20:49 2003
+++ ZODB3/BTrees/MergeTemplate.c	Thu Jul  3 17:38:59 2003
@@ -21,18 +21,22 @@
 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]);
+    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;
+    r->len++;
+    return 0;
 }
 
+/* The "reason" argument is a little integer giving "a reason" for the
+ * error.  In the Zope3 codebase, these are mapped to explanatory strings
+ * via zodb/btrees/interfaces.py.
+ */
 static PyObject *
 merge_error(int p1, int p2, int p3, int reason)
 {
@@ -40,7 +44,7 @@
 
   UNLESS (r=Py_BuildValue("iiii", p1, p2, p3, reason)) r=Py_None;
   if (ConflictError == NULL) {
-  	ConflictError=PyExc_ValueError;
+  	ConflictError = PyExc_ValueError;
 	Py_INCREF(ConflictError);
   }
   PyErr_SetObject(ConflictError, r);
@@ -52,6 +56,33 @@
   return NULL;
 }
 
+/* It's hard to explain "the rules" for bucket_merge, in large part because
+ * any automatic conflict-resolution scheme is going to be incorrect for
+ * some endcases of *some* app.  The scheme here is pretty conservative,
+ * and should be OK for most apps.  It's easier to explain what the code
+ * allows than what it forbids:
+ *
+ * Leaving things alone:  it's OK if both s2 and s3 leave a piece of s1
+ * alone (don't delete the key, and don't change the value).
+ *
+ * Key deletion:  a transaction (s2 or s3) can delete a key (from s1), but
+ * only if the other transaction (of s2 and s3) doesn't delete the same key.
+ * However, it's not OK for s2 and s3 to, between them, end up deleting all
+ * the keys.  This is a higher-level constraint, due to that the caller of
+ * bucket_merge() doesn't have enough info to unlink the resulting empty
+ * bucket from its BTree correctly.
+ *
+ * Key insertion:  s2 or s3 can add a new key, provided the other transaction
+ * doesn't insert the same key.  It's not OK even if they insert the same
+ * <key, value> pair.
+ *
+ * Mapping value modification:  s2 or s3 can modify the value associated
+ * with a key in s1, provided the other transaction doesn't make a
+ * modification of the same key to a different value.  It's OK if s2 and s3
+ * both give the same new value to the key (XXX while it's hard to be
+ * precise about why, this doesn't seem consistent with that it's *not* OK
+ * for both to add a new key mapping to the same value).
+ */
 static PyObject *
 bucket_merge(Bucket *s1, Bucket *s2, Bucket *s3)
 {
@@ -60,28 +91,34 @@
   SetIteration i1 = {0,0,0}, i2 = {0,0,0}, i3 = {0,0,0};
   int cmp12, cmp13, cmp23, mapping, set;
 
-  if (initSetIteration(&i1, OBJECT(s1), 1) < 0) goto err;
-  if (initSetIteration(&i2, OBJECT(s2), 1) < 0) goto err;
-  if (initSetIteration(&i3, OBJECT(s3), 1) < 0) goto err;
+  if (initSetIteration(&i1, OBJECT(s1), 1) < 0)
+      goto err;
+  if (initSetIteration(&i2, OBJECT(s2), 1) < 0)
+      goto err;
+  if (initSetIteration(&i3, OBJECT(s3), 1) < 0)
+      goto err;
 
   mapping = i1.usesValue | i2.usesValue | i3.usesValue;
-  set = ! mapping;
+  set = !mapping;
 
   if (mapping)
-    {
-      UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&BucketType), NULL)))
-        goto err;
-    }
+      r = (Bucket *)PyObject_CallObject((PyObject *)&BucketType, NULL);
   else
-    {
-      UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&SetType), NULL)))
-        goto err;
-    }
+      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;
+  if (i1.next(&i1) < 0)
+      goto err;
+  if (i2.next(&i2) < 0)
+      goto err;
+  if (i3.next(&i3) < 0)
+      goto err;
 
+  /* Consult zodb/btrees/interfaces.py for the meaning of the last
+   * argument passed to merge_error().
+   */
+  /* XXX This isn't passing on errors raised by value comparisons. */
   while (i1.position >= 0 && i2.position >= 0 && i3.position >= 0)
     {
       TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
@@ -91,15 +128,15 @@
           if (cmp13==0)
             {
               if (set || (TEST_VALUE(i1.value, i2.value) == 0))
-                {               /* change in i3 or all same */
+                {               /* change in i3 value 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 */
+                {               /* change in i2 value */
                   if (merge_output(r, &i2, mapping) < 0) goto err;
                 }
               else
-                {               /* conflicting changes in i2 and i3 */
+                {               /* conflicting value changes in i2 and i3 */
                   merge_error(i1.position, i2.position, i3.position, 1);
                   goto err;
                 }
@@ -113,7 +150,7 @@
               if (i3.next(&i3) < 0) goto err;
             }
           else if (set || (TEST_VALUE(i1.value, i2.value) == 0))
-            {                   /* delete i3 */
+            {                   /* deleted in i3 */
               if (i1.next(&i1) < 0) goto err;
               if (i2.next(&i2) < 0) goto err;
             }
@@ -131,7 +168,7 @@
               if (i2.next(&i2) < 0) goto err;
             }
           else if (set || (TEST_VALUE(i1.value, i3.value) == 0))
-            {                   /* delete i2 */
+            {                   /* deleted in i2 */
               if (i1.next(&i1) < 0) goto err;
               if (i3.next(&i3) < 0) goto err;
             }
@@ -145,7 +182,7 @@
         {                       /* Both keys changed */
           TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
           if (cmp23==0)
-            {                   /* dualing inserts or deletes */
+            {                   /* dueling inserts or deletes */
               merge_error(i1.position, i2.position, i3.position, 4);
               goto err;
             }
@@ -168,8 +205,8 @@
               if (i3.next(&i3) < 0) goto err;
             }
           else
-            {                   /* Dueling deletes */
-              merge_error(i1.position, i2.position, i3.position, 5);
+            {                   /* 1<2 and 1<3:  both deleted 1.key */
+	      merge_error(i1.position, i2.position, i3.position, 5);
               goto err;
             }
         }
@@ -179,7 +216,7 @@
     {                           /* New inserts */
       TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
       if (cmp23==0)
-        {                       /* dualing inserts */
+        {                       /* dueling inserts */
           merge_error(i1.position, i2.position, i3.position, 6);
           goto err;
         }
@@ -196,7 +233,7 @@
     }
 
   while (i1.position >= 0 && i2.position >= 0)
-    {                           /* deleting i3 */
+    {                           /* remainder of i1 deleted in i3 */
       TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
       if (cmp12 > 0)
         {                       /* insert i2 */
@@ -209,14 +246,14 @@
           if (i2.next(&i2) < 0) goto err;
         }
       else
-        {                       /* Dualing deletes or delete and change */
+        {                       /* 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 */
+    {                           /* remainder of i1 deleted in i2 */
       TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
       if (cmp13 > 0)
         {                       /* insert i3 */
@@ -229,7 +266,7 @@
           if (i3.next(&i3) < 0) goto err;
         }
       else
-        {                       /* Dualing deletes or delete and change */
+        {                       /* Dueling deletes or delete and change */
           merge_error(i1.position, i2.position, i3.position, 8);
           goto err;
         }
@@ -248,7 +285,7 @@
     }
 
   while (i3.position >= 0)
-    {                           /* Inserting i2 at end */
+    {                           /* Inserting i3 at end */
       if (merge_output(r, &i3, mapping) < 0) goto err;
       if (i3.next(&i3) < 0) goto err;
     }
@@ -271,7 +308,7 @@
       Py_INCREF(s1->next);
       r->next = s1->next;
     }
-  s=bucket_getstate(r, NULL);
+  s = bucket_getstate(r);
   Py_DECREF(r);
 
   return s;


=== ZODB3/BTrees/SetOpTemplate.c 1.29 => 1.29.92.1 ===
--- ZODB3/BTrees/SetOpTemplate.c:1.29	Thu Jun 27 18:24:16 2002
+++ ZODB3/BTrees/SetOpTemplate.c	Thu Jul  3 17:39:00 2003
@@ -18,33 +18,6 @@
 
 #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;
-          PER_ACCESSED(INTSET(i->set));
-        }
-
-      PER_ALLOW_DEACTIVATION(INTSET(i->set));
-    }
-
-
-  return 0;
-}
-#endif
-
 #ifdef KEY_CHECK
 static int
 nextKeyAsSet(SetIteration *i)
@@ -103,7 +76,7 @@
   i->position = -1;     /* set to 0 only on normal return */
   i->usesValue = 0;     /* assume it's a set or that values aren't iterated */
 
-  if (ExtensionClassSubclassInstance_Check(s, &BucketType))
+  if (PyObject_IsInstance(s, (PyObject *)&BucketType))
     {
       i->set = s;
       Py_INCREF(s);
@@ -116,15 +89,15 @@
       else
         i->next = nextSet;
     }
-  else if (ExtensionClassSubclassInstance_Check(s, &SetType))
+  else if (PyObject_IsInstance(s, (PyObject *)&SetType))
     {
       i->set = s;
       Py_INCREF(s);
       i->next = nextSet;
     }
-  else if (ExtensionClassSubclassInstance_Check(s, &BTreeType))
+  else if (PyObject_IsInstance(s, (PyObject *)&BTreeType))
     {
-      i->set = BTree_rangeSearch(BTREE(s), NULL, 'i');
+      i->set = BTree_rangeSearch(BTREE(s), NULL, NULL, 'i');
       UNLESS(i->set) return -1;
 
       if (useValues)
@@ -135,20 +108,12 @@
       else
         i->next = nextTreeSetItems;
     }
-  else if (ExtensionClassSubclassInstance_Check(s, &TreeSetType))
+  else if (PyObject_IsInstance(s, (PyObject *)&TreeSetType))
     {
-      i->set = BTree_rangeSearch(BTREE(s), NULL, 'k');
+      i->set = BTree_rangeSearch(BTREE(s), NULL, NULL, 'k');
       UNLESS(i->set) return -1;
       i->next = nextTreeSetItems;
     }
-#ifdef INTSET_H
-  else if (s->ob_type == (PyTypeObject*)intSetType)
-    {
-      i->set = s;
-      Py_INCREF(s);
-      i->next = nextIntSet;
-    }
-#endif
 #ifdef KEY_CHECK
   else if (KEY_CHECK(s))
     {
@@ -244,7 +209,7 @@
 #ifndef MERGE
       if (c12 && i1.usesValue && i2.usesValue) goto invalid_set_operation;
 #endif
-      if (! i1.usesValue && i2.usesValue)
+      if (! i1.usesValue&& i2.usesValue)
         {
           SetIteration t;
           int i;
@@ -339,6 +304,7 @@
   if(c1 && copyRemaining(r, &i1, merge, w1) < 0) goto err;
   if(c2 && copyRemaining(r, &i2, merge, w2) < 0) goto err;
 
+
   finiSetIteration(&i1);
   finiSetIteration(&i2);
 
@@ -383,7 +349,7 @@
 
   UNLESS(PyArg_ParseTuple(args, "OO", &o1, &o2)) return NULL;
 
-  if (o1==Py_None)
+  if (o1 == Py_None)
     {
       Py_INCREF(o2);
       return o2;
@@ -552,5 +518,4 @@
     finiSetIteration(&setiter);
     return NULL;
 }
-
 #endif


=== ZODB3/BTrees/SetTemplate.c 1.16.52.1 => 1.16.52.2 ===
--- ZODB3/BTrees/SetTemplate.c:1.16.52.1	Tue Jul  1 15:34:08 2003
+++ ZODB3/BTrees/SetTemplate.c	Thu Jul  3 17:39:00 2003
@@ -2,14 +2,14 @@
 
   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"
@@ -25,39 +25,64 @@
   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=0, *o, *t, *v, *tb;
-  int i, n=0, ind;
+    PyObject *seq = NULL;
+    int n = 0;
 
-  UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;
+    if (!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;
-        }
+    if (seq) {
+	n = _Set_update(self, seq);
+	if (n < 0)
+	    return NULL;
     }
 
-  return PyInt_FromLong(n);
+    return PyInt_FromLong(n);
 }
 
 static PyObject *
@@ -96,14 +121,14 @@
       Py_DECREF(self->next);
       self->next=0;
     }
-  
+
   if (l > self->size)
     {
-      UNLESS (keys=PyRealloc(self->keys, sizeof(KEY_TYPE)*l)) return -1;
+      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);
@@ -130,10 +155,10 @@
 
   UNLESS (PyArg_ParseTuple(args, "O", &args)) return NULL;
 
-  PER_PREVENT_DEACTIVATION(self); 
+  PER_PREVENT_DEACTIVATION(self);
   r=_set_setstate(self, args);
   PER_ALLOW_DEACTIVATION(self);
-  PER_ACCESSED(self);
+  PyPersist_SetATime(self);
 
   if (r < 0) return NULL;
   Py_INCREF(Py_None);
@@ -143,51 +168,76 @@
 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",	(PyCFunction) bucket_keys,	METH_KEYWORDS,
      "keys() -- Return the keys"},
-  {"has_key",	(PyCFunction) bucket_has_key,	METH_VARARGS,
+
+  {"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]) -- Find the maximum key\n\n"
    "If an argument is given, find the maximum <= the argument"},
+
   {"minKey", (PyCFunction) Bucket_minKey,	METH_VARARGS,
    "minKey([key]) -- Find 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", (PyCFunction) bucket__p_deactivate, METH_KEYWORDS,
    "_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 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));
+  if (!format)
+      format = PyString_FromString(MOD_NAME_PREFIX "Set(%s)");
+  UNLESS (t = PyTuple_New(1)) return NULL;
+  UNLESS (r = bucket_keys(self, NULL, NULL)) goto err;
+  PyTuple_SET_ITEM(t, 0, r);
+  r = t;
+  ASSIGN(r, PyString_Format(format, r));
   return r;
 err:
   Py_DECREF(t);
@@ -195,14 +245,14 @@
 }
 
 static int
-set_length(Bucket *self) 
+set_length(Bucket *self)
 {
   int r;
 
   PER_USE_OR_RETURN(self, -1);
   r = self->len;
   PER_ALLOW_DEACTIVATION(self);
-  PER_ACCESSED(self);
+  PyPersist_SetATime(self);
 
   return r;
 }
@@ -221,55 +271,71 @@
     IndexError(index);
 
   PER_ALLOW_DEACTIVATION(self);
-  PER_ACCESSED(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*/
+	(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 */
+        (objobjproc)bucket_contains,    /* sq_contains */
+        0,                              /* sq_inplace_concat */
+        0,                              /* sq_inplace_repeat */
 };
 
-static PyExtensionClass SetType = {
-  PyObject_HEAD_INIT(NULL)
-  0,				/*ob_size*/
-  MOD_NAME_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 
-  | EXTENSIONCLASS_NOINSTDICT_FLAG,
+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 */
+    (getiterfunc)Bucket_getiter,	/* tp_iter */
+    0,					/* tp_iternext */
+    Set_methods,			/* tp_methods */
+    Bucket_members,			/* 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 */
+    0, /*PyType_GenericNew,*/		/* tp_new */
 };
 
-static int 
+static int
 nextSet(SetIteration *i)
 {
-          
+
   if (i->position >= 0)
     {
       UNLESS(PER_USE(BUCKET(i->set))) return -1;
@@ -288,12 +354,12 @@
       else
         {
           i->position = -1;
-          PER_ACCESSED(BUCKET(i->set));
+          PyPersist_SetATime(BUCKET(i->set));
         }
 
       PER_ALLOW_DEACTIVATION(BUCKET(i->set));
     }
 
-          
+
   return 0;
 }


=== ZODB3/BTrees/TreeSetTemplate.c 1.15.52.1 => 1.15.52.2 ===
--- ZODB3/BTrees/TreeSetTemplate.c:1.15.52.1	Tue Jul  1 15:34:08 2003
+++ ZODB3/BTrees/TreeSetTemplate.c	Thu Jul  3 17:39:00 2003
@@ -17,47 +17,75 @@
 static PyObject *
 TreeSet_insert(BTree *self, PyObject *args)
 {
-  PyObject *key;
-  int i;
+    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);
+    if (!PyArg_ParseTuple(args, "O:insert", &key)) 
+	return NULL;
+    i = _BTree_set(self, key, Py_None, 1, 1);
+    if (i < 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=0, *o, *t, *v, *tb;
-  int i, n=0, ind;
+    PyObject *seq = NULL;
+    int n = 0;
 
-  UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;
+    if (!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;
-        }
+    if (seq) {
+	n = _TreeSet_update(self, seq);
+	if (n < 0)
+	    return NULL;
     }
 
-  return PyInt_FromLong(n);
+    return PyInt_FromLong(n);
 }
 
 
@@ -82,7 +110,7 @@
   PER_PREVENT_DEACTIVATION(self);
   r=_BTree_setstate(self, args, 1);
   PER_ALLOW_DEACTIVATION(self);
-  PER_ACCESSED(self);
+  PyPersist_SetATime(self);
 
   if (r < 0) return NULL;
   Py_INCREF(Py_None);
@@ -90,37 +118,54 @@
 }
 
 static struct PyMethodDef TreeSet_methods[] = {
-  {"__getstate__", (PyCFunction) BTree_getstate,	METH_VARARGS,
-   "__getstate__() -- Return the picklable state of the object"},
+  {"__getstate__", (PyCFunction) BTree_getstate,	METH_NOARGS,
+   "__getstate__() -> state\n\n"
+   "Return the picklable state of the TreeSet."},
+
   {"__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"},
+   "__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_KEYWORDS,
+   "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([key]) -- Find the maximum key\n\n"
-   "If an argument is given, find the maximum <= the argument"},
+   "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([key]) -- Find 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"},
+   "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(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"},
+   "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"},
-  {"_check", (PyCFunction) BTree_check,         METH_VARARGS,
+
+  {"_check", (PyCFunction) BTree_check,       METH_NOARGS,
    "Perform sanity check on TreeSet, and raise exception if flawed."},
+
 #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"},
+
+  {"_p_deactivate", (PyCFunction) BTree__p_deactivate,	METH_KEYWORDS,
+   "_p_deactivate()\n\nReinitialize from a newly created copy."},
 #endif
   {NULL,		NULL}		/* sentinel */
 };
@@ -129,32 +174,72 @@
   (inquiry)BTree_length,		/*mp_length*/
 };
 
-static PyExtensionClass TreeSetType = {
-  PyObject_HEAD_INIT(NULL)
-  0,				/*ob_size*/
-  MOD_NAME_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*/
-  &TreeSet_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,
-  "Set implemented as sorted tree of items",
-  METHOD_CHAIN(TreeSet_methods),
-  EXTENSIONCLASS_BASICNEW_FLAG
-  | EXTENSIONCLASS_NOINSTDICT_FLAG,
+static PySequenceMethods TreeSet_as_sequence = {
+    (inquiry)0,                     /* sq_length */
+    (binaryfunc)0,                  /* sq_concat */
+    (intargfunc)0,                  /* sq_repeat */
+    (intargfunc)0,                  /* sq_item */
+    (intintargfunc)0,               /* sq_slice */
+    (intobjargproc)0,               /* sq_ass_item */
+    (intintobjargproc)0,            /* sq_ass_slice */
+    (objobjproc)BTree_contains,     /* sq_contains */
+    0,                              /* sq_inplace_concat */
+    0,                              /* sq_inplace_repeat */
+};
+
+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 */
+    &TreeSet_as_sequence,		/* 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 */
+    (getiterfunc)BTree_getiter,		/* tp_iter */
+    0,					/* tp_iternext */
+    TreeSet_methods,			/* tp_methods */
+    BTree_members,			/* 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 */
+    0, /*PyType_GenericNew,*/		/* tp_new */
 };


=== ZODB3/BTrees/_IIBTree.c 1.7 => 1.7.92.1 ===
--- ZODB3/BTrees/_IIBTree.c:1.7	Mon Jun 24 22:00:55 2002
+++ ZODB3/BTrees/_IIBTree.c	Thu Jul  3 17:39:00 2003
@@ -11,8 +11,4 @@
 
 #include "intkeymacros.h"
 #include "intvaluemacros.h"
-#include "cPersistence.h"
-#ifndef EXCLUDE_INTSET_SUPPORT
-#include "BTree/intSet.h"
-#endif
 #include "BTreeModuleTemplate.c"


=== ZODB3/BTrees/_IOBTree.c 1.5 => 1.5.150.1 ===
--- ZODB3/BTrees/_IOBTree.c:1.5	Thu Feb 21 16:41:17 2002
+++ ZODB3/BTrees/_IOBTree.c	Thu Jul  3 17:39:00 2003
@@ -10,8 +10,4 @@
                                 
 #include "intkeymacros.h"
 #include "objectvaluemacros.h"
-#include "cPersistence.h"
-#ifndef EXCLUDE_INTSET_SUPPORT
-#include "BTree/intSet.h"
-#endif
 #include "BTreeModuleTemplate.c"


=== ZODB3/BTrees/_OIBTree.c 1.2 => 1.2.268.1 ===


=== ZODB3/BTrees/_OOBTree.c 1.2 => 1.2.268.1 ===


=== ZODB3/BTrees/_fsBTree.c 1.6 => 1.6.10.1 ===
--- ZODB3/BTrees/_fsBTree.c:1.6	Fri Apr  4 16:41:54 2003
+++ ZODB3/BTrees/_fsBTree.c	Thu Jul  3 17:39:00 2003
@@ -10,7 +10,6 @@
 typedef unsigned char char2[2];
 typedef unsigned char char6[6];
 
-
 /* Setup template macros */
 
 #define MASTER_ID "$Id$\n"
@@ -21,7 +20,7 @@
 #define INITMODULE init_fsBTree
 #define DEFAULT_MAX_BUCKET_SIZE 500
 #define DEFAULT_MAX_BTREE_SIZE 500
-                
+
 /*#include "intkeymacros.h"*/
 
 #define KEYMACROS_H "$Id$\n"
@@ -36,14 +35,13 @@
 #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; } 
+      (STATUS)=0; }
 
 /*#include "intvaluemacros.h"*/
 #define VALUEMACROS_H "$Id$\n"
 #define VALUE_TYPE char6
 #undef VALUE_TYPE_IS_PYOBJECT
 #define TEST_VALUE(K, T) memcmp(K,T,6)
-#define DECLARE_VALUE(NAME) VALUE_TYPE NAME
 #define DECREF_VALUE(k)
 #define INCREF_VALUE(k)
 #define COPY_VALUE(V, E) (memcpy(V, E, 6))
@@ -52,7 +50,7 @@
   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; } 
-  
+      (STATUS)=0; }
+
 #define NORMALIZE_VALUE(V, MIN)
 #include "BTreeModuleTemplate.c"


=== ZODB3/BTrees/sorters.c 1.4 => 1.4.94.1 ===