01d16e014a5540353994a3e007c9bbca9933f13b
[Faustine.git] / interpretor / preprocessor / faust-0.9.47mr3 / compiler / tlib / tree.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
23
24 /*****************************************************************************
25 ******************************************************************************
26 TREE
27 Y. Orlarey, (c) Grame 2002
28 ------------------------------------------------------------------------------
29 Trees are made of a Node associated with a list of branches : (Node x [CTree]).
30 Up to 4 branches are allowed in this implementation. A hash table is used to
31 maximize the sharing of trees during construction : trees at different
32 addresses always have a different content. Reference counting is used for
33 garbage collection, and smart pointers P<CTree> should be used for permanent
34 storage of trees.
35
36 API:
37 ----
38 tree (n) : tree of node n with no branch
39 tree (n, t1) : tree of node n with a branch t
40 tree (n, t1,...,tm) : tree of node n with m branches t1,...,tm
41
42 Pattern matching :
43
44 if (isTree (t, n)) ... : t has node n and no branches;
45 if (isTree (t, n, &t1) ... : t has node n and 1 branch, t1 is set accordingly;
46 if (isTree (t, n, &t1...&tm)...: t has node n and m branches, ti's are set accordingly;
47
48 Accessors :
49
50 t->node() : the node of t { return fNode; }
51 t->arity() : the number of branches of t return fArity; }
52 t->branch(i) : the ith branch of t
53
54 Attributs :
55
56 t->attribut() : return the attribut (also a tree) of t
57 t->attribut(t') : set the attribut of t to t'
58
59 Warning :
60 ---------
61 Since reference counters are used for garbage collecting, one must be careful not to
62 create cycles in trees The only possible source of cycles is by setting the attribut
63 of a tree t to a tree t' that contains t as a subtree.
64
65 Properties:
66 -----------
67 If p and q are two CTree pointers :
68 p != q <=> *p != *q
69
70 History :
71 ---------
72 2002-02-08 : First version
73 2002-10-14 : counts for height and recursiveness added
74
75 ******************************************************************************
76 *****************************************************************************/
77
78 #include <stdlib.h>
79 #include <stdio.h>
80 #include <string.h>
81 #include <limits.h>
82 #include "tree.hh"
83 #include <fstream>
84 #include <cstdlib>
85
86 Tabber TABBER(1);
87 extern Tabber TABBER;
88
89
90 static void error(const char * s, Tree t)
91 {
92 //fprintf(stderr, "ERROR : %s (%p)\n", s, t);
93 cerr << "ERROR : " << s << " : " << *t << endl;
94 }
95
96 #define ERROR(s,t) { error(s,t); exit(1); }
97
98
99 Tree CTree::gHashTable[kHashTableSize];
100 bool CTree::gDetails = false;
101 unsigned int CTree::gVisitTime = 0; ///< Should be incremented for each new visit to keep track of visited tree.
102
103 // Constructor : add the tree to the hash table
104 CTree::CTree (unsigned int hk, const Node& n, const tvec& br)
105 : fNode(n),
106 fType(0),
107 fHashKey(hk),
108 fAperture(calcTreeAperture(n,br)),
109 fVisitTime(0),
110 fBranch(br)
111 {
112 // link dans la hash table
113 int j = hk % kHashTableSize;
114 fNext = gHashTable[j];
115 gHashTable[j] = this;
116
117 }
118
119 // Destructor : remove the tree form the hash table
120 CTree::~CTree ()
121 {
122 int i = fHashKey % kHashTableSize;
123 Tree t = gHashTable[i];
124
125 //printf("Delete of "); this->print(); printf("\n");
126 if (t == this) {
127 gHashTable[i] = fNext;
128 } else {
129 Tree p;
130 while (t != this) {
131 p = t;
132 t = t->fNext;
133 }
134 p->fNext = fNext;
135 }
136 }
137
138 // equivalence
139 bool CTree::equiv (const Node& n, const tvec& br) const
140 {
141 return (fNode == n) && (fBranch == br);
142 }
143
144 Sym PROCESS = symbol("process");
145
146
147
148
149 unsigned int CTree::calcTreeHash( const Node& n, const tvec& br )
150 {
151 unsigned int hk = n.type() ^ n.getInt();
152 tvec::const_iterator b = br.begin();
153 tvec::const_iterator z = br.end();
154
155 while (b != z) {
156 hk = (hk << 1) ^ (hk >> 20) ^ ((*b)->fHashKey);
157 ++b;
158 }
159 return hk;
160 }
161
162
163 Tree CTree::make(const Node& n, int ar, Tree* tbl)
164 {
165 tvec br(ar);
166
167 for (int i=0; i<ar; i++) br[i] = tbl[i];
168
169 unsigned int hk = calcTreeHash(n, br);
170 Tree t = gHashTable[hk % kHashTableSize];
171
172 while (t && !t->equiv(n, br)) {
173 t = t->fNext;
174 }
175 return (t) ? t : new CTree(hk, n, br);
176 }
177
178
179 Tree CTree::make(const Node& n, const tvec& br)
180 {
181 unsigned int hk = calcTreeHash(n, br);
182 Tree t = gHashTable[hk % kHashTableSize];
183
184 while (t && !t->equiv(n, br)) {
185 t = t->fNext;
186 }
187 return (t) ? t : new CTree(hk, n, br);
188 }
189
190 ostream& CTree::print (ostream& fout) const
191 {
192 if (gDetails) {
193 // print the adresse of the tree
194 fout << "<" << this << ">@";
195 }
196 fout << node();
197 int a = arity();
198 if (a > 0) {
199 int i; char sep;
200 for (sep = '[', i = 0; i < a; sep = ',', i++) {
201 fout << sep; branch(i)->print(fout);
202 }
203 fout << ']';
204 }
205
206 return fout;
207 }
208
209
210 void CTree::control ()
211 {
212 printf("\ngHashTable Content :\n\n");
213 for (int i = 0; i < kHashTableSize; i++) {
214 Tree t = gHashTable[i];
215 if (t) {
216 printf ("%4d = ", i);
217 while (t) {
218 /*t->print();*/
219 printf(" => ");
220 t = t->fNext;
221 }
222 printf("VOID\n");
223 }
224 }
225 printf("\nEnd gHashTable\n");
226
227 }
228
229 // if t has a node of type int, return it otherwise error
230 int tree2int (Tree t)
231 {
232 double x;
233 int i;
234
235 if (isInt(t->node(), &i)) {
236 // nothing to do
237 } else if (isDouble(t->node(), &x)) {
238 i = int(x);
239 } else {
240 ERROR("the node of the tree is not an int nor a float", t);
241 }
242 return i;
243 }
244
245 // if t has a node of type float, return it otherwise error
246 double tree2float (Tree t)
247 {
248 double x;
249 int i;
250
251 if (isInt(t->node(), &i)) {
252 x = double(i);
253 } else if (isDouble(t->node(), &x)) {
254 //nothing to do
255 } else {
256 ERROR("the node of the tree is not a float nor an int", t);
257 }
258 return x;
259 }
260
261 // if t has a node of type float, return it as a double otherwise error
262 double tree2double (Tree t)
263 {
264 double x;
265 int i;
266
267 if (isInt(t->node(), &i)) {
268 x = double(i);
269 } else if (isDouble(t->node(), &x)) {
270 //nothing to do
271 } else {
272 ERROR("the node of the tree is not a float nor an int", t);
273 }
274 return double(x);
275 }
276
277 // if t has a node of type symbol, return its name otherwise error
278 const char* tree2str (Tree t)
279 {
280 Sym s;
281 if (!isSym(t->node(), &s)) {
282 ERROR("the node of the tree is not a symbol", t);
283 }
284 return name(s);
285 }
286
287 // if t has a node of type ptr, return it otherwise error
288 void* tree2ptr (Tree t)
289 {
290 void* x;
291 if (! isPointer(t->node(), &x)) {
292 ERROR("the node of the tree is not a pointer", t);
293 }
294 return x;
295 }
296
297 /*
298 bool isTree (const Tree& t, const Node& n)
299 {
300 return (t->node() == n) && (t->arity() == 0);
301 }
302 */
303
304 // Si ca ne pose pas de probl�es, c'est plus pratique
305 bool isTree (const Tree& t, const Node& n)
306 {
307 return (t->node() == n);
308 }
309
310 bool isTree (const Tree& t, const Node& n, Tree& a)
311 {
312 if ((t->node() == n) && (t->arity() == 1)) {
313 a=t->branch(0);
314 return true;
315 } else {
316 return false;
317 }
318 }
319
320 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b)
321 {
322 if ((t->node() == n) && (t->arity() == 2)) {
323 a=t->branch(0);
324 b=t->branch(1);
325 return true;
326 } else {
327 return false;
328 }
329 }
330
331 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c)
332 {
333 if ((t->node() == n) && (t->arity() == 3)) {
334 a=t->branch(0);
335 b=t->branch(1);
336 c=t->branch(2);
337 return true;
338 } else {
339 return false;
340 }
341 }
342
343 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d)
344 {
345 if ((t->node() == n) && (t->arity() == 4)) {
346 a=t->branch(0);
347 b=t->branch(1);
348 c=t->branch(2);
349 d=t->branch(3);
350 return true;
351 } else {
352 return false;
353 }
354 }
355
356 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e)
357 {
358 if ((t->node() == n) && (t->arity() == 5)) {
359 a=t->branch(0);
360 b=t->branch(1);
361 c=t->branch(2);
362 d=t->branch(3);
363 e=t->branch(4);
364 return true;
365 } else {
366 return false;
367 }
368 }
369
370 // July 2005, support for symbol user data
371
372 void* getUserData(Tree t)
373 {
374 Sym s;
375 if (isSym(t->node(), &s)) {
376 return getUserData(s);
377 } else {
378 return 0;
379 }
380 }
381
382
383 /**
384 * export the properties of a CTree as two vectors, one for the keys
385 * and one for the associated values
386 */
387
388 void CTree::exportProperties(vector<Tree>& keys, vector<Tree>& values)
389 {
390 for (plist::const_iterator p = fProperties.begin(); p != fProperties.end(); p++) {
391 keys.push_back(p->first);
392 values.push_back(p->second);
393 }
394 }
395