slotfile.cpp

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C++ 代码 · 共 843 行 · 第 1/2 页

/*
 *
 *          Copyright (C) 1994, M. A. Sridhar
 *  
 *
 *     This software is Copyright M. A. Sridhar, 1994. You are free
 *     to copy, modify or distribute this software  as you see fit,
 *     and to use  it  for  any  purpose, provided   this copyright
 *     notice and the following   disclaimer are included  with all
 *     copies.
 *
 *                        DISCLAIMER
 *
 *     The author makes no warranties, either expressed or implied,
 *     with respect  to  this  software, its  quality, performance,
 *     merchantability, or fitness for any particular purpose. This
 *     software is distributed  AS IS.  The  user of this  software
 *     assumes all risks  as to its quality  and performance. In no
 *     event shall the author be liable for any direct, indirect or
 *     consequential damages, even if the  author has been  advised
 *     as to the possibility of such damages.
 *
 */



// This may look like C code, but it is really -*- C++ -*-

#include "base/binding.h"
#include "base/bitset.h"
#include "base/bytestrm.h"
#include "io/slotfile.h"


#define NEW_OP new

// Notes on the SlottedFile implementation:
// 
// The  slotted file is viewed  as a tree  with three levels: the root, its
// children and its  grandchildren. The  root  has 2**14 =  16384 children,
// among which the  the leftmost 2**12 = 4096  are actual records, and  the
// remaining are bitmaps (instances of  CL_BitSet), called block    bitmaps.
// At  the root are  stored  two bitmaps, each  containing  16384 bits: the
// fullMap, in which a bit is on if the corresponding child  of the root is
// full, and  the nonemptyMap, in which  a bit is  on  if the corresponding
// child  of the root is  not empty. Note  that every element in the bitset
// fullMap also  occurs in nonemptyMap.    The former bitset is  useful for
// fast allocation, while the latter is useful for fast iteration.
// 
// This tree is stored in pre-order on the disk file.



#define ROOT_WIDTH  14           // 2**(ROOT_WIDTH) is the number of
                                 // children of the root; thus ROOT_WIDTH is
                                 // the number of bits needed to specify a
                                 // block bitmap
#define WIDTH       16           // #bits needed for specifying a
                                 // record in a block

#define RECORDS_PER_BLOCK  (((ulong) 1) << WIDTH)
                                 // #records in a block

#define UNUSED_BITS 4096         // #children of the root that are records
                                 // and not blocks.

// CL_SlottedFileHandle has the following layout:
//
//    ---------------------------------------------------------------
//    |01|<------   Block bitmap # ------>|<-- Record # in block -->|
//    ---------------------------------------------------------------
//        ^                                ^                       ^
//      Bit 29                           Bit 15                  Bit 0
//
// The 1 in bit 30 is to ensure that every handle is nonzero.
//


class CL_SlottedFileHeader: public CL_Object {

    // This is a private class encapsulating the header of a SlottedFile.
public:
    CL_SlottedFileHeader ();
    long StorableFormWidth () const;
    bool ReadFrom (const CL_Stream&);
    bool WriteTo (CL_Stream&) const;
    static long StoreWidth (); // Provided for the purpose of efficiency 

    const char* ClassName () const {return "CL_SlottedFileHeader";};

    void operator= (const CL_SlottedFileHeader& hdr);

    void operator= (const CL_Object& o)
        {*this = (const CL_SlottedFileHeader&) o;};

    // Instance data:
    CL_BitSet fullMap;
    CL_BitSet nonemptyMap;
    long allocCount; // #allocated slots in the file
    long slotSize;   // Size of each slot, in bytes
    short userHeaderSize;
};

void CL_SlottedFileHeader::operator= (const CL_SlottedFileHeader& hdr)
{
    fullMap        = hdr.fullMap;
    nonemptyMap    = hdr.nonemptyMap;
    allocCount     = hdr.allocCount;
    slotSize       = hdr.slotSize;
    userHeaderSize = hdr.userHeaderSize;
}

long CL_SlottedFileHeader::StoreWidth ()
{
    static long width = -1;
    if (width == -1) {
        CL_SlottedFileHeader hdr;
        width = hdr.StorableFormWidth();
    }
    return width;
}



