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 
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;
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 
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 }
UniConfKey::compareto
int compareto(const UniConfKey &other) const
Compares two paths lexicographically.
Definition: uniconfkey.cc:235
UniConfKey::prepend
void prepend(const UniConfKey &other)
Prepends a path to this path.
Definition: uniconfkey.cc:152
UniHashTreeBase::xchildren
Container * xchildren
Definition: unihashtree.h:63
UniHashTreeBase::key
const UniConfKey & key() const
Returns the key field.
Definition: unihashtree.h:40
UniConfKey::Iter
An iterator over the segments of a key.
Definition: uniconfkey.h:463
UniConfKey
Represents a UniConf key which is a path in a hierarchy structured much like the traditional Unix fil...
Definition: uniconfkey.h:38
UniHashTreeBase::xparent
UniHashTreeBase * xparent
Definition: unihashtree.h:62
UniConfKey::isempty
bool isempty() const
Returns true if this path has zero segments (also known as root).
Definition: uniconfkey.h:264
UniHashTreeBase
Definition: unihashtree.h:23
UniHashTreeBase::haschildren
bool haschildren() const
Returns true if the node has children.
Definition: unihashtree.cc:114