IntIntTblLR.C

Go to the documentation of this file.

// Copyright (C) 2001, Compaq Computer Corporation
// 
// This file is part of Vesta.
// 
// Vesta is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
// 
// Vesta is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public
// License along with Vesta; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

// Last modified on Thu Apr 28 23:39:45 EDT 2005 by ken@xorian.net        
//      modified on Sun Jul 28 12:03:20 EDT 2002 by lken@remote.xorian.net
//      modified on Fri Feb 27 18:44:51 PST 1998 by heydon

#include <Basics.H>
#include <FS.H>
#include <VestaLog.H>
#include <Recovery.H>

#include "IntIntTblLR.H"

using std::istream;
using std::ostream;
using std::endl;

// the value of unused entries in the table
static const short Unused = -1;

IntIntTblLR::IntIntTblLR(int sizeHint) throw ()
: numEntries(0), eltLen(sizeHint)
{
    if (sizeHint > 0) {
      this->elt = NEW_PTRFREE_ARRAY(short, sizeHint);
      for (int i = 0; i < this->eltLen; i++) {
        this->elt[i] = Unused;
      }
    } else {
        assert(sizeHint == 0);
        this->elt = (short *)NULL;
    }
}

IntIntTblLR::IntIntTblLR(const IntIntTblLR *tbl) throw ()
: numEntries(tbl->numEntries), eltLen(tbl->eltLen)
{
    if (this->eltLen > 0) {
      this->elt = NEW_PTRFREE_ARRAY(short, this->eltLen);
      int numUsed = 0;
      for (int i = 0; i < this->eltLen; i++) {
        this->elt[i] = tbl->elt[i];
        if (tbl->elt[i] != Unused) numUsed++;
      }
      assert(numUsed == this->numEntries);
    } else {
        assert(this->eltLen == 0 && this->numEntries == 0);
        this->elt = (short *)NULL;
    }
}

bool IntIntTblLR::Get(short k, /*OUT*/ short& v) const throw ()
{
    bool res;
    if (k < this->eltLen && this->elt != (short *)NULL) {
        short val = this->elt[k];
        res = (val != Unused);
        if (res) v = val;
    } else {
        res = false;
    }
    return res;
}

bool IntIntTblLR::Put(short k, short v) throw ()
{
    bool res;

    if (k < this->eltLen && this->elt != (short *)NULL) {
        // fast path: simply test if the slot is in use
        res = (this->elt[k] != Unused);
        if (!res) this->numEntries++;
    } else {
        // slow path: the array of elements must be extended or allocated
        int oldEltLen = this->eltLen;
        this->eltLen = max(k+1, oldEltLen+10);
        short *newElt = NEW_PTRFREE_ARRAY(short, this->eltLen);
        if (this->elt != (short *)NULL) {
            // copy old elts to new array; make remaining elts unused
            int i;
            for (i = 0; i < oldEltLen; i++) {
                newElt[i] = this->elt[i];
            }
            for (/*SKIP*/; i < this->eltLen; i++) {
                newElt[i] = Unused;
            }
        } else {
            // initialize the array to entirely unused elts
            for (int i = 0; i < this->eltLen; i++) {
                newElt[i] = Unused;
            }
        }
        this->elt = newElt;
        this->numEntries++;
        res = false;
    }
    this->elt[k] = v;
    return res;
}

bool IntIntTblLR::Delete(short k, /*OUT*/ short& v) throw ()
{
    bool res;
    if (k < this->eltLen && this->elt != (short *)NULL
        && this->elt[k] != Unused) {
        v = this->elt[k];
        this->elt[k] = Unused;
        this->numEntries--;
        res = true;
    } else {
        res = false;
    }
    return res;
}

void IntIntTblLR::Log(VestaLog& log) const
  throw (VestaLog::Error)
{
    log.write((char *)(&(this->numEntries)), sizeof(this->numEntries));
    log.write((char *)(&(this->eltLen)), sizeof(this->eltLen));
    if (this->numEntries > 0) {
        int numWritten = 0;
        for (short k = 0; k < this->eltLen; k++) {
            if (this->elt[k] != Unused) {
                log.write((char *)(&k), sizeof(k));
                log.write((char *)(&(this->elt[k])), sizeof(this->elt[k]));
                numWritten++;
            }
        }
        assert(numWritten == this->numEntries);
    }
}

void IntIntTblLR::Recover(RecoveryReader &rd)
  throw (VestaLog::Error, VestaLog::Eof)
