[Zope-Checkins] CVS: Zope3/lib/python/Persistence/BTrees - BTreeModuleTemplate.c:1.1.2.13 BTreeTemplate.c:1.1.2.11
Tim Peters
tim.one@comcast.net
Tue, 4 Jun 2002 16:48:07 -0400
Update of /cvs-repository/Zope3/lib/python/Persistence/BTrees
In directory cvs.zope.org:/tmp/cvs-serv12974
Modified Files:
Tag: Zope-3x-branch
BTreeModuleTemplate.c BTreeTemplate.c
Log Message:
Merged in a bunch of declaration changes, and new comments, from the trunk.
=== Zope3/lib/python/Persistence/BTrees/BTreeModuleTemplate.c 1.1.2.12 => 1.1.2.13 ===
PyErr_SetString(PyExc_AssertionError, (S)); return (R); }
-/* A BTree is complicated. See Maintainer.txt.
+/* Various kinds of BTree and Bucket structs are instances of
+ * "sized containers", and have a common initial layout:
+ * The stuff needed for all Python objects, or all Persistent objects.
+ * int size: The maximum number of things that could be contained
+ * without growing the container.
+ * int len: The number of things currently contained.
+ *
+ * Invariant: 0 <= len <= size.
+ *
+ * A sized container typically goes on to declare one or more pointers
+ * to contiguous arrays with 'size' elements each, the initial 'len' of
+ * which are currently in use.
*/
-
-typedef struct BTreeItemStruct {
- KEY_TYPE key;
- PyObject *child; /* points to another BTree, or to a Bucket of some sort */
-} BTreeItem;
-
-typedef struct Bucket_s {
#ifdef PERSISTENT
- PyPersist_INSTANCE_HEAD
- PyObject **po_weaklist;
+#define sizedcontainer_HEAD \
+ PyPersist_INSTANCE_HEAD \
+ PyObject **po_weaklist; \
+ int size; \
+ int len;
#else
- PyObject_HEAD
+#define sizedcontainer_HEAD \
+ PyObject_HEAD \
+ int size; \
+ int len;
#endif
- int size, len;
- struct Bucket_s *next;
- KEY_TYPE *keys;
- VALUE_TYPE *values;
+
+/* Nothing is actually of type Sized, but (pointers to) BTree nodes and
+ * Buckets can be cast to Sized* in contexts that only need to examine
+ * the members common to all sized containers.
+ */
+typedef struct Sized_s {
+ sizedcontainer_HEAD
+} Sized;
+
+#define SIZED(O) ((Sized*)(O))
+
+/* A Bucket wraps contiguous vectors of keys and values. Keys are unique,
+ * and stored in sorted order. The 'values' pointer may be NULL if the
+ * Bucket is used to implement a set. Buckets serving as leafs of BTrees
+ * are chained together via 'next', so that the entire BTree contents
+ * can be traversed in sorted order quickly and easily.
+ */
+typedef struct Bucket_s {
+ sizedcontainer_HEAD
+ struct Bucket_s *next; /* the bucket with the next-larger keys */
+ KEY_TYPE *keys; /* 'len' keys, in increasing order */
+ VALUE_TYPE *values; /* 'len' corresponding values; NULL if a set */
} Bucket;
#define BUCKET(O) ((Bucket*)(O))
@@ -86,31 +114,106 @@
#define ASSIGNB(V,E) PyVar_AssignB(&(V),(E))
#define ASSIGNBC(V,E) (Py_INCREF((E)), PyVar_AssignB(&(V),(E)))
-typedef struct {
-#ifdef PERSISTENT
- PyPersist_INSTANCE_HEAD
- PyObject **po_weaklist;
-#else
- PyObject_HEAD
-#endif
- int size, len;
+/* A BTree is complicated. See Maintainer.txt.
+ */
+
+typedef struct BTreeItem_s {
+ KEY_TYPE key;
+ Sized *child; /* points to another BTree, or to a Bucket of some sort */
+} BTreeItem;
+
+typedef struct BTree_s {
+ sizedcontainer_HEAD
+
+ /* firstbucket points to the bucket containing the smallest key in
+ * the BTree. This is found by traversing leftmost child pointers
+ * (data[0].child) until reaching a Bucket.
+ */
Bucket *firstbucket;
+
+ /* The BTree points to 'len' children, via the "child" fields of the data
+ * array. There are len-1 keys in the 'key' fields, stored in increasing
+ * order. data[0].key is unused. For i in 0 .. len-1, all keys reachable
+ * from data[i].child are >= data[i].key and < data[i+1].key, at the
+ * endpoints pretending that data[0].key is minus infinity and
+ * data[len].key is positive infinity.
+ */
BTreeItem *data;
} BTree;
staticforward PyTypeObject BTreeType;
-
#define BTREE(O) ((BTree*)(O))
+/* Use BTREE_SEARCH to find which child pointer to follow.
+ * RESULT An int lvalue to hold the index i such that SELF->data[i].child
+ * is the correct node to search next.
+ * SELF A pointer to a BTree node.
+ * KEY The key you're looking for, of type KEY_TYPE.
+ * ONERROR What to do if key comparison raises an exception; for example,
+ * perhaps 'return NULL'.
+ *
+ * See Maintainer.txt for discussion: this is optimized in subtle ways.
+ * It's recommended that you call this at the start of a routine, waiting
+ * to check for self->len == 0 after.
+ */
+#define BTREE_SEARCH(RESULT, SELF, KEY, ONERROR) { \
+ int _lo = 0; \
+ int _hi = (SELF)->len; \
+ int _i, _cmp; \
+ for (_i = _hi >> 1; _i > _lo; _i = (_lo + _hi) >> 1) { \
+ TEST_KEY_SET_OR(_cmp, (SELF)->data[_i].key, (KEY)) \
+ ONERROR; \
+ if (_cmp < 0) _lo = _i; \
+ else if (_cmp > 0) _hi = _i; \
+ else /* equal */ break; \
+ } \
+ (RESULT) = _i; \
+}
+
+/* SetIteration structs are used in the internal set iteration protocol.
+ * When you want to iterate over a set or bucket or BTree (even an
+ * individual key!),
+ * 1. Declare a new iterator and a "merge" int:
+ * SetIteration si = {0,0,0};
+ * int merge = 0;
+ * XXX Using "{0,0,0}" or "{0,0}" appear most common, but I don't
+ * XXX think it makes any difference; looks like "{0}" would work too;
+ * XXX looks like not initializing it at all would also work.
+ * 2. Initialize it via
+ * initSetIteration(&si, PyObject *s, int weight, &merge)
+ * There's an error if that returns an int < 0. Note that si.set must
+ * be Py_XDECREF'ed in this case.
+ * If it's successful, si.hasValue is set to true iff s has values (as
+ * well as keys).
+ * 3. Get the first element:
+ * if (si.next(&si) < 0) { there was an error }
+ * If the set isn't empty, this sets si.position to an int >= 0,
+ * si.key to the element's key (of type KEY_TYPE), and si.value to
+ * the element's value (of type VALUE_TYPE). si.value is defined
+ * iff merge was set to true by the initSetIteration() call. If
+ * there was an error, the caller is responsible for Py_XDECREF'ing
+ * si.set.
+ * 4. Process all the elements:
+ * while (si.position >= 0) {
+ * do something with si.key and/or si.value;
+ * if (si.next(&si) < 0) {
+ * there was an error;
+ * Py_XDECREF(si.set);
+ * do whatever else is appropriate for the caller;
+ * }
+ * }
+ * 5. Decref the SetIteration's set:
+ * Py_XDECREF(si.set);
+ */
typedef struct SetIteration_s
{
- PyObject *set;
- int position;
- int hasValue;
- KEY_TYPE key;
- VALUE_TYPE value;
- int (*next)(struct SetIteration_s*);
+ PyObject *set; /* the set, bucket, BTree, ..., being iterated */
+ int position; /* initialized to 0; set to -1 by next() when done */
+ int hasValue; /* true iff 'set' has values (as well as keys) */
+ KEY_TYPE key; /* next() sets to next key */
+ VALUE_TYPE value; /* next() may set to next value */
+ int (*next)(struct SetIteration_s*); /* function to get next key+value */
} SetIteration;
static PyObject *
@@ -136,10 +239,10 @@
PreviousBucket(Bucket *current, Bucket *first, int i)
{
if (!first)
- return NULL;
+ return NULL;
if (first == current) {
- IndexError(i);
- return NULL;
+ IndexError(i);
+ return NULL;
}
Py_INCREF(first);
@@ -278,6 +381,14 @@
"weightedIntersection(o1, o2 [, w1, w2]) -- "
"compute the intersection of o1 and o2\n"
"\nw1 and w2 are weights."
+ },
+#endif
+#ifdef MULTI_INT_UNION
+ {"multiunion", (PyCFunction) multiunion_m, METH_VARARGS,
+ "multiunion(seq) -- compute union of a sequence of integer sets.\n"
+ "\n"
+ "Each element of seq must be an integer set, or convertible to one\n"
+ "via the set iteration protocol. The union returned is an IISet."
},
#endif
{NULL, NULL} /* sentinel */
=== Zope3/lib/python/Persistence/BTrees/BTreeTemplate.c 1.1.2.10 => 1.1.2.11 ===
self->len = 2;
self->size = 2;
- self->data->child = (PyObject *)n1;
+ self->data->child = (Sized *)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].child = (PyObject *)n2;
+ self->data[1].child = (Sized *)n2;
return 0;
@@ -189,7 +189,7 @@
BTree_grow(BTree *self, int index, int noval)
{
int i;
- PyObject *v, *e=0;
+ Sized *v, *e=0;
BTreeItem *d;
if (self->len == self->size) {
@@ -212,7 +212,7 @@
if (self->len) {
v = d->child;
/* Create a new object of the same type as the target value */
- e = PyObject_CallObject((PyObject *)v->ob_type, NULL);
+ e = (Sized *)PyObject_CallObject((PyObject *)v->ob_type, NULL);
if (e == NULL)
return -1;
@@ -252,9 +252,9 @@
return BTree_clone(self);
} else {
if (noval)
- d->child = PyObject_CallObject((PyObject *)&SetType, NULL);
+ d->child = (Sized *)PyObject_CallObject((PyObject *)&SetType, NULL);
else
- d->child = PyObject_CallObject((PyObject *)&BucketType, NULL);
+ d->child = (Sized *)PyObject_CallObject((PyObject *)&BucketType, NULL);
if (d->child == NULL)
return -1;
self->len = 1;
@@ -274,7 +274,7 @@
static Bucket *
BTree_lastBucket(BTree *self)
{
- PyObject *o;
+ Sized *o;
if (!(self->data && self->len)) {
IndexError(-1); /*XXX*/
@@ -292,7 +292,7 @@
PyPersist_INCREF(self);
if (!PyPersist_IS_STICKY(self))
return NULL;
- ASSIGN(o, OBJECT(BTree_lastBucket(self)));
+ ASSIGN(OBJECT(o), OBJECT(BTree_lastBucket(self)));
PyPersist_DECREF(self);
PyPersist_SetATime(self);
@@ -596,7 +596,8 @@
static PyObject *
BTree_getstate(BTree *self)
{
- PyObject *r = NULL, *o;
+ PyObject *r = NULL;
+ PyObject *o;
int i, l;
PyPersist_INCREF(self);
@@ -620,14 +621,15 @@
goto err;
PyTuple_SET_ITEM(r, 0, o);
ASSIGN(r, Py_BuildValue("(O)", r));
- } else {
+ }
+ 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].child;
+ o = (PyObject *)self->data[i].child;
Py_INCREF(o);
PyTuple_SET_ITEM(r,l,o);
l++;
@@ -686,18 +688,21 @@
return -1;
INCREF_KEY(d->key);
}
- d->child = PyTuple_GET_ITEM(items, l);
+ d->child = (Sized *)PyTuple_GET_ITEM(items, l);
if (PyTuple_Check(d->child)) {
if (noval) {
- UNLESS (d->child=PyObject_CallObject(OBJECT(&SetType),
- NULL))
- return -1;
+ d->child = (Sized *)PyObject_CallObject(OBJECT(&SetType),
+ NULL);
+
+ UNLESS (d->child)
+ return -1;
if (_set_setstate(BUCKET(d->child),
PyTuple_GET_ITEM(items,l))
< 0) return -1;
} else {
- UNLESS (d->child=PyObject_CallObject(OBJECT(&BucketType),
- NULL))
+ d->child = (Sized *)PyObject_CallObject(OBJECT(&BucketType),
+ NULL);
+ UNLESS (d->child)
return -1;
if (_bucket_setstate(BUCKET(d->child),
PyTuple_GET_ITEM(items,l))
@@ -712,7 +717,7 @@
if (len)
{
if (!firstbucket)
- firstbucket = self->data->child;
+ firstbucket = (PyObject *)self->data->child;
/* XXX what is this? */
if (!PyObject_IsInstance(firstbucket, (PyObject *)