File: SimpleDB.py

package info (click to toggle)
python-bobopos 2.1-1
links: PTS
area: main
in suites: slink
size: 236 kB
ctags: 220
sloc: python: 1,774; makefile: 38; sh: 24
file content (1421 lines) | stat: -rw-r--r-- 43,426 bytes
parent folder | download | duplicates (3)
##############################################################################
#
# Copyright (c) 1996-1998, Digital Creations, Fredericksburg, VA, USA.
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
# 
#   o Redistributions of source code must retain the above copyright
#     notice, this list of conditions, and the disclaimer that follows.
# 
#   o Redistributions in binary form must reproduce the above copyright
#     notice, this list of conditions, and the following disclaimer in
#     the documentation and/or other materials provided with the
#     distribution.
# 
#   o Neither the name of Digital Creations nor the names of its
#     contributors may be used to endorse or promote products derived
#     from this software without specific prior written permission.
# 
# 
# THIS SOFTWARE IS PROVIDED BY DIGITAL CREATIONS AND CONTRIBUTORS *AS IS*
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
# TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
# PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL DIGITAL
# CREATIONS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
# OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
# TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
# USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
# DAMAGE.
#
# 
# If you have questions regarding this software, contact:
#
#   Digital Creations, L.C.
#   910 Princess Ann Street
#   Fredericksburge, Virginia  22401
#
#   info@digicool.com
#
#   (540) 371-6909
#
##############################################################################
__doc__='''Simple file-based databases

This module contains simple file-based database implementations.
All of these databases store arbitrary string records by record number.


$Id: SimpleDB.py,v 1.61 1998/10/23 21:42:37 jim Exp $'''
__version__='$Revision: 1.61 $'[11:-2]

try:
    import newstruct
    struct=newstruct
except: import struct

pack=struct.pack
unpack=struct.unpack

import time, os, traceback, sys, string, array, os
from string import join, find
from cPickle import Pickler, Unpickler
from cStringIO import StringIO
import cPickle, cStringIO

try:
    import thread
    thread_error=thread.error
    def new_thread(func,args=()): return thread.start_new_thread(func,args)
    def allocate_lock(): return thread.allocate_lock()
except:
    thread_error='thread.error'
    def new_thread(func,args=()): return apply(func,args)
    class allocate_lock:
        def acquire(*args): return 1
        def release(*args): pass

getnow=time.time

DatabaseError='DatabaseError'
ErrorFormat="""
<HTML><HEAD><TITLE>Database Error</TITLE></HEAD>
<BODY BGCOLOR=\"#FFFFFF\" LINK=\"#000099\" VLINK=\"#555555\" ALINK=\"#77003B\">
<TABLE BORDER="0" WIDTH="100%%" CELLPADDING="10">
<TR>
  <TD VALIGN="TOP"><BR>
  <CENTER><B><FONT SIZE="+6" COLOR=\"#77003B\">!</FONT></B></CENTER>
  </TD>
  <TD VALIGN="TOP"><BR><BR>
  <CENTER>%s</CENTER>
  </TD>
</TR>
</TABLE>"""


# The following two are to help detect file corruption.
# Databases that want more objects than this should probably consider
# different implementations.
min_oid=-10000   # negative oids are used by infrastructure, like PickleDict

