|
FAUST compiler
0.9.9.6b8
|
00001 /************************************************************************ 00002 ************************************************************************ 00003 FAUST compiler 00004 Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale 00005 --------------------------------------------------------------------- 00006 This program is free software; you can redistribute it and/or modify 00007 it under the terms of the GNU General Public License as published by 00008 the Free Software Foundation; either version 2 of the License, or 00009 (at your option) any later version. 00010 00011 This program is distributed in the hope that it will be useful, 00012 but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 GNU General Public License for more details. 00015 00016 You should have received a copy of the GNU General Public License 00017 along with this program; if not, write to the Free Software 00018 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00019 ************************************************************************ 00020 ************************************************************************/ 00021 00022 00023 /***************************************************************************** 00024 ******************************************************************************/ 00025 00070 /***************************************************************************** 00071 ******************************************************************************/ 00072 00073 00074 00075 #ifndef __TREE__ 00076 #define __TREE__ 00077 00078 #include "symbol.hh" 00079 #include "node.hh" 00080 #include <vector> 00081 #include <map> 00082 #include <assert.h> 00083 00084 //---------------------------------API--------------------------------------- 00085 00086 class CTree; 00087 typedef CTree* Tree; 00088 00089 typedef map<Tree, Tree> plist; 00090 typedef vector<Tree> tvec; 00091 00109 class CTree 00110 { 00111 private: 00112 static const int kHashTableSize = 2000000; //510511; ///< size of the hash table used for "hash consing" 00113 static Tree gHashTable[kHashTableSize]; 00114 00115 public: 00116 static bool gDetails; 00117 static unsigned int gVisitTime; 00118 00119 private: 00120 // fields 00121 Tree fNext; 00122 Node fNode; 00123 void* fType; 00124 plist fProperties; 00125 unsigned int fHashKey; 00126 int fAperture; 00127 unsigned int fVisitTime; 00128 tvec fBranch; 00129 00130 CTree (unsigned int hk, const Node& n, const tvec& br); 00131 00132 bool equiv (const Node& n, const tvec& br) const; 00133 static unsigned int calcTreeHash (const Node& n, const tvec& br); 00134 static int calcTreeAperture (const Node& n, const tvec& br); 00135 00136 public: 00137 ~CTree (); 00138 00139 static Tree make (const Node& n, int ar, Tree br[]); 00140 static Tree make(const Node& n, const tvec& br); 00141 00142 // Accessors 00143 const Node& node() const { return fNode; } 00144 int arity() const { return fBranch.size();} 00145 Tree branch(int i) const { return fBranch[i]; } 00146 unsigned int hashkey() const { return fHashKey; } 00147 int aperture() const { return fAperture; } 00148 void setAperture(int a) { fAperture=a; } 00149 00150 00151 // Print a tree and the hash table (for debugging purposes) 00152 ostream& print (ostream& fout) const; 00153 static void control (); 00154 00155 // type information 00156 void setType(void* t) { fType = t; } 00157 void* getType() { return fType; } 00158 00159 // Keep track of visited trees (WARNING : non reentrant) 00160 static void startNewVisit() { ++gVisitTime; } 00161 bool isAlreadyVisited() { return fVisitTime==gVisitTime; } 00162 void setVisited() { /*assert(fVisitTime!=gVisitTime);*/ fVisitTime=gVisitTime; } 00163 00164 00165 // Property list of a tree 00166 void setProperty(Tree key, Tree value) { fProperties[key] = value; } 00167 void clearProperty(Tree key) { fProperties.erase(key); } 00168 void clearProperties() { fProperties = plist(); } 00169 00170 void exportProperties(vector<Tree>& keys, vector<Tree>& values); 00171 00172 Tree getProperty(Tree key) { 00173 plist::iterator i = fProperties.find(key); 00174 if (i==fProperties.end()) { 00175 return 0; 00176 } else { 00177 return i->second; 00178 } 00179 } 00180 }; 00181 00182 //---------------------------------API--------------------------------------- 00183 00184 // to build trees 00185 inline Tree tree (const Node& n) { Tree br[1]; return CTree::make(n, 0, br); } 00186 inline Tree tree (const Node& n, const Tree& a) { Tree br[]= {a}; return CTree::make(n, 1, br); } 00187 inline Tree tree (const Node& n, const Tree& a, const Tree& b) { Tree br[]= {a,b}; return CTree::make(n, 2, br); } 00188 inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c) { Tree br[]= {a,b,c}; return CTree::make(n, 3, br); } 00189 inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d) { Tree br[]= {a,b,c,d}; return CTree::make(n, 4, br); } 00190 00191 inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d, const Tree& e) { Tree br[]= {a,b,c,d,e}; return CTree::make(n, 5, br); } 00192 00193 // useful conversions 00194 int tree2int (Tree t); 00195 double tree2float (Tree t); 00196 double tree2double (Tree t); 00197 const char* tree2str (Tree t); 00198 void* tree2ptr (Tree t); 00199 void* getUserData(Tree t); 00200 00201 // pattern matching 00202 bool isTree (const Tree& t, const Node& n); 00203 bool isTree (const Tree& t, const Node& n, Tree& a); 00204 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b); 00205 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c); 00206 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d); 00207 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e); 00208 00209 //printing 00210 inline ostream& operator << (ostream& s, const CTree& t) { return t.print(s); } 00211 00212 00213 //----------------------------------------------------------------------------- 00214 // recursive trees 00215 //----------------------------------------------------------------------------- 00216 00217 // creation a recursive trees 00218 00219 Tree rec(Tree body); 00220 Tree rec(Tree id, Tree body); 00221 00222 bool isRec(Tree t, Tree& body); 00223 bool isRec(Tree t, Tree& id, Tree& body); 00224 00225 // creation of recursive references 00226 00227 Tree ref(int level); 00228 Tree ref(Tree id); 00229 00230 bool isRef(Tree t, int& level); 00231 bool isRef(Tree t, Tree& id); 00232 00233 00234 // Open vs Closed regarding de Bruijn references 00235 00236 inline bool isOpen(Tree t) { return t->aperture() > 0; } 00237 inline bool isClosed(Tree t) { return t->aperture() <= 0;} 00238 00239 // lift by 1 the free de Bruijn references 00240 00241 Tree lift(Tree t); 00242 00243 Tree deBruijn2Sym (Tree t); 00244 void updateAperture (Tree t); 00245 00246 //--------------------------------------------------------------------------- 00247 00248 class Tabber 00249 { 00250 int fIndent; 00251 int fPostInc; 00252 public: 00253 Tabber(int n=0) : fIndent(n), fPostInc(0) {} 00254 Tabber& operator++() { fPostInc++; return *this;} 00255 Tabber& operator--() { assert(fIndent > 0); fIndent--; return *this; } 00256 00257 ostream& print (ostream& fout) 00258 { for (int i=0; i<fIndent; i++) fout << '\t'; fIndent+=fPostInc; fPostInc=0; return fout; } 00259 }; 00260 00261 //printing 00262 inline ostream& operator << (ostream& s, Tabber& t) { return t.print(s); } 00263 00264 extern Tabber TABBER; 00265 00266 00267 #endif
1.8.0