Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | 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 Tue Oct 5 01:09:19 2004 for WvStreams by doxygen 1.3.7