Branch data Line data Source code
1 : : // Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC")
2 : : //
3 : : // Permission to use, copy, modify, and/or distribute this software for any
4 : : // purpose with or without fee is hereby granted, provided that the above
5 : : // copyright notice and this permission notice appear in all copies.
6 : : //
7 : : // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
8 : : // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
9 : : // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
10 : : // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
11 : : // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
12 : : // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
13 : : // PERFORMANCE OF THIS SOFTWARE.
14 : :
15 : : #ifndef _RBTREE_H
16 : : #define _RBTREE_H 1
17 : :
18 : : //! \file datasrc/rbtree.h
19 : : ///
20 : : /// \note The purpose of the RBTree is to provide a generic map with
21 : : /// domain names as the key that can be used by various BIND 10 modules or
22 : : /// even by other applications. However, because of some unresolved design
23 : : /// issue, the design and interface are not fixed, and RBTree isn't ready
24 : : /// to be used as a base data structure by other modules.
25 : :
26 : : #include <exceptions/exceptions.h>
27 : :
28 : : #include <dns/name.h>
29 : : #include <boost/utility.hpp>
30 : : #include <boost/shared_ptr.hpp>
31 : : #include <exceptions/exceptions.h>
32 : : #include <ostream>
33 : : #include <algorithm>
34 : : #include <cassert>
35 : :
36 : : namespace isc {
37 : : namespace datasrc {
38 : :
39 : : namespace helper {
40 : :
41 : : /// \brief Helper function to remove the base domain from super domain.
42 : : ///
43 : : /// The precondition of this function is the super_name contains the
44 : : /// sub_name so
45 : : /// \code Name a("a.b.c");
46 : : /// Name b("b.c");
47 : : /// Name c = a - b;
48 : : /// \endcode
49 : : /// c will contain "a".
50 : : ///
51 : : /// \note Functions in this namespace is not intended to be used outside of
52 : : /// RBTree implementation.
53 : : inline isc::dns::Name
54 : : operator-(const isc::dns::Name& super_name, const isc::dns::Name& sub_name) {
55 : : return (super_name.split(0, super_name.getLabelCount() -
56 [ + - + - ]: 19938 : sub_name.getLabelCount()));
[ + - + - ]
57 : : }
58 : : }
59 : :
60 : : /// Forward declare RBTree class here is convinent for following friend
61 : : /// class declare inside RBNode and RBTreeNodeChain
62 : : template <typename T>
63 : : class RBTree;
64 : :
65 : : /// \brief \c RBNode is used by RBTree to store any data related to one domain
66 : : /// name.
67 : : ///
68 : : /// This is meant to be used only from RBTree. It is meaningless to inherit it
69 : : /// or create instances of it from elsewhere. For that reason, the constructor
70 : : /// is private.
71 : : ///
72 : : /// It serves three roles. One is to keep structure of the \c RBTree as a
73 : : /// red-black tree. For that purpose, it has left, right and parent pointers
74 : : /// and color member. These are private and accessed only from within the tree.
75 : : ///
76 : : /// The second one is to store data for one domain name. The data related
77 : : /// functions can be used to access and set the data.
78 : : ///
79 : : /// The third role is to keep the hierarchy of domains. The down pointer points
80 : : /// to a subtree of subdomains. Note that we can traverse the hierarchy down,
81 : : /// but not up.
82 : : ///
83 : : /// One special kind of node is non-terminal node. It has subdomains with
84 : : /// RRsets, but doesn't have any RRsets itself.
85 : : template <typename T>
86 : : class RBNode : public boost::noncopyable {
87 : : private:
88 : : /// The RBNode is meant for use from within RBTree, so it has access to
89 : : /// it.
90 : : friend class RBTree<T>;
91 : :
92 : : /// \name Constructors
93 : : ///
94 : : /// \note The existence of a RBNode without a RBTree is meaningless.
95 : : /// Therefore the constructors are private.
96 : : //@{
97 : :
98 : : /// \brief Default constructor.
99 : : ///
100 : : /// This constructor is provided specifically for generating a special
101 : : /// "null" node.
102 : : RBNode();
103 : :
104 : : /// \brief Constructor from the node name.
105 : : ///
106 : : /// \param name The *relative* domain name (if this will live inside
107 : : /// a.b.c and is called d.e.a.b.c, then you pass d.e).
108 : : RBNode(const isc::dns::Name& name);
109 : : //@}
110 : :
111 : : public:
112 : : /// \brief Alias for shared pointer to the data.
113 : : typedef boost::shared_ptr<T> NodeDataPtr;
114 : :
115 : : /// Node flags.
116 : : ///
117 : : /// Each flag value defines a non default property for a specific node.
118 : : /// These are defined as bitmask type values for the convenience of
119 : : /// internal implementation, but applications are expected to use
120 : : /// each flag separately via the enum definitions.
121 : : ///
122 : : /// All (settable) flags are off by default; they must be explicitly
123 : : /// set to on by the \c setFlag() method.
124 : : enum Flags {
125 : : FLAG_CALLBACK = 1, ///< Callback enabled. See \ref callback
126 : : FLAG_USER1 = 0x80000000U, ///< Application specific flag
127 : : FLAG_USER2 = 0x40000000U, ///< Application specific flag
128 : : FLAG_USER3 = 0x20000000U ///< Application specific flag
129 : : };
130 : : private:
131 : : // Some flag values are expected to be used for internal purposes
132 : : // (e.g., representing the node color) in future versions, so we
133 : : // limit the settable flags via the \c setFlag() method to those
134 : : // explicitly defined in \c Flags. This constant represents all
135 : : // such flags.
136 : : static const uint32_t SETTABLE_FLAGS = (FLAG_CALLBACK | FLAG_USER1 |
137 : : FLAG_USER2 | FLAG_USER3);
138 : :
139 : : public:
140 : :
141 : : /// \brief Destructor
142 : : ///
143 : : /// It might seem strange that constructors are private and destructor
144 : : /// public, but this is needed because of shared pointers need access
145 : : /// to the destructor.
146 : : ///
147 : : /// You should never call anything like:
148 : : /// \code delete pointer_to_node; \endcode
149 : : /// The RBTree handles both creation and destructoion of nodes.
150 : : ~RBNode();
151 : :
152 : : /// \name Getter functions.
153 : : //@{
154 : : /// \brief Return the name of current node.
155 : : ///
156 : : /// It's relative to its containing node.
157 : : ///
158 : : /// To get the absolute name of one node, the node path from the top node
159 : : /// to current node has to be recorded.
160 : : const isc::dns::Name& getName() const { return (name_); }
161 : :
162 : : /// \brief Return the data stored in this node.
163 : : ///
164 : : /// You should not delete the data, it is handled by shared pointers.
165 : : NodeDataPtr& getData() { return (data_); }
166 : : /// \brief Return the data stored in this node.
167 : : const NodeDataPtr& getData() const { return (data_); }
168 : :
169 : : /// \brief return whether the node has related data.
170 : : ///
171 : : /// There can be empty nodes inside the RBTree. They are usually the
172 : : /// non-terminal domains, but it is possible (yet probably meaningless)
173 : : /// empty nodes anywhere.
174 : : bool isEmpty() const { return (data_.get() == NULL); }
175 : :
176 : : //@}
177 : :
178 : : /// \name Setter functions.
179 : : //@{
180 : : /// \brief Set the data stored in the node.
181 [ + - ][ + - ]: 1438 : void setData(const NodeDataPtr& data) { data_ = data; }
[ + - ]
182 : : //@}
183 : :
184 : : /// \name Node flag manipulation methods
185 : : //@{
186 : : /// Get the status of a node flag.
187 : : ///
188 : : /// This method returns whether the given node flag is set (enabled)
189 : : /// on the node. The \c flag parameter is expected to be one of the
190 : : /// defined \c Flags constants. For simplicity, the method interface
191 : : /// does not prohibit passing an undefined flag or combined flags, but
192 : : /// the return value in such a case will be meaningless for the caller
193 : : /// (an application would have to use an ugly cast for such an unintended
194 : : /// form of call, which will hopefully avoid accidental misuse).
195 : : ///
196 : : /// \exception None
197 : : /// \param flag The flag to be tested.
198 : : /// \return \c true if the \c flag is set; \c false otherwise.
199 : 0 : bool getFlag(Flags flag) const {
200 : 0 : return ((flags_ & flag) != 0);
201 : : }
202 : :
203 : : /// Set or clear a node flag.
204 : : ///
205 : : /// This method changes the status of the specified node flag to either
206 : : /// "on" (enabled) or "off" (disabled). The new status is specified by
207 : : /// the \c on parameter.
208 : : /// Like the \c getFlag() method, \c flag is expected to be one of the
209 : : /// defined \c Flags constants. If an undefined or unsettable flag is
210 : : /// specified, \c isc::InvalidParameter exception will be thrown.
211 : : ///
212 : : /// \exception isc::InvalidParameter Unsettable flag is specified
213 : : /// \exception None otherwise
214 : : /// \param flag The node flag to be changed.
215 : : /// \param on If \c true, set the flag to on; otherwise set it to off.
216 : 387 : void setFlag(Flags flag, bool on = true) {
217 [ + + ]: 387 : if ((flag & ~SETTABLE_FLAGS) != 0) {
218 [ + - ]: 2 : isc_throw(isc::InvalidParameter,
219 : : "Unsettable RBTree flag is being set");
220 : : }
221 [ + + ]: 386 : if (on) {
222 : 384 : flags_ |= flag;
223 : : } else {
224 : 2 : flags_ &= ~flag;
225 : : }
226 : 386 : }
227 : : //@}
228 : :
229 : : private:
230 : : /// \name Callback related methods
231 : : ///
232 : : /// See the description of \c RBTree<T>::find() at \ref callback
233 : : /// about callbacks.
234 : : ///
235 : : /// These methods never throw an exception.
236 : : //@{
237 : : /// Return if callback is enabled at the node.
238 : : //@}
239 : :
240 : :
241 : : /// \brief Define rbnode color
242 : : enum RBNodeColor {BLACK, RED};
243 : : /// This is a factory class method of a special singleton null node.
244 : 7919 : static RBNode<T>* NULL_NODE() {
245 [ + + ][ + - ]: 7926 : static RBNode<T> null_node;
246 : 7919 : return (&null_node);
247 : : }
248 : :
249 : : /// \brief return the next node which is bigger than current node
250 : : /// in the same subtree
251 : : ///
252 : : /// The next successor for this node is the next bigger node in terms of
253 : : /// the DNSSEC order relation within the same single subtree.
254 : : /// Note that it may NOT be the next bigger node in the entire RBTree;
255 : : /// RBTree is a tree in tree, and the real next node may reside in
256 : : /// an upper or lower subtree of the subtree where this node belongs.
257 : : /// For example, if this node has a sub domain, the real next node is
258 : : /// the smallest node in the sub domain tree.
259 : : ///
260 : : /// If this node is the biggest node within the subtree, this method
261 : : /// returns \c NULL_NODE().
262 : : ///
263 : : /// This method never throws an exception.
264 : : const RBNode<T>* successor() const;
265 : :
266 : : /// \brief return the next node which is smaller than current node
267 : : /// in the same subtree
268 : : ///
269 : : /// The predecessor for this node is the next smaller node in terms of
270 : : /// the DNSSEC order relation within the same single subtree.
271 : : /// Note that it may NOT be the next smaller node in the entire RBTree;
272 : : /// RBTree is a tree in tree, and the real next node may reside in
273 : : /// an upper or lower subtree of the subtree where this node belongs.
274 : : /// For example, if the predecessor node has a sub domain, the real next
275 : : /// node is the largest node in the sub domain tree.
276 : : ///
277 : : /// If this node is the smallest node within the subtree, this method
278 : : /// returns \c NULL_NODE().
279 : : ///
280 : : /// This method never throws an exception.
281 : : const RBNode<T>* predecessor() const;
282 : :
283 : : /// \brief private shared implementation of successor and predecessor
284 : : ///
285 : : /// As the two mentioned functions are merely mirror images of each other,
286 : : /// it makes little sense to keep both versions. So this is the body of the
287 : : /// functions and we call it with the correct pointers.
288 : : ///
289 : : /// Not to be called directly, not even by friends.
290 : : ///
291 : : /// The overhead of the member pointers should be optimised out, as this
292 : : /// will probably get completely inlined into predecessor and successor
293 : : /// methods.
294 : : const RBNode<T>* abstractSuccessor(RBNode<T>* RBNode<T>::*left,
295 : : RBNode<T>* RBNode<T>::*right) const;
296 : :
297 : : /// \name Data to maintain the rbtree structure.
298 : : //@{
299 : : RBNode<T>* parent_;
300 : : RBNode<T>* left_;
301 : : RBNode<T>* right_;
302 : : RBNodeColor color_;
303 : : //@}
304 : :
305 : : /// \brief Relative name of the node.
306 : : isc::dns::Name name_;
307 : : /// \brief Data stored here.
308 : : NodeDataPtr data_;
309 : :
310 : : /// \brief The subdomain tree.
311 : : ///
312 : : /// This points to the root node of trees of subdomains of this domain.
313 : : ///
314 : : /// \par Adding down pointer to \c RBNode has two purposes:
315 : : /// \li Accelerate the search process, with sub domain tree, it splits the
316 : : /// big flat tree into several hierarchy trees.
317 : : /// \li It saves memory usage as it allows storing only relative names,
318 : : /// avoiding storage of the same domain labels multiple times.
319 : : RBNode<T>* down_;
320 : :
321 : : /// \brief If callback should be called when traversing this node in
322 : : /// RBTree::find().
323 : : ///
324 : : /// \todo It might be needed to put it into more general attributes field.
325 : : uint32_t flags_;
326 : : };
327 : :
328 : :
329 : : // This is only to support NULL nodes.
330 : : template <typename T>
331 : : RBNode<T>::RBNode() :
332 : : parent_(NULL),
333 : : left_(NULL),
334 : : right_(NULL),
335 : : color_(BLACK),
336 : : // dummy name, the value doesn't matter:
337 : : name_(isc::dns::Name::ROOT_NAME()),
338 : : down_(NULL),
339 [ + - ][ + - ]: 7 : flags_(0)
340 : : {
341 : : // Some compilers object to use of "this" in initializer lists.
342 : 7 : parent_ = this;
343 : 7 : left_ = this;
344 : 7 : right_ = this;
345 : 7 : down_ = this;
346 : : }
347 : :
348 : : template <typename T>
349 : 1794 : RBNode<T>::RBNode(const isc::dns::Name& name) :
350 : : parent_(NULL_NODE()),
351 : : left_(NULL_NODE()),
352 : : right_(NULL_NODE()),
353 : : color_(RED),
354 : : name_(name),
355 : : down_(NULL_NODE()),
356 [ + - ]: 1794 : flags_(0)
357 : : {
358 : 1794 : }
359 : :
360 : :
361 : : template <typename T>
362 : 1801 : RBNode<T>::~RBNode() {
363 : 1801 : }
364 : :
365 : : template <typename T>
366 : : const RBNode<T>*
367 : 139 : RBNode<T>::abstractSuccessor(RBNode<T>* RBNode<T>::*left, RBNode<T>*
368 : : RBNode<T>::*right) const
369 : : {
370 : : // This function is written as a successor. It becomes predecessor if
371 : : // the left and right pointers are swapped. So in case of predecessor,
372 : : // the left pointer points to right and vice versa. Don't get confused
373 : : // by the idea, just imagine the pointers look into a mirror.
374 : :
375 : 139 : const RBNode<T>* current = this;
376 : : // If it has right node, the successor is the left-most node of the right
377 : : // subtree.
378 [ + + ]: 139 : if (current->*right != RBNode<T>::NULL_NODE()) {
379 : 33 : current = current->*right;
380 [ + + ]: 34 : while (current->*left != RBNode<T>::NULL_NODE()) {
381 : 1 : current = current->*left;
382 : : }
383 : : return (current);
384 : : }
385 : :
386 : : // Otherwise go up until we find the first left branch on our path to
387 : : // root. If found, the parent of the branch is the successor.
388 : : // Otherwise, we return the null node
389 : 106 : const RBNode<T>* parent = current->parent_;
390 [ + + ][ + + ]: 180 : while (parent != RBNode<T>::NULL_NODE() && current == parent->*right) {
[ + + ]
391 : 41 : current = parent;
392 : 41 : parent = parent->parent_;
393 : : }
394 : : return (parent);
395 : : }
396 : :
397 : : template <typename T>
398 : : const RBNode<T>*
399 : : RBNode<T>::successor() const {
400 : 20 : return (abstractSuccessor(&RBNode<T>::left_, &RBNode<T>::right_));
401 : : }
402 : :
403 : : template <typename T>
404 : : const RBNode<T>*
405 : : RBNode<T>::predecessor() const {
406 : : // Swap the left and right pointers for the abstractSuccessor
407 : 119 : return (abstractSuccessor(&RBNode<T>::right_, &RBNode<T>::left_));
408 : : }
409 : :
410 : : /// \brief RBTreeNodeChain stores detailed information of \c RBTree::find()
411 : : /// result.
412 : : ///
413 : : /// - The \c RBNode that was last compared with the search name, and
414 : : /// the comparison result at that point in the form of
415 : : /// \c isc::dns::NameComparisonResult.
416 : : /// - A sequence of nodes that forms a path to the found node.
417 : : ///
418 : : /// The comparison result can be used to handle some rare cases such as
419 : : /// empty node processing.
420 : : /// The node sequence keeps track of the nodes to reach any given node from
421 : : /// the root of RBTree.
422 : : ///
423 : : /// Currently, RBNode does not have "up" pointers in them (i.e., back pointers
424 : : /// from the root of one level of tree of trees to the node in the parent
425 : : /// tree whose down pointer points to that root node) for memory usage
426 : : /// reasons, so there is no other way to find the path back to the root from
427 : : /// any given RBNode.
428 : : ///
429 : : /// \note This design may change in future versions. In particular, it's
430 : : /// quite likely we want to have that pointer if we want to optimize name
431 : : /// compression by exploiting the structure of the zone. If and when that
432 : : /// happens we should also revisit the need for the chaining.
433 : : /// Also, the class name may not be appropriate now that it contains other
434 : : /// information than a node "chain", and the chain itself may even be
435 : : /// deprecated. Something like "RBTreeFindContext" may be a better name.
436 : : /// This point should be revisited later.
437 : : ///
438 : : /// RBTreeNodeChain is constructed and manipulated only inside the \c RBTree
439 : : /// class.
440 : : /// \c RBTree uses it as an inner data structure to iterate over the whole
441 : : /// RBTree.
442 : : /// This is the reason why manipulation methods such as \c push() and \c pop()
443 : : /// are private (and not shown in the doxygen document).
444 : : template <typename T>
445 : : class RBTreeNodeChain {
446 : : /// RBTreeNodeChain is initialized by RBTree, only RBTree has
447 : : /// knowledge to manipulate it.
448 : : friend class RBTree<T>;
449 : : public:
450 : : /// \name Constructors and Assignment Operator.
451 : : ///
452 : : /// \note The copy constructor and the assignment operator are
453 : : /// intentionally defined as private, making this class non copyable.
454 : : /// This may have to be changed in a future version with newer need.
455 : : /// For now we explicitly disable copy to avoid accidental copy happens
456 : : /// unintentionally.
457 : : //{@
458 : : /// The default constructor.
459 : : ///
460 : : /// \exception None
461 : : RBTreeNodeChain() : node_count_(0), last_compared_(NULL),
462 : : // XXX: meaningless initial values:
463 : : last_comparison_(0, 0,
464 : 1291 : isc::dns::NameComparisonResult::EQUAL)
465 : : {}
466 : :
467 : : private:
468 : : RBTreeNodeChain(const RBTreeNodeChain<T>&);
469 : : RBTreeNodeChain<T>& operator=(const RBTreeNodeChain<T>&);
470 : : //@}
471 : :
472 : : public:
473 : : /// Clear the state of the chain.
474 : : ///
475 : : /// This method re-initializes the internal state of the chain so that
476 : : /// it can be reused for subsequent operations.
477 : : ///
478 : : /// \exception None
479 : 0 : void clear() {
480 : 539 : node_count_ = 0;
481 : 539 : last_compared_ = NULL;
482 : 0 : }
483 : :
484 : : /// Return the \c RBNode that was last compared in \c RBTree::find().
485 : : ///
486 : : /// If this chain has been passed to \c RBTree::find() and there has
487 : : /// been name comparison against the search name, the last compared
488 : : /// \c RBNode is recorded within the chain. This method returns that
489 : : /// node.
490 : : /// If \c RBTree::find() hasn't been called with this chain or name
491 : : /// comparison hasn't taken place (which is possible if the tree is empty),
492 : : /// this method returns \c NULL.
493 : : ///
494 : : /// \exception None
495 : 0 : const RBNode<T>* getLastComparedNode() const {
496 : 0 : return (last_compared_);
497 : : }
498 : :
499 : : /// Return the result of last name comparison in \c RBTree::find().
500 : : ///
501 : : /// Like \c getLastComparedNode(), \c RBTree::find() records the result
502 : : /// of the last name comparison in the chain. This method returns the
503 : : /// result.
504 : : /// The return value of this method is only meaningful when comparison
505 : : /// has taken place, i.e, when \c getLastComparedNode() would return a
506 : : /// non \c NULL value.
507 : : ///
508 : : /// \exception None
509 : : const isc::dns::NameComparisonResult& getLastComparisonResult() const {
510 : : return (last_comparison_);
511 : : }
512 : :
513 : : /// \brief Return the number of levels stored in the chain.
514 : : ///
515 : : /// It's equal to the number of nodes in the chain; for an empty
516 : : /// chain, 0 will be returned.
517 : : ///
518 : : /// \exception None
519 : 0 : unsigned int getLevelCount() const { return (node_count_); }
520 : :
521 : : /// \brief return the absolute name for the node which this
522 : : /// \c RBTreeNodeChain currently refers to.
523 : : ///
524 : : /// The chain must not be empty.
525 : : ///
526 : : /// \exception isc::BadValue the chain is empty.
527 : : /// \exception std::bad_alloc memory allocation for the new name fails.
528 : 165 : isc::dns::Name getAbsoluteName() const {
529 [ + + ]: 165 : if (isEmpty()) {
530 [ + - ]: 2 : isc_throw(isc::BadValue,
531 : : "RBTreeNodeChain::getAbsoluteName is called on an empty "
532 : : "chain");
533 : : }
534 : :
535 : 164 : const RBNode<T>* top_node = top();
536 : 164 : isc::dns::Name absolute_name = top_node->getName();
537 : 164 : int node_count = node_count_ - 1;
538 [ + + ]: 315 : while (node_count > 0) {
539 : 151 : top_node = nodes_[node_count - 1];
540 [ + - ][ + - ]: 151 : absolute_name = absolute_name.concatenate(top_node->getName());
541 : 151 : --node_count;
542 : : }
543 : 164 : return (absolute_name);
544 : : }
545 : :
546 : : private:
547 : : // the following private functions check invariants about the internal
548 : : // state using assert() instead of exception. The state of a chain
549 : : // can only be modified by operations within this file, so if any of the
550 : : // assumptions fails it means an internal bug.
551 : :
552 : : /// \brief return whether node chain has node in it.
553 : : ///
554 : : /// \exception None
555 : 0 : bool isEmpty() const { return (node_count_ == 0); }
556 : :
557 : : /// \brief return the top node for the node chain
558 : : ///
559 : : /// RBTreeNodeChain store all the nodes along top node to
560 : : /// root node of RBTree
561 : : ///
562 : : /// \exception None
563 : 384 : const RBNode<T>* top() const {
564 [ - + ]: 384 : assert(!isEmpty());
565 : 384 : return (nodes_[node_count_ - 1]);
566 : : }
567 : :
568 : : /// \brief pop the top node from the node chain
569 : : ///
570 : : /// After pop, up/super node of original top node will be
571 : : /// the top node
572 : : ///
573 : : /// \exception None
574 : 139 : void pop() {
575 [ - + ]: 139 : assert(!isEmpty());
576 : 139 : --node_count_;
577 : 139 : }
578 : :
579 : : /// \brief add the node into the node chain
580 : : ///
581 : : /// If the node chain isn't empty, the node should be
582 : : /// the sub domain of the original top node in node chain
583 : : /// otherwise the node should be the root node of RBTree.
584 : : ///
585 : : /// \exception None
586 : 11186 : void push(const RBNode<T>* node) {
587 [ - + ]: 11186 : assert(node_count_ < RBT_MAX_LEVEL);
588 : 11186 : nodes_[node_count_++] = node;
589 : 11186 : }
590 : :
591 : : private:
592 : : // The max label count for one domain name is Name::MAX_LABELS (128).
593 : : // Since each node in rbtree stores at least one label, it's also equal
594 : : // to the possible maximum level.
595 : : const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS;
596 : :
597 : : int node_count_;
598 : : const RBNode<T>* nodes_[RBT_MAX_LEVEL];
599 : : const RBNode<T>* last_compared_;
600 : : isc::dns::NameComparisonResult last_comparison_;
601 : : };
602 : :
603 : :
604 : : // note: the following class description is documented using multiline comments
605 : : // because the verbatim diagram contain a backslash, which could be interpreted
606 : : // as escape of newline in singleline comment.
607 : : /**
608 : : * \brief \c RBTree class represents all the domains with the same suffix.
609 : : * It can be used to store the domains in one zone, for example.
610 : : *
611 : : * RBTree is a generic map from domain names to any kind of data. Internally,
612 : : * it uses a red-black tree. However, it isn't one tree containing everything.
613 : : * Subdomains are trees, so this structure is recursive - trees inside trees.
614 : : * But, from the interface point of view, it is opaque data structure.
615 : : *
616 : : * \c RBTree splits the domain space into hierarchy red black trees; nodes
617 : : * in one tree has the same base name. The benefit of this struct is that:
618 : : * - Enhances the query performace compared with one big flat red black tree.
619 : : * - Decreases the memory footprint, as it doesn't store the suffix labels
620 : : * multiple times.
621 : : *
622 : : * Depending on different usage, rbtree will support different search policies.
623 : : * Whether to return an empty node to end user is one policy among them.
624 : : * The default policy is to NOT return an empty node to end user;
625 : : * to change the behavior, specify \c true for the constructor parameter
626 : : * \c returnEmptyNode.
627 : : * \note The search policy only affects the \c find() behavior of RBTree.
628 : : * When inserting one name into RBTree, if the node with the name already
629 : : * exists in the RBTree and it's an empty node which doesn't have any data,
630 : : * the \c insert() method will still return \c ALREADYEXISTS regardless of
631 : : * the search policy.
632 : : *
633 : : * \anchor diagram
634 : : *
635 : : * with the following names:
636 : : * - a
637 : : * - b
638 : : * - c
639 : : * - x.d.e.f
640 : : * - z.d.e.f
641 : : * - g.h
642 : : * - o.w.y.d.e.f
643 : : * - p.w.y.d.e.f
644 : : * - q.w.y.d.e.f
645 : : *
646 : : * the tree will look like:
647 : : * \verbatim
648 : : b
649 : : / \
650 : : a d.e.f
651 : : /|\
652 : : c | g.h
653 : : |
654 : : w.y
655 : : /|\
656 : : x | z
657 : : |
658 : : p
659 : : / \
660 : : o q
661 : : \endverbatim
662 : : * \todo
663 : : * - add remove interface
664 : : * - add iterator to iterate over the whole \c RBTree. This may be necessary,
665 : : * for example, to support AXFR.
666 : : */
667 : : template <typename T>
668 : : class RBTree : public boost::noncopyable {
669 : : friend class RBNode<T>;
670 : : public:
671 : : /// \brief The return value for the \c find() and insert() methods
672 : : enum Result {
673 : : SUCCESS, ///< Insert was successful
674 : : /// \brief The node returned from find mathes exactly the name given
675 : : EXACTMATCH,
676 : : PARTIALMATCH, ///< A superdomain node was found
677 : : NOTFOUND, ///< Not even any superdomain was found
678 : : /// \brief Returned by insert() if a node of the name already exists
679 : : ALREADYEXISTS,
680 : : };
681 : :
682 : : /// \name Constructor and Destructor
683 : : //@{
684 : : /// The constructor.
685 : : ///
686 : : /// It never throws an exception.
687 : : explicit RBTree(bool returnEmptyNode = false);
688 : :
689 : : /// \b Note: RBTree is not intended to be inherited so the destructor
690 : : /// is not virtual
691 : : ~RBTree();
692 : : //@}
693 : :
694 : : /// \name Find methods
695 : : ///
696 : : /// \brief Find the node that gives a longest match against the given name.
697 : : ///
698 : : /// \anchor find
699 : : ///
700 : : /// These methods search the RBTree for a node whose name is longest
701 : : /// against name. The found node, if any, is returned via the node pointer.
702 : : ///
703 : : /// By default, nodes that don't have data (see RBNode::isEmpty) are
704 : : /// ignored and the result can be NOTFOUND even if there's a node whose
705 : : /// name matches. If the \c RBTree is constructed with its
706 : : /// \c returnEmptyNode parameter being \c true, empty nodes will also
707 : : /// be match candidates.
708 : : ///
709 : : /// \note Even when \c returnEmptyNode is \c true, not all empty nodes
710 : : /// in terms of the DNS protocol may necessarily be found by this method.
711 : : /// For example, in the \ref diagram shown in the class description,
712 : : /// the name y.d.e.f is logically contained in the tree as part of the
713 : : /// node w.y, but the \c find() variants cannot find the former for
714 : : /// the search key of y.d.e.f, no matter how the \c RBTree is constructed.
715 : : /// The caller of this method must use a different way to identify the
716 : : /// hidden match when necessary.
717 : : ///
718 : : /// These methods involve operations on names that can throw an exception.
719 : : /// If that happens the exception will be propagated to the caller.
720 : : /// The callback function should generally not throw an exception, but
721 : : /// if it throws, the exception will be propagated to the caller.
722 : : ///
723 : : /// The \c name parameter says what should be found. The node parameter
724 : : /// is output-only, and in case of EXACTMATCH or PARTIALMATCH, it is set
725 : : /// to a pointer to the found node.
726 : : ///
727 : : /// They return:
728 : : /// - EXACTMATCH when a node with the same name as requested exists.
729 : : /// - PARTIALMATCH when a node with the same name does not exist (or is
730 : : /// empty), but there's a (nonempty) superdomain of the requested one.
731 : : /// The superdomain with longest name is returned through the node
732 : : /// parameter. Beware that if you store a zone in the tree, you may get
733 : : /// PARTIALMATCH with zone apex when the given domain name is not there.
734 : : /// You should not try to delegate into another zone in that case.
735 : : /// - NOTFOUND if there's no node with the same name nor any superdomain
736 : : /// of it. In that case, node parameter is left intact.
737 : : //@{
738 : :
739 : : /// \brief Simple find.
740 : : ///
741 : : /// Acts as described in the \ref find section.
742 : 525 : Result find(const isc::dns::Name& name, RBNode<T>** node) const {
743 : : RBTreeNodeChain<T> node_path;
744 : 525 : return (find<void*>(name, node, node_path, NULL, NULL));
745 : : }
746 : :
747 : : /// \brief Simple find returning immutable node.
748 : : ///
749 : : /// Acts as described in the \ref find section, but returns immutable node
750 : : /// pointer.
751 : 20 : Result find(const isc::dns::Name& name, const RBNode<T>** node) const {
752 : : RBTreeNodeChain<T> node_path;
753 : 20 : RBNode<T> *target_node = NULL;
754 : 20 : Result ret = (find<void*>(name, &target_node, node_path, NULL, NULL));
755 [ + + ]: 20 : if (ret != NOTFOUND) {
756 : 16 : *node = target_node;
757 : : }
758 : 20 : return (ret);
759 : : }
760 : :
761 : : /// \brief Simple find, with node_path tracking
762 : : ///
763 : : /// Acts as described in the \ref find section.
764 : : Result find(const isc::dns::Name& name, RBNode<T>** node,
765 : : RBTreeNodeChain<T>& node_path) const
766 : : {
767 [ + - + - ]: 83 : return (find<void*>(name, node, node_path, NULL, NULL));
768 : : }
769 : :
770 : : /// \brief Simple find returning immutable node, with node_path tracking
771 : : ///
772 : : /// Acts as described in the \ref find section, but returns immutable node
773 : : /// pointer.
774 : 207 : Result find(const isc::dns::Name& name, const RBNode<T>** node,
775 : : RBTreeNodeChain<T>& node_path) const
776 : : {
777 : 211 : RBNode<T> *target_node = NULL;
778 [ + - ]: 211 : Result ret = (find<void*>(name, &target_node, node_path, NULL, NULL));
779 [ + - ][ + + ]: 210 : if (ret != NOTFOUND) {
780 : 201 : *node = target_node;
781 : : }
782 : 206 : return (ret);
783 : : }
784 : :
785 : : /// \brief Find with callback and node chain.
786 : : /// \anchor callback
787 : : ///
788 : : /// This version of \c find() is specifically designed for the backend
789 : : /// of the \c InMemoryZoneFinder class, and implements all necessary
790 : : /// features for that purpose. Other applications shouldn't need these
791 : : /// additional features, and should normally use the simpler versions.
792 : : ///
793 : : /// This version of \c find() calls the callback whenever traversing (on
794 : : /// the way from root down the tree) a marked node on the way down through
795 : : /// the domain namespace (see \c RBNode::FLAG_CALLBACK).
796 : : ///
797 : : /// If you return true from the callback, the search is stopped and a
798 : : /// PARTIALMATCH is returned with the given node. Note that this node
799 : : /// doesn't really need to be the one with longest possible match.
800 : : ///
801 : : /// The callback is not called for the node which matches exactly
802 : : /// (EXACTMATCH is returned). This is typically the last node in the
803 : : /// traversal during a successful search.
804 : : ///
805 : : /// This callback mechanism was designed with zone cut (delegation)
806 : : /// processing in mind. The marked nodes would be the ones at delegation
807 : : /// points. It is not expected that any other applications would need
808 : : /// callbacks; they should use the versions of find without callbacks.
809 : : /// The callbacks are not general functors for the same reason - we don't
810 : : /// expect it to be needed.
811 : : ///
812 : : /// Another special feature of this version is the ability to record
813 : : /// more detailed information regarding the search result.
814 : : ///
815 : : /// This information will be returned via the \c node_path parameter,
816 : : /// which is an object of class \c RBTreeNodeChain.
817 : : /// The passed parameter must be empty.
818 : : ///
819 : : /// On success, the node sequence stored in \c node_path will contain all
820 : : /// the ancestor nodes from the found node towards the root.
821 : : /// For example, if we look for o.w.y.d.e.f in the example \ref diagram,
822 : : /// \c node_path will contain w.y and d.e.f; the \c top() node of the
823 : : /// chain will be o, w.y and d.e.f will be stored below it.
824 : : ///
825 : : /// This feature can be used to get the absolute name for a node;
826 : : /// to do so, we need to travel upside from the node toward the root,
827 : : /// concatenating all ancestor names. With the current implementation
828 : : /// it's not possible without a node chain, because there is a no pointer
829 : : /// from the root of a subtree to the parent subtree (this may change
830 : : /// in a future version). A node chain can also be used to find the
831 : : /// next and previous nodes of a given node in the entire RBTree;
832 : : /// the \c nextNode() and \c previousNode() methods take a node
833 : : /// chain as a parameter.
834 : : ///
835 : : /// \exception isc::BadValue node_path is not empty.
836 : : ///
837 : : /// \param name Target to be found
838 : : /// \param node On success (either \c EXACTMATCH or \c PARTIALMATCH)
839 : : /// it will store a pointer to the matching node
840 : : /// \param node_path Other search details will be stored (see the
841 : : /// description)
842 : : /// \param callback If non- \c NULL, a call back function to be called
843 : : /// at marked nodes (see the description).
844 : : /// \param callback_arg A caller supplied argument to be passed to
845 : : /// \c callback.
846 : : ///
847 : : /// \return As in the description, but in case of callback returning
848 : : /// \c true, it returns immediately with the current node.
849 : : template <typename CBARG>
850 : : Result find(const isc::dns::Name& name,
851 : : RBNode<T>** node,
852 : : RBTreeNodeChain<T>& node_path,
853 : : bool (*callback)(const RBNode<T>&, CBARG),
854 : : CBARG callback_arg) const;
855 : :
856 : : /// \brief Simple find returning immutable node.
857 : : ///
858 : : /// Acts as described in the \ref find section, but returns immutable
859 : : /// node pointer.
860 : : template <typename CBARG>
861 : : Result find(const isc::dns::Name& name,
862 : : const RBNode<T>** node,
863 : : RBTreeNodeChain<T>& node_path,
864 : : bool (*callback)(const RBNode<T>&, CBARG),
865 : : CBARG callback_arg) const
866 : : {
867 : 3 : RBNode<T>* target_node = NULL;
868 : : Result ret = find(name, &target_node, node_path, callback,
869 [ + - ][ + - ]: 3 : callback_arg);
[ + - ]
870 [ - + ][ + - ]: 3 : if (ret != NOTFOUND) {
[ + - ]
871 : 2 : *node = target_node;
872 : : }
873 : : return (ret);
874 : : }
875 : : //@}
876 : :
877 : : /// \brief return the next bigger node in DNSSEC order from a given node
878 : : /// chain.
879 : : ///
880 : : /// This method identifies the next bigger node of the node currently
881 : : /// referenced in \c node_path and returns it.
882 : : /// This method also updates the passed \c node_path so that it will store
883 : : /// the path for the returned next node.
884 : : /// It will be convenient when we want to iterate over the all nodes
885 : : /// of \c RBTree; we can do this by calling this method repeatedly
886 : : /// starting from the root node.
887 : : ///
888 : : /// \note \c nextNode() will iterate over all the nodes in RBTree including
889 : : /// empty nodes. If empty node isn't desired, it's easy to add logic to
890 : : /// check return node and keep invoking \c nextNode() until the non-empty
891 : : /// node is retrieved.
892 : : ///
893 : : /// \exception isc::BadValue node_path is empty.
894 : : ///
895 : : /// \param node_path A node chain that stores all the nodes along the path
896 : : /// from root to node.
897 : : ///
898 : : /// \return An \c RBNode that is next bigger than \c node; if \c node is
899 : : /// the largest, \c NULL will be returned.
900 : : const RBNode<T>* nextNode(RBTreeNodeChain<T>& node_path) const;
901 : :
902 : : /// \brief return the next smaller node in DNSSEC order from a node
903 : : /// searched by RBTree::find().
904 : : ///
905 : : /// This acts similarly to \c nextNode(), but it walks in the other
906 : : /// direction. But unlike \c nextNode(), this can start even if the
907 : : /// node requested by \c find() was not found. In that case, it will
908 : : /// identify the node that is previous to the queried name.
909 : : ///
910 : : /// \note \c previousNode() will iterate over all the nodes in RBTree
911 : : /// including empty nodes. If empty node isn't desired, it's easy to add
912 : : /// logic to check return node and keep invoking \c previousNode() until the
913 : : /// non-empty node is retrieved.
914 : : ///
915 : : /// \exception isc::BadValue node_path is empty.
916 : : ///
917 : : /// \param node_path A node chain that stores all the nodes along the path
918 : : /// from root to node and the result of \c find(). This will get modified.
919 : : /// You should not use the node_path again except for repetitive calls
920 : : /// of this method.
921 : : ///
922 : : /// \return An \c RBNode that is next smaller than \c node; if \c node is
923 : : /// the smallest, \c NULL will be returned.
924 : : const RBNode<T>* previousNode(RBTreeNodeChain<T>& node_path) const;
925 : :
926 : : /// \brief Get the total number of nodes in the tree
927 : : ///
928 : : /// It includes nodes internally created as a result of adding a domain
929 : : /// name that is a subdomain of an existing node of the tree.
930 : : /// This function is mainly intended to be used for debugging.
931 : 0 : int getNodeCount() const { return (node_count_); }
932 : :
933 : : /// \name Debug function
934 : : //@{
935 : : /// \brief Print the nodes in the trees.
936 : : ///
937 : : /// \param os A \c std::ostream object to which the tree is printed.
938 : : /// \param depth A factor of the initial indentation. Each line
939 : : /// will begin with space character repeating <code>5 * depth</code>
940 : : /// times.
941 : : void dumpTree(std::ostream& os, unsigned int depth = 0) const;
942 : : //@}
943 : :
944 : : /// \name Modify functions
945 : : //@{
946 : : /// \brief Insert the domain name into the tree.
947 : : ///
948 : : /// It either finds an already existing node of the given name, or inserts
949 : : /// a new one if none exists yet. In any case, the \c inserted_node parameter
950 : : /// is set to point to that node. You can fill data into it or modify it.
951 : : /// So, if you don't know if a node exists or not and you need to modify
952 : : /// it, just call insert and act by the result.
953 : : ///
954 : : /// Please note that the tree can add some empty nodes by itself, so don't
955 : : /// assume that if you didn't insert a node of that name it doesn't exist.
956 : : ///
957 : : /// This method normally involves resource allocation. If it fails
958 : : /// the corresponding standard exception will be thrown.
959 : : ///
960 : : /// This method does not provide the strong exception guarantee in its
961 : : /// strict sense; if an exception is thrown in the middle of this
962 : : /// method, the internal structure may change. However, it should
963 : : /// still retain the same property as a mapping container before this
964 : : /// method is called. For example, the result of \c find() should be
965 : : /// the same. This method provides the weak exception guarantee in its
966 : : /// normal sense.
967 : : ///
968 : : /// \param name The name to be inserted into the tree.
969 : : /// \param inserted_node This is an output parameter and is set to the
970 : : /// node.
971 : : ///
972 : : /// \return
973 : : /// - SUCCESS The node was added.
974 : : /// - ALREADYEXISTS There was already a node of that name, so it was not
975 : : /// added.
976 : : Result insert(const isc::dns::Name& name, RBNode<T>** inserted_node);
977 : :
978 : : /// \brief Swaps two tree's contents.
979 : : ///
980 : : /// This acts the same as many std::*.swap functions, exchanges the
981 : : /// contents. This doesn't throw anything.
982 : : void swap(RBTree<T>& other) {
983 : 1 : std::swap(root_, other.root_);
984 : 1 : std::swap(NULLNODE, other.NULLNODE);
985 : 1 : std::swap(node_count_, other.node_count_);
986 : : }
987 : : //@}
988 : :
989 : : private:
990 : : /// \name RBTree balance functions
991 : : //@{
992 : : void insertRebalance(RBNode<T>** root, RBNode<T>* node);
993 : : RBNode<T>* rightRotate(RBNode<T>** root, RBNode<T>* node);
994 : : RBNode<T>* leftRotate(RBNode<T>** root, RBNode<T>* node);
995 : : //@}
996 : :
997 : : /// \name Helper functions
998 : : //@{
999 : : /// \brief delete tree whose root is equal to node
1000 : : void deleteHelper(RBNode<T> *node);
1001 : :
1002 : : /// \brief Print the information of given RBNode.
1003 : : void dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
1004 : : unsigned int depth) const;
1005 : :
1006 : : /// \brief Indentation helper function for dumpTree
1007 : : static void indent(std::ostream& os, unsigned int depth);
1008 : :
1009 : : /// Split one node into two nodes, keep the old node and create one new
1010 : : /// node, old node will hold the base name, new node will be the down node
1011 : : /// of old node, new node will hold the sub_name, the data
1012 : : /// of old node will be move into new node, and old node became non-terminal
1013 : : void nodeFission(RBNode<T>& node, const isc::dns::Name& sub_name);
1014 : : //@}
1015 : :
1016 : : RBNode<T>* NULLNODE;
1017 : : RBNode<T>* root_;
1018 : : /// the node count of current tree
1019 : : unsigned int node_count_;
1020 : : /// search policy for rbtree
1021 : : const bool needsReturnEmptyNode_;
1022 : : };
1023 : :
1024 : : template <typename T>
1025 : : RBTree<T>::RBTree(bool returnEmptyNode) :
1026 : : NULLNODE(RBNode<T>::NULL_NODE()),
1027 : : root_(NULLNODE),
1028 : : node_count_(0),
1029 [ + - ][ + - ]: 407 : needsReturnEmptyNode_(returnEmptyNode)
[ + - ]
[ + - + - ]
[ + - ]
1030 : : {
1031 : : }
1032 : :
1033 : : template <typename T>
1034 : 265 : RBTree<T>::~RBTree() {
1035 : 423 : deleteHelper(root_);
1036 [ - + ]: 423 : assert(node_count_ == 0);
1037 : 265 : }
1038 : :
1039 : : template <typename T>
1040 : : void
1041 : 2217 : RBTree<T>::deleteHelper(RBNode<T>* root) {
1042 [ + + ]: 2217 : if (root == NULLNODE) {
1043 : 2217 : return;
1044 : : }
1045 : :
1046 : : RBNode<T>* node = root;
1047 [ + + ][ + + ]: 1794 : while (root->left_ != NULLNODE || root->right_ != NULLNODE) {
[ + + ]
1048 [ + + ][ + + ]: 1534 : while (node->left_ != NULLNODE || node->right_ != NULLNODE) {
[ + + ]
1049 [ + + ]: 767 : node = (node->left_ != NULLNODE) ? node->left_ : node->right_;
1050 : : }
1051 : :
1052 : 767 : RBNode<T>* parent = node->parent_;
1053 [ + + ]: 767 : if (parent->left_ == node) {
1054 : 343 : parent->left_ = NULLNODE;
1055 : : } else {
1056 : 424 : parent->right_ = NULLNODE;
1057 : : }
1058 : :
1059 : 767 : deleteHelper(node->down_);
1060 [ + - ]: 767 : delete node;
1061 : 767 : --node_count_;
1062 : 767 : node = parent;
1063 : : }
1064 : :
1065 : 1027 : deleteHelper(root->down_);
1066 [ + - ]: 1027 : delete root;
1067 : 1027 : --node_count_;
1068 : : }
1069 : :
1070 : : template <typename T>
1071 : : template <typename CBARG>
1072 : : typename RBTree<T>::Result
1073 : 1587 : RBTree<T>::find(const isc::dns::Name& target_name,
1074 : : RBNode<T>** target,
1075 : : RBTreeNodeChain<T>& node_path,
1076 : : bool (*callback)(const RBNode<T>&, CBARG),
1077 : : CBARG callback_arg) const
1078 : : {
1079 : : using namespace helper;
1080 : :
1081 [ - + ][ + + ]: 1587 : if (!node_path.isEmpty()) {
1082 [ # # ][ + - ]: 2 : isc_throw(isc::BadValue, "RBTree::find is given a non empty chain");
1083 : : }
1084 : :
1085 : 1586 : RBNode<T>* node = root_;
1086 : 1586 : Result ret = NOTFOUND;
1087 : 3172 : isc::dns::Name name = target_name;
1088 : :
1089 [ + + ][ + + ]: 13348 : while (node != NULLNODE) {
1090 : 13050 : node_path.last_compared_ = node;
1091 [ + - ][ + - ]: 13050 : node_path.last_comparison_ = name.compare(node->name_);
1092 : : const isc::dns::NameComparisonResult::NameRelation relation =
1093 : 13050 : node_path.last_comparison_.getRelation();
1094 : :
1095 [ + + ][ + + ]: 13050 : if (relation == isc::dns::NameComparisonResult::EQUAL) {
1096 [ + + ][ + + ]: 1227 : if (needsReturnEmptyNode_ || !node->isEmpty()) {
[ + + ][ + + ]
[ + + ][ + + ]
1097 : 1222 : node_path.push(node);
1098 : 1222 : *target = node;
1099 : 1222 : ret = EXACTMATCH;
1100 : : }
1101 : : break;
1102 : : } else {
1103 : : const int common_label_count =
1104 : 11823 : node_path.last_comparison_.getCommonLabels();
1105 : : // If the common label count is 1, there is no common label between
1106 : : // the two names, except the trailing "dot". In this case the two
1107 : : // sequences of labels have essentially no hierarchical
1108 : : // relationship in terms of matching, so we should continue the
1109 : : // binary search. One important exception is when the node
1110 : : // represents the root name ("."), in which case the comparison
1111 : : // result must indeed be considered subdomain matching. (We use
1112 : : // getLength() to check if the name is root, which is an equivalent
1113 : : // but cheaper way).
1114 [ + + ][ + + ]: 11823 : if (common_label_count == 1 && node->name_.getLength() != 1) {
[ + + ][ + + ]
[ + + ][ + + ]
1115 [ + + ][ + + ]: 1907 : node = (node_path.last_comparison_.getOrder() < 0) ?
1116 : : node->left_ : node->right_;
1117 [ + + ][ + + ]: 9916 : } else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
1118 [ + + ][ + + ]: 9885 : if (needsReturnEmptyNode_ || !node->isEmpty()) {
[ + + ][ + + ]
[ + + ][ + + ]
1119 : 9766 : ret = PARTIALMATCH;
1120 : 9766 : *target = node;
1121 [ + + ][ + + ]: 9766 : if (callback != NULL &&
[ + + ][ - + ]
[ # # ][ - + ]
1122 : : node->getFlag(RBNode<T>::FLAG_CALLBACK)) {
1123 [ + - ][ + + ]: 149 : if ((callback)(*node, callback_arg)) {
[ # # ][ # # ]
1124 : : break;
1125 : : }
1126 : : }
1127 : : }
1128 : 9855 : node_path.push(node);
1129 [ + - ][ + - ]: 9855 : name = name - node->name_;
1130 : 11762 : node = node->down_;
1131 : : } else {
1132 : : break;
1133 : : }
1134 : : }
1135 : : }
1136 : :
1137 : 1586 : return (ret);
1138 : : }
1139 : :
1140 : : template <typename T>
1141 : : const RBNode<T>*
1142 : 21 : RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const {
1143 [ + + ]: 21 : if (node_path.isEmpty()) {
1144 [ + - ]: 2 : isc_throw(isc::BadValue, "RBTree::nextNode is given an empty chain");
1145 : : }
1146 : :
1147 : 20 : const RBNode<T>* node = node_path.top();
1148 : : // if node has sub domain, the next domain is the smallest
1149 : : // domain in sub domain tree
1150 [ + + ]: 20 : if (node->down_ != NULLNODE) {
1151 : 7 : const RBNode<T>* left_most = node->down_;
1152 [ + + ]: 9 : while (left_most->left_ != NULLNODE) {
1153 : 2 : left_most = left_most->left_;
1154 : : }
1155 : 7 : node_path.push(left_most);
1156 : 7 : return (left_most);
1157 : : }
1158 : :
1159 : : // try to find a successor.
1160 : : // if no successor found move to up level, the next successor
1161 : : // is the successor of up node in the up level tree, if
1162 : : // up node doesn't have successor we gonna keep moving to up
1163 : : // level
1164 [ + + ]: 40 : while (!node_path.isEmpty()) {
1165 : 20 : const RBNode<T>* up_node_successor = node_path.top()->successor();
1166 : 20 : node_path.pop();
1167 [ + + ]: 20 : if (up_node_successor != NULLNODE) {
1168 : 8 : node_path.push(up_node_successor);
1169 : 21 : return (up_node_successor);
1170 : : }
1171 : : }
1172 : :
1173 : : return (NULL);
1174 : : }
1175 : :
1176 : : template <typename T>
1177 : : const RBNode<T>*
1178 : 138 : RBTree<T>::previousNode(RBTreeNodeChain<T>& node_path) const {
1179 [ + + ]: 138 : if (getNodeCount() == 0) {
1180 : : // Special case for empty trees. It would look every time like
1181 : : // we didn't search, because the last compared is empty. This is
1182 : : // a slight hack and not perfect, but this is better than throwing
1183 : : // on empty tree. And we probably won't meet an empty tree in practice
1184 : : // anyway.
1185 : : return (NULL);
1186 : : }
1187 [ + + ]: 137 : if (node_path.last_compared_ == NULL) {
1188 [ + - ]: 2 : isc_throw(isc::BadValue,
1189 : : "RBTree::previousNode() called before find()");
1190 : : }
1191 : :
1192 : : // If the relation isn't EQUAL, it means the find was called previously
1193 : : // and didn't find the exact node. Therefore we need to locate the place
1194 : : // to start iterating the chain of domains.
1195 : : //
1196 : : // The logic here is not too complex, we just need to take care to handle
1197 : : // all the cases and decide where to go from there.
1198 [ + + + ]: 136 : switch (node_path.last_comparison_.getRelation()) {
1199 : : case dns::NameComparisonResult::COMMONANCESTOR:
1200 : : // We compared with a leaf in the tree and wanted to go to one of
1201 : : // the children. But the child was not there. It now depends on the
1202 : : // direction in which we wanted to go.
1203 [ + + ]: 15 : if (node_path.last_comparison_.getOrder() < 0) {
1204 : : // We wanted to go left. So the one we compared with is
1205 : : // the one higher than we wanted. If we just put it into
1206 : : // the node_path, then the following algorithm below will find
1207 : : // the smaller one.
1208 : : //
1209 : : // This is exactly the same as with superdomain below.
1210 : : // Therefore, we just fall through to the next case.
1211 : : } else {
1212 : : // We wanted to go right. That means we want to output the
1213 : : // one which is the largest in the tree defined by the
1214 : : // compared one (it is either the compared one, or some
1215 : : // subdomain of it). There probably is not an easy trick
1216 : : // for this, so we just find the correct place.
1217 : 9 : const RBNode<T>* current(node_path.last_compared_);
1218 [ + + ]: 22 : while (current != NULLNODE) {
1219 : 13 : node_path.push(current);
1220 : : // Go a level down and as much right there as possible
1221 : 13 : current = current->down_;
1222 [ - + ]: 13 : while (current->right_ != NULLNODE) {
1223 : : // A small trick. The current may be NULLNODE, but
1224 : : // such node has the right_ pointer and it is equal
1225 : : // to NULLNODE.
1226 : 0 : current = current->right_;
1227 : : }
1228 : : }
1229 : : // Now, the one on top of the path is the one we want. We
1230 : : // return it now and leave it there, so we can search for
1231 : : // previous of it the next time we'are called.
1232 : 9 : node_path.last_comparison_ =
1233 : : dns::NameComparisonResult(0, 0,
1234 : : dns::NameComparisonResult::EQUAL);
1235 : 9 : return (node_path.top());
1236 : : }
1237 : : // No break; here - we want to fall through. See above.
1238 : : case dns::NameComparisonResult::SUPERDOMAIN:
1239 : : // This is the case there's a "compressed" node and we looked for
1240 : : // only part of it. The node itself is larger than we wanted, but
1241 : : // if we put it to the node_path and then go one step left from it,
1242 : : // we get the correct result.
1243 : 8 : node_path.push(node_path.last_compared_);
1244 : : // Correct the comparison result, so we won't trigger this case
1245 : : // next time previousNode is called. We already located the correct
1246 : : // place to start. The value is partly nonsense, but that doesn't
1247 : : // matter any more.
1248 : 8 : node_path.last_comparison_ =
1249 : : dns::NameComparisonResult(0, 0,
1250 : : dns::NameComparisonResult::EQUAL);
1251 : 8 : break;
1252 : : case dns::NameComparisonResult::SUBDOMAIN:
1253 : : // A subdomain means we returned the one above the searched one
1254 : : // already and it is on top of the stack. This is was smaller
1255 : : // than the one already, but we want to return yet smaller one.
1256 : : // So we act as if it was EQUAL.
1257 : : break;
1258 : : case dns::NameComparisonResult::EQUAL:
1259 : : // The find gave us an exact match or the previousNode was called
1260 : : // already, which located the exact node. The rest of the function
1261 : : // goes one domain left and returns it for us.
1262 : : break;
1263 : : }
1264 : :
1265 : : // So, the node_path now contains the path to a node we want previous for.
1266 : : // We just need to go one step left.
1267 : :
1268 [ + + ]: 127 : if (node_path.isEmpty()) {
1269 : : // We got past the first one. So, we're returning NULL from
1270 : : // now on.
1271 : : return (NULL);
1272 : : }
1273 : :
1274 : 119 : const RBNode<T>* node(node_path.top());
1275 : :
1276 : : // Try going left in this tree
1277 : 119 : node = node->predecessor();
1278 [ + + ]: 119 : if (node == NULLNODE) {
1279 : : // We are the smallest ones in this tree. We go one level
1280 : : // up. That one is the smaller one than us.
1281 : :
1282 : 62 : node_path.pop();
1283 [ + + ]: 62 : if (node_path.isEmpty()) {
1284 : : // We're past the first one
1285 : : return (NULL);
1286 : : } else {
1287 : 52 : return (node_path.top());
1288 : : }
1289 : : }
1290 : :
1291 : : // Exchange the node at the top of the path, as we move horizontaly
1292 : : // through the domain tree
1293 : 57 : node_path.pop();
1294 : 57 : node_path.push(node);
1295 : :
1296 : : // Try going as deep as possible, keeping on the right side of the trees
1297 [ + + ]: 153 : while (node->down_ != NULLNODE) {
1298 : : // Move to the tree below
1299 : 16 : node = node->down_;
1300 : : // And get as much to the right of the tree as possible
1301 [ + + ]: 23 : while (node->right_ != NULLNODE) {
1302 : 7 : node = node->right_;
1303 : : }
1304 : : // Now, we found the right-most node in the sub-tree, we need to
1305 : : // include it in the path
1306 : 16 : node_path.push(node);
1307 : : }
1308 : :
1309 : : // Now, if the current node has no down_ pointer any more, it's the
1310 : : // correct one.
1311 : : return (node);
1312 : : }
1313 : :
1314 : : template <typename T>
1315 : : typename RBTree<T>::Result
1316 : 2163 : RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
1317 : : using namespace helper;
1318 : 2163 : RBNode<T>* parent = NULLNODE;
1319 : 2163 : RBNode<T>* current = root_;
1320 : 2163 : RBNode<T>* up_node = NULLNODE;
1321 : 2163 : isc::dns::Name name = target_name;
1322 : :
1323 : 2163 : int order = -1;
1324 [ + + ]: 15466 : while (current != NULLNODE) {
1325 : : const isc::dns::NameComparisonResult compare_result =
1326 [ + - ]: 13795 : name.compare(current->name_);
1327 : : const isc::dns::NameComparisonResult::NameRelation relation =
1328 : 13795 : compare_result.getRelation();
1329 [ + + ]: 13795 : if (relation == isc::dns::NameComparisonResult::EQUAL) {
1330 [ + - ]: 492 : if (new_node != NULL) {
1331 : 492 : *new_node = current;
1332 : : }
1333 : : return (ALREADYEXISTS);
1334 : : } else {
1335 : 13303 : const int common_label_count = compare_result.getCommonLabels();
1336 : : // Note: see find() for the check of getLength().
1337 [ + + ][ + + ]: 13303 : if (common_label_count == 1 && current->name_.getLength() != 1) {
[ + + ]
1338 : 3220 : parent = current;
1339 : 3220 : order = compare_result.getOrder();
1340 [ + + ]: 3220 : current = order < 0 ? current->left_ : current->right_;
1341 : : } else {
1342 : : // insert sub domain to sub tree
1343 [ + + ]: 10083 : if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
1344 : 9960 : parent = NULLNODE;
1345 : 9960 : up_node = current;
1346 [ + - ]: 9960 : name = name - current->name_;
1347 : 9960 : current = current->down_;
1348 : : } else {
1349 : : // The number of labels in common is fewer
1350 : : // than the number of labels at the current
1351 : : // node, so the current node must be adjusted
1352 : : // to have just the common suffix, and a down
1353 : : // pointer made to a new tree.
1354 : : const isc::dns::Name common_ancestor = name.split(
1355 : : name.getLabelCount() - common_label_count,
1356 [ + - ]: 13426 : common_label_count);
1357 [ + - ]: 123 : nodeFission(*current, common_ancestor);
1358 : : }
1359 : : }
1360 : : }
1361 : : }
1362 : :
1363 : : RBNode<T>** current_root = (up_node != NULLNODE) ?
1364 [ + + ]: 1671 : &(up_node->down_) : &root_;
1365 : : // using auto_ptr here is avoid memory leak in case of exceptoin raised
1366 : : // after the RBNode creation, if we can make sure no exception will be
1367 : : // raised until the end of the function, we can remove it for optimization
1368 [ + - ][ + - ]: 3342 : std::auto_ptr<RBNode<T> > node(new RBNode<T>(name));
[ + - ]
1369 : 1671 : node->parent_ = parent;
1370 [ + + ]: 1671 : if (parent == NULLNODE) {
1371 : 904 : *current_root = node.get();
1372 : : //node is the new root of sub tree, so its init color
1373 : : // is BLACK
1374 : 904 : node->color_ = RBNode<T>::BLACK;
1375 [ + + ]: 767 : } else if (order < 0) {
1376 : 203 : parent->left_ = node.get();
1377 : : } else {
1378 : 564 : parent->right_ = node.get();
1379 : : }
1380 : 1671 : insertRebalance(current_root, node.get());
1381 [ + - ]: 1671 : if (new_node != NULL) {
1382 : 1671 : *new_node = node.get();
1383 : : }
1384 : :
1385 : 1671 : ++node_count_;
1386 : : node.release();
1387 : : return (SUCCESS);
1388 : : }
1389 : :
1390 : :
1391 : : // Note: when we redesign this (still keeping the basic concept), we should
1392 : : // change this part so the newly created node will be used for the inserted
1393 : : // name (and therefore the name for the existing node doesn't change).
1394 : : // Otherwise, things like shortcut links between nodes won't work.
1395 : : template <typename T>
1396 : : void
1397 : 123 : RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
1398 : : using namespace helper;
1399 : 123 : const isc::dns::Name sub_name = node.name_ - base_name;
1400 : : // using auto_ptr here is to avoid memory leak in case of exception raised
1401 : : // after the RBNode creation
1402 [ + - ][ + - ]: 246 : std::auto_ptr<RBNode<T> > down_node(new RBNode<T>(sub_name));
[ + - ]
1403 [ + - ]: 123 : node.name_ = base_name;
1404 : : // the rest of this function should be exception free so that it keeps
1405 : : // consistent behavior (i.e., a weak form of strong exception guarantee)
1406 : : // even if code after the call to this function throws an exception.
1407 : 123 : std::swap(node.data_, down_node->data_);
1408 : 123 : std::swap(node.flags_, down_node->flags_);
1409 : 123 : down_node->down_ = node.down_;
1410 : 123 : node.down_ = down_node.get();
1411 : : // root node of sub tree, the initial color is BLACK
1412 : 123 : down_node->color_ = RBNode<T>::BLACK;
1413 : 123 : ++node_count_;
1414 : : down_node.release();
1415 : 123 : }
1416 : :
1417 : :
1418 : : template <typename T>
1419 : : void
1420 : 1671 : RBTree<T>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
1421 : :
1422 : : RBNode<T>* uncle;
1423 [ + + ][ + + ]: 2164 : while (node != *root && node->parent_->color_ == RBNode<T>::RED) {
[ + + ]
1424 [ + + ]: 493 : if (node->parent_ == node->parent_->parent_->left_) {
1425 : 101 : uncle = node->parent_->parent_->right_;
1426 : :
1427 [ + + ]: 101 : if (uncle->color_ == RBNode<T>::RED) {
1428 : 54 : node->parent_->color_ = RBNode<T>::BLACK;
1429 : 54 : uncle->color_ = RBNode<T>::BLACK;
1430 : 54 : node->parent_->parent_->color_ = RBNode<T>::RED;
1431 : 54 : node = node->parent_->parent_;
1432 : : } else {
1433 [ + + ]: 47 : if (node == node->parent_->right_) {
1434 : 2 : node = node->parent_;
1435 : : leftRotate(root, node);
1436 : : }
1437 : 47 : node->parent_->color_ = RBNode<T>::BLACK;
1438 : 47 : node->parent_->parent_->color_ = RBNode<T>::RED;
1439 : 47 : rightRotate(root, node->parent_->parent_);
1440 : : }
1441 : : } else {
1442 : 392 : uncle = node->parent_->parent_->left_;
1443 [ + + ]: 392 : if (uncle->color_ == RBNode<T>::RED) {
1444 : 123 : node->parent_->color_ = RBNode<T>::BLACK;
1445 : 123 : uncle->color_ = RBNode<T>::BLACK;
1446 : 123 : node->parent_->parent_->color_ = RBNode<T>::RED;
1447 : 123 : node = node->parent_->parent_;
1448 : : } else {
1449 [ + + ]: 269 : if (node == node->parent_->left_) {
1450 : 63 : node = node->parent_;
1451 : : rightRotate(root, node);
1452 : : }
1453 : 269 : node->parent_->color_ = RBNode<T>::BLACK;
1454 : 269 : node->parent_->parent_->color_ = RBNode<T>::RED;
1455 : 269 : leftRotate(root, node->parent_->parent_);
1456 : : }
1457 : : }
1458 : : }
1459 : :
1460 : 1671 : (*root)->color_ = RBNode<T>::BLACK;
1461 : 1671 : }
1462 : :
1463 : :
1464 : : template <typename T>
1465 : : RBNode<T>*
1466 : 0 : RBTree<T>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
1467 : 271 : RBNode<T>* right = node->right_;
1468 : 271 : node->right_ = right->left_;
1469 [ # # ][ - + ]: 271 : if (right->left_ != NULLNODE)
[ + + ]
1470 : 34 : right->left_->parent_ = node;
1471 : :
1472 : 271 : right->parent_ = node->parent_;
1473 : :
1474 [ # # ][ + - ]: 271 : if (node->parent_ != NULLNODE) {
[ + + ]
1475 [ # # ][ + - ]: 146 : if (node == node->parent_->left_) {
[ + + ]
1476 : 27 : node->parent_->left_ = right;
1477 : : } else {
1478 : 119 : node->parent_->right_ = right;
1479 : : }
1480 : : } else {
1481 : 125 : *root = right;
1482 : : }
1483 : :
1484 : 271 : right->left_ = node;
1485 : 495 : node->parent_ = right;
1486 : 0 : return (node);
1487 : : }
1488 : :
1489 : : template <typename T>
1490 : : RBNode<T>*
1491 : 0 : RBTree<T>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
1492 : 110 : RBNode<T>* left = node->left_;
1493 : 110 : node->left_ = left->right_;
1494 [ # # ][ + + ]: 110 : if (left->right_ != NULLNODE)
[ - + ]
1495 : 13 : left->right_->parent_ = node;
1496 : :
1497 : 110 : left->parent_ = node->parent_;
1498 : :
1499 [ # # ][ + + ]: 110 : if (node->parent_ != NULLNODE) {
[ + - ]
1500 [ # # ][ + + ]: 66 : if (node == node->parent_->right_) {
[ + - ]
1501 : 64 : node->parent_->right_ = left;
1502 : : } else {
1503 : 2 : node->parent_->left_ = left;
1504 : : }
1505 : : } else {
1506 : 44 : *root = left;
1507 : : }
1508 : 110 : left->right_ = node;
1509 : 110 : node->parent_ = left;
1510 : 0 : return (node);
1511 : : }
1512 : :
1513 : :
1514 : : template <typename T>
1515 : : void
1516 : 5 : RBTree<T>::dumpTree(std::ostream& os, unsigned int depth) const {
1517 : 5 : indent(os, depth);
1518 : 10 : os << "tree has " << node_count_ << " node(s)\n";
1519 : 5 : dumpTreeHelper(os, root_, depth);
1520 : 5 : }
1521 : :
1522 : : template <typename T>
1523 : : void
1524 : 108 : RBTree<T>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
1525 : : unsigned int depth) const
1526 : : {
1527 [ + + ]: 108 : if (node == NULLNODE) {
1528 : 64 : indent(os, depth);
1529 : 64 : os << "NULL\n";
1530 : 108 : return;
1531 : : }
1532 : :
1533 : 44 : indent(os, depth);
1534 [ + + ][ + - ]: 44 : os << node->name_.toText() << " ("
[ + - ][ + - ]
[ + - ]
1535 : : << ((node->color_ == RBNode<T>::BLACK) ? "black" : "red") << ")";
1536 [ + + ]: 44 : os << ((node->isEmpty()) ? "[invisible] \n" : "\n");
1537 : :
1538 [ + + ]: 44 : if (node->down_ != NULLNODE) {
1539 : 15 : indent(os, depth + 1);
1540 [ + - ][ + - ]: 15 : os << "begin down from " << node->name_.toText() << "\n";
[ + - ]
1541 : 15 : dumpTreeHelper(os, node->down_, depth + 1);
1542 : 15 : indent(os, depth + 1);
1543 [ + - ][ + - ]: 15 : os << "end down from " << node->name_.toText() << "\n";
[ + - ]
1544 : : }
1545 : 44 : dumpTreeHelper(os, node->left_, depth + 1);
1546 : 44 : dumpTreeHelper(os, node->right_, depth + 1);
1547 : : }
1548 : :
1549 : : template <typename T>
1550 : : void
1551 : 143 : RBTree<T>::indent(std::ostream& os, unsigned int depth) {
1552 : : static const unsigned int INDENT_FOR_EACH_DEPTH = 5;
1553 [ + - ]: 143 : os << std::string(depth * INDENT_FOR_EACH_DEPTH, ' ');
1554 : 143 : }
1555 : :
1556 : : }
1557 : : }
1558 : :
1559 : : #endif // _RBTREE_H
1560 : :
1561 : : // Local Variables:
1562 : : // mode: c++
1563 : : // End:
|
