[Checkins] SVN: zope.bforest/trunk/ bforest files
Gary Poster
gary at zope.com
Mon Sep 11 22:05:45 EDT 2006
Log message for revision 70109:
bforest files
Changed:
_U zope.bforest/trunk/
A zope.bforest/trunk/README.txt
A zope.bforest/trunk/bootstrap.py
A zope.bforest/trunk/buildout.cfg
A zope.bforest/trunk/setup.py
A zope.bforest/trunk/src/zope/__init__.py
A zope.bforest/trunk/src/zope/bforest/__init__.py
A zope.bforest/trunk/src/zope/bforest/bforest.py
A zope.bforest/trunk/src/zope/bforest/bforest.txt
A zope.bforest/trunk/src/zope/bforest/tests.py
-=-
Property changes on: zope.bforest/trunk
___________________________________________________________________
Name: svn:ignore
+ develop-eggs
bin
parts
.installed.cfg
build
dist
Added: zope.bforest/trunk/README.txt
===================================================================
--- zope.bforest/trunk/README.txt 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/README.txt 2006-09-12 02:05:44 UTC (rev 70109)
@@ -0,0 +1,2 @@
+Mappings based transparently on multiple BTrees; good for rotating caches and
+logs.
Property changes on: zope.bforest/trunk/README.txt
___________________________________________________________________
Name: svn:eol-style
+ native
Added: zope.bforest/trunk/bootstrap.py
===================================================================
--- zope.bforest/trunk/bootstrap.py 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/bootstrap.py 2006-09-12 02:05:44 UTC (rev 70109)
@@ -0,0 +1,52 @@
+##############################################################################
+#
+# Copyright (c) 2006 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.
+#
+##############################################################################
+"""Bootstrap a buildout-based project
+
+Simply run this script in a directory containing a buildout.cfg.
+The script accepts buildout command-line options, so you can
+use the -c option to specify an alternate configuration file.
+
+$Id: bootstrap.py 69908 2006-08-31 21:53:00Z jim $
+"""
+
+import os, shutil, sys, tempfile, urllib2
+
+tmpeggs = tempfile.mkdtemp()
+
+ez = {}
+exec urllib2.urlopen('http://peak.telecommunity.com/dist/ez_setup.py'
+ ).read() in ez
+ez['use_setuptools'](to_dir=tmpeggs, download_delay=0)
+
+import pkg_resources
+
+cmd = 'from setuptools.command.easy_install import main; main()'
+if sys.platform == 'win32':
+ cmd = '"%s"' % cmd # work around spawn lamosity on windows
+
+ws = pkg_resources.working_set
+assert os.spawnle(
+ os.P_WAIT, sys.executable, sys.executable,
+ '-c', cmd, '-mqNxd', tmpeggs, 'zc.buildout',
+ dict(os.environ,
+ PYTHONPATH=
+ ws.find(pkg_resources.Requirement.parse('setuptools')).location
+ ),
+ ) == 0
+
+ws.add_entry(tmpeggs)
+ws.require('zc.buildout')
+import zc.buildout.buildout
+zc.buildout.buildout.main(sys.argv[1:] + ['bootstrap'])
+shutil.rmtree(tmpeggs)
Added: zope.bforest/trunk/buildout.cfg
===================================================================
--- zope.bforest/trunk/buildout.cfg 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/buildout.cfg 2006-09-12 02:05:44 UTC (rev 70109)
@@ -0,0 +1,15 @@
+[buildout]
+develop = .
+parts = test py
+
+find-links = http://download.zope.org/distribution/
+
+[test]
+recipe = zc.recipe.testrunner
+eggs = zope.bforest
+
+[py]
+recipe = zc.recipe.egg
+eggs = setuptools
+interpreter = py
+scripts = py
Property changes on: zope.bforest/trunk/buildout.cfg
___________________________________________________________________
Name: svn:eol-style
+ native
Added: zope.bforest/trunk/setup.py
===================================================================
--- zope.bforest/trunk/setup.py 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/setup.py 2006-09-12 02:05:44 UTC (rev 70109)
@@ -0,0 +1,20 @@
+from setuptools import setup
+
+setup(
+ name="zope.bforest",
+ version="1.0",
+ license="ZPL 2.1",
+ author="Zope Project",
+ author_email="zope3-dev at zope.org",
+
+ namespace_packages=["zope"],
+ packages=["zope", "zope.bforest"],
+ package_dir={"": "src"},
+ include_package_data=True,
+ install_requires=["zope.interface", "ZODB3"],
+ tests_require=["zope.testing"],
+ description=open('README.txt').read(),
+ long_description=open("src/zope/bforest/bforest.txt").read(),
+ keywords="zope zope3",
+ zip_safe=False
+ )
Added: zope.bforest/trunk/src/zope/__init__.py
===================================================================
--- zope.bforest/trunk/src/zope/__init__.py 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/src/zope/__init__.py 2006-09-12 02:05:44 UTC (rev 70109)
@@ -0,0 +1,7 @@
+# this is a namespace package
+try:
+ import pkg_resources
+ pkg_resources.declare_namespace(__name__)
+except ImportError:
+ import pkgutil
+ __path__ = pkgutil.extend_path(__path__, __name__)
Added: zope.bforest/trunk/src/zope/bforest/__init__.py
===================================================================
--- zope.bforest/trunk/src/zope/bforest/__init__.py 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/src/zope/bforest/__init__.py 2006-09-12 02:05:44 UTC (rev 70109)
@@ -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: __init__.py 29023 2005-02-02 21:39:04Z poster $
+"""
+from bforest import IOBForest, OIBForest, IIBForest, OOBForest
Added: zope.bforest/trunk/src/zope/bforest/bforest.py
===================================================================
--- zope.bforest/trunk/src/zope/bforest/bforest.py 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/src/zope/bforest/bforest.py 2006-09-12 02:05:44 UTC (rev 70109)
@@ -0,0 +1,249 @@
+##############################################################################
+#
+# 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: bforest.py 33325 2005-07-15 01:09:43Z poster $
+"""
+
+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 __eq__(self, other):
+ if not isinstance(other, dict):
+ if (isinstance(other, AbstractBForest) and
+ self._treemodule is not other._treemodule):
+ return False
+ try:
+ other = dict(other)
+ except (TypeError, ValueError):
+ return False
+ return dict(self)==other # :-/
+
+ def __gt__(self, other):
+ if not isinstance(other, dict):
+ try:
+ other = dict(other)
+ except TypeError:
+ return id(self) > id(other)
+ return dict(self) > other
+
+ def __lt__(self, other):
+ if not isinstance(other, dict):
+ try:
+ other = dict(other)
+ except TypeError:
+ return id(self) < id(other)
+ return dict(self) < other
+
+ def __ge__(self, other):
+ if not isinstance(other, dict):
+ try:
+ other = dict(other)
+ except TypeError:
+ return id(self) >= id(other)
+ return dict(self) >= other
+
+ def __le__(self, other):
+ if not isinstance(other, dict):
+ try:
+ other = dict(other)
+ except TypeError:
+ return id(self) <= id(other)
+ return dict(self) <= other
+
+ 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
Added: zope.bforest/trunk/src/zope/bforest/bforest.txt
===================================================================
--- zope.bforest/trunk/src/zope/bforest/bforest.txt 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/src/zope/bforest/bforest.txt 2006-09-12 02:05:44 UTC (rev 70109)
@@ -0,0 +1,253 @@
+===========
+BForest API
+===========
+
+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
+
+Finally, comparisons work similarly to dicts but in a simpleminded
+way--improvements welcome! We've already looked at a lot of examples above,
+but here are some additional cases
+
+ >>> d == None
+ False
+ >>> d == [1, 2]
+ False
+ >>> d != None
+ True
+ >>> None == d
+ False
+ >>> d != None
+ True
+ >>> d >= second
+ True
+ >>> d >= dict(second)
+ True
+ >>> d <= second
+ True
+ >>> d <= dict(second)
+ True
+ >>> d > second
+ False
+ >>> d > dict(second)
+ False
+ >>> d < second
+ False
+ >>> d > dict(second)
+ False
+ >>> second.popitem()[0] in d
+ True
+ >>> d > second
+ True
+ >>> d < second
+ False
+ >>> d >= second
+ True
+ >>> d <= second
+ False
+ >>> second < d
+ True
+ >>> second > d
+ False
+ >>> second <= d
+ True
+ >>> second >= d
+ False
Property changes on: zope.bforest/trunk/src/zope/bforest/bforest.txt
___________________________________________________________________
Name: svn:eol-style
+ native
Added: zope.bforest/trunk/src/zope/bforest/tests.py
===================================================================
--- zope.bforest/trunk/src/zope/bforest/tests.py 2006-09-12 01:47:10 UTC (rev 70108)
+++ zope.bforest/trunk/src/zope/bforest/tests.py 2006-09-12 02:05:44 UTC (rev 70109)
@@ -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: tests.py 29018 2005-02-02 15:28:36Z poster $
+"""
+
+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')
More information about the Checkins
mailing list