Dictionary.cc
Go to the documentation of this file.
00001 /*
00002  * PUBLIC DOMAIN PCCTS-BASED C++ GRAMMAR (cplusplus.g, stat.g, expr.g)
00003  *
00004  * Authors: Sumana Srinivasan, NeXT Inc.;            sumana_srinivasan@next.com
00005  *          Terence Parr, Parr Research Corporation; parrt@parr-research.com
00006  *          Russell Quong, Purdue University;        quong@ecn.purdue.edu
00007  *
00008  * VERSION 1.1
00009  *
00010  * SOFTWARE RIGHTS
00011  *
00012  * This file is a part of the ANTLR-based C++ grammar and is free
00013  * software.  We do not reserve any LEGAL rights to its use or
00014  * distribution, but you may NOT claim ownership or authorship of this
00015  * grammar or support code.  An individual or company may otherwise do
00016  * whatever they wish with the grammar distributed herewith including the
00017  * incorporation of the grammar or the output generated by ANTLR into
00018  * commerical software.  You may redistribute in source or binary form
00019  * without payment of royalties to us as long as this header remains
00020  * in all source distributions.
00021  *
00022  * We encourage users to develop parsers/tools using this grammar.
00023  * In return, we ask that credit is given to us for developing this
00024  * grammar.  By "credit", we mean that if you incorporate our grammar or
00025  * the generated code into one of your programs (commercial product,
00026  * research project, or otherwise) that you acknowledge this fact in the
00027  * documentation, research report, etc....  In addition, you should say nice
00028  * things about us at every opportunity.
00029  *
00030  * As long as these guidelines are kept, we expect to continue enhancing
00031  * this grammar.  Feel free to send us enhancements, fixes, bug reports,
00032  * suggestions, or general words of encouragement at parrt@parr-research.com.
00033  * 
00034  * NeXT Computer Inc.
00035  * 900 Chesapeake Dr.
00036  * Redwood City, CA 94555
00037  * 12/02/1994
00038  * 
00039  * Restructured for public consumption by Terence Parr late February, 1995.
00040  *
00041  * Requires PCCTS 1.32b4 or higher to get past ANTLR. 
00042  * 
00043  * DISCLAIMER: we make no guarantees that this grammar works, makes sense,
00044  *             or can be used to do anything useful.
00045  */
00046 /* 1999-2004 Version 3.0 July 2004
00047  * Modified by David Wigg at London South Bank University for CPP_parser.g
00048  *
00049  * See MyReadMe.txt for further information
00050  *
00051  * This file is best viewed in courier font with tabs set to 4 spaces
00052  *
00053  * Symbols are stored in lists in buckets selected by hashing the symbol name
00054  *
00055  * Symbols are also chained in lists from an array of scopes starting with,
00056  *      [0] = template scope    Note: these symbols are never deleted
00057  *      [1] = external scope    Note: these symbols are never deleted. "std" is allocated this scope in CPPParser::init()
00058  *      [1+]= class, function scopes    Note: these symbol references are deleted when they go out of scope.
00059  * 
00060  * The latest entry for each scope is recorded in the corresponding endScope array
00061  */
00062 
00063 #include <string>
00064 #include <stdlib.h>
00065 #include <stdio.h>
00066 #include "Dictionary.hh"
00067 
00068 /* Hashing function described in                   */
00069 /* "Fast Hashing of Variable-Length Text Strings," */
00070 /* by Peter K. Pearson, CACM, June 1990. */
00071 /* Table from p. 678.*/
00072 /* Pseudorandom Permutation of the Integers 0 through 255: */
00073 unsigned char Dictionary::randomNumbers[] =  
00074 {       
00075     1, 14,110, 25, 97,174,132,119,138,170,125,118, 27,233,140, 51,
00076     87,197,177,107,234,169, 56, 68, 30,  7,173, 73,188, 40, 36, 65,
00077     49,213,104,190, 57,211,148,223, 48,115, 15,  2, 67,186,210, 28,
00078     12,181,103, 70, 22, 58, 75, 78,183,167,238,157,124,147,172,144,
00079     176,161,141, 86, 60, 66,128, 83,156,241, 79, 46,168,198, 41,254,
00080     178, 85,253,237,250,154,133, 88, 35,206, 95,116,252,192, 54,221,
00081     102,218,255,240, 82,106,158,201, 61,  3, 89,  9, 42,155,159, 93,
00082     166, 80, 50, 34,175,195,100, 99, 26,150, 16,145,  4, 33,  8,189,
00083     121, 64, 77, 72,208,245,130,122,143, 55,105,134, 29,164,185,194,
00084     193,239,101,242,  5,171,126, 11, 74, 59,137,228,108,191,232,139,
00085     6, 24, 81, 20,127, 17, 91, 92,251,151,225,207, 21, 98,113,112,
00086     84,226, 18,214,199,187, 13, 32, 94,220,224,212,247,204,196, 43,
00087     249,236, 45,244,111,182,153,136,129, 90,217,202, 19,165,231, 71,
00088     230,142, 96,227, 62,179,246,114,162, 53,160,215,205,180, 47,109,
00089     44, 38, 31,149,135,  0,216, 52, 63, 23, 37, 69, 39,117,146,184,
00090     163,200,222,235,248,243,219, 10,152,131,123,229,203, 76,120,209
00091 };
00092 
00093 Dictionary::Dictionary(int nb, int ns, int nc)
00094 {
00095     int i;
00096 
00097     // allocate and initialize buckets
00098     bucket = new (DictEntry *[nb]);
00099     if (bucket==NULL) 
00100         panic("can't alloc buckets");
00101     nbuckets = nb;
00102     for (i=0; i<nb; i++) 
00103         bucket[i]=NULL;
00104 
00105     // allocate and end scope for each scope
00106     endScope = new (DictEntry *[ns]);
00107     if (endScope==NULL) 
00108         panic("can't alloc endScope");
00109 
00110     // allocate and initialize scopes and endScopes
00111     scope = new (DictEntry *[ns]);
00112     if (scope==NULL) 
00113         panic("can't alloc scopes");
00114     nscopes = ns;
00115     for (i=0; i<ns; i++) 
00116     {
00117         scope[i]=NULL;
00118         endScope[i] = NULL;
00119     }
00120 
00121     currentScope = 0;
00122 
00123 }
00124 
00125 Dictionary::~Dictionary()
00126 {
00127     for (int i = 0; i < nbuckets; ++i)
00128     {
00129         DictEntry* next;
00130         for( DictEntry* q = bucket[i]; q; q = next)
00131         {
00132             next = q->getNext();
00133             delete q;
00134         }
00135     }
00136     delete [] bucket;
00137 
00138     
00139     delete [] scope;
00140     delete [] endScope;
00141     nbuckets = nscopes = 0;
00142     currentScope = -1;
00143 }
00144 
00145 /* Hashing function described in                   */
00146 /* "Fast Hashing of Variable-Length Text Strings," */
00147 /* by Peter K. Pearson, CACM, June 1990.           */
00148 int Dictionary::hash(const std::string& object)
00149 {
00150     const char* string = object.c_str();
00151     int hash1  = 0;
00152     int hash2  = 0;
00153     int length = 0;
00154 
00155     while(*string != 0)
00156     {
00157         length++;
00158         /* Hash function is XOR of successive characters randomized by
00159          * the hash table.
00160          */
00161         hash1 ^= randomNumbers[*string++];
00162         if (*string != 0)
00163             hash2 ^= randomNumbers[*string++];
00164     }
00165     return (hash1 << 8) | hash2;
00166 }
00167 
00168 /* Return ptr to 1st entry found in table under key
00169  * (return NULL if none found).
00170  */
00171 DictEntry *Dictionary::lookup(const std::string& key)
00172 {
00173     DictEntry *q;
00174 
00175     int h = hash(key) % nbuckets;
00176 
00177     for (q = bucket[h]; q != NULL; q = q->getNext())
00178     {
00179         //printf("Dictionary.cpp lookup bucket %d hashcode %d key %s key %s address %d\n",
00180         //      h,q->getHashCode(),key,q->getKey(),q);
00181         if (h != q->getHashCode())
00182             std::cerr << "dictionary.cpp lookup, h not equal to q->getHashCode() for %s" << key << std::endl;
00183 
00184         if ( h==q->getHashCode() && key == q->getKey() && q->this_scope <= getCurrentScopeIndex() )
00185             return q;
00186     }
00187     return NULL;
00188 }
00189 
00190 void Dictionary::define(const std::string& key, DictEntry *entry)
00191 {
00192     defineInScope(key, entry, currentScope);
00193 }
00194 
00195 void Dictionary::defineInScope(const std::string& key, DictEntry *entry, int sc)
00196 {
00197     int h = hash(key) % nbuckets;
00198     entry->this_scope = sc; // 4/2/97 LL - added to store scope
00199 
00200     entry->setKey(key); /* make a local copy of key */
00201     entry->setHashCode( h );
00202     entry->setNext(bucket[h]);  // Set next pointer to current entry in bucket
00203     bucket[h] = entry;                          // Replace current entry in bucket
00204     if (endScope[sc]==NULL)
00205         scope[sc] = endScope[sc] = entry;
00206     else
00207     {
00208         endScope[sc]->setScope(entry);
00209         endScope[sc] = entry;
00210     }
00211 }
00212 
00213 void Dictionary::saveScope()
00214 {
00215     // Advance scope number (for included scope)
00216     currentScope++;
00217     if (currentScope>=nscopes) 
00218         panic("saveScope: overflow");
00219 }
00220 
00221 void Dictionary::restoreScope()
00222 {
00223     // Reduce scope number for next highest scope
00224     if (currentScope==0) 
00225         panic("restoreScope: underflow");
00226     currentScope--;
00227 }
00228 
00229 int Dictionary::getCurrentScopeIndex()
00230 {
00231     return currentScope;
00232 }
00233 
00234 DictEntry *Dictionary::getCurrentScope()
00235 {
00236     if (currentScope<0 || currentScope>nscopes)
00237         panic("getCurrentScope: no scope");
00238     return scope[currentScope];
00239 }
00240 
00241 /*      This unlinks all entries from the Dictionary that are members
00242  *      of the current scope.  The scope is not restored to a previous
00243  *      scope however. This requires use of restoreScope().
00244  */
00245 DictEntry *Dictionary::removeScope(int sc)
00246 {
00247     if (sc == -1)       // removeScope() without parameter value defaults sc to -1
00248         sc = currentScope;
00249 
00250     DictEntry* next;
00251     for (DictEntry* de = scope[sc]; de != NULL; de = next)
00252     {
00253         next = de -> getNextInScope();
00254         delete remove(de); 
00255     }
00256 
00257     DictEntry* r = scope[sc];
00258     scope[sc] = endScope[sc] = NULL;
00259     return r;
00260 }
00261 
00262 /*      Remove this dictEntry from its bucket by unlinking it
00263  *
00264  *
00265  */
00266 DictEntry *Dictionary::remove(DictEntry *de)
00267 {
00268     DictEntry *prev, *curr;
00269     if (de==NULL) 
00270         panic("Dictionary.cpp remove: NULL ptr");
00271 
00272     int h = hash(de->getKey()) % nbuckets;      // Find pointer to bucket
00273     for (prev = NULL, curr = bucket[h]; curr != NULL; prev = curr, curr = curr -> getNext())
00274     {
00275         if (de==curr)
00276         {
00277             if (prev==NULL) 
00278                 bucket[h] = de->getNext();
00279             else 
00280                 prev->setNext(de->getNext());
00281             de->setNext(NULL);
00282             return de;
00283         }
00284     }
00285     return NULL;        // should never get here...
00286 }
00287 
00288 /*      Lookup the object referred to by 'key' and then physically remove
00289  *      it from the Dictionary.  Return the object referred to by the key.
00290  *      If more than one definition is found for 'key', then only the
00291  *      first one is removed.  Return NULL if not found.
00292  *  Note: DW 12/06/03 Probably not used
00293  */
00294 DictEntry *Dictionary::remove(const std::string& key)
00295 {
00296     DictEntry *q, *prev;
00297 
00298     int h = hash(key) % nbuckets;
00299     for (prev=NULL, q = bucket[h]; q != NULL; prev = q, q = q->getNext())
00300     {
00301         if (h==q->getHashCode() && key == q->getKey())
00302         {
00303             if (prev==NULL) 
00304             {
00305                 bucket[h] = q->getNext();
00306             } 
00307             else 
00308             {
00309                 prev->setNext(q->getNext());
00310             }
00311             q->setNext(NULL);
00312             return q;
00313         }
00314     }
00315     return NULL;      // should never get here, but make compiler happy
00316 }
00317 
00318 void Dictionary::dumpSymbol(FILE *f, DictEntry *de)
00319 {
00320     fprintf(f, "%s\n", de->getKey().c_str());
00321 }
00322 
00323 void Dictionary::dumpScope(FILE *f, int sc)
00324 {       
00325     DictEntry *s;
00326     if (sc == -1)       // dumpScope() without parameter value defaults sc to -1
00327         sc = currentScope;
00328     for (s=scope[sc]; s!=NULL; s=s->getNextInScope())
00329     {
00330         dumpSymbol(f, s);
00331     }
00332 }
00333 
00334 // Diagnostic function
00335 // Contents of first 10 scopes printed
00336 void Dictionary::dumpScopes()
00337 {       
00338     DictEntry *dictEntry;
00339     int i;
00340 
00341     printf("Scopes");
00342     for (i=0; i<10; i++)
00343     {
00344         printf("     %d     ",i);
00345     }
00346     printf("\n");
00347     printf(" first");
00348     for (i=0; i<10; i++)
00349     {
00350         if (scope[i]!=NULL)
00351         {
00352             dictEntry = scope[i];
00353             printf("%10s ",dictEntry->getKey().c_str());
00354         }
00355         else
00356         {
00357             printf("           ");
00358         }
00359     }
00360     printf("\n");
00361     printf(" last ");
00362     for (i=0; i<10; i++)
00363     {
00364         if (endScope[i]!=NULL)
00365         {
00366             dictEntry = endScope[i];
00367             printf("%10s ",dictEntry->getKey().c_str());
00368         }
00369         else
00370         {
00371             printf("           ");
00372         }
00373     }
00374     printf("\n");
00375 }
00376 
00377 void Dictionary::panic(char const *err)
00378 {
00379     fprintf(stdout, "Dictionary panic: %s\n", err);
00380     exit(-1);
00381 }
00382 
00383 


typelib
Author(s): Sylvain Joyeux/sylvain.joyeux@m4x.org
autogenerated on Mon Sep 14 2015 15:08:17