PrefixTbl.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 Fri Apr 22 18:24:53 EDT 2005 by ken@xorian.net         
//      modified on Sat Feb 12 12:02:12 PST 2000 by mann  
//      modified on Wed May 13 16:29:15 PDT 1998 by heydon
//      modified on Wed Mar 18 12:08:30 PST 1998 by yuanyu

#include <Basics.H>
#include <Generics.H>
#include <SRPC.H>
#include "TextIO.H"
#include "FV2.H"
#include "PrefixTbl.H"

#include <iomanip>

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

// Expected number of arcs in an FV2::T
static const int ArcCountHint = 4;

PrefixTbl::PrefixTbl(int szHint) throw ()
: numArcs(0), maxArcs(szHint)
{
    if (szHint > 0) {
        this->indexArray = NEW_PTRFREE_ARRAY(Basics::uint16, szHint);
        this->arcArray = NEW_ARRAY(Text, szHint);
    } else {
        this->indexArray = (Basics::uint16 *)NULL;
        this->arcArray = (Text *)NULL;
    }
}

int PrefixTbl::AddArc(const Text& arc) throw (PrefixTbl::Overflow)
{
    int res = this->numArcs;
    if (this->numArcs >= this->maxArcs) {
        // Algorithm for picking our new size without overflowing:
        // Double if possible.  Otherwise increse by 1/2, or 1/4, or
        // 1/8th...  If we can't increase without overflowing, we'll
        // die with an assertion failure.
        Basics::uint16 size_increment = max(this->maxArcs, 2);
        Basics::uint16 new_max;
        while(((new_max = (this->maxArcs + size_increment)) <= this->maxArcs) &&
              (size_increment > 0))
          {
            size_increment >>= 1;
          }
        // If we couldn't increase our size without overflowing, throw
        // an exception.
        if(size_increment == 0)
          {
            throw PrefixTbl::Overflow(this->numArcs);
          }
        this->maxArcs = new_max;
        assert(this->maxArcs > this->numArcs);
        Basics::uint16 *newIndexArray =
          NEW_PTRFREE_ARRAY(Basics::uint16, this->maxArcs);
        Text *newArcArray = NEW_ARRAY(Text, this->maxArcs);
        for (int i = 0; i < this->numArcs; i++) {
            newIndexArray[i] = this->indexArray[i];
            newArcArray[i] = this->arcArray[i];
        }
        this->indexArray = newIndexArray;
        this->arcArray = newArcArray;
    }
    this->arcArray[this->numArcs++] = arc;
    return res;
}

int PrefixTbl::Put(const char *path, TextIntTbl /*INOUT*/ &tbl) throw (PrefixTbl::Overflow)
{
    int resIdx;
    if (!tbl.Get(Text(path, /*copy=*/ (void*)1), /*OUT*/ resIdx)) {
        // local buffer so allocation can be avoided in most cases
        const int BuffSz = 100;
        char buff[BuffSz + 1];

        // make a mutable copy of "path" in "str"
        int pathLen = strlen(path);
        char *str = (pathLen <= BuffSz)
          ? buff
          : (NEW_PTRFREE_ARRAY(char, pathLen + 1));
        memcpy(str, path, pathLen + 1);    // copy '\0' too

        char *curr = str + (pathLen - 1);
        while (curr >= str && *curr != '/') curr--;
        resIdx = this->AddArc(Text(curr + 1));
        bool inTbl = tbl.Put(Text(str), resIdx); assert(!inTbl);
        int lastIdx = resIdx;
        while (curr >= str) {
            assert(*curr == '/');
            *curr = '\0';
            int currIdx;
            if (tbl.Get(Text(str, /*copy=*/ (void*)1), /*OUT*/ currIdx)) {
                this->indexArray[lastIdx] = currIdx;
                return resIdx;
            } else {
                while (--curr >= str && *curr != '/') /*SKIP*/;
                currIdx = this->AddArc(Text(curr + 1));
                inTbl = tbl.Put(Text(str), currIdx); assert(!inTbl);
                this->indexArray[lastIdx] = currIdx;
                lastIdx = currIdx;
            }
        }
        this->indexArray[lastIdx] = PrefixTbl::endMarker;
    }
    return resIdx;
}

