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

#include <tree.hh>

Collaboration diagram for CTree:

Public Member Functions
	~CTree ()

const Node &	node () const
	return the content of the tree More...

int	arity () const
	return the number of branches (subtrees) of a tree More...

Tree	branch (int i) const
	return the ith branch (subtree) of a tree More...

const tvec &	branches () const
	return all branches (subtrees) of a tree More...

unsigned int	hashkey () const
	return the hashkey of the tree More...

int	aperture () const
	return how "open" is a tree in terms of free variables More...

void	setAperture (int a)
	modify the aperture of a tree More...

ostream &	print (ostream &fout) const
	print recursively the content of a tree on a stream More...

void	setType (void *t)

void *	getType ()

bool	isAlreadyVisited ()

void	setVisited ()

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 More...

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 More...

static Tree	make (const Node &n, const tvec &br)
	return a new tree or an existing equivalent one More...

static void	control ()
	print the hash table content (for debug purpose) More...

static void	startNewVisit ()

Static Public Attributes
static bool	gDetails = false
	Ctree::print() print with more details when true. More...

static unsigned int	gVisitTime = 0
	Should be incremented for each new visit to keep track of visited tree. More...

Private Member Functions
	CTree (unsigned int hk, const Node &n, const tvec &br)
	construction is private, uses tree::make instead More...

bool	equiv (const Node &n, const tvec &br) const
	used to check if an equivalent tree already exists More...

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 More...

static int	calcTreeAperture (const Node &n, const tvec &br)
	compute how open is a tree More...

Private Attributes
Tree	fNext
	next tree in the same hashtable entry More...

Node	fNode
	the node content of the tree More...

void *	fType
	the type of a tree More...

plist	fProperties
	the properties list attached to the tree More...

unsigned int	fHashKey
	the hashtable key More...

int	fAperture
	how "open" is a tree (synthezised field) More...

unsigned int	fVisitTime
	keep track of visits More...

tvec	fBranch
	the subtrees More...

Static Private Attributes
static const int	kHashTableSize = 2000000

static Tree	gHashTable [kHashTableSize]
	hash table used for "hash consing" More...

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 104 of file tree.cpp.

References fNext, gHashTable, and kHashTableSize.

Referenced by make().

     :   fNode(n), 
         fType(0),
         fHashKey(hk), 
         fAperture(calcTreeAperture(n,br)), 
         fVisitTime(0),
         fBranch(br) 
 { 
     // link dans la hash table
     int j = hk % kHashTableSize;
     fNext = gHashTable[j];
     gHashTable[j] = this;
 
 }

Here is the caller graph for this function:

CTree::~CTree ( )

Definition at line 120 of file tree.cpp.

References fHashKey, fNext, gHashTable, and kHashTableSize.

 {
     int     i = fHashKey % kHashTableSize;
     Tree    t = gHashTable[i];
     
     //printf("Delete of "); this->print(); printf("\n");
     if (t == this) {
         gHashTable[i] = fNext;
     } else {
         Tree p;
         while (t != this) {
             p = t;
             t = t->fNext;
         }
         p->fNext = fNext;
     }
 }

Member Function Documentation

int CTree::aperture ( ) const

inline

return how "open" is a tree in terms of free variables

Definition at line 148 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

return the number of branches (subtrees) of a tree

Definition at line 144 of file tree.hh.

References fBranch.

Referenced by annotate(), calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), Occurrences::countOccurrences(), ScalarCompiler::declareWaveform(), ScalarCompiler::generateXtended(), DocCompiler::generateXtended(), getSubSignals(), infereSigOrder(), infereWaveformType(), infereXType(), isList(), isNil(), isTree(), markOpen(), boxpp::print(), print(), print(), ppsig::printextended(), privatisation(), real_a2sb(), recomputeAperture(), sigMap(), sigMapRename(), simplification(), subst(), and tmap().

Here is the caller graph for this function:

Tree CTree::branch ( int i ) const

inline

return the ith branch (subtree) of a tree

Definition at line 145 of file tree.hh.

References fBranch.

Referenced by annotate(), calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), copyEnvReplaceDefs(), Occurrences::countOccurrences(), ScalarCompiler::declareWaveform(), evalIdDef(), ffincfile(), fflibfile(), ffsignature(), ScalarCompiler::generateXtended(), DocCompiler::generateXtended(), getSubSignals(), hd(), infereSigOrder(), infereWaveformType(), infereXType(), isSigPow(), isTree(), left(), markOpen(), boxpp::print(), print(), print(), printdoccontent(), ppsig::printextended(), real_a2sb(), recomputeAperture(), right(), searchIdDef(), sigMap(), sigMapRename(), simplification(), subst(), tl(), tmap(), and uiLabel().

Here is the caller graph for this function:

const tvec& CTree::branches ( ) const

inline

return all branches (subtrees) of a tree

Definition at line 146 of file tree.hh.

References fBranch.

Referenced by getSubSignals(), and realPropagate().

Here is the caller graph for this function:

int CTree::calcTreeAperture	(	const Node &	n,
		const tvec &	br
	)

staticprivate

compute how open is a tree

Definition at line 121 of file recursive-tree.cpp.

References isInt(), and node().

 {
     int x;
     if (n == DEBRUIJNREF) {
 
         if (isInt(br[0]->node(), &x)) {
             return x;
         } else {
             return 0;
         }
 
     } else if (n == DEBRUIJN) {
 
         return br[0]->fAperture - 1;
 
     } else {
         // return max aperture of branches
         int rc = 0;
         tvec::const_iterator    b = br.begin();
         tvec::const_iterator    z = br.end();
         while (b != z) {
             if ((*b)->aperture() > rc) rc = (*b)->aperture();
             ++b;
         }
         return rc;
     }
 }

