Dictionary.cc

Go to the documentation of this file.

/*
 * PUBLIC DOMAIN PCCTS-BASED C++ GRAMMAR (cplusplus.g, stat.g, expr.g)
 *
 * Authors: Sumana Srinivasan, NeXT Inc.;            sumana_srinivasan@next.com
 *          Terence Parr, Parr Research Corporation; parrt@parr-research.com
 *          Russell Quong, Purdue University;        quong@ecn.purdue.edu
 *
 * VERSION 1.1
 *
 * SOFTWARE RIGHTS
 *
 * This file is a part of the ANTLR-based C++ grammar and is free
 * software.  We do not reserve any LEGAL rights to its use or
 * distribution, but you may NOT claim ownership or authorship of this
 * grammar or support code.  An individual or company may otherwise do
 * whatever they wish with the grammar distributed herewith including the
 * incorporation of the grammar or the output generated by ANTLR into
 * commerical software.  You may redistribute in source or binary form
 * without payment of royalties to us as long as this header remains
 * in all source distributions.
 *
 * We encourage users to develop parsers/tools using this grammar.
 * In return, we ask that credit is given to us for developing this
 * grammar.  By "credit", we mean that if you incorporate our grammar or
 * the generated code into one of your programs (commercial product,
 * research project, or otherwise) that you acknowledge this fact in the
 * documentation, research report, etc....  In addition, you should say nice
 * things about us at every opportunity.
 *
 * As long as these guidelines are kept, we expect to continue enhancing
 * this grammar.  Feel free to send us enhancements, fixes, bug reports,
 * suggestions, or general words of encouragement at parrt@parr-research.com.
 * 
 * NeXT Computer Inc.
 * 900 Chesapeake Dr.
 * Redwood City, CA 94555
 * 12/02/1994
 * 
 * Restructured for public consumption by Terence Parr late February, 1995.
 *
 * Requires PCCTS 1.32b4 or higher to get past ANTLR. 
 * 
 * DISCLAIMER: we make no guarantees that this grammar works, makes sense,
 *             or can be used to do anything useful.
 */
/* 1999-2004 Version 3.0 July 2004
 * Modified by David Wigg at London South Bank University for CPP_parser.g
 *
 * See MyReadMe.txt for further information
 *
 * This file is best viewed in courier font with tabs set to 4 spaces
 *
 * Symbols are stored in lists in buckets selected by hashing the symbol name
 *
 * Symbols are also chained in lists from an array of scopes starting with,
 *      [0] = template scope    Note: these symbols are never deleted
 *      [1] = external scope    Note: these symbols are never deleted. "std" is allocated this scope in CPPParser::init()
 *      [1+]= class, function scopes    Note: these symbol references are deleted when they go out of scope.
 * 
 * The latest entry for each scope is recorded in the corresponding endScope array
 */

#include <string>
#include <stdlib.h>
#include <stdio.h>
#include "Dictionary.hh"

/* Hashing function described in                   */
/* "Fast Hashing of Variable-Length Text Strings," */
/* by Peter K. Pearson, CACM, June 1990. */
/* Table from p. 678.*/
/* Pseudorandom Permutation of the Integers 0 through 255: */
unsigned char Dictionary::randomNumbers[] =  
{       
    1, 14,110, 25, 97,174,132,119,138,170,125,118, 27,233,140, 51,
    87,197,177,107,234,169, 56, 68, 30,  7,173, 73,188, 40, 36, 65,
    49,213,104,190, 57,211,148,223, 48,115, 15,  2, 67,186,210, 28,
    12,181,103, 70, 22, 58, 75, 78,183,167,238,157,124,147,172,144,
    176,161,141, 86, 60, 66,128, 83,156,241, 79, 46,168,198, 41,254,
    178, 85,253,237,250,154,133, 88, 35,206, 95,116,252,192, 54,221,
    102,218,255,240, 82,106,158,201, 61,  3, 89,  9, 42,155,159, 93,
    166, 80, 50, 34,175,195,100, 99, 26,150, 16,145,  4, 33,  8,189,
    121, 64, 77, 72,208,245,130,122,143, 55,105,134, 29,164,185,194,
    193,239,101,242,  5,171,126, 11, 74, 59,137,228,108,191,232,139,
    6, 24, 81, 20,127, 17, 91, 92,251,151,225,207, 21, 98,113,112,
    84,226, 18,214,199,187, 13, 32, 94,220,224,212,247,204,196, 43,
    249,236, 45,244,111,182,153,136,129, 90,217,202, 19,165,231, 71,
    230,142, 96,227, 62,179,246,114,162, 53,160,215,205,180, 47,109,
    44, 38, 31,149,135,  0,216, 52, 63, 23, 37, 69, 39,117,146,184,
    163,200,222,235,248,243,219, 10,152,131,123,229,203, 76,120,209
};

