00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063 #include <string>
00064 #include <stdlib.h>
00065 #include <stdio.h>
00066 #include "Dictionary.hh"
00067
00068
00069
00070
00071
00072
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
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
00106 endScope = new (DictEntry *[ns]);
00107 if (endScope==NULL)
00108 panic("can't alloc endScope");
00109
00110
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
00146
00147
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
00159
00160
00161 hash1 ^= randomNumbers[*string++];
00162 if (*string != 0)
00163 hash2 ^= randomNumbers[*string++];
00164 }
00165 return (hash1 << 8) | hash2;
00166 }
00167
00168
00169
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
00180
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;
00199
00200 entry->setKey(key);
00201 entry->setHashCode( h );
00202 entry->setNext(bucket[h]);
00203 bucket[h] = entry;
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
00216 currentScope++;
00217 if (currentScope>=nscopes)
00218 panic("saveScope: overflow");
00219 }
00220
00221 void Dictionary::restoreScope()
00222 {
00223
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
00242
00243
00244
00245 DictEntry *Dictionary::removeScope(int sc)
00246 {
00247 if (sc == -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
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;
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;
00286 }
00287
00288
00289
00290
00291
00292
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;
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)
00327 sc = currentScope;
00328 for (s=scope[sc]; s!=NULL; s=s->getNextInScope())
00329 {
00330 dumpSymbol(f, s);
00331 }
00332 }
00333
00334
00335
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