Here is the call graph for this function:

unsigned int CTree::calcTreeHash	(	const Node &	n,
		const tvec &	br
	)

staticprivate

compute the hash key of a tree according to its node and branches

Definition at line 149 of file tree.cpp.

References Node::getInt(), and Node::type().

Referenced by make().

 {
     unsigned int            hk = n.type() ^ n.getInt();
     tvec::const_iterator  b = br.begin();
     tvec::const_iterator  z = br.end();
     
     while (b != z) {
         hk = (hk << 1) ^ (hk >> 20) ^ ((*b)->fHashKey);
         ++b;
     }
     return hk;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void CTree::clearProperties ( )

inline

Definition at line 169 of file tree.hh.

References fProperties.

169 { fProperties = plist(); }

plist

map< Tree, Tree > plist

Definition: tree.hh:89

CTree::fProperties

plist fProperties

the properties list attached to the tree

Definition: tree.hh:124

void CTree::clearProperty ( Tree key )

inline

Definition at line 168 of file tree.hh.

References fProperties.

Referenced by property< Loop * >::clear(), property< Tree >::clear(), property< int >::clear(), and property< double >::clear().

168 { fProperties.erase(key); }

CTree::fProperties

plist fProperties

the properties list attached to the tree

Definition: tree.hh:124

Here is the caller graph for this function:

void CTree::control ( )

static

print the hash table content (for debug purpose)

Definition at line 210 of file tree.cpp.

References fNext, gHashTable, and kHashTableSize.

 {
     printf("\ngHashTable Content :\n\n");
     for (int i = 0; i < kHashTableSize; i++) {
         Tree t = gHashTable[i];
         if (t) {
             printf ("%4d = ", i);
             while (t) {
                 /*t->print();*/
                 printf(" => ");
                 t = t->fNext;
             }
             printf("VOID\n");
         }
     }
     printf("\nEnd gHashTable\n");
 
 }

bool CTree::equiv	(	const Node &	n,
		const tvec &	br
	)		const

private

used to check if an equivalent tree already exists

Definition at line 139 of file tree.cpp.

References fBranch, and fNode.

Referenced by make().

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

Here is the caller graph for this function:

void CTree::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

Definition at line 388 of file tree.cpp.

References fProperties.

Referenced by copyEnvReplaceDefs().

 {
     for (plist::const_iterator p = fProperties.begin(); p != fProperties.end(); p++) {
         keys.push_back(p->first);
         values.push_back(p->second);
     }
 }

Here is the caller graph for this function:

Tree CTree::getProperty ( Tree key )

inline

Definition at line 173 of file tree.hh.

References fProperties.

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

                                       {
         plist::iterator i = fProperties.find(key);
         if (i==fProperties.end()) {
             return 0;
         } else {
             return i->second;
         }
     }

Here is the caller graph for this function:

void* CTree::getType ( )

inline

Definition at line 158 of file tree.hh.

References fType.

Referenced by getSigType().

158 { return fType; }

CTree::fType

void * fType

the type of a tree

Definition: tree.hh:123

Here is the caller graph for this function:

unsigned int CTree::hashkey ( ) const

inline

return the hashkey of the tree

Definition at line 147 of file tree.hh.

References fHashKey.

bool CTree::isAlreadyVisited ( )

inline

Definition at line 162 of file tree.hh.

References fVisitTime, and gVisitTime.

Referenced by T().

162 { return fVisitTime==gVisitTime; }

CTree::fVisitTime

unsigned int fVisitTime

keep track of visits

Definition: tree.hh:127

CTree::gVisitTime

static unsigned int gVisitTime

Should be incremented for each new visit to keep track of visited tree.

Definition: tree.hh:117

Here is the caller 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(), codeSimpleType(), codeTupletType(), real_a2sb(), and tree().

Here is the caller graph for this function:

Tree CTree::make	(	const Node &	n,
		const tvec &	br
	)

static

return a new tree or an existing equivalent one

Definition at line 179 of file tree.cpp.

References calcTreeHash(), CTree(), equiv(), fNext, gHashTable, and kHashTableSize.

 {
     unsigned int    hk  = calcTreeHash(n, br);
     Tree    t = gHashTable[hk % kHashTableSize];
     
     while (t && !t->equiv(n, br)) {
         t = t->fNext;
     }
     return (t) ? t : new CTree(hk, n, br);
 }

Here is the call graph for this function:

const Node& CTree::node ( ) const

inline

return the content of the tree

Definition at line 143 of file tree.hh.

References fNode.

Referenced by property< Loop * >::access(), addNums(), calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), calcTreeAperture(), computePrivatisation(), divExtendedNums(), property< int >::get(), property< double >::get(), getBoxType(), Occurrences::getCount(), getDefLineProp(), ScalarCompiler::getSharingCount(), DocCompiler::getSharingCount(), getUserData(), infereWaveformType(), inverseNum(), isBefore(), isBoxAbstr(), isBoxAppl(), isBoxIdent(), isBoxInt(), isBoxPatternOp(), isBoxPrim0(), isBoxPrim1(), isBoxPrim2(), isBoxPrim3(), isBoxPrim4(), isBoxPrim5(), isBoxReal(), isBoxSlot(), isDocTxt(), isEnvBarrier(), 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 190 of file tree.cpp.

References arity(), branch(), gDetails, node(), and print().

Referenced by operator<<(), and print().

 {
     if (gDetails) {
         // print the adresse of the tree
         fout << "<" << this << ">@"; 
     }
     fout << node();
     int a = arity();
     if (a > 0) {
         int i; char sep;
         for (sep = '[', i = 0; i < a; sep = ',', i++) {
             fout << sep; branch(i)->print(fout); 
         }
         fout << ']';
     } 
     
     return fout;
 }