PrefixTbl.H

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 Tue Aug  3 13:59:25 EDT 2004 by ken@xorian.net
//      modified on Wed May 13 16:08:16 PDT 1998 by heydon
//      modified on Wed Mar 18 12:04:09 PST 1998 by yuanyu

#ifndef _PREFIX_TBL_H
#define _PREFIX_TBL_H

/* A "PrefixTbl" is a data structure for representing a set
   of pathnames. If the pathnames in the set share common
   prefixes, the "PrefixTbl" representation is quite compact.
   Each pathname in the table is identified by a non-negative
   integer. */

#include <Basics.H>
#include <Generics.H>
#include <SRPC.H>
#include <VestaLog.H>
#include <Recovery.H>
#include <FS.H>
#include "FV2.H"

class PrefixTbl {
public:

  // This type is thrown as an exception when no more entries can be
  // added to a PrefixTbl.
  struct Overflow
  {
    Basics::uint16 numArcs;
    Overflow(Basics::uint16 arcs) : numArcs(arcs) { }
  };

  // Index value used to mark the end of a chain in a PrefixTbl.
  static const Basics::uint16 endMarker = ~0;

  PrefixTbl() throw ()
  /* Construct a new, empty "PrefixTbl". */
    : numArcs(0), maxArcs(0), indexArray(NULL), arcArray(NULL) { /*SKIP*/};
  
  PrefixTbl(int szHint) throw ();
  /* Construct a new, empty "PrefixTbl" with expected size "szHint". */

  PrefixTbl(std::istream &ifs) throw (FS::EndOfFile, FS::Failure)
  { this->Read(ifs); }

  int PrefixIndex(int idx) const throw () { return this->indexArray[idx]; }
  /* Return the index of the prefix of the name with index "idx". */

  Text Arc(int idx) const throw () { return this->arcArray[idx]; }
  /* Return the last arc of the pathname with index "idx". */

  int NumArcs() const throw () { return this->numArcs; };
  /* Return the number of pathnames in the table. */
  
  int Put(const char* path, TextIntTbl /*INOUT*/ &tbl) throw (Overflow);
  int Put(const FV2::T& path, TextIntTbl /*INOUT*/ &tbl) throw (Overflow);
  /* Insert the pathname "path" into the table, and return its
     integer identifier. The "tbl" argument is a table maintained
     by the client. Exactly one "tbl" should be used with each
     "PrefixTbl". On the first call to "Put", "tbl" should be
     empty, and the client should not perform any other modifications
     on "tbl" asside from passing it to "Put". Once the client is
     done calling "Put", "tbl" can be disposed of. */
  
  FV2::T *Get(int idx) const throw ();
  /* Return the pathname with integer identifier "idx". */

  bool GetString(int idx, char *buff, int buff_len) const throw ();
  /* If the pathname with integer identifier "idx" does not exceed
     "buff_len" (including the null termination character at the end
     of the pathname), write that pathname into "buff" and return
     true. Otherwise, return false. In the latter case, some
     characters in "buff" may have been modified. */

  int MemorySize() const throw ();
  /* Return an upper bound on the size (in bytes) required to store
     this table in memory. */

  static int Skip(std::istream &ifs) throw (FS::EndOfFile, FS::Failure);
  /* Assumes "ifs" is positioned at a pickled "PrefixTbl". Skips
     over the table, and returns the number of bytes skipped. */
  
  // write/read
  void Write(std::ostream &ofs) const throw (FS::Failure);
  void Read(std::istream &ifs) throw (FS::EndOfFile, FS::Failure);

  // logging/recovery
  void Log(VestaLog &log) const throw (VestaLog::Error);
  void Recover(RecoveryReader &rd)
    throw (VestaLog::Error, VestaLog::Eof);

  // send/recv
  void Send(SRPC &srpc) const throw (SRPC::failure);
  void Recv(SRPC &srpc) throw (SRPC::failure);

  // print
  void Print(std::ostream &os, int indent = 0) const throw ();
  /* Print a representation of this table to "os", indented by "indent"
     characters. */

private:
  /* Invariants:
     I0. 0 <= numArcs <= maxArcs
     I2. maxArcs > 0 => length(indexArray) == length(arcArray) == maxArcs
     I3. maxArcs == 0 <==> ((indexArray == NULL) /\ (arcArray == NULL))
  */
  Basics::uint16 numArcs;       // number of used table entries
  Basics::uint16 maxArcs;       // maximum number of table entries
  Basics::uint16 *indexArray;   // array for prefix indices
  Text *arcArray;               // array for arcs
  
  int AddArc(const Text& arc) throw (Overflow);
  /* Add the arc "arc" to the next position in "arcArray" (growing
     both "indexArray" and "arcArray" if necessary), and return its
     index in "arcArray". */
};

#endif // _PREFIX_TBL_H

---