class MultipleRevision:
    '''\
    A simple database that stores multiple versions of records

    Strings are stored in a binary data format.  Multiple versions may
    be stored for each string. Each record consists of:

    - a 4-byte integer object ID (oid),

    - a 4-byte integer record position of the previous version of the record.

    - an 8-byte float starting (i.e. creation) time for the version of
      the object,

    - a 4-byte total record length

    - a 4-byte integer pickle length,

    - the pickle string.

    - the meta-data string

    - a 4-byte total record length

    Note that since we are now using the new struct module, we can
    coun\'t on the above sizes, so we now use that to read just parts
    of records in many places.

    When a record is updated, a new record is written to
    the file.  The old data is not actually removed from the file.

    Unneeded data can be removed from a file when it is opened
    by specifying a free parameter.

    When an object is updated or added, a new version for the object
    is created and added to the end of the file.
    '''
    _ro=0           # Are we in read-only mode?     
    ConcurrencyError='ConcurrencyError'
    IncompatibleError='IncompatableFileFormat'
    header_size=len(pack(">iidii",0,0,0.0,0,0))
    packed_version2='SDBMV'+pack("f",2.0)
    file__version__=3.0
    packed_version='SDBMV'+pack(">f",file__version__)
    now=0.0
    lastm='' # This is the most recently written meta data, up to the delimiter

    def __init__(self, file_name=None, create=None, revision_time=None,
                 meta_index=0):
        """\
        Open/create a database

        Arguments:

          file_name -- The name of the file containing the database

          create    -- A flag indicating whether a new file should be
                       created.

          revision_time -- The time, past which revisions should not be read.

        """
        self.meta_index=meta_index
        self.open(file_name,create,revision_time,meta_index)
        self.readonly_lock=allocate_lock()

    def open(self, file_name, create=None, revision_time=None, meta_index=0):

        if create:
            file=open(file_name,'w+b')
            file.write(self.packed_version)
            revision_time=None
        else:
            if type(file_name) is not type('') and hasattr(file_name,'seek'):
                # We've been given an already opened file.
                file=file_name
                file.flush()
                file.seek(0,2)
                if not file.tell(): file.write(self.packed_version)
            else:
                try: file=open(file_name,'r+b')
                except:
                    create=1 # Read open failed, so create new
                    try: file=open(file_name,'w+b')
                    except: raise IOError, 'could not open ' + file_name
                    file.write(self.packed_version)
                    revision_time=None
                if not create:
                    v=file.read(len(self.packed_version))
                    if v != self.packed_version:
                        if v==self.packed_version2:
                            import SimpleDB23
                            SimpleDB23.convert23(file,file_name)
                            file=open(file_name,'r+b')
                            v=file.read(len(self.packed_version))
                            if v != self.packed_version:
                                raise self.IncompatableError, file_name
                        else:
                            raise self.IncompatableError, file_name

        lock_file(file)
        self.now=now=revision_time or time.time()
        self.file=file
        self.file_name=file_name

        # See if we can read a saved index:
        if not create:
            try:
                info=self.restore_index()
                self.index, self.pos = info['index'], info['pos']
                try: self._transactions = info['_transactions']
                except KeyError: pass
                return
            except: pass

        # Read the index the hard way:
        self.index,self.pos=read_index(file, now, meta_index=meta_index)

    def _file_size(self):
        self.file.seek(0,2)
        return self.file.tell()

    def readonly_mode(self, m, wait=1):
        if m:
            try: self._sync__lock.release()
            except: pass
            if not self.readonly_lock.acquire(wait):
                raise thread_error, (
                    ErrorFormat % 'Already in read-only mode')
            try: self._sync__lock.acquire()
            except: pass
        else: self.readonly_lock.release()
        self._ro=m

    def current_pos(self, pos=None):
        if pos is None: return self.pos
        file=self.file
        file.seek(pos)
        file.truncate()
        self.pos=pos

    def __getinitargs__(self): return (self.file_name,) 

    def __getstate__(self): pass
    def __setstate__(self,ignored): pass    

    def __getitem__(self,oid,IntType=type(0)):
        file=self.file
        read=file.read
        seek=file.seek
        pos=self.index[oid]
        __traceback_info__ = oid, pos
        seek(pos)
        h=read(24)
        roid,prev,start,tlen,plen=unpack(">iidii",h)
        seek(pos+tlen-4)
        if type(oid)==IntType: iid=oid
        else: iid,m=oid
        if (read(4) != h[16:20] or
            roid != iid or prev > pos or prev < 0 or tlen < plen):
            raise DatabaseError, ('Corrupted data record at %s' % pos)
        seek(pos+24)
        h=read(plen)
        return h

    def write_mode_error(self):
        raise IOError, (ErrorFormat %
            """Attempt to perform a <em>write</em> operation while the database
            is in <em>read-only</em> mode.
            """)

    def store(self,oid,p,info='',IntType=type(0)):
        if self._ro: self.write_mode_error()
        file=self.file
        now=getnow()
        if now <= self.now:
            now=self.now+0.001

        index=self.index

        try: prev=index[oid]
        except: prev=0

        if type(oid)==IntType:
            iid=oid
            m=info
        else:
            iid,m=oid
            m="%s %s" % (m,info)
        
        lm=find(m,'\t')
        if lm > 0: pm=m[:lm]
        else: pm=m
        if pm==self.lastm: m=pm  # We want to avoid storing extra info
        plen=len(p)
        tlen=28+plen+len(m)
        h=pack(">iidii",iid,prev,now,tlen,plen)
        pos=self.pos
        index[oid]=pos
        file.seek(pos)
        file.write(join((h,p,m,h[16:20]),''))
        file.flush()
        self.pos=pos+tlen
        self.now=now
        self.lastm=pm

    __setitem__=store

    def append_record(self, record, pos):
        file=self.file
        file.seek(pos)
        file.write(record)

    def ooops(self,oid,s=None,now=None):
        '''\
        Undo operations on an object.
        
        Undo all changes made within the most recent s seconds to the
        object specified by oid. Or, undo the last change, if s is
        ommitted.
        '''
        if self._ro: self.write_mode_error()
        index=self.index
        try: pos=index[oid]
        except: return doops(oid,s,now)
        file=self.file
        seek=file.seek
        read=file.read
        __traceback_info__ = oid, pos
        seek(pos+4)
        prev,start=unpack(">id",read(12))
        if s is not None:
            if now is None: now=time.time()
            if now - s >= start: return 
        seek(pos)
        file.write('\0\0\0\0')
        if not prev:
            file.flush()
            del index[oid]
            return pos
        ppos=prev
        __traceback_info__ = oid, ppos
        file.seek(ppos+8)
        start,=unpack(">d",read(8))
        index[oid]=ppos
        if s is not None:
            if now - s < start: return self.ooops(oid,s,now)
        return pos


    def Ooops(self, oid):
        """Undo the last Transaction that affected oid

        Note that this may affect other objects too.
        """
        pos=self.index[oid]
        file=self.file
        seek=file.seek
        read=file.read
        __traceback_info__ = oid, pos
        seek(pos+4)
        prev,start,tlen,plen=unpack(">idii",read(20))
        mlen=tlen-28
        if plen > 0: mlen=mlen-plen
        pos=pos+tlen-mlen-4
        __traceback_info__ = oid, pos
        seek(pos)
        m=read(mlen)
        if not m: raise 'ValueError', (
            'This object was not edited in a named session')
        self.Toops(m)

    _transactions=None
    def transactions(self,old=0):
        try: t=self._transactions
        except AttributeError: t=None
        if t is None:
            t=self._transactions=transactions(self.file)
        else:
            if not old:
                t=self._transactions=transactions(self.file, t)
        return t

    def positionOfTransaction(self,T):
        l=find(T,'\t')
        if l > 0: T=T[:l]
        i=0
        for t in self.transactions(1):
            pos=t[1]
            t=t[0]
            l=find(t,'\t')
            if l > 0: t=t[:l]
            if t==T: return i,pos
            i=i+1

    def Toops(self,T, pos=None):
        """Undo all of the changes made in transaction, T

        The optional argument, pos, gives the position of the first
        record in the transaction.
        """
        if self._ro: self.write_mode_error()
        file=self.file
        seek=file.seek
        read=file.read
        write=file.write
        index=self.index
        oids=[]
        meta_index=self.meta_index

        if pos is None:
            it, pos = self.positionOfTransaction(T)
        else: it=None

        # Compute the unique/proper part of the transaction name
        if type(T) is type(''):
            lm=find(T,'\t')
            if lm > 0: pT=T[:lm]
            else: pT=T
        else: pT=T[0]

        if meta_index:
            l=find(pT,' ')
            if l < 0: raise TypeError, 'Invalid transaction name'
            meta_name=pT[:l]

        # First, check to make sure that none of the objects modified
        # by this transaction have been modified by later
        # transactions.

        min=imax=pos
        while pos > 0:
            __traceback_info__ = pos
            seek(pos)
            h=read(24)
            if len(h) < 24: break
            oid,prev,start,tlen,plen=unpack(">iidii",h)
            if not oid: break
            seek(pos+tlen-4)
            if (read(4) != h[16:20] or
                prev > pos or prev < 0 or tlen < plen):
                raise DatabaseError, ('Corrupted data record at %s' % pos)
            mlen=tlen-28
            if plen > 0: mlen=mlen-plen
            mpos=pos+tlen-mlen-4
            __traceback_info__ = oid, mpos
            seek(mpos)
            m=read(mlen)
            lm=find(m,'\t')
            if lm > 0: pm=m[:lm]
            else: pm=m
            if pm != pT: break
            if meta_index: oid=oid, meta_name
            ipos=index[oid]
            if ipos > imax: imax=ipos
            pos=pos+tlen
        if imax >= pos: raise ConflictError, (
            """Attempt to undo a transaction but some of the data that was
            modified by the transaction was later modified by other
            transactions. """)
        max=pos

        # OK, now do the undo.
        pos=min
        while pos >= min and pos < max:
            __traceback_info__ = pos
            seek(pos)
            h=read(24)
            if len(h) < 24: break
            oid,prev,start,tlen,plen=unpack(">iidii",h)
            iid=oid
            if meta_index: oid=oid, meta_name
            seek(pos)
            write('\0\0\0\0')
            if index[oid]==pos:
                oids.append(iid)
                if prev > 0:
                    while prev > 0:
                        __traceback_info__ = oid, prev
                        seek(prev)
                        if read(4)!='\0\0\0\0':
                            self.index[oid]=prev
                            break
                        prev,=unpack(">i",read(4))
                if prev <= 0: del index[oid]
            pos=pos+tlen
        file.flush()

        if it is not None:
            t=self._transactions
            del t[it]

        return oids

    def oops(self,s=None,now=None):
        '''\
        Undo all changes made within the most recent s seconds.
        Or, undo the last change, if s is ommitted.
        '''
        # The current implementation of this is stupid.
        # It should be changed to take advantage of the fact that
        # We can nor march backward from the end of the file
        if now is None:
            now=time.time()
            if now <= self.now: return []
        index=self.index
        items=index.items()
        foundups=0
        founddels=0
        file=self.file
        seek=file.seek
        read=file.read

        if s is None:
            s=0
            for oid,pos in items:
                __traceback_info__ = oid, pos
                seek(pos+8)
                t,=unpack(">d",read(8))
                if t > s: s=t
            for oid,pos in ditems:
                __traceback_info__ = oid, pos
                seek(pos+8)
                t,=unpack(">d",read(8))
                if t > s: s=end
            s=now-s
        maxt=now-s

        affected=[]
        minp=None
        for oid,pos in ditems:
            __traceback_info__ = oid, pos
            seek(pos+8)
            t,=unpack(">d",read(8))
            if maxt < t:
                p=self.doops(oid,s,now)
                if p is not None and minp is None or p < minp: minp=p
        for oid,pos in items:
            __traceback_info__ = oid, pos
            seek(pos+8)
            t,=unpack(">d",read(8))
            if maxt < t:
                p=self.ooops(oid,s,now)
                affected.append(oid)
                if minp is None or p < minp: minp=p
        if minp is not None:
            self.file.truncate(minp)
            self.pos=minp
        self.now=now
        return affected

    def pack(self,start_time=None, bg=1):
        if self._ro: self.write_mode_error()
        if bg: return new_thread(subpack, (self,start_time))
        subpack(self, start_time)               # Run real stand-alone version

    def finish_pack(self, newindex, newpos, transactions=[]):
        self.file.close()
        try: os.unlink(self.file_name+'.old')
        except: pass
        try: os.unlink(self.file_name+'.index')
        except: pass
        os.rename(self.file_name, self.file_name+'.old')
        os.rename(self.file_name+'.pk',self.file_name)

        self.file=open(self.file_name,'r+b')
        lock_file(self.file)
        self.index=newindex
        self.pos=newpos
        try:
            if self._transactions is not None: self._transactions=transactions
        except: pass
        self.save_index()

    def remove_transaction(self,tname):
        # Remove the records for the
        # given transaction name.

        if self._ro: self.write_mode_error()
        index=self.index
        if not index.hassubindex(tname): return
        file=self.file
        read=file.read
        seek=file.seek
        write=file.write
        flush=file.flush
        for pos in index.subindex(tname).values():
            while pos > 0:
                __traceback_info__ = pos
                seek(pos)
                write('\0\0\0\0')
                flush()
                # If there are previous records, we want to get them too:
                pos,=unpack(">i",read(4))
        index.removeSubindex(tname)

        maxp=0
        for subindex in index.subindexes():
            maxp=max(maxp,max(subindex.values()))
        
        if maxp:
            __traceback_info__ = maxp
            seek(maxp+16)
            tlen,=unpack(">i",file.read(4))
            maxp=maxp+tlen
        else:
            maxp=len(self.packed_version)
        file.flush()
        if maxp < self.pos:
            try: file=file.truncate
            except AttributeError: file=None # Windoze don't have truncate
            if file is not None:
                file(maxp)
                self.pos=maxp

    def commit_info(self,tindex,newpos):
        # Update my index and position with data from LRT
        self._ro=0
        index=self.index
        for oid, pos in tindex.items(): index[oid]=pos
        self.pos=newpos
        self.file.flush()
        self.save_index()

    def transaction_records(self,tname,base,info):

        # Get a blob of data containing data records to be added to
        # the committed data file.  We can't just copy our data.  We
        # have to adjust the "previous" record pointers to reflect the
        # base database.  We also insert the comment into the
        # transaction name for the first record.
        #
        # Note that we have to maintain an invariant that the record
        # times in a SimpleDB must be ascending, so we will reset the
        # record times to be now plus a small increment necessary to
        # give each record a unique time.
        
        try: index=self.index.subindex(tname)
        except: return (),()
        file=self.file
        seek=file.seek
        read=file.read
        bindex=base.index
        dbp=base.current_pos()
        tindex={}

        data=[]
        oids=[]

        t=time.time()
        append=base.append_record

        # Copy update records:
        for oid in index.keys():

            pos=index[oid]
            __traceback_info__ = oid, pos

            #seek(pos+8)
            #start,tlen=unpack(">di",read(12))
            seek(pos)
            h=read(24)
            roid,prev,start,tlen,plen=unpack(">iidii",h)
            seek(pos+tlen-4)
            if (read(4) != h[16:20] or
                roid != oid or prev > pos or prev < 0 or tlen < plen):
                raise DatabaseError, (
                    'Corrupted data record at %s in transaction file' % pos)
            seek(pos+20)

            p=read(tlen-20)
            try: prev=bindex[oid]
            except: prev=0
            if info:
                plen,=unpack(">i",p[:4])
                mlen=tlen-28
                if plen > 0: mlen=mlen-plen
                m=p[-4-mlen:-4]
                l=find(m,'\t')
                if l > 0: m=m[:l]
                info="%s\t%s" % (m,info)
                tlen=tlen+len(info)-mlen
                p=p[:-4-mlen]+info+pack(">i",tlen)
                info=None

            p=pack(">iidi",oid,prev,t,tlen)+p
            append(p, dbp)
            tindex[oid]=dbp
            dbp=dbp+len(p)
            t=t+0.002
            oids.append(oid)

        return oids, tindex, dbp

    def mtime(self,oid,IntType=type(0)):
        pos=self.index[oid]
        file=self.file
        seek=file.seek
        read=file.read

        seek(pos)
        h=read(24)
        roid,prev,start,tlen,plen=unpack(">iidii",h)
        seek(pos+tlen-4)
        if type(oid)==IntType: iid=oid
        else: iid,m=oid
        if (read(4) != h[16:20] or
            roid != iid or prev > pos or prev < 0 or tlen < plen):
            raise DatabaseError, ('Corrupted data record at %s' % pos)
        return start

    def save_index(self):
        """Write the database index to a file to support quick startup
        """
        index_name=self.file_name+'.index'
        tmp_name=index_name+'.tmp'

        f=open(tmp_name,'wb')
        p=Pickler(f,1)

        info={'index': self.index, 'pos': self.pos}
        try: 
            t=self._transactions
            info['_transactions']=t
        except: pass

        p.dump(info)
        f.flush()
        f.close()
        try:
            try: os.unlink(index_name)
            except: pass
            os.rename(tmp_name, index_name)
        except: pass

    def restore_index(self):
        """Load the database index from a file to support quick startup
        """
        file_name=self.file_name
        index_name=file_name+'.index'
        
        f=open(index_name,'rb')
        p=Unpickler(f)

        info=p.load()
        if type(info) is type(()):
            p={'index': info[0], 'pos': info[2]}
            try: p['_transactions']=info[3]
            except IndexError: pass
            info=p

        file=self.file
        file.flush()
        file.seek(0,2)
        file_size=file.tell()
        saved_pos=info['pos']
        if saved_pos <= file_size:
            index=info['index']
            last_record=index.max_value()
            file.seek(last_record)
            oid=unpack(">i",file.read(4))[0]
            index=info['index']
            if index[oid]==last_record:
                pos=saved_pos
                if pos < file_size:
                    index,pos=read_index(file, meta_index=self.meta_index,
                                         index=index, pos=pos)
                info['index'], info['pos'] = index, pos
            return info

        raise 'IndexError', 'index data incorrect'

    def transaction_info(self, start, end, prefix='', tprefix='', since=0):
        file=self.file
        seek=file.seek
        read=file.read
        unpack=struct.unpack
        split=string.split
        i=0
        r=[]
        pos=self.pos
        last=None
        lastm=()
        lastpos=0
        lp=len(prefix)
        lt=len(tprefix)
        while 1:
            seek(pos-4)
            tlen,=unpack(">i", read(4))
            pos=pos-tlen
            if pos < 0: break
            seek(pos)

            h=read(24)
            oid,prev,startt,tlen1,plen=unpack(">iidii",h)
            if startt <= since: break
            if not oid: continue
            if (tlen != tlen1 or
                prev > pos or prev < 0 or tlen < plen):
                raise DatabaseError, ('Corrupted data record at %s' % pos)
            nmlen=plen+24
            seek(pos+nmlen)
            mlen=tlen-nmlen-4
            m=read(mlen)
            if m[:lt] != tprefix: continue
            m=split(m,'\t')
            t=m[0]
            if t != last:
                if len(lastm) > 1 and lastm[1][:lp]==prefix: 
                    if i >= start and i < end:
                        lastm[0:0]=[lastpos]
                        r.append(lastm)
                    i=i+1
                    if i >= end: break
                last=t
            lastm=m
            lastpos=pos

        if len(lastm) > 1 and lastm[1][:lp]==prefix and i >= start and i < end:
            lastm[0:0]=[lastpos]
            r.append(lastm)

        return r

    def record(self, id):
        """Return the record data for the given id.
        """
        file=self.file
        read=file.read
        pos=self.index[id]
        file.seek(pos)
        h=read(24)
        oid_, prev, start, tlen, plen = struct.unpack(">iidii", h)
        if oid_ != id or prev < 0 or prev >= pos or plen > tlen or plen < 0:
            raise DatabaseError, ('Corrupted data record at %s' % pos)
        p=read(plen)
        t=read(tlen-plen-24)
        if t[-4:] != h[16:20]: 
            raise DatabaseError, 'Corrupted data record at %s' % pos

        return h, p, t

    def exportoid(self, oid, output_file, fallback=None, index=None):
        """Export the the object for the given oid

        All objects reachable from oid are exported too.
        
        By default, an error is raised if a cycle is detected.
        """
        unpack=struct.unpack
        StringType=type('')
        TupleType=type(())
        atoi=string.atoi

        if index is None: index=self.index
        write=output_file.write
        file=self.file
        seek=file.seek
        read=file.read

        exported={}
        was_exported=exported.has_key
        oids=[oid]

        while oids:
            id=oids[-1]
            del oids[-1]
            if type(id) is TupleType: id, klass = id
            elif type(id) is StringType: id=atoi(id)

            if was_exported(id):
                if id==oid:
                    raise 'ExportError', ('Object %s references itself' % id)
                continue

            if index.has_key(id):
                pos=index[id]
                seek(pos)
                h=read(24)
                oid_, prev, start, tlen, plen = unpack(">iidii", h)
                if (oid_ != id or prev < 0 or prev >= pos
                    or plen > tlen or plen < 0):
                    raise DatabaseError, 'Corrupted data record at %s' % pos
                p=read(plen)
                t=read(tlen-plen-24)
                if t[-4:] != h[16:20]: 
                    raise DatabaseError, 'Corrupted data record at %s' % pos
            else:
                # Hm, hopefully, we are a TDB and can fall back to our
                # base db
                if fallback is None:
                    # There is no ID.  We must have fallen victem to the old
                    # pack/undo bug.
                    continue
                h, p, t = fallback(id)

            write(h[:4])
            write("\0\0\0\0")
            write(h[8:])
            write(p)
            write(t)

            u=Unpickler(StringIO(p))
            u.persistent_load=oids
            u.noload()
            u.noload()

            exported[id]=1

    def importoid(self, new_oid, input_file, index=None, tname=''):
        """Import records from an export file.

        Arguments:

          oid -- The staring object ID for the new objects

          input_file -- A file(-like) object containing the data
                        to be imported in "export" format.
                        
          index -- An optional database index, used by LRTs

          tname -- An optional LRT name 
          
        """
        # This is harder than it looks.  We have to renumber all of the
        # object ids.  We will do this by un- and then re-pickling the
        # records. BLECH!

        TupleType=type(())
        read=input_file.read
        if index is None: index=self.index
        pos=self.pos
        file=self.file
        write=file.write
        oids={}
        wrote_oid=oids.has_key
        file.seek(pos)
        unpack=struct.unpack
        start=time.time()

        class Ghost: pass

        def persistent_id(object, Ghost=Ghost):
            if hasattr(object, '__class__') and object.__class__ is Ghost:
                return object.oid

        def bad_load(oid):
            raise 'Data Import Error', (
                'pickle has persistent references in part one.')

        def persistent_load(ooid,
                            Ghost=Ghost, StringType=type(''),
                            atoi=string.atoi, TupleType=TupleType,
                            oids=oids, wrote_oid=wrote_oid, new_oid=new_oid):
        
            "Remap a persistent id to a new ID and create a ghost for it."

            if type(ooid) is TupleType: ooid, klass = ooid
            elif type(ooid) is StringType: ooid,klass=atoi(ooid),None
            else: klass=None

            if wrote_oid(ooid): oid=oids[ooid]
            else:
                if klass is None: oid=new_oid()
                else: oid=new_oid(), klass
                oids[ooid]=oid

            Ghost=Ghost()
            Ghost.oid=oid
            return Ghost

        # This is a little bit lame. We need transaction info
        # for the imported records, but there's no good place to
        # get it since this is called from the application level.
        try: info=get_transaction().info()
        except: info="%.3f\t\timport" % getnow()
        if tname: info="%s %s" % (tname, info)

        first=1
        while 1:
            h=read(24)
            if len(h) < 24: break
            ooid, p, s, tlen, plen = unpack(">iidii", h)
            p=read(plen)
            read(tlen-plen-24) # skip meta-data and trailing length

            __traceback_info__=oids, ooid, not oids

            if oids:
                oid=oids[ooid]
                if type(oid) is TupleType: oid=oid[0]
            else: oids[ooid]=return_oid=oid=new_oid()

            pfile=StringIO(p)
            unpickler=Unpickler(pfile)
            unpickler.persistent_load=bad_load
            unpickler.load()
            l1=pfile.tell()
            unpickler.persistent_load=persistent_load
            newp=StringIO()
            newp.write(p[:l1])
            pickler=Pickler(newp,1)
            pickler.persistent_id=persistent_id
            pickler.dump(unpickler.load())
            p=newp.getvalue()
            plen=len(p)
            tlen=plen+len(info)+28
            h=pack(">iidii", oid, 0, start, tlen, plen)
            write("%s%s%s%s" % (h,p,info,h[16:20]))
            index[oid]=pos
            pos=self.pos=pos+tlen
            start=start+0.002
            if first:
                l=find(info, '\t')
                if l >= 0: info=info[:l]
                first=0

        return return_oid

    def __len__(self): return len(self.index)

    def has_key(self,key): return self.index.has_key(key)

    def keys(self): return self.index.keys()

    def max_key(self):
        index=self.index
        try: m=index.max_key()
        except: 
            m=index.keys()
            m=m and max(m) or 0
        return m

    def objectReferencesIn(self, oid):
        p=self[oid]
        u=Unpickler(StringIO(p))
        u.persistent_load=l=[]
        u.noload()
        try: u.noload()
        except: pass
        tt=type(())
        for i in range(len(l)):
            v=l[i]
            if type(v) is tt: l[i]=v[0]
            
        return l
        

