Function Declaration: An assertion to the compiler that this function is implemented elsewhere with the following return type, name, and parameter attributes. This is also known as a forward declaration.
Function Definition: The function's actual implementation.
Abstract Class: A class that may have some implementation, but not enough to instantiate an object. That is, it has at least one pure virtual member function and at least one implemented member function or some data. Also, a superclass of an interface class.
Interface Class: A class that has no implementation or data, only pure virtual member functions, including the destructor. Sometimes called a "pure virtual class".
Pure Virtual Member Function: A virtual function that must be defined by non-abstract derived classes, that is, a member function with a declaration ending with = 0.
Curly Braces: '{' (open) and '}' (close).
#ifndef _WF_BOILERPLATE_HH
#define _WF_BOILERPLATE_HH
//
// Copyright 1993 by Wildfire Communications, Inc.
// remainder of copyright notice
//
// Comment describing module
//
#ident "$Id: boilerplate.hh,v 1.1.1.2 1993/10/06 19:05:00 arnold Exp $"
// Include all header files needed to make this a stand-alone module
#include <C++ Header Files>
extern "C" {
#include <C Header Files>
}
#include "private.hh" // any private headers needed
// consts
// forward decl's
// typedefs as needed
// struct and union decl's
// class decl's
// Global Variables
// Non-Class function decl's
#endif
#ifndef _MYPROJECT_HEADERFILE_H
#define _MYPROJECT_HEADERFILE_H
/*
* Copyright 1992 by Wildfire Communications, Inc.
*/
#ident "$Id: boilerplate.h,v 1.1.1.2 1993/10/06 19:04:59 arnold Exp $"
#ifdef __cplusplus /* Note: two leading underscores */
extern "C" {
#endif
/* consts and #define consts */
/* forward decl's */
/* typedefs as needed */
/* struct and union decl's */
/* Global Variables */
/* function decl's */
#ifdef __cplusplus
}
#endif
#endif
// Copyright 1993 by Wildfire Communications, Inc.
// remainder of copyright notice
// Comment describing module
//
#ident "$Id: boilerplate.cc,v 1.1.1.2 1993/10/06 19:04:58 arnold Exp $"
// Include all header files needed to make this a
// stand-alone module
#include <C++ Header Files>
extern "C" {
#include <C Header Files>
}
#include "private.hh" // any private headers needed
// consts
// forward decl's
// typedefs as needed
// struct and union decl's
// class decl's
// Global Variable decl's
// Non-Class function decl's
// Global Variable Definitions
// Static Variable Definitions
// Function/Method Definitions
#ifndef _WF_HASHTABLE_HH
#define _WF_HASHTABLE_HH
// Copyright 1993 by Wildfire Communications, Inc.
// remainder of copyright notice
// HashTable module - a general purpose hashtable that holds
// <char *, void *> pairs. Originally
// used as the basis for a symbol table.
//
// A HashTable allows you to:
// insert Add items to the HashTable
// remove Remove items from the HashTable
// lookup Find out if an item is in the HashTable
// value If the item is in the hashtable, get the value
// stream<< Print out the contents of the hashtable to cerr
//
// $Id: hashtable.hh,v 1.1.1.2 1993/10/06 19:05:03 arnold Exp $
#include <iostream.h>
#include "wfbase.hh"
class HashTable; // Defined below ...
class HashBucket
{
private:
HashBucket();
~HashBucket();
friend ostream &operator<<(ostream &stream,
HashBucket &bkt);
friend ostream &operator<<(ostream &stream,
HashTable &htable);
char *Token; // key
const void *Value; // info
HashBucket *Next; // pointer to next node
HashTable *Table; // backpointer to Htabl
friend class HashTable; // Needs access...
};
class HashTable
{
public:
enum {
default_size = 1027 // default size for tables
};
HashTable(
unsigned short sz = HashTable::default_size);
~HashTable();
void insert(const char *token, const void *value);
void remove(const char *token); // remove token
int lookup(const char *token); // 0 if not in table
void *value(const char *token); // return value for token
WfBoolean is_strings();
void set_is_strings(WfBoolean new_val);
WfBoolean show_debug();
void set_show_debug(WfBoolean new_state);
friend ostream &operator<<(
ostream &stream,
HashTable &htable);
private:
unsigned short Size; // number of slots
HashBucket **Array; // array of slots
WfBoolean IsStrings; // storing strings?
WfBoolean ShowDebug; // Trace operation?
unsigned long hash(const char *token);
HashBucket *lookup_bucket(const char *token);
};
#endif
// Copyright 1993 by Wildfire Communications, Inc.
// remainder of copyright notice
// HashTable module
//
// This implementation uses the private function hash() to generate
// "unique" values for tokens, and "seperate chaining" to resolve
// hash table collisions.
//
// See figure 7.34 and 7.35 in Aho, Sethi, and Ullman.
//
#ident "$Id: hashtable.cc,v 1.2.1.2 1993/10/06 19:05:02 arnold Exp $"
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <assert.h>
#include "hashtable.hh"
////////////////////////// Hash Buckets /////////////////////////////
// Hash Bucket Constructor
HashBucket::HashBucket() :
Token(NULL),
Value(NULL),
Next(NULL),
Table(NULL)
{
}
// Hash Bucket Destructor
HashBucket::~HashBucket()
{
delete [] Token; // delete is safe for NULL
}
// Hash Bucket "print" operator
ostream &
operator<<(ostream &stream, HashBucket &bucket)
{
stream << "[" << bucket.Token << ",";
if (bucket.Table == NULL || !bucket.Table->is_strings())
stream << (void *) bucket.Value;
else
stream << (char *) bucket.Value;
stream << "]";
return stream;
}
//////////////////////////// HashTable ///////////////////////////////
// HashTable Constructor
HashTable::HashTable(
unsigned short sz) // The size of the table (primes are best)
:
Size(sz)
{
unsigned short i;
assert(sz != 0);
set_is_strings(WfFalse);
set_show_debug(WfFalse);
Array = new HashBucket *[Size + 1];
assert(Array != NULL);
for (i = 0; i < Size; i++)
Array[i] = NULL; // no buckets yet
}
// HashTable Destructor
//
// Unallocate all storage used by the hashtable (table and chains)
HashTable::~HashTable()
{
unsigned short i;
if (show_debug())
cerr << "# HashTable::~HashTable(Size = " << Size << ")\n";
for (i = 0; i < Size; i++) {
HashBucket *bucket = Array[i];
while (bucket) { //
free the buckets
HashBucket *freeme;
freeme = bucket;
bucket = bucket->Next; // and the contents
delete freeme;
}
}
delete [] Array; // then the table
}
// Insert a value into the hashtable
void
HashTable::insert(
const char *token,
const void *value)
{
assert(token != NULL);
long chain = hash(token);
HashBucket *bucket = lookup_bucket(token);
if (show_debug()) {
cerr << "# HashTable::insert(\"" << token << "\", ";
if (is_strings())
cerr << "\"" << (char *) value << "\"";
else
cerr << "(void *)" << (void *) value;
cerr << ") into chain [" << chain << "]";
}
if (bucket != NULL) { // update existing
if (show_debug())
cerr << " <updating>";
bucket->Value = value;
} else {
if (show_debug())
cerr << " <adding>";
HashBucket *new_bucket = new HashBucket();
assert(new_bucket != NULL);
new_bucket->Token = new char[strlen(token) + 1];
assert(new_bucket->Token != NULL);
strcpy(new_bucket->Token, token);
new_bucket->Value = value;
new_bucket->Table = this;
// insert at beginning of bucket chain
new_bucket->Next = Array[chain];
Array[chain] = new_bucket;
}
if (show_debug())
cerr << "\n";
}
// Lookup a token to see if it is has a value stored in the table.
// return WfTrue if token is in the table, or WfFalse if it
// isn't.
WfBool
HashTable::lookup(const char *token)
{
assert(token != NULL);
if (show_debug())
cerr << "# HashTable::lookup(" << token << ")\n";
return (lookup_bucket(token) != NULL);
}
// Get the value stored in the hashtable under "token". return
// value associated with the token if token is in the table, NULL
// if it isn't
void *
HashTable::value(const char *token)
{
HashBucket *bucket;
void *retval;
assert(token != NULL);
if (show_debug())
cerr << "# HashTable::value(" << token << ") => ";
bucket = lookup_bucket(token);
if (bucket != NULL)
retval = (void *) bucket->Value;
else
retval = NULL;
if (show_debug()) {
if (retval == NULL)
cerr << "<NULL>";
else if (IsStrings)
cerr << "\"" << (char *) retval << "\"";
else
cerr << "(void *)" << (void *) retval;
cerr << "\n";
}
return retval;
}
// Remove token from the hashtable.
void
HashTable::remove(const char *token)
{
HashBucket *bucket;
unsigned long chain;
assert(token != NULL);
chain = hash(token);
bucket = lookup_bucket(token);
assert(bucket != NULL); // if not in table
if (show_debug())
cerr << "# HashTable::remove(" << token << ")\n";
if (Array[chain] == bucket) { // at head...
Array[chain] = bucket->Next;
bucket->Next = NULL;
delete bucket;
} else { // or elsewhere...
// At this point, back pointers would really be useful
// in removing an item. ASSUMPTION: remove will be
// an infrequent operation, so the space/time tradeoff
// of scanning the whole chain -vs- another pointer field
// falls to the side of more time and less space.
//
// We know that the bucket MUST be on this chain.
// because hash(token) pointed here AND
// lookup_bucket(token) suceeded
HashBucket *tmp = Array[chain];
// +-----+ +------+ +------+ +------+
// | |-->| |-->| |-->| |-->@
// +-----+ +------+ +------+ +------+
// tmp bucket
while (tmp->Next != NULL && tmp->Next != bucket)
tmp = tmp->Next; // step thru till found
assert(tmp != NULL);
// +-----+ +------+ +------+ +------+
// | |-->| |-->| |-->| |-->@
// +-----+ +------+ +------+ +------+
// tmp bucket
tmp->Next = tmp->Next->Next;
// /----------\
// +-----+ +------+ | +------+ | +------+
// | |-->| |-/ | | \>| |-->@
// +-----+ +------+ +------+ +------+
// tmp bucket
delete bucket;
}
}
WfBool
HashTable::is_strings()
{
return IsStrings;
}
void
HashTable::set_is_strings(WfBool value_is_strings)
{
IsStrings = value_is_strings;
}
WfBool
HashTable::show_debug()
{
return ShowDebug;
}
void
HashTable::set_show_debug(WfBool new_show_debug)
{
ShowDebug = new_show_debug;
}
// Print out a hashtable
ostream &
operator<<(ostream &stream, HashTable &htable)
{
int how_many;
unsigned short i;
stream << "HashTable Size = " << htable.Size;
if (htable.IsStrings)
stream << ", value interpreted as a (char *)";
stream << "\n";
how_many = 0;
for (i = 0; i < htable.Size; i++) { // for each chain
HashBucket *bucket = htable.Array[i];
if (bucket == NULL)
continue;
else { // Print the bucket
stream << "[";
if (i < 10) // attempt
stream << " "; // at formatting
else if (i < 100) // output into fixed
stream << " "; // width columns
stream << i << "]";
}
while (bucket != NULL) { // ... and each bucket
how_many = 0;
stream << "=>" << *bucket;
bucket = bucket->Next;
}
stream << "\n";
}
if (!how_many)
stream << "HashTable is empty";
else
stream << "HashTable contains " << how_many << " items.";
stream << "\n";
return stream;
}
// Private functions
// Internal routine used by lookup and insertion functions.
// Returns pointer to the location of the desired bucket, or NULL
// if the Token was not found
HashBucket *
HashTable::lookup_bucket(const char *token)
{
assert(token != NULL);
HashBucket *bp;
for (bp = Array[hash(token)]; bp != NULL; bp = bp->Next) {
if (strcmp(bp->Token, token) == 0)
return bp; // Found a match!
}
return NULL;
}
// Produce a hash value for the token string. This function avoids
// primary clustering, the exclusive use of even/odd locations,
// and other phenomenom which makes the use of certain locations
// more likely than others.
// The function is fast and deterministic.
// This implementation is from p436 of "Compilers" by Aho, et al
unsigned long
HashTable::hash(const char *token)
{
const char *p; // Steps thru the token
unsigned long hval; // hash value
unsigned long g; // intermediate hash value
assert(token != NULL);
hval = 0;
for (p = token; *p != '\0'; p++) {
hval = (hval << 4) + (*p);
if ((g = hval & 0xf0000000L) != 0) {
hval = hval ^ (g >> 24);
hval = hval ^ g;
}
}
return (hval % Size);
}