[Checkins] SVN: ZODB/branches/jim-python-btrees/s checkpoint
Jim Fulton
jim at zope.com
Wed May 25 09:01:58 EDT 2011
Log message for revision 121798:
checkpoint
Changed:
U ZODB/branches/jim-python-btrees/setup.py
U ZODB/branches/jim-python-btrees/src/BTrees/IFBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/IIBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/IOBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/LFBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/LLBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/LOBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/OIBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/OLBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/OOBTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/___BTree.py
U ZODB/branches/jim-python-btrees/src/BTrees/fsBTree.py
U ZODB/branches/jim-python-btrees/src/ZODB/fsIndex.py
-=-
Modified: ZODB/branches/jim-python-btrees/setup.py
===================================================================
--- ZODB/branches/jim-python-btrees/setup.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/setup.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -91,6 +91,7 @@
for flavor in ("OO", "IO", "OI", "II", "IF",
"fs", "LO", "OL", "LL", "LF",
)]
+exts = []
cPersistence = Extension(name = 'persistent.cPersistence',
include_dirs = include,
Modified: ZODB/branches/jim-python-btrees/src/BTrees/IFBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/IFBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/IFBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -16,6 +16,11 @@
import BTrees.Interfaces
# hack to overcome dynamic-linking headache.
-from _IFBTree import *
+try:
+ from _IFBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'IF', 120, 500)
+
zope.interface.moduleProvides(BTrees.Interfaces.IIntegerFloatBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/IIBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/IIBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/IIBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -16,6 +16,10 @@
import BTrees.Interfaces
# hack to overcome dynamic-linking headache.
-from _IIBTree import *
+try:
+ from _IIBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'II', 120, 500)
zope.interface.moduleProvides(BTrees.Interfaces.IIntegerIntegerBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/IOBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/IOBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/IOBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -16,6 +16,10 @@
import BTrees.Interfaces
# hack to overcome dynamic-linking headache.
-from _IOBTree import *
+try:
+ from _IOBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'IO', 60, 500)
zope.interface.moduleProvides(BTrees.Interfaces.IIntegerObjectBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/LFBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/LFBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/LFBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -15,7 +15,10 @@
import zope.interface
import BTrees.Interfaces
-# hack to overcome dynamic-linking headache.
-from _LFBTree import *
+try:
+ from _LFBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'LF', 120, 500)
zope.interface.moduleProvides(BTrees.Interfaces.IIntegerFloatBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/LLBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/LLBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/LLBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -15,7 +15,10 @@
import zope.interface
import BTrees.Interfaces
-# hack to overcome dynamic-linking headache.
-from _LLBTree import *
+try:
+ from _LLBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'LL', 120, 500)
zope.interface.moduleProvides(BTrees.Interfaces.IIntegerIntegerBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/LOBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/LOBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/LOBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -16,6 +16,10 @@
import BTrees.Interfaces
# hack to overcome dynamic-linking headache.
-from _LOBTree import *
+try:
+ from _LOBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'LO', 60, 500)
zope.interface.moduleProvides(BTrees.Interfaces.IIntegerObjectBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/OIBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/OIBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/OIBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -16,6 +16,10 @@
import BTrees.Interfaces
# hack to overcome dynamic-linking headache.
-from _OIBTree import *
+try:
+ from _OIBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'OI', 60, 250)
zope.interface.moduleProvides(BTrees.Interfaces.IObjectIntegerBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/OLBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/OLBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/OLBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -16,6 +16,10 @@
import BTrees.Interfaces
# hack to overcome dynamic-linking headache.
-from _OLBTree import *
+try:
+ from _OLBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'OL', 60, 250)
zope.interface.moduleProvides(BTrees.Interfaces.IObjectIntegerBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/OOBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/OOBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/OOBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -15,32 +15,10 @@
import zope.interface
import BTrees.Interfaces
-# hack to overcome dynamic-linking headache.
try:
from _OOBTree import *
except ImportError:
-
import ___BTree
+ ___BTree._import(globals(), 'OO', 30, 250)
- class _Base:
- pass
-
- class OOBucket(___BTree.Bucket, _Base):
- MAX_SIZE = 30
-
- _Base._mapping_type = OOBucket
-
- class OOSet(___BTree.Set, _Base)):
- MAX_SIZE = 30
-
- _Base._set_type = OOSet
-
- class OOBTree(___BTree.BTree, _Base)):
- _bucket_type = OOBucket
- MAX_SIZE = 250
-
- class OOBTreeSet(___BTree.BTree, _Base)):
- _bucket_type = OOSet
- MAX_SIZE = 250
-
zope.interface.moduleProvides(BTrees.Interfaces.IObjectObjectBTreeModule)
Modified: ZODB/branches/jim-python-btrees/src/BTrees/___BTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/___BTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/___BTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -14,7 +14,9 @@
"""Python BTree implementation
"""
+from struct import pack
from ZODB.POSException import ConflictError
+
import persistent
_marker = object()
@@ -93,7 +95,8 @@
else:
raise ValueError("no key satisfies the conditions")
- def _range(min=_marker, max=_marker, excludemin=False, excludemax=False):
+ def _range(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False):
if min is _marker:
start = 0
if excludemin:
@@ -114,12 +117,10 @@
max = self._to_key(max)
end = self._search(max)
if end >= 0:
- if excludemax:
- end -= 1
+ if not excludemax:
+ end += 1
else:
end = -end - 1
- if excludemax:
- end -= 1
return start, end
@@ -204,7 +205,7 @@
if cmp12 > 0: # insert committed
merge_output(i2)
elif set or i1.value == i3.value: # delete committed
- if i2.position == 1
+ if i2.position == 1:
# Deleted the first item. This will modify the
# parent node, so we don't know if merging will be
# safe
@@ -308,13 +309,18 @@
return self
-class _MappingBase:
+class _MappingBase(_Base):
def setdefault(self, key, value):
return self._set(self._to_key(key), self._to_value(value), True)[1]
- def pop(self, key):
- return self._del(self._to_key(key))[1]
+ def pop(self, key, default=_marker):
+ try:
+ return self._del(self._to_key(key))[1]
+ except KeyError:
+ if default is _marker:
+ raise
+ return default
def update(self, items):
if hasattr(items, 'iteritems'):
@@ -332,10 +338,10 @@
def __delitem__(self, key):
self._del(self._to_key(key))
-class _SetBase:
+class _SetBase(_Base):
def add(self, key):
- self._set(self._to_key(key))
+ return self._set(self._to_key(key))[0]
insert = add
@@ -347,7 +353,7 @@
for i in items:
add(i)
-class Bucket(_Base, _MappingBase):
+class Bucket(_MappingBase):
_value_type = list
_to_value = lambda x: x
@@ -395,8 +401,6 @@
self._values.insert(index, value)
return 1, value
- __setitem__ = _set
-
def _del(self, key):
index = self._search(key)
if index >= 0:
@@ -410,10 +414,10 @@
if index < 0 or index >= len(self._keys):
index = len(self._keys) / 2
new_instance = self.__class__()
- new_instance._keys = self._keys[i:]
- new_instance._values = self._values[i:]
- del self._keys[i:]
- del self._values[i:]
+ new_instance._keys = self._keys[index:]
+ new_instance._values = self._values[index:]
+ del self._keys[index:]
+ del self._values[index:]
new_instance._next = self._next
self._next = new_instance
return new_instance
@@ -439,7 +443,12 @@
def __getstate__(self):
keys = self._keys
values = self._values
- data = tuple((keys[i], values[i]) for i in range(len(self._keys)))
+ data = []
+ for i in range(len(keys)):
+ data.append(keys[i])
+ data.append(values[i])
+ data = tuple(data)
+
if self._next:
return data, self._next
else:
@@ -451,14 +460,18 @@
state, self._next = state
else:
self._next = None
+ state = state[0]
+ if not isinstance(state, tuple):
+ raise TypeError("tuple required for first state element")
+
keys = self._keys
values = self._values
- for k, v in state:
- self._keys.append(k)
- self._values.append(v)
+ for i in range(0, len(state), 2):
+ keys.append(state[i])
+ values.append(state[i+1])
-class Set(_Base, _SetBase):
+class Set(_SetBase):
def __getstate__(self):
data = tuple(self._keys)
@@ -473,6 +486,7 @@
state, self._next = state
else:
self._next = None
+ state = state[0]
self.keys.extend(data)
@@ -503,11 +517,8 @@
self.key = key
self.child = child
-class _Tree(persistent.Persistent):
+class _Tree(_MappingBase):
- def __init__(self, items):
- self.clear()
-
def clear(self):
self._data = []
self._firstbucket = None
@@ -524,7 +535,7 @@
@property
def size(self):
- return len(self._keys)
+ return len(self._data)
def _search(self, key):
data = self._data
@@ -553,7 +564,8 @@
return key in (self._findbucket(self._to_key(key)) or ())
has_key = __contains__
- def iterkeys(min=_marker, max=_marker, excludemin=False, excludemax=False,
+ def iterkeys(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False,
iter_type='iterkeys'):
if not self._data:
return
@@ -631,7 +643,7 @@
def _grow(self, child, index):
self._p_changed = True
- new_child = child.split()
+ new_child = child._split()
self._data.insert(index+1, _TreeItem(new_child.minKey(), new_child))
if len(self._data) > self.MAX_SIZE * 2:
self._split_root()
@@ -643,6 +655,21 @@
self._data = [_TreeItem(None, child)]
self._grow(child, 0)
+ def _split(self, index=None):
+ data = self._data
+ if index is None:
+ index = len(data)//2
+
+ next = self.__class__()
+ next._data = data[index:]
+ first = data[index]
+ del data[index:]
+ if isinstance(first.child, self.__class__):
+ next._firstbucket = first.child._firstbucket
+ else:
+ next._firstbucket = first.child;
+ return next
+
def _del(self, key):
data = self._data
if data:
@@ -694,9 +721,9 @@
for item in data:
if sdata:
sdata.append(item.key)
- sdata.append(item.value)
+ sdata.append(item.child)
else:
- sdata.append(item.value)
+ sdata.append(item.child)
return sdata, self._firstbucket
@@ -781,7 +808,7 @@
def iteritems(self, min=_marker, max=_marker,
excludemin=False, excludemax=False):
- return self.iterkeys(min, max, excludemin, excludemax, 'itervalues')
+ return self.iterkeys(min, max, excludemin, excludemax, 'iteritems')
items = iteritems
@@ -878,13 +905,91 @@
return _set_operation(o1, o2, 0, 0, 1, 1, 0, 1, 0)
def weightedUnion(o1, o2, w1=1, w2=1):
- wtf?
+ if o1 is None:
+ if o2 is None:
+ return 0, o2
+ else:
+ return w2, o2
+ elif o2 is None:
+ return w1, o1
+ else:
+ return 1, _set_operation(o1, o2, 1, 1, w1, w2, 0, 1, 0)
def weightedIntersection(o1, o2):
- pass
+ if o1 is None:
+ if o2 is None:
+ return 0, o2
+ else:
+ return w2, o2
+ elif o2 is None:
+ return w1, o1
+ else:
+ return (
+ w1+w2 if isinstance(o1, Set) else 1,
+ _set_operation(o1, o2, 1, 1, w1, w2, 0, 1, 0),
+ )
-def multiunion(o1, o2):
- pass
+def multiunion(seqs):
+ # XXX simple/slow implementation. Goal is just to get tests to pass.
+ if not seqs:
+ return None
+ result = seqs[0]._set_type()
+ for s in seqs:
+ result.update(s)
+def to_ob(self, v):
+ return v
+def to_int(self, v):
+ pack("i", v)
+ return int(v)
+def to_float(self, v):
+ pack("f", v)
+ return float(v)
+
+def to_long(self, v):
+ pack("q", v)
+ return int(v)
+
+def to_str(l):
+ def to(self, v):
+ assert isinstance(v, str) and len(v) == l
+ return v
+ return to
+
+tos = dict(I=to_int, L=to_long, F=to_float, O=to_ob)
+
+def _import(globals, prefix, bucket_size, tree_size,
+ to_key=None, to_value=None):
+ if to_key is None:
+ to_key = tos[prefix[0]]
+ if to_value is None:
+ to_value = tos[prefix[1]]
+ mc = Bucket.__class__
+ bucket = mc(prefix+'Bucket', (Bucket, ), dict(MAX_SIZE=bucket_size,
+ _to_value=to_value))
+ set = mc(prefix+'Set', (Set, ), dict(MAX_SIZE=bucket_size))
+ tree = mc(prefix+'BTree', (Tree, ), dict(MAX_SIZE=tree_size,
+ _to_value=to_value))
+ treeset = mc(prefix+'TreeSet', (TreeSet, ), dict(MAX_SIZE=tree_size))
+ for c in bucket, set, tree, treeset:
+ c._bucket_type = bucket
+ c._set_type = set
+ c._to_key = to_key
+ c.__module__ = 'BTrees.%sBTree' % prefix
+ globals[c.__name__] = c
+ globals.update(
+ Bucket = bucket,
+ Set = set,
+ BTree = tree,
+ TreeSet = treeset,
+ difference = difference,
+ union = union,
+ intersection = intersection,
+ weightedUnion = weightedUnion,
+ weightedIntersection = weightedIntersection,
+ multiunion = multiunion,
+ using64bits='L' in prefix,
+ )
+ del globals['___BTree']
Modified: ZODB/branches/jim-python-btrees/src/BTrees/fsBTree.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/BTrees/fsBTree.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/BTrees/fsBTree.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -16,4 +16,11 @@
# expected to be "public" excpect to FileStorage.
# hack to overcome dynamic-linking headache.
-from _fsBTree import *
+try:
+ from _fsBTree import *
+except ImportError:
+ import ___BTree
+ ___BTree._import(globals(), 'fs', 500, 500,
+ to_key=___BTree.to_str(2),
+ to_value=___BTree.to_str(6),
+ )
Modified: ZODB/branches/jim-python-btrees/src/ZODB/fsIndex.py
===================================================================
--- ZODB/branches/jim-python-btrees/src/ZODB/fsIndex.py 2011-05-25 07:16:52 UTC (rev 121797)
+++ ZODB/branches/jim-python-btrees/src/ZODB/fsIndex.py 2011-05-25 13:01:57 UTC (rev 121798)
@@ -44,7 +44,7 @@
import cPickle
import struct
-from BTrees._fsBTree import fsBucket
+from BTrees.fsBTree import fsBucket
from BTrees.OOBTree import OOBTree
# convert between numbers and six-byte strings
More information about the checkins
mailing list