def reachable(self, file, start_time, non=0):
    """Find all objects that were reachable as of start-time
    """

    index, pos = read_indext(file, self._file_size(), start_time)
    unpack=struct.unpack
    seek=file.seek
    read=file.read
    rootl=[-1] # Initial list of root objects
    rootd={} # Objects that have been visited
    inroot=rootd.has_key
    Unpickler=cPickle.Unpickler
    StringIO=cStringIO.StringIO
    StringType=type('')
    TupleType=type(())
    atoi=string.atoi
    while rootl:
        oid=rootl[-1]
        del rootl[-1]
        t=type(oid)
        if t is StringType: oid=atoi(oid)
        elif t is TupleType: oid=oid[0]
        if inroot(oid): continue
        try: pos=index[oid]
        except: pass # Broken reference, Waaaa! No point in following.
        else:
            rootd[oid]=1
            seek(pos+20)
            plen,=unpack(">i",read(4))
            p=read(plen)
            u=Unpickler(StringIO(p))
            u.persistent_load=rootl
            u.noload()
            try: u.noload()
            except:
                # Hm.  We failed to do second load.  Maybe there wasn't a
                # second pickle.  Let's check:
                f=StringIO(p)
                u=Unpickler(f)
                u.persistent_load=[]
                u.noload()
                if len(p) > f.tell(): raise ValueError, 'Error unpickling, %s' % p

    if non:
        for oid in rootd.keys(): del index[oid]
        del index[-1]
        return index
    else:
        return rootd


