[Zope-Checkins] CVS: Zope2 - BTreeItemsTemplate.c:1.3.6.1 BTreeModuleTemplate.c:1.4.6.1 BTreeTemplate.c:1.9.6.1 BucketTemplate.c:1.6.6.1 IIBTree.c:1.6.6.1 IOBTree.c:1.6.6.1 Interfaces.py:1.4.6.1 Length.py:1.1.4.1 MergeTemplate.c:1.1.4.1 OIBTree.c:1.5.6.1 OOBTree.c:1.5.6.1 SetOpTemplate.c:1.3.6.1 SetTemplate.c:1.6.6.1 Setup:1.5.6.1 TreeSetTemplate.c:1.5.6.1 __init__.py:1.2.6.1 config.c:1.1.4.1 convert.py:1.1.4.1 intkeymacros.h:1.2.6.1 intvaluemacros.h:1.3.6.1 objectkeymacros.h:1.1.6.1 objectvaluemacros.h:1.2.6.1
Jim Fulton
jim@digiciool.com
Thu, 15 Mar 2001 08:10:30 -0500 (EST)
Update of /cvs-repository/Zope2/lib/python/BTrees
In directory korak:/home/jim/atmp/merge/2.3/lib/python/BTrees
Added Files:
Tag: zope-2_3-branch
BTreeItemsTemplate.c BTreeModuleTemplate.c BTreeTemplate.c
BucketTemplate.c IIBTree.c IOBTree.c Interfaces.py Length.py
MergeTemplate.c OIBTree.c OOBTree.c SetOpTemplate.c
SetTemplate.c Setup TreeSetTemplate.c __init__.py config.c
convert.py intkeymacros.h intvaluemacros.h objectkeymacros.h
objectvaluemacros.h
Log Message:
Merged changes from Catalog-BTrees-Integration branch.
--- Added File BTreeItemsTemplate.c in package Zope2 ---
/*****************************************************************************
Zope Public License (ZPL) Version 1.0
-------------------------------------
Copyright (c) Digital Creations. All rights reserved.
This license has been certified as Open Source(tm).
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions in source code must retain the above copyright
notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions, and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
3. Digital Creations requests that attribution be given to Zope
in any manner possible. Zope includes a "Powered by Zope"
button that is installed by default. While it is not a license
violation to remove this button, it is requested that the
attribution remain. A significant investment has been put
into Zope, and this effort will continue if the Zope community
continues to grow. This is one way to assure that growth.
4. All advertising materials and documentation mentioning
features derived from or use of this software must display
the following acknowledgement:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
In the event that the product being advertised includes an
intact Zope distribution (with copyright and license included)
then this clause is waived.
5. Names associated with Zope or Digital Creations must not be used to
endorse or promote products derived from this software without
prior written permission from Digital Creations.
6. Modified redistributions of any form whatsoever must retain
the following acknowledgment:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
Intact (re-)distributions of any official Zope release do not
require an external acknowledgement.
7. Modifications are encouraged but must be packaged separately as
patches to official Zope releases. Distributions that do not
clearly separate the patches from the original work must be clearly
labeled as unofficial distributions. Modifications which do not
carry the name Zope may be packaged in any form, as long as they
conform to all of the clauses above.
Disclaimer
THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
This software consists of contributions made by Digital Creations and
many individuals on behalf of Digital Creations. Specific
attributions are listed in the accompanying credits file.
****************************************************************************/
typedef struct {
PyObject_HEAD
Bucket *firstbucket; /* First bucket known */
Bucket *currentbucket; /* Current bucket position */
Bucket *lastbucket; /* Last bucket position */
int currentoffset; /* Start count of current bucket*/
int pseudoindex; /* Its an indicator */
int first, last;
char kind;
} BTreeItems;
#define ITEMS(O)((BTreeItems*)(O))
static PyObject *
newBTreeItems(char kind,
Bucket *lowbucket, int lowoffset,
Bucket *highbucket, int highoffset);
static void
BTreeItems_dealloc(BTreeItems *self)
{
Py_XDECREF(self->firstbucket);
Py_XDECREF(self->lastbucket);
Py_XDECREF(self->currentbucket);
PyMem_DEL(self);
}
static int
BTreeItems_length_or_nonzero(BTreeItems *self, int nonzero)
{
int r;
Bucket *b, *next;
b=self->firstbucket;
UNLESS(b) return 0;
r=self->last + 1 - self->first;
if (nonzero && r > 0)
/* Short-circuit if all we care about is nonempty */
return 1;
if (b == self->lastbucket) return r;
Py_INCREF(b);
PER_USE_OR_RETURN(b, -1);
while ((next=b->next))
{
r += b->len;
if (nonzero && r > 0)
/* Short-circuit if all we care about is nonempty */
break;
if (next == self->lastbucket)
break; /* we already counted the last bucket */
Py_INCREF(next);
PER_ALLOW_DEACTIVATION(b);
Py_DECREF(b);
b=next;
PER_USE_OR_RETURN(b, -1);
}
PER_ALLOW_DEACTIVATION(b);
Py_DECREF(b);
return r >= 0 ? r : 0;
}
static int
BTreeItems_length( BTreeItems *self)
{
return BTreeItems_length_or_nonzero(self, 0);
}
/*
** BTreeItems_seek
**
** Find the ith position in the BTreeItems. Pseudoindex is used to
** determine motion relative to the current bucket.
**
** Arguments: self The BTree
** i the index to seek to, positive for a forward
** index (0..n) or negative (-m..-1) (m=n+1)
**
**
** Returns 0 if successful, -1 on failure to seek
*/
static int
BTreeItems_seek(BTreeItems *self, int i)
{
int delta, pseudoindex, currentoffset;
Bucket *b, *currentbucket;
currentbucket=self->currentbucket;
UNLESS(currentbucket)
{
IndexError(i);
return -1;
}
pseudoindex=self->pseudoindex;
Py_INCREF(currentbucket);
currentoffset=self->currentoffset;
/* Make sure that the index and psuedoindex have the same sign */
if (pseudoindex < 0 && i >=0)
{
/* Position to the start of the sequence. */
ASSIGNB(currentbucket, self->firstbucket);
Py_INCREF(currentbucket);
currentoffset = self->first;
UNLESS (PER_USE(currentbucket)) goto err;
/* We need to be careful that we have a valid offset! */
if (currentoffset >= currentbucket->len)
{
switch (firstBucketOffset(¤tbucket, ¤toffset))
{
case 0: goto no_match;
case -1: goto err;
}
}
pseudoindex = 0;
}
else if (self->pseudoindex >= 0 && i < 0)
{
/* Position to the end of the sequence. */
ASSIGNBC(currentbucket, self->lastbucket);
currentoffset = self->last;
UNLESS (PER_USE(currentbucket)) goto err;
/* We need to be careful that we have a valid offset! */
if (currentoffset >= currentbucket->len)
{
switch (lastBucketOffset(¤tbucket, ¤toffset,
self->firstbucket, i))
{
case 0: goto no_match;
case -1: goto err;
}
}
pseudoindex = -1;
}
else
{
UNLESS (PER_USE(currentbucket)) goto err;
/* We need to be careful that we have a valid offset! */
if (currentoffset >= currentbucket->len) goto no_match;
}
/* Whew, we got here so we have a valid offset! */
delta = i - pseudoindex;
if (delta)
while (delta)
{
if (delta < 0)
{
/* First, would we drop below zero? */
if (pseudoindex >= 0 && pseudoindex + delta < 0) goto no_match;
/* Next, do we have to backup a bucket? */
if (currentoffset + delta < 0)
{
if (currentbucket == self->firstbucket) goto no_match;
b=PreviousBucket(currentbucket, self->firstbucket, i);
if (b==NULL) goto no_match;
PER_ALLOW_DEACTIVATION(currentbucket);
ASSIGNB(currentbucket, b);
UNLESS (PER_USE(currentbucket)) goto err;
delta += currentoffset;
pseudoindex -= currentoffset + 1;
if ((currentoffset = currentbucket->len - 1) < 0)
/* We backed into an empty bucket. Fix the psuedo index */
if (++pseudoindex == 0) goto no_match;
}
else
{ /* Local adjustment */
pseudoindex += delta;
currentoffset += delta;
}
if (currentbucket == self->firstbucket &&
currentoffset < self->first) goto no_match;
}
else if (delta > 0)
{
/* Simple backwards range check */
if (pseudoindex < 0 && pseudoindex + delta >= 0)
goto no_match;
/* Next, do we go forward a bucket? */
if (currentoffset + delta >= currentbucket->len)
{
while (1)
{
if (currentbucket == self->lastbucket) goto no_match;
if ((b=currentbucket->next) == NULL) goto no_match;
delta -= currentbucket->len - currentoffset;
pseudoindex += (currentbucket->len - currentoffset);
Py_INCREF(b);
PER_ALLOW_DEACTIVATION(currentbucket);
ASSIGNB(currentbucket, b);
UNLESS (PER_USE(currentbucket)) goto err;
currentoffset = 0;
if (currentbucket->len) break;
}
}
else
{ /* Local adjustment */
pseudoindex += delta;
currentoffset += delta;
}
if (currentbucket == self->lastbucket &&
currentoffset > self->last) goto no_match;
}
delta = i - pseudoindex;
}
else
{ /* Sanity check current bucket/offset */
if (currentbucket == self->firstbucket &¤toffset < self->first)
goto no_match;
if (currentbucket == self->lastbucket && currentoffset > self->last)
goto no_match;
}
PER_ALLOW_DEACTIVATION(currentbucket);
if (currentbucket==self->currentbucket) Py_DECREF(currentbucket);
else ASSIGNB(self->currentbucket, currentbucket);
self->pseudoindex=pseudoindex;
self->currentoffset=currentoffset;
return 0;
no_match:
IndexError(i);
PER_ALLOW_DEACTIVATION(currentbucket);
err:
Py_XDECREF(currentbucket);
return -1;
}
/*
** BTreeItems_item
**
** Arguments: self a BTreeItems structure
** i Which item to inspect
**
** Returns: the BTreeItems_item_BTree of self->kind, i
** (ie pulls the ith item out)
*/
static PyObject *
BTreeItems_item(BTreeItems *self, int i)
{
PyObject *r, *k=0, *v=0;
if (BTreeItems_seek(self, i) < 0) return NULL;
PER_USE_OR_RETURN(self->currentbucket, NULL);
switch(self->kind) {
case 'v':
COPY_VALUE_TO_OBJECT(r, self->currentbucket->values[self->currentoffset]);
break;
case 'i':
COPY_KEY_TO_OBJECT(k, self->currentbucket->keys[self->currentoffset]);
UNLESS (k) return NULL;
COPY_VALUE_TO_OBJECT(v, self->currentbucket->values[self->currentoffset]);
UNLESS (v) return NULL;
UNLESS (r=PyTuple_New(2)) goto err;
PyTuple_SET_ITEM(r, 0, k);
PyTuple_SET_ITEM(r, 1, v);
break;
default:
COPY_KEY_TO_OBJECT(r, self->currentbucket->keys[self->currentoffset]);
break;
}
PER_ALLOW_DEACTIVATION(self->currentbucket);
return r;
err:
Py_DECREF(k);
Py_XDECREF(v);
PER_ALLOW_DEACTIVATION(self->currentbucket);
return NULL;
}
/*
** BTreeItems_slice
**
** Creates a new BTreeItems structure representing the slice
** between the low and high range
**
** Arguments: self The old BTreeItems structure
** ilow The start index
** ihigh The end index
**
** Returns: BTreeItems item
*/
static PyObject *
BTreeItems_slice(BTreeItems *self, int ilow, int ihigh)
{
Bucket *lowbucket;
Bucket *highbucket;
int lowoffset;
int highoffset;
if (BTreeItems_seek(self, ilow) < 0) return NULL;
lowbucket = self->currentbucket;
lowoffset = self->currentoffset;
if (BTreeItems_seek(self, ihigh) < 0) return NULL;
highbucket = self->currentbucket;
highoffset = self->currentoffset;
return newBTreeItems(self->kind,
lowbucket, lowoffset, highbucket, highoffset);
}
static PySequenceMethods BTreeItems_as_sequence = {
(inquiry) BTreeItems_length,
(binaryfunc)0,
(intargfunc)0,
(intargfunc) BTreeItems_item,
(intintargfunc) BTreeItems_slice,
};
/* Number Method items (just for nb_nonzero!) */
static int
BTreeItems_nonzero(BTreeItems *self)
{
return BTreeItems_length_or_nonzero(self, 1);
}
static PyNumberMethods BTreeItems_as_number_for_nonzero = {
0,0,0,0,0,0,0,0,0,0,
(inquiry)BTreeItems_nonzero};
static PyTypeObject BTreeItemsType = {
PyObject_HEAD_INIT(NULL)
0, /*ob_size*/
PREFIX "BTreeItems", /*tp_name*/
sizeof(BTreeItems), /*tp_basicsize*/
0, /*tp_itemsize*/
/* methods */
(destructor) BTreeItems_dealloc, /*tp_dealloc*/
(printfunc)0, /*tp_print*/
(getattrfunc)0, /*obsolete tp_getattr*/
(setattrfunc)0, /*obsolete tp_setattr*/
(cmpfunc)0, /*tp_compare*/
(reprfunc)0, /*tp_repr*/
&BTreeItems_as_number_for_nonzero, /*tp_as_number*/
&BTreeItems_as_sequence, /*tp_as_sequence*/
0, /*tp_as_mapping*/
(hashfunc)0, /*tp_hash*/
(ternaryfunc)0, /*tp_call*/
(reprfunc)0, /*tp_str*/
0, /*tp_getattro*/
0, /*tp_setattro*/
/* Space for future expansion */
0L,0L,
"Sequence type used to iterate over BTree items." /* Documentation string */
};
static PyObject *
newBTreeItems(char kind,
Bucket *lowbucket, int lowoffset,
Bucket *highbucket, int highoffset)
{
BTreeItems *self;
UNLESS (self = PyObject_NEW(BTreeItems, &BTreeItemsType)) return NULL;
self->kind=kind;
self->first=lowoffset;
self->last=highoffset;
if (! lowbucket || (lowbucket==highbucket && lowoffset > highoffset))
{
self->firstbucket = 0;
self->lastbucket = 0;
self->currentbucket = 0;
}
else
{
Py_INCREF(lowbucket);
self->firstbucket = lowbucket;
Py_XINCREF(highbucket);
self->lastbucket = highbucket;
Py_XINCREF(lowbucket);
self->currentbucket = lowbucket;
}
self->currentoffset = lowoffset;
self->pseudoindex = 0;
return OBJECT(self);
}
static int
nextBTreeItems(SetIteration *i)
{
if (i->position >= 0)
{
if (i->position)
{
DECREF_KEY(i->key);
DECREF_VALUE(i->value);
}
if (BTreeItems_seek(ITEMS(i->set), i->position) >= 0)
{
Bucket *currentbucket;
currentbucket = BUCKET(ITEMS(i->set)->currentbucket);
UNLESS(PER_USE(currentbucket)) return -1;
COPY_KEY(i->key, currentbucket->keys[ITEMS(i->set)->currentoffset]);
INCREF_KEY(i->key);
COPY_VALUE(i->value,
currentbucket->values[ITEMS(i->set)->currentoffset]);
COPY_VALUE(i->value,
BUCKET(ITEMS(i->set)->currentbucket)
->values[ITEMS(i->set)->currentoffset]);
INCREF_VALUE(i->value);
i->position ++;
PER_ALLOW_DEACTIVATION(currentbucket);
}
else
{
i->position = -1;
PyErr_Clear();
}
}
return 0;
}
static int
nextTreeSetItems(SetIteration *i)
{
if (i->position >= 0)
{
if (i->position)
{
DECREF_KEY(i->key);
}
if (BTreeItems_seek(ITEMS(i->set), i->position) >= 0)
{
Bucket *currentbucket;
currentbucket = BUCKET(ITEMS(i->set)->currentbucket);
UNLESS(PER_USE(currentbucket)) return -1;
COPY_KEY(i->key, currentbucket->keys[ITEMS(i->set)->currentoffset]);
INCREF_KEY(i->key);
i->position ++;
PER_ALLOW_DEACTIVATION(currentbucket);
}
else
{
i->position = -1;
PyErr_Clear();
}
}
return 0;
}
--- Added File BTreeModuleTemplate.c in package Zope2 ---
/*****************************************************************************
Zope Public License (ZPL) Version 1.0
-------------------------------------
Copyright (c) Digital Creations. All rights reserved.
This license has been certified as Open Source(tm).
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions in source code must retain the above copyright
notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions, and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
3. Digital Creations requests that attribution be given to Zope
in any manner possible. Zope includes a "Powered by Zope"
button that is installed by default. While it is not a license
violation to remove this button, it is requested that the
attribution remain. A significant investment has been put
into Zope, and this effort will continue if the Zope community
continues to grow. This is one way to assure that growth.
4. All advertising materials and documentation mentioning
features derived from or use of this software must display
the following acknowledgement:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
In the event that the product being advertised includes an
intact Zope distribution (with copyright and license included)
then this clause is waived.
5. Names associated with Zope or Digital Creations must not be used to
endorse or promote products derived from this software without
prior written permission from Digital Creations.
6. Modified redistributions of any form whatsoever must retain
the following acknowledgment:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
Intact (re-)distributions of any official Zope release do not
require an external acknowledgement.
7. Modifications are encouraged but must be packaged separately as
patches to official Zope releases. Distributions that do not
clearly separate the patches from the original work must be clearly
labeled as unofficial distributions. Modifications which do not
carry the name Zope may be packaged in any form, as long as they
conform to all of the clauses above.
Disclaimer
THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
This software consists of contributions made by Digital Creations and
many individuals on behalf of Digital Creations. Specific
attributions are listed in the accompanying credits file.
****************************************************************************/
static char BTree_module_documentation[] =
""
"\n$Id: BTreeModuleTemplate.c,v 1.4.6.1 2001/03/15 13:10:28 jim Exp $"
;
#ifdef PERSISTENT
#include "cPersistence.h"
/***************************************************************
The following are macros that ought to be in cPersistence.h */
#ifndef PER_USE
#define PER_USE(O) \
(((O)->state != cPersistent_GHOST_STATE \
|| (cPersistenceCAPI->setstate((PyObject*)(O)) >= 0)) \
? (((O)->state==cPersistent_UPTODATE_STATE) \
? ((O)->state=cPersistent_STICKY_STATE) : 1) : 0)
#endif
/***************************************************************/
#else
#include "ExtensionClass.h"
#define PER_USE_OR_RETURN(self, NULL)
#define PER_ALLOW_DEACTIVATION(self)
#define PER_PREVENT_DEACTIVATION(self)
#define PER_DEL(self)
#define PER_USE(O) 1
#define PER_CHANGED(O) 0
#endif
static PyObject *sort_str, *reverse_str, *items_str, *__setstate___str;
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); }
typedef struct BTreeItemStruct {
KEY_TYPE key;
PyObject *value;
} BTreeItem;
typedef struct Bucket_s {
#ifdef PERSISTENT
cPersistent_HEAD
#else
PyObject_HEAD
#endif
int size, len;
struct Bucket_s *next;
KEY_TYPE *keys;
VALUE_TYPE *values;
} Bucket;
#define BUCKET(O) ((Bucket*)(O))
static void PyVar_AssignB(Bucket **v, Bucket *e) { Py_XDECREF(*v); *v=e;}
#define ASSIGNB(V,E) PyVar_AssignB(&(V),(E))
#define ASSIGNBC(V,E) (Py_INCREF((E)), PyVar_AssignB(&(V),(E)))
typedef struct {
#ifdef PERSISTENT
cPersistent_HEAD
#else
PyObject_HEAD
#endif
int size, len;
Bucket *firstbucket;
BTreeItem *data;
} BTree;
staticforward PyExtensionClass BTreeType;
#define BTREE(O) ((BTree*)(O))
typedef struct SetIteration_s
{
PyObject *set;
int position;
int hasValue;
KEY_TYPE key;
VALUE_TYPE value;
int (*next)(struct SetIteration_s*);
} SetIteration;
static PyObject *
IndexError(int i)
{
PyObject *v;
v=PyInt_FromLong(i);
UNLESS (v) {
v=Py_None;
Py_INCREF(v);
}
PyErr_SetObject(PyExc_IndexError, v);
Py_DECREF(v);
return NULL;
}
static Bucket *
PreviousBucket(Bucket *current, Bucket *first, int i)
{
if (! first) return NULL;
if (first==current)
{
IndexError(i);
return NULL;
}
Py_INCREF(first);
while (1)
{
PER_USE_OR_RETURN(first,NULL);
if (first->next==current)
{
PER_ALLOW_DEACTIVATION(first);
return first;
}
else if (first->next)
{
Bucket *next = first->next;
Py_INCREF(next);
PER_ALLOW_DEACTIVATION(first);
Py_DECREF(first);
first=next;
}
else
{
PER_ALLOW_DEACTIVATION(first);
Py_DECREF(first);
IndexError(i);
return NULL;
}
}
}
static int
firstBucketOffset(Bucket **bucket, int *offset)
{
Bucket *b;
*offset = (*bucket)->len - 1;
while ((*bucket)->len < 1)
{
b=(*bucket)->next;
if (b==NULL) return 0;
Py_INCREF(b);
PER_ALLOW_DEACTIVATION((*bucket));
ASSIGNB((*bucket), b);
UNLESS (PER_USE(*bucket)) return -1;
*offset = 0;
}
}
static int
lastBucketOffset(Bucket **bucket, int *offset, Bucket *firstbucket, int i)
{
Bucket *b;
*offset = (*bucket)->len - 1;
while ((*bucket)->len < 1)
{
b=PreviousBucket((*bucket), firstbucket, i);
if (b==NULL) return 0;
PER_ALLOW_DEACTIVATION((*bucket));
ASSIGNB((*bucket), b);
UNLESS (PER_USE(*bucket)) return -1;
*offset = (*bucket)->len - 1;
}
}
static void *
PyMalloc(size_t sz)
{
void *r;
ASSERT(sz > 0, "non-positive size malloc", NULL);
if (r=malloc(sz)) return r;
PyErr_NoMemory();
return NULL;
}
static void *
PyRealloc(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
{NULL, NULL} /* sentinel */
};
void
INITMODULE ()
{
PyObject *m, *d;
UNLESS (sort_str=PyString_FromString("sort")) return;
UNLESS (reverse_str=PyString_FromString("reverse")) return;
UNLESS (items_str=PyString_FromString("items")) return;
UNLESS (__setstate___str=PyString_FromString("__setstate__")) return;
UNLESS (PyExtensionClassCAPI=PyCObject_Import("ExtensionClass","CAPI"))
return;
#ifdef PERSISTENT
if (cPersistenceCAPI=PyCObject_Import("cPersistence","CAPI"))
{
BucketType.methods.link=cPersistenceCAPI->methods;
BucketType.tp_getattro=cPersistenceCAPI->getattro;
BucketType.tp_setattro=cPersistenceCAPI->setattro;
SetType.methods.link=cPersistenceCAPI->methods;
SetType.tp_getattro=cPersistenceCAPI->getattro;
SetType.tp_setattro=cPersistenceCAPI->setattro;
BTreeType.methods.link=cPersistenceCAPI->methods;
BTreeType.tp_getattro=cPersistenceCAPI->getattro;
BTreeType.tp_setattro=cPersistenceCAPI->setattro;
TreeSetType.methods.link=cPersistenceCAPI->methods;
TreeSetType.tp_getattro=cPersistenceCAPI->getattro;
TreeSetType.tp_setattro=cPersistenceCAPI->setattro;
}
else return;
#else
BTreeType.tp_getattro=PyExtensionClassCAPI->getattro;
BucketType.tp_getattro=PyExtensionClassCAPI->getattro;
SetType.tp_getattro=PyExtensionClassCAPI->getattro;
TreeSetType.tp_getattro=PyExtensionClassCAPI->getattro;
#endif
BTreeItemsType.ob_type=&PyType_Type;
#ifdef INTSET_H
UNLESS(d = PyImport_ImportModule("intSet")) return;
UNLESS(intSetType = PyObject_GetAttrString (d, "intSet")) return;
Py_DECREF (d);
#endif
/* Create the module and add the functions */
m = Py_InitModule4(PREFIX "BTree", module_methods,
BTree_module_documentation,
(PyObject*)NULL,PYTHON_API_VERSION);
/* Add some symbolic constants to the module */
d = PyModule_GetDict(m);
PyDict_SetItemString(d, "__version__",
PyString_FromString("$Revision: 1.4.6.1 $"));
PyExtensionClass_Export(d,PREFIX "Bucket", BucketType);
PyExtensionClass_Export(d,PREFIX "BTree", BTreeType);
PyExtensionClass_Export(d,PREFIX "Set", SetType);
PyExtensionClass_Export(d,PREFIX "TreeSet", TreeSetType);
/* Check for errors */
if (PyErr_Occurred())
Py_FatalError("can't initialize module " PREFIX "BTree");
}
--- Added File BTreeTemplate.c in package Zope2 ---
/*****************************************************************************
Zope Public License (ZPL) Version 1.0
-------------------------------------
Copyright (c) Digital Creations. All rights reserved.
This license has been certified as Open Source(tm).
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions in source code must retain the above copyright
notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions, and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
3. Digital Creations requests that attribution be given to Zope
in any manner possible. Zope includes a "Powered by Zope"
button that is installed by default. While it is not a license
violation to remove this button, it is requested that the
attribution remain. A significant investment has been put
into Zope, and this effort will continue if the Zope community
continues to grow. This is one way to assure that growth.
4. All advertising materials and documentation mentioning
features derived from or use of this software must display
the following acknowledgement:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
In the event that the product being advertised includes an
intact Zope distribution (with copyright and license included)
then this clause is waived.
5. Names associated with Zope or Digital Creations must not be used to
endorse or promote products derived from this software without
prior written permission from Digital Creations.
6. Modified redistributions of any form whatsoever must retain
the following acknowledgment:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
Intact (re-)distributions of any official Zope release do not
require an external acknowledgement.
7. Modifications are encouraged but must be packaged separately as
patches to official Zope releases. Distributions that do not
clearly separate the patches from the original work must be clearly
labeled as unofficial distributions. Modifications which do not
carry the name Zope may be packaged in any form, as long as they
conform to all of the clauses above.
Disclaimer
THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
This software consists of contributions made by Digital Creations and
many individuals on behalf of Digital Creations. Specific
attributions are listed in the accompanying credits file.
****************************************************************************/
/*
** _BTree_get
**
*/
static PyObject *
_BTree_get(BTree *self, PyObject *keyarg, int has_key)
{
int min, max, i, cmp, copied=1;
PyObject *r;
KEY_TYPE key;
COPY_KEY_FROM_ARG(key, keyarg, &copied);
UNLESS (copied) return NULL;
PER_USE_OR_RETURN(self, NULL);
if (self->len)
{
for (min=0, max=self->len, i=max/2; max-min > 1; i=(min+max)/2)
{
cmp=TEST_KEY(self->data[i].key, key);
if (cmp < 0) min=i;
else if (cmp == 0)
{
min=i;
break;
}
else max=i;
}
if (SameType_Check(self, self->data[min].value))
r=_BTree_get( BTREE(self->data[min].value), keyarg,
has_key ? has_key + 1: 0);
else
r=_bucket_get(BUCKET(self->data[min].value), keyarg,
has_key ? has_key + 1: 0);
}
else
{ /* No data */
UNLESS (has_key)
{
PyErr_SetObject(PyExc_KeyError, keyarg);
r=NULL;
}
else
r=PyInt_FromLong(0);
}
PER_ALLOW_DEACTIVATION(self);
return r;
}
static PyObject *
BTree_get(BTree *self, PyObject *key)
{
return _BTree_get(self, key, 0);
}
/*
Copy data from the current BTree to the newly created BTree, next.
Reset length to reflect the fact that we've given up some data.
*/
static int
BTree_split(BTree *self, int index, BTree *next)
{
int next_size;
ASSERT(self->len > 1, "split of empty tree", -1);
if (index < 0 || index >= self->len) index=self->len/2;
next_size=self->len-index;
ASSERT(next_size > 0, "split creates empty tree", -1);
UNLESS (next->data=PyMalloc(sizeof(BTreeItem)*next_size)) return -1;
memcpy(next->data, self->data+index, sizeof(BTreeItem)*next_size);
next->size=next->len=next_size;
self->len = index;
if (SameType_Check(self, next->data->value))
{
PER_USE_OR_RETURN(BTREE(next->data->value), -1);
next->firstbucket = BTREE(next->data->value)->firstbucket;
Py_XINCREF(next->firstbucket);
PER_ALLOW_DEACTIVATION(BTREE(next->data->value));
}
else
{
next->firstbucket = BUCKET(next->data->value);
Py_XINCREF(next->firstbucket);
}
return 0;
}
/* Split out data among two newly created BTrees, which become
out children.
*/
static int
BTree_clone(BTree *self)
{
/* We've grown really big without anybody splitting us.
We should split ourselves.
*/
BTree *n1=0, *n2=0;
BTreeItem *d=0;
/* Create two BTrees to hold ourselves after split */
UNLESS (n1=BTREE(PyObject_CallObject(OBJECT(self->ob_type), NULL)))
return -1;
UNLESS (n2=BTREE(PyObject_CallObject(OBJECT(self->ob_type), NULL)))
goto err;
/* Create a new data buffer to hold two BTrees */
UNLESS (d=PyMalloc(sizeof(BTreeItem)*2)) goto err;
/* Split ourself */
if (BTree_split(self,-1,n2) < 0) goto err;
/* Move our data to new BTree */
n1->size=self->size;
n1->len=self->len;
n1->data=self->data;
n1->firstbucket = self->firstbucket;
Py_XINCREF(n1->firstbucket);
/* Initialize our data to hold split data */
self->data=d;
self->len=2;
self->size=2;
self->data->value=OBJECT(n1);
COPY_KEY(self->data[1].key, n2->data->key);
/* We take the unused reference from n2, so there's no reason to INCREF! */
/* INCREF_KEY(self->data[1].key); */
self->data[1].value=OBJECT(n2);
return 0;
err:
Py_XDECREF(n1);
Py_XDECREF(n2);
if (d) free(d);
return -1;
}
/*
** BTree_grow
**
** Grow a BTree
**
** Arguments: self The BTree
** index the index item to insert at
**
** Returns: 0 on success
** -1 on failure
*/
static int
BTree_grow(BTree *self, int index, int noval)
{
int i;
PyObject *v, *e=0;
BTreeItem *d;
if (self->len == self->size)
{
if (self->size)
{
UNLESS (d=PyRealloc(self->data, sizeof(BTreeItem)*self->size*2))
return -1;
self->data=d;
self->size *= 2;
}
else
{
UNLESS (d=PyMalloc(sizeof(BTreeItem)*2))
return -1;
self->data=d;
self->size = 2;
}
}
d=self->data+index;
if (self->len)
{
v=d->value;
/* Create a new object of the same type as the target value */
UNLESS (e=PyObject_CallObject(OBJECT(v->ob_type), NULL)) return -1;
PER_USE_OR_RETURN(BUCKET(v), -1);
/* Now split between the original (v) and the new (e) at the midpoint*/
if (SameType_Check(self, v))
{
i=BTree_split( BTREE(v), -1, BTREE(e));
}
else
{
i=bucket_split(BUCKET(v), -1, BUCKET(e));
}
PER_ALLOW_DEACTIVATION(BUCKET(v));
if (i < 0)
{
Py_DECREF(e);
return -1;
}
index++;
d++;
if (self->len > index) /* Shift up the old values one array slot */
memmove(d+1, d, sizeof(BTreeItem)*(self->len-index));
if (SameType_Check(self, v))
{
COPY_KEY(d->key, BTREE(e)->data->key);
/* We take the unused reference from e, so there's no
reason to INCREF!
*/
/* INCREF_KEY(self->data[1].key); */
}
else
{
COPY_KEY(d->key, BUCKET(e)->keys[0]);
INCREF_KEY(d->key);
}
d->value=e;
self->len++;
if (self->len >= MAX_BTREE_SIZE(self) * 2) return BTree_clone(self);
}
else
{
if (noval)
{
UNLESS (d->value=PyObject_CallObject(OBJECT(&SetType), NULL))
return -1;
}
else
{
UNLESS (d->value=PyObject_CallObject(OBJECT(&BucketType), NULL))
return -1;
}
self->len=1;
Py_INCREF(d->value);
self->firstbucket = BUCKET(d->value);
}
return 0;
}
static Bucket *
BTree_lastBucket(BTree *self)
{
PyObject *o;
UNLESS (self->data && self->len)
{
IndexError(-1); /*XXX*/
return NULL;
}
o=self->data[self->len - 1].value;
Py_INCREF(o);
UNLESS (SameType_Check(self, o)) return BUCKET(o);
self=BTREE(o);
PER_USE_OR_RETURN(self, NULL);
ASSIGN(o, OBJECT(BTree_lastBucket(self)));
PER_ALLOW_DEACTIVATION(self);
return BUCKET(o);
}
static int
BTree_deleteNextBucket(BTree *self)
{
Bucket *b;
PER_USE_OR_RETURN(self, -1);
UNLESS (b=BTree_lastBucket(self)) goto err;
if (Bucket_deleteNextBucket(b) < 0) goto err;
return 0;
err:
PER_ALLOW_DEACTIVATION(self);
return -1;
}
/*
Set (value != 0) or delete (value=0) a tree item.
If unique is non-zero, then only change if the key is
new.
If noval is non-zero, then don't set a value (the tree
is a set).
Return 1 on successful change, 0 is no change, -1 on error.
*/
static int
_BTree_set(BTree *self, PyObject *keyarg, PyObject *value,
int unique, int noval)
{
int i, min, max, cmp, grew, copied=1, changed=0, bchanged=0;
BTreeItem *d;
KEY_TYPE key;
COPY_KEY_FROM_ARG(key, keyarg, &copied);
UNLESS (copied) return -1;
PER_USE_OR_RETURN(self, -1);
UNLESS (self->len)
{
if (value)
{
if (BTree_grow(self, 0, noval) < 0) return -1;
}
else
{
PyErr_SetObject(PyExc_KeyError, keyarg);
return -1;
}
}
/* Binary search to find insertion point */
for (min=0, max=self->len, i=max/2; max-min > 1; i=(max+min)/2)
{
d=self->data+i;
cmp=TEST_KEY(d->key, key);
if (cmp < 0) min=i;
else if (cmp==0)
{
min=i;
break;
}
else max=i;
}
d=self->data+min;
if (SameType_Check(self, d->value))
grew= _BTree_set( BTREE(d->value), keyarg, value, unique, noval);
else
grew=_bucket_set(BUCKET(d->value), keyarg, value, unique, noval,
&bchanged);
if (grew < 0) goto err;
if (grew)
{
bchanged=1; /* A bucket changed size */
if (value) /* got bigger */
{
if (SameType_Check(self, d->value))
{
if (BTREE(d->value)->len > MAX_BTREE_SIZE(d->value))
{
if (BTree_grow(self, min, noval) < 0) goto err;
changed=1;
}
}
else
{
if (BUCKET(d->value)->len > MAX_BUCKET_SIZE(d->value))
{
if (BTree_grow(self, min, noval) < 0) goto err;
changed=1;
}
}
}
else /* got smaller */
{
if (min && grew > 1)
{ /* Somebody below us deleted their first bucket and */
/* and an intermediate tree couldn't handle it. */
if (BTree_deleteNextBucket(BTREE(d[-1].value)) < 0)
goto err;
grew=1; /* Reset flag, since we handled it */
}
if (BUCKET(d->value)->len == 0)
{ /* Got empty */
if (! SameType_Check(self, d->value))
{ /* We are about to delete a bucket. */
if (min)
{ /*If it's not our first bucket, we can tell the
previous bucket to adjust it's reference to
it. */
if (Bucket_deleteNextBucket(BUCKET(d[-1].value)) < 0)
goto err;
}
else
{ /* If it's the first bucket, we can't adjust the
reference to it ourselves, so we'll just
increment the grew flag to indicate to a
parent node that it's last bucket should
adjust its reference. If there is no parent,
then there's nothing to do. */
grew++;
}
}
self->len--;
Py_DECREF(d->value);
if (min) DECREF_KEY(d->key);
if (min < self->len)
memmove(d, d+1, (self->len-min)*sizeof(BTreeItem));
if (! min)
if (self->len)
{ /* We just deleted our first child, so we need to
adjust our first bucket. */
if (SameType_Check(self, self->data->value))
{
UNLESS (PER_USE(BTREE(self->data->value))) goto err;
ASSIGNB(self->firstbucket,
BTREE(self->data->value)->firstbucket);
Py_XINCREF(self->firstbucket);
PER_ALLOW_DEACTIVATION(BTREE(self->data->value));
}
else
{
ASSIGNB(self->firstbucket, BUCKET(self->data->value));
Py_INCREF(self->firstbucket);
}
/* We can toss our first key now */
DECREF_KEY(self->data->key);
}
else
{
Py_XDECREF(self->firstbucket);
self->firstbucket = 0;
}
changed=1;
}
}
}
#ifdef PERSISTENT
if (changed
|| (bchanged /* The bucket changed */
&& self->len == 1 /* We have only one */
&& ! SameType_Check(self, self->data->value) /* It's our child */
&& BUCKET(self->data->value)->oid == NULL /* It's in our record */
)
)
if (PER_CHANGED(self) < 0)
goto err;
#endif
PER_ALLOW_DEACTIVATION(self);
return grew;
err:
PER_ALLOW_DEACTIVATION(self);
return -1;
}
/*
** BTree_setitem
**
** wrapper for _BTree_set
**
** Arguments: self The BTree
** key The key to insert
** v The value to insert
**
** Returns -1 on failure
** 0 on success
*/
static int
BTree_setitem(BTree *self, PyObject *key, PyObject *v)
{
if (_BTree_set(self, key, v, 0, 0) < 0) return -1;
return 0;
}
/*
** _BTree_clear
**
** Clears out all of the values in the BTree
**
** Arguments: self The BTree
**
** Returns: 0 on success
** -1 on failure
*/
static int
_BTree_clear(BTree *self)
{
int i, l;
/* The order in which we dealocate, from "top to bottom" is critical
to prevent memory memory errors when the deallocation stack
becomes huge when dealocating use linked lists of buckets.
*/
if (self->firstbucket)
{
ASSERT(self->firstbucket->ob_refcnt > 1,
"Invalid firstbucket pointer", -1);
Py_DECREF(self->firstbucket);
self->firstbucket=NULL;
}
for (l=self->len, i=0; i < l; i++)
{
if (i) DECREF_KEY(self->data[i].key);
Py_DECREF(self->data[i].value);
}
self->len=0;
if (self->data)
{
free(self->data);
self->data=0;
self->size=0;
}
return 0;
}
#ifdef PERSISTENT
static PyObject *
BTree__p_deactivate(BTree *self, PyObject *args)
{
if (self->state==cPersistent_UPTODATE_STATE && self->jar)
{
if (_BTree_clear(self) < 0) return NULL;
self->state=cPersistent_GHOST_STATE;
}
Py_INCREF(Py_None);
return Py_None;
}
#endif
static PyObject *
BTree_clear(BTree *self, PyObject *args)
{
PER_USE_OR_RETURN(self, NULL);
if (self->len)
{
if (_BTree_clear(self) < 0) goto err;
if (PER_CHANGED(self) < 0) goto err;
}
PER_ALLOW_DEACTIVATION(self);
Py_INCREF(Py_None);
return Py_None;
err:
PER_ALLOW_DEACTIVATION(self);
return NULL;
}
static PyObject *
BTree_getstate(BTree *self, PyObject *args)
{
PyObject *r=0, *o;
int i, l;
PER_USE_OR_RETURN(self, NULL);
if (self->len)
{
UNLESS (r=PyTuple_New(self->len*2-1)) goto err;
if (self->len == 1
&& self->data->value->ob_type != self->ob_type
#ifdef PERSISTENT
&& BUCKET(self->data->value)->oid == NULL
#endif
)
{
/* We have just one bucket. Save it's data directly. */
UNLESS(o=bucket_getstate(BUCKET(self->data->value), NULL)) goto err;
PyTuple_SET_ITEM(r,0,o);
ASSIGN(r, Py_BuildValue("(O)", r));
}
else
{
for (i=0, l=0; i < self->len; i++)
{
if (i)
{
COPY_KEY_TO_OBJECT(o, self->data[i].key);
PyTuple_SET_ITEM(r,l,o);
l++;
}
o=self->data[i].value;
Py_INCREF(o);
PyTuple_SET_ITEM(r,l,o);
l++;
}
ASSIGN(r, Py_BuildValue("OO", r, self->firstbucket));
}
}
else
{
r = Py_None;
Py_INCREF(r);
}
PER_ALLOW_DEACTIVATION(self);
return r;
err:
PER_ALLOW_DEACTIVATION(self);
return NULL;
}
static int
_BTree_setstate(BTree *self, PyObject *state, int noval)
{
PyObject *items, *o, *firstbucket=0;
BTreeItem *d;
int len, l, i, r, copied=1;
if (_BTree_clear(self) < 0) return -1;
if (state != Py_None)
{
if (!PyArg_ParseTuple(state,"O|O",&items, &firstbucket))
return -1;
if ((len=PyTuple_Size(items)) < 0) return -1;
len=(len+1)/2;
if (len > self->size)
{
UNLESS (d=PyRealloc(self->data, sizeof(BTreeItem)*len)) return -1;
self->data=d;
self->size=len;
}
for (i=0, d=self->data, l=0; i < len; i++, d++)
{
if (i)
{
COPY_KEY_FROM_ARG(d->key, PyTuple_GET_ITEM(items,l), &copied);
l++;
UNLESS (&copied) return -1;
INCREF_KEY(d->key);
}
d->value=PyTuple_GET_ITEM(items,l);
if (PyTuple_Check(d->value))
{
if (noval)
{
UNLESS (d->value=PyObject_CallObject(OBJECT(&SetType),
NULL))
return -1;
if (_set_setstate(BUCKET(d->value),
PyTuple_GET_ITEM(items,l))
< 0) return -1;
}
else
{
UNLESS (d->value=PyObject_CallObject(OBJECT(&BucketType),
NULL))
return -1;
if (_bucket_setstate(BUCKET(d->value),
PyTuple_GET_ITEM(items,l))
< 0) return -1;
}
}
else
{
Py_INCREF(d->value);
}
l++;
}
if (len)
{
if (! firstbucket) firstbucket=self->data->value;
UNLESS (ExtensionClassSubclassInstance_Check(
firstbucket,
noval ? &SetType : &BucketType))
{
PyErr_SetString(PyExc_TypeError,
"No firstbucket in non-empty BTree");
return -1;
}
self->firstbucket = BUCKET(firstbucket);
Py_INCREF(firstbucket);
}
self->len=len;
}
return 0;
}
static PyObject *
BTree_setstate(BTree *self, PyObject *args)
{
int r;
if (!PyArg_ParseTuple(args,"O",&args)) return NULL;
PER_PREVENT_DEACTIVATION(self);
r=_BTree_setstate(self, args, 0);
PER_ALLOW_DEACTIVATION(self);
if (r < 0) return NULL;
Py_INCREF(Py_None);
return Py_None;
}
#ifdef PERSISTENT
static PyObject *
BTree__p_resolveConflict(BTree *self, PyObject *args)
{
PyObject *s[3], *r;
int i;
UNLESS (PyArg_ParseTuple(args, "OOO", s, s+1, s+2)) return NULL;
/* for each state, detuplefy it twice */
for (i=0; i < 3; i++)
UNLESS (s[i]==Py_None || PyArg_ParseTuple(s[i], "O", s+i)) return NULL;
for (i=0; i < 3; i++)
UNLESS (s[i]==Py_None || PyArg_ParseTuple(s[i], "O", s+i)) return NULL;
for (i=0; i < 3; i++) /* Now make sure detupled thing is a tuple */
UNLESS (s[i]==Py_None || PyTuple_Check(s[i]))
return merge_error(-100, -100, -100, -100);
if (ExtensionClassSubclassInstance_Check(self, &BTreeType))
r = _bucket__p_resolveConflict(OBJECT(&BucketType), s);
else
r = _bucket__p_resolveConflict(OBJECT(&SetType), s);
if (r) ASSIGN(r, Py_BuildValue("((O))", r));
return r;
}
#endif
/*
BTree_findRangeEnd -- Find one end, expressed as a bucket and
position, for a range search. Used by BTree_rangeSearch below.
If low, return bucket and index of the smallest item >= key,
otherwise return bucket and index of the largest item <= key.
Return: 0 -- Not found, 1 -- found, -1 -- error.
*/
static int
BTree_findRangeEnd(BTree *self, PyObject *keyarg, int low,
Bucket **bucket, int *offset) {
int min, max, i=0, cmp, copied=1;
KEY_TYPE key;
COPY_KEY_FROM_ARG(key, keyarg, &copied);
UNLESS (copied) return -1;
/* We don't need to: PER_USE_OR_RETURN(self, -1);
because the caller does. */
UNLESS (self->data && self->len) return 0;
for (min=0, max=self->len, i=max/2; max-min > 1; i=(min+max)/2)
{
cmp=TEST_KEY(self->data[i].key, key);
if (cmp < 0) min=i;
else if (cmp == 0)
{
min=i;
break;
}
else max=i;
}
if (SameType_Check(self, self->data[min].value))
{
self=BTREE(self->data[min].value);
PER_USE_OR_RETURN(self, -1);
i = BTree_findRangeEnd(self, keyarg, low, bucket, offset);
PER_ALLOW_DEACTIVATION(self);
}
else
{
*bucket = BUCKET(self->data[min].value);
if ((i=Bucket_findRangeEnd(*bucket, keyarg, low, offset)))
Py_INCREF(*bucket);
}
return i;
}
static PyObject *
BTree_maxminKey(BTree *self, PyObject *args, int min)
{
PyObject *key=0;
Bucket *bucket = NULL;
int offset, rc;
UNLESS (PyArg_ParseTuple(args, "|O", &key)) return NULL;
PER_USE_OR_RETURN(self, NULL);
UNLESS (self->data && self->len) goto empty;
/* Find the range */
if (key)
{
if ((rc = BTree_findRangeEnd(self, key, min, &bucket, &offset)) <= 0)
{
if (rc < 0) goto err;
goto empty;
}
PER_ALLOW_DEACTIVATION(self);
PER_USE_OR_RETURN(bucket, NULL);
}
else if (min)
{
bucket = self->firstbucket;
Py_INCREF(bucket);
PER_ALLOW_DEACTIVATION(self);
PER_USE_OR_RETURN(bucket, NULL);
offset = 0;
if (offset >= bucket->len)
{
switch (firstBucketOffset(&bucket, &offset))
{
case 0: goto empty;
case -1: goto err;
}
}
}
else
{
bucket = BTree_lastBucket(self);
PER_ALLOW_DEACTIVATION(self);
PER_USE_OR_RETURN(bucket, NULL);
if (bucket->len)
offset = bucket->len - 1;
else
{
switch (lastBucketOffset(&bucket, &offset, self->firstbucket, -1))
{
case 0: goto empty;
case -1: goto err;
}
}
}
COPY_KEY_TO_OBJECT(key, bucket->keys[offset]);
PER_ALLOW_DEACTIVATION(bucket);
Py_DECREF(bucket);
return key;
empty:
PyErr_SetString(PyExc_ValueError, "empty tree");
err:
PER_ALLOW_DEACTIVATION(self);
if (bucket)
{
PER_ALLOW_DEACTIVATION(bucket);
Py_DECREF(bucket);
}
return NULL;
}
static PyObject *
BTree_minKey(BTree *self, PyObject *args)
{
return BTree_maxminKey(self, args, 1);
}
static PyObject *
BTree_maxKey(BTree *self, PyObject *args)
{
return BTree_maxminKey(self, args, 0);
}
/*
** BTree_rangeSearch
**
** Generates a BTreeItems object based on the two indexes passed in,
** being the range between them.
**
*/
static PyObject *
BTree_rangeSearch(BTree *self, PyObject *args, char type)
{
PyObject *f=0, *l=0;
int rc;
Bucket *lowbucket = NULL;
Bucket *highbucket = NULL;
int lowoffset;
int highoffset;
UNLESS (! args || PyArg_ParseTuple(args,"|OO",&f, &l)) return NULL;
PER_USE_OR_RETURN(self, NULL);
UNLESS (self->data && self->len) goto empty;
/* Find the low range */
if (f && f != Py_None)
{
if ((rc = BTree_findRangeEnd(self, f, 1, &lowbucket, &lowoffset)) <= 0)
{
if (rc < 0) goto err;
goto empty;
}
}
else
{
lowbucket = self->firstbucket;
Py_INCREF(lowbucket);
lowoffset = 0;
}
/* Find the high range */
if (l && l != Py_None)
{
if ((rc = BTree_findRangeEnd(self, l, 0, &highbucket, &highoffset)) <= 0)
{
Py_DECREF(lowbucket);
if (rc < 0) goto err;
goto empty;
}
}
else
{
highbucket = BTree_lastBucket(self);
UNLESS (PER_USE(highbucket)) goto err;
highoffset = highbucket->len - 1;
PER_ALLOW_DEACTIVATION(highbucket);
}
PER_ALLOW_DEACTIVATION(self);
f=newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
Py_DECREF(lowbucket);
Py_DECREF(highbucket);
return f;
err:
PER_ALLOW_DEACTIVATION(self);
return NULL;
empty:
PER_ALLOW_DEACTIVATION(self);
return newBTreeItems(type, 0, 0, 0, 0);
}
/*
** BTree_keys
*/
static PyObject *
BTree_keys(BTree *self, PyObject *args)
{
return BTree_rangeSearch(self,args, 'k');
}
/*
** BTree_values
*/
static PyObject *
BTree_values(BTree *self, PyObject *args)
{
return BTree_rangeSearch(self,args,'v');
}
/*
** BTree_items
*/
static PyObject *
BTree_items(BTree *self, PyObject *args)
{
return BTree_rangeSearch(self,args,'i');
}
static PyObject *
BTree_byValue(BTree *self, PyObject *args)
{
PyObject *r=0, *o=0, *item=0, *omin;
VALUE_TYPE min;
VALUE_TYPE v;
int i, l, copied=1;
SetIteration it={0,0};
PER_USE_OR_RETURN(self, NULL);
UNLESS (PyArg_ParseTuple(args, "O", &omin)) return NULL;
COPY_VALUE_FROM_ARG(min, omin, &copied);
UNLESS(copied) return NULL;
UNLESS (r=PyList_New(0)) goto err;
it.set=BTree_rangeSearch(self, NULL, 'i');
UNLESS(it.set) goto err;
if (nextBTreeItems(&it) < 0) goto err;
while (it.position >= 0)
{
if (TEST_VALUE(it.value, min) >= 0)
{
UNLESS (item = PyTuple_New(2)) goto err;
COPY_KEY_TO_OBJECT(o, it.key);
UNLESS (o) goto err;
PyTuple_SET_ITEM(item, 1, o);
COPY_VALUE(v, it.value);
NORMALIZE_VALUE(v, min);
COPY_VALUE_TO_OBJECT(o, v);
DECREF_VALUE(v);
UNLESS (o) goto err;
PyTuple_SET_ITEM(item, 0, o);
if (PyList_Append(r, item) < 0) goto err;
Py_DECREF(item);
item = 0;
}
if (nextBTreeItems(&it) < 0) goto err;
}
item=PyObject_GetAttr(r,sort_str);
UNLESS (item) goto err;
ASSIGN(item, PyObject_CallObject(item, NULL));
UNLESS (item) goto err;
ASSIGN(item, PyObject_GetAttr(r, reverse_str));
UNLESS (item) goto err;
ASSIGN(item, PyObject_CallObject(item, NULL));
UNLESS (item) goto err;
Py_DECREF(item);
PER_ALLOW_DEACTIVATION(self);
return r;
err:
PER_ALLOW_DEACTIVATION(self);
Py_XDECREF(r);
Py_XDECREF(it.set);
Py_XDECREF(item);
return NULL;
}
/*
** BTree_getm
*/
static PyObject *
BTree_getm(BTree *self, PyObject *args)
{
PyObject *key, *d=Py_None, *r;
UNLESS (PyArg_ParseTuple(args, "O|O", &key, &d)) return NULL;
if ((r=_BTree_get(self, key, 0))) return r;
PyErr_Clear();
Py_INCREF(d);
return d;
}
/*
** BTree_has_key
*/
static PyObject *
BTree_has_key(BTree *self, PyObject *args)
{
PyObject *key;
UNLESS (PyArg_ParseTuple(args,"O",&key)) return NULL;
return _BTree_get(self, key, 1);
}
static PyObject *
BTree_addUnique(BTree *self, PyObject *args)
{
int grew;
PyObject *key, *v;
UNLESS (PyArg_ParseTuple(args, "OO", &key, &v)) return NULL;
if ((grew=_BTree_set(self, key, v, 1, 0)) < 0) return NULL;
return PyInt_FromLong(grew);
}
static struct PyMethodDef BTree_methods[] = {
{"__getstate__", (PyCFunction) BTree_getstate, METH_VARARGS,
"__getstate__() -- Return the picklable state of the object"},
{"__setstate__", (PyCFunction) BTree_setstate, METH_VARARGS,
"__setstate__() -- Set the state of the object"},
{"has_key", (PyCFunction) BTree_has_key, METH_VARARGS,
"has_key(key) -- Test whether the bucket contains the given key"},
{"keys", (PyCFunction) BTree_keys, METH_VARARGS,
"keys([min, max]) -- Return the keys"},
{"values", (PyCFunction) BTree_values, METH_VARARGS,
"values([min, max]) -- Return the values"},
{"items", (PyCFunction) BTree_items, METH_VARARGS,
"items([min, max]) -- Return the items"},
{"byValue", (PyCFunction) BTree_byValue, METH_VARARGS,
"byValue(min) -- "
"Return value-keys with values >= min and reverse sorted by values"
},
{"get", (PyCFunction) BTree_getm, METH_VARARGS,
"get(key[,default]) -- Look up a value\n\n"
"Return the default (or None) if the key is not found."
},
{"maxKey", (PyCFunction) BTree_maxKey, METH_VARARGS,
"maxKey([key]) -- Fine the maximum key\n\n"
"If an argument is given, find the maximum <= the argument"},
{"minKey", (PyCFunction) BTree_minKey, METH_VARARGS,
"minKey([key]) -- Fine the minimum key\n\n"
"If an argument is given, find the minimum >= the argument"},
{"clear", (PyCFunction) BTree_clear, METH_VARARGS,
"clear() -- Remove all of the items from the BTree"},
{"insert", (PyCFunction)BTree_addUnique, METH_VARARGS,
"insert(key, value) -- Add an item if the key is not already used.\n\n"
"Return 1 if the item was added, or 0 otherwise"
},
{"update", (PyCFunction) Mapping_update, METH_VARARGS,
"update(collection) -- Add the items from the given collection"},
{"__init__", (PyCFunction) Mapping_update, METH_VARARGS,
"__init__(collection) -- Initialize with items from the given collection"},
#ifdef PERSISTENT
{"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict, METH_VARARGS,
"_p_resolveConflict() -- Reinitialize from a newly created copy"},
{"_p_deactivate", (PyCFunction) BTree__p_deactivate, METH_VARARGS,
"_p_deactivate() -- Reinitialize from a newly created copy"},
#endif
{NULL, NULL} /* sentinel */
};
static void
BTree_dealloc(BTree *self)
{
_BTree_clear(self);
PER_DEL(self);
Py_DECREF(self->ob_type);
PyMem_DEL(self);
}
static int
BTree_length_or_nonzero(BTree *self, int nonzero)
{
int c=0;
Bucket *b, *n;
PER_USE_OR_RETURN(self, -1);
b = self->firstbucket;
Py_XINCREF(b);
PER_ALLOW_DEACTIVATION(self);
while (b != NULL)
{
PER_USE_OR_RETURN(b, -1);
c += b->len;
if (nonzero && c)
{
/* Short-circuit if all we care about is nonempty */
PER_ALLOW_DEACTIVATION(b);
Py_DECREF(b);
return 1;
}
n = b->next;
Py_XINCREF(n);
PER_ALLOW_DEACTIVATION(b);
ASSIGNB(b, n);
}
return c;
}
static int
BTree_length( BTree *self)
{
return BTree_length_or_nonzero(self, 0);
}
static PyMappingMethods BTree_as_mapping = {
(inquiry)BTree_length, /*mp_length*/
(binaryfunc)BTree_get, /*mp_subscript*/
(objobjargproc)BTree_setitem, /*mp_ass_subscript*/
};
static int
BTree_nonzero( BTree *self)
{
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 PyExtensionClass BTreeType = {
PyObject_HEAD_INIT(NULL)
0, /*ob_size*/
PREFIX "BTree", /*tp_name*/
sizeof(BTree), /*tp_basicsize*/
0, /*tp_itemsize*/
/************* methods ********************/
(destructor) BTree_dealloc,/*tp_dealloc*/
(printfunc)0, /*tp_print*/
(getattrfunc)0, /*obsolete tp_getattr*/
(setattrfunc)0, /*obsolete tp_setattr*/
(cmpfunc)0, /*tp_compare*/
(reprfunc)0, /*tp_repr*/
&BTree_as_number_for_nonzero, /*tp_as_number*/
0, /*tp_as_sequence*/
&BTree_as_mapping, /*tp_as_mapping*/
(hashfunc)0, /*tp_hash*/
(ternaryfunc)0, /*tp_call*/
(reprfunc)0, /*tp_str*/
(getattrofunc)0,
0, /*tp_setattro*/
/* Space for future expansion */
0L,0L,
"Mapping type implemented as sorted list of items",
METHOD_CHAIN(BTree_methods),
EXTENSIONCLASS_BASICNEW_FLAG
#ifdef PERSISTENT
| PERSISTENT_TYPE_FLAG
#endif
| EXTENSIONCLASS_NOINSTDICT_FLAG,
};
--- Added File BucketTemplate.c in package Zope2 ---
/*****************************************************************************
Zope Public License (ZPL) Version 1.0
-------------------------------------
Copyright (c) Digital Creations. All rights reserved.
This license has been certified as Open Source(tm).
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions in source code must retain the above copyright
notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions, and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
3. Digital Creations requests that attribution be given to Zope
in any manner possible. Zope includes a "Powered by Zope"
button that is installed by default. While it is not a license
violation to remove this button, it is requested that the
attribution remain. A significant investment has been put
into Zope, and this effort will continue if the Zope community
continues to grow. This is one way to assure that growth.
4. All advertising materials and documentation mentioning
features derived from or use of this software must display
the following acknowledgement:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
In the event that the product being advertised includes an
intact Zope distribution (with copyright and license included)
then this clause is waived.
5. Names associated with Zope or Digital Creations must not be used to
endorse or promote products derived from this software without
prior written permission from Digital Creations.
6. Modified redistributions of any form whatsoever must retain
the following acknowledgment:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
Intact (re-)distributions of any official Zope release do not
require an external acknowledgement.
7. Modifications are encouraged but must be packaged separately as
patches to official Zope releases. Distributions that do not
clearly separate the patches from the original work must be clearly
labeled as unofficial distributions. Modifications which do not
carry the name Zope may be packaged in any form, as long as they
conform to all of the clauses above.
Disclaimer
THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
This software consists of contributions made by Digital Creations and
many individuals on behalf of Digital Creations. Specific
attributions are listed in the accompanying credits file.
****************************************************************************/
/*
** _bucket_get
**
** Get the bucket item with the matching key
**
** Arguments: self The bucket
** key The key to match against
** has_key Just return object "1" if key found, object "0" if not
**
** Returns: object matching object or 0/1 object
*/
static PyObject *
_bucket_get(Bucket *self, PyObject *keyarg, int has_key)
{
int min, max, i, l, cmp, copied=1;
PyObject *r;
KEY_TYPE key;
COPY_KEY_FROM_ARG(key, keyarg, &copied);
UNLESS (copied) return NULL;
PER_USE_OR_RETURN(self, NULL);
for (min=0, max=self->len, i=max/2, l=max; i != l; l=i, i=(min+max)/2)
{
cmp=TEST_KEY(self->keys[i], key);
if (cmp < 0) min=i;
else if (cmp == 0)
{
if (has_key) r=PyInt_FromLong(has_key);
else
{
COPY_VALUE_TO_OBJECT(r, self->values[i]);
}
PER_ALLOW_DEACTIVATION(self);
return r;
}
else max=i;
}
PER_ALLOW_DEACTIVATION(self);
if (has_key) return PyInt_FromLong(0);
PyErr_SetObject(PyExc_KeyError, keyarg);
return NULL;
}
static PyObject *
bucket_getitem(Bucket *self, PyObject *key)
{
return _bucket_get(self, key, 0);
}
static int
Bucket_grow(Bucket *self, int noval)
{
KEY_TYPE *keys;
VALUE_TYPE *values;
if (self->size)
{
UNLESS (keys=PyRealloc(self->keys, sizeof(KEY_TYPE)*self->size*2))
return -1;
UNLESS (noval)
{
UNLESS (values=PyRealloc(self->values,
sizeof(VALUE_TYPE)*self->size*2))
return -1;
self->values=values;
}
self->keys=keys;
self->size*=2;
}
else
{
UNLESS (self->keys=PyMalloc(sizeof(KEY_TYPE)*MIN_BUCKET_ALLOC))
return -1;
UNLESS (noval ||
(self->values=PyMalloc(sizeof(VALUE_TYPE)*MIN_BUCKET_ALLOC))
)
return -1;
self->size=MIN_BUCKET_ALLOC;
}
return 0;
}
/*
** _bucket_set
**
** Assign a value into a bucket
**
** Arguments: self The bucket
** key The key of the object to insert
** v The value of the object to insert
** unique Inserting a unique key
**
** Returns: -1 on error
** 0 on success with a replacement
** 1 on success with a new value (growth)
*/
static int
_bucket_set(Bucket *self, PyObject *keyarg, PyObject *v,
int unique, int noval, int *changed)
{
int min, max, i, l, cmp, copied=1;
KEY_TYPE key;
COPY_KEY_FROM_ARG(key, keyarg, &copied);
UNLESS(copied) return -1;
PER_USE_OR_RETURN(self, -1);
for (min=0, max=l=self->len, i=max/2; i != l; l=i, i=(min+max)/2)
{
if ((cmp=TEST_KEY(self->keys[i], key)) < 0) min=i;
else if (cmp==0)
{
if (v) /* Assign value to key */
{
if (! unique && ! noval && self->values)
{
VALUE_TYPE value;
COPY_VALUE_FROM_ARG(value, v, &copied);
UNLESS(copied) return -1;
#ifdef VALUE_SAME
if (VALUE_SAME(self->values[i], value))
{ /* short-circuit if no change */
PER_ALLOW_DEACTIVATION(self);
return 0;
}
#endif
if (changed) *changed=1;
DECREF_VALUE(self->values[i]);
COPY_VALUE(self->values[i], value);
INCREF_VALUE(self->values[i]);
if (PER_CHANGED(self) < 0) goto err;
}
PER_ALLOW_DEACTIVATION(self);
return 0;
}
else /* There's no value so remove the item */
{
self->len--;
DECREF_KEY(self->keys[i]);
if (i < self->len)
memmove(self->keys+i, self->keys+i+1,
sizeof(KEY_TYPE)*(self->len-i));
if (self->values && ! noval)
{
DECREF_VALUE(self->values[i]);
if (i < self->len)
memmove(self->values+i, self->values+i+1,
sizeof(VALUE_TYPE)*(self->len-i));
}
if (! self->len)
{
self->size=0;
free(self->keys);
self->keys=NULL;
if (self->values)
{
free(self->values);
self->values=NULL;
}
}
if (PER_CHANGED(self) < 0) goto err;
PER_ALLOW_DEACTIVATION(self);
return 1;
}
}
else max=i;
}
if (!v)
{
PyErr_SetObject(PyExc_KeyError, keyarg);
goto err;
}
if (self->len==self->size && Bucket_grow(self, noval) < 0) goto err;
if (max != i) i++;
if (self->len > i)
{
memmove(self->keys+i+1, self->keys+i,
sizeof(KEY_TYPE)*(self->len-i));
UNLESS (noval)
memmove(self->values+i+1, self->values+i,
sizeof(VALUE_TYPE)*(self->len-i));
}
COPY_KEY(self->keys[i], key);
INCREF_KEY(self->keys[i]);
UNLESS (noval)
{
COPY_VALUE_FROM_ARG(self->values[i], v, &copied);
UNLESS(copied) return -1;
INCREF_VALUE(self->values[i]);
}
self->len++;
if (PER_CHANGED(self) < 0) goto err;
PER_ALLOW_DEACTIVATION(self);
return 1;
err:
PER_ALLOW_DEACTIVATION(self);
return -1;
}
/*
** bucket_setitem
**
** wrapper for _bucket_setitem (eliminates +1 return code)
**
** Arguments: self The bucket
** key The key to insert under
** v The value to insert
**
** Returns 0 on success
** -1 on failure
*/
static int
bucket_setitem(Bucket *self, PyObject *key, PyObject *v)
{
if (_bucket_set(self, key, v, 0, 0, 0) < 0) return -1;
return 0;
}
static PyObject *
Mapping_update(PyObject *self, PyObject *args)
{
PyObject *seq=0, *o, *t, *v, *tb, *k;
int i, n=0, ind;
UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;
if (seq)
{
if (PySequence_Check(seq))
{
Py_INCREF(seq);
}
else
{
seq=PyObject_GetAttr(seq, items_str);
UNLESS(seq) return NULL;
ASSIGN(seq, PyObject_CallObject(seq, NULL));
UNLESS(seq) return NULL;
}
for (i=0; ; i++)
{
UNLESS (o=PySequence_GetItem(seq, i))
{
PyErr_Fetch(&t, &v, &tb);
if (t != PyExc_IndexError)
{
PyErr_Restore(t, v, tb);
goto err;
}
Py_XDECREF(t);
Py_XDECREF(v);
Py_XDECREF(tb);
break;
}
ind=PyArg_ParseTuple(o, "OO;items must be 2-item tuples", &k, &v);
if (ind)
ind = PyObject_SetItem(self, k, v);
else
ind=-1;
Py_DECREF(o);
if (ind < 0) goto err;
}
}
Py_INCREF(Py_None);
return Py_None;
err:
Py_DECREF(seq);
return NULL;
}
/*
** bucket_split
**
** Splits one bucket into two
**
** Arguments: self The bucket
** index the index of the key to split at (O.O.B use midpoint)
** next the new bucket to split into
**
** Returns: 0 on success
** -1 on failure
*/
static int
bucket_split(Bucket *self, int index, Bucket *next)
{
int next_size;
ASSERT(self->len > 1, "split of empty bucket", -1);
if (index < 0 || index >= self->len) index=self->len/2;
next_size=self->len-index;
UNLESS (next->keys=PyMalloc(sizeof(KEY_TYPE)*next_size)) return -1;
memcpy(next->keys, self->keys+index, sizeof(KEY_TYPE)*next_size);
if (self->values)
{
UNLESS (next->values=PyMalloc(sizeof(VALUE_TYPE)*next_size))
return -1;
memcpy(next->values, self->values+index, sizeof(VALUE_TYPE)*next_size);
}
next->size = next_size;
next->len= next_size;
self->len=index;
next->next = self->next;
Py_INCREF(next);
self->next = next;
return 0;
}
static int
Bucket_nextBucket(Bucket *self, Bucket **r)
{
PER_USE_OR_RETURN(self, -1);
*r=self->next;
Py_XINCREF(*r);
PER_ALLOW_DEACTIVATION(self);
return 0;
}
static int
Bucket_deleteNextBucket(Bucket *self)
{
PER_USE_OR_RETURN(self, -1);
if (self->next)
{
Bucket *n;
if (Bucket_nextBucket(self->next, &n) < 0) goto err;
ASSIGNB(self->next, n);
PER_CHANGED(self);
}
PER_ALLOW_DEACTIVATION(self);
return 0;
err:
PER_ALLOW_DEACTIVATION(self);
return -1;
}
/*
Bucket_findRangeEnd -- Find the index of a range endpoint
(possibly) contained in a bucket.
Arguments: self The bucket
key the key to match against
low end flag
offset The output offset
If low, return bucket and index of the smallest item >= key,
otherwise return bucket and index of the largest item <= key.
Return: 0 -- Not found, 1 -- found, -1 -- error.
*/
static int
Bucket_findRangeEnd(Bucket *self, PyObject *keyarg, int low, int *offset)
{
int min, max, i, l, cmp, copied=1;
Bucket *chase;
Bucket *release = NULL;
KEY_TYPE key;
COPY_KEY_FROM_ARG(key, keyarg, &copied);
UNLESS (copied) return -1;
PER_USE_OR_RETURN(self, -1);
for (min=0, max=self->len, i=max/2, l=max; i != l; l=i, i=(min+max)/2)
{
cmp=TEST_KEY(self->keys[i], key);
if (cmp < 0)
min=i;
else if (cmp == 0)
{
PER_ALLOW_DEACTIVATION(self);
*offset=i;
return 1;
}
else
max=i;
}
/* OK, no matches, pick max or min, depending on whether
we want an upper or low end.
*/
if (low)
{
if (max == self->len) i=0;
else
{
i=1;
*offset=max;
}
}
else
{
if (max == 0) i=0;
else
{
i=1;
*offset=min;
}
}
PER_ALLOW_DEACTIVATION(self);
return i;
}
static PyObject *
Bucket_maxminKey(Bucket *self, PyObject *args, int min)
{
PyObject *key=0;
int rc, offset;
if (args && ! PyArg_ParseTuple(args, "|O", &key)) return NULL;
PER_USE_OR_RETURN(self, NULL);
UNLESS (self->len) goto empty;
/* Find the low range */
if (key)
{
if ((rc = Bucket_findRangeEnd(self, key, min, &offset)) <= 0)
{
if (rc < 0) return NULL;
goto empty;
}
}
else if (min) offset = 0;
else offset = self->len -1;
COPY_KEY_TO_OBJECT(key, self->keys[offset]);
PER_ALLOW_DEACTIVATION(self);
return key;
empty:
PyErr_SetString(PyExc_ValueError, "empty bucket");
err:
PER_ALLOW_DEACTIVATION(self);
return NULL;
}
static PyObject *
Bucket_minKey(Bucket *self, PyObject *args)
{
return Bucket_maxminKey(self, args, 1);
}
static PyObject *
Bucket_maxKey(Bucket *self, PyObject *args)
{
return Bucket_maxminKey(self, args, 0);
}
static int
Bucket_rangeSearch(Bucket *self, PyObject *args, int *low, int *high)
{
PyObject *f=0, *l=0;
int rc;
if (args && ! PyArg_ParseTuple(args,"|OO",&f, &l)) return -1;
UNLESS (self->len) goto empty;
/* Find the low range */
if (f && f != Py_None)
{
UNLESS (rc = Bucket_findRangeEnd(self, f, 1, low))
{
if (rc < 0) return -1;
goto empty;
}
}
else *low = 0;
/* Find the high range */
if (l && l != Py_None)
{
UNLESS (rc = Bucket_findRangeEnd(self, l, 0, high))
{
if (rc < 0) return -1;
goto empty;
}
}
else *high=self->len - 1;
return 0;
empty:
*low=0;
*high=-1;
return 0;
}
/*
** bucket_keys
**
** Generate a list of all keys in the bucket
**
** Arguments: self The Bucket
** args (unused)
**
** Returns: list of bucket keys
*/
static PyObject *
bucket_keys(Bucket *self, PyObject *args)
{
PyObject *r=0, *key;
int i, low, high;
PER_USE_OR_RETURN(self, NULL);
if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;
UNLESS (r=PyList_New(high-low+1)) goto err;
for (i=low; i <= high; i++)
{
COPY_KEY_TO_OBJECT(key, self->keys[i]);
if (PyList_SetItem(r, i, key) < 0) goto err;
}
PER_ALLOW_DEACTIVATION(self);
return r;
err:
PER_ALLOW_DEACTIVATION(self);
Py_XDECREF(r);
return NULL;
}
/*
** bucket_values
**
** Generate a list of all values in the bucket
**
** Arguments: self The Bucket
** args (unused)
**
** Returns list of values
*/
static PyObject *
bucket_values(Bucket *self, PyObject *args)
{
PyObject *r=0, *v;
int i, low, high;
PER_USE_OR_RETURN(self, NULL);
if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;
UNLESS (r=PyList_New(high-low+1)) goto err;
for (i=low; i <= high; i++)
{
COPY_KEY_TO_OBJECT(v, self->keys[i]);
UNLESS (v) goto err;
if (PyList_SetItem(r, i, v) < 0) goto err;
}
PER_ALLOW_DEACTIVATION(self);
return r;
err:
PER_ALLOW_DEACTIVATION(self);
Py_XDECREF(r);
return NULL;
}
/*
** bucket_items
**
** Returns a list of all items in a bucket
**
** Arguments: self The Bucket
** args (unused)
**
** Returns: list of all items in the bucket
*/
static PyObject *
bucket_items(Bucket *self, PyObject *args)
{
PyObject *r=0, *o=0, *item=0;
int i, low, high;
PER_USE_OR_RETURN(self, NULL);
if (Bucket_rangeSearch(self, args, &low, &high) < 0) goto err;
UNLESS (r=PyList_New(high-low+1)) goto err;
for (i=low; i <= high; i++)
{
UNLESS (item = PyTuple_New(2)) goto err;
COPY_KEY_TO_OBJECT(o, self->keys[i]);
UNLESS (o) goto err;
PyTuple_SET_ITEM(item, 0, o);
COPY_VALUE_TO_OBJECT(o, self->values[i]);
UNLESS (o) goto err;
PyTuple_SET_ITEM(item, 1, o);
if (PyList_SetItem(r, i, item) < 0) goto err;
item = 0;
}
PER_ALLOW_DEACTIVATION(self);
return r;
err:
PER_ALLOW_DEACTIVATION(self);
Py_XDECREF(r);
Py_XDECREF(item);
return NULL;
}
static PyObject *
bucket_byValue(Bucket *self, PyObject *args)
{
PyObject *r=0, *o=0, *item=0, *omin;
VALUE_TYPE min;
VALUE_TYPE v;
int i, l, copied=1;
PER_USE_OR_RETURN(self, NULL);
UNLESS (PyArg_ParseTuple(args, "O", &omin)) return NULL;
COPY_VALUE_FROM_ARG(min, omin, &copied);
UNLESS(copied) return NULL;
for (i=0, l=0; i < self->len; i++)
if (TEST_VALUE(self->values[i], min) >= 0)
l++;
UNLESS (r=PyList_New(l)) goto err;
for (i=0, l=0; i < self->len; i++)
{
if (TEST_VALUE(self->values[i], min) < 0) continue;
UNLESS (item = PyTuple_New(2)) goto err;
COPY_KEY_TO_OBJECT(o, self->keys[i]);
UNLESS (o) goto err;
PyTuple_SET_ITEM(item, 1, o);
COPY_VALUE(v, self->values[i]);
NORMALIZE_VALUE(v, min);
COPY_VALUE_TO_OBJECT(o, v);
DECREF_VALUE(v);
UNLESS (o) goto err;
PyTuple_SET_ITEM(item, 0, o);
if (PyList_SetItem(r, l, item) < 0) goto err;
l++;
item = 0;
}
item=PyObject_GetAttr(r,sort_str);
UNLESS (item) goto err;
ASSIGN(item, PyObject_CallObject(item, NULL));
UNLESS (item) goto err;
ASSIGN(item, PyObject_GetAttr(r, reverse_str));
UNLESS (item) goto err;
ASSIGN(item, PyObject_CallObject(item, NULL));
UNLESS (item) goto err;
Py_DECREF(item);
PER_ALLOW_DEACTIVATION(self);
return r;
err:
PER_ALLOW_DEACTIVATION(self);
Py_XDECREF(r);
Py_XDECREF(item);
return NULL;
}
static int
_bucket_clear(Bucket *self)
{
int i;
if (self->next)
{
Py_DECREF(self->next);
self->next=0;
}
for (i=self->len; --i >= 0; )
{
DECREF_KEY(self->keys[i]);
if (self->values) DECREF_VALUE(self->values[i]);
}
self->len=0;
if (self->values)
{
free(self->values);
self->values=0;
}
if (self->keys)
{
free(self->keys);
self->keys=0;
}
self->size=0;
return 0;
}
#ifdef PERSISTENT
static PyObject *
bucket__p_deactivate(Bucket *self, PyObject *args)
{
if (self->state==cPersistent_UPTODATE_STATE && self->jar)
{
if (_bucket_clear(self) < 0) return NULL;
self->state=cPersistent_GHOST_STATE;
}
Py_INCREF(Py_None);
return Py_None;
}
#endif
static PyObject *
bucket_clear(Bucket *self, PyObject *args)
{
int i;
PER_USE_OR_RETURN(self, NULL);
if (self->len)
{
if (_bucket_clear(self) < 0) return NULL;
if (PER_CHANGED(self) < 0) goto err;
}
PER_ALLOW_DEACTIVATION(self);
Py_INCREF(Py_None);
return Py_None;
err:
PER_ALLOW_DEACTIVATION(self);
return NULL;
}
static PyObject *
bucket_getstate(Bucket *self, PyObject *args)
{
PyObject *o=0, *items=0;
int i, len, l;
if (args && ! PyArg_ParseTuple(args, "")) return NULL;
PER_USE_OR_RETURN(self, NULL);
len=self->len;
if (self->values)
{ /* Bucket */
UNLESS (items=PyTuple_New(len*2)) goto err;
for (i=0, l=0; i < len; i++)
{
COPY_KEY_TO_OBJECT(o, self->keys[i]);
UNLESS (o) goto err;
PyTuple_SET_ITEM(items, l, o);
l++;
COPY_VALUE_TO_OBJECT(o, self->values[i]);
UNLESS (o) goto err;
PyTuple_SET_ITEM(items, l, o);
l++;
}
}
else
{ /* Set */
UNLESS (items=PyTuple_New(len)) goto err;
for (i=0; i < len; i++)
{
COPY_KEY_TO_OBJECT(o, self->keys[i]);
UNLESS (o) goto err;
PyTuple_SET_ITEM(items, i, o);
}
}
if (self->next)
ASSIGN(items, Py_BuildValue("OO", items, self->next));
else
ASSIGN(items, Py_BuildValue("(O)", items));
PER_ALLOW_DEACTIVATION(self);
return items;
err:
PER_ALLOW_DEACTIVATION(self);
Py_XDECREF(items);
return NULL;
}
static int
_bucket_setstate(Bucket *self, PyObject *args)
{
PyObject *k, *v, *r, *items;
Bucket *next=0;
int i, l, len, copied=1;
KEY_TYPE *keys;
VALUE_TYPE *values;
UNLESS (PyArg_ParseTuple(args, "O|O", &items, &next))
return -1;
if ((len=PyTuple_Size(items)) < 0) return -1;
len /= 2;
for (i=self->len; --i >= 0; )
{
DECREF_KEY(self->keys[i]);
DECREF_VALUE(self->values[i]);
}
self->len=0;
if (self->next)
{
Py_DECREF(self->next);
self->next=0;
}
if (len > self->size)
{
UNLESS (keys=PyRealloc(self->keys, sizeof(KEY_TYPE)*len))
return -1;
UNLESS (values=PyRealloc(self->values, sizeof(KEY_TYPE)*len))
return -1;
self->keys=keys;
self->values=values;
self->size=len;
}
for (i=0, l=0; i<len; i++)
{
k=PyTuple_GET_ITEM(items, l);
l++;
v=PyTuple_GET_ITEM(items, l);
l++;
COPY_KEY_FROM_ARG(self->keys[i], k, &copied);
UNLESS (copied) return -1;
COPY_VALUE_FROM_ARG(self->values[i], v, &copied);
UNLESS (copied) return -1;
INCREF_KEY(self->keys[i]);
INCREF_VALUE(self->values[i]);
}
self->len=len;
if (next)
{
self->next=next;
Py_INCREF(next);
}
PER_ALLOW_DEACTIVATION(self);
return 0;
}
static PyObject *
bucket_setstate(Bucket *self, PyObject *args)
{
int r;
UNLESS (PyArg_ParseTuple(args, "O", &args)) return NULL;
PER_PREVENT_DEACTIVATION(self);
r=_bucket_setstate(self, args);
PER_ALLOW_DEACTIVATION(self);
if (r < 0) return NULL;
Py_INCREF(Py_None);
return Py_None;
}
/*
** bucket_has_key
**
*/
static PyObject *
bucket_has_key(Bucket *self, PyObject *args)
{
PyObject *key;
UNLESS (PyArg_ParseTuple(args,"O",&key)) return NULL;
return _bucket_get(self, key, 1);
}
/*
** bucket_getm
**
*/
static PyObject *
bucket_getm(Bucket *self, PyObject *args)
{
PyObject *key, *d=Py_None, *r;
UNLESS (PyArg_ParseTuple(args, "O|O", &key, &d)) return NULL;
if ((r=_bucket_get(self, key, 0))) return r;
PyErr_Clear();
Py_INCREF(d);
return d;
}
#ifdef PERSISTENT
static PyObject *merge_error(int p1, int p2, int p3, int reason);
static PyObject *bucket_merge(Bucket *s1, Bucket *s2, Bucket *s3);
static PyObject *
_bucket__p_resolveConflict(PyObject *ob_type, PyObject *s[3])
{
PyObject *r=0, *a;
Bucket *b[3];
int i;
for (i=0; i < 3; i++)
{
if (b[i]=(Bucket*)PyObject_CallObject(OBJECT(ob_type), NULL))
{
if (s[i] == Py_None) /* None is equivalent to empty, for BTrees */
continue;
ASSIGN(r, PyObject_GetAttr(OBJECT(b[i]), __setstate___str));
if (a=PyTuple_New(1))
{
if (r)
{
PyTuple_SET_ITEM(a, 0, s[i]);
Py_INCREF(s[i]);
ASSIGN(r, PyObject_CallObject(r, a));
}
Py_DECREF(a);
if (r) continue;
}
}
Py_XDECREF(r);
while (--i >= 0)
{
Py_DECREF(b[i]);
}
return NULL;
}
Py_DECREF(r);
r=NULL;
if (b[0]->next != b[1]->next || b[0]->next != b[2]->next)
{
merge_error(-1, -1, -1, -1);
goto err;
}
r=bucket_merge(b[0], b[1], b[2]);
err:
Py_DECREF(b[0]);
Py_DECREF(b[1]);
Py_DECREF(b[2]);
return r;
}
static PyObject *
bucket__p_resolveConflict(Bucket *self, PyObject *args)
{
PyObject *s[3];
UNLESS(PyArg_ParseTuple(args, "OOO", &s[0], &s[1], &s[2])) return NULL;
return _bucket__p_resolveConflict(OBJECT(self->ob_type), s);
}
#endif
static struct PyMethodDef Bucket_methods[] = {
{"__getstate__", (PyCFunction) bucket_getstate, METH_VARARGS,
"__getstate__() -- Return the picklable state of the object"},
{"__setstate__", (PyCFunction) bucket_setstate, METH_VARARGS,
"__setstate__() -- Set the state of the object"},
{"keys", (PyCFunction) bucket_keys, METH_VARARGS,
"keys([min, max]) -- Return the keys"},
{"has_key", (PyCFunction) bucket_has_key, METH_VARARGS,
"has_key(key) -- Test whether the bucket contains the given key"},
{"clear", (PyCFunction) bucket_clear, METH_VARARGS,
"clear() -- Remove all of the items from the bucket"},
{"update", (PyCFunction) Mapping_update, METH_VARARGS,
"update(collection) -- Add the items from the given collection"},
{"__init__", (PyCFunction) Mapping_update, METH_VARARGS,
"__init__(collection) -- Initialize with items from the given collection"},
{"maxKey", (PyCFunction) Bucket_maxKey, METH_VARARGS,
"maxKey([key]) -- 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"},
{"values", (PyCFunction) bucket_values, METH_VARARGS,
"values([min, max]) -- Return the values"},
{"items", (PyCFunction) bucket_items, METH_VARARGS,
"items([min, max])) -- Return the items"},
{"byValue", (PyCFunction) bucket_byValue, METH_VARARGS,
"byValue(min) -- "
"Return value-keys with values >= min and reverse sorted by values"
},
{"get", (PyCFunction) bucket_getm, METH_VARARGS,
"get(key[,default]) -- Look up a value\n\n"
"Return the default (or None) if the key is not found."
},
#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
{NULL, NULL} /* sentinel */
};
static void
Bucket_dealloc(Bucket *self)
{
int i;
_bucket_clear(self);
PER_DEL(self);
Py_DECREF(self->ob_type);
PyMem_DEL(self);
}
/* Code to access Bucket objects as mappings */
static int
Bucket_length( Bucket *self)
{
int r;
PER_USE_OR_RETURN(self, -1);
r=self->len;
PER_ALLOW_DEACTIVATION(self);
return r;
}
static PyMappingMethods Bucket_as_mapping = {
(inquiry)Bucket_length, /*mp_length*/
(binaryfunc)bucket_getitem, /*mp_subscript*/
(objobjargproc)bucket_setitem, /*mp_ass_subscript*/
};
static PyObject *
bucket_repr(Bucket *self)
{
static PyObject *format;
PyObject *r, *t;
UNLESS (format) UNLESS (format=PyString_FromString(PREFIX "Bucket(%s)"))
return NULL;
UNLESS (t=PyTuple_New(1)) return NULL;
UNLESS (r=bucket_items(self,NULL)) goto err;
PyTuple_SET_ITEM(t,0,r);
r=t;
ASSIGN(r,PyString_Format(format,r));
return r;
err:
Py_DECREF(t);
return NULL;
}
static PyExtensionClass BucketType = {
PyObject_HEAD_INIT(NULL)
0, /*ob_size*/
PREFIX "Bucket", /*tp_name*/
sizeof(Bucket), /*tp_basicsize*/
0, /*tp_itemsize*/
/*********** methods ***********************/
(destructor) Bucket_dealloc, /*tp_dealloc*/
(printfunc)0, /*tp_print*/
(getattrfunc)0, /*obsolete tp_getattr*/
(setattrfunc)0, /*obsolete tp_setattr*/
(cmpfunc)0, /*tp_compare*/
(reprfunc) bucket_repr, /*tp_repr*/
0, /*tp_as_number*/
0, /*tp_as_sequence*/
&Bucket_as_mapping, /*tp_as_mapping*/
(hashfunc)0, /*tp_hash*/
(ternaryfunc)0, /*tp_call*/
(reprfunc)0, /*tp_str*/
(getattrofunc)0, /*tp_getattro*/
0, /*tp_setattro*/
/* Space for future expansion */
0L,0L,
"Mapping type implemented as sorted list of items",
METHOD_CHAIN(Bucket_methods),
EXTENSIONCLASS_BASICNEW_FLAG
#ifdef PERSISTENT
| PERSISTENT_TYPE_FLAG
#endif
| EXTENSIONCLASS_NOINSTDICT_FLAG,
};
static int
nextBucket(SetIteration *i)
{
UNLESS(PER_USE(BUCKET(i->set))) return -1;
if (i->position >= 0)
{
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;
}
PER_ALLOW_DEACTIVATION(BUCKET(i->set));
return 0;
}
--- Added File IIBTree.c in package Zope2 ---
/* Setup template macros */
#define PERSISTENT
#define PREFIX "II"
#define INITMODULE initIIBTree
#define DEFAULT_MAX_BUCKET_SIZE 120
#define DEFAULT_MAX_BTREE_SIZE 500
#include "intkeymacros.h"
#include "intvaluemacros.h"
#include "cPersistence.h"
#include "BTree/intSet.h"
#include "BTreeModuleTemplate.c"
--- Added File IOBTree.c in package Zope2 ---
#define PERSISTENT
#define PREFIX "IO"
#define DEFAULT_MAX_BUCKET_SIZE 60
#define DEFAULT_MAX_BTREE_SIZE 500
#define INITMODULE initIOBTree
#include "intkeymacros.h"
#include "objectvaluemacros.h"
#include "cPersistence.h"
#include "BTree/intSet.h"
#include "BTreeModuleTemplate.c"
--- Added File Interfaces.py in package Zope2 ---
##############################################################################
#
# Zope Public License (ZPL) Version 1.0
# -------------------------------------
#
# Copyright (c) Digital Creations. All rights reserved.
#
# This license has been certified as Open Source(tm).
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
#
# 1. Redistributions in source code must retain the above copyright
# notice, this list of conditions, and the following disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright
# notice, this list of conditions, and the following disclaimer in
# the documentation and/or other materials provided with the
# distribution.
#
# 3. Digital Creations requests that attribution be given to Zope
# in any manner possible. Zope includes a "Powered by Zope"
# button that is installed by default. While it is not a license
# violation to remove this button, it is requested that the
# attribution remain. A significant investment has been put
# into Zope, and this effort will continue if the Zope community
# continues to grow. This is one way to assure that growth.
#
# 4. All advertising materials and documentation mentioning
# features derived from or use of this software must display
# the following acknowledgement:
#
# "This product includes software developed by Digital Creations
# for use in the Z Object Publishing Environment
# (http://www.zope.org/)."
#
# In the event that the product being advertised includes an
# intact Zope distribution (with copyright and license included)
# then this clause is waived.
#
# 5. Names associated with Zope or Digital Creations must not be used to
# endorse or promote products derived from this software without
# prior written permission from Digital Creations.
#
# 6. Modified redistributions of any form whatsoever must retain
# the following acknowledgment:
#
# "This product includes software developed by Digital Creations
# for use in the Z Object Publishing Environment
# (http://www.zope.org/)."
#
# Intact (re-)distributions of any official Zope release do not
# require an external acknowledgement.
#
# 7. Modifications are encouraged but must be packaged separately as
# patches to official Zope releases. Distributions that do not
# clearly separate the patches from the original work must be clearly
# labeled as unofficial distributions. Modifications which do not
# carry the name Zope may be packaged in any form, as long as they
# conform to all of the clauses above.
#
#
# Disclaimer
#
# THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
# EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGE.
#
#
# This software consists of contributions made by Digital Creations and
# many individuals on behalf of Digital Creations. Specific
# attributions are listed in the accompanying credits file.
#
##############################################################################
import OOBTree, Interface
class ICollection(Interface.Base):
def clear():
"""Remove all of the items from the collection"""
def __nonzero__():
"""Check if the collection is non-empty.
Return a true value if the collection is non-empty and a
false otherwise.
"""
class ISized(ICollection):
def __len__():
"""Return the number of items in the set"""
class IReadSequence(Interface.Base):
def __getitem__(index):
"""Return an item for a given index."""
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, ISized):
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, ISized):
def __getitem__(key):
"""Get the value for the given key
Raise a key error if the key if not in the collection.
"""
def get(key, default=None):
"""Get the value for the given key
Raise a key error if the key if not in the collection and no
default is specified.
Return the default if specified and the key is not in the
collection.
"""
def __setitem__(key, value):
"""Set the value for the given key"""
def __delitem__(key):
"""delete the value for the given key
Raise a key error if the key if not in the collection."""
def update(collection):
"""Add the items from the given collection object to the collection
The input collection must be a sequence of key-value tuples,
or an object with an 'items' method that returns a sequence of
key-value tuples.
"""
def values(min=None, max=None):
"""Return a IReadSequence containing the values in the collection
The type of the IReadSequence is not specified. It could be a
list or a tuple or some other type.
If a min is specified, then output is constrained to
items having keys greater than or equal to the given min.
A min value of None is ignored.
If a max is specified, then output is constrained to
items having keys less than or equal to the given min.
A max value of None is ignored.
"""
def items(min=None, max=None):
"""Return a IReadSequence containing the items in the collection
An item is a key-value tuple.
The type of the IReadSequence is not specified. It could be a
list or a tuple or some other type.
If a min is specified, then output is constrained to
items having keys greater than or equal to the given min.
A min value of None is ignored.
If a max is specified, then output is constrained to
items having keys less than or equal to the given min.
A max value of None is ignored.
"""
def byValue(minValue):
"""Return a sequence of value-key pairs, sorted by value
Values < min are ommitted and other values are "normalized" by
the minimum value. This normalization may be a noop, but, for
integer values, the normalization is division.
"""
class IBTree(IDictionaryIsh):
def insert(key, value):
"""Insert a key and value into the collection.
If the key was already in the collection, then there is no
change and 0 is returned.
If the key was not already in the collection, then the item is
added and 1 is returned.
This method is here to allow one to generate random keys and
to insert and test whether the key was there in one operation.
A standard idiom for generating new keys will be::
key=generate_key()
while not t.insert(key, value):
key=generate_key()
"""
class IMerge(Interfaces.Base):
"""Object with methods for merging sets, buckets, and trees.
These methods are supplied in modules that define collection
classes with particular key and value types. The operations apply
only to collections from the same module. For example, the
IIBTree.union can only be used with IIBTree.IIBTree,
IIBTree.IIBucket, IIBTree.IISet, and IIBTree.IITreeSet.
The implementing module has a value type. The IOBTree and OOBTree
modules have object value type. The IIBTree and OIBTree modules
have integer value tyoes. Other modules may be defined in the
future that have other value types.
The individual types are classified into set (Set and TreeSet) and
mapping (Bucket and BTree) types.
"""
def difference(c1, c2):
"""Return the keys or items in c1 for which there is no key in
c2.
If c1 is None, then None is returned. If c2 is none, then c1
is returned.
"""
def union(c1, c2):
"""Compute the Union of c1 and c2.
If c1 is None, then c2 is returned, otherwise, if c2 is None,
then c1 is returned.
The output is a Set containing keys from the input
collections.
"""
def intersection(c1, c2):
"""Compute the Union of c1 and c2.
If c1 is None, then c2 is returned, otherwise, if c2 is None,
then c1 is returned.
The output is a Set containing matching keys from the input
collections.
"""
class IIMerge(IMerge):
"""Merge collections with integer value type.
A primary intent is to support operations with no or integer
values, which are used as "scores" to rate indiviual keys. That
is, in this context, a BTree or Bucket is viewed as a set with
scored keys, using integer scores.
"""
def weightedUnion(c1, c2, weight1=1, weight2=1):
"""Compute the weighted Union of c1 and c2.
If c1 and c2 are None, the output is 0 and None
if c1 is None and c2 is not None, the output is weight2 and
c2.
if c1 is not None and c2 not None, the output is weight1 and
c1.
If c1 and c2 are not None, the output is 1 and a Bucket
such that the output values are::
v1*weight1 + v2*weight2
where:
v1 is 0 if the key was not in c1. Otherwise, v1 is 1, if
c1 is a set, or the value from c1.
v2 is 0 if the key was not in c2. Otherwise, v2 is 2, if
c2 is a set, or the value from c2.
Note that c1 and c2 must be collections. None may not be
passed as one of the collections.
"""
def weightedIntersection(c1, c2, weight1=1, weight2=1):
"""Compute the weighted intersection of c1 and c2.
If c1 and c2 are None, the output is None, None.
if c1 is None and c2 is not None, the output is weight2 and
c2.
if c1 is not None and c2 not None, the output is weight1 and
c1.
If c1 and c2 are sets, the output is the sum of the weights
and the (unweighted) intersection of the sets.
If c1 and c2 are not None and not both sets, the output is 1
and a Bucket such that the output values are::
v1*weight1 + v2*weight2
where:
v1 is 0 if the key was not in c1. Otherwise, v1 is 1, if
c1 is a set, or the value from c1.
v2 is 0 if the key was not in c2. Otherwise, v2 is 2, if
c2 is a set, or the value from c2.
Note that c1 and c2 must be collections. None may not be
passed as one of the collections.
"""
###############################################################
# IMPORTANT NOTE
#
# Getting the length of a BTree, TreeSet, or output of keys,
# values, or items of same is expensive. If you need to get the
# length, you need to maintain this separately.
#
# Eventually, I need to express this through the interfaces.
#
################################################################
Interface.assertTypeImplements(OOBTree.OOSet, ISet)
Interface.assertTypeImplements(OOBTree.OOTreeSet, ITreeSet)
Interface.assertTypeImplements(OOBTree.OOBucket, IDictionaryIsh)
Interface.assertTypeImplements(OOBTree.OOBTree, IBTree)
--- Added File Length.py in package Zope2 ---
##############################################################################
#
# Zope Public License (ZPL) Version 1.0
# -------------------------------------
#
# Copyright (c) Digital Creations. All rights reserved.
#
# This license has been certified as Open Source(tm).
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
#
# 1. Redistributions in source code must retain the above copyright
# notice, this list of conditions, and the following disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright
# notice, this list of conditions, and the following disclaimer in
# the documentation and/or other materials provided with the
# distribution.
#
# 3. Digital Creations requests that attribution be given to Zope
# in any manner possible. Zope includes a "Powered by Zope"
# button that is installed by default. While it is not a license
# violation to remove this button, it is requested that the
# attribution remain. A significant investment has been put
# into Zope, and this effort will continue if the Zope community
# continues to grow. This is one way to assure that growth.
#
# 4. All advertising materials and documentation mentioning
# features derived from or use of this software must display
# the following acknowledgement:
#
# "This product includes software developed by Digital Creations
# for use in the Z Object Publishing Environment
# (http://www.zope.org/)."
#
# In the event that the product being advertised includes an
# intact Zope distribution (with copyright and license included)
# then this clause is waived.
#
# 5. Names associated with Zope or Digital Creations must not be used to
# endorse or promote products derived from this software without
# prior written permission from Digital Creations.
#
# 6. Modified redistributions of any form whatsoever must retain
# the following acknowledgment:
#
# "This product includes software developed by Digital Creations
# for use in the Z Object Publishing Environment
# (http://www.zope.org/)."
#
# Intact (re-)distributions of any official Zope release do not
# require an external acknowledgement.
#
# 7. Modifications are encouraged but must be packaged separately as
# patches to official Zope releases. Distributions that do not
# clearly separate the patches from the original work must be clearly
# labeled as unofficial distributions. Modifications which do not
# carry the name Zope may be packaged in any form, as long as they
# conform to all of the clauses above.
#
#
# Disclaimer
#
# THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
# EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGE.
#
#
# This software consists of contributions made by Digital Creations and
# many individuals on behalf of Digital Creations. Specific
# attributions are listed in the accompanying credits file.
#
##############################################################################
import Persistence
class Length(Persistence.Persistent):
"""BTree lengths aqre 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 MergeTemplate.c in package Zope2 ---
/*****************************************************************************
Zope Public License (ZPL) Version 1.0
-------------------------------------
Copyright (c) Digital Creations. All rights reserved.
This license has been certified as Open Source(tm).
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions in source code must retain the above copyright
notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions, and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
3. Digital Creations requests that attribution be given to Zope
in any manner possible. Zope includes a "Powered by Zope"
button that is installed by default. While it is not a license
violation to remove this button, it is requested that the
attribution remain. A significant investment has been put
into Zope, and this effort will continue if the Zope community
continues to grow. This is one way to assure that growth.
4. All advertising materials and documentation mentioning
features derived from or use of this software must display
the following acknowledgement:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
In the event that the product being advertised includes an
intact Zope distribution (with copyright and license included)
then this clause is waived.
5. Names associated with Zope or Digital Creations must not be used to
endorse or promote products derived from this software without
prior written permission from Digital Creations.
6. Modified redistributions of any form whatsoever must retain
the following acknowledgment:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
Intact (re-)distributions of any official Zope release do not
require an external acknowledgement.
7. Modifications are encouraged but must be packaged separately as
patches to official Zope releases. Distributions that do not
clearly separate the patches from the original work must be clearly
labeled as unofficial distributions. Modifications which do not
carry the name Zope may be packaged in any form, as long as they
conform to all of the clauses above.
Disclaimer
THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
This software consists of contributions made by Digital Creations and
many individuals on behalf of Digital Creations. Specific
attributions are listed in the accompanying credits file.
****************************************************************************/
/****************************************************************************
Set operations
****************************************************************************/
static int
merge_output(Bucket *r, SetIteration *i, int mapping)
{
if(r->len >= r->size && Bucket_grow(r, ! 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;
PyErr_SetObject(PyExc_ValueError, 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}, it;
int cmp12, cmp13, cmp23, mapping=0, set;
if (initSetIteration(&i1, OBJECT(s1), 0, &mapping) < 0) return NULL;
if (initSetIteration(&i2, OBJECT(s2), 0, &mapping) < 0) return NULL;
if (initSetIteration(&i3, OBJECT(s3), 0, &mapping) < 0) return NULL;
set = ! mapping;
if (mapping)
{
UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&BucketType), NULL)))
goto err;
}
else
{
UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&SetType), NULL)))
goto err;
}
if (i1.next(&i1) < 0) return NULL;
if (i2.next(&i2) < 0) return NULL;
if (i3.next(&i3) < 0) return NULL;
while (i1.position >= 0 && i2.position >= 0 && i3.position >= 0)
{
cmp12=TEST_KEY(i1.key, i2.key);
cmp13=TEST_KEY(i1.key, i3.key);
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 */
cmp23=TEST_KEY(i2.key, i3.key);
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 */
cmp23=TEST_KEY(i2.key, i3.key);
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 */
cmp12=TEST_KEY(i1.key, i2.key);
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
{ /* Dualing 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 */
cmp13=TEST_KEY(i1.key, i3.key);
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
{ /* Dualing 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;
}
Py_DECREF(i1.set);
Py_DECREF(i2.set);
Py_DECREF(i3.set);
if (s1->next)
{
Py_INCREF(s1->next);
r->next = s1->next;
}
s=bucket_getstate(r, NULL);
Py_DECREF(r);
return s;
invalid_set_operation:
PyErr_SetString(PyExc_TypeError, "invalid set operation");
err:
Py_XDECREF(i1.set);
Py_XDECREF(i2.set);
Py_XDECREF(i3.set);
Py_XDECREF(r);
return NULL;
}
--- Added File OIBTree.c in package Zope2 ---
#define PERSISTENT
#define PREFIX "OI"
#define INITMODULE initOIBTree
#define DEFAULT_MAX_BUCKET_SIZE 60
#define DEFAULT_MAX_BTREE_SIZE 250
#include "objectkeymacros.h"
#include "intvaluemacros.h"
#include "BTreeModuleTemplate.c"
--- Added File OOBTree.c in package Zope2 ---
#define PERSISTENT
#define PREFIX "OO"
#define INITMODULE initOOBTree
#define DEFAULT_MAX_BUCKET_SIZE 30
#define DEFAULT_MAX_BTREE_SIZE 250
#include "objectkeymacros.h"
#include "objectvaluemacros.h"
#include "BTreeModuleTemplate.c"
--- Added File SetOpTemplate.c in package Zope2 ---
/*****************************************************************************
Zope Public License (ZPL) Version 1.0
-------------------------------------
Copyright (c) Digital Creations. All rights reserved.
This license has been certified as Open Source(tm).
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions in source code must retain the above copyright
notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions, and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
3. Digital Creations requests that attribution be given to Zope
in any manner possible. Zope includes a "Powered by Zope"
button that is installed by default. While it is not a license
violation to remove this button, it is requested that the
attribution remain. A significant investment has been put
into Zope, and this effort will continue if the Zope community
continues to grow. This is one way to assure that growth.
4. All advertising materials and documentation mentioning
features derived from or use of this software must display
the following acknowledgement:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
In the event that the product being advertised includes an
intact Zope distribution (with copyright and license included)
then this clause is waived.
5. Names associated with Zope or Digital Creations must not be used to
endorse or promote products derived from this software without
prior written permission from Digital Creations.
6. Modified redistributions of any form whatsoever must retain
the following acknowledgment:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
Intact (re-)distributions of any official Zope release do not
require an external acknowledgement.
7. Modifications are encouraged but must be packaged separately as
patches to official Zope releases. Distributions that do not
clearly separate the patches from the original work must be clearly
labeled as unofficial distributions. Modifications which do not
carry the name Zope may be packaged in any form, as long as they
conform to all of the clauses above.
Disclaimer
THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
This software consists of contributions made by Digital Creations and
many individuals on behalf of Digital Creations. Specific
attributions are listed in the accompanying credits file.
****************************************************************************/
/****************************************************************************
Set operations
****************************************************************************/
#ifdef INTSET_H
static int
nextIntSet(SetIteration *i)
{
UNLESS(PER_USE(INTSET(i->set))) return -1;
if (i->position >= 0)
{
if (i->position < INTSET(i->set)->len)
{
i->key = INTSET(i->set)->data[i->position];
i->position ++;
}
else
i->position = -1;
}
PER_ALLOW_DEACTIVATION(INTSET(i->set));
return 0;
}
#endif
#ifdef KEY_CHECK
static int
nextKeyAsSet(SetIteration *i)
{
if (i->position >= 0)
{
if (i->position < 1)
{
i->position ++;
}
else
i->position = -1;
}
return 0;
}
#endif
static int
initSetIteration(SetIteration *i, PyObject *s, int w, int *merge)
{
i->position=0;
if (ExtensionClassSubclassInstance_Check(s, &BucketType))
{
i->set = s;
Py_INCREF(s);
if (w >= 0)
{
*merge=1;
i->next=nextBucket;
}
else
i->next=nextSet;
i->hasValue=1;
}
else if (ExtensionClassSubclassInstance_Check(s, &SetType))
{
i->set = s;
Py_INCREF(s);
i->next=nextSet;
i->hasValue=0;
}
else if (ExtensionClassSubclassInstance_Check(s, &BTreeType))
{
i->set=BTree_rangeSearch(BTREE(s), NULL, 'i');
UNLESS(i->set) return -1;
if (w >= 0)
{
*merge=1;
i->next=nextBTreeItems;
}
else
i->next=nextTreeSetItems;
i->hasValue=1;
}
else if (ExtensionClassSubclassInstance_Check(s, &TreeSetType))
{
i->set=BTree_rangeSearch(BTREE(s), NULL, 'k');
UNLESS(i->set) return -1;
i->next=nextTreeSetItems;
i->hasValue=0;
}
#ifdef INTSET_H
else if (s->ob_type==(PyTypeObject*)intSetType)
{
i->set = s;
Py_INCREF(s);
i->next=nextIntSet;
i->hasValue=0;
}
#endif
#ifdef KEY_CHECK
else if (KEY_CHECK(s))
{
int copied=1;
i->set = s;
Py_INCREF(s);
i->next=nextKeyAsSet;
i->hasValue=0;
COPY_KEY_FROM_ARG(i->key, s, &copied);
UNLESS (copied) return -1;
}
#endif
else
{
PyErr_SetString(PyExc_TypeError, "invalid argument");
return -1;
}
return 0;
}
#ifndef MERGE_WEIGHT
#define MERGE_WEIGHT(O, w) (O)
#endif
static int
copyRemaining(Bucket *r, SetIteration *i, int merge, int w)
{
while (i->position >= 0)
{
if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) return -1;
COPY_KEY(r->keys[r->len], i->key);
INCREF_KEY(r->keys[r->len]);
if (merge)
{
COPY_VALUE(r->values[r->len], MERGE_WEIGHT(i->value, w));
INCREF_VALUE(r->values[r->len]);
}
r->len++;
if (i->next(i) < 0) return -1;
}
return 0;
}
static PyObject *
set_operation(PyObject *s1, PyObject *s2,
int w1, int w2,
int c1, int c12, int c2)
{
Bucket *r=0;
SetIteration i1 = {0,0,0}, i2 = {0,0,0};
int cmp, merge=0;
if (initSetIteration(&i1, s1, w1, &merge) < 0) return NULL;
if (initSetIteration(&i2, s2, w2, &merge) < 0) return NULL;
if (merge)
{
#ifndef MERGE
if (c12 && i1.hasValue && i2.hasValue) goto invalid_set_operation;
#endif
if (! i1.hasValue && i2.hasValue)
{
SetIteration t;
int i;
t=i1; i1=i2; i2=t;
i=c1; c1=c2; c2=i;
i=w1; w1=w2; w2=i;
}
#ifdef MERGE_DEFAULT
i1.value=MERGE_DEFAULT;
i2.value=MERGE_DEFAULT;
#else
if (i1.hasValue)
{
if (! i2.hasValue && c2) goto invalid_set_operation;
}
else
{
if (c1 || c12) goto invalid_set_operation;
}
#endif
UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&BucketType), NULL)))
goto err;
}
else
{
UNLESS(r=BUCKET(PyObject_CallObject(OBJECT(&SetType), NULL)))
goto err;
}
if (i1.next(&i1) < 0) return NULL;
if (i2.next(&i2) < 0) return NULL;
while (i1.position >= 0 && i2.position >= 0)
{
cmp=TEST_KEY(i1.key, i2.key);
if(cmp < 0)
{
if(c1)
{
if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
COPY_KEY(r->keys[r->len], i1.key);
INCREF_KEY(r->keys[r->len]);
if (merge)
{
COPY_VALUE(r->values[r->len], MERGE_WEIGHT(i1.value, w1));
INCREF_VALUE(r->values[r->len]);
}
r->len++;
}
if (i1.next(&i1) < 0) goto err;
}
else if(cmp==0)
{
if(c12)
{
if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
COPY_KEY(r->keys[r->len], i1.key);
INCREF_KEY(r->keys[r->len]);
if (merge)
{
#ifdef MERGE
r->values[r->len] = MERGE(i1.value, w1, i2.value, w2);
#else
COPY_VALUE(r->values[r->len], i1.value);
INCREF_VALUE(r->values[r->len]);
#endif
}
r->len++;
}
if (i1.next(&i1) < 0) goto err;
if (i2.next(&i2) < 0) goto err;
}
else
{
if(c2)
{
if(r->len >= r->size && Bucket_grow(r, ! merge) < 0) goto err;
COPY_KEY(r->keys[r->len], i2.key);
INCREF_KEY(r->keys[r->len]);
if (merge)
{
COPY_VALUE(r->values[r->len], MERGE_WEIGHT(i2.value, w2));
INCREF_VALUE(r->values[r->len]);
}
r->len++;
}
if (i2.next(&i2) < 0) goto err;
}
}
if(c1 && copyRemaining(r, &i1, merge, w1) < 0) goto err;
if(c2 && copyRemaining(r, &i2, merge, w2) < 0) goto err;
Py_DECREF(i1.set);
Py_DECREF(i2.set);
return OBJECT(r);
invalid_set_operation:
PyErr_SetString(PyExc_TypeError, "invalid set operation");
err:
Py_XDECREF(i1.set);
Py_XDECREF(i2.set);
Py_XDECREF(r);
return NULL;
}
static PyObject *
difference_m(PyObject *ignored, PyObject *args)
{
PyObject *o1, *o2;
UNLESS(PyArg_ParseTuple(args, "OO", &o1, &o2)) return NULL;
if (o1==Py_None || o2==Py_None)
{
Py_INCREF(o1);
return Py_None;
}
return set_operation(o1, o2, 1, -1, 1, 0, 0);
}
static PyObject *
union_m(PyObject *ignored, PyObject *args)
{
PyObject *o1, *o2;
UNLESS(PyArg_ParseTuple(args, "OO", &o1, &o2)) return NULL;
if (o1==Py_None)
{
Py_INCREF(o2);
return o2;
}
else if (o2==Py_None)
{
Py_INCREF(o1);
return o1;
}
return set_operation(o1, o2, -1, -1, 1, 1, 1);
}
static PyObject *
intersection_m(PyObject *ignored, PyObject *args)
{
PyObject *o1, *o2;
UNLESS(PyArg_ParseTuple(args, "OO", &o1, &o2)) return NULL;
if (o1==Py_None)
{
Py_INCREF(o2);
return o2;
}
else if (o2==Py_None)
{
Py_INCREF(o1);
return o1;
}
return set_operation(o1, o2, -1, -1, 0, 1, 0);
}
#ifdef MERGE
static PyObject *
wunion_m(PyObject *ignored, PyObject *args)
{
PyObject *o1, *o2;
int w1=1, w2=1;
UNLESS(PyArg_ParseTuple(args, "OO|ii", &o1, &o2, &w1, &w2)) return NULL;
if (o1==Py_None)
return Py_BuildValue("iO", (o2==Py_None ? 0 : w2), o2);
else if (o2==Py_None)
return Py_BuildValue("iO", w1, o1);
o1=set_operation(o1, o2, w1, w2, 1, 1, 1);
if (o1) ASSIGN(o1, Py_BuildValue("iO", 1, o1));
return o1;
}
static PyObject *
wintersection_m(PyObject *ignored, PyObject *args)
{
PyObject *o1, *o2;
int w1=1, w2=1;
UNLESS(PyArg_ParseTuple(args, "OO|ii", &o1, &o2, &w1, &w2)) return NULL;
if (o1==Py_None)
return Py_BuildValue("iO", (o2==Py_None ? 0 : w2), o2);
else if (o2==Py_None)
return Py_BuildValue("iO", w1, o1);
o1=set_operation(o1, o2, w1, w2, 0, 1, 0);
if (o1)
ASSIGN(o1, Py_BuildValue("iO",
((o1->ob_type == (PyTypeObject*)(&SetType)) ? w2+w1 : 1),
o1));
return o1;
}
#endif
--- Added File SetTemplate.c in package Zope2 ---
/*****************************************************************************
Zope Public License (ZPL) Version 1.0
-------------------------------------
Copyright (c) Digital Creations. All rights reserved.
This license has been certified as Open Source(tm).
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions in source code must retain the above copyright
notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions, and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
3. Digital Creations requests that attribution be given to Zope
in any manner possible. Zope includes a "Powered by Zope"
button that is installed by default. While it is not a license
violation to remove this button, it is requested that the
attribution remain. A significant investment has been put
into Zope, and this effort will continue if the Zope community
continues to grow. This is one way to assure that growth.
4. All advertising materials and documentation mentioning
features derived from or use of this software must display
the following acknowledgement:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
In the event that the product being advertised includes an
intact Zope distribution (with copyright and license included)
then this clause is waived.
5. Names associated with Zope or Digital Creations must not be used to
endorse or promote products derived from this software without
prior written permission from Digital Creations.
6. Modified redistributions of any form whatsoever must retain
the following acknowledgment:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
Intact (re-)distributions of any official Zope release do not
require an external acknowledgement.
7. Modifications are encouraged but must be packaged separately as
patches to official Zope releases. Distributions that do not
clearly separate the patches from the original work must be clearly
labeled as unofficial distributions. Modifications which do not
carry the name Zope may be packaged in any form, as long as they
conform to all of the clauses above.
Disclaimer
THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
This software consists of contributions made by Digital Creations and
many individuals on behalf of Digital Creations. Specific
attributions are listed in the accompanying credits file.
****************************************************************************/
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);
}
static PyObject *
Set_update(Bucket *self, PyObject *args)
{
PyObject *seq=0, *o, *t, *v, *tb;
int i, n=0, ind;
UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;
if (seq)
{
for (i=0; ; i++)
{
UNLESS (o=PySequence_GetItem(seq, i))
{
PyErr_Fetch(&t, &v, &tb);
if (t != PyExc_IndexError)
{
PyErr_Restore(t, v, tb);
return NULL;
}
Py_XDECREF(t);
Py_XDECREF(v);
Py_XDECREF(tb);
break;
}
ind=_bucket_set(self, o, Py_None, 1, 1, 0);
Py_DECREF(o);
if (ind < 0) return NULL;
n += ind;
}
}
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;
VALUE_TYPE *values;
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=PyRealloc(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);
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_VARARGS,
"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"},
{"__init__", (PyCFunction)Set_update, METH_VARARGS,
"__init__(seq) -- Initialize with the items from the given sequence"},
{"remove", (PyCFunction)Set_remove, METH_VARARGS,
"remove(id) -- Remove an id from the set"},
{NULL, NULL} /* sentinel */
};
static PyObject *
set_repr(Bucket *self)
{
static PyObject *format;
PyObject *r, *t;
UNLESS (format) UNLESS (format=PyString_FromString(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);
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);
return r;
}
static PySequenceMethods set_as_sequence = {
(inquiry)set_length, /*sq_length*/
(binaryfunc)0, /*sq_concat*/
(intargfunc)0, /*sq_repeat*/
(intargfunc)set_item, /*sq_item*/
(intintargfunc)0, /*sq_slice*/
(intobjargproc)0, /*sq_ass_item*/
(intintobjargproc)0, /*sq_ass_slice*/
};
static PyExtensionClass SetType = {
PyObject_HEAD_INIT(NULL)
0, /*ob_size*/
PREFIX "Set", /*tp_name*/
sizeof(Bucket), /*tp_basicsize*/
0, /*tp_itemsize*/
/*********** methods ***********************/
(destructor) Bucket_dealloc, /*tp_dealloc*/
(printfunc)0, /*tp_print*/
(getattrfunc)0, /*obsolete tp_getattr*/
(setattrfunc)0, /*obsolete tp_setattr*/
(cmpfunc)0, /*tp_compare*/
(reprfunc) set_repr, /*tp_repr*/
0, /*tp_as_number*/
&set_as_sequence, /*tp_as_sequence*/
0, /*tp_as_mapping*/
(hashfunc)0, /*tp_hash*/
(ternaryfunc)0, /*tp_call*/
(reprfunc)0, /*tp_str*/
(getattrofunc)0, /*tp_getattro*/
0, /*tp_setattro*/
/* Space for future expansion */
0L,0L,
"Set implemented as sorted keys",
METHOD_CHAIN(Set_methods),
EXTENSIONCLASS_BASICNEW_FLAG
#ifdef PERSISTENT
| PERSISTENT_TYPE_FLAG
#endif
| EXTENSIONCLASS_NOINSTDICT_FLAG,
};
static int
nextSet(SetIteration *i)
{
UNLESS(PER_USE(BUCKET(i->set))) return -1;
if (i->position >= 0)
{
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;
}
PER_ALLOW_DEACTIVATION(BUCKET(i->set));
return 0;
}
--- Added File Setup in package Zope2 ---
*shared*
OOBTree OOBTree.c -I../../Components/ExtensionClass/src -I../ZODB
OIBTree OIBTree.c -I../../Components/ExtensionClass/src -I../ZODB
IIBTree IIBTree.c -I../../Components/ExtensionClass/src -I../ZODB -I../../Components
IOBTree IOBTree.c -I../../Components/ExtensionClass/src -I../ZODB -I../../Components
--- Added File TreeSetTemplate.c in package Zope2 ---
/*****************************************************************************
Zope Public License (ZPL) Version 1.0
-------------------------------------
Copyright (c) Digital Creations. All rights reserved.
This license has been certified as Open Source(tm).
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
1. Redistributions in source code must retain the above copyright
notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions, and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
3. Digital Creations requests that attribution be given to Zope
in any manner possible. Zope includes a "Powered by Zope"
button that is installed by default. While it is not a license
violation to remove this button, it is requested that the
attribution remain. A significant investment has been put
into Zope, and this effort will continue if the Zope community
continues to grow. This is one way to assure that growth.
4. All advertising materials and documentation mentioning
features derived from or use of this software must display
the following acknowledgement:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
In the event that the product being advertised includes an
intact Zope distribution (with copyright and license included)
then this clause is waived.
5. Names associated with Zope or Digital Creations must not be used to
endorse or promote products derived from this software without
prior written permission from Digital Creations.
6. Modified redistributions of any form whatsoever must retain
the following acknowledgment:
"This product includes software developed by Digital Creations
for use in the Z Object Publishing Environment
(http://www.zope.org/)."
Intact (re-)distributions of any official Zope release do not
require an external acknowledgement.
7. Modifications are encouraged but must be packaged separately as
patches to official Zope releases. Distributions that do not
clearly separate the patches from the original work must be clearly
labeled as unofficial distributions. Modifications which do not
carry the name Zope may be packaged in any form, as long as they
conform to all of the clauses above.
Disclaimer
THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
This software consists of contributions made by Digital Creations and
many individuals on behalf of Digital Creations. Specific
attributions are listed in the accompanying credits file.
****************************************************************************/
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);
}
static PyObject *
TreeSet_update(BTree *self, PyObject *args)
{
PyObject *seq=0, *o, *t, *v, *tb;
int i, n=0, ind;
UNLESS(PyArg_ParseTuple(args, "|O:update", &seq)) return NULL;
if (seq)
{
for (i=0; ; i++)
{
UNLESS (o=PySequence_GetItem(seq, i))
{
PyErr_Fetch(&t, &v, &tb);
if (t != PyExc_IndexError)
{
PyErr_Restore(t, v, tb);
return NULL;
}
Py_XDECREF(t);
Py_XDECREF(v);
Py_XDECREF(tb);
break;
}
ind=_BTree_set(self, o, Py_None, 1, 1);
Py_DECREF(o);
if (ind < 0) return NULL;
n += ind;
}
}
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);
if (r < 0) return NULL;
Py_INCREF(Py_None);
return Py_None;
}
static struct PyMethodDef TreeSet_methods[] = {
{"__getstate__", (PyCFunction) BTree_getstate, METH_VARARGS,
"__getstate__() -- Return the picklable state of the object"},
{"__setstate__", (PyCFunction) TreeSet_setstate, METH_VARARGS,
"__setstate__() -- Set the state of the object"},
{"has_key", (PyCFunction) BTree_has_key, METH_VARARGS,
"has_key(key) -- Test whether the bucket contains the given key"},
{"keys", (PyCFunction) BTree_keys, METH_VARARGS,
"keys() -- Return the keys"},
{"maxKey", (PyCFunction) BTree_maxKey, METH_VARARGS,
"maxKey([key]) -- Fine the maximum key\n\n"
"If an argument is given, find the maximum <= the argument"},
{"minKey", (PyCFunction) BTree_minKey, METH_VARARGS,
"minKey([key]) -- Fine the minimum key\n\n"
"If an argument is given, find the minimum >= the argument"},
{"clear", (PyCFunction) BTree_clear, METH_VARARGS,
"clear() -- Remove all of the items from the BTree"},
{"insert", (PyCFunction)TreeSet_insert, METH_VARARGS,
"insert(id,[ignored]) -- Add an id to the set"},
{"update", (PyCFunction)TreeSet_update, METH_VARARGS,
"update(seq) -- Add the items from the given sequence to the set"},
{"__init__", (PyCFunction)TreeSet_update, METH_VARARGS,
"__init__(seq) -- Initialize with the items from the given sequence"},
{"remove", (PyCFunction)TreeSet_remove, METH_VARARGS,
"remove(id) -- Remove a key from the set"},
#ifdef PERSISTENT
{"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict, METH_VARARGS,
"_p_resolveConflict() -- Reinitialize from a newly created copy"},
{"_p_deactivate", (PyCFunction) BTree__p_deactivate, METH_VARARGS,
"_p_deactivate() -- Reinitialize from a newly created copy"},
#endif
{NULL, NULL} /* sentinel */
};
static PyExtensionClass TreeSetType = {
PyObject_HEAD_INIT(NULL)
0, /*ob_size*/
PREFIX "TreeSet", /*tp_name*/
sizeof(BTree), /*tp_basicsize*/
0, /*tp_itemsize*/
/************* methods ********************/
(destructor) BTree_dealloc, /*tp_dealloc*/
(printfunc)0, /*tp_print*/
(getattrfunc)0, /*obsolete tp_getattr*/
(setattrfunc)0, /*obsolete tp_setattr*/
(cmpfunc)0, /*tp_compare*/
(reprfunc)0, /*tp_repr*/
&BTree_as_number_for_nonzero, /*tp_as_number*/
0, /*tp_as_sequence*/
0, /*tp_as_mapping*/
(hashfunc)0, /*tp_hash*/
(ternaryfunc)0, /*tp_call*/
(reprfunc)0, /*tp_str*/
(getattrofunc)0,
0, /*tp_setattro*/
/* Space for future expansion */
0L,0L,
"Set implemented as sorted tree of items",
METHOD_CHAIN(TreeSet_methods),
EXTENSIONCLASS_BASICNEW_FLAG
#ifdef PERSISTENT
| PERSISTENT_TYPE_FLAG
#endif
| EXTENSIONCLASS_NOINSTDICT_FLAG,
};
--- Added File __init__.py in package Zope2 ---
import ZODB
try: import intSet
except: pass
else: del intSet
--- Added File config.c in package Zope2 ---
/* Generated automatically from /usr/local/python1.5.2/lib/python1.5/config/config.c.in by makesetup. */
/* -*- C -*- ***********************************************
Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
The Netherlands.
All Rights Reserved
Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in
supporting documentation, and that the names of Stichting Mathematisch
Centrum or CWI or Corporation for National Research Initiatives or
CNRI not be used in advertising or publicity pertaining to
distribution of the software without specific, written prior
permission.
While CWI is the initial source for this software, a modified version
is made available by the Corporation for National Research Initiatives
(CNRI) at the Internet address ftp://ftp.python.org.
STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.
******************************************************************/
/* Module configuration */
/* !!! !!! !!! This file is edited by the makesetup script !!! !!! !!! */
/* This file contains the table of built-in modules.
See init_builtin() in import.c. */
#include "Python.h"
extern void initthread();
extern void initregex();
extern void initpcre();
extern void initposix();
extern void initsignal();
extern void initarray();
extern void initcmath();
extern void initmath();
extern void initstrop();
extern void initstruct();
extern void inittime();
extern void initoperator();
extern void initfcntl();
extern void initpwd();
extern void initgrp();
extern void initselect();
extern void initsocket();
extern void initerrno();
extern void initmd5();
extern void initsha();
extern void initrotor();
extern void initnew();
extern void initbinascii();
extern void initparser();
extern void initcStringIO();
extern void initcPickle();
/* -- ADDMODULE MARKER 1 -- */
extern void PyMarshal_Init();
extern void initimp();
struct _inittab _PyImport_Inittab[] = {
{"thread", initthread},
{"regex", initregex},
{"pcre", initpcre},
{"posix", initposix},
{"signal", initsignal},
{"array", initarray},
{"cmath", initcmath},
{"math", initmath},
{"strop", initstrop},
{"struct", initstruct},
{"time", inittime},
{"operator", initoperator},
{"fcntl", initfcntl},
{"pwd", initpwd},
{"grp", initgrp},
{"select", initselect},
{"socket", initsocket},
{"errno", initerrno},
{"md5", initmd5},
{"sha", initsha},
{"rotor", initrotor},
{"new", initnew},
{"binascii", initbinascii},
{"parser", initparser},
{"cStringIO", initcStringIO},
{"cPickle", initcPickle},
/* -- ADDMODULE MARKER 2 -- */
/* This module "lives in" with marshal.c */
{"marshal", PyMarshal_Init},
/* This lives it with import.c */
{"imp", initimp},
/* These entries are here for sys.builtin_module_names */
{"__main__", NULL},
{"__builtin__", NULL},
{"sys", NULL},
/* Sentinel */
{0, 0}
};
--- Added File convert.py in package Zope2 ---
##############################################################################
#
# Zope Public License (ZPL) Version 1.0
# -------------------------------------
#
# Copyright (c) Digital Creations. All rights reserved.
#
# This license has been certified as Open Source(tm).
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
#
# 1. Redistributions in source code must retain the above copyright
# notice, this list of conditions, and the following disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright
# notice, this list of conditions, and the following disclaimer in
# the documentation and/or other materials provided with the
# distribution.
#
# 3. Digital Creations requests that attribution be given to Zope
# in any manner possible. Zope includes a "Powered by Zope"
# button that is installed by default. While it is not a license
# violation to remove this button, it is requested that the
# attribution remain. A significant investment has been put
# into Zope, and this effort will continue if the Zope community
# continues to grow. This is one way to assure that growth.
#
# 4. All advertising materials and documentation mentioning
# features derived from or use of this software must display
# the following acknowledgement:
#
# "This product includes software developed by Digital Creations
# for use in the Z Object Publishing Environment
# (http://www.zope.org/)."
#
# In the event that the product being advertised includes an
# intact Zope distribution (with copyright and license included)
# then this clause is waived.
#
# 5. Names associated with Zope or Digital Creations must not be used to
# endorse or promote products derived from this software without
# prior written permission from Digital Creations.
#
# 6. Modified redistributions of any form whatsoever must retain
# the following acknowledgment:
#
# "This product includes software developed by Digital Creations
# for use in the Z Object Publishing Environment
# (http://www.zope.org/)."
#
# Intact (re-)distributions of any official Zope release do not
# require an external acknowledgement.
#
# 7. Modifications are encouraged but must be packaged separately as
# patches to official Zope releases. Distributions that do not
# clearly separate the patches from the original work must be clearly
# labeled as unofficial distributions. Modifications which do not
# carry the name Zope may be packaged in any form, as long as they
# conform to all of the clauses above.
#
#
# Disclaimer
#
# THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS ``AS IS'' AND ANY
# EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DIGITAL CREATIONS OR ITS
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGE.
#
#
# This software consists of contributions made by Digital Creations and
# many individuals on behalf of Digital Creations. Specific
# attributions are listed in the accompanying credits file.
#
##############################################################################
def convert(old, new, threshold=200, f=None, None=None):
"Utility for converting old btree new new"
n=0
for k, v in old.items():
if f is not None: v=f(v)
new[k]=v
n=n+1
if n > threshold:
get_transaction().commit(1)
old._p_jar.cacheMinimize(3)
n=0
get_transaction().commit(1)
old._p_jar.cacheMinimize(3)
--- Added File intkeymacros.h in package Zope2 ---
#define KEY_TYPE int
#define KEY_CHECK PyInt_Check
#define TEST_KEY(K, T) (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 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_AsLong(ARG); else { \
PyErr_SetString(PyExc_TypeError, "expected integer key"); \
*(STATUS)=0; }
--- Added File intvaluemacros.h in package Zope2 ---
#define VALUE_TYPE int
#define TEST_VALUE(K, T) (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0))
#define VALUE_SAME(VALUE, TARGET) ( (VALUE) == (TARGET) )
#define DECLARE_VALUE(NAME) VALUE_TYPE NAME
#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; }
#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 objectkeymacros.h in package Zope2 ---
#define KEY_TYPE PyObject *
#define TEST_KEY(KEY, TARGET) PyObject_Compare((KEY),(TARGET))
#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 objectvaluemacros.h in package Zope2 ---
#define VALUE_TYPE PyObject *
#define TEST_VALUE(VALUE, TARGET) PyObject_Compare((VALUE),(TARGET))
#define DECLARE_VALUE(NAME) VALUE_TYPE NAME
#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)