Dictionary::Dictionary(int nb, int ns, int nc)
{
    int i;

    // allocate and initialize buckets
    bucket = new (DictEntry *[nb]);
    if (bucket==NULL) 
        panic("can't alloc buckets");
    nbuckets = nb;
    for (i=0; i<nb; i++) 
        bucket[i]=NULL;

    // allocate and end scope for each scope
    endScope = new (DictEntry *[ns]);
    if (endScope==NULL) 
        panic("can't alloc endScope");

    // allocate and initialize scopes and endScopes
    scope = new (DictEntry *[ns]);
    if (scope==NULL) 
        panic("can't alloc scopes");
    nscopes = ns;
    for (i=0; i<ns; i++) 
    {
        scope[i]=NULL;
        endScope[i] = NULL;
    }

    currentScope = 0;

}

Dictionary::~Dictionary()
{
    for (int i = 0; i < nbuckets; ++i)
    {
        DictEntry* next;
        for( DictEntry* q = bucket[i]; q; q = next)
        {
            next = q->getNext();
            delete q;
        }
    }
    delete [] bucket;

    
    delete [] scope;
    delete [] endScope;
    nbuckets = nscopes = 0;
    currentScope = -1;
}

/* Hashing function described in                   */
/* "Fast Hashing of Variable-Length Text Strings," */
/* by Peter K. Pearson, CACM, June 1990.           */
int Dictionary::hash(const std::string& object)
{
    const char* string = object.c_str();
    int hash1  = 0;
    int hash2  = 0;
    int length = 0;

    while(*string != 0)
    {
        length++;
        /* Hash function is XOR of successive characters randomized by
         * the hash table.
         */
        hash1 ^= randomNumbers[*string++];
        if (*string != 0)
            hash2 ^= randomNumbers[*string++];
    }
    return (hash1 << 8) | hash2;
}

/* Return ptr to 1st entry found in table under key
 * (return NULL if none found).
 */
DictEntry *Dictionary::lookup(const std::string& key)
{
    DictEntry *q;

    int h = hash(key) % nbuckets;

    for (q = bucket[h]; q != NULL; q = q->getNext())
    {
        //printf("Dictionary.cpp lookup bucket %d hashcode %d key %s key %s address %d\n",
        //      h,q->getHashCode(),key,q->getKey(),q);
        if (h != q->getHashCode())
            std::cerr << "dictionary.cpp lookup, h not equal to q->getHashCode() for %s" << key << std::endl;

        if ( h==q->getHashCode() && key == q->getKey() && q->this_scope <= getCurrentScopeIndex() )
            return q;
    }
    return NULL;
}

void Dictionary::define(const std::string& key, DictEntry *entry)
{
    defineInScope(key, entry, currentScope);
}

void Dictionary::defineInScope(const std::string& key, DictEntry *entry, int sc)
{
    int h = hash(key) % nbuckets;
    entry->this_scope = sc; // 4/2/97 LL - added to store scope

    entry->setKey(key); /* make a local copy of key */
    entry->setHashCode( h );
    entry->setNext(bucket[h]);  // Set next pointer to current entry in bucket
    bucket[h] = entry;                          // Replace current entry in bucket
    if (endScope[sc]==NULL)
        scope[sc] = endScope[sc] = entry;
    else
    {
        endScope[sc]->setScope(entry);
        endScope[sc] = entry;
    }
}

void Dictionary::saveScope()
{
    // Advance scope number (for included scope)
    currentScope++;
    if (currentScope>=nscopes) 
        panic("saveScope: overflow");
}

