inheritancetree.cpp

Pegasus is an open-source implementationof the DMTF CIM and WBEM standards. It is designed to be por

//%2006////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2000, 2001, 2002 BMC Software; Hewlett-Packard Development
// Company, L.P.; IBM Corp.; The Open Group; Tivoli Systems.
// Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L.P.;
// IBM Corp.; EMC Corporation, The Open Group.
// Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
// IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
// Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
// EMC Corporation; VERITAS Software Corporation; The Open Group.
// Copyright (c) 2006 Hewlett-Packard Development Company, L.P.; IBM Corp.;
// EMC Corporation; Symantec Corporation; The Open Group.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
// ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED
// "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
// LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
//==============================================================================
//
//%/////////////////////////////////////////////////////////////////////////////

#include <Pegasus/Common/String.h>
#include <Pegasus/Common/HashTable.h>
#include <Pegasus/Common/Dir.h>
#include <Pegasus/Common/XmlWriter.h>
#include <Pegasus/Common/CommonUTF.h>
#include <Pegasus/Common/CIMNameUnchecked.h>
#include "InheritanceTree.h"

#if 0
#undef PEG_METHOD_ENTER
#undef PEG_METHOD_EXIT
#define PEG_METHOD_ENTER(x,y)  cout<<"--- Enter: "<<y<<endl;
#define PEG_METHOD_EXIT()
#endif

PEGASUS_NAMESPACE_BEGIN

PEGASUS_USING_STD;

////////////////////////////////////////////////////////////////////////////////
//
// NoCaseEqualFunc
//
////////////////////////////////////////////////////////////////////////////////

struct NoCaseEqualFunc
{
    static Boolean equal(const String& x, const String& y)
    {
        return String::equalNoCase(x, y);
    }
};

////////////////////////////////////////////////////////////////////////////////
//
// InheritanceTreeRep
//
////////////////////////////////////////////////////////////////////////////////

struct InheritanceTreeNode;

struct InheritanceTreeRep
{
    typedef HashTable<
        String, InheritanceTreeNode*, NoCaseEqualFunc, HashLowerCaseFunc> Table;
    Table table;

    // Tradeoff: chosing a larger value decreases hash lookup time but
    // increases iteration (which seems to be the dominant operations).
    // This power of two (256) seems to produce the best results.

    InheritanceTreeRep() : table(256)
    {
    }
};

////////////////////////////////////////////////////////////////////////////////
//
// InheritanceTreeNode
//
////////////////////////////////////////////////////////////////////////////////

class NameSpace;

struct InheritanceTreeExt
{
    InheritanceTreeExt(NameSpace* t, InheritanceTreeNode* itn)
       : tag(t), node(itn) {}
    NameSpace* tag;
    InheritanceTreeNode* node;
};


struct InheritanceTreeNode
{
    InheritanceTreeNode(const CIMName& className);

    void addSubClass(InheritanceTreeNode* subClass);

    Boolean removeSubClass(InheritanceTreeNode* subClass);

    void getSubClassNames(
        Array<CIMName>& subClassNames,
        Boolean deepInheritance,
        NameSpace* tag = 0);

    void getSuperClassNames(Array<CIMName>& superClassNames);

    void print(PEGASUS_STD(ostream)& os) const;
#if 0
    Boolean isSubClass(const CIMName& className) const;
#endif
    CIMName className;
    InheritanceTreeNode* superClass;
    InheritanceTreeNode* sibling;
    union {
    InheritanceTreeNode* subClasses;
       Array<InheritanceTreeExt*>* extNodes;
    };
    Boolean provisional;
    Boolean extension;
};

InheritanceTreeNode::InheritanceTreeNode(const CIMName& className)
    : className(className), superClass(0),
    sibling(0), subClasses(0), provisional(true), extension(false)
{
}

void InheritanceTreeNode::addSubClass(InheritanceTreeNode* subClass)
{
    subClass->superClass = this;
    subClass->sibling = subClasses;
    subClasses = subClass;
}

