WvStreams
|
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 }