Appendix A: Glossary

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).

Appendix B: Bibliography & Recommended Readings

B.1 On C and ANSI-C: [1] B. Kernighan and D. Ritchie, The C Programming Language, Prentice-Hall 1978.
ISBN 0-13-110163-3
[2]
B. Kernighan and D. Ritchie, The C Programming Language, 2nd edition, Prentice-Hall, 1989
ISBN 0-13-110362-8
[3]
Harbison and Steele, C: A Reference Manual, 3rd edition.,Prentice- Hall, 1991.
ISBN 0-13-110933-2
[4]
K. Arnold and J. Peyton, A C User's Guide to ANSI C, Addison-Wesley, 1992
ISBN ?
[5]
Draft Proposed American National Standard for Information Systems Programming Language C, 1988, ANSI Doc No X3J11/88-159. (There is a newer version...)
[6]
J Lapin, Portable C and Unix System Programming, Prentice-Hall, 1987.
ISBN 0-13-686494-5
B.2 On C++:
[7]
B. Stroustrup, The C++ Programming Language, 2nd edition, Addison-Wesley, 1991.
ISBN 0-201-53992-6
[8]
S. Lippman, The C++ Primer, 2nd edition, Addison-Wesley, 1991.
ISBN 0-201-54848-8
[9]
The Evolution of C++: 1985 to 1989, AT&T C++ Selected Readings
[10]
M. Ellis and B. Stroustrup, The Annotated C++ Reference Manual, Addison-Wesley, 1990.
ISBN 0-201-51459-1 (The ARM)
[11]
Hansen, The C++ Answer Book, Addison-Wesley, 1990
[12]
S. Meyers, Effective C++, Addison-Wesley, 1992
ISBN 0-201-56364-9
[13]
J. Coplien, Advanced C++ Programming Styles and Idioms, Addison-Wesley, 1992
ISBN ?
B.3 On Object Oriented Programming:
[14]
A. Snyder, Encapsulation and Inheritance in object-based Programming Languages, OOPSLA Proceedings, 1986
[15]
Liskov, Abstraction and Specification in Program Development, McGraw-Hill, 1987
ISBN ?
[16]
B. Meyer, Object-Oriented Software Construction, Prentice-Hall, 1988
ISBN ?
[17]
G. Booch, Object-Oriented Design with Applications, Benjamin/Cummings, 1991
ISBN 0-8053-0091-0
B.4 Other Style Guides That Influenced This One
[18]
R Pike, Notes on Programming in C Bell Labs technical paper
[19]
E. Adams, et al., Naming conventions for Software Packages, June 21, 1987, Sun internal
[20]
W. Teitelman and B. Shannon, C Style and Coding Standards at Sun, Sun internal
[21]
G. Skinner, S. Shah, and B. Shannon, C Style and Coding Standards, Sun internal
[22]
D. Hare, Code Style Guide of Link Service Project, March 1990, Sun internal
[23]
A. Reddy, C++ Style Guide, Sun internal
[24]
D. Goldsmith & J. Palevich, Unofficial C++ Style Guide, develop, April 1990
[25]
J. Adcock (jimad@microsoft.com), comp.lang.c++
[26]
T. Rentsch, C++ Programming Standards, Aug 24, 1992, Personal copy

Appendix C: Example Source Code

C.1 Template for C++ Header Files
#ifndef _WF_BOILERPLATE_HH
#define _WF_BOILERPLATE_HH

//
// Copyright 1993 by Wildfire Communications, Inc.
// remainder of copyright notice
//
// Comment describing module
//

#ident "$Id: Wildfire-C++Style-endmatter.html,v 1.1 2011/01/18 13:28:41 lott 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
C.2 Template for Shared C and C++ Header Files
#ifndef _MYPROJECT_HEADERFILE_H
#define _MYPROJECT_HEADERFILE_H

/*
 * Copyright 1992 by Wildfire Communications, Inc.
 */

#ident "$Id: Wildfire-C++Style-endmatter.html,v 1.1 2011/01/18 13:28:41 lott 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

C.3 Template for C++ Implementation files
// Copyright 1993 by Wildfire Communications, Inc.

// remainder of copyright notice

// Comment describing module
//

#ident "$Id: Wildfire-C++Style-endmatter.html,v 1.1 2011/01/18 13:28:41 lott 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
C.4 hashtable.hh --- A C++ Header File
#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: Wildfire-C++Style-endmatter.html,v 1.1 2011/01/18 13:28:41 lott 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
C.5 hashtable.cc --- A C++ Header File
// 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: Wildfire-C++Style-endmatter.html,v 1.1 2011/01/18 13:28:41 lott 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);
}

Archived by Chris Lott.
Collection index