def subpack(self,start_time=None):
    """Pack a database file

    This operation replaces the current database file with a new
    file that has some records removed.  Records are removed that:

    A. Have been marked for removal (by undo or abort) by setting
       their OID values to 0.

    B. Are for old revisions that were created prior to the start
       time,

    C. Are for objects that were unreachable as of the start time.

    """
    # This is implemented as a stand-alone function to support
    # background packing.

    if start_time is None: start_time=time.time()
    if self.meta_index:
        raise TypeError, 'Attempt to pack a transaction file'

    self.readonly_mode(1)

    #readAt=self._readAt
    file=open(self.file_name,'r+b')
    seek=file.seek
    read=file.read
    dest_name=self.file_name+'.pk'
    newfile=open(dest_name,'wb')
    write=newfile.write
    write(MultipleRevision.packed_version)
    index=self.index
    newindex=Index()
    pack=struct.pack
    unpack=struct.unpack
    pos=newpos=len(MultipleRevision.packed_version)

    try:
        try: unreachable=reachable(self, file, start_time, non=1).has_key
        except: unreachable={}.has_key
    
        while 1:
            #h=readAt(24,pos) # 24=header_size
            seek(pos)
            h=read(24)
            #rpos=pos+24
            if len(h) !=  24:
                oid=0
                break
            oid,prev,start,tlen,plen=unpack(">iidii",h)
            p=pos
            pos=pos+tlen
            if not oid: continue              # Case A.
            if start >= start_time: break
            if index[oid] != p: continue    # Case B.
            if unreachable(oid): continue     # Case C.
            prev=0
            newindex[oid]=newpos
            #write(pack(">iidii",oid,prev,start,tlen,plen))
            #write(readAt(tlen-24,rpos))
            write(pack(">iidii",oid,prev,start,tlen,plen)+read(tlen-24))
            newpos=newpos+tlen
    
        while 1:
            if oid:
                try: prev=newindex[oid]
                except: prev=0
                newindex[oid]=newpos
                #write(pack(">iidii",oid,prev,start,tlen,plen))
                #write(readAt(plen,rpos))
                write(pack(">iidii",oid,prev,start,tlen,plen)+read(tlen-24))
                newpos=newpos+tlen
            #h=readAt(24,pos) # 24=header_size
            #rpos=pos+24
            seek(pos)
            h=read(24)
            if len(h) !=  24:
                oid=0
                break
            oid,prev,start,tlen,plen=unpack(">iidii",h)
            pos=pos+tlen

        if self._transactions is not None:
            _trans=transactions(newfile, '\t')
        else: _trans=[]
        newfile.close()
        file.close()
        self.finish_pack(newindex, newpos, _trans)
    finally:
        self.readonly_mode(0)

