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 <stdlib.h>
00079 #include <stdio.h>
00080 #include <string.h>
00081 #include <limits.h>
00082 #include "tree.hh"
00083 #include <fstream>
00084 #include <cstdlib>
00085
00086 Tabber TABBER(1);
00087 extern Tabber TABBER;
00088
00089
00090 static void error(const char * s, Tree t)
00091 {
00092
00093 cerr << "ERROR : " << s << " : " << *t << endl;
00094 }
00095
00096 #define ERROR(s,t) { error(s,t); exit(1); }
00097
00098
00099 Tree CTree::gHashTable[kHashTableSize];
00100 bool CTree::gDetails = false;
00101
00102
00103 CTree::CTree (unsigned int hk, const Node& n, const tvec& br)
00104 : fNode(n),
00105 fType(0),
00106 fHashKey(hk),
00107 fAperture(calcTreeAperture(n,br)),
00108 fBranch(br)
00109 {
00110
00111 int j = hk % kHashTableSize;
00112 fNext = gHashTable[j];
00113 gHashTable[j] = this;
00114
00115 }
00116
00117
00118 CTree::~CTree ()
00119 {
00120 int i = fHashKey % kHashTableSize;
00121 Tree t = gHashTable[i];
00122
00123
00124 if (t == this) {
00125 gHashTable[i] = fNext;
00126 } else {
00127 Tree p;
00128 while (t != this) {
00129 p = t;
00130 t = t->fNext;
00131 }
00132 p->fNext = fNext;
00133 }
00134 }
00135
00136
00137 bool CTree::equiv (const Node& n, const tvec& br) const
00138 {
00139 return (fNode == n) && (fBranch == br);
00140 }
00141
00142 Sym PROCESS = symbol("process");
00143
00144
00145
00146
00147 unsigned int CTree::calcTreeHash( const Node& n, const tvec& br )
00148 {
00149 unsigned int hk = n.type() ^ n.getInt();
00150 tvec::const_iterator b = br.begin();
00151 tvec::const_iterator z = br.end();
00152
00153 while (b != z) {
00154 hk = (hk << 1) ^ (hk >> 20) ^ ((*b)->fHashKey);
00155 ++b;
00156 }
00157 return hk;
00158 }
00159
00160
00161 Tree CTree::make(const Node& n, int ar, Tree* tbl)
00162 {
00163 tvec br(ar);
00164
00165 for (int i=0; i<ar; i++) br[i] = tbl[i];
00166
00167 unsigned int hk = calcTreeHash(n, br);
00168 Tree t = gHashTable[hk % kHashTableSize];
00169
00170 while (t && !t->equiv(n, br)) {
00171 t = t->fNext;
00172 }
00173 return (t) ? t : new CTree(hk, n, br);
00174 }
00175
00176
00177 Tree CTree::make(const Node& n, const tvec& br)
00178 {
00179 unsigned int hk = calcTreeHash(n, br);
00180 Tree t = gHashTable[hk % kHashTableSize];
00181
00182 while (t && !t->equiv(n, br)) {
00183 t = t->fNext;
00184 }
00185 return (t) ? t : new CTree(hk, n, br);
00186 }
00187
00188 ostream& CTree::print (ostream& fout) const
00189 {
00190 if (gDetails) {
00191
00192 fout << "<" << this << ">@";
00193 }
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210 fout << node();
00211 int a = arity();
00212 if (a > 0) {
00213 int i; char sep;
00214 for (sep = '[', i = 0; i < a; sep = ',', i++) {
00215 fout << sep; branch(i)->print(fout);
00216 }
00217 fout << ']';
00218 }
00219
00220 return fout;
00221 }
00222
00223
00224 void CTree::control ()
00225 {
00226 printf("\ngHashTable Content :\n\n");
00227 for (int i = 0; i < kHashTableSize; i++) {
00228 Tree t = gHashTable[i];
00229 if (t) {
00230 printf ("%4d = ", i);
00231 while (t) {
00232
00233 printf(" => ");
00234 t = t->fNext;
00235 }
00236 printf("VOID\n");
00237 }
00238 }
00239 printf("\nEnd gHashTable\n");
00240
00241 }
00242
00243
00244 int tree2int (Tree t)
00245 {
00246 double x;
00247 int i;
00248
00249 if (isInt(t->node(), &i)) {
00250
00251 } else if (isDouble(t->node(), &x)) {
00252 i = int(x);
00253 } else {
00254 ERROR("the node of the tree is not an int nor a float", t);
00255 }
00256 return i;
00257 }
00258
00259
00260 double tree2float (Tree t)
00261 {
00262 double x;
00263 int i;
00264
00265 if (isInt(t->node(), &i)) {
00266 x = double(i);
00267 } else if (isDouble(t->node(), &x)) {
00268
00269 } else {
00270 ERROR("the node of the tree is not a float nor an int", t);
00271 }
00272 return x;
00273 }
00274
00275
00276 double tree2double (Tree t)
00277 {
00278 double x;
00279 int i;
00280
00281 if (isInt(t->node(), &i)) {
00282 x = double(i);
00283 } else if (isDouble(t->node(), &x)) {
00284
00285 } else {
00286 ERROR("the node of the tree is not a float nor an int", t);
00287 }
00288 return double(x);
00289 }
00290
00291
00292 const char* tree2str (Tree t)
00293 {
00294 Sym s;
00295 if (!isSym(t->node(), &s)) {
00296 ERROR("the node of the tree is not a symbol", t);
00297 }
00298 return name(s);
00299 }
00300
00301
00302 void* tree2ptr (Tree t)
00303 {
00304 void* x;
00305 if (! isPointer(t->node(), &x)) {
00306 ERROR("the node of the tree is not a pointer", t);
00307 }
00308 return x;
00309 }
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319 bool isTree (const Tree& t, const Node& n)
00320 {
00321 return (t->node() == n);
00322 }
00323
00324 bool isTree (const Tree& t, const Node& n, Tree& a)
00325 {
00326 if ((t->node() == n) && (t->arity() == 1)) {
00327 a=t->branch(0);
00328 return true;
00329 } else {
00330 return false;
00331 }
00332 }
00333
00334 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b)
00335 {
00336 if ((t->node() == n) && (t->arity() == 2)) {
00337 a=t->branch(0);
00338 b=t->branch(1);
00339 return true;
00340 } else {
00341 return false;
00342 }
00343 }
00344
00345 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c)
00346 {
00347 if ((t->node() == n) && (t->arity() == 3)) {
00348 a=t->branch(0);
00349 b=t->branch(1);
00350 c=t->branch(2);
00351 return true;
00352 } else {
00353 return false;
00354 }
00355 }
00356
00357 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d)
00358 {
00359 if ((t->node() == n) && (t->arity() == 4)) {
00360 a=t->branch(0);
00361 b=t->branch(1);
00362 c=t->branch(2);
00363 d=t->branch(3);
00364 return true;
00365 } else {
00366 return false;
00367 }
00368 }
00369
00370 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e)
00371 {
00372 if ((t->node() == n) && (t->arity() == 5)) {
00373 a=t->branch(0);
00374 b=t->branch(1);
00375 c=t->branch(2);
00376 d=t->branch(3);
00377 e=t->branch(4);
00378 return true;
00379 } else {
00380 return false;
00381 }
00382 }
00383
00384
00385
00386 void* getUserData(Tree t)
00387 {
00388 Sym s;
00389 if (isSym(t->node(), &s)) {
00390 return getUserData(s);
00391 } else {
00392 return 0;
00393 }
00394 }
00395
00396
00402 void CTree::exportProperties(vector<Tree>& keys, vector<Tree>& values)
00403 {
00404 for (plist::const_iterator p = fProperties.begin(); p != fProperties.end(); p++) {
00405 keys.push_back(p->first);
00406 values.push_back(p->second);
00407 }
00408 }
00409