[Zope3-checkins] CVS: Zope3/src/zodb/storage - __init__.py:1.2 _helper.c:1.2 base.py:1.2 bdbfull.py:1.2 bdbminimal.py:1.2 file.py:1.2 fsdump.py:1.2 fsindex.py:1.2 fsrecover.py:1.2 mapping.py:1.2

Jim Fulton jim@zope.com
Wed, 25 Dec 2002 09:13:52 -0500


Update of /cvs-repository/Zope3/src/zodb/storage
In directory cvs.zope.org:/tmp/cvs-serv15352/src/zodb/storage

Added Files:
	__init__.py _helper.c base.py bdbfull.py bdbminimal.py file.py 
	fsdump.py fsindex.py fsrecover.py mapping.py 
Log Message:
Grand renaming:

- Renamed most files (especially python modules) to lower case.

- Moved views and interfaces into separate hierarchies within each
  project, where each top-level directory under the zope package
  is a separate project.

- Moved everything to src from lib/python.

  lib/python will eventually go away. I need access to the cvs
  repository to make this happen, however.

There are probably some bits that are broken. All tests pass
and zope runs, but I haven't tried everything. There are a number
of cleanups I'll work on tomorrow.



=== Zope3/src/zodb/storage/__init__.py 1.1 => 1.2 ===
--- /dev/null	Wed Dec 25 09:13:51 2002
+++ Zope3/src/zodb/storage/__init__.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,2 @@
+#
+# This file is necessary to make this directory a package.


=== Zope3/src/zodb/storage/_helper.c 1.1 => 1.2 ===
--- /dev/null	Wed Dec 25 09:13:51 2002
+++ Zope3/src/zodb/storage/_helper.c	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,73 @@
+/*****************************************************************************
+
+  Copyright (c) 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
+
+ ****************************************************************************/
+
+#include <Python.h>
+
+/* This helper only works for Python 2.2 and beyond.  If we're using an
+ * older version of Python, stop out now so we don't leave a broken, but
+ * compiled and importable module laying about.  Full.py has a workaround
+ * for when this extension isn't available.
+ */
+#if PY_VERSION_HEX < 0x020200F0
+#error "Must be using at least Python 2.2"
+#endif
+
+static PyObject*
+helper_incr(PyObject* self, PyObject* args)
+{
+    PyObject *pylong, *incr, *sum;
+    char *s, x[8];
+    int len, res;
+
+    if (!PyArg_ParseTuple(args, "s#O:incr", &s, &len, &incr))
+        return NULL;
+
+    assert(len == 8);
+
+    /* There seems to be no direct route from byte array to long long, so
+     * first convert it to a PyLongObject*, then convert /that/ thing to a
+     * long long.
+     */
+    pylong = _PyLong_FromByteArray(s, len,
+                                   0 /* big endian */,
+                                   0 /* unsigned */);
+    
+    if (!pylong)
+        return NULL;
+
+    sum = PyNumber_Add(pylong, incr);
+    if (!sum)
+        return NULL;
+
+    res = _PyLong_AsByteArray((PyLongObject*)sum, x, 8,
+                              0 /* big endian */,
+                              0 /* unsigned */);
+    if (res < 0)
+        return NULL;
+
+    return PyString_FromStringAndSize(x, 8);
+}
+
+
+static PyMethodDef helper_methods[] = {
+    {"incr", helper_incr, METH_VARARGS},
+    {NULL, NULL}                             /* sentinel */
+};
+
+
+DL_EXPORT(void)
+init_helper(void)
+{
+    (void)Py_InitModule("_helper", helper_methods);
+}