int PrefixTbl::Put(const FV2::T& ts, TextIntTbl /*INOUT*/ &tbl) throw (PrefixTbl::Overflow)
{
    int arcIdx = ts.size() - 1;
    if (arcIdx < 0) return -1;

    int resIdx;
    char *str = ts.ToText().chars();
    int strPos = (int) strlen(str);
    if (!tbl.Get(Text(str, /*copy=*/ (void*)1), /*OUT*/ resIdx)) {
        resIdx = this->AddArc(ts.get(arcIdx));
        bool inTbl = tbl.Put(Text(str), resIdx); assert(!inTbl);
        int lastIdx = resIdx;
        while (arcIdx-- > 0) {
            while (str[--strPos] != '/') /*SKIP*/;
            str[strPos] = '\0';
            int currIdx;
            if (tbl.Get(Text(str, /*copy=*/ (void*)1), /*OUT*/ currIdx)) {
                this->indexArray[lastIdx] = currIdx;
                return resIdx;
            } else {
                currIdx = this->AddArc(ts.get(arcIdx));
                inTbl = tbl.Put(Text(str), currIdx); assert(!inTbl);
                this->indexArray[lastIdx] = currIdx;
                lastIdx = currIdx;
            }
        }
        this->indexArray[lastIdx] = PrefixTbl::endMarker;
    }
    return resIdx;
}

FV2::T *PrefixTbl::Get(int idx) const throw ()
{
    FV2::T *path = NEW_CONSTR(FV2::T, (ArcCountHint));
    register int index = idx;
    while ((index != PrefixTbl::endMarker) &&
           (index != -1)) {
        assert(0 <= index  && index < this->numArcs);
        path->addlo(this->arcArray[index]);
        index = this->indexArray[index];
    }
    return path;
}

bool PrefixTbl::GetString(int idx, char *buff, int buff_len) const throw ()
/* This method constructs the string "backwards", starting at the end of the
   buffer and prepending arcs (just as the "Get" method above uses "addlo" to 
   prepend each arc). */
{
    // first, build list of arc indices
    const int InitBuffSz = 20;
    int indexBuff[InitBuffSz];
    int buffSz = InitBuffSz;
    int *indexList = indexBuff;
    register int num_arcs = 0;
    register int index = idx;
    while ((index != PrefixTbl::endMarker) &&
           (index != -1)) {
        if (num_arcs >= buffSz) {
            // slow path -- copy to dynamically-allocated buffer
            buffSz <<= 1; // double buffer size
            int *newList = NEW_PTRFREE_ARRAY(int, buffSz);
            for (int i = 0; i < num_arcs; i++) {
                newList[i] = indexList[i];
            }
            indexList = newList;
        }
        indexList[num_arcs++] = index;
        index = this->indexArray[index];
    }

    // second, write arcs into "buff"
    register char *curr = buff;
    buff_len--; // subtract one for required null terminator
    while (--num_arcs >= 0) {
        index = indexList[num_arcs];
        assert(0 <= index  && index < this->numArcs);
        Text *txt = &(this->arcArray[index]);
        int arcLen = txt->Length();
        if (arcLen > buff_len) return false; // not enough space
        (void) memcpy(curr, txt->cchars(), arcLen);
        curr += arcLen;
        *curr++ = '/';
        buff_len -= (arcLen + 1);
    }

    // replace final '/' by null and return
    *(curr - 1) = '\0';
    return true;
}

int PrefixTbl::MemorySize() const throw ()
{
    register int res = sizeof(this->numArcs) + sizeof(this->maxArcs);
    if (this->indexArray != (Basics::uint16 *)NULL) {
        res += this->maxArcs * sizeof(this->indexArray[0]);
        res += this->maxArcs * sizeof(this->arcArray[0]);
    }
    for (int i = 0; i < this->numArcs; i++) {
        res += this->arcArray[i].Length() + 1;
    }
    return res;
}

int PrefixTbl::Skip(istream &ifs) throw (FS::EndOfFile, FS::Failure)
{
    int res = 0;
    Basics::uint16 numArcs;
    FS::Read(ifs, (char *)(&numArcs), sizeof(numArcs));
    res += sizeof(numArcs);
    if (numArcs > 0) {
        for (int i = 0; i < numArcs; i++) {
            Basics::uint16 idx; FS::Read(ifs, (char *)(&idx), sizeof(idx));
            res += sizeof(idx);
            res += TextIO::Skip(ifs);
        }
    }
    return res;
}