/* We must set any unused entries to "Unused". We could do this by setting all
   entries to "Unused" immediately after the array is allocated. But if the
   array is mostly full, that would mean writing most entries twice. Instead,
   we set entries to "Unused" between the used entries, and at the end of the
   loop. The correctness of this algorithm relies on the fact that the entries
   are written by the corresponding "Log" method in order of increasing key.
*/
{
    rd.readAll((char *)(&(this->numEntries)), sizeof(this->numEntries));
    rd.readAll((char *)(&(this->eltLen)), sizeof(this->eltLen));
    if (this->numEntries > 0) {
        short nextToWrite = 0;
        this->elt = NEW_PTRFREE_ARRAY(short, this->eltLen);
        // Invariant: All elements of "this->elt" in the half-open
        // interval "[0, nextToWrite)" have been written.
        for (int i = 0; i < this->numEntries; i++) {
            short k;
            rd.readAll((char *)(&k), sizeof(k));
            // make intervening entries unused
            assert(k >= nextToWrite);
            while (nextToWrite < k) {
                this->elt[nextToWrite++] = Unused;
            }
            assert(k < this->eltLen);
            rd.readAll((char *)(&(this->elt[k])), sizeof(this->elt[k]));
            nextToWrite++; // == k+1
        }
        // make any remaining entries unused
        while (nextToWrite < this->eltLen) {
            this->elt[nextToWrite++] = Unused;
        }
    } else {
        this->elt = (short *)NULL;
    }
}

void IntIntTblLR::Write(ostream &ofs) const
  throw (FS::Failure)
{
    FS::Write(ofs, (char *)(&(this->numEntries)), sizeof(this->numEntries));
    FS::Write(ofs, (char *)(&(this->eltLen)), sizeof(this->eltLen));
    if (this->numEntries > 0) {
        int numWritten = 0;
        for (short k = 0; k < this->eltLen; k++) {
            if (this->elt[k] != Unused) {
                FS::Write(ofs, (char *)(&k), sizeof(k));
                FS::Write(ofs, (char *)(&(this->elt[k])), sizeof(this->elt[k]));
                numWritten++;
            }
        }
        assert(numWritten == this->numEntries);
    }
}

void IntIntTblLR::Read(istream &ifs)
  throw (FS::EndOfFile, FS::Failure)
/* We must set any unused entries to "Unused". We could do this by setting all
   entries to "Unused" immediately after the array is allocated. But if the
   array is mostly full, that would mean writing most entries twice. Instead,
   we set entries to "Unused" between the used entries, and at the end of the
   loop. The correctness of this algorithm relies on the fact that the entries
   are written by the corresponding "Write" method in order of increasing key.
*/
{
    FS::Read(ifs, (char *)(&(this->numEntries)), sizeof(this->numEntries));
    FS::Read(ifs, (char *)(&(this->eltLen)), sizeof(this->eltLen));
    if (this->numEntries > 0) {
        short nextToWrite = 0;
        this->elt = NEW_PTRFREE_ARRAY(short, this->eltLen);
        // Invariant: All elements of "this->elt" in the half-open
        // interval "[0, nextToWrite)" have been written.
        for (int i = 0; i < this->numEntries; i++) {
            short k;
            FS::Read(ifs, (char *)(&k), sizeof(k));
            // make intervening entries unused
            assert(k >= nextToWrite);
            while (nextToWrite < k) {
                this->elt[nextToWrite++] = Unused;
            }
            assert(k < this->eltLen);
            FS::Read(ifs, (char *)(&(this->elt[k])), sizeof(this->elt[k]));
            nextToWrite++; // == k+1
        }
        // make any remaining entries unused
        while (nextToWrite < this->eltLen) {
            this->elt[nextToWrite++] = Unused;
        }
    } else {
        this->elt = (short *)NULL;
    }
}

inline void Indent(ostream &os, int indent) throw ()
{
    for (int i = 0; i < indent; i++) os << " ";
}

void IntIntTblLR::Print(ostream &os, int indent) const throw ()
{
    const int NumPerLine = 7;
    int cnt = 0;
    os << "{ ";
    for (short k = 0; cnt < this->numEntries; k++) {
        short v;
        if (this->Get(k, /*OUT*/ v)) {
            if (cnt > 0) os << ", ";
            if (cnt % NumPerLine == 0) {
                os << endl; Indent(os, indent);
            }
            os << k << "->" << v;
            cnt++;
        }
    }
    os << " }" << endl;
}

bool IntIntTblIter::Next(/*OUT*/ short& k, /*OUT*/ short& v) throw ()
{
    bool res;
    assert(!(this->done));
    while (this->k < this->tbl->eltLen && this->tbl->elt[this->k] == Unused) {
        (this->k)++;
    }
    if (this->k < this->tbl->eltLen) {
        k = this->k;
        v = this->tbl->elt[k];
        (this->k)++;
        res = true;
    } else {
        this->done = true;
        res = false;
    }
    return res;
}

---