[Zope-Checkins] CVS: ZODB3/BTrees - sorters.c:1.4.112.1
_fsBTree.c:1.7.4.1 __init__.py:1.5.168.1 _OOBTree.c:1.2.286.1
_OIBTree.c:1.2.286.1 _IOBTree.c:1.5.168.1
_IIBTree.c:1.7.110.1 TreeSetTemplate.c:1.15.66.1
SetTemplate.c:1.16.66.1 SetOpTemplate.c:1.29.110.1
OOBTree.py:1.8.32.1 OIBTree.py:1.8.32.1
MergeTemplate.c:1.16.32.1 Length.py:1.6.106.1
Interfaces.py:1.18.110.1 IOBTree.py:1.7.32.1
IIBTree.py:1.7.32.1 BucketTemplate.c:1.54.20.1
BTreeTemplate.c:1.74.24.1 BTreeModuleTemplate.c:1.37.110.1
BTreeItemsTemplate.c:1.19.30.1
Jeremy Hylton
jeremy at zope.com
Tue Dec 23 14:06:54 EST 2003
Update of /cvs-repository/ZODB3/BTrees
In directory cvs.zope.org:/tmp/cvs-serv26665/BTrees
Modified Files:
Tag: ZODB3-mvcc-2-branch
sorters.c _fsBTree.c __init__.py _OOBTree.c _OIBTree.c
_IOBTree.c _IIBTree.c TreeSetTemplate.c SetTemplate.c
SetOpTemplate.c OOBTree.py OIBTree.py MergeTemplate.c
Length.py Interfaces.py IOBTree.py IIBTree.py BucketTemplate.c
BTreeTemplate.c BTreeModuleTemplate.c BTreeItemsTemplate.c
Log Message:
Merge the head to the mvcc branch.
This merge should be the final preparation for merging the branch to
the trunk.
=== ZODB3/BTrees/sorters.c 1.4 => 1.4.112.1 ===
=== ZODB3/BTrees/_fsBTree.c 1.7 => 1.7.4.1 ===
--- ZODB3/BTrees/_fsBTree.c:1.7 Wed Sep 3 13:14:25 2003
+++ ZODB3/BTrees/_fsBTree.c Tue Dec 23 14:06:21 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/__init__.py 1.5 => 1.5.168.1 ===
--- ZODB3/BTrees/__init__.py:1.5 Thu Feb 21 16:41:17 2002
+++ ZODB3/BTrees/__init__.py Tue Dec 23 14:06:21 2003
@@ -1,12 +1,15 @@
-import ZODB
-
-try: import intSet
-except: pass
-else: del intSet
+try:
+ import intSet
+except:
+ pass
+else:
+ del intSet
# Register interfaces
-try: import Interface
-except ImportError: pass # Don't register interfaces if no scarecrow
+try:
+ import Interface
+except ImportError:
+ pass # Don't register interfaces if no scarecrow
else:
import Interfaces
del Interfaces
=== ZODB3/BTrees/_OOBTree.c 1.2 => 1.2.286.1 ===
=== ZODB3/BTrees/_OIBTree.c 1.2 => 1.2.286.1 ===
=== ZODB3/BTrees/_IOBTree.c 1.5 => 1.5.168.1 ===
--- ZODB3/BTrees/_IOBTree.c:1.5 Thu Feb 21 16:41:17 2002
+++ ZODB3/BTrees/_IOBTree.c Tue Dec 23 14:06:21 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/_IIBTree.c 1.7 => 1.7.110.1 ===
--- ZODB3/BTrees/_IIBTree.c:1.7 Mon Jun 24 22:00:55 2002
+++ ZODB3/BTrees/_IIBTree.c Tue Dec 23 14:06:21 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/TreeSetTemplate.c 1.15 => 1.15.66.1 ===
--- ZODB3/BTrees/TreeSetTemplate.c:1.15 Fri Oct 4 20:39:57 2002
+++ ZODB3/BTrees/TreeSetTemplate.c Tue Dec 23 14:06:21 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);
}
@@ -81,8 +109,7 @@
PER_PREVENT_DEACTIVATION(self);
r=_BTree_setstate(self, args, 1);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
if (r < 0) return NULL;
Py_INCREF(Py_None);
@@ -90,37 +117,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,35 +173,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
-#ifdef PERSISTENT
- | PERSISTENT_TYPE_FLAG
-#endif
- | 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 */
+ 0, /* 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/SetTemplate.c 1.16 => 1.16.66.1 ===
--- ZODB3/BTrees/SetTemplate.c:1.16 Fri Oct 4 20:39:57 2002
+++ ZODB3/BTrees/SetTemplate.c Tue Dec 23 14:06:21 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,9 @@
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);
+ PER_UNUSE(self);
if (r < 0) return NULL;
Py_INCREF(Py_None);
@@ -143,51 +167,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 +244,13 @@
}
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);
+ PER_UNUSE(self);
return r;
}
@@ -220,59 +268,71 @@
else
IndexError(index);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(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
-#ifdef PERSISTENT
- | PERSISTENT_TYPE_FLAG
-#endif
- | 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 */
+ 0, /* 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;
@@ -297,6 +357,6 @@
PER_ALLOW_DEACTIVATION(BUCKET(i->set));
}
-
+
return 0;
}
=== ZODB3/BTrees/SetOpTemplate.c 1.29 => 1.29.110.1 ===
--- ZODB3/BTrees/SetOpTemplate.c:1.29 Thu Jun 27 18:24:16 2002
+++ ZODB3/BTrees/SetOpTemplate.c Tue Dec 23 14:06:21 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/OOBTree.py 1.8 => 1.8.32.1 ===
--- ZODB3/BTrees/OOBTree.py:1.8 Tue Feb 18 14:05:18 2003
+++ ZODB3/BTrees/OOBTree.py Tue Dec 23 14:06:21 2003
@@ -14,8 +14,3 @@
# hack to overcome dynamic-linking headache.
from _OOBTree import *
-
-# We don't really want _ names in pickles, so update all of the __module__
-# references.
-for obj in OOBucket, OOBTree, OOSet, OOTreeSet:
- obj.__module__ = __name__
=== ZODB3/BTrees/OIBTree.py 1.8 => 1.8.32.1 ===
--- ZODB3/BTrees/OIBTree.py:1.8 Tue Feb 18 14:05:18 2003
+++ ZODB3/BTrees/OIBTree.py Tue Dec 23 14:06:21 2003
@@ -14,8 +14,3 @@
# hack to overcome dynamic-linking headache.
from _OIBTree import *
-
-# We don't really want _ names in pickles, so update all of the __module__
-# references.
-for obj in OIBucket, OIBTree, OISet, OITreeSet:
- obj.__module__ = __name__
=== ZODB3/BTrees/MergeTemplate.c 1.16 => 1.16.32.1 ===
--- ZODB3/BTrees/MergeTemplate.c:1.16 Fri Jan 17 12:20:49 2003
+++ ZODB3/BTrees/MergeTemplate.c Tue Dec 23 14:06:21 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/Length.py 1.6 => 1.6.106.1 ===
--- ZODB3/BTrees/Length.py:1.6 Wed Aug 14 17:32:23 2002
+++ ZODB3/BTrees/Length.py Tue Dec 23 14:06:21 2003
@@ -12,32 +12,47 @@
#
##############################################################################
-import Persistence
+import persistent
-class Length(Persistence.Persistent):
+class Length(persistent.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.
+ As a bonus, the object support application-level conflict
+ resolution.
+
+ It is tempting to to assign length objects to __len__ attributes
+ to provide instance-specific __len__ methods. However, this no
+ longer works as expected, because new-style classes cache
+ class-defined slot methods (like __len__) in C type slots. Thus,
+ instance-define slot fillers are ignores.
+
"""
- def __init__(self, v=0): self.value=v
+ def __init__(self, v=0):
+ self.value = v
- def __getstate__(self): return self.value
+ def __getstate__(self):
+ return self.value
- def __setstate__(self, v): self.value=v
+ def __setstate__(self, v):
+ self.value = v
- def set(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_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 change(self, delta):
+ self.value += delta
- def __call__(self, *args): return self.value
+ def __call__(self, *args):
+ return self.value
=== ZODB3/BTrees/Interfaces.py 1.18 => 1.18.110.1 ===
--- ZODB3/BTrees/Interfaces.py:1.18 Tue Jun 25 18:46:42 2002
+++ ZODB3/BTrees/Interfaces.py Tue Dec 23 14:06:21 2003
@@ -348,6 +348,38 @@
Note that c1 and c2 must be collections.
"""
+class IMergeIntegerKey(IMerge):
+ """IMerge-able objects with integer keys.
+
+ Concretely, this means the types in IOBTree and IIBTree.
+ """
+
+ def multiunion(seq):
+ """Return union of (zero or more) integer sets, as an integer set.
+
+ seq is a sequence of objects each convertible to an integer set.
+ These objects are convertible to an integer set:
+
+ + An integer, which is added to the union.
+
+ + A Set or TreeSet from the same module (for example, an
+ IIBTree.TreeSet for IIBTree.multiunion()). The elements of the
+ set are added to the union.
+
+ + A Bucket or BTree from the same module (for example, an
+ IOBTree.IOBTree for IOBTree.multiunion()). The keys of the
+ mapping are added to the union.
+
+ The union is returned as a Set from the same module (for example,
+ IIBTree.multiunion() returns an IIBTree.IISet).
+
+ The point to this method is that it can run much faster than
+ doing a sequence of two-input union() calls. Under the covers,
+ all the integers in all the inputs are sorted via a single
+ linear-time radix sort, then duplicates are removed in a second
+ linear-time pass.
+ """
+
###############################################################
# IMPORTANT NOTE
#
@@ -359,7 +391,10 @@
#
################################################################
-OOBTree.OOSet.__implements__=ISet
-OOBTree.OOTreeSet.__implements__=ITreeSet
-OOBTree.OOBucket.__implements__=IDictionaryIsh
-OOBTree.OOBTree.__implements__=IBTree
+# XXX Need to use the new declaration syntax once it is available
+# for Zope 2.
+
+## OOBTree.OOSet.__implements__=ISet
+## OOBTree.OOTreeSet.__implements__=ITreeSet
+## OOBTree.OOBucket.__implements__=IDictionaryIsh
+## OOBTree.OOBTree.__implements__=IBTree
=== ZODB3/BTrees/IOBTree.py 1.7 => 1.7.32.1 ===
--- ZODB3/BTrees/IOBTree.py:1.7 Tue Feb 18 14:05:18 2003
+++ ZODB3/BTrees/IOBTree.py Tue Dec 23 14:06:21 2003
@@ -14,8 +14,3 @@
# hack to overcome dynamic-linking headache.
from _IOBTree import *
-
-# We don't really want _ names in pickles, so update all of the __module__
-# references.
-for obj in IOBucket, IOBTree, IOSet, IOTreeSet:
- obj.__module__ = __name__
=== ZODB3/BTrees/IIBTree.py 1.7 => 1.7.32.1 ===
--- ZODB3/BTrees/IIBTree.py:1.7 Tue Feb 18 14:05:18 2003
+++ ZODB3/BTrees/IIBTree.py Tue Dec 23 14:06:21 2003
@@ -14,8 +14,3 @@
# hack to overcome dynamic-linking headache.
from _IIBTree import *
-
-# We don't really want _ names in pickles, so update all of the __module__
-# references.
-for obj in IIBucket, IIBTree, IISet, IITreeSet:
- obj.__module__ = __name__
=== ZODB3/BTrees/BucketTemplate.c 1.54 => 1.54.20.1 ===
--- ZODB3/BTrees/BucketTemplate.c:1.54 Sun May 11 20:36:17 2003
+++ ZODB3/BTrees/BucketTemplate.c Tue Dec 23 14:06:21 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;
+ PyObject *iter, *o, *k, *v;
+ int err = -1;
- 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;
- }
-
- for (i=0; ; i++)
- {
- o = PySequence_GetItem(seq, i);
- UNLESS (o)
- {
- PyErr_Fetch(&t, &v, &tb);
- if (t != PyExc_IndexError)
- {
- PyErr_Restore(t, v, tb);
- goto err;
- }
- Py_XDECREF(t);
- Py_XDECREF(v);
- Py_XDECREF(tb);
- break;
+ /* One path creates a new seq object. The other path has an
+ INCREF of the seq argument. So seq must always be DECREFed on
+ the way out.
+ */
+ if (!PySequence_Check(seq)) {
+ PyObject *items;
+ items = PyObject_GetAttrString(seq, "items");
+ if (items == NULL)
+ return -1;
+ seq = PyObject_CallObject(items, NULL);
+ Py_DECREF(items);
+ if (seq == NULL)
+ return -1;
+ } else
+ Py_INCREF(seq);
+
+ iter = PyObject_GetIter(seq);
+ if (iter == NULL)
+ goto err;
+ while (1) {
+ o = PyIter_Next(iter);
+ if (o == NULL) {
+ if (PyErr_Occurred())
+ goto err;
+ else
+ break;
}
-
- if (!PyTuple_Check(o) || PyTuple_GET_SIZE(o) != 2)
- {
- Py_DECREF(o);
- PyErr_SetString(PyExc_TypeError,
- "Sequence must contain 2-item tuples");
- goto err;
- }
- k = PyTuple_GET_ITEM(o, 0);
- v = PyTuple_GET_ITEM(o, 1);
- if (PyObject_SetItem(self, k, v) < 0)
- {
- Py_DECREF(o);
- goto err;
- }
- Py_DECREF(o);
+ if (!PyTuple_Check(o) || PyTuple_GET_SIZE(o) != 2) {
+ Py_DECREF(o);
+ PyErr_SetString(PyExc_TypeError,
+ "Sequence must contain 2-item tuples");
+ goto err;
+ }
+ k = PyTuple_GET_ITEM(o, 0);
+ v = PyTuple_GET_ITEM(o, 1);
+ if (PyObject_SetItem(map, k, v) < 0) {
+ Py_DECREF(o);
+ goto err;
+ }
+ Py_DECREF(o);
}
- Py_XDECREF(items);
- Py_INCREF(Py_None);
- return Py_None;
-
+ err = 0;
err:
- Py_XDECREF(items);
- return NULL;
+ Py_DECREF(iter);
+ Py_DECREF(seq);
+ return err;
}
+static PyObject *
+Mapping_update(PyObject *self, PyObject *seq)
+{
+ if (update_from_seq(self, seq) < 0)
+ return NULL;
+ Py_INCREF(Py_None);
+ return Py_None;
+}
/*
** bucket_split
@@ -540,44 +526,42 @@
static int
bucket_split(Bucket *self, int index, Bucket *next)
{
- int next_size;
+ int next_size;
- ASSERT(self->len > 1, "split of empty bucket", -1);
+ ASSERT(self->len > 1, "split of empty bucket", -1);
- if (index < 0 || index >= self->len)
- index = self->len / 2;
+ if (index < 0 || index >= self->len)
+ index = self->len / 2;
- next_size = self->len - index;
+ next_size = self->len - index;
- next->keys = PyMalloc(sizeof(KEY_TYPE) * next_size);
- if (!next->keys)
- return -1;
- memcpy(next->keys, self->keys + index, sizeof(KEY_TYPE) * next_size);
- if (self->values)
- {
- next->values = PyMalloc(sizeof(VALUE_TYPE) * next_size);
- if (!next->values)
- {
- free(next->keys);
- next->keys = NULL;
- return -1;
+ next->keys = BTree_Malloc(sizeof(KEY_TYPE) * next_size);
+ if (!next->keys)
+ return -1;
+ memcpy(next->keys, self->keys + index, sizeof(KEY_TYPE) * next_size);
+ if (self->values) {
+ next->values = BTree_Malloc(sizeof(VALUE_TYPE) * next_size);
+ if (!next->values) {
+ free(next->keys);
+ next->keys = NULL;
+ return -1;
}
- memcpy(next->values, self->values + index,
- sizeof(VALUE_TYPE) * next_size);
+ memcpy(next->values, self->values + index,
+ sizeof(VALUE_TYPE) * next_size);
}
- next->size = next_size;
- next->len = next_size;
- self->len = index;
+ next->size = next_size;
+ next->len = next_size;
+ self->len = index;
- next->next = self->next;
+ next->next = self->next;
- Py_INCREF(next);
- self->next = next;
+ Py_INCREF(next);
+ self->next = next;
- if (PER_CHANGED(self) < 0)
- return -1;
+ if (PER_CHANGED(self) < 0)
+ return -1;
- return 0;
+ return 0;
}
/* Set self->next to self->next->next, i.e. unlink self's successor from
@@ -624,6 +608,9 @@
Arguments: self The bucket
keyarg The key to match against
low Boolean; true for low end of range, false for high
+ exclude_equal Boolean; if true, don't accept an exact match,
+ and if there is one then move right if low and
+ left if !low.
offset The output offset
If low true, *offset <- index of the smallest item >= key,
@@ -635,9 +622,9 @@
1 The correct index was stored into *offset
-1 Error
- Example: Suppose the keys are [2, 4]. Searching for 2 sets *offset to 0 and
- returns 1 regardless of low. Searching for 4 sets *offset to 1 and returns
- 1 regardless of low.
+ Example: Suppose the keys are [2, 4], and exclude_equal is false. Searching
+ for 2 sets *offset to 0 and returns 1 regardless of low. Searching for 4
+ sets *offset to 1 and returns 1 regardless of low.
Searching for 1:
If low true, sets *offset to 0, returns 1.
If low false, returns 0.
@@ -647,9 +634,12 @@
Searching for 5:
If low true, returns 0.
If low false, sets *offset to 1, returns 1.
+
+ The 1, 3 and 5 examples are the same when exclude_equal is true.
*/
static int
-Bucket_findRangeEnd(Bucket *self, PyObject *keyarg, int low, int *offset)
+Bucket_findRangeEnd(Bucket *self, PyObject *keyarg, int low, int exclude_equal,
+ int *offset)
{
int i, cmp;
int result = -1; /* until proven innocent */
@@ -659,28 +649,33 @@
COPY_KEY_FROM_ARG(key, keyarg, copied);
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) /* exact match at index i */
- result = 1;
-
- /* Else keys[i-1] < key < keys[i], picturing infinities at OOB indices */
- else if (low) /* i has the smallest item > key, unless i is OOB */
- result = i < self->len;
-
- else { /* i-1 has the largest item < key, unless i-1 is 0OB */
- --i;
- result = i >= 0;
+ if (cmp == 0) {
+ /* exact match at index i */
+ if (exclude_equal) {
+ /* but we don't want an exact match */
+ if (low)
+ ++i;
+ else
+ --i;
+ }
}
+ /* Else keys[i-1] < key < keys[i], picturing infinities at OOB indices,
+ * and i has the smallest item > key, which is correct for low.
+ */
+ else if (! low)
+ /* i-1 has the largest item < key (unless i-1 is 0OB) */
+ --i;
+ result = 0 <= i && i < self->len;
if (result)
*offset = i;
Done:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
- return result;
+ PER_UNUSE(self);
+ return result;
}
static PyObject *
@@ -698,7 +693,7 @@
/* Find the low range */
if (key)
{
- if ((rc = Bucket_findRangeEnd(self, key, min, &offset)) <= 0)
+ if ((rc = Bucket_findRangeEnd(self, key, min, 0, &offset)) <= 0)
{
if (rc < 0) return NULL;
goto empty;
@@ -708,15 +703,13 @@
else offset = self->len -1;
COPY_KEY_TO_OBJECT(key, self->keys[offset]);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return key;
empty:
PyErr_SetString(PyExc_ValueError, "empty bucket");
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return NULL;
}
@@ -733,45 +726,66 @@
}
static int
-Bucket_rangeSearch(Bucket *self, PyObject *args, int *low, int *high)
+Bucket_rangeSearch(Bucket *self, PyObject *args, PyObject *kw,
+ int *low, int *high)
{
- PyObject *f=0, *l=0;
- int rc;
-
- if (args && ! PyArg_ParseTuple(args,"|OO",&f, &l)) return -1;
-
- UNLESS (self->len) goto empty;
-
- /* Find the low range */
- if (f && f != Py_None)
- {
- UNLESS (rc = Bucket_findRangeEnd(self, f, 1, low))
- {
- if (rc < 0) return -1;
- goto empty;
+ PyObject *min = Py_None;
+ PyObject *max = Py_None;
+ int excludemin = 0;
+ int excludemax = 0;
+ int rc;
+
+ if (args) {
+ if (! PyArg_ParseTupleAndKeywords(args, kw, "|OOii", search_keywords,
+ &min,
+ &max,
+ &excludemin,
+ &excludemax))
+ return -1;
+ }
+
+ UNLESS (self->len) goto empty;
+
+ /* Find the low range */
+ if (min != Py_None) {
+ UNLESS (rc = Bucket_findRangeEnd(self, min, 1, excludemin, low)) {
+ if (rc < 0) return -1;
+ goto empty;
}
}
- else *low = 0;
+ else {
+ *low = 0;
+ if (excludemin) {
+ if (self->len < 2)
+ goto empty;
+ ++*low;
+ }
+ }
- /* Find the high range */
- if (l && l != Py_None)
- {
- UNLESS (rc = Bucket_findRangeEnd(self, l, 0, high))
- {
- if (rc < 0) return -1;
- goto empty;
- }
+ /* Find the high range */
+ if (max != Py_None) {
+ UNLESS (rc = Bucket_findRangeEnd(self, max, 0, excludemax, high)) {
+ if (rc < 0) return -1;
+ goto empty;
+ }
+ }
+ else {
+ *high = self->len - 1;
+ if (excludemax) {
+ if (self->len < 2)
+ goto empty;
+ --*high;
+ }
}
- else *high = self->len - 1;
- /* If f < l to begin with, it's quite possible that low > high now. */
- if (*low <= *high)
- return 0;
+ /* If min < max to begin with, it's quite possible that low > high now. */
+ if (*low <= *high)
+ return 0;
empty:
- *low = 0;
- *high = -1;
- return 0;
+ *low = 0;
+ *high = -1;
+ return 0;
}
/*
@@ -785,30 +799,31 @@
** Returns: list of bucket keys
*/
static PyObject *
-bucket_keys(Bucket *self, PyObject *args)
+bucket_keys(Bucket *self, PyObject *args, PyObject *kw)
{
- PyObject *r=0, *key;
+ PyObject *r = NULL, *key;
int i, low, high;
PER_USE_OR_RETURN(self, NULL);
- if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;
+ if (Bucket_rangeSearch(self, args, kw, &low, &high) < 0)
+ goto err;
- UNLESS (r=PyList_New(high-low+1)) goto err;
+ r = PyList_New(high-low+1);
+ if (r == NULL)
+ goto err;
- for (i=low; i <= high; i++)
- {
+ for (i=low; i <= high; i++) {
COPY_KEY_TO_OBJECT(key, self->keys[i]);
- if (PyList_SetItem(r, i-low , key) < 0) goto err;
- }
+ if (PyList_SetItem(r, i-low , key) < 0)
+ goto err;
+ }
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return r;
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
Py_XDECREF(r);
return NULL;
}
@@ -824,14 +839,14 @@
** Returns list of values
*/
static PyObject *
-bucket_values(Bucket *self, PyObject *args)
+bucket_values(Bucket *self, PyObject *args, PyObject *kw)
{
PyObject *r=0, *v;
int i, low, high;
PER_USE_OR_RETURN(self, NULL);
- if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;
+ if (Bucket_rangeSearch(self, args, kw, &low, &high) < 0) goto err;
UNLESS (r=PyList_New(high-low+1)) goto err;
@@ -842,13 +857,11 @@
if (PyList_SetItem(r, i-low, v) < 0) goto err;
}
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return r;
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
Py_XDECREF(r);
return NULL;
}
@@ -864,14 +877,14 @@
** Returns: list of all items in the bucket
*/
static PyObject *
-bucket_items(Bucket *self, PyObject *args)
+bucket_items(Bucket *self, PyObject *args, PyObject *kw)
{
PyObject *r=0, *o=0, *item=0;
int i, low, high;
PER_USE_OR_RETURN(self, NULL);
- if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;
+ if (Bucket_rangeSearch(self, args, kw, &low, &high) < 0) goto err;
UNLESS (r=PyList_New(high-low+1)) goto err;
@@ -892,29 +905,26 @@
item = 0;
}
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return r;
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
Py_XDECREF(r);
Py_XDECREF(item);
return NULL;
}
static PyObject *
-bucket_byValue(Bucket *self, PyObject *args)
+bucket_byValue(Bucket *self, PyObject *omin)
{
- PyObject *r=0, *o=0, *item=0, *omin;
+ PyObject *r=0, *o=0, *item=0;
VALUE_TYPE min;
VALUE_TYPE v;
int i, l, copied=1;
PER_USE_OR_RETURN(self, NULL);
- UNLESS (PyArg_ParseTuple(args, "O", &omin)) return NULL;
COPY_VALUE_FROM_ARG(min, omin, copied);
UNLESS(copied) return NULL;
@@ -957,13 +967,11 @@
UNLESS (item) goto err;
Py_DECREF(item);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return r;
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
Py_XDECREF(r);
Py_XDECREF(item);
return NULL;
@@ -1012,16 +1020,44 @@
#ifdef PERSISTENT
static PyObject *
-bucket__p_deactivate(Bucket *self, PyObject *args)
+bucket__p_deactivate(Bucket *self, PyObject *args, PyObject *keywords)
{
- if (self->state==cPersistent_UPTODATE_STATE && self->jar)
- {
- if (_bucket_clear(self) < 0) return NULL;
- PER_GHOSTIFY(self);
+ int ghostify = 1;
+ PyObject *force = NULL;
+
+ if (args && PyTuple_GET_SIZE(args) > 0) {
+ PyErr_SetString(PyExc_TypeError,
+ "_p_deactivate takes not positional arguments");
+ return NULL;
+ }
+ if (keywords) {
+ int size = PyDict_Size(keywords);
+ force = PyDict_GetItemString(keywords, "force");
+ if (force)
+ size--;
+ if (size) {
+ PyErr_SetString(PyExc_TypeError,
+ "_p_deactivate only accepts keyword arg force");
+ return NULL;
+ }
}
- Py_INCREF(Py_None);
- return Py_None;
+ if (self->jar && self->oid) {
+ ghostify = self->state == cPersistent_UPTODATE_STATE;
+ if (!ghostify && force) {
+ if (PyObject_IsTrue(force))
+ ghostify = 1;
+ if (PyErr_Occurred())
+ return NULL;
+ }
+ if (ghostify) {
+ if (_bucket_clear(self) < 0)
+ return NULL;
+ PER_GHOSTIFY(self);
+ }
+ }
+ Py_INCREF(Py_None);
+ return Py_None;
}
#endif
@@ -1030,19 +1066,18 @@
{
PER_USE_OR_RETURN(self, NULL);
- if (self->len)
- {
- if (_bucket_clear(self) < 0) return NULL;
- if (PER_CHANGED(self) < 0) goto err;
- }
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ if (self->len) {
+ if (_bucket_clear(self) < 0)
+ return NULL;
+ if (PER_CHANGED(self) < 0)
+ goto err;
+ }
+ PER_UNUSE(self);
Py_INCREF(Py_None);
return Py_None;
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return NULL;
}
@@ -1070,176 +1105,251 @@
* )
*/
static PyObject *
-bucket_getstate(Bucket *self, PyObject *args)
+bucket_getstate(Bucket *self)
{
- PyObject *o=0, *items=0;
- int i, len, l;
+ PyObject *o = NULL, *items = NULL, *state;
+ int i, len, l;
- if (args && ! PyArg_ParseTuple(args, "")) return NULL;
-
- PER_USE_OR_RETURN(self, NULL);
+ PER_USE_OR_RETURN(self, NULL);
- len=self->len;
+ len = self->len;
- if (self->values)
- { /* Bucket */
- UNLESS (items=PyTuple_New(len*2)) goto err;
- for (i=0, l=0; i < len; i++)
- {
- COPY_KEY_TO_OBJECT(o, self->keys[i]);
- UNLESS (o) goto err;
- PyTuple_SET_ITEM(items, l, o);
- l++;
-
- COPY_VALUE_TO_OBJECT(o, self->values[i]);
- UNLESS (o) goto err;
- PyTuple_SET_ITEM(items, l, o);
- l++;
+ if (self->values) { /* Bucket */
+ items = PyTuple_New(len * 2);
+ if (items == NULL)
+ goto err;
+ for (i = 0, l = 0; i < len; i++) {
+ COPY_KEY_TO_OBJECT(o, self->keys[i]);
+ if (o == NULL)
+ goto err;
+ PyTuple_SET_ITEM(items, l, o);
+ l++;
+
+ COPY_VALUE_TO_OBJECT(o, self->values[i]);
+ if (o == NULL)
+ goto err;
+ PyTuple_SET_ITEM(items, l, o);
+ l++;
}
- }
- else
- { /* Set */
- UNLESS (items=PyTuple_New(len)) goto err;
- for (i=0; i < len; i++)
- {
- COPY_KEY_TO_OBJECT(o, self->keys[i]);
- UNLESS (o) goto err;
- PyTuple_SET_ITEM(items, i, o);
+ } else { /* Set */
+ items = PyTuple_New(len);
+ if (items == NULL)
+ goto err;
+ for (i = 0; i < len; i++) {
+ COPY_KEY_TO_OBJECT(o, self->keys[i]);
+ if (o == NULL)
+ goto err;
+ PyTuple_SET_ITEM(items, i, o);
}
}
- if (self->next)
- ASSIGN(items, Py_BuildValue("OO", items, self->next));
- else
- ASSIGN(items, Py_BuildValue("(O)", items));
+ if (self->next)
+ state = Py_BuildValue("OO", items, self->next);
+ else
+ state = Py_BuildValue("(O)", items);
+ Py_DECREF(items);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
-
- return items;
+ PER_UNUSE(self);
+ return state;
-err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
- Py_XDECREF(items);
- return NULL;
+ err:
+ PER_UNUSE(self);
+ Py_XDECREF(items);
+ return NULL;
}
static int
-_bucket_setstate(Bucket *self, PyObject *args)
+_bucket_setstate(Bucket *self, PyObject *state)
{
- PyObject *k, *v, *items;
- Bucket *next=0;
- int i, l, len, copied=1;
- KEY_TYPE *keys;
- VALUE_TYPE *values;
-
- UNLESS (PyArg_ParseTuple(args, "O|O", &items, &next))
- return -1;
-
- if ((len=PyTuple_Size(items)) < 0) return -1;
- len /= 2;
-
- for (i=self->len; --i >= 0; )
- {
- DECREF_KEY(self->keys[i]);
- DECREF_VALUE(self->values[i]);
- }
- self->len=0;
-
- if (self->next)
- {
- Py_DECREF(self->next);
- self->next=0;
+ PyObject *k, *v, *items;
+ Bucket *next = NULL;
+ int i, l, len, copied=1;
+ KEY_TYPE *keys;
+ VALUE_TYPE *values;
+
+ if (!PyArg_ParseTuple(state, "O|O:__setstate__", &items, &next))
+ return -1;
+
+ len = PyTuple_Size(items);
+ if (len < 0)
+ return -1;
+ len /= 2;
+
+ for (i = self->len; --i >= 0; ) {
+ DECREF_KEY(self->keys[i]);
+ DECREF_VALUE(self->values[i]);
}
+ self->len = 0;
- if (len > self->size)
- {
- UNLESS (keys=PyRealloc(self->keys, sizeof(KEY_TYPE)*len))
- return -1;
- UNLESS (values=PyRealloc(self->values, sizeof(VALUE_TYPE)*len))
- return -1;
- self->keys=keys;
- self->values=values;
- self->size=len;
+ if (self->next) {
+ Py_DECREF(self->next);
+ self->next = NULL;
}
- for (i=0, l=0; i<len; i++)
- {
- k=PyTuple_GET_ITEM(items, l);
- l++;
- v=PyTuple_GET_ITEM(items, l);
- l++;
-
- COPY_KEY_FROM_ARG(self->keys[i], k, copied);
- UNLESS (copied) return -1;
- COPY_VALUE_FROM_ARG(self->values[i], v, copied);
- UNLESS (copied) return -1;
- INCREF_KEY(self->keys[i]);
- INCREF_VALUE(self->values[i]);
+ if (len > self->size) {
+ keys = BTree_Realloc(self->keys, sizeof(KEY_TYPE)*len);
+ if (keys == NULL)
+ return -1;
+ values = BTree_Realloc(self->values, sizeof(VALUE_TYPE)*len);
+ if (values == NULL)
+ return -1;
+ self->keys = keys;
+ self->values = values;
+ self->size = len;
+ }
+
+ for (i=0, l=0; i < len; i++) {
+ k = PyTuple_GET_ITEM(items, l);
+ l++;
+ v = PyTuple_GET_ITEM(items, l);
+ l++;
+
+ COPY_KEY_FROM_ARG(self->keys[i], k, copied);
+ if (!copied)
+ return -1;
+ COPY_VALUE_FROM_ARG(self->values[i], v, copied);
+ if (!copied)
+ return -1;
+ INCREF_KEY(self->keys[i]);
+ INCREF_VALUE(self->values[i]);
+ }
+
+ self->len = len;
+
+ if (next) {
+ self->next = next;
+ Py_INCREF(next);
}
- self->len=len;
+ return 0;
+}
- if (next)
- {
- self->next=next;
- Py_INCREF(next);
- }
+static PyObject *
+bucket_setstate(Bucket *self, PyObject *state)
+{
+ int r;
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_PREVENT_DEACTIVATION(self);
+ r = _bucket_setstate(self, state);
+ PER_UNUSE(self);
- return 0;
+ if (r < 0)
+ return NULL;
+ Py_INCREF(Py_None);
+ return Py_None;
}
static PyObject *
-bucket_setstate(Bucket *self, PyObject *args)
+bucket_has_key(Bucket *self, PyObject *key)
{
- int r;
+ return _bucket_get(self, key, 1);
+}
- UNLESS (PyArg_ParseTuple(args, "O", &args)) return NULL;
- PER_PREVENT_DEACTIVATION(self);
- r=_bucket_setstate(self, args);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+/* Search bucket self for key. This is the sq_contains slot of the
+ * PySequenceMethods.
+ *
+ * Return:
+ * -1 error
+ * 0 not found
+ * 1 found
+ */
+static int
+bucket_contains(Bucket *self, PyObject *key)
+{
+ PyObject *asobj = _bucket_get(self, key, 1);
+ int result = -1;
- if (r < 0) return NULL;
- Py_INCREF(Py_None);
- return Py_None;
+ if (asobj != NULL) {
+ result = PyInt_AsLong(asobj) ? 1 : 0;
+ Py_DECREF(asobj);
+ }
+ return result;
}
/*
-** bucket_has_key
+** bucket_getm
**
*/
static PyObject *
-bucket_has_key(Bucket *self, PyObject *args)
+bucket_getm(Bucket *self, PyObject *args)
{
- PyObject *key;
+ PyObject *key, *d=Py_None, *r;
- UNLESS (PyArg_ParseTuple(args,"O",&key)) return NULL;
- return _bucket_get(self, key, 1);
+ if (!PyArg_ParseTuple(args, "O|O:get", &key, &d))
+ return NULL;
+ r = _bucket_get(self, key, 0);
+ if (r)
+ return r;
+ if (!PyErr_ExceptionMatches(PyExc_KeyError))
+ return NULL;
+ PyErr_Clear();
+ Py_INCREF(d);
+ return d;
+}
+
+/**************************************************************************/
+/* Iterator support. */
+
+/* A helper to build all the iterators for Buckets and Sets.
+ * If args is NULL, the iterator spans the entire structure. Else it's an
+ * argument tuple, with optional low and high arguments.
+ * kind is 'k', 'v' or 'i'.
+ * Returns a BTreeIter object, or NULL if error.
+ */
+static PyObject *
+buildBucketIter(Bucket *self, PyObject *args, PyObject *kw, char kind)
+{
+ BTreeItems *items;
+ int lowoffset, highoffset;
+ BTreeIter *result = NULL;
+
+ PER_USE_OR_RETURN(self, NULL);
+ if (Bucket_rangeSearch(self, args, kw, &lowoffset, &highoffset) < 0)
+ goto Done;
+
+ items = (BTreeItems *)newBTreeItems(kind, self, lowoffset,
+ self, highoffset);
+ if (items == NULL) goto Done;
+
+ result = BTreeIter_new(items); /* win or lose, we're done */
+ Py_DECREF(items);
+
+Done:
+ PER_UNUSE(self);
+ return (PyObject *)result;
}
-/*
-** bucket_getm
-**
-*/
+/* The implementation of iter(Bucket_or_Set); the Bucket tp_iter slot. */
static PyObject *
-bucket_getm(Bucket *self, PyObject *args)
+Bucket_getiter(Bucket *self)
{
- PyObject *key, *d=Py_None, *r;
+ return buildBucketIter(self, NULL, NULL, 'k');
+}
- UNLESS (PyArg_ParseTuple(args, "O|O", &key, &d)) return NULL;
- if ((r=_bucket_get(self, key, 0))) return r;
- UNLESS (PyErr_ExceptionMatches(PyExc_KeyError)) return NULL;
- PyErr_Clear();
- Py_INCREF(d);
- return d;
+/* The implementation of Bucket.iterkeys(). */
+static PyObject *
+Bucket_iterkeys(Bucket *self, PyObject *args, PyObject *kw)
+{
+ return buildBucketIter(self, args, kw, 'k');
}
+/* The implementation of Bucket.itervalues(). */
+static PyObject *
+Bucket_itervalues(Bucket *self, PyObject *args, PyObject *kw)
+{
+ return buildBucketIter(self, args, kw, 'v');
+}
+
+/* The implementation of Bucket.iteritems(). */
+static PyObject *
+Bucket_iteritems(Bucket *self, PyObject *args, PyObject *kw)
+{
+ return buildBucketIter(self, args, kw, 'i');
+}
+
+/* End of iterator support. */
+
#ifdef PERSISTENT
static PyObject *merge_error(int p1, int p2, int p3, int reason);
static PyObject *bucket_merge(Bucket *s1, Bucket *s2, Bucket *s3);
@@ -1247,142 +1357,231 @@
static PyObject *
_bucket__p_resolveConflict(PyObject *ob_type, PyObject *s[3])
{
- PyObject *r=0, *a;
- Bucket *b[3];
- int i;
+ PyObject *result = NULL; /* guilty until proved innocent */
+ Bucket *b[3] = {NULL, NULL, NULL};
+ PyObject *meth = NULL;
+ PyObject *a = NULL;
+ int i;
- for (i=0; i < 3; i++)
- {
- if ((b[i]=(Bucket*)PyObject_CallObject(OBJECT(ob_type), NULL)))
- {
- if ((s[i] == Py_None)) /* None is equivalent to empty, for BTrees */
- continue;
- ASSIGN(r, PyObject_GetAttr(OBJECT(b[i]), __setstate___str));
- if ((a=PyTuple_New(1)))
- {
- if (r)
- {
- PyTuple_SET_ITEM(a, 0, s[i]);
- Py_INCREF(s[i]);
- ASSIGN(r, PyObject_CallObject(r, a));
- }
- Py_DECREF(a);
- if (r) continue;
- }
- }
- /* This is not the expected path. It's the error exit path! */
- Py_XDECREF(r);
- while (--i >= 0)
- {
- Py_DECREF(b[i]);
- }
- return NULL;
- }
- Py_DECREF(r);
- r=NULL;
+ for (i = 0; i < 3; i++) {
+ PyObject *r;
- if (b[0]->next != b[1]->next || b[0]->next != b[2]->next)
- {
- merge_error(-1, -1, -1, -1);
- goto err;
+ b[i] = (Bucket*)PyObject_CallObject((PyObject *)ob_type, NULL);
+ if (b[i] == NULL)
+ goto Done;
+ if (s[i] == Py_None) /* None is equivalent to empty, for BTrees */
+ continue;
+ meth = PyObject_GetAttr((PyObject *)b[i], __setstate___str);
+ if (meth == NULL)
+ goto Done;
+ a = PyTuple_New(1);
+ if (a == NULL)
+ goto Done;
+ PyTuple_SET_ITEM(a, 0, s[i]);
+ Py_INCREF(s[i]);
+ r = PyObject_CallObject(meth, a); /* b[i].__setstate__(s[i]) */
+ if (r == NULL)
+ goto Done;
+ Py_DECREF(r);
+ Py_DECREF(a);
+ Py_DECREF(meth);
+ a = meth = NULL;
}
- r=bucket_merge(b[0], b[1], b[2]);
+ if (b[0]->next != b[1]->next || b[0]->next != b[2]->next)
+ merge_error(-1, -1, -1, 0);
+ else
+ result = bucket_merge(b[0], b[1], b[2]);
- err:
- Py_DECREF(b[0]);
- Py_DECREF(b[1]);
- Py_DECREF(b[2]);
-
- if (r == NULL) {
- PyObject *error;
- PyObject *value;
- PyObject *traceback;
-
- PyErr_Fetch(&error, &value, &traceback);
- Py_INCREF(ConflictError);
- Py_XDECREF(error);
- PyErr_Restore(ConflictError, value, traceback);
- }
+Done:
+ Py_XDECREF(meth);
+ Py_XDECREF(a);
+ Py_XDECREF(b[0]);
+ Py_XDECREF(b[1]);
+ Py_XDECREF(b[2]);
- return r;
+ return result;
}
static PyObject *
bucket__p_resolveConflict(Bucket *self, PyObject *args)
{
- PyObject *s[3];
+ PyObject *s[3];
- UNLESS(PyArg_ParseTuple(args, "OOO", &s[0], &s[1], &s[2])) return NULL;
+ if (!PyArg_ParseTuple(args, "OOO", &s[0], &s[1], &s[2]))
+ return NULL;
- return _bucket__p_resolveConflict(OBJECT(self->ob_type), s);
+ return _bucket__p_resolveConflict((PyObject *)self->ob_type, s);
}
#endif
+/* XXX Even though the _next attribute is read-only, a program could
+ probably do arbitrary damage to a the btree internals. For
+ example, it could call clear() on a bucket inside a BTree.
+
+ We need to decide if the convenience for inspecting BTrees is worth
+ the risk.
+*/
+
+static struct PyMemberDef Bucket_members[] = {
+ {"_next", T_OBJECT, offsetof(Bucket, next)},
+ {NULL}
+};
+
static struct PyMethodDef Bucket_methods[] = {
- {"__getstate__", (PyCFunction) bucket_getstate, METH_VARARGS,
- "__getstate__() -- Return the picklable state of the object"},
- {"__setstate__", (PyCFunction) bucket_setstate, METH_VARARGS,
- "__setstate__() -- Set the state of the object"},
- {"keys", (PyCFunction) bucket_keys, METH_VARARGS,
+ {"__getstate__", (PyCFunction) bucket_getstate, METH_NOARGS,
+ "__getstate__() -- Return the picklable state of the object"},
+
+ {"__setstate__", (PyCFunction) bucket_setstate, METH_O,
+ "__setstate__() -- Set the state of the object"},
+
+ {"keys", (PyCFunction) bucket_keys, METH_KEYWORDS,
"keys([min, max]) -- 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"},
- {"update", (PyCFunction) Mapping_update, METH_VARARGS,
- "update(collection) -- Add the items from the given collection"},
- {"__init__", (PyCFunction) Mapping_update, METH_VARARGS,
- "__init__(collection) -- Initialize with items from the given collection"},
- {"maxKey", (PyCFunction) Bucket_maxKey, METH_VARARGS,
- "maxKey([key]) -- 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"},
- {"values", (PyCFunction) bucket_values, METH_VARARGS,
+
+ {"clear", (PyCFunction) bucket_clear, METH_VARARGS,
+ "clear() -- Remove all of the items from the bucket"},
+
+ {"update", (PyCFunction) Mapping_update, METH_O,
+ "update(collection) -- Add the items from the given collection"},
+
+ {"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"},
+
+ {"values", (PyCFunction) bucket_values, METH_KEYWORDS,
"values([min, max]) -- Return the values"},
- {"items", (PyCFunction) bucket_items, METH_VARARGS,
+
+ {"items", (PyCFunction) bucket_items, METH_KEYWORDS,
"items([min, max])) -- Return the items"},
- {"byValue", (PyCFunction) bucket_byValue, METH_VARARGS,
- "byValue(min) -- "
- "Return value-keys with values >= min and reverse sorted by values"
- },
- {"get", (PyCFunction) bucket_getm, METH_VARARGS,
- "get(key[,default]) -- Look up a value\n\n"
- "Return the default (or None) if the key is not found."
- },
+
+ {"byValue", (PyCFunction) bucket_byValue, METH_O,
+ "byValue(min) -- "
+ "Return value-keys with values >= min and reverse sorted by values"},
+
+ {"get", (PyCFunction) bucket_getm, METH_VARARGS,
+ "get(key[,default]) -- Look up a value\n\n"
+ "Return the default (or None) if the key is not found."},
+
+ {"iterkeys", (PyCFunction) Bucket_iterkeys, METH_KEYWORDS,
+ "B.iterkeys([min[,max]]) -> an iterator over the keys of B"},
+
+ {"itervalues", (PyCFunction) Bucket_itervalues, METH_KEYWORDS,
+ "B.itervalues([min[,max]]) -> an iterator over the values of B"},
+
+ {"iteritems", (PyCFunction) Bucket_iteritems, METH_KEYWORDS,
+ "B.iteritems([min[,max]]) -> an iterator over the (key, value) items of B"},
+
#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"},
+ {"_p_resolveConflict", (PyCFunction) bucket__p_resolveConflict,
+ METH_VARARGS,
+ "_p_resolveConflict() -- Reinitialize from a newly created copy"},
+
+ {"_p_deactivate", (PyCFunction) bucket__p_deactivate, METH_KEYWORDS,
+ "_p_deactivate() -- Reinitialize from a newly created copy"},
#endif
- {NULL, NULL} /* sentinel */
+ {NULL, NULL}
};
+static int
+Bucket_init(PyObject *self, PyObject *args, PyObject *kwds)
+{
+ PyObject *v = NULL;
+
+ if (!PyArg_ParseTuple(args, "|O:" MOD_NAME_PREFIX "Bucket", &v))
+ return -1;
+
+ if (v)
+ return update_from_seq(self, v);
+ else
+ return 0;
+}
+
static void
-Bucket_dealloc(Bucket *self)
+bucket_dealloc(Bucket *self)
{
if (self->state != cPersistent_GHOST_STATE)
_bucket_clear(self);
- PER_DEL(self);
+ cPersistenceCAPI->pertype->tp_dealloc((PyObject *)self);
+}
+
+static int
+bucket_traverse(Bucket *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; \
+ }
+
+ /* Call our base type's traverse function. Because buckets are
+ * subclasses of Peristent, there must be one.
+ */
+ err = cPersistenceCAPI->pertype->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 buckets
+ * here just to chase pointers every time gc runs.
+ */
+ if (self->state == cPersistent_GHOST_STATE)
+ goto Done;
+
+ 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
- Py_DECREF(self->ob_type);
- PyObject_Del(self);
+#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
+}
+
+static int
+bucket_tp_clear(Bucket *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,58 +1590,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
-#ifdef PERSISTENT
- | PERSISTENT_TYPE_FLAG
-#endif
- | 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 */
+ 0, /* 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/BTreeTemplate.c 1.74 => 1.74.24.1 ===
--- ZODB3/BTrees/BTreeTemplate.c:1.74 Fri Apr 11 12:09:58 2003
+++ ZODB3/BTrees/BTreeTemplate.c Tue Dec 23 14:06:22 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)
+ return -1;
self->len = 1;
Py_INCREF(d->child);
- self->firstbucket = BUCKET(d->child);
- }
+ self->firstbucket = (Bucket *)d->child;
+ }
return 0;
}
@@ -473,8 +478,7 @@
self = BTREE(pchild);
PER_USE_OR_RETURN(self, NULL);
result = BTree_lastBucket(self);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
}
else {
Py_INCREF(pchild);
@@ -486,23 +490,25 @@
static int
BTree_deleteNextBucket(BTree *self)
{
- Bucket *b;
+ Bucket *b;
- PER_USE_OR_RETURN(self, -1);
+ UNLESS (PER_USE(self)) return -1;
- UNLESS (b = BTree_lastBucket(self)) goto err;
- if (Bucket_deleteNextBucket(b) < 0) goto err;
+ b = BTree_lastBucket(self);
+ if (b == NULL)
+ goto err;
+ if (Bucket_deleteNextBucket(b) < 0)
+ goto err;
- Py_DECREF(b);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ Py_DECREF(b);
+ PER_UNUSE(self);
- return 0;
+ return 0;
err:
- Py_XDECREF(b);
- PER_ALLOW_DEACTIVATION(self);
- return -1;
+ Py_XDECREF(b);
+ PER_ALLOW_DEACTIVATION(self);
+ return -1;
}
/*
@@ -611,7 +617,7 @@
int copied = 1;
COPY_KEY_FROM_ARG(key, keyarg, copied);
- UNLESS (copied) return -1;
+ if (!copied) return -1;
PER_USE_OR_RETURN(self, -1);
@@ -643,7 +649,8 @@
/* If a BTree contains only a single bucket, BTree.__getstate__()
* includes the bucket's entire state, and the bucket doesn't get
* an oid of its own. So if we have a single oid-less bucket that
- * changed, it's *our* oid that should be marked as changed.
+ * changed, it's *our* oid that should be marked as changed -- the
+ * bucket doesn't have one.
*/
if (bucket_changed
&& self->len == 1
@@ -788,6 +795,7 @@
return status;
Error:
+ assert(PyErr_Occurred());
if (self_was_empty) {
/* BTree_grow may have left the BTree in an invalid state. Make
* sure the tree is a legitimate empty tree.
@@ -813,45 +821,75 @@
static int
BTree_setitem(BTree *self, PyObject *key, PyObject *v)
{
- if (_BTree_set(self, key, v, 0, 0) < 0) return -1;
- return 0;
+ if (_BTree_set(self, key, v, 0, 0) < 0)
+ return -1;
+ return 0;
}
#ifdef PERSISTENT
static PyObject *
-BTree__p_deactivate(BTree *self, PyObject *args)
+BTree__p_deactivate(BTree *self, PyObject *args, PyObject *keywords)
{
- if (self->state==cPersistent_UPTODATE_STATE && self->jar)
- {
- if (_BTree_clear(self) < 0) return NULL;
- PER_GHOSTIFY(self);
+ int ghostify = 1;
+ PyObject *force = NULL;
+
+ if (args && PyTuple_GET_SIZE(args) > 0) {
+ PyErr_SetString(PyExc_TypeError,
+ "_p_deactivate takes not positional arguments");
+ return NULL;
+ }
+ if (keywords) {
+ int size = PyDict_Size(keywords);
+ force = PyDict_GetItemString(keywords, "force");
+ if (force)
+ size--;
+ if (size) {
+ PyErr_SetString(PyExc_TypeError,
+ "_p_deactivate only accepts keyword arg force");
+ return NULL;
+ }
}
- Py_INCREF(Py_None);
- return Py_None;
+ if (self->jar && self->oid) {
+ ghostify = self->state == cPersistent_UPTODATE_STATE;
+ if (!ghostify && force) {
+ if (PyObject_IsTrue(force))
+ ghostify = 1;
+ if (PyErr_Occurred())
+ return NULL;
+ }
+ if (ghostify) {
+ if (_BTree_clear(self) < 0)
+ return NULL;
+ PER_GHOSTIFY(self);
+ }
+ }
+
+ Py_INCREF(Py_None);
+ return Py_None;
}
#endif
static PyObject *
-BTree_clear(BTree *self, PyObject *args)
+BTree_clear(BTree *self)
{
- PER_USE_OR_RETURN(self, NULL);
+ UNLESS (PER_USE(self)) return NULL;
if (self->len)
{
- if (_BTree_clear(self) < 0) goto err;
- if (PER_CHANGED(self) < 0) goto err;
+ if (_BTree_clear(self) < 0)
+ goto err;
+ if (PER_CHANGED(self) < 0)
+ goto err;
}
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
Py_INCREF(Py_None);
return Py_None;
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return NULL;
}
@@ -883,69 +921,67 @@
* In the above, key[i] means self->data[i].key, and similarly for child[i].
*/
static PyObject *
-BTree_getstate(BTree *self, PyObject *args)
+BTree_getstate(BTree *self)
{
- PyObject *r=0, *o;
- int i, l;
+ PyObject *r = NULL;
+ PyObject *o;
+ int i, l;
- PER_USE_OR_RETURN(self, NULL);
+ UNLESS (PER_USE(self)) return NULL;
- if (self->len)
- {
- UNLESS (r=PyTuple_New(self->len*2-1)) goto err;
+ if (self->len) {
+ r = PyTuple_New(self->len * 2 - 1);
+ if (r == NULL)
+ goto err;
- if (self->len == 1
- && self->data->child->ob_type != self->ob_type
+ if (self->len == 1
+ && self->data->child->ob_type != self->ob_type
#ifdef PERSISTENT
- && BUCKET(self->data->child)->oid == NULL
+ && BUCKET(self->data->child)->oid == NULL
#endif
- )
- {
- /* We have just one bucket. Save its data directly. */
- UNLESS(o=bucket_getstate(BUCKET(self->data->child), NULL)) goto err;
- PyTuple_SET_ITEM(r,0,o);
- ASSIGN(r, Py_BuildValue("(O)", r));
+ ) {
+ /* We have just one bucket. Save its data directly. */
+ o = bucket_getstate((Bucket *)self->data->child);
+ if (o == NULL)
+ goto err;
+ PyTuple_SET_ITEM(r, 0, o);
+ ASSIGN(r, Py_BuildValue("(O)", r));
}
- else
- {
- for (i=0, l=0; i < self->len; i++)
- {
- if (i)
- {
- COPY_KEY_TO_OBJECT(o, self->data[i].key);
- PyTuple_SET_ITEM(r,l,o);
- l++;
+ else {
+ for (i=0, l=0; i < self->len; i++) {
+ if (i) {
+ COPY_KEY_TO_OBJECT(o, self->data[i].key);
+ PyTuple_SET_ITEM(r, l, o);
+ l++;
}
- o = OBJECT(self->data[i].child);
- Py_INCREF(o);
- PyTuple_SET_ITEM(r,l,o);
- l++;
+ o = (PyObject *)self->data[i].child;
+ Py_INCREF(o);
+ PyTuple_SET_ITEM(r,l,o);
+ l++;
}
- ASSIGN(r, Py_BuildValue("OO", r, self->firstbucket));
+ ASSIGN(r, Py_BuildValue("OO", r, self->firstbucket));
}
}
- else
- {
- r = Py_None;
- Py_INCREF(r);
+ else {
+ r = Py_None;
+ Py_INCREF(r);
}
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
- return r;
+ return r;
-err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
- return NULL;
+ err:
+ PER_UNUSE(self);
+ Py_XDECREF(r);
+ return NULL;
}
static int
_BTree_setstate(BTree *self, PyObject *state, int noval)
{
- PyObject *items, *firstbucket=0;
+ PyObject *items, *firstbucket = NULL;
BTreeItem *d;
int len, l, i, copied=1;
@@ -963,17 +999,17 @@
return 0;
if (!PyArg_ParseTuple(state, "O|O:__setstate__", &items, &firstbucket))
- return -1;
+ return -1;
len = PyTuple_Size(items);
if (len < 0)
return -1;
len = (len + 1) / 2;
- assert(len > 0);
- assert(self->size == 0); /* XXX we called _BTree_clear() above! */
- assert(self->data == NULL); /* ditto */
- self->data = PyMalloc(sizeof(BTreeItem) * len);
+ assert(len > 0); /* If the BTree is empty, it's state is None. */
+ assert(self->size == 0); /* We called _BTree_clear(). */
+
+ self->data = BTree_Malloc(sizeof(BTreeItem) * len);
if (self->data == NULL)
return -1;
self->size = len;
@@ -981,7 +1017,7 @@
for (i = 0, d = self->data, l = 0; i < len; i++, d++) {
PyObject *v;
if (i) { /* skip the first key slot */
- COPY_KEY_FROM_ARG(d->key, PyTuple_GET_ITEM(items,l), copied);
+ COPY_KEY_FROM_ARG(d->key, PyTuple_GET_ITEM(items, l), copied);
l++;
if (!copied)
return -1;
@@ -991,17 +1027,14 @@
if (PyTuple_Check(v)) {
/* Handle the special case in __getstate__() for a BTree
with a single bucket. */
+ d->child = BTree_newBucket(self);
+ if (!d->child)
+ return -1;
if (noval) {
- d->child = SIZED(PyObject_CallObject(OBJECT(&SetType),
- NULL));
- UNLESS (d->child) return -1;
if (_set_setstate(BUCKET(d->child), v) < 0)
return -1;
}
else {
- d->child = SIZED(PyObject_CallObject(OBJECT(&BucketType),
- NULL));
- UNLESS (d->child) return -1;
if (_bucket_setstate(BUCKET(d->child), v) < 0)
return -1;
}
@@ -1014,14 +1047,14 @@
}
if (!firstbucket)
- firstbucket = OBJECT(self->data->child);
+ firstbucket = (PyObject *)self->data->child;
- if (!ExtensionClassSubclassInstance_Check(
- firstbucket, noval ? &SetType : &BucketType)) {
- PyErr_SetString(PyExc_TypeError, "No firstbucket in non-empty BTree");
+ if (!PyObject_IsInstance(firstbucket, (PyObject *)
+ (noval ? &SetType : &BucketType))) {
+ PyErr_SetString(PyExc_TypeError,
+ "No firstbucket in non-empty BTree");
return -1;
}
-
self->firstbucket = BUCKET(firstbucket);
Py_INCREF(firstbucket);
#ifndef PERSISTENT
@@ -1030,73 +1063,119 @@
*/
assert(self->firstbucket->ob_refcnt > 1);
#endif
-
self->len = len;
return 0;
}
static PyObject *
-BTree_setstate(BTree *self, PyObject *args)
+BTree_setstate(BTree *self, PyObject *arg)
{
- int r;
+ int r;
- if (!PyArg_ParseTuple(args,"O",&args)) return NULL;
-
- PER_PREVENT_DEACTIVATION(self);
- r=_BTree_setstate(self, args, 0);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_PREVENT_DEACTIVATION(self);
+ r = _BTree_setstate(self, arg, 0);
+ PER_UNUSE(self);
- if (r < 0) return NULL;
- Py_INCREF(Py_None);
- return Py_None;
+ if (r < 0)
+ return NULL;
+ Py_INCREF(Py_None);
+ return Py_None;
}
#ifdef PERSISTENT
-static PyObject *
-BTree__p_resolveConflict(BTree *self, PyObject *args)
+
+/* Recognize the special cases of a BTree that's empty or contains a single
+ * bucket. In the former case, return a borrowed reference to Py_None.
+ * In this single-bucket case, the bucket state is embedded directly in the
+ * BTree state, like so:
+ *
+ * (
+ * (
+ * thebucket.__getstate__(),
+ * ),
+ * )
+ *
+ * When this obtains, return a borrowed reference to thebucket.__getstate__().
+ * Else return NULL with an exception set. The exception should always be
+ * ConflictError then, but may be TypeError if the state makes no sense at all
+ * for a BTree (corrupted or hostile state).
+ */
+PyObject *
+get_bucket_state(PyObject *t)
{
- PyObject *s[3], *r;
- int i;
+ if (t == Py_None)
+ return Py_None; /* an empty BTree */
+ if (! PyTuple_Check(t)) {
+ PyErr_SetString(PyExc_TypeError,
+ "_p_resolveConflict: expected tuple or None for state");
+ return NULL;
+ }
- r = NULL;
+ if (PyTuple_GET_SIZE(t) == 2) {
+ /* A non-degenerate BTree. */
+ return merge_error(-1, -1, -1, 11);
+ }
- UNLESS (PyArg_ParseTuple(args, "OOO", s, s+1, s+2)) goto err;
+ /* We're in the one-bucket case. */
- /* for each state, detuplefy it twice */
- for (i=0; i < 3; i++)
- UNLESS (s[i]==Py_None || PyArg_ParseTuple(s[i], "O", s+i)) goto err;
- for (i=0; i < 3; i++)
- UNLESS (s[i]==Py_None || PyArg_ParseTuple(s[i], "O", s+i)) goto err;
-
- for (i=0; i < 3; i++) /* Now make sure detupled thing is a tuple */
- UNLESS (s[i]==Py_None || PyTuple_Check(s[i]))
- return merge_error(-100, -100, -100, -100);
+ if (PyTuple_GET_SIZE(t) != 1) {
+ PyErr_SetString(PyExc_TypeError,
+ "_p_resolveConflict: expected 1- or 2-tuple for state");
+ return NULL;
+ }
- if (ExtensionClassSubclassInstance_Check(self, &BTreeType))
- r = _bucket__p_resolveConflict(OBJECT(&BucketType), s);
- else
- r = _bucket__p_resolveConflict(OBJECT(&SetType), s);
+ t = PyTuple_GET_ITEM(t, 0);
+ if (! PyTuple_Check(t) || PyTuple_GET_SIZE(t) != 1) {
+ PyErr_SetString(PyExc_TypeError,
+ "_p_resolveConflict: expected 1-tuple containing "
+ "bucket state");
+ return NULL;
+ }
-err:
+ t = PyTuple_GET_ITEM(t, 0);
+ if (! PyTuple_Check(t)) {
+ PyErr_SetString(PyExc_TypeError,
+ "_p_resolveConflict: expected tuple for bucket state");
+ return NULL;
+ }
- if (r) {
- ASSIGN(r, Py_BuildValue("((O))", r));
- }
- else {
- PyObject *error;
- PyObject *value;
- PyObject *traceback;
- /* Change any errors to ConflictErrors */
-
- PyErr_Fetch(&error, &value, &traceback);
- Py_INCREF(ConflictError);
- Py_XDECREF(error);
- PyErr_Restore(ConflictError, value, traceback);
- }
+ return t;
+}
- return r;
+/* Tricky. The only kind of BTree conflict we can actually potentially
+ * resolve is the special case of a BTree containing a single bucket,
+ * in which case this becomes a fancy way of calling the bucket conflict
+ * resolution code.
+ */
+static PyObject *
+BTree__p_resolveConflict(BTree *self, PyObject *args)
+{
+ PyObject *s[3];
+ PyObject *x, *y, *z;
+
+ if (!PyArg_ParseTuple(args, "OOO", &x, &y, &z))
+ return NULL;
+
+ s[0] = get_bucket_state(x);
+ if (s[0] == NULL)
+ return NULL;
+ s[1] = get_bucket_state(y);
+ if (s[1] == NULL)
+ return NULL;
+ s[2] = get_bucket_state(z);
+ if (s[2] == NULL)
+ return NULL;
+
+ if (PyObject_IsInstance((PyObject *)self, (PyObject *)&BTreeType))
+ x = _bucket__p_resolveConflict(OBJECT(&BucketType), s);
+ else
+ x = _bucket__p_resolveConflict(OBJECT(&SetType), s);
+
+ if (x == NULL)
+ return NULL;
+
+ return Py_BuildValue("((N))", x);
}
#endif
@@ -1107,6 +1186,10 @@
If low, return bucket and index of the smallest item >= key,
otherwise return bucket and index of the largest item <= key.
+ If exclude_equal, exact matches aren't acceptable; if one is found,
+ move right if low, or left if !low (this is for range searches exclusive
+ of an endpoint).
+
Return:
-1 Error; offset and bucket unchanged
0 Not found; offset and bucket unchanged
@@ -1152,7 +1235,7 @@
at first. This is clumsy to get at, but efficient.
*/
static int
-BTree_findRangeEnd(BTree *self, PyObject *keyarg, int low,
+BTree_findRangeEnd(BTree *self, PyObject *keyarg, int low, int exclude_equal,
Bucket **bucket, int *offset) {
Sized *deepest_smaller = NULL; /* last possibility to move left */
int deepest_smaller_is_btree = 0; /* Boolean; if false, it's a bucket */
@@ -1185,8 +1268,7 @@
if (pchild_is_btree) {
if (self_got_rebound) {
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
}
self = BTREE(pchild);
self_got_rebound = 1;
@@ -1199,7 +1281,7 @@
}
/* Search the bucket for a suitable key. */
- i = Bucket_findRangeEnd(pbucket, keyarg, low, offset);
+ i = Bucket_findRangeEnd(pbucket, keyarg, low, exclude_equal, offset);
if (i < 0)
goto Done;
if (i > 0) {
@@ -1222,8 +1304,7 @@
}
else
result = 0;
- PER_ALLOW_DEACTIVATION(pbucket);
- PER_ACCESSED(pbucket);
+ PER_UNUSE(pbucket);
}
/* High-end search: if it's possible to go left, do so. */
else if (deepest_smaller) {
@@ -1231,8 +1312,7 @@
UNLESS(PER_USE(deepest_smaller)) goto Done;
/* We own the reference this returns. */
pbucket = BTree_lastBucket(BTREE(deepest_smaller));
- PER_ALLOW_DEACTIVATION(deepest_smaller);
- PER_ACCESSED(deepest_smaller);
+ PER_UNUSE(deepest_smaller);
if (pbucket == NULL) goto Done; /* error */
}
else {
@@ -1243,16 +1323,14 @@
result = 1;
*bucket = pbucket; /* transfer ownership to caller */
*offset = pbucket->len - 1;
- PER_ALLOW_DEACTIVATION(pbucket);
- PER_ACCESSED(pbucket);
+ PER_UNUSE(pbucket);
}
else
result = 0; /* simply not found */
Done:
if (self_got_rebound) {
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
}
return result;
}
@@ -1260,13 +1338,13 @@
static PyObject *
BTree_maxminKey(BTree *self, PyObject *args, int min)
{
- PyObject *key = 0;
+ PyObject *key=0;
Bucket *bucket = NULL;
int offset, rc;
UNLESS (PyArg_ParseTuple(args, "|O", &key)) return NULL;
- PER_USE_OR_RETURN(self, NULL);
+ UNLESS (PER_USE(self)) return NULL;
UNLESS (self->data && self->len) goto empty;
@@ -1274,13 +1352,12 @@
if (key)
{
- if ((rc = BTree_findRangeEnd(self, key, min, &bucket, &offset)) <= 0)
+ if ((rc = BTree_findRangeEnd(self, key, min, 0, &bucket, &offset)) <= 0)
{
if (rc < 0) goto err;
goto empty;
}
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
UNLESS (PER_USE(bucket))
{
Py_DECREF(bucket);
@@ -1290,8 +1367,7 @@
else if (min)
{
bucket = self->firstbucket;
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
PER_USE_OR_RETURN(bucket, NULL);
Py_INCREF(bucket);
offset = 0;
@@ -1299,8 +1375,7 @@
else
{
bucket = BTree_lastBucket(self);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
UNLESS (PER_USE(bucket))
{
Py_DECREF(bucket);
@@ -1308,11 +1383,10 @@
}
assert(bucket->len);
offset = bucket->len - 1;
- }
+ }
COPY_KEY_TO_OBJECT(key, bucket->keys[offset]);
- PER_ALLOW_DEACTIVATION(bucket);
- PER_ACCESSED(bucket);
+ PER_UNUSE(bucket);
Py_DECREF(bucket);
return key;
@@ -1321,12 +1395,10 @@
PyErr_SetString(PyExc_ValueError, "empty tree");
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
if (bucket)
{
- PER_ALLOW_DEACTIVATION(bucket);
- PER_ACCESSED(bucket);
+ PER_UNUSE(bucket);
Py_DECREF(bucket);
}
return NULL;
@@ -1352,172 +1424,207 @@
**
*/
static PyObject *
-BTree_rangeSearch(BTree *self, PyObject *args, char type)
+BTree_rangeSearch(BTree *self, PyObject *args, PyObject *kw, char type)
{
- PyObject *f=0, *l=0;
- int rc;
- Bucket *lowbucket = NULL;
- Bucket *highbucket = NULL;
- int lowoffset;
- int highoffset;
-
- UNLESS (! args || PyArg_ParseTuple(args,"|OO",&f, &l)) return NULL;
-
- PER_USE_OR_RETURN(self, NULL);
-
- UNLESS (self->data && self->len) goto empty;
-
- /* Find the low range */
+ PyObject *min = Py_None;
+ PyObject *max = Py_None;
+ int excludemin = 0;
+ int excludemax = 0;
+ int rc;
+ Bucket *lowbucket = NULL;
+ Bucket *highbucket = NULL;
+ int lowoffset;
+ int highoffset;
+ PyObject *result;
+
+ if (args) {
+ if (! PyArg_ParseTupleAndKeywords(args, kw, "|OOii", search_keywords,
+ &min,
+ &max,
+ &excludemin,
+ &excludemax))
+ return NULL;
+ }
+
+ UNLESS (PER_USE(self)) return NULL;
+
+ UNLESS (self->data && self->len) goto empty;
+
+ /* Find the low range */
+ if (min != Py_None) {
+ if ((rc = BTree_findRangeEnd(self, min, 1, excludemin,
+ &lowbucket, &lowoffset)) <= 0) {
+ if (rc < 0) goto err;
+ goto empty;
+ }
+ }
+ else {
+ lowbucket = self->firstbucket;
+ lowoffset = 0;
+ if (excludemin) {
+ int bucketlen;
+ UNLESS (PER_USE(lowbucket)) goto err;
+ bucketlen = lowbucket->len;
+ PER_UNUSE(lowbucket);
+ if (bucketlen > 1)
+ lowoffset = 1;
+ else if (self->len < 2)
+ goto empty;
+ else { /* move to first item in next bucket */
+ Bucket *next;
+ UNLESS (PER_USE(lowbucket)) goto err;
+ next = lowbucket->next;
+ PER_UNUSE(lowbucket);
+ assert(next != NULL);
+ lowbucket = next;
+ /* and lowoffset is still 0 */
+ assert(lowoffset == 0);
+ }
+ }
+ Py_INCREF(lowbucket);
+ }
- if (f && f != Py_None)
- {
- if ((rc = BTree_findRangeEnd(self, f, 1, &lowbucket, &lowoffset)) <= 0)
- {
- if (rc < 0) goto err;
- goto empty;
+ /* Find the high range */
+ if (max != Py_None) {
+ if ((rc = BTree_findRangeEnd(self, max, 0, excludemax,
+ &highbucket, &highoffset)) <= 0) {
+ Py_DECREF(lowbucket);
+ if (rc < 0) goto err;
+ goto empty;
}
}
- else
- {
- lowbucket = self->firstbucket;
- Py_INCREF(lowbucket);
- lowoffset = 0;
+ else {
+ int bucketlen;
+ highbucket = BTree_lastBucket(self);
+ assert(highbucket != NULL); /* we know self isn't empty */
+ UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
+ bucketlen = highbucket->len;
+ PER_UNUSE(highbucket);
+ highoffset = bucketlen - 1;
+ if (excludemax) {
+ if (highoffset > 0)
+ --highoffset;
+ else if (self->len < 2)
+ goto empty_and_decref_buckets;
+ else { /* move to last item of preceding bucket */
+ int status;
+ assert(highbucket != self->firstbucket);
+ Py_DECREF(highbucket);
+ status = PreviousBucket(&highbucket, self->firstbucket);
+ if (status < 0) {
+ Py_DECREF(lowbucket);
+ goto err;
+ }
+ assert(status > 0);
+ Py_INCREF(highbucket);
+ UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
+ highoffset = highbucket->len - 1;
+ PER_UNUSE(highbucket);
+ }
+ }
+ assert(highoffset >= 0);
}
- /* Find the high range */
+ /* It's still possible that the range is empty, even if min < max. For
+ * example, if min=3 and max=4, and 3 and 4 aren't in the BTree, but 2 and
+ * 5 are, then the low position points to the 5 now and the high position
+ * points to the 2 now. They're not necessarily even in the same bucket,
+ * so there's no trick we can play with pointer compares to get out
+ * cheap in general.
+ */
+ if (lowbucket == highbucket && lowoffset > highoffset)
+ goto empty_and_decref_buckets; /* definitely empty */
- if (l && l != Py_None)
- {
- if ((rc = BTree_findRangeEnd(self, l, 0, &highbucket, &highoffset)) <= 0)
- {
- Py_DECREF(lowbucket);
- if (rc < 0) goto err;
- goto empty;
- }
+ /* The buckets differ, or they're the same and the offsets show a non-
+ * empty range.
+ */
+ if (min != Py_None && max != Py_None && /* both args user-supplied */
+ lowbucket != highbucket) /* and different buckets */ {
+ KEY_TYPE first;
+ KEY_TYPE last;
+ int cmp;
+
+ /* Have to check the hard way: see how the endpoints compare. */
+ UNLESS (PER_USE(lowbucket)) goto err_and_decref_buckets;
+ COPY_KEY(first, lowbucket->keys[lowoffset]);
+ PER_UNUSE(lowbucket);
+
+ UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
+ COPY_KEY(last, highbucket->keys[highoffset]);
+ PER_UNUSE(highbucket);
+
+ TEST_KEY_SET_OR(cmp, first, last) goto err_and_decref_buckets;
+ if (cmp > 0) goto empty_and_decref_buckets;
}
- else
- {
- highbucket = BTree_lastBucket(self);
- assert(highbucket != NULL); /* we know self isn't empty */
- UNLESS (PER_USE(highbucket))
- {
- Py_DECREF(lowbucket);
- Py_DECREF(highbucket);
- goto err;
- }
- highoffset = highbucket->len - 1;
- PER_ALLOW_DEACTIVATION(highbucket);
- PER_ACCESSED(highbucket);
- }
-
- /* It's still possible that the range is empty, even if f < l. For
- * example, if f=3 and l=4, and 3 and 4 aren't in the BTree, but 2 and
- * 5 are, then the low position points to the 5 now and the high position
- * points to the 2 now. They're not necessarily even in the same bucket,
- * so there's no trick we can play with pointer compares to get out
- * cheap in general.
- */
- if (lowbucket == highbucket && lowoffset > highoffset)
- goto empty_and_decref_buckets; /* definitely empty */
-
- /* The buckets differ, or they're the same and the offsets show a non-
- * empty range.
- */
- if (f && f != Py_None /* both args user-supplied */
- && l && l != Py_None
- && lowbucket != highbucket) /* and different buckets */
- {
- KEY_TYPE first;
- KEY_TYPE last;
- int cmp;
-
- /* Have to check the hard way: see how the endpoints compare. */
- UNLESS (PER_USE(lowbucket)) goto err_and_decref_buckets;
- COPY_KEY(first, lowbucket->keys[lowoffset]);
- PER_ALLOW_DEACTIVATION(lowbucket);
- PER_ACCESSED(lowbucket);
-
- UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
- COPY_KEY(last, highbucket->keys[highoffset]);
- PER_ALLOW_DEACTIVATION(highbucket);
- PER_ACCESSED(highbucket);
-
- TEST_KEY_SET_OR(cmp, first, last) goto err_and_decref_buckets;
- if (cmp > 0) goto empty_and_decref_buckets;
- }
-
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
-
- f = newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
- Py_DECREF(lowbucket);
- Py_DECREF(highbucket);
- return f;
+
+ PER_UNUSE(self);
+
+ result = newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
+ Py_DECREF(lowbucket);
+ Py_DECREF(highbucket);
+ return result;
err_and_decref_buckets:
- Py_DECREF(lowbucket);
- Py_DECREF(highbucket);
+ Py_DECREF(lowbucket);
+ Py_DECREF(highbucket);
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
- return NULL;
+ PER_UNUSE(self);
+ return NULL;
empty_and_decref_buckets:
- Py_DECREF(lowbucket);
- Py_DECREF(highbucket);
+ Py_DECREF(lowbucket);
+ Py_DECREF(highbucket);
empty:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
- return newBTreeItems(type, 0, 0, 0, 0);
+ PER_UNUSE(self);
+ return newBTreeItems(type, 0, 0, 0, 0);
}
/*
** BTree_keys
*/
static PyObject *
-BTree_keys(BTree *self, PyObject *args)
+BTree_keys(BTree *self, PyObject *args, PyObject *kw)
{
- return BTree_rangeSearch(self,args, 'k');
+ return BTree_rangeSearch(self, args, kw, 'k');
}
/*
** BTree_values
*/
static PyObject *
-BTree_values(BTree *self, PyObject *args)
+BTree_values(BTree *self, PyObject *args, PyObject *kw)
{
- return BTree_rangeSearch(self,args,'v');
+ return BTree_rangeSearch(self, args, kw, 'v');
}
/*
** BTree_items
*/
static PyObject *
-BTree_items(BTree *self, PyObject *args)
+BTree_items(BTree *self, PyObject *args, PyObject *kw)
{
- return BTree_rangeSearch(self,args,'i');
+ return BTree_rangeSearch(self, args, kw, 'i');
}
static PyObject *
-BTree_byValue(BTree *self, PyObject *args)
+BTree_byValue(BTree *self, PyObject *omin)
{
- PyObject *r=0, *o=0, *item=0, *omin;
+ PyObject *r=0, *o=0, *item=0;
VALUE_TYPE min;
VALUE_TYPE v;
int copied=1;
SetIteration it = {0, 0, 1};
- PER_USE_OR_RETURN(self, NULL);
+ UNLESS (PER_USE(self)) return NULL;
- UNLESS (PyArg_ParseTuple(args, "O", &omin)) return NULL;
COPY_VALUE_FROM_ARG(min, omin, copied);
UNLESS(copied) return NULL;
UNLESS (r=PyList_New(0)) goto err;
- it.set=BTree_rangeSearch(self, NULL, 'i');
+ it.set=BTree_rangeSearch(self, NULL, NULL, 'i');
UNLESS(it.set) goto err;
if (nextBTreeItems(&it) < 0) goto err;
@@ -1557,13 +1664,11 @@
Py_DECREF(item);
finiSetIteration(&it);
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
return r;
err:
- PER_ALLOW_DEACTIVATION(self);
- PER_ACCESSED(self);
+ PER_UNUSE(self);
Py_XDECREF(r);
finiSetIteration(&it);
Py_XDECREF(item);
@@ -1586,16 +1691,31 @@
return d;
}
-/*
-** BTree_has_key
-*/
static PyObject *
-BTree_has_key(BTree *self, PyObject *args)
+BTree_has_key(BTree *self, PyObject *key)
+{
+ return _BTree_get(self, key, 1);
+}
+
+/* Search BTree self for key. This is the sq_contains slot of the
+ * PySequenceMethods.
+ *
+ * Return:
+ * -1 error
+ * 0 not found
+ * 1 found
+ */
+static int
+BTree_contains(BTree *self, PyObject *key)
{
- PyObject *key;
+ PyObject *asobj = _BTree_get(self, key, 1);
+ int result = -1;
- UNLESS (PyArg_ParseTuple(args,"O",&key)) return NULL;
- return _BTree_get(self, key, 1);
+ if (asobj != NULL) {
+ result = PyInt_AsLong(asobj) ? 1 : 0;
+ Py_DECREF(asobj);
+ }
+ return result;
}
static PyObject *
@@ -1610,65 +1730,234 @@
return PyInt_FromLong(grew);
}
+/**************************************************************************/
+/* Iterator support. */
+
+/* A helper to build all the iterators for BTrees and TreeSets.
+ * If args is NULL, the iterator spans the entire structure. Else it's an
+ * argument tuple, with optional low and high arguments.
+ * kind is 'k', 'v' or 'i'.
+ * Returns a BTreeIter object, or NULL if error.
+ */
+static PyObject *
+buildBTreeIter(BTree *self, PyObject *args, PyObject *kw, char kind)
+{
+ BTreeIter *result = NULL;
+ BTreeItems *items = (BTreeItems *)BTree_rangeSearch(self, args, kw, kind);
+
+ if (items) {
+ result = BTreeIter_new(items);
+ Py_DECREF(items);
+ }
+ return (PyObject *)result;
+}
+
+/* The implementation of iter(BTree_or_TreeSet); the BTree tp_iter slot. */
+static PyObject *
+BTree_getiter(BTree *self)
+{
+ return buildBTreeIter(self, NULL, NULL, 'k');
+}
+
+/* The implementation of BTree.iterkeys(). */
+static PyObject *
+BTree_iterkeys(BTree *self, PyObject *args, PyObject *kw)
+{
+ return buildBTreeIter(self, args, kw, 'k');
+}
+
+/* The implementation of BTree.itervalues(). */
+static PyObject *
+BTree_itervalues(BTree *self, PyObject *args, PyObject *kw)
+{
+ return buildBTreeIter(self, args, kw, 'v');
+}
+
+/* The implementation of BTree.iteritems(). */
+static PyObject *
+BTree_iteritems(BTree *self, PyObject *args, PyObject *kw)
+{
+ return buildBTreeIter(self, args, kw, 'i');
+}
+
+/* End of iterator support. */
+
+
+/* XXX Even though the _firstbucket attribute is read-only, a program
+ could probably do arbitrary damage to a the btree internals. For
+ example, it could call clear() on a bucket inside a BTree.
+
+ We need to decide if the convenience for inspecting BTrees is worth
+ the risk.
+*/
+
+static struct PyMemberDef BTree_members[] = {
+ {"_firstbucket", T_OBJECT, offsetof(BTree, firstbucket), RO},
+ {NULL}
+};
static struct PyMethodDef BTree_methods[] = {
- {"__getstate__", (PyCFunction) BTree_getstate, METH_VARARGS,
- "__getstate__() -- Return the picklable state of the object"},
- {"__setstate__", (PyCFunction) BTree_setstate, METH_VARARGS,
- "__setstate__() -- Set the state of the object"},
- {"has_key", (PyCFunction) BTree_has_key, METH_VARARGS,
- "has_key(key) -- Test whether the bucket contains the given key"},
- {"keys", (PyCFunction) BTree_keys, METH_VARARGS,
- "keys([min, max]) -- Return the keys"},
- {"values", (PyCFunction) BTree_values, METH_VARARGS,
- "values([min, max]) -- Return the values"},
- {"items", (PyCFunction) BTree_items, METH_VARARGS,
- "items([min, max]) -- Return the items"},
- {"byValue", (PyCFunction) BTree_byValue, METH_VARARGS,
- "byValue(min) -- "
- "Return value-keys with values >= min and reverse sorted by values"
- },
- {"get", (PyCFunction) BTree_getm, METH_VARARGS,
- "get(key[,default]) -- Look up a value\n\n"
- "Return the default (or None) if the key is not found."
- },
- {"maxKey", (PyCFunction) BTree_maxKey, METH_VARARGS,
- "maxKey([key]) -- Find the maximum key\n\n"
- "If an argument is given, find the maximum <= the argument"},
- {"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"},
- {"insert", (PyCFunction)BTree_addUnique, METH_VARARGS,
- "insert(key, value) -- Add an item if the key is not already used.\n\n"
- "Return 1 if the item was added, or 0 otherwise"
- },
- {"update", (PyCFunction) Mapping_update, METH_VARARGS,
- "update(collection) -- Add the items from the given collection"},
- {"__init__", (PyCFunction) Mapping_update, METH_VARARGS,
- "__init__(collection) -- Initialize with items from the given collection"},
- {"_check", (PyCFunction) BTree_check, METH_VARARGS,
- "Perform sanity check on BTree, and raise exception if flawed."},
+ {"__getstate__", (PyCFunction) BTree_getstate, METH_NOARGS,
+ "__getstate__() -> state\n\n"
+ "Return the picklable state of the BTree."},
+
+ {"__setstate__", (PyCFunction) BTree_setstate, METH_O,
+ "__setstate__(state)\n\n"
+ "Set the state of the BTree."},
+
+ {"has_key", (PyCFunction) BTree_has_key, METH_O,
+ "has_key(key)\n\n"
+ "Return true if the BTree contains the given key."},
+
+ {"keys", (PyCFunction) BTree_keys, METH_KEYWORDS,
+ "keys([min, max]) -> list of keys\n\n"
+ "Returns the keys of the BTree. If min and max are supplied, only\n"
+ "keys greater than min and less than max are returned."},
+
+ {"values", (PyCFunction) BTree_values, METH_KEYWORDS,
+ "values([min, max]) -> list of values\n\n"
+ "Returns the values of the BTree. If min and max are supplied, only\n"
+ "values corresponding to keys greater than min and less than max are\n"
+ "returned."},
+
+ {"items", (PyCFunction) BTree_items, METH_KEYWORDS,
+ "items([min, max]) -> -- list of key, value pairs\n\n"
+ "Returns the items of the BTree. If min and max are supplied, only\n"
+ "items with keys greater than min and less than max are returned."},
+
+ {"byValue", (PyCFunction) BTree_byValue, METH_O,
+ "byValue(min) -> list of value, key pairs\n\n"
+ "Returns list of value, key pairs where the value is >= min. The\n"
+ "list is sorted by value. Note that items() returns keys in the\n"
+ "opposite order."},
+
+ {"get", (PyCFunction) BTree_getm, METH_VARARGS,
+ "get(key[, default=None]) -> Value for key or default\n\n"
+ "Return the value or the default if the key is not found."},
+
+ {"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)BTree_addUnique, METH_VARARGS,
+ "insert(key, value) -> 0 or 1\n\n"
+ "Add an item if the key is not already used. Return 1 if the item was\n"
+ "added, or 0 otherwise."},
+
+ {"update", (PyCFunction) Mapping_update, METH_O,
+ "update(collection)\n\n Add the items from the given collection."},
+
+ {"iterkeys", (PyCFunction) BTree_iterkeys, METH_KEYWORDS,
+ "B.iterkeys([min[,max]]) -> an iterator over the keys of B"},
+
+ {"itervalues", (PyCFunction) BTree_itervalues, METH_KEYWORDS,
+ "B.itervalues([min[,max]]) -> an iterator over the values of B"},
+
+ {"iteritems", (PyCFunction) BTree_iteritems, METH_KEYWORDS,
+ "B.iteritems([min[,max]]) -> an iterator over the (key, value) items of B"},
+
+ {"_check", (PyCFunction) BTree_check, METH_NOARGS,
+ "Perform sanity check on BTree, 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_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->state != cPersistent_GHOST_STATE)
+ _BTree_clear(self);
+ cPersistenceCAPI->pertype->tp_dealloc((PyObject *)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);
+
+ /* Call our base type's traverse function. Because BTrees are
+ * subclasses of Peristent, there must be one.
+ */
+ err = cPersistenceCAPI->pertype->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);
- Py_DECREF(self->ob_type);
- PyObject_Del(self);
+Done:
+ return err;
+
+#undef VISIT
+}
+
+static int
+BTree_tp_clear(BTree *self)
+{
+ if (self->state != cPersistent_GHOST_STATE)
+ _BTree_clear(self);
+ return 0;
}
/*
@@ -1722,8 +2011,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,35 +2034,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
-#ifdef PERSISTENT
- | PERSISTENT_TYPE_FLAG
-#endif
- | 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 */
+ 0, /* 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/BTreeModuleTemplate.c 1.37 => 1.37.110.1 ===
--- ZODB3/BTrees/BTreeModuleTemplate.c:1.37 Tue Jun 25 18:02:27 2002
+++ ZODB3/BTrees/BTreeModuleTemplate.c Tue Dec 23 14:06:22 2003
@@ -12,34 +12,20 @@
****************************************************************************/
+#include "Python.h"
+/* include structmember.h for offsetof */
+#include "structmember.h"
+
#ifdef PERSISTENT
#include "cPersistence.h"
-
-/***************************************************************
- The following are macros that ought to be in cPersistence.h */
-#ifndef PER_USE
-
-#define PER_USE(O) \
-(((O)->state != cPersistent_GHOST_STATE \
- || (cPersistenceCAPI->setstate((PyObject*)(O)) >= 0)) \
- ? (((O)->state==cPersistent_UPTODATE_STATE) \
- ? ((O)->state=cPersistent_STICKY_STATE) : 1) : 0)
-
-#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
/* So sue me. This pair gets used all over the place, so much so that it
@@ -53,15 +39,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 "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
@@ -150,7 +144,8 @@
BTreeItem *data;
} BTree;
-staticforward PyExtensionClass BTreeType;
+static PyTypeObject BTreeType;
+static PyTypeObject BucketType;
#define BTREE(O) ((BTree*)(O))
@@ -252,16 +247,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
@@ -286,8 +281,7 @@
trailing = first;
PER_USE_OR_RETURN(first, -1);
first = first->next;
- PER_ALLOW_DEACTIVATION(trailing);
- PER_ACCESSED(trailing);
+ PER_UNUSE(trailing);
if (first == *current) {
*current = trailing;
@@ -300,33 +294,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"
@@ -385,81 +391,99 @@
BTREEITEMSTEMPLATE_C
;
-void
-INITMODULE (void)
+int
+init_persist_type(PyTypeObject *type)
{
- PyObject *m, *d, *c;
+ type->ob_type = &PyType_Type;
+ type->tp_base = cPersistenceCAPI->pertype;
- 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;
+ if (PyType_Ready(type) < 0)
+ return 0;
- UNLESS (PyExtensionClassCAPI=PyCObject_Import("ExtensionClass","CAPI"))
- return;
-
-#ifdef PERSISTENT
- if ((cPersistenceCAPI=PyCObject_Import("cPersistence","CAPI")))
- {
- BucketType.methods.link=cPersistenceCAPI->methods;
- BucketType.tp_getattro=cPersistenceCAPI->getattro;
- BucketType.tp_setattro=cPersistenceCAPI->setattro;
-
- SetType.methods.link=cPersistenceCAPI->methods;
- SetType.tp_getattro=cPersistenceCAPI->getattro;
- SetType.tp_setattro=cPersistenceCAPI->setattro;
-
- BTreeType.methods.link=cPersistenceCAPI->methods;
- BTreeType.tp_getattro=cPersistenceCAPI->getattro;
- BTreeType.tp_setattro=cPersistenceCAPI->setattro;
-
- TreeSetType.methods.link=cPersistenceCAPI->methods;
- TreeSetType.tp_getattro=cPersistenceCAPI->getattro;
- TreeSetType.tp_setattro=cPersistenceCAPI->setattro;
- }
- else return;
-
- /* 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.POSException");
+ 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("persistent.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("_" 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/BTreeItemsTemplate.c 1.19 => 1.19.30.1 ===
--- ZODB3/BTrees/BTreeItemsTemplate.c:1.19 Sun Mar 16 16:42:29 2003
+++ ZODB3/BTrees/BTreeItemsTemplate.c Tue Dec 23 14:06:22 2003
@@ -72,44 +72,43 @@
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_UNUSE(b);
+ Py_DECREF(b);
+ b = next;
+ PER_USE_OR_RETURN(b, -1);
+ }
+ PER_UNUSE(b);
+ Py_DECREF(b);
- return r >= 0 ? r : 0;
+ return r >= 0 ? r : 0;
}
static int
@@ -167,8 +166,7 @@
PER_USE_OR_RETURN(currentbucket, -1);
max = currentbucket->len - currentoffset - 1;
b = currentbucket->next;
- PER_ALLOW_DEACTIVATION(currentbucket);
- PER_ACCESSED(currentbucket);
+ PER_UNUSE(currentbucket);
if (delta <= max) {
currentoffset += delta;
pseudoindex += delta;
@@ -206,8 +204,7 @@
delta += currentoffset + 1;
PER_USE_OR_RETURN(currentbucket, -1);
currentoffset = currentbucket->len - 1;
- PER_ALLOW_DEACTIVATION(currentbucket);
- PER_ACCESSED(currentbucket);
+ PER_UNUSE(currentbucket);
}
assert(pseudoindex == i);
@@ -218,8 +215,7 @@
*/
PER_USE_OR_RETURN(currentbucket, -1);
error = currentoffset < 0 || currentoffset >= currentbucket->len;
- PER_ALLOW_DEACTIVATION(currentbucket);
- PER_ACCESSED(currentbucket);
+ PER_UNUSE(currentbucket);
if (error) {
PyErr_SetString(PyExc_RuntimeError,
"the bucket being iterated changed size");
@@ -238,6 +234,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 +301,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 +460,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 +476,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 +572,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 */
+};
More information about the Zope-Checkins
mailing list