A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches. More...
#include <tree.hh>
Public Member Functions | |
~CTree () | |
const Node & | node () const |
return the content of the tree | |
int | arity () const |
return the number of branches (subtrees) of a tree | |
Tree | branch (int i) const |
return the ith branch (subtree) of a tree | |
unsigned int | hashkey () const |
return the hashkey of the tree | |
int | aperture () const |
return how "open" is a tree in terms of free variables | |
void | setAperture (int a) |
modify the aperture of a tree | |
ostream & | print (ostream &fout) const |
print recursively the content of a tree on a stream | |
void | setType (void *t) |
void * | getType () |
void | setProperty (Tree key, Tree value) |
void | clearProperty (Tree key) |
void | clearProperties () |
void | exportProperties (vector< Tree > &keys, vector< Tree > &values) |
export the properties of a CTree as two vectors, one for the keys and one for the associated values | |
Tree | getProperty (Tree key) |
Static Public Member Functions | |
static Tree | make (const Node &n, int ar, Tree br[]) |
return a new tree or an existing equivalent one | |
static Tree | make (const Node &n, const tvec &br) |
return a new tree or an existing equivalent one | |
static void | control () |
print the hash table content (for debug purpose) | |
Static Public Attributes | |
static bool | gDetails = false |
Ctree::print() print with more details when true. | |
Private Member Functions | |
CTree (unsigned int hk, const Node &n, const tvec &br) | |
construction is private, uses tree::make instead | |
bool | equiv (const Node &n, const tvec &br) const |
used to check if an equivalent tree already exists | |
Static Private Member Functions | |
static unsigned int | calcTreeHash (const Node &n, const tvec &br) |
compute the hash key of a tree according to its node and branches | |
static int | calcTreeAperture (const Node &n, const tvec &br) |
compute how open is a tree | |
Private Attributes | |
Tree | fNext |
next tree in the same hashtable entry | |
Node | fNode |
the node content of the tree | |
void * | fType |
the type of a tree | |
plist | fProperties |
the properties list attached to the tree | |
unsigned int | fHashKey |
the hashtable key | |
int | fAperture |
how "open" is a tree (synthezised field) | |
tvec | fBranch |
the subtrees | |
Static Private Attributes | |
static const int | kHashTableSize = 2000000 |
static Tree | gHashTable [kHashTableSize] |
hash table used for "hash consing" |
A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches.
A CTree = (Node x [CTree]) is the association of a content Node and a list of subtrees called branches. In order to maximize the sharing of trees, hashconsing techniques are used. Ctrees at different addresses always have a different content. A first consequence of this approach is that a fast equality test on pointers can be used as an equality test on CTrees. A second consequence is that a CTree can NEVER be modified. But a property list is associated to each CTree that can be used to attach arbitrary information to it. Due to the maximal sharing property it is therefore easy to do memoization using these property lists.
Means are also provided to do maximal sharing on recursive trees. The idea is to start from a deBruijn representation and progressively build a classical representation such that alpha-equivalent recursive CTrees are necesseraly identical (and therefore shared).
WARNING : in the current implementation CTrees are allocated but never deleted
Definition at line 109 of file tree.hh.
construction is private, uses tree::make instead
Definition at line 103 of file tree.cpp.
References fNext, gHashTable, and kHashTableSize.
Referenced by make().
00104 : fNode(n), 00105 fType(0), 00106 fHashKey(hk), 00107 fAperture(calcTreeAperture(n,br)), 00108 fBranch(br) 00109 { 00110 // link dans la hash table 00111 int j = hk % kHashTableSize; 00112 fNext = gHashTable[j]; 00113 gHashTable[j] = this; 00114 00115 }
CTree::~CTree | ( | ) |
Definition at line 118 of file tree.cpp.
References fHashKey, fNext, gHashTable, and kHashTableSize.
00119 { 00120 int i = fHashKey % kHashTableSize; 00121 Tree t = gHashTable[i]; 00122 00123 //printf("Delete of "); this->print(); printf("\n"); 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 }
int CTree::aperture | ( | ) | const [inline] |
return how "open" is a tree in terms of free variables
Definition at line 145 of file tree.hh.
References fAperture.
Referenced by calcsubstitute(), isClosed(), isOpen(), markOpen(), and recomputeAperture().
int CTree::arity | ( | ) | const [inline] |
return the number of branches (subtrees) of a tree
Definition at line 142 of file tree.hh.
References fBranch.
Referenced by annotate(), calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), Occurrences::countOccurrences(), DocCompiler::generateXtended(), ScalarCompiler::generateXtended(), getSubSignals(), infereSigOrder(), infereXType(), isList(), isNil(), isTree(), markOpen(), print(), print(), ppsig::printextended(), privatisation(), real_a2sb(), recomputeAperture(), sigMap(), sigMapRename(), simplification(), subst(), and tmap().
Tree CTree::branch | ( | int | i | ) | const [inline] |
return the ith branch (subtree) of a tree
Definition at line 143 of file tree.hh.
References fBranch.
Referenced by annotate(), calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), copyEnvReplaceDefs(), Occurrences::countOccurrences(), evalIdDef(), ffincfile(), fflibfile(), ffsignature(), DocCompiler::generateXtended(), ScalarCompiler::generateXtended(), getSubSignals(), hd(), infereSigOrder(), infereXType(), isSigPow(), isTree(), left(), markOpen(), print(), print(), printdoccontent(), ppsig::printextended(), real_a2sb(), recomputeAperture(), right(), searchIdDef(), sigMap(), sigMapRename(), simplification(), subst(), tl(), tmap(), and uiLabel().
compute how open is a tree
Definition at line 121 of file recursive-tree.cpp.
References isInt(), and node().
00122 { 00123 int x; 00124 if (n == DEBRUIJNREF) { 00125 00126 if (isInt(br[0]->node(), &x)) { 00127 return x; 00128 } else { 00129 return 0; 00130 } 00131 00132 } else if (n == DEBRUIJN) { 00133 00134 return br[0]->fAperture - 1; 00135 00136 } else { 00137 // return max aperture of branches 00138 int rc = 0; 00139 tvec::const_iterator b = br.begin(); 00140 tvec::const_iterator z = br.end(); 00141 while (b != z) { 00142 if ((*b)->aperture() > rc) rc = (*b)->aperture(); 00143 ++b; 00144 } 00145 return rc; 00146 } 00147 }
compute the hash key of a tree according to its node and branches
Definition at line 147 of file tree.cpp.
References Node::getInt(), and Node::type().
Referenced by make().
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 }
void CTree::clearProperties | ( | ) | [inline] |
void CTree::clearProperty | ( | Tree | key | ) | [inline] |
void CTree::control | ( | ) | [static] |
print the hash table content (for debug purpose)
Definition at line 224 of file tree.cpp.
References fNext, gHashTable, and kHashTableSize.
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 /*t->print();*/ 00233 printf(" => "); 00234 t = t->fNext; 00235 } 00236 printf("VOID\n"); 00237 } 00238 } 00239 printf("\nEnd gHashTable\n"); 00240 00241 }
export the properties of a CTree as two vectors, one for the keys and one for the associated values
Definition at line 402 of file tree.cpp.
References fProperties.
Referenced by copyEnvReplaceDefs().
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 }
Definition at line 164 of file tree.hh.
References fProperties.
Referenced by property< Loop * >::access(), boxComplexity(), deBruijn2Sym(), OccMarkup::getOcc(), getProperty(), isRec(), liftn(), and substitute().
00164 { 00165 plist::iterator i = fProperties.find(key); 00166 if (i==fProperties.end()) { 00167 return 0; 00168 } else { 00169 return i->second; 00170 } 00171 }
void* CTree::getType | ( | ) | [inline] |
Definition at line 155 of file tree.hh.
References fType.
Referenced by getInferredType(), and getSigType().
00155 { return fType; }
unsigned int CTree::hashkey | ( | ) | const [inline] |
return a new tree or an existing equivalent one
Definition at line 177 of file tree.cpp.
References calcTreeHash(), CTree(), equiv(), fNext, gHashTable, and kHashTableSize.
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 }
return a new tree or an existing equivalent one
Referenced by calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), real_a2sb(), and tree().
const Node& CTree::node | ( | ) | const [inline] |
return the content of the tree
Definition at line 141 of file tree.hh.
References fNode.
Referenced by property< Loop * >::access(), addNums(), calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), calcTreeAperture(), computePrivatisation(), divExtendedNums(), divNums(), getBoxType(), Occurrences::getCount(), getDefLineProp(), ScalarCompiler::getSharingCount(), DocCompiler::getSharingCount(), getUserData(), inverseNum(), isBefore(), isBoxAbstr(), isBoxAppl(), isBoxIdent(), isBoxInt(), isBoxPatternOp(), isBoxPrim0(), isBoxPrim1(), isBoxPrim2(), isBoxPrim3(), isBoxPrim4(), isBoxPrim5(), isBoxReal(), isBoxSlot(), isDocTxt(), isffunction(), isGEZero(), isGTZero(), isList(), isMinusOne(), isNil(), isNum(), isOne(), isProj(), isRef(), isSigBinOp(), isSigGen(), isSigInput(), isSigInt(), isSigOutput(), isSigReal(), isSigTuple(), isTree(), isZero(), minusNum(), mulNums(), normalizeLabel(), print(), print(), real_a2sb(), shcount(), sigFloatCast(), sigIntCast(), sigMap(), sigMapRename(), simplification(), subNums(), subst(), tmap(), tree2double(), tree2float(), tree2int(), tree2ptr(), and tree2str().
ostream & CTree::print | ( | ostream & | fout | ) | const |
print recursively the content of a tree on a stream
Definition at line 188 of file tree.cpp.
References arity(), branch(), gDetails, node(), and print().
Referenced by operator<<(), and print().
00189 { 00190 if (gDetails) { 00191 // print the adresse of the tree 00192 fout << "<" << this << ">@"; 00193 } 00194 /* 00195 switch (node().type()) { 00196 case kIntNode : 00197 fout << node().getInt(); 00198 break; 00199 case kFloatNode : 00200 fout << node().getFloat(); 00201 break; 00202 case kSymNode : 00203 fout << name(node().getSym()); 00204 break; 00205 case kPointerNode : 00206 fout << node().getPointer(); 00207 break; 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 }
void CTree::setAperture | ( | int | a | ) | [inline] |
modify the aperture of a tree
Definition at line 146 of file tree.hh.
References fAperture.
Referenced by markOpen(), and recomputeAperture().
Definition at line 158 of file tree.hh.
References fProperties.
Referenced by boxComplexity(), deBruijn2Sym(), liftn(), rec(), OccMarkup::setOcc(), setProperty(), and substitute().
00158 { fProperties[key] = value; }
void CTree::setType | ( | void * | t | ) | [inline] |
Definition at line 154 of file tree.hh.
References fType.
Referenced by setSigType().
00154 { fType = t; }
int CTree::fAperture [private] |
how "open" is a tree (synthezised field)
Definition at line 125 of file tree.hh.
Referenced by aperture(), and setAperture().
tvec CTree::fBranch [private] |
unsigned int CTree::fHashKey [private] |
Tree CTree::fNext [private] |
Node CTree::fNode [private] |
plist CTree::fProperties [private] |
the properties list attached to the tree
Definition at line 123 of file tree.hh.
Referenced by clearProperties(), clearProperty(), exportProperties(), getProperty(), and setProperty().
void* CTree::fType [private] |
bool CTree::gDetails = false [static] |
Ctree::print() print with more details when true.
Definition at line 116 of file tree.hh.
Referenced by print().
Tree CTree::gHashTable [static, private] |
const int CTree::kHashTableSize = 2000000 [static, private] |