def transactions(file,transactions=None):
    """\
    Read a file's index to compute a list of transaction names.
    """ #'

    file.flush()
    seek=file.seek
    read=file.read
    unpack=struct.unpack
    find=string.find
    seek(0,2)
    file_size=file.tell()

    if transactions:
        m,pos,tlen=transactions[-1]
        if pos+tlen >= file_size: return transactions
        del transactions[-1]
    else:
        pos=len(MultipleRevision.packed_version)
        transactions=[]

    last_time=0
     
    mlast=''
    while 1:
        __traceback_info__ = pos
        seek(pos)
        h=read(24)
        if len(h) != 24: break
        tlen,plen=unpack(">ii",h[16:24])
        newpos=pos+tlen
        if newpos > file_size: break  # Must be a bad record
        if h[:4]!='\0\0\0\0':
            mlen=tlen-28
            if plen > 0: mlen=mlen-plen
            __traceback_info__ = pos
            seek(pos+tlen-mlen-4)
            m=read(mlen)
            lm=find(m,'\t')
            if lm > 0: pm=m[:lm]
            else: pm=m
            if m:
                if pm != mlast:
                    transactions.append((m,pos,tlen))
                    mlast=pm
                else:
                    t=transactions[-1]
                    transactions[-1]=(t[0],t[1],t[2]+tlen)
        pos=newpos

    return transactions

