interpretor/preprocessor/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 }