[Zope3-checkins] SVN: Zope3/trunk/src/zope/bforest/ Add bforest
package, ported from some Zope 2 code. Not part of standard Zope
Gary Poster
gary at zope.com
Wed Feb 2 10:28:36 EST 2005
Log message for revision 29018:
Add bforest package, ported from some Zope 2 code. Not part of standard Zope
3 distro. bforests are objects with dict API comprised of multiple btrees.
Changed:
A Zope3/trunk/src/zope/bforest/
A Zope3/trunk/src/zope/bforest/__init__.py
A Zope3/trunk/src/zope/bforest/bforest.py
A Zope3/trunk/src/zope/bforest/bforest.txt
A Zope3/trunk/src/zope/bforest/tests.py
-=-
Added: Zope3/trunk/src/zope/bforest/__init__.py
===================================================================
--- Zope3/trunk/src/zope/bforest/__init__.py 2005-02-02 12:21:26 UTC (rev 29017)
+++ Zope3/trunk/src/zope/bforest/__init__.py 2005-02-02 15:28:36 UTC (rev 29018)
@@ -0,0 +1,18 @@
+##############################################################################
+#
+# Copyright (c) 2001, 2002 Zope Corporation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+"""objects with dict API comprised of multiple btrees.
+
+$Id$
+"""
+from bforest import IOBForest, OIBForest, IIBForest, OOBForest
Property changes on: Zope3/trunk/src/zope/bforest/__init__.py
___________________________________________________________________
Name: svn:keywords
+ Id
Added: Zope3/trunk/src/zope/bforest/bforest.py
===================================================================
--- Zope3/trunk/src/zope/bforest/bforest.py 2005-02-02 12:21:26 UTC (rev 29017)
+++ Zope3/trunk/src/zope/bforest/bforest.py 2005-02-02 15:28:36 UTC (rev 29018)
@@ -0,0 +1,213 @@
+##############################################################################
+#
+# Copyright (c) 2004 Zope Corporation and Contributors. All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+"""objects with dict API comprised of multiple btrees.
+
+$Id$
+"""
+
+from persistent import Persistent
+from BTrees import IOBTree, OOBTree, OIBTree, IIBTree
+from persistent.list import PersistentList
+
+class AbstractBForest(Persistent):
+
+ _treemodule = None # override
+ _treeclass = None # override
+ _marker = object()
+
+ def __init__(self, d=None, count=2):
+ if count < 0:
+ raise ValueError("count must be 0 or greater")
+ if count == 0:
+ if d is not None:
+ raise ValueError(
+ "cannot set initial values without a bucket")
+ l = PersistentList()
+ else:
+ Tree = self._treeclass
+ if d is not None:
+ first = Tree(d)
+ else:
+ first = Tree()
+ l = [Tree() for i in range(count - 1)]
+ l.insert(0, first)
+ l = PersistentList(l)
+ self.buckets = l
+
+ def __getitem__(self, key):
+ m = self._marker
+ res = self.get(key, m)
+ if res is m:
+ raise KeyError(key)
+ return res
+
+ def __setitem__(self, key, value):
+ self.buckets[0][key] = value
+
+ def get(self, key, default=None):
+ m = self._marker
+ for b in self.buckets:
+ res = b.get(key, m)
+ if res is not m:
+ return res
+ return default
+
+ def __delitem__(self, key):
+ found = False
+ for b in self.buckets:
+ try:
+ del b[key]
+ except KeyError:
+ pass
+ else:
+ found = True
+ if not found:
+ raise KeyError(key)
+
+ def update(self, d):
+ self.buckets[0].update(d)
+
+ def keys(self):
+ union = self._treemodule.union
+ buckets = self.buckets
+ if len(buckets) == 1:
+ res = buckets[0].keys()
+ else:
+ res = union(buckets[0], buckets[1])
+ for b in buckets[2:]:
+ res = union(res, b)
+ return res
+
+ def tree(self):
+ # convert to a tree; do as much in C as possible.
+ buckets = self.buckets
+ res = self._treeclass(buckets[-1])
+ for b in buckets[-2::-1]:
+ res.update(b)
+ return res
+
+ def items(self):
+ return self.tree().items()
+
+ def values(self):
+ return self.tree().values()
+
+ def iteritems(self):
+ for key in self.keys():
+ yield key, self[key]
+
+ def iterkeys(self):
+ return iter(self.keys())
+
+ __iter__ = iterkeys
+
+ def itervalues(self):
+ for key in self.keys():
+ yield self[key]
+
+ def has_key(self, key):
+ try:
+ self[key]
+ except KeyError:
+ return False
+ else:
+ return True
+
+ def __cmp__(self, d):
+ # this is probably not the most efficient approach, but I'm not sure
+ # what is, and this is certainly among the simplest. Don't do
+ # comparisons with large bforests unless you are willing to pay the
+ # price. Improvements welcome.
+ return cmp(dict(self), dict(d))
+
+ def __len__(self):
+ return len(self.tree())
+
+ def setdefault(self, key, failobj=None):
+ try:
+ res = self[key]
+ except KeyError:
+ res = self[key] = failobj
+ return res
+
+ def pop(self, key, d=_marker):
+ try:
+ res = self[key]
+ except KeyError:
+ if d is self._marker:
+ raise KeyError(key)
+ else:
+ return d
+ else:
+ del self[key]
+ return res
+
+ def popitem(self):
+ for b in self.buckets:
+ try:
+ key = b.minKey()
+ except ValueError:
+ pass
+ else:
+ val = b[key]
+ del b[key]
+ return key, val
+ else:
+ raise KeyError('popitem():dictionary is empty')
+
+ def __contains__(self, key):
+ for b in self.buckets:
+ if b.has_key(key):
+ return True
+ return False
+
+ def copy(self):
+ # this makes an exact copy, including the individual state of each
+ # bucket. If you want a dict, cast it to a dict, or if you want
+ # another one of these but with all of the keys in the first bucket,
+ # call obj.__class__(obj)
+ copy = self.__class__(count=0)
+ copy.buckets = [self._treeclass(t) for t in self.buckets]
+ return copy
+
+ def clear(self):
+ for b in self.buckets:
+ b.clear()
+
+ def __nonzero__(self):
+ for b in self.buckets:
+ if bool(b):
+ return True
+ return False
+
+ def rotateBucket(self):
+ buckets = self.buckets
+ b = buckets.pop()
+ b.clear()
+ buckets.insert(0, b)
+
+class IOBForest(AbstractBForest):
+ _treemodule = IOBTree
+ _treeclass = IOBTree.IOBTree
+
+class OIBForest(AbstractBForest):
+ _treemodule = OIBTree
+ _treeclass = OIBTree.OIBTree
+
+class OOBForest(AbstractBForest):
+ _treemodule = OOBTree
+ _treeclass = OOBTree.OOBTree
+
+class IIBForest(AbstractBForest):
+ _treemodule = IIBTree
+ _treeclass = IIBTree.IIBTree
Property changes on: Zope3/trunk/src/zope/bforest/bforest.py
___________________________________________________________________
Name: svn:keywords
+ Id
Added: Zope3/trunk/src/zope/bforest/bforest.txt
===================================================================
--- Zope3/trunk/src/zope/bforest/bforest.txt 2005-02-02 12:21:26 UTC (rev 29017)
+++ Zope3/trunk/src/zope/bforest/bforest.txt 2005-02-02 15:28:36 UTC (rev 29018)
@@ -0,0 +1,201 @@
+bforests are dictionary-like objects that use multiple BTrees for a backend and
+support rotation of the composite trees. This supports various implementations
+of timed member expirations, enabling caches and semi-persistent storage. A
+useful and simple subclass would be to promote a key-value pair to the
+first (newest) bucket whenever the key is accessed, for instance. It also is
+useful with disabling the rotation capability.
+
+Like btrees, bforests come in four flavors: Integer-Integer (IIBForest),
+Integer-Object (IOBForest), Object-Integer (OIBForest), and Object-Object
+(OOBForest). The examples here will deal with them in the abstract: we will
+create classes from the imaginary and representative BForest class, and
+generate keys from KeyGenerator and values from ValueGenerator. From the
+examples you should be able to extrapolate usage of all four types.
+
+First let's instantiate a bforest and look at an empty example. By default,
+a new bforest creates two composite btree buckets.
+
+>>> d = BForest()
+>>> list(d.keys())
+[]
+>>> list(d.values())
+[]
+>>> len(d.buckets)
+2
+>>> dummy_key = KeyGenerator()
+>>> d.get(dummy_key)
+>>> d.get(dummy_key, 42)
+42
+
+Now we'll populate it. We'll first create a dictionary we'll use to compare.
+
+>>> original = {}
+>>> for i in range(10):
+... original[KeyGenerator()] = ValueGenerator()
+...
+>>> d.update(original)
+>>> d == original
+True
+>>> d_keys = list(d.keys())
+>>> d_keys.sort()
+>>> o_keys = original.keys()
+>>> o_keys.sort()
+>>> d_keys == o_keys
+True
+>>> d_values = list(d.values())
+>>> d_values.sort()
+>>> o_values = original.values()
+>>> o_values.sort()
+>>> o_values == d_values
+True
+>>> d_items = list(d.items())
+>>> d_items.sort()
+>>> o_items = original.items()
+>>> o_items.sort()
+>>> o_items == d_items
+True
+>>> key, value = d.popitem()
+>>> value == original.pop(key)
+True
+>>> key, value = original.popitem()
+>>> value == d.pop(key)
+True
+>>> len(d) == len(original)
+True
+
+Now let's rotate the buckets.
+
+>>> d.rotateBucket()
+
+...and we'll do the exact same test as above, first.
+
+>>> d == original
+True
+>>> d_keys = list(d.keys())
+>>> d_keys.sort()
+>>> o_keys = original.keys()
+>>> o_keys.sort()
+>>> d_keys == o_keys
+True
+>>> d_values = list(d.values())
+>>> d_values.sort()
+>>> o_values = original.values()
+>>> o_values.sort()
+>>> o_values == d_values
+True
+>>> d_items = list(d.items())
+>>> d_items.sort()
+>>> o_items = original.items()
+>>> o_items.sort()
+>>> o_items == d_items
+True
+>>> key, value = d.popitem()
+>>> value == original.pop(key)
+True
+>>> key, value = original.popitem()
+>>> value == d.pop(key)
+True
+>>> len(d) == len(original)
+True
+
+Now we'll make a new dictionary to represent changes made after the bucket
+rotation.
+
+>>> second = {}
+>>> for i in range(10):
+... key = KeyGenerator()
+... value = ValueGenerator()
+... second[key] = value
+... d[key] = value
+...
+>>> original.update(second)
+
+...and we'll do almost the exact same test as above, first.
+
+>>> d == original
+True
+>>> d_keys = list(d.keys())
+>>> d_keys.sort()
+>>> o_keys = original.keys()
+>>> o_keys.sort()
+>>> d_keys == o_keys
+True
+>>> d_values = list(d.values())
+>>> d_values.sort()
+>>> o_values = original.values()
+>>> o_values.sort()
+>>> o_values == d_values
+True
+>>> d_items = list(d.items())
+>>> d_items.sort()
+>>> o_items = original.items()
+>>> o_items.sort()
+>>> o_items == d_items
+True
+>>> key, value = d.popitem()
+>>> ignore = second.pop(key, None) # keep second up-to-date
+>>> value == original.pop(key)
+True
+>>> key, value = original.popitem()
+>>> ignore = second.pop(key, None) # keep second up-to-date
+>>> value == d.pop(key)
+True
+>>> len(d) == len(original)
+True
+
+Now if we rotate the buckets, the first set of items will be gone, but the
+second will remain.
+
+>>> d.rotateBucket()
+>>> d == original
+False
+>>> d == second
+True
+
+Let's set a value, check the copy behavior, and then rotate it one more time.
+
+>>> third = {KeyGenerator(): ValueGenerator()}
+>>> d.update(third)
+>>> copy = d.copy()
+>>> copy == d
+True
+>>> copy != second # because second doesn't have the values of third
+True
+>>> list(copy.buckets[0].items()) == list(d.buckets[0].items())
+True
+>>> list(copy.buckets[1].items()) == list(d.buckets[1].items())
+True
+>>> copy[KeyGenerator()] = ValueGenerator()
+>>> copy == d
+False
+>>> d.rotateBucket()
+>>> d == third
+True
+>>> d.clear()
+>>> d == BForest() == {}
+True
+
+>>> d.update(second)
+
+We'll make a value in one bucket that we'll override in another.
+
+>>> d[third.keys()[0]] = ValueGenerator()
+>>> d.rotateBucket()
+>>> d.update(third)
+>>> second.update(third)
+>>> d == second
+True
+>>> second == d
+True
+
+The tree method converts the bforest to a btree as efficiently as I know how
+for a common case of more items in buckets than buckets.
+
+>>> tree = d.tree()
+>>> d_items = list(d.items())
+>>> d_items.sort()
+>>> t_items = list(tree.items())
+>>> t_items.sort()
+>>> t_items == d_items
+True
+
Property changes on: Zope3/trunk/src/zope/bforest/bforest.txt
___________________________________________________________________
Name: svn:keywords
+ Id
Added: Zope3/trunk/src/zope/bforest/tests.py
===================================================================
--- Zope3/trunk/src/zope/bforest/tests.py 2005-02-02 12:21:26 UTC (rev 29017)
+++ Zope3/trunk/src/zope/bforest/tests.py 2005-02-02 15:28:36 UTC (rev 29018)
@@ -0,0 +1,68 @@
+##############################################################################
+#
+# Copyright (c) 2004 Zope Corporation and Contributors. All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+"""test bforests
+
+$Id$
+"""
+
+import unittest
+from zope import bforest
+from zope.testing import doctest
+
+def StringGenerator(src='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'):
+ "infinite-ish unique string generator"
+ for el in src:
+ yield el
+ for pre in StringGenerator(src):
+ for el in src:
+ yield pre + el
+
+def NumberGenerator(number=0, interval=1):
+ "infinite-ish unique number generator"
+ while 1:
+ yield number
+ number += interval
+
+def test_suite():
+ suite = unittest.TestSuite()
+ numgen = iter(NumberGenerator()).next
+ strgen = iter(StringGenerator()).next
+ suite.addTest(
+ doctest.DocFileSuite(
+ 'bforest.txt',
+ globs={'BForest': bforest.IOBForest,
+ 'KeyGenerator': numgen,
+ 'ValueGenerator': strgen}))
+ suite.addTest(
+ doctest.DocFileSuite(
+ 'bforest.txt',
+ globs={'BForest': bforest.OIBForest,
+ 'KeyGenerator': strgen,
+ 'ValueGenerator': numgen}))
+ suite.addTest(
+ doctest.DocFileSuite(
+ 'bforest.txt',
+ globs={'BForest': bforest.IIBForest,
+ 'KeyGenerator': numgen,
+ 'ValueGenerator': numgen}))
+ suite.addTest(
+ doctest.DocFileSuite(
+ 'bforest.txt',
+ globs={'BForest': bforest.OOBForest,
+ 'KeyGenerator': strgen,
+ 'ValueGenerator': strgen}))
+ return suite
+
+if __name__ == '__main__':
+ import unittest
+ unittest.main(defaultTest='test_suite')
Property changes on: Zope3/trunk/src/zope/bforest/tests.py
___________________________________________________________________
Name: svn:keywords
+ Id
More information about the Zope3-Checkins
mailing list