CTree Class Reference

A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches. More...

#include <tree.hh>

Collaboration diagram for CTree:
[legend]

List of all members.

Public Member Functions

 ~CTree ()
const Nodenode () 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)
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"

Detailed Description

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.


Constructor & Destructor Documentation

CTree::CTree ( unsigned int  hk,
const Node n,
const tvec br 
) [private]

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 }

Here is the caller graph for this function:

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 }


Member Function Documentation

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().

Here is the caller graph for this function:

int CTree::arity (  )  const [inline]
Tree CTree::branch ( int  i  )  const [inline]
int CTree::calcTreeAperture ( const Node n,
const tvec br 
) [static, private]

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 }

Here is the call graph for this function:

unsigned int CTree::calcTreeHash ( const Node n,
const tvec br 
) [static, private]

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

void CTree::clearProperty ( Tree  key  )  [inline]

Definition at line 159 of file tree.hh.

References fProperties.

00159 { fProperties.erase(key); }

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 }

bool CTree::equiv ( const Node n,
const tvec br 
) const [private]

used to check if an equivalent tree already exists

Definition at line 137 of file tree.cpp.

References fBranch, and fNode.

Referenced by make().

00138 {
00139     return (fNode == n) && (fBranch == br);
00140 }

Here is the caller graph for this function:

Tree CTree::getProperty ( Tree  key  )  [inline]

Definition at line 160 of file tree.hh.

References fProperties.

Referenced by property< Loop * >::access(), boxComplexity(), deBruijn2Sym(), OccMarkup::getOcc(), getProperty(), isRec(), liftn(), and substitute().

00160                                       {
00161         plist::iterator i = fProperties.find(key);
00162         if (i==fProperties.end()) {
00163             return 0;
00164         } else {
00165             return i->second;
00166         }
00167     }

Here is the caller graph for this function:

void* CTree::getType (  )  [inline]

Definition at line 155 of file tree.hh.

References fType.

Referenced by getInferredType(), and getSigType().

00155 { return fType; }

Here is the caller graph for this function:

unsigned int CTree::hashkey (  )  const [inline]

return the hashkey of the tree

Definition at line 144 of file tree.hh.

References fHashKey.

Tree CTree::make ( const Node n,
const tvec br 
) [static]

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 }

Here is the call graph for this function:

static Tree CTree::make ( const Node n,
int  ar,
Tree  br[] 
) [static]

return a new tree or an existing equivalent one

Referenced by calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), real_a2sb(), and tree().

Here is the caller graph for this function:

const Node& CTree::node (  )  const [inline]
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 }

Here is the call graph for this function:

Here is the caller graph for this function:

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().

Here is the caller graph for this function:

void CTree::setProperty ( Tree  key,
Tree  value 
) [inline]

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; }

Here is the caller graph for this function:

void CTree::setType ( void *  t  )  [inline]

Definition at line 154 of file tree.hh.

References fType.

Referenced by setSigType().

00154 { fType = t; }

Here is the caller graph for this function:


Member Data Documentation

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]

the subtrees

Definition at line 126 of file tree.hh.

Referenced by arity(), branch(), and equiv().

unsigned int CTree::fHashKey [private]

the hashtable key

Definition at line 124 of file tree.hh.

Referenced by hashkey(), and ~CTree().

Tree CTree::fNext [private]

next tree in the same hashtable entry

Definition at line 120 of file tree.hh.

Referenced by control(), CTree(), make(), and ~CTree().

Node CTree::fNode [private]

the node content of the tree

Definition at line 121 of file tree.hh.

Referenced by equiv(), and node().

the properties list attached to the tree

Definition at line 123 of file tree.hh.

Referenced by clearProperty(), getProperty(), and setProperty().

void* CTree::fType [private]

the type of a tree

Definition at line 122 of file tree.hh.

Referenced by getType(), and setType().

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]

hash table used for "hash consing"

Definition at line 113 of file tree.hh.

Referenced by control(), CTree(), make(), and ~CTree().

const int CTree::kHashTableSize = 2000000 [static, private]

Definition at line 112 of file tree.hh.

Referenced by control(), CTree(), make(), and ~CTree().


The documentation for this class was generated from the following files:
Generated on Thu Apr 29 00:00:18 2010 for FAUST compiler by  doxygen 1.6.3