+++ /dev/null
-/************************************************************************
- ************************************************************************
- 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<CTree> 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 <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-#include <limits.h>
-#include "tree.hh"
-#include <fstream>
-#include <cstdlib>
-
-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; i<ar; i++) br[i] = tbl[i];
-
- 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);
-}
-
-
-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<Tree>& keys, vector<Tree>& values)
-{
- for (plist::const_iterator p = fProperties.begin(); p != fProperties.end(); p++) {
- keys.push_back(p->first);
- values.push_back(p->second);
- }
-}
-
projects / Faustine.git / blobdiff