[Zope-Checkins] CVS: Packages/ZODB - fsIndex.py:188.8.131.52
tim.one at comcast.net
Thu Feb 24 17:41:55 EST 2005
Update of /cvs-repository/Packages/ZODB
In directory cvs.zope.org:/tmp/cvs-serv2861/ZODB
Give fsIndex an efficient maxKey() implementation.
This will (in a later checkin) be used to give FileStorage an "obviously
correct" way to determine the largest oid used in an .fs.index file.
=== Packages/ZODB/fsIndex.py 1.4 => 184.108.40.206 ===
--- Packages/ZODB/fsIndex.py:1.4 Tue Dec 3 13:45:16 2002
+++ Packages/ZODB/fsIndex.py Thu Feb 24 17:41:25 2005
@@ -25,7 +25,7 @@
# 2. We limit the data size to 48 bits. This should allow databases
# as large as 256 terabytes.
-# Mostof the space is consumed by items in the mappings from 2-byte
+# Most of the space is consumed by items in the mappings from 2-byte
# suffix to 6-byte data. This should reduce the overall memory usage to
# 8-16 bytes per OID.
@@ -125,3 +125,32 @@
for v in tree.values():
+ def maxKey(self):
+ # This is less general than the BTree method of the same name: we
+ # only care about the largest key in the entire tree. By
+ # construction, that's the largest oid in use in the associated
+ # FileStorage.
+ keys = self._data.keys()
+ if not keys:
+ # This is the same exception a BTree maxKey() raises when the
+ # tree is empty.
+ raise ValueError("empty tree")
+ # We expect that keys is small, since each fsBTree in _data.values()
+ # can hold as many as 2**16 = 64K entries. So this max() should go
+ # fast too. Regardless, there's no faster way to find the largest
+ # prefix.
+ biggest_prefix = max(keys)
+ tree = self._data[biggest_prefix]
+ # Obscure: what if tree is actually empty? We're relying here on
+ # that this class doesn't implement __delitem__: once a key gets
+ # into an fsIndex, the only way it can go away is by invoking
+ # clear(). Therefore nothing in _data.values() is ever empty.
+ # Note that because `tree` is an fsBTree, its maxKey() method is very
+ # efficient.
+ assert tree
+ return biggest_prefix + tree.maxKey()
More information about the Zope-Checkins