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