void Dictionary::restoreScope()
{
    // Reduce scope number for next highest scope
    if (currentScope==0) 
        panic("restoreScope: underflow");
    currentScope--;
}

int Dictionary::getCurrentScopeIndex()
{
    return currentScope;
}

DictEntry *Dictionary::getCurrentScope()
{
    if (currentScope<0 || currentScope>nscopes)
        panic("getCurrentScope: no scope");
    return scope[currentScope];
}

/*      This unlinks all entries from the Dictionary that are members
 *      of the current scope.  The scope is not restored to a previous
 *      scope however. This requires use of restoreScope().
 */
DictEntry *Dictionary::removeScope(int sc)
{
    if (sc == -1)       // removeScope() without parameter value defaults sc to -1
        sc = currentScope;

    DictEntry* next;
    for (DictEntry* de = scope[sc]; de != NULL; de = next)
    {
        next = de -> getNextInScope();
        delete remove(de); 
    }

    DictEntry* r = scope[sc];
    scope[sc] = endScope[sc] = NULL;
    return r;
}

/*      Remove this dictEntry from its bucket by unlinking it
 *
 *
 */
DictEntry *Dictionary::remove(DictEntry *de)
{
    DictEntry *prev, *curr;
    if (de==NULL) 
        panic("Dictionary.cpp remove: NULL ptr");

    int h = hash(de->getKey()) % nbuckets;      // Find pointer to bucket
    for (prev = NULL, curr = bucket[h]; curr != NULL; prev = curr, curr = curr -> getNext())
    {
        if (de==curr)
        {
            if (prev==NULL) 
                bucket[h] = de->getNext();
            else 
                prev->setNext(de->getNext());
            de->setNext(NULL);
            return de;
        }
    }
    return NULL;        // should never get here...
}

/*      Lookup the object referred to by 'key' and then physically remove
 *      it from the Dictionary.  Return the object referred to by the key.
 *      If more than one definition is found for 'key', then only the
 *      first one is removed.  Return NULL if not found.
 *  Note: DW 12/06/03 Probably not used
 */
DictEntry *Dictionary::remove(const std::string& key)
{
    DictEntry *q, *prev;

    int h = hash(key) % nbuckets;
    for (prev=NULL, q = bucket[h]; q != NULL; prev = q, q = q->getNext())
    {
        if (h==q->getHashCode() && key == q->getKey())
        {
            if (prev==NULL) 
            {
                bucket[h] = q->getNext();
            } 
            else 
            {
                prev->setNext(q->getNext());
            }
            q->setNext(NULL);
            return q;
        }
    }
    return NULL;      // should never get here, but make compiler happy
}

void Dictionary::dumpSymbol(FILE *f, DictEntry *de)
{
    fprintf(f, "%s\n", de->getKey().c_str());
}

void Dictionary::dumpScope(FILE *f, int sc)
{       
    DictEntry *s;
    if (sc == -1)       // dumpScope() without parameter value defaults sc to -1
        sc = currentScope;
    for (s=scope[sc]; s!=NULL; s=s->getNextInScope())
    {
        dumpSymbol(f, s);
    }
}

// Diagnostic function
// Contents of first 10 scopes printed
void Dictionary::dumpScopes()
{       
    DictEntry *dictEntry;
    int i;

    printf("Scopes");
    for (i=0; i<10; i++)
    {
        printf("     %d     ",i);
    }
    printf("\n");
    printf(" first");
    for (i=0; i<10; i++)
    {
        if (scope[i]!=NULL)
        {
            dictEntry = scope[i];
            printf("%10s ",dictEntry->getKey().c_str());
        }
        else
        {
            printf("           ");
        }
    }
    printf("\n");
    printf(" last ");
    for (i=0; i<10; i++)
    {
        if (endScope[i]!=NULL)
        {
            dictEntry = endScope[i];
            printf("%10s ",dictEntry->getKey().c_str());
        }
        else
        {
            printf("           ");
        }
    }
    printf("\n");
}

void Dictionary::panic(char const *err)
{
    fprintf(stdout, "Dictionary panic: %s\n", err);
    exit(-1);
}