uniconf/unihashtree.cc

   1 /*
   2  * Worldvisions Weaver Software:
   3  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
   4  *
   5  * UniConf low-level tree storage abstraction.
   6  */
   7 #include "unihashtree.h"
   8 #include "assert.h"
   9
  10
  11 UniHashTreeBase::UniHashTreeBase(UniHashTreeBase *parent,
  12     const UniConfKey &key) :
  13     xkey(key)
  14 {
  15     xparent = parent;
  16     xchildren = NULL;
  17
  18     if (xparent)
  19         xparent->link(this);
  20 }
  21
  22
  23 UniHashTreeBase::~UniHashTreeBase()
  24 {
  25     if (xchildren)
  26     {
  27         Container *oldchildren = xchildren;
  28         xchildren = NULL;
  29
  30         delete oldchildren;
  31     }
  32
  33     // This happens only after the children are deleted by our
  34     // subclass.  This ensures that we do not confuse them
  35     // about their parentage as their destructors are invoked
  36     // The xchildren vector is destroyed by the subclass!
  37     if (xparent)
  38         xparent->unlink(this);
  39 }
  40
  41
  42 void UniHashTreeBase::_setparent(UniHashTreeBase *parent)
  43 {
  44     if (xparent == parent)
  45         return;
  46     if (xparent)
  47         xparent->unlink(this);
  48     xparent = parent;
  49     if (xparent)
  50         xparent->link(this);
  51 }
  52
  53
  54 UniHashTreeBase *UniHashTreeBase::_root() const
  55 {
  56     const UniHashTreeBase *node = this;
  57     while (node->xparent)
  58         node = node->xparent;
  59     return const_cast<UniHashTreeBase*>(node);
  60 }
  61
  62
  63 UniConfKey UniHashTreeBase::_fullkey(const UniHashTreeBase *ancestor) const
  64 {
  65     UniConfKey result;
  66     if (ancestor)
  67     {
  68         const UniHashTreeBase *node = this;
  69         while (node != ancestor)
  70         {
  71             result.prepend(node->key());
  72             node = node->xparent;
  73             assert(node != NULL ||
  74                 ! "ancestor was not a node in the tree");
  75         }
  76     }
  77     else
  78     {
  79         const UniHashTreeBase *node = this;
  80         while (node->xparent)
  81         {
  82             result.prepend(node->key());
  83             node = node->xparent;
  84         }
  85     }
  86     return result;
  87 }
  88
  89
  90 UniHashTreeBase *UniHashTreeBase::_find(const UniConfKey &key) const
  91 {
  92     const UniHashTreeBase *node = this;
  93     UniConfKey::Iter it(key);
  94     it.rewind();
  95     while (it.next())
  96     {
  97         node = node->_findchild(it());
  98         if (!node)
  99             break;
 100     }
 101     return const_cast<UniHashTreeBase*>(node);
 102 }
 103
 104
 105 UniHashTreeBase *UniHashTreeBase::_findchild(const UniConfKey &key) const
 106 {
 107     if (key.isempty())
 108         return const_cast<UniHashTreeBase*>(this);
 109
 110     return xchildren ? (*xchildren)[key] : NULL;
 111 }
 112
 113
 114 bool UniHashTreeBase::haschildren() const
 115 {
 116     return xchildren && !xchildren->isempty();
 117 }
 118
 119
 120 void UniHashTreeBase::link(UniHashTreeBase *node)
 121 {
 122     if (!xchildren)
 123         xchildren = new Container();
 124
 125     xchildren->add(node);
 126 }
 127
 128
 129 void UniHashTreeBase::unlink(UniHashTreeBase *node)
 130 {
 131     if (!xchildren)
 132         return;
 133
 134     xchildren->remove(node);
 135     if (xchildren->count() == 0)
 136     {
 137         delete xchildren;
 138         xchildren = NULL;
 139     }
 140 }
 141
 142
 143 static int keysorter(const UniHashTreeBase *a, const UniHashTreeBase *b)
 144 {
 145     return a->key().compareto(b->key());
 146 }
 147
 148 void UniHashTreeBase::_recursive_unsorted_visit(
 149     const UniHashTreeBase *a,
 150     const UniHashTreeBaseVisitor &visitor, void *userdata,
 151     bool preorder, bool postorder)
 152 {
 153     if (preorder)
 154         visitor(a, userdata);
 155     Container::Iter i(*const_cast<Container*>(a->xchildren));
 156     for (i.rewind(); i.next();)
 157         _recursive_unsorted_visit(i.ptr(), visitor, userdata,
 158             preorder, postorder);
 159     if (postorder)
 160         visitor(a, userdata);
 161 }
 162
 163 bool UniHashTreeBase::_recursivecompare(
 164     const UniHashTreeBase *a, const UniHashTreeBase *b,
 165     const UniHashTreeBaseComparator &comparator)
 166 {
 167     bool equal = true;
 168
 169     // don't bother comparing subtree if this returns false
 170     // apenwarr 2004/04/26: some people seem to call recursivecompare and
 171     // have their comparator function get called for *all* keys, because
 172     // it has side effects.  Gross, but whatever.  If that's the case, then
 173     // short-circuiting here is a bad idea.
 174     if (!comparator(a, b))
 175         equal = false;
 176
 177     // begin iteration sequence
 178     Container::Sorter *ait = NULL, *bit = NULL;
 179     if (a != NULL)
 180     {
 181         ait = new Container::Sorter(*const_cast<Container*>(a->xchildren),
 182                                     keysorter);
 183         ait->rewind();
 184         a = ait->next() ? ait->ptr() : NULL;
 185     }
 186     if (b != NULL)
 187     {
 188         bit = new Container::Sorter(*const_cast<Container*>(b->xchildren),
 189                                     keysorter);
 190         bit->rewind();
 191         b = bit->next() ? bit->ptr() : NULL;
 192     }
 193
 194     // compare each key
 195     while (a != NULL && b != NULL)
 196     {
 197         int order = a->key().compareto(b->key());
 198         if (order < 0)
 199         {
 200             equal = false;
 201             _recursivecompare(a, NULL, comparator);
 202             a = ait->next() ? ait->ptr() : NULL;
 203         }
 204         else if (order > 0)
 205         {
 206             equal = false;
 207             _recursivecompare(NULL, b, comparator);
 208             b = bit->next() ? bit->ptr() : NULL;
 209         }
 210         else // keys are equal
 211         {
 212             if (!_recursivecompare(a, b, comparator))
 213                 equal = false;
 214             a = ait->next() ? ait->ptr() : NULL;
 215             b = bit->next() ? bit->ptr() : NULL;
 216         }
 217     }
 218
 219     // finish up if one side is bigger than the other
 220     while (a != NULL)
 221     {
 222         equal = false;
 223         _recursivecompare(a, NULL, comparator);
 224         a = ait->next() ? ait->ptr() : NULL;
 225     }
 226     while (b != NULL)
 227     {
 228         equal = false;
 229         _recursivecompare(NULL, b, comparator);
 230         b = bit->next() ? bit->ptr() : NULL;
 231     }
 232
 233     delete ait;
 234     delete bit;
 235
 236     return equal;
 237 }