void PrefixTbl::Write(ostream &ofs) const throw (FS::Failure)
{
    FS::Write(ofs, (char *)(&(this->numArcs)), sizeof(this->numArcs));
    if (this->numArcs > 0) {
        for (int i = 0; i < this->numArcs; i++) {
            Basics::uint16 *idx = &(this->indexArray[i]);
            FS::Write(ofs, (char *)(idx), sizeof(*idx));
            TextIO::Write(ofs, this->arcArray[i]);
        }
    }
}

void PrefixTbl::Read(istream &ifs) throw (FS::EndOfFile, FS::Failure)
{
    FS::Read(ifs, (char *)(&(this->numArcs)), sizeof(this->numArcs));
    this->maxArcs = this->numArcs;
    if (this->numArcs > 0) {
        this->indexArray = NEW_PTRFREE_ARRAY(Basics::uint16, this->numArcs);
        this->arcArray = NEW_ARRAY(Text, this->numArcs);
        for (int i = 0; i < this->numArcs; i++) {
            Basics::uint16 *idx = &(this->indexArray[i]);
            FS::Read(ifs, (char *)(idx), sizeof(*idx));
            TextIO::Read(ifs, /*OUT*/ this->arcArray[i]);
        }
    } else {
        this->indexArray = (Basics::uint16 *)NULL;
        this->arcArray = (Text *)NULL;
    }
}

void PrefixTbl::Log(VestaLog &log) const throw (VestaLog::Error)
{
    log.write((char *)(&(this->numArcs)), sizeof(this->numArcs));
    if (this->numArcs > 0) {
        for (int i = 0; i < this->numArcs; i++) {
            Basics::uint16 *idx = &(this->indexArray[i]);
            log.write((char *)(idx), sizeof(*idx));
            TextIO::Log(log, this->arcArray[i]);
        }
    }
}

void PrefixTbl::Recover(RecoveryReader &rd)
  throw (VestaLog::Error, VestaLog::Eof)
{
    rd.readAll((char *)(&(this->numArcs)), sizeof(this->numArcs));
    this->maxArcs = this->numArcs;
    if (this->numArcs > 0) {
        this->indexArray =
          NEW_PTRFREE_ARRAY(Basics::uint16, this->numArcs);
        this->arcArray = NEW_ARRAY(Text, this->numArcs);
        for (int i = 0; i < this->numArcs; i++) {
            Basics::uint16 *idx = &(this->indexArray[i]);
            rd.readAll((char *)(idx), sizeof(*idx));
            TextIO::Recover(rd, /*OUT*/ this->arcArray[i]);
        }
    } else {
        this->indexArray = (Basics::uint16 *)NULL;
        this->arcArray = (Text *)NULL;
    }
}

void PrefixTbl::Send(SRPC &srpc) const throw (SRPC::failure)
{
    srpc.send_int((int)(this->numArcs));
    if (this->numArcs > 0) {
        srpc.send_short_array((Basics::int16 *) this->indexArray,
                              this->numArcs);
        for (int i = 0; i < this->numArcs; i++) {
            srpc.send_Text(this->arcArray[i]);
        }
    }
}

void PrefixTbl::Recv(SRPC &srpc) throw (SRPC::failure)
{
    this->numArcs = (Basics::uint16) srpc.recv_int();
    this->maxArcs = this->numArcs;
    if (this->numArcs > 0) {
        int dummyLen = 0;
        this->indexArray =
          (Basics::uint16 *) srpc.recv_short_array(/*OUT*/ dummyLen);
        assert(dummyLen == this->numArcs);
        this->arcArray = NEW_ARRAY(Text, this->numArcs);
        for (int i = 0; i < this->numArcs; i++) {
            srpc.recv_Text(/*OUT*/ this->arcArray[i]);
        }
    } else {
        this->indexArray = (Basics::uint16 *)NULL;
        this->arcArray = (Text *)NULL;
    }
}

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

void PrefixTbl::Print(ostream &os, int indent) const throw ()
{
    Indent(os, indent); os << "Index  Prefix  Arc" << endl;
    for (int i = 0; i < this->numArcs; i++) {
        Indent(os, indent);
        os << setw(4) << i;
        os << setw(7);
        if(this->indexArray[i] == PrefixTbl::endMarker)
          {
            os << "<END>";
          }
        else
          {
            os << this->indexArray[i];
          }
        os << "    ";
        os << this->arcArray[i] << endl;
    }
}

---