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
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 ()
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
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 void	startNewVisit ()
Static Public Attributes
static bool	gDetails = false
	Ctree::print() print with more details when true.
static unsigned int	gVisitTime = 0
	Should be incremented for each new visit to keep track of visited tree.
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)
unsigned int	fVisitTime
	keep track of visits
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 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 147 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::generateXtended(), DocCompiler::generateXtended(), getSubSignals(), infereSigOrder(), infereXType(), isList(), isNil(), isTree(), markOpen(), 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(), evalIdDef(), ffincfile(), fflibfile(), ffsignature(), ScalarCompiler::generateXtended(), DocCompiler::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().

Here is the caller graph for this function:

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

{
    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
	)		`[static, private]`

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 168 of file tree.hh.

References fProperties.

{ fProperties = plist(); }

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

Definition at line 167 of file tree.hh.

References fProperties.

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

{ fProperties.erase(key); }

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 172 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 157 of file tree.hh.

References fType.

Referenced by getSigType().

{ 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 146 of file tree.hh.

References fHashKey.

bool CTree::isAlreadyVisited ( ) [inline]

Definition at line 161 of file tree.hh.

References fVisitTime, and gVisitTime.

Referenced by T().

{ return fVisitTime==gVisitTime; }

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(), divNums(), property< int >::get(), property< double >::get(), 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(), 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;
}

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 148 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 166 of file tree.hh.

References fProperties.

Referenced by boxComplexity(), deBruijn2Sym(), liftn(), rec(), property< Tree >::set(), property< int >::set(), property< double >::set(), OccMarkup::setOcc(), setProperty(), and substitute().

{ fProperties[key] = value; }

Here is the caller graph for this function:

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

Definition at line 156 of file tree.hh.

References fType.

Referenced by codeAudioType(), and setSigType().

{ fType = t; }

Here is the caller graph for this function:

void CTree::setVisited ( ) [inline]

Definition at line 162 of file tree.hh.

References fVisitTime, and gVisitTime.

Referenced by T().

{ /*assert(fVisitTime!=gVisitTime);*/ fVisitTime=gVisitTime; }

Here is the caller graph for this function:

static void CTree::startNewVisit ( ) [inline, static]

Definition at line 160 of file tree.hh.

References gVisitTime.

Referenced by typeAnnotation().

{ ++gVisitTime; }

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 126 of file tree.hh.

Referenced by aperture(), and setAperture().

tvec CTree::fBranch [private]

the subtrees

Definition at line 128 of file tree.hh.

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

unsigned int CTree::fHashKey [private]

the hashtable key

Definition at line 125 of file tree.hh.

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

Tree CTree::fNext [private]

next tree in the same hashtable entry

Definition at line 121 of file tree.hh.

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

Node CTree::fNode [private]

the node content of the tree

Definition at line 122 of file tree.hh.

Referenced by equiv(), and node().

plist CTree::fProperties [private]

the properties list attached to the tree

Definition at line 124 of file tree.hh.

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

void* CTree::fType [private]

the type of a tree

Definition at line 123 of file tree.hh.

Referenced by getType(), and setType().

unsigned int CTree::fVisitTime [private]

keep track of visits

Definition at line 127 of file tree.hh.

Referenced by isAlreadyVisited(), and setVisited().

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

unsigned int CTree::gVisitTime = 0 [static]

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

Definition at line 117 of file tree.hh.

Referenced by isAlreadyVisited(), setVisited(), and startNewVisit().

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:

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation