[Zope-Checkins] CVS: Zope3/lib/python/Persistence/BTrees - .cvsignore:1.2 BTreeItemsTemplate.c:1.2 BTreeModuleTemplate.c:1.2 BTreeTemplate.c:1.2 BucketTemplate.c:1.2 Exception.py:1.2 IIBTree.py:1.2 IOBTree.py:1.2 Interfaces.py:1.2 Length.py:1.2 Maintainer.txt:1.2 MergeTemplate.c:1.2 OIBTree.py:1.2 OOBTree.py:1.2 SetOpTemplate.c:1.2 SetTemplate.c:1.2 TreeSetTemplate.c:1.2 _IIBTree.c:1.2 _IOBTree.c:1.2 _OIBTree.c:1.2 _OOBTree.c:1.2 __init__.py:1.2 _fsBTree.c:1.2 convert.py:1.2 intkeymacros.h:1.2 intvaluemacros.h:1.2 objectkeymacros.h:1.2 objectvaluemacros.h:1.2 sorters.c:1.2
Jim Fulton
jim@zope.com
Mon, 10 Jun 2002 19:28:45 -0400
Update of /cvs-repository/Zope3/lib/python/Persistence/BTrees
In directory cvs.zope.org:/tmp/cvs-serv17445/lib/python/Persistence/BTrees
Added Files:
.cvsignore BTreeItemsTemplate.c BTreeModuleTemplate.c
BTreeTemplate.c BucketTemplate.c Exception.py IIBTree.py
IOBTree.py Interfaces.py Length.py Maintainer.txt
MergeTemplate.c OIBTree.py OOBTree.py SetOpTemplate.c
SetTemplate.c TreeSetTemplate.c _IIBTree.c _IOBTree.c
_OIBTree.c _OOBTree.c __init__.py _fsBTree.c convert.py
intkeymacros.h intvaluemacros.h objectkeymacros.h
objectvaluemacros.h sorters.c
Log Message:
Merged Zope-3x-branch into newly forked Zope3 CVS Tree.
=== Zope3/lib/python/Persistence/BTrees/.cvsignore 1.1 => 1.2 ===
+Makefile
+Makefile.pre
+Makefile.pre.in
+config.c
=== Zope3/lib/python/Persistence/BTrees/BTreeItemsTemplate.c 1.1 => 1.2 === (511/611 lines abridged)
+
+ Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define BTREEITEMSTEMPLATE_C "$Id$\n"
+
+/* A BTreeItems struct is returned from calling .items(), .keys() or
+ * .values() on a BTree-based data structure, and is also the result of
+ * taking slices of those. It represents a contiguous slice of a BTree.
+ *
+ * The start of the slice is in firstbucket, at offset first. The end of
+ * the slice is in lastbucket, at offset last. Both endpoints are inclusive.
+ * It should be possible to get from firstbucket to lastbucket via following
+ * bucket 'next' pointers zero or more times. firstbucket, first, lastbucket,
+ * and last are readonly after initialization. An empty slice is represented
+ * by [XXX (firstbucket == NULL) or (firstbucket == lastbucket and
+ * first > last) XXX].
+ *
+ * 'kind' determines whether this slice represents 'k'eys alone, 'v'alues
+ * alone, or 'i'items (key+value pairs). 'kind' is also readonly after
+ * initialization.
+ *
+ * [XXX currentoffset and currentbucket appear to be used to return function
+ * results XXX]
+ *
+ * [XXX pseudoindex may be the index corresponding to the position identified
+ * by the currentbucket+currenoffset pair. Seems to be a kind of search
+ * finger. XXX]
+ */
+typedef struct {
+ PyObject_HEAD
+ Bucket *firstbucket; /* First bucket */
+ Bucket *currentbucket; /* Current bucket */
+ Bucket *lastbucket; /* Last bucket */
+ int currentoffset; /* Offset in currentbucket */
+ int pseudoindex; /* It's an indicator (what?) */
+ int first; /* Start offset in firstbucket */
+ int last; /* End offset in lastbucket */
+ char kind; /* 'k', 'v', 'i' */
+} BTreeItems;
+
[-=- -=- -=- 511 lines omitted -=- -=- -=-]
+ PER_ALLOW_DEACTIVATION(currentbucket);
+ }
+ else
+ {
+ i->position = -1;
+ PyErr_Clear();
+ }
+ }
+ return 0;
+}
+
+static int
+nextTreeSetItems(SetIteration *i)
+{
+ if (i->position >= 0)
+ {
+ if (i->position)
+ {
+ DECREF_KEY(i->key);
+ }
+
+ if (BTreeItems_seek(ITEMS(i->set), i->position) >= 0)
+ {
+ Bucket *currentbucket;
+
+ currentbucket = BUCKET(ITEMS(i->set)->currentbucket);
+ UNLESS(PER_USE(currentbucket))
+ {
+ /* Mark iteration terminated, so that finiSetIteration doesn't
+ * try to redundantly decref the key and value
+ */
+ i->position = -1;
+ return -1;
+ }
+
+ COPY_KEY(i->key, currentbucket->keys[ITEMS(i->set)->currentoffset]);
+ INCREF_KEY(i->key);
+
+ i->position ++;
+
+ PER_ALLOW_DEACTIVATION(currentbucket);
+ }
+ else
+ {
+ i->position = -1;
+ PyErr_Clear();
+ }
+ }
+ return 0;
+}
=== Zope3/lib/python/Persistence/BTrees/BTreeModuleTemplate.c 1.1 => 1.2 === (428/528 lines abridged)
+
+ Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#include "Python.h"
+/* include structmember.h for offsetof */
+#include "structmember.h"
+
+#ifdef PERSISTENT
+#include "cPersistence.h"
+#include "cPersistenceAPI.h"
+#else
+#define PER_USE_OR_RETURN(self, NULL)
+#define PER_ALLOW_DEACTIVATION(self)
+#define PER_PREVENT_DEACTIVATION(self)
+#define PER_DEL(self)
+#define PER_USE(O) 1
+#define PER_ACCESSED(O) 1
+#define PER_CHANGED(O) 0
+#endif
+
+/*
+ The tp_name slots of the various BTree types contain the fully
+ qualified names of the types, e.g. Persistence.BTrees.OOBTree.OOBTree.
+ The full name is usd to support pickling and because it is not
+ possible to modify the __module__ slot of a type dynamically. (This
+ may be a bug in Python 2.2).
+*/
+
+#define MODULE_NAME "Persistence.BTrees." MOD_NAME_PREFIX "BTree."
+
+static PyObject *sort_str, *reverse_str, *__setstate___str;
+static PyObject *ConflictError = NULL;
+
+static void PyVar_Assign(PyObject **v, PyObject *e) { Py_XDECREF(*v); *v=e;}
+#define ASSIGN(V,E) PyVar_Assign(&(V),(E))
+#define ASSIGNC(V,E) (Py_INCREF((E)), PyVar_Assign(&(V),(E)))
+#define UNLESS(E) if (!(E))
+#define UNLESS_ASSIGN(V,E) ASSIGN(V,E); UNLESS(V)
+#define LIST(O) ((PyListObject*)(O))
+#define OBJECT(O) ((PyObject*)(O))
[-=- -=- -=- 428 lines omitted -=- -=- -=-]
+ m = PyImport_ImportModule("Persistence.BTrees.Exception");
+ if (m != NULL) {
+ c = PyObject_GetAttrString(m, "BTreesConflictError");
+ if (c != NULL)
+ ConflictError = c;
+ Py_DECREF(m);
+ }
+
+ if (ConflictError == NULL) {
+ Py_INCREF(PyExc_ValueError);
+ ConflictError=PyExc_ValueError;
+ }
+
+#ifdef INTSET_H
+ UNLESS(d = PyImport_ImportModule("intSet")) return;
+ UNLESS(intSetType = PyObject_GetAttrString (d, "intSet")) return;
+ Py_DECREF (d);
+#endif
+
+ /* Initialize the PyPersist_C_API and the type objects. */
+ PyPersist_C_API = PyCObject_Import("Persistence.cPersistence", "C_API");
+ if (PyPersist_C_API == NULL)
+ return;
+
+ BTreeItemsType.ob_type = &PyType_Type;
+ init_persist_type(&BucketType);
+ init_persist_type(&BTreeType);
+ init_persist_type(&SetType);
+ init_persist_type(&TreeSetType);
+
+ /* Create the module and add the functions */
+ m = Py_InitModule4("_" MOD_NAME_PREFIX "BTree",
+ module_methods, BTree_module_documentation,
+ (PyObject *)NULL, PYTHON_API_VERSION);
+
+ /* Add some symbolic constants to the module */
+ d = PyModule_GetDict(m);
+ if (PyDict_SetItemString(d, MOD_NAME_PREFIX "Bucket",
+ (PyObject *)&BucketType) < 0)
+ return;
+ if (PyDict_SetItemString(d, MOD_NAME_PREFIX "BTree",
+ (PyObject *)&BTreeType) < 0)
+ return;
+ if (PyDict_SetItemString(d, MOD_NAME_PREFIX "Set",
+ (PyObject *)&SetType) < 0)
+ return;
+ if (PyDict_SetItemString(d, MOD_NAME_PREFIX "TreeSet",
+ (PyObject *)&TreeSetType) < 0)
+ return;
+}
=== Zope3/lib/python/Persistence/BTrees/BTreeTemplate.c 1.1 => 1.2 === (1343/1443 lines abridged)
+
+ Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define BTREETEMPLATE_C "$Id$\n"
+
+/*
+** _BTree_get
+**
+** Search a BTree.
+**
+** Arguments
+** self a pointer to a BTree
+** keyarg the key to search for, as a Python object
+** has_key true/false; when false, try to return the associated
+** value; when true, return a boolean
+** Return
+** When has_key false:
+** If key exists, its associated value.
+** If key doesn't exist, NULL and KeyError is set.
+** When has_key true:
+** A Python int is returned in any case.
+** If key exists, the depth of the bucket in which it was found.
+** If key doesn't exist, 0.
+*/
+static PyObject *
+_BTree_get(BTree *self, PyObject *keyarg, int has_key)
+{
+ KEY_TYPE key;
+ int min; /* index of child to search */
+ PyObject *r = NULL; /* result object */
+ int copied = 1;
+
+ COPY_KEY_FROM_ARG(key, keyarg, copied);
+ UNLESS (copied) return NULL;
+
+ PyPersist_INCREF(self);
+ if (!PyPersist_IS_STICKY(self))
+ return NULL;
+
+ BTREE_SEARCH(min, self, key, goto Error);
[-=- -=- -=- 1343 lines omitted -=- -=- -=-]
+{
+ return BTree_length_or_nonzero(self, 1);
+}
+
+static PyNumberMethods BTree_as_number_for_nonzero = {
+ 0,0,0,0,0,0,0,0,0,0,
+ (inquiry)BTree_nonzero};
+
+static PyTypeObject BTreeType = {
+ PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+ 0, /* ob_size */
+ MODULE_NAME MOD_NAME_PREFIX "BTree",/* tp_name */
+ sizeof(BTree), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)BTree_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ &BTree_as_number_for_nonzero, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ &BTree_as_mapping, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)BTree_traverse, /* tp_traverse */
+ (inquiry)BTree_tp_clear, /* tp_clear */
+ 0, /* tp_richcompare */
+ offsetof(BTree, po_weaklist), /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ BTree_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ BTree_init, /* tp_init */
+ 0, /* tp_alloc */
+ PyType_GenericNew, /* tp_new */
+};
=== Zope3/lib/python/Persistence/BTrees/BucketTemplate.c 1.1 => 1.2 === (1310/1410 lines abridged)
+
+ Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define BUCKETTEMPLATE_C "$Id$\n"
+
+/* Use BUCKET_SEARCH to find the index at which a key belongs.
+ * INDEX An int lvalue to hold the index i such that KEY belongs at
+ * SELF->keys[i]. Note that this will equal SELF->len if KEY
+ * is larger than the bucket's largest key. Else it's the
+ * smallest i such that SELF->keys[i] >= KEY.
+ * ABSENT An int lvalue to hold a Boolean result, true (!= 0) if the
+ * key is absent, false (== 0) if the key is at INDEX.
+ * SELF A pointer to a Bucket node.
+ * KEY The key you're looking for, of type KEY_TYPE.
+ * ONERROR What to do if key comparison raises an exception; for example,
+ * perhaps 'return NULL'.
+ *
+ * See Maintainer.txt for discussion: this is optimized in subtle ways.
+ * It's recommended that you call this at the start of a routine, waiting
+ * to check for self->len == 0 after (if an empty bucket is special in
+ * context; INDEX becomes 0 and ABSENT becomes true if this macro is run
+ * with an empty SELF, and that may be all the invoker needs to know).
+ */
+#define BUCKET_SEARCH(INDEX, ABSENT, SELF, KEY, ONERROR) { \
+ int _lo = 0; \
+ int _hi = (SELF)->len; \
+ int _i; \
+ int _cmp = 1; \
+ for (_i = _hi >> 1; _lo < _hi; _i = (_lo + _hi) >> 1) { \
+ TEST_KEY_SET_OR(_cmp, (SELF)->keys[_i], (KEY)) \
+ ONERROR; \
+ if (_cmp < 0) _lo = _i + 1; \
+ else if (_cmp == 0) break; \
+ else _hi = _i; \
+ } \
+ (INDEX) = _i; \
+ (ABSENT) = _cmp; \
+}
+
+/*
[-=- -=- -=- 1310 lines omitted -=- -=- -=-]
+ 0, /* tp_richcompare */
+ offsetof(Bucket, po_weaklist), /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ Bucket_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ Bucket_init, /* tp_init */
+ 0, /* tp_alloc */
+ PyType_GenericNew, /* tp_new */
+};
+
+static int
+nextBucket(SetIteration *i)
+{
+ if (i->position >= 0)
+ {
+ UNLESS(PER_USE(BUCKET(i->set))) return -1;
+
+ if (i->position)
+ {
+ DECREF_KEY(i->key);
+ DECREF_VALUE(i->value);
+ }
+
+ if (i->position < BUCKET(i->set)->len)
+ {
+ COPY_KEY(i->key, BUCKET(i->set)->keys[i->position]);
+ INCREF_KEY(i->key);
+ COPY_VALUE(i->value, BUCKET(i->set)->values[i->position]);
+ INCREF_VALUE(i->value);
+ i->position ++;
+ }
+ else
+ {
+ i->position = -1;
+ PyPersist_SetATime(BUCKET(i->set));
+ }
+
+ PyPersist_DECREF(BUCKET(i->set));
+ }
+
+
+ return 0;
+}
=== Zope3/lib/python/Persistence/BTrees/Exception.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+from Transaction.Exceptions import ConflictError
+
+class BTreesConflictError(ConflictError):
+
+ msgs = ['',
+ 'Conflicting changes', # in i2 & i3
+ 'Conflicting del and change', # in i3 & i2
+ 'Conflicting del and change', # in i2 & i3
+ 'Conflicting inserts or deletes',
+ 'Conflicting deletes',
+ 'Conflicting inserts',
+ 'Conflicting deletes or delete and change',
+ 'Conflicting deletes or delete and change',
+ ]
+
+ def __init__(self, p1, p2, p3, reason):
+ self.p1 = p1
+ self.p2 = p2
+ self.p3 = p3
+ self.reason = reason
+
+ def __repr__(self):
+ return "BTreesConflictError(%d, %d, %d, %d)" % (self.p1,
+ self.p2,
+ self.p3,
+ self.reason)
+ def __str__(self):
+ return "BTrees conflict error at %d/%d/%d: %s" % (
+ self.p1, self.p2, self.p3, self.msgs[self.reason])
+
=== Zope3/lib/python/Persistence/BTrees/IIBTree.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+from _IIBTree import *
=== Zope3/lib/python/Persistence/BTrees/IOBTree.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+from _IOBTree import *
=== Zope3/lib/python/Persistence/BTrees/Interfaces.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+import OOBTree, Interface, Interface.Standard
+
+class ICollection(Interface.Base):
+
+ def clear():
+ """Remove all of the items from the collection"""
+
+ def __nonzero__():
+ """Check if the collection is non-empty.
+
+ Return a true value if the collection is non-empty and a
+ false otherwise.
+ """
+
+class IReadSequence(Interface.Standard.Sequence):
+
+ def __getslice__(index1, index2):
+ """Return a subsequence from the original sequence
+
+ Such that the subsequence includes the items from index1 up
+ to, but not including, index2.
+ """
+
+class IKeyed(ICollection):
+
+ def has_key(key):
+ """Check whether the object has an item with the given key"""
+
+ def keys(min=None, max=None):
+ """Return an IReadSequence containing the keys in the collection
+
+ The type of the IReadSequence is not specified. It could be a
+ list or a tuple or some other type.
+
+ If a min is specified, then output is constrained to
+ items having keys greater than or equal to the given min.
+ A min value of None is ignored.
+
+ If a max is specified, then output is constrained to
+ items having keys less than or equal to the given min.
+ A max value of None is ignored.
+ """
+
+ def maxKey(key=None):
+ """Return the maximum key
+
+ If a key argument if provided, return the largest key that is
+ less than or equal to the argument.
+ """
+
+ def minKey(key=None):
+ """Return the minimum key
+
+ If a key argument if provided, return the smallest key that is
+ greater than or equal to the argument.
+ """
+
+class ISetMutable(IKeyed):
+
+ def insert(key):
+ """Add the key (value) to the set.
+
+ If the key was already in the set, return 0, otherwise return 1.
+ """
+
+ def remove(key):
+ """Remove the key from the set."""
+
+ def update(seq):
+ """Add the items from the given sequence to the set"""
+
+class IKeySequence(IKeyed, Interface.Standard.Sized):
+
+ def __getitem__(index):
+ """Return the key in the given index position
+
+ This allows iteration with for loops and use in functions,
+ like map and list, that read sequences.
+ """
+
+class ISet(IKeySequence, ISetMutable):
+ pass
+
+class ITreeSet(IKeyed, ISetMutable):
+ pass
+
+
+class IDictionaryIsh(IKeyed, Interface.Standard.MinimalDictionary):
+
+ def update(collection):
+ """Add the items from the given collection object to the collection
+
+ The input collection must be a sequence of key-value tuples,
+ or an object with an 'items' method that returns a sequence of
+ key-value tuples.
+ """
+
+ def values(min=None, max=None):
+ """Return a IReadSequence containing the values in the collection
+
+ The type of the IReadSequence is not specified. It could be a
+ list or a tuple or some other type.
+
+ If a min is specified, then output is constrained to
+ items having keys greater than or equal to the given min.
+ A min value of None is ignored.
+
+ If a max is specified, then output is constrained to
+ items having keys less than or equal to the given min.
+ A max value of None is ignored.
+ """
+
+ def items(min=None, max=None):
+ """Return a IReadSequence containing the items in the collection
+
+ An item is a key-value tuple.
+
+ The type of the IReadSequence is not specified. It could be a
+ list or a tuple or some other type.
+
+ If a min is specified, then output is constrained to
+ items having keys greater than or equal to the given min.
+ A min value of None is ignored.
+
+ If a max is specified, then output is constrained to
+ items having keys less than or equal to the given min.
+ A max value of None is ignored.
+ """
+
+ def byValue(minValue):
+ """Return a sequence of value-key pairs, sorted by value
+
+ Values < min are ommitted and other values are "normalized" by
+ the minimum value. This normalization may be a noop, but, for
+ integer values, the normalization is division.
+ """
+
+class IBTree(IDictionaryIsh):
+
+ def insert(key, value):
+ """Insert a key and value into the collection.
+
+ If the key was already in the collection, then there is no
+ change and 0 is returned.
+
+ If the key was not already in the collection, then the item is
+ added and 1 is returned.
+
+ This method is here to allow one to generate random keys and
+ to insert and test whether the key was there in one operation.
+
+ A standard idiom for generating new keys will be::
+
+ key=generate_key()
+ while not t.insert(key, value):
+ key=generate_key()
+ """
+
+class IMerge(Interface.Base):
+ """Object with methods for merging sets, buckets, and trees.
+
+ These methods are supplied in modules that define collection
+ classes with particular key and value types. The operations apply
+ only to collections from the same module. For example, the
+ IIBTree.union can only be used with IIBTree.IIBTree,
+ IIBTree.IIBucket, IIBTree.IISet, and IIBTree.IITreeSet.
+
+ The implementing module has a value type. The IOBTree and OOBTree
+ modules have object value type. The IIBTree and OIBTree modules
+ have integer value tyoes. Other modules may be defined in the
+ future that have other value types.
+
+ The individual types are classified into set (Set and TreeSet) and
+ mapping (Bucket and BTree) types.
+ """
+
+ def difference(c1, c2):
+ """Return the keys or items in c1 for which there is no key in
+ c2.
+
+ If c1 is None, then None is returned. If c2 is none, then c1
+ is returned.
+ """
+
+ def union(c1, c2):
+ """Compute the Union of c1 and c2.
+
+ If c1 is None, then c2 is returned, otherwise, if c2 is None,
+ then c1 is returned.
+
+ The output is a Set containing keys from the input
+ collections.
+ """
+
+ def intersection(c1, c2):
+ """Compute the Union of c1 and c2.
+
+ If c1 is None, then c2 is returned, otherwise, if c2 is None,
+ then c1 is returned.
+
+ The output is a Set containing matching keys from the input
+ collections.
+ """
+
+class IIMerge(IMerge):
+ """Merge collections with integer value type.
+
+ A primary intent is to support operations with no or integer
+ values, which are used as "scores" to rate indiviual keys. That
+ is, in this context, a BTree or Bucket is viewed as a set with
+ scored keys, using integer scores.
+ """
+
+ def weightedUnion(c1, c2, weight1=1, weight2=1):
+ """Compute the weighted Union of c1 and c2.
+
+ If c1 and c2 are None, the output is 0 and None
+
+ if c1 is None and c2 is not None, the output is weight2 and
+ c2.
+
+ if c1 is not None and c2 not None, the output is weight1 and
+ c1.
+
+ If c1 and c2 are not None, the output is 1 and a Bucket
+ such that the output values are::
+
+ v1*weight1 + v2*weight2
+
+ where:
+
+ v1 is 0 if the key was not in c1. Otherwise, v1 is 1, if
+ c1 is a set, or the value from c1.
+
+ v2 is 0 if the key was not in c2. Otherwise, v2 is 2, if
+ c2 is a set, or the value from c2.
+
+ Note that c1 and c2 must be collections. None may not be
+ passed as one of the collections.
+ """
+
+ def weightedIntersection(c1, c2, weight1=1, weight2=1):
+ """Compute the weighted intersection of c1 and c2.
+
+ If c1 and c2 are None, the output is None, None.
+
+ if c1 is None and c2 is not None, the output is weight2 and
+ c2.
+
+ if c1 is not None and c2 not None, the output is weight1 and
+ c1.
+
+ If c1 and c2 are sets, the output is the sum of the weights
+ and the (unweighted) intersection of the sets.
+
+ If c1 and c2 are not None and not both sets, the output is 1
+ and a Bucket such that the output values are::
+
+ v1*weight1 + v2*weight2
+
+ where:
+
+ v1 is 0 if the key was not in c1. Otherwise, v1 is 1, if
+ c1 is a set, or the value from c1.
+
+ v2 is 0 if the key was not in c2. Otherwise, v2 is 2, if
+ c2 is a set, or the value from c2.
+
+ Note that c1 and c2 must be collections. None may not be
+ passed as one of the collections.
+ """
+
+###############################################################
+# IMPORTANT NOTE
+#
+# Getting the length of a BTree, TreeSet, or output of keys,
+# values, or items of same is expensive. If you need to get the
+# length, you need to maintain this separately.
+#
+# Eventually, I need to express this through the interfaces.
+#
+################################################################
+
+OOBTree.OOSet.__implements__=ISet
+OOBTree.OOTreeSet.__implements__=ITreeSet
+OOBTree.OOBucket.__implements__=IDictionaryIsh
+OOBTree.OOBTree.__implements__=IBTree
=== Zope3/lib/python/Persistence/BTrees/Length.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+import Persistence
+
+class Length(Persistence.Persistent):
+ """BTree lengths are too expensive to compute
+
+ Objects that use BTrees need to keep track of lengths themselves.
+ This class provides an object for doing this.
+
+ As a bonus, the object support application-level conflict resolution.
+ """
+
+ def __init__(self, v=0): self.value=v
+
+ def __getstate__(self): return self.value
+
+ def __setstate__(self, v): self.value=v
+
+ def set(self, v): self.value=v
+
+ def _p_resolveConflict(self, old, s1, s2): return s1 + s2 - old
+
+ def _p_independent(self):
+ # My state doesn't depend on or materially effect the state of
+ # other objects.
+ return 1
+
+ def change(self, delta): self.value = self.value + delta
+
+ def __call__(self, *args): return self.value
=== Zope3/lib/python/Persistence/BTrees/Maintainer.txt 1.1 => 1.2 ===
+extend BTrees.
+
+Macros
+======
+BTrees are defined using a "template", roughly akin to a a C++
+template. To create a new family of BTrees, create a source file that
+defines macros used to handle differences in key and value types:
+
+
+Configuration Macros
+
+MASTER_ID
+A string to hold an RCS/CVS Id key to be included in compiled binaries.
+
+MOD_NAME_PREFIX
+A string (like "IO" or "OO") that provides the prefix used for the
+module. This gets used to generate type names and the internal module
+name string.
+
+DEFAULT_MAX_BUCKET_SIZE
+An int giving the maximum bucket size (number of key/value pairs).
+When a bucket gets larger than this due to an insertion *into a BTREE*,
+it splits. Inserting into a bucket directly doesn't split, and
+functions that produce a bucket output (e.g., union()) also have no
+bound on how large a bucket may get. Someday this will be tunable
+on BTree instances.
+
+DEFAULT_MAX_BTREE_SIZE
+An int giving the maximum size (number of children) of an internal
+btree node. Someday this will be tunable on BTree instances.
+
+
+Macros for Keys
+
+KEY_TYPE
+The C type declaration for keys (e.g., int or PyObject*).
+
+KEY_TYPE_IS_PYOBJECT
+Define if KEY_TYPE is a PyObject*, else undef.
+
+KEY_CHECK(K)
+Tests whether the PyObject* K can be converted to the (C) key type
+(KEY_TYPE). The macro should return a boolean (zero for false,
+non-zero for true). When it returns false, its caller should probably
+set a TypeError exception.
+
+TEST_KEY_SET_OR(V, K, T)
+Like Python's cmp(). Compares K(ey) to T(arget), where K & T are C
+values of type KEY_TYPE. V is assigned an int value depending on
+the outcome:
+ < 0 if K < T
+ == 0 if K == T
+ > 0 if K > T
+This macro acts like an 'if', where the following statement is
+executed only if a Python exception has been raised because the
+values could not be compared.
+
+DECREF_KEY(K)
+K is a value of KEY_TYPE. If KEY_TYPE is a flavor of PyObject*, write
+this to do Py_DECREF(K). Else (e.g., KEY_TYPE is int) make it a nop.
+
+INCREF_KEY(K)
+K is a value of KEY_TYPE. If KEY_TYPE is a flavor of PyObject*, write
+this to do Py_INCREF(K). Else (e.g., KEY_TYPE is int) make it a nop.
+
+COPY_KEY(K, E)
+Like K=E. Copy a key from E to K, both of KEY_TYPE. Note that this
+doesn't decref K or incref E when KEY_TYPE is a PyObject*; the caller
+is responsible for keeping refcounts straight.
+
+COPY_KEY_TO_OBJECT(O, K)
+Roughly like O=K. O is a PyObject*, and the macro must build a Python
+object form of K, assign it to O, and ensure that O owns the reference
+to its new value. It may do this by creating a new Python object based
+on K (e.g., PyInt_FromLong(K) when KEY_TYPE is int), or simply by doing
+Py_INCREF(K) if KEY_TYPE is a PyObject*.
+
+COPY_KEY_FROM_ARG(TARGET, ARG, STATUS)
+Copy an argument to the target without creating a new reference to ARG.
+ARG is a PyObject*, and TARGET is of type KEY_TYPE. If this can't be
+done (for example, KEY_CHECK(ARG) returns false), set a Python error
+and set status to 0. If there is no error, leave status alone.
+
+
+Macros for Values
+
+VALUE_TYPE
+The C type declaration for values (e.g., int or PyObject*).
+
+VALUE_TYPE_IS_PYOBJECT
+Define if VALUE_TYPE is a PyObject*, else undef.
+
+TEST_VALUE(X, Y)
+Like Python's cmp(). Compares X to Y, where X & Y are C values of
+type VALUE_TYPE. The macro returns an int, with value
+ < 0 if X < Y
+ == 0 if X == Y
+ > 0 if X > Y
+XXX There is no provision for determining whether the comparison
+attempt failed (set a Python exception).
+
+DECREF_VALUE(K)
+Like DECREF_KEY, except applied to values of VALUE_TYPE.
+
+INCREF_VALUE(K)
+Like INCREF_KEY, except applied to values of VALUE_TYPE.
+
+COPY_VALUE(K, E)
+Like COPY_KEY, except applied to values of VALUE_TYPE.
+
+COPY_VALUE_TO_OBJECT(O, K)
+Like COPY_KEY_TO_OBJECT, except applied to values of VALUE_TYPE.
+
+COPY_VALUE_FROM_ARG(TARGET, ARG, STATUS)
+Like COPY_KEY_FROM_ARG, except applied to values of VALUE_TYPE.
+
+NORMALIZE_VALUE(V, MIN)
+Normalize the value, V, using the parameter MIN. This is almost
+certainly a YAGNI. It is a no op for most types. For integers, V is
+replaced by V/MIN only if MIN > 0.
+
+
+Macros for Set Operations
+
+MERGE_DEFAULT
+A value of VALUE_TYPE specifying the value to associate with set
+elements when sets are merged with mappings via weighed union or
+weighted intersection.
+
+MERGE(O1, w1, O2, w2)
+Performs a weighted merge of two values, O1 and O2, using weights w1
+and w2. The result must be of VALUE_TYPE. Note that weighted unions
+and weighted intersections are not enabled if this macro is left
+undefined.
+
+MERGE_WEIGHT(O, w)
+Computes a weighted value for O. The result must be of VALUE_TYPE.
+This is used for "filling out" weighted unions, i.e. to compute a
+weighted value for keys that appear in only one of the input
+mappings. If left undefined, MERGE_WEIGHT defaults to
+
+ #define MERGE_WEIGHT(O, w) (O)
+
+MULTI_INT_UNION
+The value doesn't matter. If defined, SetOpTemplate.c compiles
+code for a multiunion() function (compute a union of many input sets
+at high speed). This currently makes sense only for II sets, so
+only _IIBTree.c defines it.
+
+
+BTree Clues
+===========
+More or less random bits of helpful info.
+
++ In papers and textbooks, this flavor of BTree is usually called
+ a B+-Tree, where "+" is a superscript.
+
++ All keys and all values live in the bucket leaf nodes. Keys in
+ interior (BTree) nodes merely serve to guide a search efficiently
+ toward the correct leaf.
+
++ When a key is deleted, it's physically removed from the bucket
+ it's in, but this doesn't propagate back up the tree: since keys
+ in interior nodes only serve to guide searches, it's OK-- and
+ saves time --to leave "stale" keys in interior nodes.
+
++ No attempt is made to rebalance the tree after a deletion, unless
+ a bucket thereby becomes entirely empty. "Classic BTrees" do
+ rebalance, keeping all buckets at least half full (provided there
+ are enough keys in the entire tree to fill half a bucket). The
+ tradeoffs are murky. Pathological cases in the presence of
+ deletion do exist. Pathologies include trees tending toward only
+ one key per bucket, and buckets at differing depths (all buckets
+ are at the same depth in a classic BTree).
+
++ DEFAULT_MAX_BUCKET_SIZE and DEFAULT_MAX_BTREE_SIZE are chosen
+ mostly to "even out" pickle sizes in storage. That's why, e.g.,
+ an IIBTree has larger values than an OOBTree: pickles store ints
+ more efficiently than they can store arbitrary Python objects.
+
+
+The BTREE_SEARCH Macro
+======================
+For notational ease, consider a fixed BTree node x, and let
+
+ K(i) mean x->data.key[i]
+ C(i) mean all the keys reachable from x->data.child[i]
+
+For each i in 0 to x->len-1 inclusive,
+
+ K(i) <= C(i) < K(i+1)
+
+is a BTree node invariant, where we pretend that K(0) holds a key
+smaller than any possible key, and K(x->len) holds a key larger
+than any possible key. (Note that K(x->len) doesn't actually exist,
+and K(0) is never used although space for it exists in non-empty
+BTree nodes.)
+
+When searching for a key k, then, the child pointer we want to follow
+is the one at index i such that K(i) <= k < K(i+1). There can be
+at most one such i, since the K(i) are strictly increasing. And there
+is at least one such i provided the tree isn't empty (so that 0 < len).
+For the moment, assume the tree isn't empty (we'll get back to that
+later).
+
+The macro's chief loop invariant is
+
+ K(lo) < k < K(hi)
+
+This holds trivially at the start, since lo is set to 0, and hi to
+x->len, and we pretend K(0) is minus infinity and K(len) is plus
+infinity. Inside the loop, if K(i) < k we set lo to i, and if
+K(i) > k we set hi to i. These obviously preserve the invariant.
+If K(i) == k, the loop breaks and sets the result to i, and since
+K(i) == k in that case i is obviously the correct result.
+
+Other cases depend on how i = floor((lo + hi)/2) works, exactly.
+Suppose lo + d = hi for some d >= 0. Then i = floor((lo + lo + d)/2) =
+floor(lo + d/2) = lo + floor(d/2). So:
+
+a. [d == 0] (lo == i == hi) if and only if (lo == hi).
+b. [d == 1] (lo == i < hi) if and only if (lo+1 == hi).
+c. [d > 1] (lo < i < hi) if and only if (lo+1 < hi).
+
+If the node is empty (x->len == 0), then lo==i==hi==0 at the start,
+and the loop exits immediately (the first "i > lo" test fails),
+without entering the body.
+
+Else lo < hi at the start, and the invariant K(lo) < k < K(hi) holds.
+
+If lo+1 < hi, we're in case #c: i is strictly between lo and hi,
+so the loop body is entered, and regardless of whether the body sets
+the new lo or the new hi to i, the new lo is strictly less than the
+new hi, and the difference between the new lo and new hi is strictly
+less than the difference between the old lo and old hi. So long as
+the new lo + 1 remains < the new hi, we stay in this case. We can't
+stay in this case forever, though: because hi-lo decreases on each
+trip but remains > 0, lo+1 == hi must eventually become true. (In
+fact, it becomes true quickly, in about log2(x->len) trips; the
+point is more that lo doesn't equal hi when the loop ends, it has to
+end with lo+1==hi and i==lo).
+
+Then we're in case #b: i==lo==hi-1 then, and the loop exits. The
+invariant still holds, with lo==i and hi==lo+1==i+1:
+
+ K(i) < k < K(i+1)
+
+so i is again the correct answer.
+
+Optimization points:
+
++ Division by 2 is done via shift rather via "/2". These are
+ signed ints, and almost all C compilers treat signed int division
+ as truncating, and shifting is not the same as truncation for
+ signed int division. The compiler has no way to know these values
+ aren't negative, so has to generate longer-winded code for "/2".
+ But we know these values aren't negative, and exploit it.
+
++ The order of _cmp comparisons matters. We're in an interior
+ BTree node, and are looking at only a tiny fraction of all the
+ keys that exist. So finding the key exactly in this node is
+ unlikely, and checking _cmp == 0 is a waste of time to the same
+ extent. It doesn't matter whether we check for _cmp < 0 or
+ _cmp > 0 first, so long as we do both before worrying about
+ equality.
+
++ At the start of a routine, it's better to run this macro even
+ if x->len is 0 (check for that afterwards). We just called a
+ function and so probably drained the pipeline. If the first thing
+ we do then is read up self->len and check it against 0, we just
+ sit there waiting for the data to get read up, and then another
+ immediate test-and-branch, and for a very unlikely case (BTree
+ nodes are rarely empty). It's better to get into the loop right
+ away so the normal case makes progress ASAP.
+
+
+The BUCKET_SEARCH Macro
+=======================
+This has a different job than BTREE_SEARCH: the key 0 slot is
+legitimate in a bucket, and we want to find the index at which the
+key belongs. If the key is larger than the bucket's largest key, a
+new slot at index len is where it belongs, else it belongs at the
+smallest i with keys[i] >= the key we're looking for. We also need
+to know whether or not the key is present (BTREE_SEARCH didn't care;
+it only wanted to find the next node to search).
+
+The mechanics of the search are quite similar, though. The primary
+loop invariant changes to (say we're searching for key k):
+
+ K(lo-1) < k < K(hi)
+
+where K(i) means keys[i], and we pretend K(-1) is minus infinity and
+K(len) is plus infinity.
+
+If the bucket is empty, lo=hi=i=0 at the start, the loop body is never
+entered, and the macro sets INDEX to 0 and ABSENT to true. That's why
+_cmp is initialized to 1 (_cmp becomes ABSENT).
+
+Else the bucket is not empty, lo<hi at the start, and the loop body
+is entered. The invariant is obviously satisfied then, as lo=0 and
+hi=len.
+
+If K[i]<k, lo is set to i+1, preserving that K(lo-1) = K[i] < k.
+If K[i]>k, hi is set to i, preserving that K[hi] = K[i] > k.
+If the loop exits after either of those, _cmp != 0, so ABSENT becomes
+true.
+If K[i]=k, the loop breaks, so that INDEX becomes i, and ABSENT
+becomes false (_cmp=0 in this case).
+
+The same case analysis for BTREE_SEARCH on lo and hi holds here:
+
+a. (lo == i == hi) if and only if (lo == hi).
+b. (lo == i < hi) if and only if (lo+1 == hi).
+c. (lo < i < hi) if and only if (lo+1 < hi).
+
+So long as lo+1 < hi, we're in case #c, and either break with
+equality (in which case the right results are obviously computed) or
+narrow the range. If equality doesn't obtain, the range eventually
+narrows to cases #a or #b.
+
+To go from #c to #a, we must have lo+2==hi at the start, and
+K[i]=K[lo+1]<k. Then the new lo gets set to i+1 = lo+2 = hi, and the
+loop exits with lo=hi=i and _cmp<0. This is correct, because we
+know that k != K(i) (loop invariant! we actually know something
+stronger, that k < K(hi); since i=hi, this implies k != K(i)).
+
+Else #c eventually falls into case #b, lo+1==hi and i==lo. The
+invariant tells us K(lo-1) < k < K(hi) = K(lo+1), so if the key
+is present it must be at K(lo). i==lo in this case, so we test
+K(lo) against k. As always, if equality obtains we do the right
+thing, else case #b becomes case #a.
+
+When #b becomes #a, the last comparison was non-equal, so _cmp is
+non-zero, and the loop exits because lo==hi==i in case #a. The
+invariant then tells us K(lo-1) < k < K(lo), so the key is in fact
+not present, it's correct to exit with _cmp non-zero, and i==lo is
+again the index at which k belongs.
+
+Optimization points:
+
++ As for BTREE_SEARCH, shifting of signed ints is cheaper than
+ division.
+
++ Unlike as for BTREE_SEARCH, there's nothing special about searching
+ an empty bucket, and the macro computes thoroughly sensible results
+ in that case.
+
++ The order of _cmp comparisons differs from BTREE_SEARCH. When
+ searching a bucket, it's much more likely (than when searching a
+ BTree node) that the key is present, so testing __cmp==0 isn't a
+ systematic waste of cycles. At the extreme, if all searches are
+ successful (key present), on average this saves one comparison per
+ search, against leaving the determination of _cmp==0 implicit (as
+ BTREE_SEARCH does). But even on successful searches, __cmp != 0 is
+ a more popular outcome than __cmp == 0 across iterations (unless
+ the bucket has only a few keys), so it's important to check one
+ of the inequality cases first. It turns out it's better on average
+ to check K(i) < key (than to check K(i) > key), because when it
+ pays it narrows the range more (we get a little boost from setting
+ lo=i+1 in this case; the other case sets hi=i, which isn't as much
+ of a narrowing).
=== Zope3/lib/python/Persistence/BTrees/MergeTemplate.c 1.1 => 1.2 ===
+
+ Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define MERGETEMPLATE_C "$Id$\n"
+
+/****************************************************************************
+ Set operations
+ ****************************************************************************/
+
+static int
+merge_output(Bucket *r, SetIteration *i, int mapping)
+{
+ if (r->len >= r->size && Bucket_grow(r, -1, !mapping) < 0)
+ return -1;
+ COPY_KEY(r->keys[r->len], i->key);
+ INCREF_KEY(r->keys[r->len]);
+ if (mapping) {
+ COPY_VALUE(r->values[r->len], i->value);
+ INCREF_VALUE(r->values[r->len]);
+ }
+ r->len++;
+ return 0;
+}
+
+static PyObject *
+merge_error(int p1, int p2, int p3, int reason)
+{
+ PyObject *r;
+
+ UNLESS (r=Py_BuildValue("iiii", p1, p2, p3, reason)) r=Py_None;
+ if (ConflictError == NULL) {
+ ConflictError = PyExc_ValueError;
+ Py_INCREF(ConflictError);
+ }
+ PyErr_SetObject(ConflictError, r);
+ if (r != Py_None)
+ {
+ Py_DECREF(r);
+ }
+
+ return NULL;
+}
+
+static PyObject *
+bucket_merge(Bucket *s1, Bucket *s2, Bucket *s3)
+{
+ Bucket *r=0;
+ PyObject *s;
+ SetIteration i1 = {0,0,0}, i2 = {0,0,0}, i3 = {0,0,0};
+ int cmp12, cmp13, cmp23, mapping=0, set;
+
+ if (initSetIteration(&i1, OBJECT(s1), 0, &mapping) < 0)
+ goto err;
+ if (initSetIteration(&i2, OBJECT(s2), 0, &mapping) < 0)
+ goto err;
+ if (initSetIteration(&i3, OBJECT(s3), 0, &mapping) < 0)
+ goto err;
+
+ set = !mapping;
+
+ if (mapping)
+ r = (Bucket *)PyObject_CallObject((PyObject *)&BucketType, NULL);
+ else
+ r = (Bucket *)PyObject_CallObject((PyObject *)&SetType, NULL);
+ if (r == NULL)
+ goto err;
+
+ if (i1.next(&i1) < 0)
+ goto err;
+ if (i2.next(&i2) < 0)
+ goto err;
+ if (i3.next(&i3) < 0)
+ goto err;
+
+ while (i1.position >= 0 && i2.position >= 0 && i3.position >= 0)
+ {
+ TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
+ TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
+ if (cmp12==0)
+ {
+ if (cmp13==0)
+ {
+ if (set || (TEST_VALUE(i1.value, i2.value) == 0))
+ { /* change in i3 or all same */
+ if (merge_output(r, &i3, mapping) < 0) goto err;
+ }
+ else if (set || (TEST_VALUE(i1.value, i3.value) == 0))
+ { /* change in i2 */
+ if (merge_output(r, &i2, mapping) < 0) goto err;
+ }
+ else
+ { /* conflicting changes in i2 and i3 */
+ merge_error(i1.position, i2.position, i3.position, 1);
+ goto err;
+ }
+ if (i1.next(&i1) < 0) goto err;
+ if (i2.next(&i2) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+ else if (cmp13 > 0)
+ { /* insert i3 */
+ if (merge_output(r, &i3, mapping) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+ else if (set || (TEST_VALUE(i1.value, i2.value) == 0))
+ { /* delete i3 */
+ if (i1.next(&i1) < 0) goto err;
+ if (i2.next(&i2) < 0) goto err;
+ }
+ else
+ { /* conflicting del in i3 and change in i2 */
+ merge_error(i1.position, i2.position, i3.position, 2);
+ goto err;
+ }
+ }
+ else if (cmp13 == 0)
+ {
+ if (cmp12 > 0)
+ { /* insert i2 */
+ if (merge_output(r, &i2, mapping) < 0) goto err;
+ if (i2.next(&i2) < 0) goto err;
+ }
+ else if (set || (TEST_VALUE(i1.value, i3.value) == 0))
+ { /* delete i2 */
+ if (i1.next(&i1) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+ else
+ { /* conflicting del in i2 and change in i3 */
+ merge_error(i1.position, i2.position, i3.position, 3);
+ goto err;
+ }
+ }
+ else
+ { /* Both keys changed */
+ TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
+ if (cmp23==0)
+ { /* dualing inserts or deletes */
+ merge_error(i1.position, i2.position, i3.position, 4);
+ goto err;
+ }
+ if (cmp12 > 0)
+ { /* insert i2 */
+ if (cmp23 > 0)
+ { /* insert i3 first */
+ if (merge_output(r, &i3, mapping) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+ else
+ { /* insert i2 first */
+ if (merge_output(r, &i2, mapping) < 0) goto err;
+ if (i2.next(&i2) < 0) goto err;
+ }
+ }
+ else if (cmp13 > 0)
+ { /* Insert i3 */
+ if (merge_output(r, &i3, mapping) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+ else
+ { /* Dueling deletes */
+ merge_error(i1.position, i2.position, i3.position, 5);
+ goto err;
+ }
+ }
+ }
+
+ while (i2.position >= 0 && i3.position >= 0)
+ { /* New inserts */
+ TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
+ if (cmp23==0)
+ { /* dualing inserts */
+ merge_error(i1.position, i2.position, i3.position, 6);
+ goto err;
+ }
+ if (cmp23 > 0)
+ { /* insert i3 */
+ if (merge_output(r, &i3, mapping) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+ else
+ { /* insert i2 */
+ if (merge_output(r, &i2, mapping) < 0) goto err;
+ if (i2.next(&i2) < 0) goto err;
+ }
+ }
+
+ while (i1.position >= 0 && i2.position >= 0)
+ { /* deleting i3 */
+ TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
+ if (cmp12 > 0)
+ { /* insert i2 */
+ if (merge_output(r, &i2, mapping) < 0) goto err;
+ if (i2.next(&i2) < 0) goto err;
+ }
+ else if (cmp12==0 && (set || (TEST_VALUE(i1.value, i2.value) == 0)))
+ { /* delete i3 */
+ if (i1.next(&i1) < 0) goto err;
+ if (i2.next(&i2) < 0) goto err;
+ }
+ else
+ { /* Dueling deletes or delete and change */
+ merge_error(i1.position, i2.position, i3.position, 7);
+ goto err;
+ }
+ }
+
+ while (i1.position >= 0 && i3.position >= 0)
+ { /* deleting i2 */
+ TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
+ if (cmp13 > 0)
+ { /* insert i3 */
+ if (merge_output(r, &i3, mapping) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+ else if (cmp13==0 && (set || (TEST_VALUE(i1.value, i3.value) == 0)))
+ { /* delete i2 */
+ if (i1.next(&i1) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+ else
+ { /* Dueling deletes or delete and change */
+ merge_error(i1.position, i2.position, i3.position, 8);
+ goto err;
+ }
+ }
+
+ if (i1.position >= 0)
+ { /* Dueling deletes */
+ merge_error(i1.position, i2.position, i3.position, 9);
+ goto err;
+ }
+
+ while (i2.position >= 0)
+ { /* Inserting i2 at end */
+ if (merge_output(r, &i2, mapping) < 0) goto err;
+ if (i2.next(&i2) < 0) goto err;
+ }
+
+ while (i3.position >= 0)
+ { /* Inserting i2 at end */
+ if (merge_output(r, &i3, mapping) < 0) goto err;
+ if (i3.next(&i3) < 0) goto err;
+ }
+
+ finiSetIteration(&i1);
+ finiSetIteration(&i2);
+ finiSetIteration(&i3);
+
+ if (s1->next)
+ {
+ Py_INCREF(s1->next);
+ r->next = s1->next;
+ }
+ s = bucket_getstate(r);
+ Py_DECREF(r);
+
+ return s;
+
+ err:
+ finiSetIteration(&i1);
+ finiSetIteration(&i2);
+ finiSetIteration(&i3);
+ Py_XDECREF(r);
+ return NULL;
+}
=== Zope3/lib/python/Persistence/BTrees/OIBTree.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+from _OIBTree import *
=== Zope3/lib/python/Persistence/BTrees/OOBTree.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+from _OOBTree import *
=== Zope3/lib/python/Persistence/BTrees/SetOpTemplate.c 1.1 => 1.2 === (443/543 lines abridged)
+
+ Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+/****************************************************************************
+ Set operations
+ ****************************************************************************/
+
+#define SETOPTEMPLATE_C "$Id$\n"
+
+#ifdef INTSET_H
+static int
+nextIntSet(SetIteration *i)
+{
+ if (i->position >= 0)
+ {
+ UNLESS(PER_USE(INTSET(i->set))) return -1;
+
+ if (i->position < INTSET(i->set)->len)
+ {
+ i->key = INTSET(i->set)->data[i->position];
+ i->position ++;
+ }
+ else
+ {
+ i->position = -1;
+ PyPersist_SetATime(INTSET(i->set));
+ }
+
+ PER_ALLOW_DEACTIVATION(INTSET(i->set));
+ }
+
+
+ return 0;
+}
+#endif
+
+#ifdef KEY_CHECK
+static int
+nextKeyAsSet(SetIteration *i)
+{
[-=- -=- -=- 443 lines omitted -=- -=- -=-]
+ PER_ACCESSED(set);
+ goto Error;
+ }
+ }
+ memcpy(result->keys + result->len,
+ BUCKET(set)->keys,
+ setsize * sizeof(KEY_TYPE));
+ result->len += setsize;
+ PER_ALLOW_DEACTIVATION(SIZED(set));
+ PER_ACCESSED(set);
+ }
+ else {
+ /* No cheap way: iterate over set's elements one at a time. */
+ int merge; /* dummy needed for initSetIteration */
+
+ if (initSetIteration(&setiter, set, -1, &merge) < 0) goto Error;
+ if (setiter.next(&setiter) < 0) goto Error;
+ while (setiter.position >= 0) {
+ if (result->len >= result->size && Bucket_grow(result, -1, 1) < 0)
+ goto Error;
+ COPY_KEY(result->keys[result->len], setiter.key);
+ ++result->len;
+ /* We know the key is an int, so no need to incref it. */
+ if (setiter.next(&setiter) < 0) goto Error;
+ }
+ finiSetIteration(&setiter);
+ }
+ Py_DECREF(set);
+ set = NULL;
+ }
+
+ /* Combine, sort, remove duplicates, and reset the result's len.
+ If the set shrinks (which happens if and only if there are
+ duplicates), no point to realloc'ing the set smaller, as we
+ expect the result set to be short-lived.
+ */
+ if (result->len > 0) {
+ size_t newlen; /* number of elements in final result set */
+ newlen = sort_int4_nodups(result->keys, (size_t)result->len);
+ result->len = (int)newlen;
+ }
+ return (PyObject *)result;
+
+Error:
+ Py_DECREF(result);
+ Py_XDECREF(set);
+ finiSetIteration(&setiter);
+ return NULL;
+}
+#endif
=== Zope3/lib/python/Persistence/BTrees/SetTemplate.c 1.1 => 1.2 ===
+
+ Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define SETTEMPLATE_C "$Id$\n"
+
+static PyObject *
+Set_insert(Bucket *self, PyObject *args)
+{
+ PyObject *key;
+ int i;
+
+ UNLESS (PyArg_ParseTuple(args, "O", &key)) return NULL;
+ if ( (i=_bucket_set(self, key, Py_None, 1, 1, 0)) < 0) return NULL;
+ return PyInt_FromLong(i);
+}
+
+/* _Set_update and _TreeSet_update are identical except for the
+ function they call to add the element to the set.
+*/
+
+static int
+_Set_update(Bucket *self, PyObject *seq)
+{
+ int n = -1;
+ PyObject *iter, *v;
+ int ind;
+
+ iter = PyObject_GetIter(seq);
+ if (iter == NULL)
+ return -1;
+
+ while (1) {
+ v = PyIter_Next(iter);
+ if (v == NULL) {
+ if (PyErr_Occurred())
+ goto err;
+ else
+ break;
+ }
+ ind = _bucket_set(self, v, Py_None, 1, 1, 0);
+ Py_DECREF(v);
+ if (ind < 0)
+ goto err;
+ else
+ n += ind;
+ }
+ /* n starts out at -1, which is the error return value. If
+ this point is reached, then there is no error. n must be
+ incremented to account for the initial value of -1 instead of
+ 0.
+ */
+ n++;
+
+ err:
+ Py_DECREF(iter);
+ return n;
+}
+
+static PyObject *
+Set_update(Bucket *self, PyObject *args)
+{
+ PyObject *seq = NULL;
+ int n = 0;
+
+ if (!PyArg_ParseTuple(args, "|O:update", &seq))
+ return NULL;
+
+ if (seq) {
+ n = _Set_update(self, seq);
+ if (n < 0)
+ return NULL;
+ }
+
+ return PyInt_FromLong(n);
+}
+
+static PyObject *
+Set_remove(Bucket *self, PyObject *args)
+{
+ PyObject *key;
+
+ UNLESS (PyArg_ParseTuple(args, "O", &key)) return NULL;
+ if (_bucket_set(self, key, NULL, 0, 1, 0) < 0) return NULL;
+
+ Py_INCREF(Py_None);
+ return Py_None;
+}
+
+static int
+_set_setstate(Bucket *self, PyObject *args)
+{
+ PyObject *k, *items;
+ Bucket *next=0;
+ int i, l, copied=1;
+ KEY_TYPE *keys;
+
+ UNLESS (PyArg_ParseTuple(args, "O|O", &items, &next))
+ return -1;
+
+ if ((l=PyTuple_Size(items)) < 0) return -1;
+
+ for (i=self->len; --i >= 0; )
+ {
+ DECREF_KEY(self->keys[i]);
+ }
+ self->len=0;
+
+ if (self->next)
+ {
+ Py_DECREF(self->next);
+ self->next=0;
+ }
+
+ if (l > self->size)
+ {
+ UNLESS (keys=BTree_Realloc(self->keys, sizeof(KEY_TYPE)*l)) return -1;
+ self->keys=keys;
+ self->size=l;
+ }
+
+ for (i=0; i<l; i++)
+ {
+ k=PyTuple_GET_ITEM(items, i);
+ COPY_KEY_FROM_ARG(self->keys[i], k, copied);
+ UNLESS (copied) return -1;
+ INCREF_KEY(self->keys[i]);
+ }
+
+ self->len=l;
+
+ if (next)
+ {
+ self->next=next;
+ Py_INCREF(next);
+ }
+
+ return 0;
+}
+
+static PyObject *
+set_setstate(Bucket *self, PyObject *args)
+{
+ int r;
+
+ UNLESS (PyArg_ParseTuple(args, "O", &args)) return NULL;
+
+ PER_PREVENT_DEACTIVATION(self);
+ r=_set_setstate(self, args);
+ PER_ALLOW_DEACTIVATION(self);
+ PyPersist_SetATime(self);
+
+ if (r < 0) return NULL;
+ Py_INCREF(Py_None);
+ return Py_None;
+}
+
+static struct PyMethodDef Set_methods[] = {
+ {"__getstate__", (PyCFunction) bucket_getstate, METH_VARARGS,
+ "__getstate__() -- Return the picklable state of the object"},
+ {"__setstate__", (PyCFunction) set_setstate, METH_VARARGS,
+ "__setstate__() -- Set the state of the object"},
+ {"keys", (PyCFunction) bucket_keys, METH_VARARGS,
+ "keys() -- Return the keys"},
+ {"has_key", (PyCFunction) bucket_has_key, METH_O,
+ "has_key(key) -- Test whether the bucket contains the given key"},
+ {"clear", (PyCFunction) bucket_clear, METH_VARARGS,
+ "clear() -- Remove all of the items from the bucket"},
+ {"maxKey", (PyCFunction) Bucket_maxKey, METH_VARARGS,
+ "maxKey([key]) -- Fine the maximum key\n\n"
+ "If an argument is given, find the maximum <= the argument"},
+ {"minKey", (PyCFunction) Bucket_minKey, METH_VARARGS,
+ "minKey([key]) -- Fine the minimum key\n\n"
+ "If an argument is given, find the minimum >= the argument"},
+#ifdef PERSISTENT
+ {"_p_resolveConflict", (PyCFunction) bucket__p_resolveConflict, METH_VARARGS,
+ "_p_resolveConflict() -- Reinitialize from a newly created copy"},
+ {"_p_deactivate", (PyCFunction) bucket__p_deactivate, METH_VARARGS,
+ "_p_deactivate() -- Reinitialize from a newly created copy"},
+#endif
+ {"insert", (PyCFunction)Set_insert, METH_VARARGS,
+ "insert(id,[ignored]) -- Add a key to the set"},
+ {"update", (PyCFunction)Set_update, METH_VARARGS,
+ "update(seq) -- Add the items from the given sequence to the set"},
+ {"remove", (PyCFunction)Set_remove, METH_VARARGS,
+ "remove(id) -- Remove an id from the set"},
+
+ {NULL, NULL} /* sentinel */
+};
+
+static int
+Set_init(PyObject *self, PyObject *args, PyObject *kwds)
+{
+ PyObject *v = NULL;
+
+ if (!PyArg_ParseTuple(args, "|O:" MOD_NAME_PREFIX "Set", &v))
+ return -1;
+
+ if (v)
+ return _Set_update((Bucket *)self, v);
+ else
+ return 0;
+}
+
+
+
+static PyObject *
+set_repr(Bucket *self)
+{
+ static PyObject *format;
+ PyObject *r, *t;
+
+ UNLESS (format) UNLESS (format=PyString_FromString(MOD_NAME_PREFIX "Set(%s)"))
+ return NULL;
+ UNLESS (t=PyTuple_New(1)) return NULL;
+ UNLESS (r=bucket_keys(self,NULL)) goto err;
+ PyTuple_SET_ITEM(t,0,r);
+ r=t;
+ ASSIGN(r,PyString_Format(format,r));
+ return r;
+err:
+ Py_DECREF(t);
+ return NULL;
+}
+
+static int
+set_length(Bucket *self)
+{
+ int r;
+
+ PER_USE_OR_RETURN(self, -1);
+ r = self->len;
+ PER_ALLOW_DEACTIVATION(self);
+ PyPersist_SetATime(self);
+
+ return r;
+}
+
+static PyObject *
+set_item(Bucket *self, int index)
+{
+ PyObject *r=0;
+
+ PER_USE_OR_RETURN(self, NULL);
+ if (index >= 0 && index < self->len)
+ {
+ COPY_KEY_TO_OBJECT(r, self->keys[index]);
+ }
+ else
+ IndexError(index);
+
+ PER_ALLOW_DEACTIVATION(self);
+ PyPersist_SetATime(self);
+
+ return r;
+}
+
+static PySequenceMethods set_as_sequence = {
+ (inquiry)set_length, /*sq_length*/
+ (binaryfunc)0, /*sq_concat*/
+ (intargfunc)0, /*sq_repeat*/
+ (intargfunc)set_item, /*sq_item*/
+ (intintargfunc)0, /*sq_slice*/
+ (intobjargproc)0, /*sq_ass_item*/
+ (intintobjargproc)0, /*sq_ass_slice*/
+};
+
+static PyTypeObject SetType = {
+ PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+ 0, /* ob_size */
+ MODULE_NAME MOD_NAME_PREFIX "Set", /* tp_name */
+ sizeof(Bucket), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)bucket_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ (reprfunc)set_repr, /* tp_repr */
+ 0, /* tp_as_number */
+ &set_as_sequence, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)bucket_traverse, /* tp_traverse */
+ (inquiry)bucket_tp_clear, /* tp_clear */
+ 0, /* tp_richcompare */
+ offsetof(Bucket, po_weaklist), /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ Set_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ Set_init, /* tp_init */
+ 0, /* tp_alloc */
+ PyType_GenericNew, /* tp_new */
+};
+
+static int
+nextSet(SetIteration *i)
+{
+
+ if (i->position >= 0)
+ {
+ UNLESS(PER_USE(BUCKET(i->set))) return -1;
+
+ if (i->position)
+ {
+ DECREF_KEY(i->key);
+ }
+
+ if (i->position < BUCKET(i->set)->len)
+ {
+ COPY_KEY(i->key, BUCKET(i->set)->keys[i->position]);
+ INCREF_KEY(i->key);
+ i->position ++;
+ }
+ else
+ {
+ i->position = -1;
+ PyPersist_SetATime(BUCKET(i->set));
+ }
+
+ PER_ALLOW_DEACTIVATION(BUCKET(i->set));
+ }
+
+
+ return 0;
+}
=== Zope3/lib/python/Persistence/BTrees/TreeSetTemplate.c 1.1 => 1.2 ===
+
+ Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+#define TREESETTEMPLATE_C "$Id$\n"
+
+static PyObject *
+TreeSet_insert(BTree *self, PyObject *args)
+{
+ PyObject *key;
+ int i;
+
+ UNLESS (PyArg_ParseTuple(args, "O", &key)) return NULL;
+ if ((i=_BTree_set(self, key, Py_None, 1, 1)) < 0) return NULL;
+ return PyInt_FromLong(i);
+}
+
+/* _Set_update and _TreeSet_update are identical except for the
+ function they call to add the element to the set.
+*/
+
+static int
+_TreeSet_update(BTree *self, PyObject *seq)
+{
+ int n = -1;
+ PyObject *iter, *v;
+ int ind;
+
+ iter = PyObject_GetIter(seq);
+ if (iter == NULL)
+ return -1;
+
+ while (1) {
+ v = PyIter_Next(iter);
+ if (v == NULL) {
+ if (PyErr_Occurred())
+ goto err;
+ else
+ break;
+ }
+ ind = _BTree_set(self, v, Py_None, 1, 1);
+ Py_DECREF(v);
+ if (ind < 0)
+ goto err;
+ else
+ n += ind;
+ }
+ /* n starts out at -1, which is the error return value. If
+ this point is reached, then there is no error. n must be
+ incremented to account for the initial value of -1 instead of
+ 0.
+ */
+ n++;
+
+ err:
+ Py_DECREF(iter);
+ return n;
+}
+
+static PyObject *
+TreeSet_update(BTree *self, PyObject *args)
+{
+ PyObject *seq = NULL;
+ int n = 0;
+
+ if (!PyArg_ParseTuple(args, "|O:update", &seq))
+ return NULL;
+
+ if (seq) {
+ n = _TreeSet_update(self, seq);
+ if (n < 0)
+ return NULL;
+ }
+
+ return PyInt_FromLong(n);
+}
+
+
+static PyObject *
+TreeSet_remove(BTree *self, PyObject *args)
+{
+ PyObject *key;
+
+ UNLESS (PyArg_ParseTuple(args, "O", &key)) return NULL;
+ if (_BTree_set(self, key, NULL, 0, 1) < 0) return NULL;
+ Py_INCREF(Py_None);
+ return Py_None;
+}
+
+static PyObject *
+TreeSet_setstate(BTree *self, PyObject *args)
+{
+ int r;
+
+ if (!PyArg_ParseTuple(args,"O",&args)) return NULL;
+
+ PER_PREVENT_DEACTIVATION(self);
+ r=_BTree_setstate(self, args, 1);
+ PER_ALLOW_DEACTIVATION(self);
+ PyPersist_SetATime(self);
+
+ if (r < 0) return NULL;
+ Py_INCREF(Py_None);
+ return Py_None;
+}
+
+static struct PyMethodDef TreeSet_methods[] = {
+ {"__getstate__", (PyCFunction) BTree_getstate, METH_NOARGS,
+ "__getstate__() -> state\n\n"
+ "Return the picklable state of the TreeSet."},
+ {"__setstate__", (PyCFunction) TreeSet_setstate, METH_VARARGS,
+ "__setstate__(state)\n\n"
+ "Set the state of the TreeSet."},
+ {"has_key", (PyCFunction) BTree_has_key, METH_O,
+ "has_key(key)\n\n"
+ "Return true if the TreeSet contains the given key."},
+ {"keys", (PyCFunction) BTree_keys, METH_VARARGS,
+ "keys([min, max]) -> list of keys\n\n"
+ "Returns the keys of the TreeSet. If min and max are supplied, only\n"
+ "keys greater than min and less than max are returned."},
+ {"maxKey", (PyCFunction) BTree_maxKey, METH_VARARGS,
+ "maxKey([max]) -> key\n\n"
+ "Return the largest key in the BTree. If max is specified, return\n"
+ "the largest key <= max."},
+ {"minKey", (PyCFunction) BTree_minKey, METH_VARARGS,
+ "minKey([mi]) -> key\n\n"
+ "Return the smallest key in the BTree. If min is specified, return\n"
+ "the smallest key >= min."},
+ {"clear", (PyCFunction) BTree_clear, METH_NOARGS,
+ "clear()\n\nRemove all of the items from the BTree."},
+ {"insert", (PyCFunction)TreeSet_insert, METH_VARARGS,
+ "insert(id,[ignored]) -- Add an id to the set"},
+ {"update", (PyCFunction)TreeSet_update, METH_VARARGS,
+ "update(collection)\n\n Add the items from the given collection."},
+ {"remove", (PyCFunction)TreeSet_remove, METH_VARARGS,
+ "remove(id) -- Remove a key from the set"},
+#ifdef PERSISTENT
+ {"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict, METH_VARARGS,
+ "_p_resolveConflict() -- Reinitialize from a newly created copy"},
+ {"_p_deactivate", (PyCFunction) BTree__p_deactivate, METH_NOARGS,
+ "_p_deactivate()\n\nReinitialize from a newly created copy."},
+#endif
+ {NULL, NULL} /* sentinel */
+};
+
+static PyMappingMethods TreeSet_as_mapping = {
+ (inquiry)BTree_length, /*mp_length*/
+};
+
+static int
+TreeSet_init(PyObject *self, PyObject *args, PyObject *kwds)
+{
+ PyObject *v = NULL;
+
+ if (!PyArg_ParseTuple(args, "|O:" MOD_NAME_PREFIX "TreeSet", &v))
+ return -1;
+
+ if (v)
+ return _TreeSet_update((BTree *)self, v);
+ else
+ return 0;
+}
+
+static PyTypeObject TreeSetType = {
+ PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+ 0, /* ob_size */
+ MODULE_NAME MOD_NAME_PREFIX "TreeSet",/* tp_name */
+ sizeof(BTree), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)BTree_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ &BTree_as_number_for_nonzero, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ &TreeSet_as_mapping, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)BTree_traverse, /* tp_traverse */
+ (inquiry)BTree_tp_clear, /* tp_clear */
+ 0, /* tp_richcompare */
+ offsetof(BTree, po_weaklist), /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ TreeSet_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ TreeSet_init, /* tp_init */
+ 0, /* tp_alloc */
+ PyType_GenericNew, /* tp_new */
+};
=== Zope3/lib/python/Persistence/BTrees/_IIBTree.c 1.1 => 1.2 ===
+
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "II"
+#define INITMODULE init_IIBTree
+#define DEFAULT_MAX_BUCKET_SIZE 120
+#define DEFAULT_MAX_BTREE_SIZE 500
+#define MULTI_INT_UNION 1
+
+#include "intkeymacros.h"
+#include "intvaluemacros.h"
+#ifndef EXCLUDE_INTSET_SUPPORT
+#include "BTree/intSet.h"
+#endif
+#include "BTreeModuleTemplate.c"
=== Zope3/lib/python/Persistence/BTrees/_IOBTree.c 1.1 => 1.2 ===
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "IO"
+#define DEFAULT_MAX_BUCKET_SIZE 60
+#define DEFAULT_MAX_BTREE_SIZE 500
+#define INITMODULE init_IOBTree
+
+#include "intkeymacros.h"
+#include "objectvaluemacros.h"
+#ifndef EXCLUDE_INTSET_SUPPORT
+#include "BTree/intSet.h"
+#endif
+#include "BTreeModuleTemplate.c"
=== Zope3/lib/python/Persistence/BTrees/_OIBTree.c 1.1 => 1.2 ===
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "OI"
+#define INITMODULE init_OIBTree
+#define DEFAULT_MAX_BUCKET_SIZE 60
+#define DEFAULT_MAX_BTREE_SIZE 250
+
+#include "objectkeymacros.h"
+#include "intvaluemacros.h"
+#include "BTreeModuleTemplate.c"
=== Zope3/lib/python/Persistence/BTrees/_OOBTree.c 1.1 => 1.2 ===
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "OO"
+#define INITMODULE init_OOBTree
+#define DEFAULT_MAX_BUCKET_SIZE 30
+#define DEFAULT_MAX_BTREE_SIZE 250
+
+#include "objectkeymacros.h"
+#include "objectvaluemacros.h"
+#include "BTreeModuleTemplate.c"
=== Zope3/lib/python/Persistence/BTrees/__init__.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+##import ZODB
+
+##try: import intSet
+##except: pass
+##else: del intSet
+
+### Register interfaces
+##try: import Interface
+##except ImportError: pass # Don't register interfaces if no scarecrow
+##else:
+## import Interfaces
+## del Interfaces
+## del Interface
=== Zope3/lib/python/Persistence/BTrees/_fsBTree.c 1.1 => 1.2 ===
+
+ This BTree implments a mapping from 2-character strings
+ to six-character strings. This allows us to effieciently store
+ a FileStorage index as a nested mapping of 6-character oid prefix
+ to mapping of 2-character oid suffix to 6-character (byte) file
+ positions.
+*/
+
+#include <string.h>
+
+typedef unsigned char char2[2];
+typedef unsigned char char6[6];
+
+
+/* Setup template macros */
+
+#define MASTER_ID "$Id$\n"
+
+#define PERSISTENT
+
+#define MOD_NAME_PREFIX "fs"
+#define INITMODULE init_fsBTree
+#define DEFAULT_MAX_BUCKET_SIZE 500
+#define DEFAULT_MAX_BTREE_SIZE 500
+
+/*#include "intkeymacros.h"*/
+
+#define KEYMACROS_H "$Id$\n"
+#define KEY_TYPE char2
+#undef KEY_TYPE_IS_PYOBJECT
+#define KEY_CHECK(K) (PyString_Check(K) && PyString_GET_SIZE(K)==2)
+#define TEST_KEY_SET_OR(V, K, T) if ( ( (V) = ((*(K) < *(T) || (*(K) == *(T) && (K)[1] < (T)[1])) ? -1 : ((*(K) == *(T) && (K)[1] == (T)[1]) ? 0 : 1)) ), 0 )
+#define DECREF_KEY(KEY)
+#define INCREF_KEY(k)
+#define COPY_KEY(KEY, E) (*(KEY)=*(E), (KEY)[1]=(E)[1])
+#define COPY_KEY_TO_OBJECT(O, K) O=PyString_FromStringAndSize(K,2)
+#define COPY_KEY_FROM_ARG(TARGET, ARG, STATUS) \
+ if (KEY_CHECK(ARG)) memcpy(TARGET, PyString_AS_STRING(ARG), 2); else { \
+ PyErr_SetString(PyExc_TypeError, "expected two-character string key"); \
+ (STATUS)=0; }
+
+/*#include "intvaluemacros.h"*/
+#define VALUEMACROS_H "$Id$\n"
+#define VALUE_TYPE char6
+#undef VALUE_TYPE_IS_PYOBJECT
+#define TEST_VALUE(K, T) strncmp(K,T,6)
+#define DECREF_VALUE(k)
+#define INCREF_VALUE(k)
+#define COPY_VALUE(V, E) (memcpy(V, E, 6))
+#define COPY_VALUE_TO_OBJECT(O, K) O=PyString_FromStringAndSize(K,6)
+#define COPY_VALUE_FROM_ARG(TARGET, ARG, STATUS) \
+ if ((PyString_Check(ARG) && PyString_GET_SIZE(ARG)==6)) \
+ memcpy(TARGET, PyString_AS_STRING(ARG), 6); else { \
+ PyErr_SetString(PyExc_TypeError, "expected six-character string key"); \
+ (STATUS)=0; }
+
+#define NORMALIZE_VALUE(V, MIN)
+#include "BTreeModuleTemplate.c"
=== Zope3/lib/python/Persistence/BTrees/convert.py 1.1 => 1.2 ===
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+def convert(old, new, threshold=200, f=None):
+ "Utility for converting old btree to new"
+ n=0
+ for k, v in old.items():
+ if f is not None: v=f(v)
+ new[k]=v
+ n=n+1
+ if n > threshold:
+ get_transaction().commit(1)
+ old._p_jar.cacheMinimize(3)
+ n=0
+
+ get_transaction().commit(1)
+ old._p_jar.cacheMinimize(3)
=== Zope3/lib/python/Persistence/BTrees/intkeymacros.h 1.1 => 1.2 ===
+#define KEYMACROS_H "$Id$\n"
+
+#define KEY_TYPE int
+#undef KEY_TYPE_IS_PYOBJECT
+#define KEY_CHECK PyInt_Check
+#define TEST_KEY_SET_OR(V, K, T) if ( ( (V) = (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0)) ) , 0 )
+#define DECREF_KEY(KEY)
+#define INCREF_KEY(k)
+#define COPY_KEY(KEY, E) (KEY=(E))
+#define COPY_KEY_TO_OBJECT(O, K) O=PyInt_FromLong(K)
+#define COPY_KEY_FROM_ARG(TARGET, ARG, STATUS) \
+ if (PyInt_Check(ARG)) \
+ TARGET = PyInt_AS_LONG(ARG); \
+ else { \
+ PyErr_Format(PyExc_TypeError, "expected integer key, found %s", \
+ (ARG)->ob_type->tp_name); \
+ (STATUS) = 0; \
+ (TARGET) = 0; \
+ }
=== Zope3/lib/python/Persistence/BTrees/intvaluemacros.h 1.1 => 1.2 ===
+#define VALUEMACROS_H "$Id$\n"
+
+#define VALUE_TYPE int
+#undef VALUE_TYPE_IS_PYOBJECT
+
+#define TEST_VALUE(K, T) (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0))
+#define VALUE_SAME(VALUE, TARGET) ( (VALUE) == (TARGET) )
+#define VALUE_PARSE "i"
+#define DECREF_VALUE(k)
+#define INCREF_VALUE(k)
+#define COPY_VALUE(V, E) (V=(E))
+#define COPY_VALUE_TO_OBJECT(O, K) O=PyInt_FromLong(K)
+#define COPY_VALUE_FROM_ARG(TARGET, ARG, STATUS) \
+ if (PyInt_Check(ARG)) TARGET=PyInt_AsLong(ARG); else { \
+ PyErr_SetString(PyExc_TypeError, "expected integer value"); \
+ (STATUS)=0; (TARGET)=0; }
+
+#define NORMALIZE_VALUE(V, MIN) ((MIN) > 0) ? ((V)/=(MIN)) : 0
+
+#define MERGE_DEFAULT 1
+#define MERGE(O1, w1, O2, w2) ((O1)*(w1)+(O2)*(w2))
+#define MERGE_WEIGHT(O, w) ((O)*(w))
=== Zope3/lib/python/Persistence/BTrees/objectkeymacros.h 1.1 => 1.2 ===
+#define KEY_TYPE PyObject *
+#define KEY_TYPE_IS_PYOBJECT
+#define TEST_KEY_SET_OR(V, KEY, TARGET) if ( ( (V) = PyObject_Compare((KEY),(TARGET)) ), PyErr_Occurred() )
+#define INCREF_KEY(k) Py_INCREF(k)
+#define DECREF_KEY(KEY) Py_DECREF(KEY)
+#define COPY_KEY(KEY, E) KEY=(E)
+#define COPY_KEY_TO_OBJECT(O, K) O=(K); Py_INCREF(O)
+#define COPY_KEY_FROM_ARG(TARGET, ARG, S) TARGET=(ARG)
=== Zope3/lib/python/Persistence/BTrees/objectvaluemacros.h 1.1 => 1.2 ===
+#define VALUEMACROS_H "$Id$\n"
+
+#define VALUE_TYPE PyObject *
+#define VALUE_TYPE_IS_PYOBJECT
+#define TEST_VALUE(VALUE, TARGET) PyObject_Compare((VALUE),(TARGET))
+#define INCREF_VALUE(k) Py_INCREF(k)
+#define DECREF_VALUE(k) Py_DECREF(k)
+#define COPY_VALUE(k,e) k=(e)
+#define COPY_VALUE_TO_OBJECT(O, K) O=(K); Py_INCREF(O)
+#define COPY_VALUE_FROM_ARG(TARGET, ARG, S) TARGET=(ARG)
+#define NORMALIZE_VALUE(V, MIN) Py_INCREF(V)
=== Zope3/lib/python/Persistence/BTrees/sorters.c 1.1 => 1.2 === (427/527 lines abridged)
+
+ Copyright (c) 2002 Zope Corporation and Contributors.
+ All Rights Reserved.
+
+ This software is subject to the provisions of the Zope Public License,
+ Version 2.0 (ZPL). A copy of the ZPL should accompany this distribution.
+ THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+ WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+ FOR A PARTICULAR PURPOSE
+
+ ****************************************************************************/
+
+/* Revision information: $Id$ */
+
+/* The only routine here intended to be used outside the file is
+ size_t sort_int4_nodups(int *p, size_t n)
+
+ Sort the array of n ints pointed at by p, in place, and also remove
+ duplicates. Return the number of unique elements remaining, which occupy
+ a contiguous and monotonically increasing slice of the array starting at p.
+
+ Example: If the input array is [3, 1, 2, 3, 1, 5, 2], sort_int4_nodups
+ returns 4, and the first 4 elements of the array are changed to
+ [1, 2, 3, 5]. The content of the remaining array positions is not defined.
+
+ Notes:
+
+ + This is specific to 4-byte signed ints, with endianness natural to the
+ platform.
+
+ + 4*n bytes of available heap memory are required for best speed.
+*/
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <malloc.h>
+#include <memory.h>
+#include <string.h>
+#include <assert.h>
+
+/* The type of array elements to be sorted. Most of the routines don't
+ care about the type, and will work fine for any scalar C type (provided
+ they're recompiled with element_type appropriately redefined). However,
+ the radix sort has to know everything about the type's internal
+ representation.
+*/
+typedef int element_type;
+
+/* The radixsort is faster than the quicksort for large arrays, but radixsort
[-=- -=- -=- 427 lines omitted -=- -=- -=-]
+ plo[1] = *pj;
+ *pj = pivot;
+
+ /* Subfiles are from plo to pj-1 inclusive, and pj+1 to phi
+ inclusive. Push the larger one, and loop back to do the
+ smaller one directly.
+ */
+ if (pj - plo >= phi - pj) {
+ PUSH(plo, pj-1);
+ plo = pj+1;
+ }
+ else {
+ PUSH(pj+1, phi);
+ phi = pj-1;
+ }
+ }
+
+#undef PUSH
+#undef SWAP
+}
+
+/* Sort p and remove duplicates, as fast as we can. */
+static size_t
+sort_int4_nodups(int *p, size_t n)
+{
+ size_t nunique;
+ element_type *work;
+
+ assert(sizeof(int) == sizeof(element_type));
+ assert(p);
+
+ /* Use quicksort if the array is small, OR if malloc can't find
+ enough temp memory for radixsort.
+ */
+ work = NULL;
+ if (n > QUICKSORT_BEATS_RADIXSORT)
+ work = (element_type *)malloc(n * sizeof(element_type));
+
+ if (work) {
+ element_type *out = radixsort_int4(p, work, n);
+ nunique = uniq(p, out, n);
+ free(work);
+ }
+ else {
+ quicksort(p, n);
+ nunique = uniq(p, p, n);
+ }
+
+ return nunique;
+}