CTree Class Reference

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

#include <tree.hh>

List of all members.

Public Member Functions

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

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 = 510511
 size of the hash table used for "hash consing"
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.


The documentation for this class was generated from the following files:

Generated on Sat Jul 25 12:28:17 2009 for FAUST compiler by  doxygen 1.5.9