def read_index(file, revision_time=9.e30, pos=None, index=None, meta_index=0,
               min_oid=min_oid):
    """\
    Read a file's index up to the given time.
    """ #'

    file.flush()
    seek=file.seek
    read=file.read
    unpack=struct.unpack
    find=string.find
    seek(0,2)
    file_size=file.tell()
    if index is None:
        if meta_index:
            import MetaIndex
            index=MetaIndex.MetaIndex()
        else: index=Index()
    pos=pos or len(MultipleRevision.packed_version)
     
    tlast=0
    maxt=time.time()+1000
    last_tname=''
    while 1:
        __traceback_info__ = pos
        seek(pos)
        h=read(24) # 24=header_size
        if len(h) !=  24: break
        oid,prev,start,tlen,plen=unpack(">iidii",h)
        seek(pos+tlen-4)
        if (read(4) != h[16:20] or
            prev < 0 or prev >= pos or start < tlast or start > maxt
            or plen > tlen or plen < 0
            or oid < min_oid or tlen + pos > file_size):
            raise DatabaseError, ('Corrupted data record at %s' % pos)
        tlast=start-100
        if meta_index and oid:
            __traceback_info__ = oid, pos
            seek(pos+24+plen)
            tname=read(tlen-plen-28)
            l=find(tname,'\t')
            if l > 0: tname=tname[:l]
            l=find(tname,' ')
            if l < 0: raise DatabaseError, (
                'Bad tname at %s in %s' % (pos,self.file_name))
            tname=tname[:l]
            oid=oid,tname
        newpos=pos+tlen

        if start >= revision_time: break

        if oid: index[oid]=pos

        pos=newpos

    return index,pos

