1/****************************************************************************\
2Copyright (c) 2002, NVIDIA Corporation.
3
4NVIDIA Corporation("NVIDIA") supplies this software to you in
5consideration of your agreement to the following terms, and your use,
6installation, modification or redistribution of this NVIDIA software
7constitutes acceptance of these terms.  If you do not agree with these
8terms, please do not use, install, modify or redistribute this NVIDIA
9software.
10
11In consideration of your agreement to abide by the following terms, and
12subject to these terms, NVIDIA grants you a personal, non-exclusive
13license, under NVIDIA's copyrights in this original NVIDIA software (the
14"NVIDIA Software"), to use, reproduce, modify and redistribute the
15NVIDIA Software, with or without modifications, in source and/or binary
16forms; provided that if you redistribute the NVIDIA Software, you must
17retain the copyright notice of NVIDIA, this notice and the following
18text and disclaimers in all such redistributions of the NVIDIA Software.
19Neither the name, trademarks, service marks nor logos of NVIDIA
20Corporation may be used to endorse or promote products derived from the
21NVIDIA Software without specific prior written permission from NVIDIA.
22Except as expressly stated in this notice, no other rights or licenses
23express or implied, are granted by NVIDIA herein, including but not
24limited to any patent rights that may be infringed by your derivative
25works or by other works in which the NVIDIA Software may be
26incorporated. No hardware is licensed hereunder.
27
28THE NVIDIA SOFTWARE IS BEING PROVIDED ON AN "AS IS" BASIS, WITHOUT
29WARRANTIES OR CONDITIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED,
30INCLUDING WITHOUT LIMITATION, WARRANTIES OR CONDITIONS OF TITLE,
31NON-INFRINGEMENT, MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR
32ITS USE AND OPERATION EITHER ALONE OR IN COMBINATION WITH OTHER
33PRODUCTS.
34
35IN NO EVENT SHALL NVIDIA BE LIABLE FOR ANY SPECIAL, INDIRECT,
36INCIDENTAL, EXEMPLARY, CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
37TO, LOST PROFITS; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
38USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) OR ARISING IN ANY WAY
39OUT OF THE USE, REPRODUCTION, MODIFICATION AND/OR DISTRIBUTION OF THE
40NVIDIA SOFTWARE, HOWEVER CAUSED AND WHETHER UNDER THEORY OF CONTRACT,
41TORT (INCLUDING NEGLIGENCE), STRICT LIABILITY OR OTHERWISE, EVEN IF
42NVIDIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43\****************************************************************************/
44
45//
46// atom.c
47//
48
49#include <stdlib.h>
50#include <stdio.h>
51#include <string.h>
52
53#include "compiler/debug.h"
54#include "compiler/preprocessor/slglobals.h"
55
56#undef malloc
57#undef realloc
58#undef free
59
60///////////////////////////////////////////////////////////////////////////////////////////////
61////////////////////////////////////////// String table: //////////////////////////////////////
62///////////////////////////////////////////////////////////////////////////////////////////////
63
64static const struct {
65    int val;
66    const char *str;
67} tokens[] = {
68    { CPP_AND_OP,         "&&" },
69    { CPP_AND_ASSIGN,     "&=" },
70    { CPP_SUB_ASSIGN,     "-=" },
71    { CPP_MOD_ASSIGN,     "%=" },
72    { CPP_ADD_ASSIGN,     "+=" },
73    { CPP_DIV_ASSIGN,     "/=" },
74    { CPP_MUL_ASSIGN,     "*=" },
75    { CPP_RIGHT_BRACKET,  ":>" },
76    { CPP_EQ_OP,          "==" },
77    { CPP_XOR_OP,         "^^" },
78    { CPP_XOR_ASSIGN,     "^=" },
79    { CPP_FLOATCONSTANT,  "<float-const>" },
80    { CPP_GE_OP,          ">=" },
81    { CPP_RIGHT_OP,       ">>" },
82    { CPP_RIGHT_ASSIGN,   ">>=" },
83    { CPP_IDENTIFIER,     "<ident>" },
84    { CPP_INTCONSTANT,    "<int-const>" },
85    { CPP_LE_OP,          "<=" },
86    { CPP_LEFT_OP,        "<<" },
87    { CPP_LEFT_ASSIGN,    "<<=" },
88    { CPP_LEFT_BRACKET,   "<:" },
89    { CPP_LEFT_BRACE,     "<%" },
90    { CPP_DEC_OP,         "--" },
91    { CPP_RIGHT_BRACE,    "%>" },
92    { CPP_NE_OP,          "!=" },
93    { CPP_OR_OP,          "||" },
94    { CPP_OR_ASSIGN,      "|=" },
95    { CPP_INC_OP,         "++" },
96    { CPP_STRCONSTANT,    "<string-const>" },
97    { CPP_TYPEIDENTIFIER, "<type-ident>" },
98};
99
100///////////////////////////////////////////////////////////////////////////////////////////////
101////////////////////////////////////////// String table: //////////////////////////////////////
102///////////////////////////////////////////////////////////////////////////////////////////////
103
104#define INIT_STRING_TABLE_SIZE 16384
105
106typedef struct StringTable_Rec {
107    char *strings;
108    int nextFree;
109    int size;
110} StringTable;
111
112/*
113 * InitStringTable() - Initialize the string table.
114 *
115 */
116
117static int InitStringTable(StringTable *stable)
118{
119    stable->strings = (char *) malloc(INIT_STRING_TABLE_SIZE);
120    if (!stable->strings)
121        return 0;
122    // Zero-th offset means "empty" so don't use it.
123    stable->nextFree = 1;
124    stable->size = INIT_STRING_TABLE_SIZE;
125    return 1;
126} // InitStringTable
127
128/*
129 * FreeStringTable() - Free the string table.
130 *
131 */
132
133static void FreeStringTable(StringTable *stable)
134{
135    if (stable->strings)
136        free(stable->strings);
137    stable->strings = NULL;
138    stable->nextFree = 0;
139    stable->size = 0;
140} // FreeStringTable
141
142/*
143 * HashString() - Hash a string with the base hash function.
144 *
145 */
146
147static int HashString(const char *s)
148{
149    int hval = 0;
150
151    while (*s) {
152        hval = (hval*13507 + *s*197) ^ (hval >> 2);
153        s++;
154    }
155    return hval & 0x7fffffff;
156} // HashString
157
158/*
159 * HashString2() - Hash a string with the incrimenting hash function.
160 *
161 */
162
163static int HashString2(const char *s)
164{
165    int hval = 0;
166
167    while (*s) {
168        hval = (hval*729 + *s*37) ^ (hval >> 1);
169        s++;
170    }
171    return hval;
172} // HashString2
173
174/*
175 * AddString() - Add a string to a string table.  Return it's offset.
176 *
177 */
178
179static int AddString(StringTable *stable, const char *s)
180{
181    int len, loc;
182    char *str;
183
184    len = (int) strlen(s);
185    if (stable->nextFree + len + 1 >= stable->size) {
186        assert(stable->size < 1000000);
187        str = (char *) malloc(stable->size*2);
188        memcpy(str, stable->strings, stable->size);
189        free(stable->strings);
190        stable->strings = str;
191    }
192    loc = stable->nextFree;
193    strcpy(&stable->strings[loc], s);
194    stable->nextFree += len + 1;
195    return loc;
196} // AddString
197
198///////////////////////////////////////////////////////////////////////////////////////////////
199/////////////////////////////////////////// Hash table: ///////////////////////////////////////
200///////////////////////////////////////////////////////////////////////////////////////////////
201
202#define INIT_HASH_TABLE_SIZE 2047
203#define HASH_TABLE_MAX_COLLISIONS 3
204
205typedef struct HashEntry_Rec {
206    int index;      // String table offset of string representation
207    int value;      // Atom (symbol) value
208} HashEntry;
209
210typedef struct HashTable_Rec {
211    HashEntry *entry;
212    int size;
213    int entries;
214    int counts[HASH_TABLE_MAX_COLLISIONS + 1];
215} HashTable;
216
217/*
218 * InitHashTable() - Initialize the hash table.
219 *
220 */
221
222static int InitHashTable(HashTable *htable, int fsize)
223{
224    int ii;
225
226    htable->entry = (HashEntry *) malloc(sizeof(HashEntry)*fsize);
227    if (!htable->entry)
228        return 0;
229    htable->size = fsize;
230    for (ii = 0; ii < fsize; ii++) {
231        htable->entry[ii].index = 0;
232        htable->entry[ii].value = 0;
233    }
234    htable->entries = 0;
235    for (ii = 0; ii <= HASH_TABLE_MAX_COLLISIONS; ii++)
236        htable->counts[ii] = 0;
237    return 1;
238} // InitHashTable
239
240/*
241 * FreeHashTable() - Free the hash table.
242 *
243 */
244
245static void FreeHashTable(HashTable *htable)
246{
247    if (htable->entry)
248        free(htable->entry);
249    htable->entry = NULL;
250    htable->size = 0;
251    htable->entries = 0;
252} // FreeHashTable
253
254/*
255 * Empty() - See if a hash table entry is empty.
256 *
257 */
258
259static int Empty(HashTable *htable, int hashloc)
260{
261    assert(hashloc >= 0 && hashloc < htable->size);
262    if (htable->entry[hashloc].index == 0) {
263        return 1;
264    } else {
265        return 0;
266    }
267} // Empty
268
269/*
270 * Match() - See if a hash table entry is matches a string.
271 *
272 */
273
274static int Match(HashTable *htable, StringTable *stable, const char *s, int hashloc)
275{
276    int strloc;
277
278    strloc = htable->entry[hashloc].index;
279    if (!strcmp(s, &stable->strings[strloc])) {
280        return 1;
281    } else {
282        return 0;
283    }
284} // Match
285
286///////////////////////////////////////////////////////////////////////////////////////////////
287/////////////////////////////////////////// Atom table: ///////////////////////////////////////
288///////////////////////////////////////////////////////////////////////////////////////////////
289
290#define INIT_ATOM_TABLE_SIZE 1024
291
292
293struct AtomTable_Rec {
294    StringTable stable; // String table.
295    HashTable htable;   // Hashes string to atom number and token value.  Multiple strings can
296                        // have the same token value but each unique string is a unique atom.
297    int *amap;          // Maps atom value to offset in string table.  Atoms all map to unique
298                        // strings except for some undefined values in the lower, fixed part
299                        // of the atom table that map to "<undefined>".  The lowest 256 atoms
300                        // correspond to single character ASCII values except for alphanumeric
301                        // characters and '_', which can be other tokens.  Next come the
302                        // language tokens with their atom values equal to the token value.
303                        // Then come predefined atoms, followed by user specified identifiers.
304    int *arev;          // Reversed atom for symbol table use.
305    int nextFree;
306    int size;
307};
308
309static AtomTable latable = { { 0 } };
310AtomTable *atable = &latable;
311
312static int AddAtomFixed(AtomTable *atable, const char *s, int atom);
313
314/*
315 * GrowAtomTable() - Grow the atom table to at least "size" if it's smaller.
316 *
317 */
318
319static int GrowAtomTable(AtomTable *atable, int size)
320{
321    int *newmap, *newrev;
322
323    if (atable->size < size) {
324        if (atable->amap) {
325            newmap = realloc(atable->amap, sizeof(int)*size);
326            newrev = realloc(atable->arev, sizeof(int)*size);
327        } else {
328            newmap = malloc(sizeof(int)*size);
329            newrev = malloc(sizeof(int)*size);
330            atable->size = 0;
331        }
332        if (!newmap || !newrev) {
333            /* failed to grow -- error */
334            if (newmap)
335                atable->amap = newmap;
336            if (newrev)
337                atable->amap = newrev;
338            return -1;
339        }
340        memset(&newmap[atable->size], 0, (size - atable->size) * sizeof(int));
341        memset(&newrev[atable->size], 0, (size - atable->size) * sizeof(int));
342        atable->amap = newmap;
343        atable->arev = newrev;
344        atable->size = size;
345    }
346    return 0;
347} // GrowAtomTable
348
349/*
350 * lReverse() - Reverse the bottom 20 bits of a 32 bit int.
351 *
352 */
353
354static int lReverse(int fval)
355{
356    unsigned int in = fval;
357    int result = 0, cnt = 0;
358
359    while(in) {
360        result <<= 1;
361        result |= in&1;
362        in >>= 1;
363        cnt++;
364    }
365
366    // Don't use all 31 bits.  One million atoms is plenty and sometimes the
367    // upper bits are used for other things.
368
369    if (cnt < 20)
370        result <<= 20 - cnt;
371    return result;
372} // lReverse
373
374/*
375 * AllocateAtom() - Allocate a new atom.  Associated with the "undefined" value of -1.
376 *
377 */
378
379static int AllocateAtom(AtomTable *atable)
380{
381    if (atable->nextFree >= atable->size)
382        GrowAtomTable(atable, atable->nextFree*2);
383    atable->amap[atable->nextFree] = -1;
384    atable->arev[atable->nextFree] = lReverse(atable->nextFree);
385    atable->nextFree++;
386    return atable->nextFree - 1;
387} // AllocateAtom
388
389/*
390 * SetAtomValue() - Allocate a new atom associated with "hashindex".
391 *
392 */
393
394static void SetAtomValue(AtomTable *atable, int atomnumber, int hashindex)
395{
396    atable->amap[atomnumber] = atable->htable.entry[hashindex].index;
397    atable->htable.entry[hashindex].value = atomnumber;
398} // SetAtomValue
399
400/*
401 * FindHashLoc() - Find the hash location for this string.  Return -1 it hash table is full.
402 *
403 */
404
405static int FindHashLoc(AtomTable *atable, const char *s)
406{
407    int hashloc, hashdelta, count;
408    int FoundEmptySlot = 0;
409    int collision[HASH_TABLE_MAX_COLLISIONS + 1];
410
411    hashloc = HashString(s) % atable->htable.size;
412    if (!Empty(&atable->htable, hashloc)) {
413        if (Match(&atable->htable, &atable->stable, s, hashloc))
414            return hashloc;
415        collision[0] = hashloc;
416        hashdelta = HashString2(s);
417        count = 0;
418        while (count < HASH_TABLE_MAX_COLLISIONS) {
419            hashloc = ((hashloc + hashdelta) & 0x7fffffff) % atable->htable.size;
420            if (!Empty(&atable->htable, hashloc)) {
421                if (Match(&atable->htable, &atable->stable, s, hashloc)) {
422                    return hashloc;
423                }
424            } else {
425                FoundEmptySlot = 1;
426                break;
427            }
428            count++;
429            collision[count] = hashloc;
430        }
431
432        if (!FoundEmptySlot) {
433            if (cpp->options.DumpAtomTable) {
434                int ii;
435                char str[200];
436                sprintf(str, "*** Hash failed with more than %d collisions. Must increase hash table size. ***",
437                       HASH_TABLE_MAX_COLLISIONS);
438                CPPShInfoLogMsg(str);
439
440                sprintf(str, "*** New string \"%s\", hash=%04x, delta=%04x", s, collision[0], hashdelta);
441                CPPShInfoLogMsg(str);
442                for (ii = 0; ii <= HASH_TABLE_MAX_COLLISIONS; ii++) {
443                    sprintf(str, "*** Collides on try %d at hash entry %04x with \"%s\"",
444                           ii + 1, collision[ii], GetAtomString(atable, atable->htable.entry[collision[ii]].value));
445                    CPPShInfoLogMsg(str);
446                }
447            }
448            return -1;
449        } else {
450            atable->htable.counts[count]++;
451        }
452    }
453    return hashloc;
454} // FindHashLoc
455
456/*
457 * IncreaseHashTableSize()
458 *
459 */
460
461static int IncreaseHashTableSize(AtomTable *atable)
462{
463    int ii, strloc, oldhashloc, value, size;
464    AtomTable oldtable;
465    char *s;
466
467    // Save the old atom table and create a new one:
468
469    oldtable = *atable;
470    size = oldtable.htable.size*2 + 1;
471    if (!InitAtomTable(atable, size))
472        return 0;
473
474    // Add all the existing values to the new atom table preserving their atom values:
475
476    for (ii = atable->nextFree; ii < oldtable.nextFree; ii++) {
477        strloc = oldtable.amap[ii];
478        s = &oldtable.stable.strings[strloc];
479        oldhashloc = FindHashLoc(&oldtable, s);
480        assert(oldhashloc >= 0);
481        value = oldtable.htable.entry[oldhashloc].value;
482        AddAtomFixed(atable, s, value);
483    }
484    FreeAtomTable(&oldtable);
485    return 1;
486} // IncreaseHashTableSize
487
488/*
489 * LookUpAddStringHash() - Lookup a string in the hash table.  If it's not there, add it and
490 *        initialize the atom value in the hash table to 0.  Return the hash table index.
491 */
492
493static int LookUpAddStringHash(AtomTable *atable, const char *s)
494{
495    int hashloc, strloc;
496
497    while(1) {
498        hashloc = FindHashLoc(atable, s);
499        if (hashloc >= 0)
500            break;
501        IncreaseHashTableSize(atable);
502    }
503
504    if (Empty(&atable->htable, hashloc)) {
505        atable->htable.entries++;
506        strloc = AddString(&atable->stable, s);
507        atable->htable.entry[hashloc].index = strloc;
508        atable->htable.entry[hashloc].value = 0;
509    }
510    return hashloc;
511} // LookUpAddStringHash
512
513/*
514 * LookUpAddString() - Lookup a string in the hash table.  If it's not there, add it and
515 *        initialize the atom value in the hash table to the next atom number.
516 *        Return the atom value of string.
517 */
518
519int LookUpAddString(AtomTable *atable, const char *s)
520{
521    int hashindex, atom;
522
523    hashindex = LookUpAddStringHash(atable, s);
524    atom = atable->htable.entry[hashindex].value;
525    if (atom == 0) {
526        atom = AllocateAtom(atable);
527        SetAtomValue(atable, atom, hashindex);
528    }
529    return atom;
530} // LookUpAddString
531
532/*
533 * GetAtomString()
534 *
535 */
536
537const  char *GetAtomString(AtomTable *atable, int atom)
538{
539    int soffset;
540
541    if (atom > 0 && atom < atable->nextFree) {
542        soffset = atable->amap[atom];
543        if (soffset > 0 && soffset < atable->stable.nextFree) {
544            return &atable->stable.strings[soffset];
545        } else {
546            return "<internal error: bad soffset>";
547        }
548    } else {
549        if (atom == 0) {
550            return "<null atom>";
551        } else {
552            if (atom == EOF) {
553                return "<EOF>";
554            } else {
555                return "<invalid atom>";
556            }
557        }
558    }
559} // GetAtomString
560
561/*
562 * GetReversedAtom()
563 *
564 */
565
566int GetReversedAtom(AtomTable *atable, int atom)
567{
568    if (atom > 0 && atom < atable->nextFree) {
569        return atable->arev[atom];
570    } else {
571        return 0;
572    }
573} // GetReversedAtom
574
575/*
576 * AddAtom() - Add a string to the atom, hash and string tables if it isn't already there.
577 *         Return it's atom index.
578 */
579
580int AddAtom(AtomTable *atable, const char *s)
581{
582    int atom;
583
584    atom = LookUpAddString(atable, s);
585    return atom;
586} // AddAtom
587
588/*
589 * AddAtomFixed() - Add an atom to the hash and string tables if it isn't already there.
590 *         Assign it the atom value of "atom".
591 */
592
593static int AddAtomFixed(AtomTable *atable, const char *s, int atom)
594{
595    int hashindex, lsize;
596
597    hashindex = LookUpAddStringHash(atable, s);
598    if (atable->nextFree >= atable->size || atom >= atable->size) {
599        lsize = atable->size*2;
600        if (lsize <= atom)
601            lsize = atom + 1;
602        GrowAtomTable(atable, lsize);
603    }
604    atable->amap[atom] = atable->htable.entry[hashindex].index;
605    atable->htable.entry[hashindex].value = atom;
606    //if (atom >= atable->nextFree)
607    //    atable->nextFree = atom + 1;
608    while (atom >= atable->nextFree) {
609        atable->arev[atable->nextFree] = lReverse(atable->nextFree);
610        atable->nextFree++;
611    }
612    return atom;
613} // AddAtomFixed
614
615/*
616 * InitAtomTable() - Initialize the atom table.
617 *
618 */
619
620int InitAtomTable(AtomTable *atable, int htsize)
621{
622    unsigned int ii;
623
624    htsize = htsize <= 0 ? INIT_HASH_TABLE_SIZE : htsize;
625    if (!InitStringTable(&atable->stable))
626        return 0;
627    if (!InitHashTable(&atable->htable, htsize))
628        return 0;
629
630    atable->nextFree = 0;
631    atable->amap = NULL;
632    atable->size = 0;
633    GrowAtomTable(atable, INIT_ATOM_TABLE_SIZE);
634    if (!atable->amap)
635        return 0;
636
637    // Initialize lower part of atom table to "<undefined>" atom:
638
639    AddAtomFixed(atable, "<undefined>", 0);
640    for (ii = 0; ii < FIRST_USER_TOKEN_SY; ii++)
641        atable->amap[ii] = atable->amap[0];
642
643    // Add single character tokens to the atom table:
644
645    {
646		const char *s = "~!%^&*()-+=|,.<>/?;:[]{}#";
647        char t[2];
648
649        t[1] = '\0';
650        while (*s) {
651            t[0] = *s;
652            AddAtomFixed(atable, t, s[0]);
653            s++;
654        }
655    }
656
657    // Add multiple character scanner tokens :
658
659    for (ii = 0; ii < sizeof(tokens)/sizeof(tokens[0]); ii++)
660        AddAtomFixed(atable, tokens[ii].str, tokens[ii].val);
661
662    // Add error symbol if running in error mode:
663
664    if (cpp->options.ErrorMode)
665        AddAtomFixed(atable, "error", ERROR_SY);
666
667    AddAtom(atable, "<*** end fixed atoms ***>");
668
669    return 1;
670} // InitAtomTable
671
672///////////////////////////////////////////////////////////////////////////////////////////////
673////////////////////////////////// Debug Printing Functions: //////////////////////////////////
674///////////////////////////////////////////////////////////////////////////////////////////////
675
676/*
677 * PrintAtomTable()
678 *
679 */
680
681void PrintAtomTable(AtomTable *atable)
682{
683    int ii;
684    char str[200];
685
686    for (ii = 0; ii < atable->nextFree; ii++) {
687        sprintf(str, "%d: \"%s\"", ii, &atable->stable.strings[atable->amap[ii]]);
688        CPPDebugLogMsg(str);
689    }
690    sprintf(str, "Hash table: size=%d, entries=%d, collisions=",
691           atable->htable.size, atable->htable.entries);
692    CPPDebugLogMsg(str);
693    for (ii = 0; ii < HASH_TABLE_MAX_COLLISIONS; ii++) {
694        sprintf(str, " %d", atable->htable.counts[ii]);
695        CPPDebugLogMsg(str);
696    }
697
698} // PrintAtomTable
699
700
701/*
702 * GetStringOfAtom()
703 *
704 */
705
706char* GetStringOfAtom(AtomTable *atable, int atom)
707{
708	 char* chr_str;
709	 chr_str=&atable->stable.strings[atable->amap[atom]];
710	 return chr_str;
711} // GetStringOfAtom
712
713/*
714 * FreeAtomTable() - Free the atom table and associated memory
715 *
716 */
717
718void FreeAtomTable(AtomTable *atable)
719{
720    FreeStringTable(&atable->stable);
721    FreeHashTable(&atable->htable);
722    if (atable->amap)
723        free(atable->amap);
724    if (atable->arev)
725        free(atable->arev);
726    atable->amap = NULL;
727    atable->arev = NULL;
728    atable->nextFree = 0;
729    atable->size = 0;
730} // FreeAtomTable
731
732///////////////////////////////////////////////////////////////////////////////////////////////
733///////////////////////////////////////// End of atom.c ///////////////////////////////////////
734///////////////////////////////////////////////////////////////////////////////////////////////
735
736