X-Git-Url: https://scm.cri.ensmp.fr/git/Faustine.git/blobdiff_plain/1059e1cc0c2ecfa237406949aa26155b6a5b9154..66f23d4fabf89ad09adbd4dfc15ac6b5b2b7da83:/interpreter/preprocessor/faust-0.9.47mr3/compiler/tlib/tree.cpp diff --git a/interpreter/preprocessor/faust-0.9.47mr3/compiler/tlib/tree.cpp b/interpreter/preprocessor/faust-0.9.47mr3/compiler/tlib/tree.cpp new file mode 100644 index 0000000..01d16e0 --- /dev/null +++ b/interpreter/preprocessor/faust-0.9.47mr3/compiler/tlib/tree.cpp @@ -0,0 +1,395 @@ +/************************************************************************ + ************************************************************************ + FAUST compiler + Copyright (C) 2003-2004 GRAME, Centre National de Creation Musicale + --------------------------------------------------------------------- + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + ************************************************************************ + ************************************************************************/ + + + +/***************************************************************************** +****************************************************************************** + TREE + Y. Orlarey, (c) Grame 2002 +------------------------------------------------------------------------------ +Trees are made of a Node associated with a list of branches : (Node x [CTree]). +Up to 4 branches are allowed in this implementation. A hash table is used to +maximize the sharing of trees during construction : trees at different +addresses always have a different content. Reference counting is used for +garbage collection, and smart pointers P should be used for permanent +storage of trees. + + API: + ---- + tree (n) : tree of node n with no branch + tree (n, t1) : tree of node n with a branch t + tree (n, t1,...,tm) : tree of node n with m branches t1,...,tm + + Pattern matching : + + if (isTree (t, n)) ... : t has node n and no branches; + if (isTree (t, n, &t1) ... : t has node n and 1 branch, t1 is set accordingly; + if (isTree (t, n, &t1...&tm)...: t has node n and m branches, ti's are set accordingly; + + Accessors : + + t->node() : the node of t { return fNode; } + t->arity() : the number of branches of t return fArity; } + t->branch(i) : the ith branch of t + + Attributs : + + t->attribut() : return the attribut (also a tree) of t + t->attribut(t') : set the attribut of t to t' + + Warning : + --------- + Since reference counters are used for garbage collecting, one must be careful not to + create cycles in trees The only possible source of cycles is by setting the attribut + of a tree t to a tree t' that contains t as a subtree. + + Properties: + ----------- + If p and q are two CTree pointers : + p != q <=> *p != *q + + History : + --------- + 2002-02-08 : First version + 2002-10-14 : counts for height and recursiveness added + +****************************************************************************** +*****************************************************************************/ + +#include +#include +#include +#include +#include "tree.hh" +#include +#include + +Tabber TABBER(1); +extern Tabber TABBER; + + +static void error(const char * s, Tree t) +{ + //fprintf(stderr, "ERROR : %s (%p)\n", s, t); + cerr << "ERROR : " << s << " : " << *t << endl; +} + +#define ERROR(s,t) { error(s,t); exit(1); } + + +Tree CTree::gHashTable[kHashTableSize]; +bool CTree::gDetails = false; +unsigned int CTree::gVisitTime = 0; ///< Should be incremented for each new visit to keep track of visited tree. + +// Constructor : add the tree to the hash table +CTree::CTree (unsigned int hk, const Node& n, const tvec& br) + : fNode(n), + fType(0), + fHashKey(hk), + fAperture(calcTreeAperture(n,br)), + fVisitTime(0), + fBranch(br) +{ + // link dans la hash table + int j = hk % kHashTableSize; + fNext = gHashTable[j]; + gHashTable[j] = this; + +} + +// Destructor : remove the tree form the hash table +CTree::~CTree () +{ + int i = fHashKey % kHashTableSize; + Tree t = gHashTable[i]; + + //printf("Delete of "); this->print(); printf("\n"); + if (t == this) { + gHashTable[i] = fNext; + } else { + Tree p; + while (t != this) { + p = t; + t = t->fNext; + } + p->fNext = fNext; + } +} + +// equivalence +bool CTree::equiv (const Node& n, const tvec& br) const +{ + return (fNode == n) && (fBranch == br); +} + +Sym PROCESS = symbol("process"); + + + + +unsigned int CTree::calcTreeHash( const Node& n, const tvec& br ) +{ + unsigned int hk = n.type() ^ n.getInt(); + tvec::const_iterator b = br.begin(); + tvec::const_iterator z = br.end(); + + while (b != z) { + hk = (hk << 1) ^ (hk >> 20) ^ ((*b)->fHashKey); + ++b; + } + return hk; +} + + +Tree CTree::make(const Node& n, int ar, Tree* tbl) +{ + tvec br(ar); + + for (int i=0; iequiv(n, br)) { + t = t->fNext; + } + return (t) ? t : new CTree(hk, n, br); +} + + +Tree CTree::make(const Node& n, const tvec& br) +{ + unsigned int hk = calcTreeHash(n, br); + Tree t = gHashTable[hk % kHashTableSize]; + + while (t && !t->equiv(n, br)) { + t = t->fNext; + } + return (t) ? t : new CTree(hk, n, br); +} + +ostream& CTree::print (ostream& fout) const +{ + if (gDetails) { + // print the adresse of the tree + fout << "<" << this << ">@"; + } + fout << node(); + int a = arity(); + if (a > 0) { + int i; char sep; + for (sep = '[', i = 0; i < a; sep = ',', i++) { + fout << sep; branch(i)->print(fout); + } + fout << ']'; + } + + return fout; +} + + +void CTree::control () +{ + printf("\ngHashTable Content :\n\n"); + for (int i = 0; i < kHashTableSize; i++) { + Tree t = gHashTable[i]; + if (t) { + printf ("%4d = ", i); + while (t) { + /*t->print();*/ + printf(" => "); + t = t->fNext; + } + printf("VOID\n"); + } + } + printf("\nEnd gHashTable\n"); + +} + +// if t has a node of type int, return it otherwise error +int tree2int (Tree t) +{ + double x; + int i; + + if (isInt(t->node(), &i)) { + // nothing to do + } else if (isDouble(t->node(), &x)) { + i = int(x); + } else { + ERROR("the node of the tree is not an int nor a float", t); + } + return i; +} + +// if t has a node of type float, return it otherwise error +double tree2float (Tree t) +{ + double x; + int i; + + if (isInt(t->node(), &i)) { + x = double(i); + } else if (isDouble(t->node(), &x)) { + //nothing to do + } else { + ERROR("the node of the tree is not a float nor an int", t); + } + return x; +} + +// if t has a node of type float, return it as a double otherwise error +double tree2double (Tree t) +{ + double x; + int i; + + if (isInt(t->node(), &i)) { + x = double(i); + } else if (isDouble(t->node(), &x)) { + //nothing to do + } else { + ERROR("the node of the tree is not a float nor an int", t); + } + return double(x); +} + +// if t has a node of type symbol, return its name otherwise error +const char* tree2str (Tree t) +{ + Sym s; + if (!isSym(t->node(), &s)) { + ERROR("the node of the tree is not a symbol", t); + } + return name(s); +} + +// if t has a node of type ptr, return it otherwise error +void* tree2ptr (Tree t) +{ + void* x; + if (! isPointer(t->node(), &x)) { + ERROR("the node of the tree is not a pointer", t); + } + return x; +} + +/* +bool isTree (const Tree& t, const Node& n) +{ + return (t->node() == n) && (t->arity() == 0); +} +*/ + +// Si ca ne pose pas de probl�es, c'est plus pratique +bool isTree (const Tree& t, const Node& n) +{ + return (t->node() == n); +} + +bool isTree (const Tree& t, const Node& n, Tree& a) +{ + if ((t->node() == n) && (t->arity() == 1)) { + a=t->branch(0); + return true; + } else { + return false; + } +} + +bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b) +{ + if ((t->node() == n) && (t->arity() == 2)) { + a=t->branch(0); + b=t->branch(1); + return true; + } else { + return false; + } +} + +bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c) +{ + if ((t->node() == n) && (t->arity() == 3)) { + a=t->branch(0); + b=t->branch(1); + c=t->branch(2); + return true; + } else { + return false; + } +} + +bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d) +{ + if ((t->node() == n) && (t->arity() == 4)) { + a=t->branch(0); + b=t->branch(1); + c=t->branch(2); + d=t->branch(3); + return true; + } else { + return false; + } +} + +bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e) +{ + if ((t->node() == n) && (t->arity() == 5)) { + a=t->branch(0); + b=t->branch(1); + c=t->branch(2); + d=t->branch(3); + e=t->branch(4); + return true; + } else { + return false; + } +} + +// July 2005, support for symbol user data + +void* getUserData(Tree t) +{ + Sym s; + if (isSym(t->node(), &s)) { + return getUserData(s); + } else { + return 0; + } +} + + +/** + * export the properties of a CTree as two vectors, one for the keys + * and one for the associated values + */ + +void CTree::exportProperties(vector& keys, vector& values) +{ + for (plist::const_iterator p = fProperties.begin(); p != fProperties.end(); p++) { + keys.push_back(p->first); + values.push_back(p->second); + } +} +