Boolean InheritanceTreeNode::removeSubClass(InheritanceTreeNode* subClass)
{
    InheritanceTreeNode* prev = 0;

    for (InheritanceTreeNode* p = subClasses; p; p = p->sibling)
    {
        if (p == subClass)
        {
            if (prev)
                prev->sibling = subClass->sibling;
            else
                subClasses = subClass->sibling;

            return true;
        }
        prev = p;
    }

    return false;
}

void InheritanceTreeNode::getSubClassNames(
    Array<CIMName>& subClassNames,
    Boolean deepInheritance,
    NameSpace* ns)
{
    // For each subClass:

    for (InheritanceTreeNode* p = subClasses; p; p = p->sibling)
    {
        if (p->extension)
        {
            for (int j = 0, m = p->extNodes->size(); j < m; j++)
            {
                InheritanceTreeExt* itx = (*(p->extNodes))[j];
                subClassNames.append(p->className);
                if (!ns)
                {
                    InheritanceTreeNode* itn=itx->node;
                    itn->getSubClassNames(subClassNames, deepInheritance, ns);
                }
                else if (itx->tag == ns)
                {
                    InheritanceTreeNode* itn=itx->node;
                    itn->getSubClassNames(subClassNames, deepInheritance, ns);
                    break;
                }
            }
        }
        else
        {
            subClassNames.append(p->className);
            if (deepInheritance)
            {
                p->getSubClassNames(subClassNames, true, ns);
            }
        }
    }
}

#if 0
Boolean InheritanceTreeNode::isSubClass(const CIMName& className_) const
{
    if (className.equal (className_))
        return true;

    for (InheritanceTreeNode* p = subClasses; p; p = p->sibling)
    {
        if (p->className.equal (className_))
            return true;
    }

    return false;
}
#endif

void InheritanceTreeNode::getSuperClassNames(Array<CIMName>& superClassNames)
{
    // For each superClass:

    for (InheritanceTreeNode* p = superClass; p; p = p->superClass)
    {
        superClassNames.append(p->className);
        // p->getSuperClassNames(superClassNames);
    }
}

void InheritanceTreeNode::print(PEGASUS_STD(ostream)& os) const
{
    os << className << " : " ;
    os << (superClass ? superClass->className : CIMName ());

    os << " { ";

    for (InheritanceTreeNode* p = subClasses; p; p = p->sibling)
        os << p->className << ' ';

    os << "}" << endl;
}

////////////////////////////////////////////////////////////////////////////////
//
// InheritanceTree
//
////////////////////////////////////////////////////////////////////////////////

InheritanceTree::InheritanceTree()
{
    _rep = new InheritanceTreeRep;
}

InheritanceTree::~InheritanceTree()
{
    for (InheritanceTreeRep::Table::Iterator i = _rep->table.start(); i; i++)
        delete i.value();

    delete _rep;
}
void InheritanceTree::insert(
    const String& className,
    const String& superClassName,
    InheritanceTree& parentTree,
    NameSpace* tag)
{
    InheritanceTreeNode* superClassNode = 0;

    if (superClassName.size() &&
        !parentTree._rep->table.lookup(superClassName, superClassNode))
    {
        superClassNode =
            new InheritanceTreeNode(CIMNameUnchecked(superClassName));
        parentTree._rep->table.insert(superClassName, superClassNode);
    }

    InheritanceTreeNode* extNode = 0;

    if (!parentTree._rep->table.lookup(className, extNode))
    {
        extNode = new InheritanceTreeNode(CIMNameUnchecked(className));
        parentTree._rep->table.insert(className, extNode);
        extNode->extension=true;
        extNode->extNodes=new Array<InheritanceTreeExt*>;
    }

    extNode->provisional = false;

    if (superClassNode)
        superClassNode->addSubClass(extNode);

    InheritanceTreeNode* classNode = 0;

    if (!_rep->table.lookup(className, classNode))
    {
        classNode = new InheritanceTreeNode(className);
        _rep->table.insert(className, classNode);
    }

    extNode->extNodes->append(new InheritanceTreeExt(tag,classNode));

    classNode->superClass = superClassNode;
    /* temp comment out this code from bug 3352.  See bug 3498 for reason
    if (extNode)