=== Zope3/src/zodb/storage/base.py 1.1 => 1.2 === (746/846 lines abridged)
--- /dev/null	Wed Dec 25 09:13:51 2002
+++ Zope3/src/zodb/storage/base.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,843 @@
+##############################################################################
+#
+# 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
+#
+##############################################################################
+
+
+
+"""Handy standard storage machinery
+
+$Id$
+"""
+
+__metaclass__ = type
+
+import threading
+from zodb import interfaces
+from zodb.timestamp import newTimeStamp, TimeStamp
+from zodb.interfaces import ITransactionAttrs
+z64='\0'*8
+
+class BaseStorage:
+    _transaction = None # Transaction that is being committed
+    _serial = z64       # Transaction serial number
+    _tstatus = ' '      # Transaction status, used for copying data
+    _is_read_only = False
+
+    def __init__(self, name, base=None):
+        self._name = name
+
+        # Allocate locks:
+        l=threading.RLock()
+        self._lock_acquire = l.acquire
+        self._lock_release = l.release
+        l=threading.Lock()
+        self._commit_lock_acquire = l.acquire
+        self._commit_lock_release = l.release
+
+        self._ts = newTimeStamp()

[-=- -=- -=- 746 lines omitted -=- -=- -=-]

+    try:
+        shutil.rmtree(envdir)
+    except OSError, e:
+        if e.errno <> errno.ENOENT:
+            raise
+
+
+
+class _WorkThread(threading.Thread):
+    NAME = 'worker'
+
+    def __init__(self, storage, event, checkinterval):
+        threading.Thread.__init__(self)
+        self._storage = storage
+        self._event = event
+        self._interval = checkinterval
+        # Bookkeeping.  _nextcheck is useful as a non-public interface aiding
+        # testing.  See test_autopack.py.
+        self._stop = False
+        self._nextcheck = checkinterval
+        # We don't want these threads to hold up process exit.  That could
+        # lead to corrupt databases, but recovery should ultimately save us.
+        self.setDaemon(True)
+
+    def run(self):
+        name = self.NAME
+        self._storage.log('%s thread started', name)
+        while not self._stop:
+            now = time.time()
+            if now >= self._nextcheck:
+                self._storage.log('running %s', name)
+                self._dowork()
+                # Recalculate `now' because _dowork() could have taken a
+                # while.  time.time() can be expensive, but oh well.
+                self._nextcheck = time.time() + self._interval
+            # Block w/ timeout on the shutdown event.
+            self._event.wait(self._interval)
+            self._stop = self._event.isSet()
+        self._storage.log('%s thread finished', name)
+
+    def _dowork(self):
+        pass
+
+
+
+class _Checkpoint(_WorkThread):
+    NAME = 'checkpointing'
+
+    def _dowork(self):
+        self._storage.docheckpoint()


=== Zope3/src/zodb/storage/bdbfull.py 1.1 => 1.2 === (1780/1880 lines abridged)
--- /dev/null	Wed Dec 25 09:13:51 2002
+++ Zope3/src/zodb/storage/bdbfull.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,1877 @@
+##############################################################################
+#
+# 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
+#
+##############################################################################
+
+"""Berkeley storage with full undo and versioning support.
+"""
+
+__version__ = '$Revision$'.split()[-2:][0]
+
+import time
+import cPickle as pickle
+from struct import pack, unpack
+
+# This uses the Dunn/Kuchling PyBSDDB v3 extension module available from
+# http://pybsddb.sourceforge.net.  It is compatible with release 3.4 of
+# PyBSDDB3.  The only recommended version of BerkeleyDB is 4.0.14.
+from bsddb3 import db
+
+from zodb import interfaces
+from zodb.utils import p64, u64
+from zodb.serialize import findrefs
+from zodb.timestamp import TimeStamp
+from zodb.conflict import ConflictResolvingStorage, ResolvedSerial
+
+# BerkeleyBase.BerkeleyBase class provides some common functionality for both
+# the Full and Minimal implementations.  It in turn inherits from
+# zodb.storage.base.BaseStorage which itself provides some common storage
+# functionality.
+from zodb.storage.base import BerkeleyBase, PackStop, _WorkThread
+from zodb.storage._helper import incr
+
+ABORT = 'A'
+COMMIT = 'C'
+PRESENT = 'X'
+ZERO = '\0'*8
+
+# Special flag for uncreated objects (i.e. Does Not Exist)

[-=- -=- -=- 1780 lines omitted -=- -=- -=-]

