[Zope3-checkins] CVS: Zope3/src/zodb/btrees - BTreeItemsTemplace.c:1.1.2.1 BTreeModuleTemplate.c:1.1.2.1 BTreeTemplate.c:1.1.2.1 BucketTemplate.c:1.1.2.1 IIBTree.py:1.1.2.1 IOBTree.py:1.1.2.1 Length.py:1.1.2.1 MergeTemplate.c:1.1.2.1 OIBTree.py:1.1.2.1 OOBTree.py:1.1.2.1 SetOpTemplate.c:1.1.2.1 SetTemplate.c:1.1.2.1 TreeSetTemplate.c:1.1.2.1 _IIBTree.c:1.1.2.1 _IOBTree.c:1.1.2.1 _OOBTree.c:1.1.2.1 __init__.py:1.1.2.1 _fsBTree.c:1.1.2.1 fsBTree.py:1.1.2.1 interfaces.py:1.1.2.1 intkeymacros.h:1.1.2.1 intvaluemacros.h:1.1.2.1 objectkeymacros.h:1.1.2.1 objectvaluemacros.h:1.1.2.1 sorters.c:1.1.2.1
Jim Fulton
jim@zope.com
Mon, 23 Dec 2002 14:30:49 -0500
Update of /cvs-repository/Zope3/src/zodb/btrees
In directory cvs.zope.org:/tmp/cvs-serv19908/zodb/btrees
Added Files:
Tag: NameGeddon-branch
BTreeItemsTemplace.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
_OOBTree.c __init__.py _fsBTree.c fsBTree.py interfaces.py
intkeymacros.h intvaluemacros.h objectkeymacros.h
objectvaluemacros.h sorters.c
Log Message:
Initial renaming before debugging
=== Added File Zope3/src/zodb/btrees/BTreeItemsTemplace.c === (604/704 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: BTreeItemsTemplace.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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) */
Bucket *lastbucket; /* Last bucket */
int currentoffset; /* Offset in currentbucket */
int pseudoindex; /* search finger index */
[-=- -=- -=- 604 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 */
};
=== Added File Zope3/src/zodb/btrees/BTreeModuleTemplate.c ===
/*****************************************************************************
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
/* 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. 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,
*_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: BTreeModuleTemplate.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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("Persistence.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.cPersistence", "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;
}
=== Added File Zope3/src/zodb/btrees/BTreeTemplate.c === (1885/1985 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: BTreeTemplate.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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,
"Empty BTree has non-NULL firstbucket");
result = 0;
goto Done;
[-=- -=- -=- 1885 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 */
};
=== Added File Zope3/src/zodb/btrees/BucketTemplate.c === (1562/1662 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: BucketTemplate.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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; \
}
[-=- -=- -=- 1562 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;
}
=== Added File Zope3/src/zodb/btrees/IIBTree.py ===
##############################################################################
#
# 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 *
=== Added File Zope3/src/zodb/btrees/IOBTree.py ===
##############################################################################
#
# 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 *
=== Added File Zope3/src/zodb/btrees/Length.py ===
##############################################################################
#
# 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
=== Added File Zope3/src/zodb/btrees/MergeTemplate.c ===
/*****************************************************************************
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: MergeTemplate.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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;
}
=== Added File Zope3/src/zodb/btrees/OIBTree.py ===
##############################################################################
#
# 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 *
=== Added File Zope3/src/zodb/btrees/OOBTree.py ===
##############################################################################
#
# 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 *
=== Added File Zope3/src/zodb/btrees/SetOpTemplate.c === (456/556 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: SetOpTemplate.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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)
[-=- -=- -=- 456 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
=== Added File Zope3/src/zodb/btrees/SetTemplate.c ===
/*****************************************************************************
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: SetTemplate.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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;
}
=== Added File Zope3/src/zodb/btrees/TreeSetTemplate.c ===
/*****************************************************************************
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: TreeSetTemplate.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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 */
};
=== Added File Zope3/src/zodb/btrees/_IIBTree.c ===
/* Setup template macros */
#define MASTER_ID "$Id: _IIBTree.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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"
=== Added File Zope3/src/zodb/btrees/_IOBTree.c ===
#define MASTER_ID "$Id: _IOBTree.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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"
=== Added File Zope3/src/zodb/btrees/_OOBTree.c ===
#define MASTER_ID "$Id: _OOBTree.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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"
=== Added File Zope3/src/zodb/btrees/__init__.py ===
##############################################################################
#
# 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.
#
##############################################################################
=== Added File Zope3/src/zodb/btrees/_fsBTree.c ===
/* 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: _fsBTree.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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: _fsBTree.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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: _fsBTree.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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"
=== Added File Zope3/src/zodb/btrees/fsBTree.py ===
##############################################################################
#
# 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 *
=== Added File Zope3/src/zodb/btrees/interfaces.py ===
##############################################################################
#
# 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
=== Added File Zope3/src/zodb/btrees/intkeymacros.h ===
#define KEYMACROS_H "$Id: intkeymacros.h,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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
=== Added File Zope3/src/zodb/btrees/intvaluemacros.h ===
#define VALUEMACROS_H "$Id: intvaluemacros.h,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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))
=== Added File Zope3/src/zodb/btrees/objectkeymacros.h ===
#define KEYMACROS_H "$Id: objectkeymacros.h,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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)
=== Added File Zope3/src/zodb/btrees/objectvaluemacros.h ===
#define VALUEMACROS_H "$Id: objectvaluemacros.h,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $\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)
=== Added File Zope3/src/zodb/btrees/sorters.c === (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: sorters.c,v 1.1.2.1 2002/12/23 19:30:46 jim Exp $ */
/* 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.
*/
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;
}