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
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
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.
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 ************************************************************************/
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.
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
42 Pattern matching :
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;
48 Accessors :
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
54 Attributs :
56 t->attribut() : return the attribut (also a tree) of t
57 t->attribut(t') : set the attribut of t to t'
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.
65 Properties:
66 -----------
67 If p and q are two CTree pointers :
68 p != q <=> *p != *q
70 History :
71 ---------
72 2002-02-08 : First version
73 2002-10-14 : counts for height and recursiveness added
75 ******************************************************************************
76 *****************************************************************************/
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>
86 Tabber TABBER(1);
87 extern Tabber TABBER;
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 }
96 #define ERROR(s,t) { error(s,t); exit(1); }
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.
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;
117 }
119 // Destructor : remove the tree form the hash table
120 CTree::~CTree ()
121 {
122 int i = fHashKey % kHashTableSize;
123 Tree t = gHashTable[i];
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 }
138 // equivalence
139 bool CTree::equiv (const Node& n, const tvec& br) const
140 {
141 return (fNode == n) && (fBranch == br);
142 }
144 Sym PROCESS = symbol("process");
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();
155 while (b != z) {
156 hk = (hk << 1) ^ (hk >> 20) ^ ((*b)->fHashKey);
157 ++b;
158 }
159 return hk;
160 }
163 Tree CTree::make(const Node& n, int ar, Tree* tbl)
164 {
165 tvec br(ar);
167 for (int i=0; i<ar; i++) br[i] = tbl[i];
169 unsigned int hk = calcTreeHash(n, br);
170 Tree t = gHashTable[hk % kHashTableSize];
172 while (t && !t->equiv(n, br)) {
173 t = t->fNext;
174 }
175 return (t) ? t : new CTree(hk, n, br);
176 }
179 Tree CTree::make(const Node& n, const tvec& br)
180 {
181 unsigned int hk = calcTreeHash(n, br);
182 Tree t = gHashTable[hk % kHashTableSize];
184 while (t && !t->equiv(n, br)) {
185 t = t->fNext;
186 }
187 return (t) ? t : new CTree(hk, n, br);
188 }
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 }
206 return fout;
207 }
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");
227 }
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;
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 }
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;
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 }
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;
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 }
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 }
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 }
297 /*
298 bool isTree (const Tree& t, const Node& n)
299 {
300 return (t->node() == n) && (t->arity() == 0);
301 }
302 */
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 }
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 }
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 }
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 }
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 }
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 }
370 // July 2005, support for symbol user data
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 }
383 /**
384 * export the properties of a CTree as two vectors, one for the keys
385 * and one for the associated values
386 */
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 }