[Zodb-checkins] CVS: Zope/lib/python/ZODB - fsIndex.py:1.2.2.1 FileStorage.py:1.76.16.1

[Guido van Rossum]

Update of /cvs-repository/Zope/lib/python/ZODB
In directory cvs.zope.org:/tmp/cvs-serv29969/lib/python/ZODB

Modified Files:
      Tag: Zope-2_5-branch
	FileStorage.py 
Added Files:
      Tag: Zope-2_5-branch
	fsIndex.py 
Log Message:
Add the fsIndex feature (merge from trunk).  This adds a new BTree
variant, fsBTree, a module fsIndex.py that uses it, and some changes
to FileStorage.py that use fsIndex.


=== Added File Zope/lib/python/ZODB/fsIndex.py ===
##############################################################################
#
# 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.0 (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
# 
##############################################################################
"""Implement an OID to File-position (long integer) mapping
"""
# 
# To save space, we do two things:
# 
#     1. We split the keys (OIDS) into 6-byte prefixes and 2-byte suffixes.
#        We use the prefixes as keys in a mapping from prefix to mappings
#        of suffix to data:
# 
#           data is  {prefix -> {suffix -> data}}
# 
#     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
# suffix to 6-byte data. This should reduce the overall memory usage to
# 8-16 bytes per OID.
# 
# We use p64 to convert integers to 8-byte strings and lop off the two
# high-order bytes when saving. On loading data, we add the leading
# bytes back before using U64 to convert the data back to (long)
# integers.

from BTrees._fsBTree import fsBTree as _fsBTree

import struct

# convert between numbers and six-byte strings

_t32 = 1L<< 32

def num2str(n):
    h, l = divmod(long(n), _t32)
    return struct.pack(">HI", h, l)

def str2num(s):
    h, l = struct.unpack(">HI", s)
    if h:
        return (long(h) << 32) + l
    else:
       return l

class fsIndex:

    def __init__(self):
        self._data = {}

    def __getitem__(self, key):
        return str2num(self._data[key[:6]][key[6:]])

    def get(self, key, default=None):
        tree = self._data.get(key[:6], default)
        if tree is default:
            return default
        v = tree.get(key[6:], default)
        if v is default:
            return default
        return str2num(v)

    def __setitem__(self, key, value):
        value = num2str(value)
        treekey = key[:6]
        tree = self._data.get(treekey)
        if tree is None:
            tree = _fsBTree()
            self._data[treekey] = tree
        tree[key[6:]] = value

    def __len__(self):
        r = 0
        for tree in self._data.values():
            r += len(tree)
        return r

    def update(self, mapping):
        for k, v in mapping.items():
            self[k] = v

    def has_key(self, key):
        v=self.get(key, self)
        return v is not self

    def clear(self):
        self._data.clear()

    def keys(self):
        r = []
        for prefix, tree in self._data.items():
            for suffix in tree.keys():
                r.append(prefix + suffix)
        return r

    def items(self):
        r = []
        for prefix, tree in self._data.items():
            for suffix, v in tree.items():
                r.append(((prefix + suffix), str2num(v)))
        return r

    def values(self):
        r = []
        for prefix, tree in self._data.items():
            for v in tree.values():
                r.append(str2num(v))
        return r


=== Zope/lib/python/ZODB/FileStorage.py 1.76 => 1.76.16.1 ===
 #
-# Copyright (c) 2001 Zope Corporation and Contributors. All Rights Reserved.
+# 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.0 (ZPL).  A copy of the ZPL should accompany this distribution.
@@ -130,6 +131,12 @@
 from cPickle import Pickler, Unpickler
 import ConflictResolution
 
+try:
+    from fsIndex import fsIndex
+except ImportError:
+    def fsIndex():
+        return {}
+
 try: from posix import fsync
 except: fsync=None
 
@@ -1218,7 +1225,7 @@
     
             rootl=[z64]
             pop=rootl.pop
-            pindex={}
+            pindex=fsIndex()
             referenced=pindex.has_key
             _load=self._load
             _loada=self._loada
@@ -1248,7 +1255,7 @@
     
             # Index for non-version data.  This is a temporary structure
             # to reduce I/O during packing
-            nvindex={}
+            nvindex=fsIndex()
     
             # Cache a bunch of methods
             seek=file.seek