def read_indext(file, file_size, revision_time=9.e30, min_oid=min_oid):
    """\
    Read a file\'s index up to the the of the last transaction
    that starts before the given time.
    """ 

    unpack=struct.unpack
    find=string.find
    index=Index()
    pos=len(MultipleRevision.packed_version)
    read=file.read
    seek=file.seek
     
    tlast=0
    maxt=time.time()+1000
    mlast=''
    while 1:
        #h=readAt(24,pos)
        seek(pos)
        h=read(24)
        if len(h) !=  24: break
        oid,prev,start,tlen,plen=unpack(">iidii",h)
        newpos=tlen+pos
        seek(pos+tlen-4)
        if (read(4) != h[16:20] or
            prev < 0 or prev >= pos or start < tlast or start > maxt
            or plen > tlen or plen < 0 or
            oid < min_oid or newpos > file_size):
            raise DatabaseError, ('Corrupted data record at %s' % pos)
        tlast=start-100
        #m=readAt(tlen-plen-28,pos+24+plen)
        seek(plen,1)
        m=read(tlen-plen-28)
        lm=find(m,'\t')
        if lm > 0: m=m[:lm]
        if m != mlast:
            if start >= revision_time: break
            mlast=m

        if oid: index[oid]=pos

        pos=newpos

    return index,pos