CL_SlottedFileHeader::CL_SlottedFileHeader ()
: fullMap (1L << ROOT_WIDTH), nonemptyMap (1L << ROOT_WIDTH)
{
    userHeaderSize = 0;
}

long CL_SlottedFileHeader::StorableFormWidth() const
{
    return sizeof (short) + 2*sizeof (long) + 2*fullMap.StorableFormWidth();
}

bool CL_SlottedFileHeader::WriteTo (CL_Stream& s) const
{
    return s.Write (userHeaderSize) && s.Write (allocCount) && s.Write
        (slotSize) && fullMap.WriteTo (s) && nonemptyMap.WriteTo (s);
}

bool CL_SlottedFileHeader::ReadFrom (const CL_Stream& s)
{
    return s.Read (userHeaderSize) && s.Read (allocCount) && s.Read
        (slotSize) && fullMap.ReadFrom (s) && nonemptyMap.ReadFrom (s);
}    



// ------------------------ IO_Iter structure ---------------------
// 
// struct IO_Iter {
//     IO_Iter () : _rootIter (root), _blockIter (block) {};
//     CL_BitSet root, block;
//     CL_BitSetIterator _rootIter, _blockIter;
//     short _blockIndex;
// };



/* ---------------------- Handle manipulation functions ------------- */

inline CL_SlottedFileHandle __MakeHandle (long record_no,
                                          long block_map_index)
{
    return record_no | (((ulong) block_map_index) <<  WIDTH)
        | (((ulong) 1) << (ROOT_WIDTH + WIDTH));
}

inline long __RecordNumber (CL_SlottedFileHandle h)
{
    return ((((ulong) 1) << WIDTH) - 1) & h;
}

inline long __BlockMapIndex (CL_SlottedFileHandle h)
{
    return (h  >> WIDTH) & ((((ulong) 1) << ROOT_WIDTH) - 1);
}





/* ------------------------ CL_SlottedFile methods --------------------- */


CL_SlottedFile::CL_SlottedFile (CL_Stream& s, bool report)
: _file (s), _reportErrors (report)
{
    _header = new CL_SlottedFileHeader;
}

/* ------------------------------------------------------------------ */

CL_SlottedFile::~CL_SlottedFile ()
{
    if (_header) {
        delete _header;
    }
}


/* ------------------------------------------------------------------ */

CL_SlottedFileHandle CL_SlottedFile::AllocateSlot ()
{
    if (!PrepareToChange())
        return 0;
    CL_SlottedFileHandle h =  _GetSlot ();
    Notify();
    return h;
}

/* ------------------------------------------------------------------ */

CL_SlottedFileHandle CL_SlottedFile::AddRecord (uchar* record)
{
    if (!PrepareToChange())
        return 0;
    CL_SlottedFileHandle h = _GetSlot ();
    if (h)
        if (!_file.Write (_RecordOffset (h), record, _slotSize))
            _DoError ("AddRecord", h);
    Notify ();
    return h;
}


/* ------------------------------------------------------------------ */


bool CL_SlottedFile::IsValid (CL_SlottedFileHandle h) const
{
    if (!_ReadHeader (*_header)) {
        _DoError ("IsValid: header read");
        return FALSE;
    }
    long rec   = __RecordNumber (h);
    long index = __BlockMapIndex (h);
    if (index < UNUSED_BITS) {
        ulong hi_bits = h & (3L << (WIDTH + ROOT_WIDTH));
        return (rec == index)
            && (hi_bits == (1L << (WIDTH + ROOT_WIDTH)))
            && _header->fullMap.Includes (rec);
    }
    CL_BitSet block_map;
    if (!_file.Read (_BlockBitmapOffset (index), block_map)) {
        _DoError ("IsValid: block map read");
        return FALSE;
    }
    return block_map.Includes (rec);
}


/* ------------------------------------------------------------------ */

long CL_SlottedFile::SlotsAllocated () const
{
    if (!_ReadHeader (*_header)) {
        _DoError ("SlotsAllocated: header read");
        return 0;
    }
    return _header->allocCount;
}


/* ------------------------------------------------------------------ */


bool CL_SlottedFile::RetrieveRecord (CL_SlottedFileHandle h,
                                     uchar* record) const
{
    if (!IsValid (h))
        return FALSE;
    if (_file.Read (_RecordOffset (h), record, _slotSize) != _slotSize) {
        _DoError ("RetrieveRecord: record read failed", h);
        return FALSE;
    }
    return TRUE;
}


