drlvm/modules/vm/src/main/native/jitrino/shared/shared/Tree.h

/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/**
 * @author Intel, Mikhail Y. Fursov
 *
 */

#ifndef _TREE_H_
#define _TREE_H_

#include "PrintDotFile.h"
#include "open/types.h"

#include <assert.h>
#include <string>

namespace Jitrino {

class Tree;

class TreeNode {
    friend class Tree;
public:
    TreeNode() : child(NULL), siblings(NULL), parent(NULL), preNum((U_32) -1), postNum((U_32) -1) {}
    void addChild(TreeNode* chd) {
        chd->parent = this;
        chd->siblings = child;
        child = chd;
    }

    virtual ~TreeNode() {}

    virtual void print(::std::ostream& os) { os << "T"; }
    virtual void printTag(::std::ostream& os) { print(os); }

    /**** utilities to print Dot files */

    virtual void printDotNodesInTreeNode(::std::ostream &os) { }

    void printDotTreeNode(::std::ostream& os) {
        printDotTreeNode(os,NULL);
    }

    void printDotTreeNode(::std::ostream& os, TreeNode *parent) {
        printTag(os);
        os << "[label= \""; 
        print(os);
        printDotNodesInTreeNode(os);
        os << "\"];";

        if (child != NULL)
            child->printDotTreeNode(os,this);
        if (siblings != NULL)
            siblings->printDotTreeNode(os,parent);

        // dump child and sibling edges
        if (child != NULL) {
            printTag(os);
            os << " -> "; child->printTag(os);
            os << ";" << ::std::endl;
        }
        if (siblings != NULL) {
            if (parent != NULL) {
                parent->printTag(os);
                os << " -> "; siblings->printTag(os);
                os << ";" << ::std::endl;
            }
        }
    }

    void printDotRank(::std::ostream &os) {
        // make all siblings are in the same rank
        if (siblings != NULL) {
            os << "{ rank = same; ";
            os << "\""; printTag(os); os << "\"; ";
            for (TreeNode* sb = siblings; sb != NULL; sb = sb->siblings) {
                os << "\""; sb->printTag(os); os << "\"; ";
            }
            os << "}" << ::std::endl;
        }

        // dump children's rank
        if (child != NULL)
            child->printDotRank(os);

        // dump rank of siblings' children
        for (TreeNode* sb = siblings; sb != NULL; sb = sb->siblings) {
            TreeNode *sibl = sb->child;
            if (sibl != NULL)
                sibl->printDotRank(os);
        }
    }

    void printIndentedNode(::std::ostream& os, const ::std::string& indentstr = "") {
        os << indentstr.c_str();
        print(os);
        os << ::std::endl;
        if(child) child->printIndentedNode(os, indentstr + "  ");
        if(siblings) siblings->printIndentedNode(os, indentstr);
    }

    U_32 getHeight() const {
        U_32 i = 0;
        if(child != NULL) {
            i = child->getHeight();

            for (TreeNode *siblings = child->siblings; siblings!=NULL; siblings = siblings->siblings) {
                U_32 j = siblings->getHeight();
                if(j > i) i = j;
            }
        }
        return i + 1;
    }

    U_32 getCount() const {
        U_32 i = 1;
        if(child != NULL)
            i += child->getCount();
        if(siblings != NULL)
            i += siblings->getCount();
        return i;
    }
    
    //return number of parents
    U_32 getDepth() const {
        return parent != NULL ? parent->getDepth() + 1 : 0; 
    }

    U_32 getPreNum() const { return preNum; }
    U_32 getPostNum() const { return postNum; }

    // Return true if this is a proper ancestor of n.
    bool isAncestorOf(TreeNode* n) {
        return (preNum < n->preNum) && (postNum > n->postNum); 
    }

protected:
    TreeNode* child;
    TreeNode* siblings;
    TreeNode* parent;
    U_32 preNum;
    U_32 postNum;
};


class Tree: public PrintDotFile {
public:
    Tree(): root(NULL) {}
    TreeNode* getRoot() {return root;}

    virtual void printDotFile(MethodDesc& mh, const char *suffix) {
        if (root == NULL) return;
        PrintDotFile::printDotFile(mh,suffix);
    }
    virtual void printDotBody() {
        if (root == NULL) return;
        root->printDotTreeNode(*os);
        //
        // lay out ranks
        //
        root->printDotRank(*os);
    }

    virtual void printIndentedTree(::std::ostream& os, const ::std::string& indentstr = "") {
        if(root == NULL) return;
        root->printIndentedNode(os, indentstr);
    }

    U_32 getHeight() const { return root==NULL ? 0 : root->getHeight(); }
    U_32 getCount() const { return root == NULL ? 0: root->getCount(); }

    // Return true if n1 is a proper ancestor of n2.
    bool isAncestor(const TreeNode* n1, const TreeNode* n2) const {
        return (n1->preNum < n2->preNum) && (n1->postNum > n2->postNum); 
    }

protected:
    void computeOrder() {
        U_32 preNum = 0;
        U_32 postNum = 0;
        computeNodeOrder(root, preNum, postNum);
        assert(preNum == postNum);
    }

    void computeNodeOrder(TreeNode* node, U_32& preNum, U_32& postNum) {
        node->preNum = preNum++;
        if(node->child != NULL)
            computeNodeOrder(node->child,preNum,postNum);
        node->postNum = postNum++;
        if(node->siblings != NULL)
            computeNodeOrder(node->siblings,preNum,postNum);
    }

    TreeNode *root;
};

} //namespace Jitrino 

#endif // _TREE_H_