+        # Let IndexError percolate up
+        oid = self._oids.pop()
+        data, version, lrevid = self._storage._loadSerialEx(oid, self.tid)
+        return _Record(oid, self.tid, version, data, lrevid)
+
+
+
+class _Record:
+    # Object Id
+    oid = None
+    # Object serial number (i.e. revision id)
+    serial = None
+    # Version string
+    version = None
+    # Data pickle
+    data = None
+    # The pointer to the transaction containing the pickle data, if not None
+    data_txn = None
+
+    def __init__(self, oid, serial, version, data, data_txn):
+        self.oid = oid
+        self.serial = serial
+        self.version = version
+        self.data = data
+        self.data_txn = data_txn
+
+
+
+class _Autopack(_WorkThread):
+    NAME = 'autopacking'
+
+    def __init__(self, storage, event,
+                 frequency, packtime, classicpack,
+                 lastpacktime):
+        _WorkThread.__init__(self, storage, event, frequency)
+        self._packtime = packtime
+        self._classicpack = classicpack
+        # Bookkeeping
+        self._lastclassic = 0
+
+    def _dowork(self):
+        # Should we do a classic pack this time?
+        if self._classicpack <= 0:
+            classicp = False
+        else:
+            v = (self._lastclassic + 1) % self._classicpack
+            self._lastclassic = v
+            classicp = not v
+        # Run the autopack phase
+        self._storage.autopack(time.time() - self._packtime, classicp)


=== Zope3/src/zodb/storage/bdbminimal.py 1.1 => 1.2 === (431/531 lines abridged)
--- /dev/null	Wed Dec 25 09:13:51 2002
+++ Zope3/src/zodb/storage/bdbminimal.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,528 @@
+##############################################################################
+#
+# 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
+#
+##############################################################################
+
+"""Berkeley storage without undo or versioning.
+"""
+
+__version__ = '$Revision$'[-2:][0]
+
+# This uses the Dunn/Kuchling PyBSDDB v3 extension module available from
+# http://pybsddb.sourceforge.net.  It is compatible with release 3.4 of
+# PyBSDDB3.
+from bsddb3 import db
+
+from zodb import interfaces
+from zodb.utils import p64, u64
+from zodb.serialize import findrefs
+from zodb.conflict import ConflictResolvingStorage, ResolvedSerial
+
+# BerkeleyBase class provides some common functionality for BerkeleyDB-based
+# storages.  It in turn inherits from BaseStorage which itself provides some
+# common storage functionality.
+from zodb.storage.base import BerkeleyBase, PackStop, _WorkThread
+
+ABORT = 'A'
+COMMIT = 'C'
+PRESENT = 'X'
+ZERO = '\0'*8
+
+
+
+class BDBMinimalStorage(BerkeleyBase, ConflictResolvingStorage):
+    def _setupDBs(self):
+        # Data Type Assumptions:
+        #
+        # - Object ids (oid) are 8-bytes
+        # - Objects have revisions, with each revision being identified by a

[-=- -=- -=- 431 lines omitted -=- -=- -=-]

+                    data = rec[1]
+                    c.delete()
+                    rec = c.next()
+                    deltas = {}
+                    self._update(deltas, data, -1)
+                    for oid, delta in deltas.items():
+                        refcount = u64(self._refcounts.get(oid, ZERO)) + delta
+                        if refcount <= 0:
+                            self._oidqueue.append(oid, txn)
+                        else:
+                            self._refcounts.put(oid, p64(refcount), txn=txn)
+            finally:
+                c.close()
+            # We really do want this down here, since _decrefPickle() could
+            # add more items to the queue.
+            orec = self._oidqueue.consume(txn)
+        assert len(self._oidqueue) == 0
+
+    #
+    # Stuff we don't support
+    #
+
+    def supportsTransactionalUndo(self):
+        return False
+
+    def supportsUndo(self):
+        return False
+
+    def supportsVersions(self):
+        return False
+
+    # Don't implement these
+    #
+    # versionEmpty(self, version)
+    # versions(self, max=None)
+    # loadSerial(self, oid, serial)
+    # getSerial(self, oid)
+    # transactionalUndo(self, tid, transaction)
+    # undoLog(self, first=0, last=-20, filter=None)
+    # history(self, oid, version=None, size=1, filter=None)
+    # iterator(self, start=None, stop=None)
+
+
+
+class _Autopack(_WorkThread):
+    NAME = 'autopacking'
+
+    def _dowork(self):
+        # Run the autopack phase
+        self._storage.pack('ignored')


=== Zope3/src/zodb/storage/file.py 1.1 => 1.2 === (2244/2344 lines abridged)
--- /dev/null	Wed Dec 25 09:13:51 2002
+++ Zope3/src/zodb/storage/file.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,2341 @@
+##############################################################################
+#
+# 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.
+#
+##############################################################################
+"""File-based ZODB storage
+
+Files are arranged as follows.
+
+  - The first 4 bytes are a file identifier.
+
+  - The rest of the file consists of a sequence of transaction
+    "records".
+
+A transaction record consists of:
+
+  - 8-byte transaction id, which is also a time stamp.
+
+  - 8-byte transaction record length - 8.
+
+  - 1-byte status code
+
+  - 2-byte length of user name
+
+  - 2-byte length of description
+
+  - 2-byte length of extension attributes
+
+  -   user name
+
+  -   description
+
+  -   extension attributes
+
+  * A sequence of data records
+
+  - 8-byte redundant transaction length -8
+
+A data record consists of

[-=- -=- -=- 2244 lines omitted -=- -=- -=-]

+            d = self.file.read(dl)
+        e = {}
+        if el:
+            try:
+                e = loads(self.file.read(el))
+            except:
+                pass
+        d = {'id': base64.encodestring(tid).rstrip(),
+             'time': TimeStamp(tid).timeTime(),
+             'user_name': u,
+             'description': d}
+        d.update(e)
+        return d
+
+class DataHeader:
+    """Header for a data record."""
+
+    __slots__ = ("oid", "serial", "prev", "tloc", "vlen", "plen", "back",
+                 # These three attributes are only defined when vlen > 0
+                 "pnv", "vprev", "version")
+
+    version = ""
+    back = 0
+
+    def __init__(self, oid, serial, prev, tloc, vlen, plen):
+        self.oid = oid
+        self.serial = serial
+        self.prev = prev
+        self.tloc = tloc
+        self.vlen = vlen
+        self.plen = plen
+
+    def fromString(cls, s):
+        return cls(*struct.unpack(DATA_HDR, s))
+
+    fromString = classmethod(fromString)
+
+    def parseVersion(self, buf):
+        self.pnv, self.vprev = struct.unpack(">QQ", buf[:16])
+        self.version = buf[16:]
+
+
+def cleanup(filename):
+    """Remove all FileStorage related files."""
+    for ext in '', '.old', '.tmp', '.lock', '.index', '.pack':
+        try:
+            os.remove(filename + ext)
+        except OSError, e:
+            if e.errno != errno.ENOENT:
+                raise


=== Zope3/src/zodb/storage/fsdump.py 1.1 => 1.2 ===
--- /dev/null	Wed Dec 25 09:13:51 2002
+++ Zope3/src/zodb/storage/fsdump.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,93 @@
+##############################################################################
+#
+# 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.
+#
+##############################################################################
+
+import struct
+from zodb.storage.file import TRANS_HDR, TRANS_HDR_LEN
+from zodb.storage.file import DATA_HDR, DATA_HDR_LEN
+from zodb.utils import u64
+
+def fmt(p64):
+    # Return a nicely formatted string for a packaged 64-bit value
+    return "%016x" % u64(p64)
+
+def dump(path, dest=None):
+    Dumper(path, dest).dump()
+
+class Dumper:
+    """A very verbose dumper for debugging FileStorage problems."""
+
+    def __init__(self, path, dest=None):
+        self.file = open(path, "rb")
+        self.dest = dest
+
+    def dump(self):
+        fid = self.file.read(4)
+        print >> self.dest, "*" * 60
+        print >> self.dest, "file identifier: %r" % fid
+        while self.dump_txn():
+            pass
+
+    def dump_txn(self):
+        pos = self.file.tell()
+        h = self.file.read(TRANS_HDR_LEN)
+        if not h:
+            return False
+        tid, tlen, status, ul, dl, el = struct.unpack(TRANS_HDR, h)
+        end = pos + tlen
+        print >> self.dest, "=" * 60
+        print >> self.dest, "offset: %d" % pos
+        print >> self.dest, "end pos: %d" % end
+        print >> self.dest, "transaction id: %s" % fmt(tid)
+        print >> self.dest, "trec len: %d" % tlen
+        print >> self.dest, "status: %r" % status
+        user = descr = extra = ""
+        if ul:
+            user = self.file.read(ul)
+        if dl:
+            descr = self.file.read(dl)
+        if el:
+            extra = self.file.read(el)
+        print >> self.dest, "user: %r" % user
+        print >> self.dest, "description: %r" % descr
+        print >> self.dest, "len(extra): %d" % el
+        while self.file.tell() < end:
+            self.dump_data(pos)
+        tlen2 = u64(self.file.read(8))
+        print >> self.dest, "redundant trec len: %d" % tlen2
+        return True
+
+    def dump_data(self, tloc):
+        pos = self.file.tell()
+        h = self.file.read(DATA_HDR_LEN)
+        assert len(h) == DATA_HDR_LEN
+        oid, revid, prev, tloc, vlen, dlen = struct.unpack(DATA_HDR, h)
+        print >> self.dest, "-" * 60
+        print >> self.dest, "offset: %d" % pos
+        print >> self.dest, "oid: %s" % fmt(oid)
+        print >> self.dest, "revid: %s" % fmt(revid)
+        print >> self.dest, "previous record offset: %d" % prev
+        print >> self.dest, "transaction offset: %d" % tloc
+        if vlen:
+            pnv = self.file.read(8)
+            sprevdata = self.file.read(8)
+            version = self.file.read(vlen)
+            print >> self.dest, "version: %r" % version
+            print >> self.dest, "non-version data offset: %d" % u64(pnv)
+            print >> self.dest, \
+                  "previous version data offset: %d" % u64(sprevdata)
+        print >> self.dest, "len(data): %d" % dlen
+        self.file.read(dlen)
+        if not dlen:
+            sbp = self.file.read(8)
+            print >> self.dest, "backpointer: %d" % u64(sbp)


=== Zope3/src/zodb/storage/fsindex.py 1.1 => 1.2 ===
--- /dev/null	Wed Dec 25 09:13:52 2002
+++ Zope3/src/zodb/storage/fsindex.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,127 @@
+##############################################################################
+#
+# 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 zodb.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 __contains__(self, key):
+        tree = self._data.get(key[:6])
+        if tree is None:
+            return False
+        v = tree.get(key[6:], None)
+        if v is None:
+            return False
+        return True
+
+    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


=== Zope3/src/zodb/storage/fsrecover.py 1.1 => 1.2 ===
--- /dev/null	Wed Dec 25 09:13:52 2002
+++ Zope3/src/zodb/storage/fsrecover.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,326 @@
+##############################################################################
+#
+# 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.
+#
+##############################################################################
+"""Simple script for repairing damaged FileStorage files.
+
+Usage: %s [-f] input output
+
+Recover data from a FileStorage data file, skipping over damaged
+data. Any damaged data will be lost. This could lead to useless output
+of critical data were lost.
+
+Options:
+
+    -f
+       Force output to putput file even if it exists
+
+    -v level
+
+       Set the verbosity level:
+
+         0 -- Show progress indicator (default)
+
+         1 -- Show transaction times and sizes
+
+         2 -- Show transaction times and sizes, and
+              show object (record) ids, versions, and sizes.
+
+    -p
+
+       Copy partial transactions. If a data record in the middle of a
+       transaction is bad, the data up to the bad data are packed. The
+       output record is marked as packed. If this option is not used,
+       transaction with any bad data are skipped.
+
+    -P t
+
+       Pack data to t seconds in the past. Note that is the "-p"
+       option is used, then t should be 0.
+
+
+Important note: The ZODB package must be imporable.  You may need
+                to adjust the Python path accordingly.
+
+"""
+
+# Algorithm:
+#
+#     position to start of input
+#     while 1:
+#         if end of file: break
+#          try: copy_transaction
+#          except:
+#                 scan for transaction
+#                 continue
+
+import sys, os
+
+if __name__ == '__main__' and len(sys.argv) < 3:
+    print __doc__ % sys.argv[0]
+
+def die(mess=''):
+    if not mess: mess="%s: %s" % sys.exc_info()[:2]
+    print mess+'\n'
+    sys.exit(1)
+
+try: import ZODB
+except ImportError:
+    if os.path.exists('ZODB'): sys.path.append('.')
+    elif os.path.exists('FileStorage.py'):  sys.path.append('..')
+    import ZODB
+
+
+import getopt, ZODB.FileStorage, struct, time
+from struct import unpack
+from zodb.utils import t32, p64, u64
+from zodb.timestamp import TimeStamp
+from cPickle import loads
+from zodb.storage.file import RecordIterator
+
+class EOF(Exception): pass
+class ErrorFound(Exception): pass
+
+def error(mess, *args):
+    raise ErrorFound(mess % args)
+
+def read_transaction_header(file, pos, file_size):
+    # Read the transaction record
+    seek=file.seek
+    read=file.read
+
+    seek(pos)
+    h=read(23)
+    if len(h) < 23: raise EOF
+
+    tid, stl, status, ul, dl, el = unpack(">8s8scHHH",h)
+    if el < 0: el=t32-el
+
+    tl=u64(stl)
+
+    if status=='c': raise EOF
+
+    if pos+(tl+8) > file_size:
+        error("bad transaction length at %s", pos)
+
+    if status not in ' up':
+        error('invalid status, %s, at %s', status, pos)
+
+    if tl < (23+ul+dl+el):
+        error('invalid transaction length, %s, at %s', tl, pos)
+
+    tpos=pos
+    tend=tpos+tl
+
+    if status=='u':
+        # Undone transaction, skip it
+        seek(tend)
+        h=read(8)
+        if h != stl: error('inconsistent transaction length at %s', pos)
+        pos=tend+8
+        return pos, None
+
+    pos=tpos+(23+ul+dl+el)
+    user=read(ul)
+    description=read(dl)
+    if el:
+        try: e=loads(read(el))
+        except: e={}
+    else: e={}
+
+    result=RecordIterator(
+        tid, status, user, description, e,
+        pos, (tend, file, seek, read,
+              tpos,
+              )
+        )
+
+    pos=tend
+
+    # Read the (intentionally redundant) transaction length
+    seek(pos)
+    h=read(8)
+    if h != stl:
+        error("redundant transaction length check failed at %s", pos)
+    pos=pos+8
+
+    return pos, result
+
+def scan(file, pos, file_size):
+    seek=file.seek
+    read=file.read
+    while 1:
+        seek(pos)
+        data=read(8096)
+        if not data: return 0
+
+        s=0
+        while 1:
+            l=data.find('.', s)
+            if l < 0:
+                pos=pos+8096
+                break
+            if l > 8080:
+                pos = pos + l
+                break
+            s=l+1
+            tl=u64(data[s:s+8])
+            if tl < pos:
+                return pos + s + 8
+
+def iprogress(i):
+    if i%2: print '.',
+    else: print (i/2)%10,
+    sys.stdout.flush()
+
+def progress(p):
+    for i in range(p): iprogress(i)
+
+def recover(argv=sys.argv):
+
+    try:
+        opts, (inp, outp) = getopt.getopt(argv[1:], 'fv:pP:')
+        force = partial = verbose = 0
+        pack = None
+        for opt, v in opts:
+            if opt == '-v': verbose = int(v)
+            elif opt == '-p': partial=1
+            elif opt == '-f': force=1
+            elif opt == '-P': pack=time.time()-float(v)
+
+
+        force = filter(lambda opt: opt[0]=='-f', opts)
+        partial = filter(lambda opt: opt[0]=='-p', opts)
+        verbose = filter(lambda opt: opt[0]=='-v', opts)
+        verbose = verbose and int(verbose[0][1]) or 0
+        print 'Recovering', inp, 'into', outp
+    except:
+        die()
+        print __doc__ % argv[0]
+
+
+    if os.path.exists(outp) and not force:
+        die("%s exists" % outp)
+
+    file=open(inp, "rb")
+    seek=file.seek
+    read=file.read
+    if read(4) != ZODB.FileStorage.packed_version:
+        die("input is not a file storage")
+
+    seek(0,2)
+    file_size=file.tell()
+
+    ofs=ZODB.FileStorage.FileStorage(outp, create=1)
+    _ts=None
+    ok=1
+    prog1=0
+    preindex={}; preget=preindex.get   # waaaa
+    undone=0
+
+    pos=4
+    while pos:
+
+        try:
+            npos, transaction = read_transaction_header(file, pos, file_size)
+        except EOF:
+            break
+        except:
+            print "\n%s: %s\n" % sys.exc_info()[:2]
+            if not verbose: progress(prog1)
+            pos = scan(file, pos, file_size)
+            continue
+
+        if transaction is None:
+            undone = undone + npos - pos
+            pos=npos
+            continue
+        else:
+            pos=npos
+
+        tid=transaction.tid
+
+        if _ts is None:
+            _ts=TimeStamp(tid)
+        else:
+            t=TimeStamp(tid)
+            if t <= _ts:
+                if ok: print ('Time stamps out of order %s, %s' % (_ts, t))
+                ok=0
+                _ts=t.laterThan(_ts)
+                tid=_ts.raw()
+            else:
+                _ts = t
+                if not ok:
+                    print ('Time stamps back in order %s' % (t))
+                    ok=1
+
+        if verbose:
+            print 'begin',
+            if verbose > 1: print
+            sys.stdout.flush()
+
+        ofs.tpc_begin(transaction, tid, transaction.status)
+
+        if verbose:
+            print 'begin', pos, _ts,
+            if verbose > 1: print
+            sys.stdout.flush()
+
+        nrec=0
+        try:
+            for r in transaction:
+                oid=r.oid
+                if verbose > 1: print u64(oid), r.version, len(r.data)
+                pre=preget(oid, None)
+                s=ofs.store(oid, pre, r.data, r.version, transaction)
+                preindex[oid]=s
+                nrec=nrec+1
+        except:
+            if partial and nrec:
+                ofs._status='p'
+                ofs.tpc_vote(transaction)
+                ofs.tpc_finish(transaction)
+                if verbose: print 'partial'
+            else:
+                ofs.tpc_abort(transaction)
+            print "\n%s: %s\n" % sys.exc_info()[:2]
+            if not verbose: progress(prog1)
+            pos = scan(file, pos, file_size)
+        else:
+            ofs.tpc_vote(transaction)
+            ofs.tpc_finish(transaction)
+            if verbose:
+                print 'finish'
+                sys.stdout.flush()
+
+        if not verbose:
+            prog = pos * 20l / file_size
+            while prog > prog1:
+                prog1 = prog1 + 1
+                iprogress(prog1)
+
+
+    bad = file_size - undone - ofs._pos
+
+    print "\n%s bytes removed during recovery" % bad
+    if undone:
+        print "%s bytes of undone transaction data were skipped" % undone
+
+    if pack is not None:
+        print "Packing ..."
+        ofs.pack(pack)
+
+    ofs.close()
+
+
+if __name__=='__main__': recover()


=== Zope3/src/zodb/storage/mapping.py 1.1 => 1.2 ===
--- /dev/null	Wed Dec 25 09:13:52 2002
+++ Zope3/src/zodb/storage/mapping.py	Wed Dec 25 09:12:19 2002
@@ -0,0 +1,193 @@
+##############################################################################
+#
+# 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.
+#
+##############################################################################
+"""Very Simple Mapping ZODB storage
+
+The Mapping storage provides an extremely simple storage
+implementation that doesn't provide undo or version support.
+
+It is meant to illustrate the simplest possible storage.
+
+The Mapping storage uses a single data structure to map
+object ids to data.
+
+The Demo storage serves two purposes:
+
+  - Provide an example implementation of a full storage without
+    distracting storage details,
+
+  - Provide a volatile storage that is useful for giving demonstrations.
+
+The demo strorage can have a "base" storage that is used in a
+read-only fashion. The base storage must not not to contain version
+data.
+
+There are three main data structures:
+
+  _data -- Transaction logging information necessary for undo
+
+      This is a mapping from transaction id to transaction, where
+      a transaction is simply a 4-tuple:
+
+        packed, user, description, extension_data, records
+
+      where extension_data is a dictionary or None and records are the
+      actual records in chronological order. Packed is a flag
+      indicating whethe the transaction has been packed or not
+
+  _index -- A mapping from oid to record
+
+  _vindex -- A mapping from version name to version data
+
+      where version data is a mapping from oid to record
+
+A record is a tuple:
+
+  oid, serial, pre, vdata, p,
+
+where:
+
+     oid -- object id
+
+     serial -- object serial number
+
+     pre -- The previous record for this object (or None)
+
+     vdata -- version data
+
+        None if not a version, ortherwise:
+           version, non-version-record
+
+     p -- the pickle data or None
+
+The pickle data will be None for a record for an object created in
+an aborted version.
+
+It is instructive to watch what happens to the internal data structures
+as changes are made.  Foe example, in Zope, you can create an external
+method::
+
+  import Zope
+
+  def info(RESPONSE):
+      RESPONSE['Content-type']= 'text/plain'
+
+      return Zope.DB._storage._splat()
+
+and call it to minotor the storage.
+
+$Id$
+"""
+
+import zodb.db
+from zodb import interfaces, utils
+from zodb.storage import base
+from zodb.serialize import findrefs
+from zodb.timestamp import TimeStamp
+from zodb.utils import z64
+
+def DB(name="Mapping Storage",
+       pool_size=7, cache_size=400):
+    ms = MappingStorage(name)
+    db = zodb.db.DB(ms, pool_size, cache_size)
+    return db
+
+class MappingStorage(base.BaseStorage):
+
+    def __init__(self, name='Mapping Storage'):
+
+        base.BaseStorage.__init__(self, name)
+
+        self._index={}
+        self._tindex=[]
+
+        # Note:
+        # If you subclass this and use a persistent mapping facility
+        # (e.g. a dbm file), you will need to get the maximum key and
+        # save it as self._oid.  See dbmStorage.
+
+    def load(self, oid, version):
+        self._lock_acquire()
+        try:
+            p=self._index[oid]
+            return p[8:], p[:8] # pickle, serial
+        finally: self._lock_release()
+
+    def store(self, oid, serial, data, version, transaction):
+        if transaction is not self._transaction:
+            raise interfaces.StorageTransactionError(self, transaction)
+
+        if version:
+            raise interfaces.Unsupported, "Versions aren't supported"
+
+        self._lock_acquire()
+        try:
+            if self._index.has_key(oid):
+                old=self._index[oid]
+                oserial=old[:8]
+                if serial != oserial:
+                    raise interfaces.ConflictError(serials=(oserial, serial))
+
+            serial=self._serial
+            self._tindex.append((oid,serial+data))
+        finally: self._lock_release()
+
+        return serial
+
+    def _clear_temp(self):
+        self._tindex=[]
+
+    def _finish(self, tid, user, desc, ext):
+
+        index=self._index
+        for oid, p in self._tindex: index[oid]=p
+
+    def pack(self, t):
+        self._lock_acquire()
+        try:
+            # Build an index of *only* those objects reachable
+            # from the root.
+            index=self._index
+            rootl = [z64]
+            pop=rootl.pop
+            pindex={}
+            referenced=pindex.has_key
+            while rootl:
+                oid=pop()
+                if referenced(oid): continue
+
+                # Scan non-version pickle for references
+                r=index[oid]
+                pindex[oid]=r
+                p=r[8:]
+                rootl.extend(findrefs(p))
+
+            # Now delete any unreferenced entries:
+            for oid in index.keys():
+                if not referenced(oid): del index[oid]
+
+        finally: self._lock_release()
+
+    def _splat(self):
+        """Spit out a string showing state."""
+        o=[]
+        o.append('Index:')
+        index=self._index
+        keys=index.keys()
+        keys.sort()
+        for oid in keys:
+            r=index[oid]
+            o.append('  %s: %s, %s' %
+                     (utils.u64(oid),TimeStamp(r[:8]),`r[8:]`))
+
+        return "\n".join(o)