def print_index(file):
    """Read a file\'s index up to the given time.
    """ 

    if type(file)==type(''): file=open(file,'rb')
    pos=len(MultipleRevision.packed_version)
    seek=file.seek
    read=file.read
    ctime=time.ctime
    unpack=struct.unpack
    tt=type(())
     
    while 1:
        __traceback_info__ = pos
        seek(pos)
        h=read(24) # 24=header_size
        if len(h) !=  24: break
        oid,prev,start,tlen,plen=unpack(">iidii",h)
        print ("%s:\t%s\t%s\t%s\t%s\t%s\t"
               % (pos,oid,prev,ctime(start),tlen,plen)),
        if oid > 0 and plen > 0:
            p=read(plen)
            p=Unpickler(StringIO(p))
            try: p=p.load()
            except: p=None
            if type(p) is tt: p=p[0].__name__
            else:
                try: p=p.__class__.__name__
                except: p=type(p).__name__
        else: p=''
        mlen=tlen-28
        if plen > 0: mlen=mlen-plen
        seek(pos+tlen-mlen-4)
        m=read(mlen)
        print ("%s\t%s" % (p,m,))
        pos=pos+tlen

# Try to create a function that creates Unix file locks.  On windows
# this will fail, but we don't need it on windows.
try:
    import fcntl, FCNTL

    lock_file_FLAG=FCNTL.LOCK_EX|FCNTL.LOCK_NB

    def lock_file(file):
        try: un=file.fileno()
        except: return # don't care if not a real file

        fcntl.flock(un,lock_file_FLAG)

except:
    def lock_file(file): pass
    

Default=MR=MultipleRevision # Default is a parameter for SDB type

def Index():
    global Index

    try:
        import iTree
        Index=iTree.Bucket
    except: 
        def Index(): return {}

    return Index()


def main(): print_index(sys.argv[1])

if __name__ == "__main__": print_index(sys.argv[1])