1e2390c872a80e189c21b988ca96eff81d2771e7
[Faustine.git] / interpretor / faust-0.9.47mr3 / compiler / tlib / symbol.cpp
1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale
5 ---------------------------------------------------------------------
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 ************************************************************************
20 ************************************************************************/
21
22 #include <stdlib.h>
23 #include <stdio.h>
24 #include <string.h>
25 #include "symbol.hh"
26 #include "compatibility.hh"
27 #include <iostream>
28 #include <cstring>
29 #include <assert.h>
30
31 using namespace std;
32
33 /**
34 * Hash table used to store the symbols
35 */
36
37 Symbol* Symbol::gSymbolTable[kHashTableSize];
38
39
40 /**
41 * Search the hash table for the symbol of name \p str or returns a new one.
42 * \param str the name of the symbol
43 * \return a symbol of name str
44 */
45
46 Symbol* Symbol::get(const string& str)
47 {
48 char buf[1024];
49 int i;
50 int n = str.length();
51
52 if (n>1023) n = 1023;
53 for (i = 0; i < n; i++) { buf[i] = str[i]; }
54 buf[i] = 0;
55
56 return Symbol::get(buf);
57 }
58
59
60
61 /**
62 * Search the hash table for the symbol of name \p str or returns a new one.
63 * \param str the name of the symbol
64 * \return a symbol of name str
65 */
66
67 Symbol* Symbol::get(const char* str)
68 {
69 unsigned int hsh = calcHashKey(str);
70 int bckt = hsh % kHashTableSize;
71 Symbol* item = gSymbolTable[bckt];
72
73 while ( item && !item->equiv(hsh,str) ) item = item->fNext;
74 Symbol* r = item ? item : gSymbolTable[bckt] = new Symbol(str, hsh, gSymbolTable[bckt]);
75 return r;
76 }
77
78
79 /**
80 * Static method that searches the symbol table for a string.
81 * \param str string to search
82 * \return true if the string is NOT in the table (it is a new string)
83 */
84
85 bool Symbol::isnew(const char* str)
86 {
87 unsigned int hsh = calcHashKey(str);
88 int bckt = hsh % kHashTableSize;
89 Symbol* item = gSymbolTable[bckt];
90
91 while ( item && !item->equiv(hsh,str) ) item = item->fNext;
92 return item == 0;
93 }
94
95
96 /**
97 * Creates a new symbol with a name obtained by concatenating the \p str prefix with a number in order to make it unique
98 * \param str the prefix of the name
99 * \return a symbol of name \p prefix++n
100 */
101
102 Symbol* Symbol::prefix (const char* str)
103 {
104 char name[256];
105
106 static map<const char*, unsigned int> gPrefixCounters;
107
108 for (int n = 0; n<10000; n++) {
109 snprintf(name, 256, "%s%d", str, gPrefixCounters[str]++);
110 if (isnew(name)) return get(name);
111 }
112 assert(false);
113 return get("UNIQUEOVERFLOW");
114 }
115
116
117 /**
118 * Check if the name of the symbol is equal to string \p str
119 * This method is used by isnew() and make() when searching the hashtable
120 * for an existing symbol.
121 *
122 * \param hash the hash key of the string (used to speedup the comparison)
123 * \param str the string to compare
124 * \return \p true if the name of the symbol and \p str are the same
125 */
126
127 bool Symbol::equiv (unsigned int hash, const char *str) const
128 {
129 return (fHash == hash) && (strcmp(fName,str) == 0);
130 }
131
132
133
134 /**
135 * Compute the 32-bits hash key of string \p str
136 * \param str the string
137 * \return a 32-bits hash key
138 */
139
140 unsigned int Symbol::calcHashKey (const char* str)
141 {
142 unsigned int h = 0;
143
144 while (*str) h = (h << 1) ^ (h >> 20) ^ (*str++);
145 return h;
146 }
147
148
149
150 /**
151 * Constructs a symbol ready to be placed in the hash table.
152 * It makes a private copy of its name.
153 * \param str the name of the symbol
154 * \param hsh the hash key of the symbol
155 * \param nxt a pointer to the next symbol in the hash table entry
156 */
157
158 Symbol::Symbol(const char* str, unsigned int hsh, Symbol* nxt)
159 {
160 int len = strlen(str);
161
162 fName = new char [len+1];
163 memcpy(fName, str, len+1);
164 fHash = hsh;
165 fNext = nxt;
166 fData = 0;
167 }
168
169 Symbol::~Symbol ()
170 {
171 delete [] fName;
172 }
173
174 ostream& Symbol::print (ostream& fout) const ///< print a symbol on a stream
175 {
176 return fout << fName;
177 }