00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078 #include <stdio.h>
00079 #include <stdlib.h>
00080 #include <limits.h>
00081 #include "tree.hh"
00082 #include <fstream>
00083
00084 Tabber TABBER(1);
00085 extern Tabber TABBER;
00086
00087
00088 static void error(const char * s, Tree t)
00089 {
00090
00091 cerr << "ERROR : " << s << " : " << *t << endl;
00092 }
00093
00094 #define ERROR(s,t) { error(s,t); exit(1); }
00095
00096
00097 Tree CTree::gHashTable[kHashTableSize];
00098 bool CTree::gDetails = false;
00099
00100
00101 CTree::CTree (unsigned int hk, const Node& n, const tvec& br)
00102 : fNode(n),
00103 fType(0),
00104 fHashKey(hk),
00105 fAperture(calcTreeAperture(n,br)),
00106 fBranch(br)
00107 {
00108
00109 int j = hk % kHashTableSize;
00110 fNext = gHashTable[j];
00111 gHashTable[j] = this;
00112
00113 }
00114
00115
00116 CTree::~CTree ()
00117 {
00118 int i = fHashKey % kHashTableSize;
00119 Tree t = gHashTable[i];
00120
00121
00122 if (t == this) {
00123 gHashTable[i] = fNext;
00124 } else {
00125 Tree p;
00126 while (t != this) {
00127 p = t;
00128 t = t->fNext;
00129 }
00130 p->fNext = fNext;
00131 }
00132 }
00133
00134
00135 bool CTree::equiv (const Node& n, const tvec& br) const
00136 {
00137 return (fNode == n) && (fBranch == br);
00138 }
00139
00140 Sym PROCESS = symbol("process");
00141
00142
00143
00144
00145 unsigned int CTree::calcTreeHash( const Node& n, const tvec& br )
00146 {
00147 unsigned int hk = n.type() ^ n.getInt();
00148 tvec::const_iterator b = br.begin();
00149 tvec::const_iterator z = br.end();
00150
00151 while (b != z) {
00152 hk = (hk << 1) ^ (hk >> 20) ^ ((*b)->fHashKey);
00153 ++b;
00154 }
00155 return hk;
00156 }
00157
00158
00159 Tree CTree::make(const Node& n, int ar, Tree* tbl)
00160 {
00161 tvec br(ar);
00162
00163 for (int i=0; i<ar; i++) br[i] = tbl[i];
00164
00165 unsigned int hk = calcTreeHash(n, br);
00166 Tree t = gHashTable[hk % kHashTableSize];
00167
00168 while (t && !t->equiv(n, br)) {
00169 t = t->fNext;
00170 }
00171 return (t) ? t : new CTree(hk, n, br);
00172 }
00173
00174
00175 Tree CTree::make(const Node& n, const tvec& br)
00176 {
00177 unsigned int hk = calcTreeHash(n, br);
00178 Tree t = gHashTable[hk % kHashTableSize];
00179
00180 while (t && !t->equiv(n, br)) {
00181 t = t->fNext;
00182 }
00183 return (t) ? t : new CTree(hk, n, br);
00184 }
00185
00186 ostream& CTree::print (ostream& fout) const
00187 {
00188 if (gDetails) {
00189
00190 fout << "<" << this << ">@";
00191 }
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208 fout << node();
00209 int a = arity();
00210 if (a > 0) {
00211 int i; char sep;
00212 for (sep = '[', i = 0; i < a; sep = ',', i++) {
00213 fout << sep; branch(i)->print(fout);
00214 }
00215 fout << ']';
00216 }
00217
00218 return fout;
00219 }
00220
00221
00222 void CTree::control ()
00223 {
00224 printf("\ngHashTable Content :\n\n");
00225 for (int i = 0; i < kHashTableSize; i++) {
00226 Tree t = gHashTable[i];
00227 if (t) {
00228 printf ("%4d = ", i);
00229 while (t) {
00230
00231 printf(" => ");
00232 t = t->fNext;
00233 }
00234 printf("VOID\n");
00235 }
00236 }
00237 printf("\nEnd gHashTable\n");
00238
00239 }
00240
00241
00242 int tree2int (Tree t)
00243 {
00244 float x;
00245 int i;
00246
00247 if (isInt(t->node(), &i)) {
00248
00249 } else if (isFloat(t->node(), &x)) {
00250 i = int(x);
00251 } else {
00252 ERROR("the node of the tree is not an int nor a float", t);
00253 }
00254 return i;
00255 }
00256
00257
00258 float tree2float (Tree t)
00259 {
00260 float x;
00261 int i;
00262
00263 if (isInt(t->node(), &i)) {
00264 x = float(i);
00265 } else if (isFloat(t->node(), &x)) {
00266
00267 } else {
00268 ERROR("the node of the tree is not a float nor an int", t);
00269 }
00270 return x;
00271 }
00272
00273
00274 const char* tree2str (Tree t)
00275 {
00276 Sym s;
00277 if (!isSym(t->node(), &s)) {
00278 ERROR("the node of the tree is not a symbol", t);
00279 }
00280 return name(s);
00281 }
00282
00283
00284 void* tree2ptr (Tree t)
00285 {
00286 void* x;
00287 if (! isPointer(t->node(), &x)) {
00288 ERROR("the node of the tree is not a pointer", t);
00289 }
00290 return x;
00291 }
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301 bool isTree (const Tree& t, const Node& n)
00302 {
00303 return (t->node() == n);
00304 }
00305
00306 bool isTree (const Tree& t, const Node& n, Tree& a)
00307 {
00308 if ((t->node() == n) && (t->arity() == 1)) {
00309 a=t->branch(0);
00310 return true;
00311 } else {
00312 return false;
00313 }
00314 }
00315
00316 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b)
00317 {
00318 if ((t->node() == n) && (t->arity() == 2)) {
00319 a=t->branch(0);
00320 b=t->branch(1);
00321 return true;
00322 } else {
00323 return false;
00324 }
00325 }
00326
00327 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c)
00328 {
00329 if ((t->node() == n) && (t->arity() == 3)) {
00330 a=t->branch(0);
00331 b=t->branch(1);
00332 c=t->branch(2);
00333 return true;
00334 } else {
00335 return false;
00336 }
00337 }
00338
00339 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d)
00340 {
00341 if ((t->node() == n) && (t->arity() == 4)) {
00342 a=t->branch(0);
00343 b=t->branch(1);
00344 c=t->branch(2);
00345 d=t->branch(3);
00346 return true;
00347 } else {
00348 return false;
00349 }
00350 }
00351
00352 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e)
00353 {
00354 if ((t->node() == n) && (t->arity() == 5)) {
00355 a=t->branch(0);
00356 b=t->branch(1);
00357 c=t->branch(2);
00358 d=t->branch(3);
00359 e=t->branch(4);
00360 return true;
00361 } else {
00362 return false;
00363 }
00364 }
00365
00366
00367
00368 void* getUserData(Tree t)
00369 {
00370 Sym s;
00371 if (isSym(t->node(), &s)) {
00372 return getUserData(s);
00373 } else {
00374 return 0;
00375 }
00376 }
00377