/* ------------------------------------------------------------------ */


bool CL_SlottedFile::ModifyRecord (CL_SlottedFileHandle h,
                                   uchar* record)
{
    if (!PrepareToChange())
        return FALSE;
    if (!IsValid (h))
        return FALSE;
    if (!_file.Write (_RecordOffset (h), record, _slotSize)) {
        _DoError ("ModifyRecord: record write failed", h);
        return FALSE;
    }
    Notify ();
    return TRUE;
}




/* ------------------------------------------------------------------ */



bool CL_SlottedFile::DeleteRecord (CL_SlottedFileHandle handle)
    // Free a previously-allocated slot
{
    if (!PrepareToChange())
        return FALSE;
    ulong hi_bits = handle & (3L << (WIDTH + ROOT_WIDTH));
    if (hi_bits != (1L << (WIDTH + ROOT_WIDTH)))
        return FALSE;
    long rec = __RecordNumber (handle);
    long index = __BlockMapIndex (handle);
    long new_file_size = -1L; // Will be changed appropriately if the file
                              // needs to be truncated
    CL_BitSet block_map;
    if (!_ReadHeader (*_header))
        return FALSE;
    if (index < UNUSED_BITS) {
        // The index specifies a record, not a bitmap
        _header->fullMap.Remove (index);
        _header->nonemptyMap.Remove (index);
        if (_header->nonemptyMap.IsEmpty()) {
            // There are no more records in the file after this deletion
            new_file_size = CL_SlottedFileHeader::StoreWidth();
        }
        else {
            long l = _header->nonemptyMap.Largest();
            if (l < index) {
                // We're deleting the record at the end of the file
                new_file_size = _BlockBitmapOffset (l) + _slotSize;
            }
        }
    }
    else {
        // The index specifies a bitmap
        CL_Offset block_offset = _BlockBitmapOffset (index);
        long file_size = _file.Size();
        if (block_offset < 0 || block_offset >= file_size)
            return FALSE;
        if (!_file.Read (block_offset, block_map)) {
            _DoError ("DeleteRecord: Level-1 map read failed");
            return FALSE;
        }
        block_map.Remove (rec);
        _header->fullMap.Remove (index);
        register long rec_end = _RecordOffset (handle) + _slotSize;
        if (block_map.IsEmpty()) {
            _header->nonemptyMap.Remove (index);
            if (file_size <= rec_end) {
                // We're removing the only allocated record in the block
                new_file_size = block_offset;
            }
        }
        else {
            if (file_size <= rec_end) {
                // We're removing the record at the end of the file
                new_file_size = rec_end - _slotSize;
            }
        }
        if (new_file_size != block_offset &&
            !_file.Write (block_offset, block_map)) {
            _DoError ("DeleteRecord: block map write failed", handle);
            return FALSE;
        }
    }
    _header->allocCount--;
    if (!_WriteHeader (*_header))
        return FALSE;
    if (new_file_size != -1L && !_file.ChangeSize (new_file_size)) {
        _DoError ("DeleteRecord: ChangeSize failed");
        return FALSE;
    }
    Notify ();
    return TRUE;
}



/* ------------------------------------------------------------------ */
bool CL_SlottedFile::ReadHeader (uchar* header) const
{
    return (_userHeaderSize > 0)
        ? _file.Read (CL_SlottedFileHeader::StoreWidth(), header,
                      _userHeaderSize)
        : FALSE;
}

        

// Write the parameter into the user-defined header. Returns
// TRUE on success, FALSE on i/o error.
bool CL_SlottedFile::WriteHeader (uchar* header)
{
    return (_userHeaderSize > 0)
        ? _file.Write (CL_SlottedFileHeader::StoreWidth(), header,
                       _userHeaderSize)
        : FALSE;
}






CL_SlottedFileHandle CL_SlottedFile::FirstRecord (uchar* record) const
{
    if (!_ReadHeader (*_header)) {
        _DoError ("FirstRecord: header read");
        return 0;
    }
    if (_header->allocCount <= 0)
        return 0;
    long index = _header->nonemptyMap.Smallest ();