WvStreams
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
11UniHashTreeBase::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
23UniHashTreeBase::~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
42void 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
54UniHashTreeBase *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
63UniConfKey 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
90UniHashTreeBase *UniHashTreeBase::_find(const UniConfKey &key) const
91{
92 const UniHashTreeBase *node = this;
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
105UniHashTreeBase *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
115{
116 return xchildren && !xchildren->isempty();
117}
118
119
120void UniHashTreeBase::link(UniHashTreeBase *node)
121{
122 if (!xchildren)
123 xchildren = new Container();
124
125 xchildren->add(node);
126}
127
128
129void 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
143static int keysorter(const UniHashTreeBase *a, const UniHashTreeBase *b)
144{
145 return a->key().compareto(b->key());
146}
147
148void 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
163bool 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}
An iterator over the segments of a key.
Definition: uniconfkey.h:464
Represents a UniConf key which is a path in a hierarchy structured much like the traditional Unix fil...
Definition: uniconfkey.h:39
int compareto(const UniConfKey &other) const
Compares two paths lexicographically.
Definition: uniconfkey.cc:235
void prepend(const UniConfKey &other)
Prepends a path to this path.
Definition: uniconfkey.cc:152
bool isempty() const
Returns true if this path has zero segments (also known as root).
Definition: uniconfkey.h:264
Container * xchildren
Definition: unihashtree.h:63
const UniConfKey & key() const
Returns the key field.
Definition: unihashtree.h:40
UniHashTreeBase * xparent
Definition: unihashtree.h:62
bool haschildren() const
Returns true if the node has children.
Definition: unihashtree.cc:114