[Zope3-checkins] CVS: Zope3/src/zodb/btrees - BTreeItemsTemplate.c:1.2 BTreeModuleTemplate.c:1.2 BTreeTemplate.c:1.2 BucketTemplate.c:1.2 IIBTree.py:1.2 IOBTree.py:1.2 Length.py: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 fsBTree.py:1.2 interfaces.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
Wed, 25 Dec 2002 09:13:51 -0500
Update of /cvs-repository/Zope3/src/zodb/btrees
In directory cvs.zope.org:/tmp/cvs-serv15352/src/zodb/btrees
Added Files:
BTreeItemsTemplate.c BTreeModuleTemplate.c BTreeTemplate.c
BucketTemplate.c IIBTree.py IOBTree.py Length.py
MergeTemplate.c OIBTree.py OOBTree.py SetOpTemplate.c
SetTemplate.c TreeSetTemplate.c _IIBTree.c _IOBTree.c
_OIBTree.c _OOBTree.c __init__.py _fsBTree.c fsBTree.py
interfaces.py intkeymacros.h intvaluemacros.h
objectkeymacros.h objectvaluemacros.h sorters.c
Log Message:
Grand renaming:
- Renamed most files (especially python modules) to lower case.
- Moved views and interfaces into separate hierarchies within each
project, where each top-level directory under the zope package
is a separate project.
- Moved everything to src from lib/python.
lib/python will eventually go away. I need access to the cvs
repository to make this happen, however.
There are probably some bits that are broken. All tests pass
and zope runs, but I haven't tried everything. There are a number
of cleanups I'll work on tomorrow.
=== Zope3/src/zodb/btrees/BTreeItemsTemplate.c 1.1 => 1.2 === (607/707 lines abridged)
--- /dev/null Wed Dec 25 09:13:47 2002
+++ Zope3/src/zodb/btrees/BTreeItemsTemplate.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,704 @@
+/*****************************************************************************
+
+ 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 must 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 firstbucket == lastbucket == currentbucket == NULL.
+ *
+ * 'kind' determines whether this slice represents 'k'eys alone, 'v'alues
+ * alone, or 'i'items (key+value pairs). 'kind' is also readonly after
+ * initialization.
+ *
+ * The combination of currentbucket, currentoffset and pseudoindex acts as
+ * a search finger. Offset currentoffset in bucket currentbucket is at index
+ * pseudoindex, where pseudoindex==0 corresponds to offset first in bucket
+ * firstbucket, and pseudoindex==-1 corresponds to offset last in bucket
+ * lastbucket. The function BTreeItems_seek() can be used to set this combo
+ * correctly for any in-bounds index, and uses this combo on input to avoid
+ * needing to search from the start (or end) on each call. Calling
+ * BTreeItems_seek() with consecutive larger positions is very efficent.
+ * Calling it with consecutive smaller positions is more efficient than if
+ * a search finger weren't being used at all, but is still quadratic time
+ * in the number of buckets in the slice.
+ */
+typedef struct {
+ PyObject_HEAD
+ Bucket *firstbucket; /* First bucket */
+ Bucket *currentbucket; /* Current bucket (search finger) */
[-=- -=- -=- 607 lines omitted -=- -=- -=-]
+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 */
+};
=== Zope3/src/zodb/btrees/BTreeModuleTemplate.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/BTreeModuleTemplate.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,494 @@
+/*****************************************************************************
+
+ 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 "persistence/persistence.h"
+#include "persistence/persistenceAPI.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
+
+/* So sue me. This pair gets used all over the place, so much so that it
+ * interferes with understanding non-persistence parts of algorithms.
+ * PER_UNUSE can be used after a successul PER_USE or PER_USE_OR_RETURN.
+ * It allows the object to become ghostified, and tells the persistence
+ * machinery that the object's fields were used recently.
+ */
+#define PER_UNUSE(OBJ) do { \
+ PER_ALLOW_DEACTIVATION(OBJ); \
+ PER_ACCESSED(OBJ); \
+} while (0)
+
+/*
+ The tp_name slots of the various BTree types contain the fully
+ qualified names of the types, e.g. zodb.btrees.OOBTree.OOBTree.
+ The full name is usd to support pickling and because it is not
+ possible to modify the __module__ slot of a type dynamically. (This
+ may be a bug in Python 2.2).
+*/
+
+#define MODULE_NAME "zodb.btrees." MOD_NAME_PREFIX "BTree."
+
+static PyObject *sort_str, *reverse_str, *__setstate___str,
+ *_bucket_type_str;
+static PyObject *ConflictError = NULL;
+
+static void PyVar_Assign(PyObject **v, PyObject *e) { Py_XDECREF(*v); *v=e;}
+#define ASSIGN(V,E) PyVar_Assign(&(V),(E))
+#define ASSIGNC(V,E) (Py_INCREF((E)), PyVar_Assign(&(V),(E)))
+#define UNLESS(E) if (!(E))
+#define UNLESS_ASSIGN(V,E) ASSIGN(V,E); UNLESS(V)
+#define LIST(O) ((PyListObject*)(O))
+#define OBJECT(O) ((PyObject*)(O))
+
+#define MIN_BUCKET_ALLOC 16
+#define MAX_BTREE_SIZE(B) DEFAULT_MAX_BTREE_SIZE
+#define MAX_BUCKET_SIZE(B) DEFAULT_MAX_BUCKET_SIZE
+
+#define SameType_Check(O1, O2) ((O1)->ob_type==(O2)->ob_type)
+
+#define ASSERT(C, S, R) if (! (C)) { \
+ PyErr_SetString(PyExc_AssertionError, (S)); return (R); }
+
+/* Various kinds of BTree and Bucket structs are instances of
+ * "sized containers", and have a common initial layout:
+ * The stuff needed for all Python objects, or all Persistent objects.
+ * int size: The maximum number of things that could be contained
+ * without growing the container.
+ * int len: The number of things currently contained.
+ *
+ * Invariant: 0 <= len <= size.
+ *
+ * A sized container typically goes on to declare one or more pointers
+ * to contiguous arrays with 'size' elements each, the initial 'len' of
+ * which are currently in use.
+ */
+#ifdef PERSISTENT
+#define sizedcontainer_HEAD \
+ PyPersist_HEAD \
+ PyObject *po_weaklist; \
+ int size; \
+ int len;
+#else
+#define sizedcontainer_HEAD \
+ PyObject_HEAD \
+ int size; \
+ int len;
+#endif
+
+/* Nothing is actually of type Sized, but (pointers to) BTree nodes and
+ * Buckets can be cast to Sized* in contexts that only need to examine
+ * the members common to all sized containers.
+ */
+typedef struct Sized_s {
+ sizedcontainer_HEAD
+} Sized;
+
+#define SIZED(O) ((Sized*)(O))
+
+/* A Bucket wraps contiguous vectors of keys and values. Keys are unique,
+ * and stored in sorted order. The 'values' pointer may be NULL if the
+ * Bucket is used to implement a set. Buckets serving as leafs of BTrees
+ * are chained together via 'next', so that the entire BTree contents
+ * can be traversed in sorted order quickly and easily.
+ */
+typedef struct Bucket_s {
+ sizedcontainer_HEAD
+ struct Bucket_s *next; /* the bucket with the next-larger keys */
+ KEY_TYPE *keys; /* 'len' keys, in increasing order */
+ VALUE_TYPE *values; /* 'len' corresponding values; NULL if a set */
+} Bucket;
+
+#define BUCKET(O) ((Bucket*)(O))
+
+/* A BTree is complicated. See Maintainer.txt.
+ */
+
+typedef struct BTreeItem_s {
+ KEY_TYPE key;
+ Sized *child; /* points to another BTree, or to a Bucket of some sort */
+} BTreeItem;
+
+typedef struct BTree_s {
+ sizedcontainer_HEAD
+
+ /* firstbucket points to the bucket containing the smallest key in
+ * the BTree. This is found by traversing leftmost child pointers
+ * (data[0].child) until reaching a Bucket.
+ */
+ Bucket *firstbucket;
+
+ /* The BTree points to 'len' children, via the "child" fields of the data
+ * array. There are len-1 keys in the 'key' fields, stored in increasing
+ * order. data[0].key is unused. For i in 0 .. len-1, all keys reachable
+ * from data[i].child are >= data[i].key and < data[i+1].key, at the
+ * endpoints pretending that data[0].key is minus infinity and
+ * data[len].key is positive infinity.
+ */
+ BTreeItem *data;
+} BTree;
+
+static PyTypeObject BTreeType;
+static PyTypeObject BucketType;
+
+#define BTREE(O) ((BTree*)(O))
+
+/* Use BTREE_SEARCH to find which child pointer to follow.
+ * RESULT An int lvalue to hold the index i such that SELF->data[i].child
+ * is the correct node to search next.
+ * SELF A pointer to a BTree 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.
+ */
+#define BTREE_SEARCH(RESULT, SELF, KEY, ONERROR) { \
+ int _lo = 0; \
+ int _hi = (SELF)->len; \
+ int _i, _cmp; \
+ for (_i = _hi >> 1; _i > _lo; _i = (_lo + _hi) >> 1) { \
+ TEST_KEY_SET_OR(_cmp, (SELF)->data[_i].key, (KEY)) \
+ ONERROR; \
+ if (_cmp < 0) _lo = _i; \
+ else if (_cmp > 0) _hi = _i; \
+ else /* equal */ break; \
+ } \
+ (RESULT) = _i; \
+}
+
+/* SetIteration structs are used in the internal set iteration protocol.
+ * When you want to iterate over a set or bucket or BTree (even an
+ * individual key!),
+ * 1. Declare a new iterator:
+ * SetIteration si = {0,0,0};
+ * Using "{0,0,0}" or "{0,0}" appear most common. Only one {0} is
+ * necssary. At least one must be given so that finiSetIteration() works
+ * correctly even if you don't get around to calling initSetIteration().
+ * 2. Initialize it via
+ * initSetIteration(&si, PyObject *s, useValues)
+ * It's an error if that returns an int < 0. In case of error on the
+ * init call, calling finiSetIteration(&si) is optional. But if the
+ * init call succeeds, you must eventually call finiSetIteration(),
+ * and whether or not subsequent calls to si.next() fail.
+ * 3. Get the first element:
+ * if (si.next(&si) < 0) { there was an error }
+ * If the set isn't empty, this sets si.position to an int >= 0,
+ * si.key to the element's key (of type KEY_TYPE), and maybe si.value to
+ * the element's value (of type VALUE_TYPE). si.value is defined
+ * iff si.usesValue is true.
+ * 4. Process all the elements:
+ * while (si.position >= 0) {
+ * do something with si.key and/or si.value;
+ * if (si.next(&si) < 0) { there was an error; }
+ * }
+ * 5. Finalize the SetIterator:
+ * finiSetIteration(&si);
+ * This is mandatory! si may contain references to iterator objects,
+ * keys and values, and they must be cleaned up else they'll leak. If
+ * this were C++ we'd hide that in the destructor, but in C you have to
+ * do it by hand.
+ */
+typedef struct SetIteration_s
+{
+ PyObject *set; /* the set, bucket, BTree, ..., being iterated */
+ int position; /* initialized to 0; set to -1 by next() when done */
+ int usesValue; /* true iff 'set' has values & we iterate them */
+ KEY_TYPE key; /* next() sets to next key */
+ VALUE_TYPE value; /* next() may set to next value */
+ int (*next)(struct SetIteration_s*); /* function to get next key+value */
+} SetIteration;
+
+/* Finish the set iteration protocol. This MUST be called by everyone
+ * who starts a set iteration, unless the initial call to initSetIteration
+ * failed; in that case, and only that case, calling finiSetIteration is
+ * optional.
+ */
+static void
+finiSetIteration(SetIteration *i)
+{
+ assert(i != NULL);
+ if (i->set == NULL)
+ return;
+ Py_DECREF(i->set);
+ i->set = NULL; /* so it doesn't hurt to call this again */
+
+ if (i->position > 0) {
+ /* next() was called at least once, but didn't finish iterating
+ * (else position would be negative). So the cached key and
+ * value need to be cleaned up.
+ */
+ DECREF_KEY(i->key);
+ if (i->usesValue) {
+ DECREF_VALUE(i->value);
+ }
+ }
+ i->position = -1; /* stop any stray next calls from doing harm */
+}
+
+static PyObject *
+IndexError(int i)
+{
+ PyObject *v;
+
+ 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
+ * starting at first. current, *current and first must not be NULL.
+ *
+ * Return:
+ * 1 *current holds the correct bucket; this is a borrowed reference
+ * 0 no such bucket exists; *current unaltered
+ * -1 error; *current unaltered
+ */
+static int
+PreviousBucket(Bucket **current, Bucket *first)
+{
+ Bucket *trailing = NULL; /* first travels; trailing follows it */
+ int result = 0;
+
+ assert(current && *current && first);
+ if (first == *current)
+ return 0;
+
+ do {
+ trailing = first;
+ PER_USE_OR_RETURN(first, -1);
+ first = first->next;
+ PER_ALLOW_DEACTIVATION(trailing);
+ PER_ACCESSED(trailing);
+
+ if (first == *current) {
+ *current = trailing;
+ result = 1;
+ break;
+ }
+ } while (first);
+
+ return result;
+}
+
+static void *
+BTree_Malloc(size_t sz)
+{
+ void *r;
+
+ ASSERT(sz > 0, "non-positive size malloc", NULL);
+
+ r = malloc(sz);
+ if (r)
+ return r;
+
+ PyErr_NoMemory();
+ return NULL;
+}
+
+static void *
+BTree_Realloc(void *p, size_t sz)
+{
+ void *r;
+
+ ASSERT(sz > 0, "non-positive size realloc", NULL);
+
+ if (p)
+ r = realloc(p, sz);
+ else
+ r = malloc(sz);
+
+ UNLESS (r)
+ PyErr_NoMemory();
+
+ return r;
+}
+
+#include "BTreeItemsTemplate.c"
+#include "BucketTemplate.c"
+#include "SetTemplate.c"
+#include "BTreeTemplate.c"
+#include "TreeSetTemplate.c"
+#include "SetOpTemplate.c"
+#include "MergeTemplate.c"
+
+static struct PyMethodDef module_methods[] = {
+ {"difference", (PyCFunction) difference_m, METH_VARARGS,
+ "difference(o1, o2) -- "
+ "compute the difference between o1 and o2"
+ },
+ {"union", (PyCFunction) union_m, METH_VARARGS,
+ "union(o1, o2) -- compute the union of o1 and o2\n"
+ },
+ {"intersection", (PyCFunction) intersection_m, METH_VARARGS,
+ "intersection(o1, o2) -- "
+ "compute the intersection of o1 and o2"
+ },
+#ifdef MERGE
+ {"weightedUnion", (PyCFunction) wunion_m, METH_VARARGS,
+ "weightedUnion(o1, o2 [, w1, w2]) -- compute the union of o1 and o2\n"
+ "\nw1 and w2 are weights."
+ },
+ {"weightedIntersection", (PyCFunction) wintersection_m, METH_VARARGS,
+ "weightedIntersection(o1, o2 [, w1, w2]) -- "
+ "compute the intersection of o1 and o2\n"
+ "\nw1 and w2 are weights."
+ },
+#endif
+#ifdef MULTI_INT_UNION
+ {"multiunion", (PyCFunction) multiunion_m, METH_VARARGS,
+ "multiunion(seq) -- compute union of a sequence of integer sets.\n"
+ "\n"
+ "Each element of seq must be an integer set, or convertible to one\n"
+ "via the set iteration protocol. The union returned is an IISet."
+ },
+#endif
+ {NULL, NULL} /* sentinel */
+};
+
+static char BTree_module_documentation[] =
+"\n"
+MASTER_ID
+BTREEITEMSTEMPLATE_C
+"$Id$\n"
+BTREETEMPLATE_C
+BUCKETTEMPLATE_C
+KEYMACROS_H
+MERGETEMPLATE_C
+SETOPTEMPLATE_C
+SETTEMPLATE_C
+TREESETTEMPLATE_C
+VALUEMACROS_H
+BTREEITEMSTEMPLATE_C
+;
+
+int
+init_persist_type(PyTypeObject *type)
+{
+ type->ob_type = &PyType_Type;
+ type->tp_base = PyPersist_TYPE;
+
+ if (PyType_Ready(type) < 0)
+ return 0;
+
+ return 1;
+}
+
+void
+INITMODULE (void)
+{
+ PyObject *m, *d, *c;
+
+ sort_str = PyString_InternFromString("sort");
+ if (!sort_str)
+ return;
+ reverse_str = PyString_InternFromString("reverse");
+ if (!reverse_str)
+ return;
+ __setstate___str = PyString_InternFromString("__setstate__");
+ if (!__setstate___str)
+ return;
+ _bucket_type_str = PyString_InternFromString("_bucket_type");
+ if (!_bucket_type_str)
+ return;
+
+ /* Grab the ConflictError class */
+ m = PyImport_ImportModule("zodb.btrees.interfaces");
+ if (m != NULL) {
+ c = PyObject_GetAttrString(m, "BTreesConflictError");
+ if (c != NULL)
+ ConflictError = c;
+ 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._persistence", "C_API");
+ if (PyPersist_C_API == 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);
+ 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/src/zodb/btrees/BTreeTemplate.c 1.1 => 1.2 === (1888/1988 lines abridged)
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/BTreeTemplate.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,1985 @@
+/*****************************************************************************
+
+ 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"
+
+/* Sanity-check a BTree. This is a private helper for BTree_check. Return:
+ * -1 Error. If it's an internal inconsistency in the BTree,
+ * AssertionError is set.
+ * 0 No problem found.
+ *
+ * nextbucket is the bucket "one beyond the end" of the BTree; the last bucket
+ * directly reachable from following right child pointers *should* be linked
+ * to nextbucket (and this is checked).
+ */
+static int
+BTree_check_inner(BTree *self, Bucket *nextbucket)
+{
+ int i;
+ Bucket *bucketafter;
+ Sized *child;
+ char *errormsg = "internal error"; /* someone should have overriden */
+ Sized *activated_child = NULL;
+ int result = -1; /* until proved innocent */
+
+#define CHECK(CONDITION, ERRORMSG) \
+ if (!(CONDITION)) { \
+ errormsg = (ERRORMSG); \
+ goto Error; \
+ }
+
+ PER_USE_OR_RETURN(self, -1);
+ CHECK(self->len >= 0, "BTree len < 0");
+ CHECK(self->len <= self->size, "BTree len > size");
+ if (self->len == 0) {
+ /* Empty BTree. */
+ CHECK(self->firstbucket == NULL,
[-=- -=- -=- 1888 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 */
+ &BTree_as_sequence, /* tp_as_sequence */
+ &BTree_as_mapping, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)BTree_traverse, /* tp_traverse */
+ (inquiry)BTree_tp_clear, /* tp_clear */
+ 0, /* tp_richcompare */
+ offsetof(BTree, po_weaklist), /* tp_weaklistoffset */
+ (getiterfunc)BTree_getiter, /* tp_iter */
+ 0, /* tp_iternext */
+ BTree_methods, /* tp_methods */
+ BTree_members, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ BTree_init, /* tp_init */
+ 0, /* tp_alloc */
+ 0, /*PyType_GenericNew,*/ /* tp_new */
+};
=== Zope3/src/zodb/btrees/BucketTemplate.c 1.1 => 1.2 === (1565/1665 lines abridged)
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/BucketTemplate.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,1662 @@
+/*****************************************************************************
+
+ 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; \
[-=- -=- -=- 1565 lines omitted -=- -=- -=-]
+ 0, /* tp_richcompare */
+ offsetof(Bucket, po_weaklist), /* tp_weaklistoffset */
+ (getiterfunc)Bucket_getiter, /* tp_iter */
+ 0, /* tp_iternext */
+ Bucket_methods, /* tp_methods */
+ Bucket_members, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ Bucket_init, /* tp_init */
+ 0, /* tp_alloc */
+ 0, /*PyType_GenericNew,*/ /* tp_new */
+};
+
+static int
+nextBucket(SetIteration *i)
+{
+ 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/src/zodb/btrees/IIBTree.py 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/IIBTree.py Wed Dec 25 09:12:16 2002
@@ -0,0 +1,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.
+#
+##############################################################################
+from zodb.btrees._IIBTree import *
=== Zope3/src/zodb/btrees/IOBTree.py 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/IOBTree.py Wed Dec 25 09:12:16 2002
@@ -0,0 +1,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.
+#
+##############################################################################
+from zodb.btrees._IOBTree import *
=== Zope3/src/zodb/btrees/Length.py 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/Length.py Wed Dec 25 09:12:16 2002
@@ -0,0 +1,42 @@
+##############################################################################
+#
+# 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/src/zodb/btrees/MergeTemplate.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/MergeTemplate.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,278 @@
+/*****************************************************************************
+
+ 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, 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;
+
+ mapping = i1.usesValue | i2.usesValue | i3.usesValue;
+ 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/src/zodb/btrees/OIBTree.py 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/OIBTree.py Wed Dec 25 09:12:16 2002
@@ -0,0 +1,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.
+#
+##############################################################################
+from zodb.btrees._OIBTree import *
=== Zope3/src/zodb/btrees/OOBTree.py 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/OOBTree.py Wed Dec 25 09:12:16 2002
@@ -0,0 +1,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.
+#
+##############################################################################
+from zodb.btrees._OOBTree import *
=== Zope3/src/zodb/btrees/SetOpTemplate.c 1.1 => 1.2 === (459/559 lines abridged)
--- /dev/null Wed Dec 25 09:13:48 2002
+++ Zope3/src/zodb/btrees/SetOpTemplate.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,556 @@
+/*****************************************************************************
+
+ 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
+
[-=- -=- -=- 459 lines omitted -=- -=- -=-]
+ /* If set is a bucket, do a straight resize + memcpy. */
+ if (set->ob_type == (PyTypeObject*)&SetType ||
+ set->ob_type == (PyTypeObject*)&BucketType)
+ {
+ Bucket *b = BUCKET(set);
+ int status = 0;
+
+ UNLESS (PER_USE(b)) goto Error;
+ if (b->len)
+ status = bucket_append(result, b, 0, b->len, 0, i < n-1);
+ PER_UNUSE(b);
+ if (status < 0) goto Error;
+ }
+ else {
+ /* No cheap way: iterate over set's elements one at a time. */
+ if (initSetIteration(&setiter, set, 0) < 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/src/zodb/btrees/SetTemplate.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:49 2002
+++ Zope3/src/zodb/btrees/SetTemplate.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,354 @@
+/*****************************************************************************
+
+ 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 */
+ (objobjproc)bucket_contains, /* sq_contains */
+ 0, /* sq_inplace_concat */
+ 0, /* sq_inplace_repeat */
+};
+
+static PyTypeObject SetType = {
+ PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+ 0, /* ob_size */
+ MODULE_NAME MOD_NAME_PREFIX "Set", /* tp_name */
+ sizeof(Bucket), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)bucket_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ (reprfunc)set_repr, /* tp_repr */
+ 0, /* tp_as_number */
+ &set_as_sequence, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)bucket_traverse, /* tp_traverse */
+ (inquiry)bucket_tp_clear, /* tp_clear */
+ 0, /* tp_richcompare */
+ offsetof(Bucket, po_weaklist), /* tp_weaklistoffset */
+ (getiterfunc)Bucket_getiter, /* tp_iter */
+ 0, /* tp_iternext */
+ Set_methods, /* tp_methods */
+ 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 */
+ 0, /*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/src/zodb/btrees/TreeSetTemplate.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:49 2002
+++ Zope3/src/zodb/btrees/TreeSetTemplate.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,230 @@
+/*****************************************************************************
+
+ 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"},
+ {"_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_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 PySequenceMethods TreeSet_as_sequence = {
+ (inquiry)0, /* sq_length */
+ (binaryfunc)0, /* sq_concat */
+ (intargfunc)0, /* sq_repeat */
+ (intargfunc)0, /* sq_item */
+ (intintargfunc)0, /* sq_slice */
+ (intobjargproc)0, /* sq_ass_item */
+ (intintobjargproc)0, /* sq_ass_slice */
+ (objobjproc)BTree_contains, /* sq_contains */
+ 0, /* sq_inplace_concat */
+ 0, /* sq_inplace_repeat */
+};
+
+static int
+TreeSet_init(PyObject *self, PyObject *args, PyObject *kwds)
+{
+ PyObject *v = NULL;
+
+ if (!PyArg_ParseTuple(args, "|O:" MOD_NAME_PREFIX "TreeSet", &v))
+ return -1;
+
+ if (v)
+ return _TreeSet_update((BTree *)self, v);
+ else
+ return 0;
+}
+
+static PyTypeObject TreeSetType = {
+ PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
+ 0, /* ob_size */
+ MODULE_NAME MOD_NAME_PREFIX "TreeSet",/* tp_name */
+ sizeof(BTree), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)BTree_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ &BTree_as_number_for_nonzero, /* tp_as_number */
+ &TreeSet_as_sequence, /* tp_as_sequence */
+ &TreeSet_as_mapping, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)BTree_traverse, /* tp_traverse */
+ (inquiry)BTree_tp_clear, /* tp_clear */
+ 0, /* tp_richcompare */
+ offsetof(BTree, po_weaklist), /* tp_weaklistoffset */
+ (getiterfunc)BTree_getiter, /* tp_iter */
+ 0, /* tp_iternext */
+ TreeSet_methods, /* tp_methods */
+ 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 */
+ 0, /*PyType_GenericNew,*/ /* tp_new */
+};
=== Zope3/src/zodb/btrees/_IIBTree.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:49 2002
+++ Zope3/src/zodb/btrees/_IIBTree.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,17 @@
+/* Setup template macros */
+
+#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
+
+#include "intkeymacros.h"
+#include "intvaluemacros.h"
+#ifndef EXCLUDE_INTSET_SUPPORT
+#include "BTree/intSet.h"
+#endif
+#include "BTreeModuleTemplate.c"
=== Zope3/src/zodb/btrees/_IOBTree.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:49 2002
+++ Zope3/src/zodb/btrees/_IOBTree.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,16 @@
+
+#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/src/zodb/btrees/_OIBTree.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:49 2002
+++ Zope3/src/zodb/btrees/_OIBTree.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,13 @@
+
+#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/src/zodb/btrees/_OOBTree.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:49 2002
+++ Zope3/src/zodb/btrees/_OOBTree.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,13 @@
+
+#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/src/zodb/btrees/__init__.py 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:49 2002
+++ Zope3/src/zodb/btrees/__init__.py Wed Dec 25 09:12:16 2002
@@ -0,0 +1,13 @@
+##############################################################################
+#
+# 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.
+#
+##############################################################################
=== Zope3/src/zodb/btrees/_fsBTree.c 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:49 2002
+++ Zope3/src/zodb/btrees/_fsBTree.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,56 @@
+/* fsBTree - FileStorage index BTree
+
+ 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.
+*/
+
+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/src/zodb/btrees/fsBTree.py 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:50 2002
+++ Zope3/src/zodb/btrees/fsBTree.py Wed Dec 25 09:12:16 2002
@@ -0,0 +1,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.
+#
+##############################################################################
+from zodb.btrees._fsBTree import *
=== Zope3/src/zodb/btrees/interfaces.py 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:50 2002
+++ Zope3/src/zodb/btrees/interfaces.py Wed Dec 25 09:12:16 2002
@@ -0,0 +1,336 @@
+##############################################################################
+#
+# 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 Interface, Interface.Standard
+from zodb.btrees import OOBTree
+from transaction.interfaces 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])
+
+class ICollection(Interface.Interface):
+
+ 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 max.
+ 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 max.
+ 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.Interface):
+ """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 types. 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.
+
+ If neither c1 nor c2 is None, the output is a Set if c1 is a Set or
+ TreeSet, and is a Bucket if c1 is a Bucket or BTree.
+ """
+
+ 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 Intersection 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, None).
+
+ If c1 is None and c2 is not None, the output is (weight2, c2).
+
+ If c1 is not None and c2 is None, the output is (weight1, c1).
+
+ Else, and hereafter, c1 is not None and c2 is not None.
+
+ If c1 and c2 are both sets, the output is 1 and the (unweighted)
+ union of the sets.
+
+ Else the output is 1 and a Bucket whose keys are the union of c1 and
+ c2's keys, and whose values are::
+
+ v1*weight1 + v2*weight2
+
+ where:
+
+ v1 is 0 if the key is not in c1
+ 1 if the key is in c1 and c1 is a set
+ c1[key] if the key is in c1 and c1 is a mapping
+
+ v2 is 0 if the key is not in c2
+ 1 if the key is in c2 and c2 is a set
+ c2[key] if the key is in c2 and c2 is a mapping
+
+ Note that c1 and c2 must be 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 (0, None).
+
+ If c1 is None and c2 is not None, the output is (weight2, c2).
+
+ If c1 is not None and c2 is None, the output is (weight1, c1).
+
+ Else, and hereafter, c1 is not None and c2 is not None.
+
+ If c1 and c2 are both sets, the output is the sum of the weights
+ and the (unweighted) intersection of the sets.
+
+ Else the output is 1 and a Bucket whose keys are the intersection of
+ c1 and c2's keys, and whose values are::
+
+ v1*weight1 + v2*weight2
+
+ where:
+
+ v1 is 1 if c1 is a set
+ c1[key] if c1 is a mapping
+
+ v2 is 1 if c2 is a set
+ c2[key] if c2 is a mapping
+
+ Note that c1 and c2 must be 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/src/zodb/btrees/intkeymacros.h 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:50 2002
+++ Zope3/src/zodb/btrees/intkeymacros.h Wed Dec 25 09:12:16 2002
@@ -0,0 +1,21 @@
+
+#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; \
+ }
+#define MULTI_INT_UNION 1
=== Zope3/src/zodb/btrees/intvaluemacros.h 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:50 2002
+++ Zope3/src/zodb/btrees/intvaluemacros.h Wed Dec 25 09:12:16 2002
@@ -0,0 +1,23 @@
+
+#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/src/zodb/btrees/objectkeymacros.h 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:50 2002
+++ Zope3/src/zodb/btrees/objectkeymacros.h Wed Dec 25 09:12:16 2002
@@ -0,0 +1,9 @@
+#define KEYMACROS_H "$Id$\n"
+#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/src/zodb/btrees/objectvaluemacros.h 1.1 => 1.2 ===
--- /dev/null Wed Dec 25 09:13:50 2002
+++ Zope3/src/zodb/btrees/objectvaluemacros.h Wed Dec 25 09:12:16 2002
@@ -0,0 +1,12 @@
+
+#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/src/zodb/btrees/sorters.c 1.1 => 1.2 === (430/530 lines abridged)
--- /dev/null Wed Dec 25 09:13:50 2002
+++ Zope3/src/zodb/btrees/sorters.c Wed Dec 25 09:12:16 2002
@@ -0,0 +1,527 @@
+/*****************************************************************************
+
+ 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 <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.
+*/
[-=- -=- -=- 430 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;
+}