Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

unihashtree.cc

Go to the documentation of this file.
00001 /*
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * UniConf low-level tree storage abstraction.
00006  */
00007 #include "unihashtree.h"
00008 #include "assert.h"
00009 
00010 
00011 UniHashTreeBase::UniHashTreeBase(UniHashTreeBase *parent, 
00012     const UniConfKey &key) :
00013     xkey(key)
00014 {
00015     xparent = parent;
00016     xchildren = NULL;
00017     
00018     if (xparent)
00019         xparent->link(this);
00020 }
00021 
00022 
00023 UniHashTreeBase::~UniHashTreeBase()
00024 {
00025     if (xchildren)
00026     {
00027         Container *oldchildren = xchildren;
00028         xchildren = NULL;
00029 
00030         delete oldchildren;
00031     } 
00032 
00033     // This happens only after the children are deleted by our
00034     // subclass.  This ensures that we do not confuse them
00035     // about their parentage as their destructors are invoked
00036     // The xchildren vector is destroyed by the subclass!
00037     if (xparent)
00038         xparent->unlink(this);
00039 }
00040 
00041 
00042 void UniHashTreeBase::_setparent(UniHashTreeBase *parent)
00043 {
00044     if (xparent == parent)
00045         return;
00046     if (xparent)
00047         xparent->unlink(this);
00048     xparent = parent;
00049     if (xparent)
00050         xparent->link(this);
00051 }
00052 
00053 
00054 UniHashTreeBase *UniHashTreeBase::_root() const
00055 {
00056     const UniHashTreeBase *node = this;
00057     while (node->xparent)
00058         node = node->xparent;
00059     return const_cast<UniHashTreeBase*>(node);
00060 }
00061 
00062 
00063 UniConfKey UniHashTreeBase::_fullkey(const UniHashTreeBase *ancestor) const
00064 {
00065     UniConfKey result;
00066     if (ancestor)
00067     {
00068         const UniHashTreeBase *node = this;
00069         while (node != ancestor)
00070         {
00071             result.prepend(node->key());
00072             node = node->xparent;
00073             assert(node != NULL ||
00074                 ! "ancestor was not a node in the tree");
00075         }
00076     }
00077     else
00078     {
00079         const UniHashTreeBase *node = this;
00080         while (node->xparent)
00081         {
00082             result.prepend(node->key());
00083             node = node->xparent;
00084         }
00085     }
00086     return result;
00087 }
00088 
00089 
00090 UniHashTreeBase *UniHashTreeBase::_find(const UniConfKey &key) const
00091 {
00092     const UniHashTreeBase *node = this;
00093     UniConfKey::Iter it(key);
00094     it.rewind();
00095     while (it.next())
00096     {
00097         node = node->_findchild(it());
00098         if (!node)
00099             break;
00100     }
00101     return const_cast<UniHashTreeBase*>(node);
00102 }
00103 
00104 UniHashTreeBase *UniHashTreeBase::_findchild(const UniConfKey &key) const
00105 {
00106     if (key.isempty())
00107         return const_cast<UniHashTreeBase*>(this);
00108 
00109     return xchildren ? (*xchildren)[key] : NULL;
00110 }
00111 
00112 
00113 bool UniHashTreeBase::haschildren() const
00114 {
00115     return xchildren && !xchildren->isempty();
00116 }
00117 
00118 void UniHashTreeBase::link(UniHashTreeBase *node)
00119 {
00120     if (!xchildren)
00121         xchildren = new Container();
00122 
00123     xchildren->add(node);
00124 }
00125 
00126 void UniHashTreeBase::unlink(UniHashTreeBase *node)
00127 {
00128     if (!xchildren)
00129         return;
00130 
00131     xchildren->remove(node);
00132     if (xchildren->count() == 0)
00133     {
00134         delete xchildren;
00135         xchildren = NULL;
00136     }
00137 }
00138 
00139 
00140 void UniHashTreeBase::_recursivecompare(
00141     const UniHashTreeBase *a, const UniHashTreeBase *b,
00142     const UniHashTreeBaseComparator &comparator, void *userdata)
00143 {
00144     // don't bother comparing subtree if this returns false
00145     if (! comparator(a, b, userdata))
00146         return;
00147 
00148     // begin iteration sequence
00149     Iter ait(*const_cast<UniHashTreeBase*>(a));
00150     if (a != NULL)
00151     {
00152         ait.rewind();
00153         if (ait.next())
00154             a = ait.ptr();
00155         else
00156             a = NULL;
00157     }
00158     Iter bit(*const_cast<UniHashTreeBase*>(b));
00159     if (b != NULL)
00160     {
00161         bit.rewind();
00162         if (bit.next())
00163             b = bit.ptr();
00164         else
00165             b = NULL;
00166     }
00167 
00168     // loop
00169     while (a != NULL && b != NULL)
00170     {
00171         int order = a->key().compareto(b->key());
00172         if (order < 0)
00173         {
00174             _recursivecompare(a, NULL, comparator, userdata);
00175             a = ait.next() ? ait.ptr() : NULL;
00176         }
00177         else if (order == 0)
00178         {
00179             // keys are equal
00180             _recursivecompare(a, b, comparator, userdata);
00181             a = ait.next() ? ait.ptr() : NULL;
00182             b = bit.next() ? bit.ptr() : NULL;
00183         }
00184         else
00185         {
00186             _recursivecompare(NULL, b, comparator, userdata);
00187             b = bit.next() ? bit.ptr() : NULL;
00188         }
00189     }
00190     while (a != NULL)
00191     {
00192         _recursivecompare(a, NULL, comparator, userdata);
00193         a = ait.next() ? ait.ptr() : NULL;
00194     }
00195     while (b != NULL)
00196     {
00197         _recursivecompare(NULL, b, comparator, userdata);
00198         b = bit.next() ? bit.ptr() : NULL;
00199     }
00200 }
00201 

Generated on Wed Dec 15 15:08:10 2004 for WvStreams by  doxygen 1.3.9.1