WvStreams
unihashtree.cc
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 
00105 UniHashTreeBase *UniHashTreeBase::_findchild(const UniConfKey &key) const
00106 {
00107     if (key.isempty())
00108         return const_cast<UniHashTreeBase*>(this);
00109 
00110     return xchildren ? (*xchildren)[key] : NULL;
00111 }
00112 
00113 
00114 bool UniHashTreeBase::haschildren() const
00115 {
00116     return xchildren && !xchildren->isempty();
00117 }
00118 
00119 
00120 void UniHashTreeBase::link(UniHashTreeBase *node)
00121 {
00122     if (!xchildren)
00123         xchildren = new Container();
00124 
00125     xchildren->add(node);
00126 }
00127 
00128 
00129 void UniHashTreeBase::unlink(UniHashTreeBase *node)
00130 {
00131     if (!xchildren)
00132         return;
00133 
00134     xchildren->remove(node);
00135     if (xchildren->count() == 0)
00136     {
00137         delete xchildren;
00138         xchildren = NULL;
00139     }
00140 }
00141 
00142 
00143 static int keysorter(const UniHashTreeBase *a, const UniHashTreeBase *b)
00144 {
00145     return a->key().compareto(b->key());
00146 }
00147 
00148 void UniHashTreeBase::_recursive_unsorted_visit(
00149     const UniHashTreeBase *a,
00150     const UniHashTreeBaseVisitor &visitor, void *userdata,
00151     bool preorder, bool postorder)
00152 {
00153     if (preorder)
00154         visitor(a, userdata);
00155     Container::Iter i(*const_cast<Container*>(a->xchildren));
00156     for (i.rewind(); i.next();)
00157         _recursive_unsorted_visit(i.ptr(), visitor, userdata,
00158             preorder, postorder);
00159     if (postorder)
00160         visitor(a, userdata);
00161 }
00162 
00163 bool UniHashTreeBase::_recursivecompare(
00164     const UniHashTreeBase *a, const UniHashTreeBase *b,
00165     const UniHashTreeBaseComparator &comparator)
00166 {
00167     bool equal = true;
00168     
00169     // don't bother comparing subtree if this returns false
00170     // apenwarr 2004/04/26: some people seem to call recursivecompare and
00171     // have their comparator function get called for *all* keys, because
00172     // it has side effects.  Gross, but whatever.  If that's the case, then
00173     // short-circuiting here is a bad idea.
00174     if (!comparator(a, b))
00175         equal = false;
00176 
00177     // begin iteration sequence
00178     Container::Sorter *ait = NULL, *bit = NULL;
00179     if (a != NULL)
00180     {
00181         ait = new Container::Sorter(*const_cast<Container*>(a->xchildren),
00182                                     keysorter);
00183         ait->rewind();
00184         a = ait->next() ? ait->ptr() : NULL;
00185     }
00186     if (b != NULL)
00187     {
00188         bit = new Container::Sorter(*const_cast<Container*>(b->xchildren),
00189                                     keysorter);
00190         bit->rewind();
00191         b = bit->next() ? bit->ptr() : NULL;
00192     }
00193 
00194     // compare each key
00195     while (a != NULL && b != NULL)
00196     {
00197         int order = a->key().compareto(b->key());
00198         if (order < 0)
00199         {
00200             equal = false;
00201             _recursivecompare(a, NULL, comparator);
00202             a = ait->next() ? ait->ptr() : NULL;
00203         }
00204         else if (order > 0)
00205         {
00206             equal = false;
00207             _recursivecompare(NULL, b, comparator);
00208             b = bit->next() ? bit->ptr() : NULL;
00209         }
00210         else // keys are equal 
00211         {
00212             if (!_recursivecompare(a, b, comparator))
00213                 equal = false;
00214             a = ait->next() ? ait->ptr() : NULL;
00215             b = bit->next() ? bit->ptr() : NULL;
00216         }
00217     }
00218     
00219     // finish up if one side is bigger than the other
00220     while (a != NULL)
00221     {
00222         equal = false;
00223         _recursivecompare(a, NULL, comparator);
00224         a = ait->next() ? ait->ptr() : NULL;
00225     }
00226     while (b != NULL)
00227     {
00228         equal = false;
00229         _recursivecompare(NULL, b, comparator);
00230         b = bit->next() ? bit->ptr() : NULL;
00231     }
00232     
00233     delete ait;
00234     delete bit;
00235     
00236     return equal;
00237 }