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