domaintree.h 78.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Copyright (C) 2010  Internet Systems Consortium, Inc. ("ISC")
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

#ifndef _DOMAINTREE_H
#define _DOMAINTREE_H 1

//! \file datasrc/memory/domaintree.h
///
/// \note The purpose of the DomainTree is to provide a generic map with
21
22
23
24
25
///     domain names as the key that can be used by various BIND 10
///     modules or even by other applications.  However, because of some
///     unresolved design issue, the design and interface are not fixed,
///     and DomainTree isn't ready to be used as a base data structure
///     by other modules.
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <exceptions/exceptions.h>
#include <util/memory_segment.h>
#include <dns/name.h>
#include <dns/labelsequence.h>

#include <boost/utility.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/interprocess/offset_ptr.hpp>
#include <boost/static_assert.hpp>

#include <ostream>
#include <algorithm>
#include <cassert>

namespace isc {
namespace datasrc {
namespace memory {

45
46
/// Forward declare DomainTree class here is convinent for following
/// friend class declare inside DomainTreeNode and DomainTreeNodeChain
47
template <typename T, typename DT>
48
49
class DomainTree;

50
51
/// \brief \c DomainTreeNode is used by DomainTree to store any data
///     related to one domain name.
52
///
53
54
55
/// This is meant to be used only from DomainTree. It is meaningless to
/// inherit it or create instances of it from elsewhere. For that
/// reason, the constructor (and the allocator, see below) is private.
56
///
57
58
59
60
/// It serves three roles. One is to keep structure of the \c DomainTree
/// as a red-black tree. For that purpose, it has left, right and parent
/// pointers and color member. These are private and accessed only from
/// within the tree.
61
///
62
63
/// The second one is to store data for one domain name. The data
/// related functions can be used to access and set the data.
64
65
66
67
68
///
/// The third role is to keep the hierarchy of domains. The down pointer
/// points to a subtree of subdomains. The parent pointer of a subtree's
/// root node points to the parent leaf of the upper tree.
///
69
70
/// One special kind of node is non-terminal node. It has subdomains
/// with RRsets, but doesn't have any RRsets itself.
71
///
72
73
74
75
76
77
78
79
80
/// In order to keep memory footprint as small as possible, the node
/// data are heavily packed.  Specifically, some internal node
/// properties (such as the node color) are encoded as part of "flags",
/// some of the flag bits can also be set by the user application.  Each
/// node is associated with a sequence of domain name labels, which is
/// essentially the search/insert key for the node (see also the
/// description of DomainTree).  This is encoded as opaque binary
/// immediately following the main node object.  The size of the
/// allocated space for the labels data is encoded by borrowing some
81
/// bits of the "flags" field.
82
template <typename T, typename DT>
83
84
class DomainTreeNode : public boost::noncopyable {
private:
85
86
    /// The DomainTreeNode is meant for use from within DomainTree, so
    /// it has access to it.
87
    friend class DomainTree<T, DT>;
88
89
90
91
92

    /// \brief Just a type alias
    ///
    /// We are going to use a lot of these offset pointers here and they
    /// have a long name.
93
    typedef boost::interprocess::offset_ptr<DomainTreeNode<T, DT> >
94
        DomainTreeNodePtr;
95
96
97

    /// \name Constructors
    ///
98
99
    /// \note The existence of a DomainTreeNode without a DomainTree is
    ///     meaningless.  Therefore the constructors are private.
100
101
102
103
104
105
106
107
108
109
110
111
    //@{

    /// \brief Constructor from normal nodes.
    DomainTreeNode(size_t labels_capacity);

    /// \brief Destructor
    ~DomainTreeNode();

    //@}

    /// \brief Accessor to the memory region for node labels.
    ///
112
113
    /// The only valid usage of the returned pointer is to pass it to
    /// the corresponding constructor of \c dns::LabelSequence.
114
115
116
117
118
119
120
121
122
123
124
125
    const void* getLabelsData() const { return (this + 1); }

    /// \brief Accessor to the memory region for node labels, mutable version.
    ///
    /// The only valid usage of the returned pointer is to pass it to
    /// \c LabelSequence::serialize() with the node's labels_capacity_ member
    /// (which should be sufficiently large for the \c LabelSequence in that
    /// context).
    void* getLabelsData() { return (this + 1); }

    /// \brief Allocate and construct \c DomainTreeNode
    ///
126
127
128
    /// This static method allocates memory for a new \c DomainTreeNode
    /// object from the given memory segment, constructs the object, and
    /// returns a pointer to it.
129
130
131
132
133
    ///
    /// \throw std::bad_alloc Memory allocation fails.
    ///
    /// \param mem_sgmt A \c MemorySegment from which memory for the new
    /// \c DomainTreeNode is allocated.
134
    static DomainTreeNode<T, DT>* create(util::MemorySegment& mem_sgmt,
135
136
137
                             const dns::LabelSequence& labels)
    {
        const size_t labels_len = labels.getSerializedLength();
138
139
        void* p = mem_sgmt.allocate(sizeof(DomainTreeNode<T, DT>) + labels_len);
        DomainTreeNode<T, DT>* node = new(p) DomainTreeNode<T, DT>(labels_len);
140
141
142
143
144
145
146
147
148
        labels.serialize(node->getLabelsData(), labels_len);
        return (node);
    }

    /// \brief Destruct and deallocate \c DomainTreeNode
    ///
    /// \throw none
    ///
    /// \param mem_sgmt The \c MemorySegment that allocated memory for
149
150
    /// \c node.
    /// \param node A non NULL pointer to a valid \c DomainTreeNode object
151
152
    /// that was originally created by the \c create() method (the behavior
    /// is undefined if this condition isn't met).
153
    static void destroy(util::MemorySegment& mem_sgmt,
154
155
156
157
                        DomainTreeNode<T, DT>* node) {
        const size_t labels_capacity = node->labels_capacity_;
        node->~DomainTreeNode<T, DT>();
        mem_sgmt.deallocate(node,
158
                            sizeof(DomainTreeNode<T, DT>) + labels_capacity);
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
    }

    /// \brief Reset node's label sequence to a new one.
    ///
    /// The new labels must be a sub sequence of the current label sequence;
    /// otherwise the serialize() method will throw an exception.
    void resetLabels(const dns::LabelSequence& labels) {
        labels.serialize(getLabelsData(), labels_capacity_);
    }

public:
    /// Node flags.
    ///
    /// Each flag value defines a non default property for a specific node.
    /// These are defined as bitmask type values for the convenience of
    /// internal implementation, but applications are expected to use
    /// each flag separately via the enum definitions.
    ///
    /// All (settable) flags are off by default; they must be explicitly
    /// set to on by the \c setFlag() method.
    enum Flags {
        FLAG_CALLBACK = 1, ///< Callback enabled. See \ref callback
        FLAG_RED = 2, ///< Node color; 1 if node is red, 0 if node is black.
        FLAG_SUBTREE_ROOT = 4, ///< Set if the node is the root of a subtree
        FLAG_USER1 = 0x400000U, ///< Application specific flag
        FLAG_USER2 = 0x200000U, ///< Application specific flag
        FLAG_USER3 = 0x100000U, ///< Application specific flag
        FLAG_MAX = 0x400000U    // for integrity check
    };
private:
    // Some flag values are expected to be used for internal purposes
    // (e.g., representing the node color) in future versions, so we
    // limit the settable flags via the \c setFlag() method to those
    // explicitly defined in \c Flags.  This constant represents all
    // such flags.
    static const uint32_t SETTABLE_FLAGS = (FLAG_CALLBACK | FLAG_USER1 |
                                            FLAG_USER2 | FLAG_USER3);

public:

    /// \name Getter functions.
    //@{
    /// \brief Return the name of current node.
    ///
    /// It's relative to its containing node.
    ///
    /// To get the absolute name of one node, the node path from the top node
    /// to current node has to be recorded.
    ///
    /// \note We should eventually deprecate this method and revise all its
    /// usage with \c getLabels().  At this point the only user of this method
    /// is getAbsoluteName()::getAbsoluteName(), which would have to be revised
    /// using \c LabelSequence.  Until then we keep this interface as a
    /// simplest form of wrapper; it's not efficient, but should be replaced
    /// before we need to worry about that.
    const isc::dns::Name getName() const {
        return (dns::Name(dns::LabelSequence(getLabelsData()).toText()));
    }

    /// \brief Return the label sequence of the node.
    ///
    /// This method returns the label sequence corresponding to this node
    /// in the form of \c dns::LabelSequence object.  Any modification to
    /// the tree can invalidate the returned \c LabelSequence object or copy
    /// of it; in general, it's expected to be used in a very limited scope.
    dns::LabelSequence getLabels() const {
        return (dns::LabelSequence(getLabelsData()));
    }

    /// \brief Return the data stored in this node.
    ///
230
231
    /// You should not delete the data, it is deleted when the tree is
    /// destroyed.
232
    T* getData() { return (data_.get()); }
233
234

    /// \brief Return the data stored in this node (const).
235
    const T* getData() const { return (data_.get()); }
236
237
238
239
240
241

    /// \brief return whether the node has related data.
    ///
    /// There can be empty nodes inside the DomainTree. They are usually the
    /// non-terminal domains, but it is possible (yet probably meaningless)
    /// empty nodes anywhere.
242
    bool isEmpty() const { return (!data_); }
243
244
245
246
    //@}

    /// \name Setter functions.
    //@{
247

248
249
250
    /// \brief Set the data stored in the node. If there is old data, it
    /// is either returned or destroyed based on what is passed in \c
    /// old_data.
251
252
    /// \param mem_sgmt The \c MemorySegment that allocated memory for
    ///                 the node data.
253
254
255
256
    /// \param data The new data to set.
    /// \param old_data If \c NULL is passed here, any old data is
    ///                 destroyed. Otherwise, the old data is returned
    ///                 in this location.
257
    void setData(util::MemorySegment& mem_sgmt, T* data, T** old_data = NULL) {
258
259
260
261
        if (old_data != NULL) {
            *old_data = data;
        } else {
            const DT deleter;
262
            deleter(mem_sgmt, data_.get());
263
        }
264
265
        data_ = data;
    }
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
    //@}

    /// \name Node flag manipulation methods
    //@{
    /// Get the status of a node flag.
    ///
    /// This method returns whether the given node flag is set (enabled)
    /// on the node.  The \c flag parameter is expected to be one of the
    /// defined \c Flags constants.  For simplicity, the method interface
    /// does not prohibit passing an undefined flag or combined flags, but
    /// the return value in such a case will be meaningless for the caller
    /// (an application would have to use an ugly cast for such an unintended
    /// form of call, which will hopefully avoid accidental misuse).
    ///
    /// \exception None
    /// \param flag The flag to be tested.
    /// \return \c true if the \c flag is set; \c false otherwise.
    bool getFlag(Flags flag) const {
        return ((flags_ & flag) != 0);
    }

    /// Set or clear a node flag.
    ///
    /// This method changes the status of the specified node flag to either
    /// "on" (enabled) or "off" (disabled).  The new status is specified by
    /// the \c on parameter.
    /// Like the \c getFlag() method, \c flag is expected to be one of the
    /// defined \c Flags constants.  If an undefined or unsettable flag is
    /// specified, \c isc::InvalidParameter exception will be thrown.
    ///
    /// \exception isc::InvalidParameter Unsettable flag is specified
    /// \exception None otherwise
    /// \param flag The node flag to be changed.
    /// \param on If \c true, set the flag to on; otherwise set it to off.
    void setFlag(Flags flag, bool on = true) {
        if ((flag & ~SETTABLE_FLAGS) != 0) {
            isc_throw(isc::InvalidParameter,
                      "Unsettable DomainTree flag is being set");
        }
        if (on) {
            flags_ |= flag;
        } else {
            flags_ &= ~flag;
        }
    }
    //@}

private:
    /// \name Callback related methods
    ///
316
    /// See the description of \c DomainTree<T, DT>::find() at \ref callback
317
318
319
320
321
322
323
324
    /// about callbacks.
    ///
    /// These methods never throw an exception.
    //@{
    /// Return if callback is enabled at the node.
    //@}


325
    /// \brief Define node color
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
    enum DomainTreeNodeColor {BLACK, RED};

    /// \brief Returns the color of this node
    DomainTreeNodeColor getColor() const {
        if ((flags_ & FLAG_RED) != 0) {
            return (RED);
        } else {
            return (BLACK);
        }
    }

    /// \brief Sets the color of this node
    void setColor(const DomainTreeNodeColor color) {
        if (color == RED) {
            flags_ |= FLAG_RED;
        } else {
            flags_ &= ~FLAG_RED;
        }
    }

    void setSubTreeRoot(bool root) {
        if (root) {
            flags_ |= FLAG_SUBTREE_ROOT;
        } else {
            flags_ &= ~FLAG_SUBTREE_ROOT;
        }
    }

    bool isSubTreeRoot() const {
        return ((flags_ & FLAG_SUBTREE_ROOT) != 0);
    }

public:
    /// \brief returns the parent of the root of its subtree
    ///
    /// This method takes a node and returns the parent of the root of
    /// its subtree (i.e, it returns the node's immediate ancestor in
    /// the tree-of-tree hierarchy). If the node is at the top level
    /// (which should be absolute), it will return \c NULL.
    ///
    /// This method never throws an exception.
367
    const DomainTreeNode<T, DT>* getUpperNode() const;
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384

private:
    /// \brief return the next node which is bigger than current node
    /// in the same subtree
    ///
    /// The next successor for this node is the next bigger node in terms of
    /// the DNSSEC order relation within the same single subtree.
    /// Note that it may NOT be the next bigger node in the entire DomainTree;
    ///  DomainTree is a tree in tree, and the real next node may reside in
    /// an upper or lower subtree of the subtree where this node belongs.
    /// For example, if this node has a sub domain, the real next node is
    /// the smallest node in the sub domain tree.
    ///
    /// If this node is the biggest node within the subtree, this method
    /// returns \c NULL.
    ///
    /// This method never throws an exception.
385
    const DomainTreeNode<T, DT>* successor() const;
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401

    /// \brief return the next node which is smaller than current node
    /// in the same subtree
    ///
    /// The predecessor for this node is the next smaller node in terms of
    /// the DNSSEC order relation within the same single subtree.
    /// Note that it may NOT be the next smaller node in the entire DomainTree;
    /// DomainTree is a tree in tree, and the real next node may reside in
    /// an upper or lower subtree of the subtree where this node belongs.
    /// For example, if the predecessor node has a sub domain, the real next
    /// node is the largest node in the sub domain tree.
    ///
    /// If this node is the smallest node within the subtree, this method
    /// returns \c NULL.
    ///
    /// This method never throws an exception.
402
    const DomainTreeNode<T, DT>* predecessor() const;
403
404
405
406
407
408
409
410
411
412
413
414

    /// \brief private shared implementation of successor and predecessor
    ///
    /// As the two mentioned functions are merely mirror images of each other,
    /// it makes little sense to keep both versions. So this is the body of the
    /// functions and we call it with the correct pointers.
    ///
    /// Not to be called directly, not even by friends.
    ///
    /// The overhead of the member pointers should be optimised out, as this
    /// will probably get completely inlined into predecessor and successor
    /// methods.
415
416
417
418
419
    const DomainTreeNode<T, DT>*
        abstractSuccessor(typename DomainTreeNode<T, DT>::DomainTreeNodePtr
                              DomainTreeNode<T, DT>::*left,
                          typename DomainTreeNode<T, DT>::DomainTreeNodePtr
                              DomainTreeNode<T, DT>::*right)
420
421
422
423
424
425
426
427
428
429
430
431
        const;

    /// \name Data to maintain the rbtree structure.
    ///
    /// We keep them as offset pointers. This is part of a future plan, when we
    /// want to share the image of the tree between multiple processes.
    /// However, whenever we have a chance, we switch to bare pointers during
    /// the processing. The pointers on stack are never shared and the offset
    /// pointers have non-trivial performance impact.
    //@{
    DomainTreeNodePtr parent_;
    /// \brief Access the parent_ as bare pointer.
432
    DomainTreeNode<T, DT>* getParent() {
433
434
435
        return (parent_.get());
    }
    /// \brief Access the parent_ as bare pointer, const.
436
    const DomainTreeNode<T, DT>* getParent() const {
437
438
439
440
        return (parent_.get());
    }
    DomainTreeNodePtr left_;
    /// \brief Access the left_ as bare pointer.
441
    DomainTreeNode<T, DT>* getLeft() {
442
443
444
        return (left_.get());
    }
    /// \brief Access the left_ as bare pointer, const.
445
    const DomainTreeNode<T, DT>* getLeft() const {
446
447
448
449
        return (left_.get());
    }
    DomainTreeNodePtr right_;
    /// \brief Access the right_ as bare pointer.
450
    DomainTreeNode<T, DT>* getRight() {
451
452
453
        return (right_.get());
    }
    /// \brief Access the right_ as bare pointer, const.
454
    const DomainTreeNode<T, DT>* getRight() const {
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
        return (right_.get());
    }
    //@}

    /// \brief The subdomain tree.
    ///
    /// This points to the root node of trees of subdomains of this domain.
    ///
    /// \par Adding down pointer to \c DomainTreeNode has two purposes:
    /// \li Accelerate the search process, with sub domain tree, it splits the
    ///     big flat tree into several hierarchy trees.
    /// \li It saves memory usage as it allows storing only relative names,
    ///     avoiding storage of the same domain labels multiple times.
    DomainTreeNodePtr down_;
    /// \brief Access the down_ as bare pointer.
470
    DomainTreeNode<T, DT>* getDown() {
471
472
473
        return (down_.get());
    }
    /// \brief Access the down_ as bare pointer, const.
474
    const DomainTreeNode<T, DT>* getDown() const {
475
476
477
        return (down_.get());
    }

478
    /// \brief Data stored here.
479
    boost::interprocess::offset_ptr<T> data_;
480

481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
    /// \brief Internal or user-configurable flags of node's properties.
    ///
    /// See the \c Flags enum for available flags.
    ///
    /// For memory efficiency reasons, we only use a subset of the 32-bit
    /// space, and use the rest to store the allocated size for the node's
    /// label sequence data.
    uint32_t flags_ : 23;          // largest flag being 0x400000
    BOOST_STATIC_ASSERT((1 << 23) > FLAG_MAX); // assumption check

    const uint32_t labels_capacity_ : 9; // size for labelseq; range is 0..511
    // Make sure the reserved space for labels_capacity_ is sufficiently
    // large.  In effect, we use the knowledge of the implementation of the
    // serialization, but we still only use its public interface, and the
    // public interface of this class doesn't rely on this assumption.
    // So we can change this implementation without affecting its users if
    // a future change to LabelSequence breaks this assumption.
    BOOST_STATIC_ASSERT((1 << 9) > dns::LabelSequence::MAX_SERIALIZED_LENGTH);
};

501
template <typename T, typename DT>
502
DomainTreeNode<T, DT>::DomainTreeNode(size_t labels_capacity) :
503
504
505
506
    parent_(NULL),
    left_(NULL),
    right_(NULL),
    down_(NULL),
507
    data_(NULL),
508
509
510
511
512
    flags_(FLAG_RED | FLAG_SUBTREE_ROOT),
    labels_capacity_(labels_capacity)
{
}

513
template <typename T, typename DT>
514
DomainTreeNode<T, DT>::~DomainTreeNode() {
515
516
}

517
template <typename T, typename DT>
518
519
520
const DomainTreeNode<T, DT>*
DomainTreeNode<T, DT>::getUpperNode() const {
    const DomainTreeNode<T, DT>* current = this;
521
522
523
524
525
526
527
528
529
530

    // current would never be equal to NULL here (in a correct tree
    // implementation)
    while (!current->isSubTreeRoot()) {
        current = current->getParent();
    }

    return (current->getParent());
}

531
template <typename T, typename DT>
532
533
534
535
536
const DomainTreeNode<T, DT>*
DomainTreeNode<T, DT>::abstractSuccessor(typename DomainTreeNode<T, DT>::DomainTreeNodePtr
                                            DomainTreeNode<T, DT>::*left,
                                        typename DomainTreeNode<T, DT>::DomainTreeNodePtr
                                            DomainTreeNode<T, DT>::*right)
537
538
539
540
541
542
543
    const
{
    // This function is written as a successor. It becomes predecessor if
    // the left and right pointers are swapped. So in case of predecessor,
    // the left pointer points to right and vice versa. Don't get confused
    // by the idea, just imagine the pointers look into a mirror.

544
    const DomainTreeNode<T, DT>* current = this;
545
546
547
548
    // If it has right node, the successor is the left-most node of the right
    // subtree.
    if ((current->*right).get() != NULL) {
        current = (current->*right).get();
549
        const DomainTreeNode<T, DT>* left_n;
550
551
552
553
554
555
556
557
558
        while ((left_n = (current->*left).get()) != NULL) {
            current = left_n;
        }
        return (current);
    }

    // Otherwise go up until we find the first left branch on our path to
    // root.  If found, the parent of the branch is the successor.
    // Otherwise, we return the null node
559
    const DomainTreeNode<T, DT>* parent = current->getParent();
560
561
562
563
564
565
566
567
568
569
570
571
572
    while ((!current->isSubTreeRoot()) &&
           (current == (parent->*right).get())) {
        current = parent;
        parent = parent->getParent();
    }

    if (!current->isSubTreeRoot()) {
        return (parent);
    } else {
        return (NULL);
    }
}

573
template <typename T, typename DT>
574
575
576
577
const DomainTreeNode<T, DT>*
DomainTreeNode<T, DT>::successor() const {
    return (abstractSuccessor(&DomainTreeNode<T, DT>::left_,
                              &DomainTreeNode<T, DT>::right_));
578
579
}

580
template <typename T, typename DT>
581
582
const DomainTreeNode<T, DT>*
DomainTreeNode<T, DT>::predecessor() const {
583
    // Swap the left and right pointers for the abstractSuccessor
584
585
    return (abstractSuccessor(&DomainTreeNode<T, DT>::right_,
                              &DomainTreeNode<T, DT>::left_));
586
587
}

588
589
/// \brief DomainTreeNodeChain stores detailed information of \c
/// DomainTree::find() result.
590
591
592
593
594
595
596
597
598
599
600
///
/// - The \c DomainTreeNode that was last compared with the search name, and
///   the comparison result at that point in the form of
///   \c isc::dns::NameComparisonResult.
/// - A sequence of nodes that forms a path to the found node.
///
/// The comparison result can be used to handle some rare cases such as
/// empty node processing.
/// The node sequence keeps track of the nodes to reach any given node from
/// the root of DomainTree.
///
601
602
603
604
605
/// Currently, DomainTreeNode does not have "up" pointers in them (i.e.,
/// back pointers from the root of one level of tree of trees to the
/// node in the parent tree whose down pointer points to that root node)
/// for memory usage reasons, so there is no other way to find the path
/// back to the root from any given DomainTreeNode.
606
607
608
609
610
611
612
613
614
615
///
/// \note This design may change in future versions.  In particular, it's
/// quite likely we want to have that pointer if we want to optimize name
/// compression by exploiting the structure of the zone.  If and when that
/// happens we should also revisit the need for the chaining.
/// Also, the class name may not be appropriate now that it contains other
/// information than a node "chain", and the chain itself may even be
/// deprecated.  Something like "DomainTreeFindContext" may be a better name.
/// This point should be revisited later.
///
616
617
/// DomainTreeNodeChain is constructed and manipulated only inside the
/// \c DomainTree class.
618
619
620
621
/// \c DomainTree uses it as an inner data structure to iterate over the whole
/// DomainTree.
/// This is the reason why manipulation methods such as \c push() and \c pop()
/// are private (and not shown in the doxygen document).
622
template <typename T, typename DT>
623
624
625
class DomainTreeNodeChain {
    /// DomainTreeNodeChain is initialized by DomainTree, only DomainTree has
    /// knowledge to manipulate it.
626
    friend class DomainTree<T, DT>;
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
public:
    /// \name Constructors and Assignment Operator.
    ///
    /// \note The copy constructor and the assignment operator are
    /// intentionally defined as private, making this class non copyable.
    /// This may have to be changed in a future version with newer need.
    /// For now we explicitly disable copy to avoid accidental copy happens
    /// unintentionally.
    //{@
    /// The default constructor.
    ///
    /// \exception None
    DomainTreeNodeChain() : node_count_(0), last_compared_(NULL),
                        // XXX: meaningless initial values:
                        last_comparison_(0, 0,
                                         isc::dns::NameComparisonResult::EQUAL)
    {}

private:
646
647
    DomainTreeNodeChain(const DomainTreeNodeChain<T, DT>&);
    DomainTreeNodeChain<T, DT>& operator=(const DomainTreeNodeChain<T, DT>&);
648
649
650
651
652
653
654
655
656
657
658
659
660
661
    //@}

public:
    /// Clear the state of the chain.
    ///
    /// This method re-initializes the internal state of the chain so that
    /// it can be reused for subsequent operations.
    ///
    /// \exception None
    void clear() {
        node_count_ = 0;
        last_compared_ = NULL;
    }

662
663
664
665
666
667
668
    /// Return the \c DomainTreeNode that was last compared in \c
    /// DomainTree::find().
    ///
    /// If this chain has been passed to \c DomainTree::find() and there
    /// has been name comparison against the search name, the last
    /// compared \c DomainTreeNode is recorded within the chain.  This
    /// method returns that node.
669
    ///
670
671
672
    /// If \c DomainTree::find() hasn't been called with this chain or
    /// name comparison hasn't taken place (which is possible if the
    /// tree is empty), this method returns \c NULL.
673
674
    ///
    /// \exception None
675
    const DomainTreeNode<T, DT>* getLastComparedNode() const {
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
        return (last_compared_);
    }

    /// Return the result of last name comparison in \c DomainTree::find().
    ///
    /// Like \c getLastComparedNode(), \c DomainTree::find() records the result
    /// of the last name comparison in the chain.  This method returns the
    /// result.
    /// The return value of this method is only meaningful when comparison
    /// has taken place, i.e, when \c getLastComparedNode() would return a
    /// non \c NULL value.
    ///
    /// \exception None
    const isc::dns::NameComparisonResult& getLastComparisonResult() const {
        return (last_comparison_);
    }

    /// \brief Return the number of levels stored in the chain.
    ///
    /// It's equal to the number of nodes in the chain; for an empty
    /// chain, 0 will be returned.
    ///
    /// \exception None
    unsigned int getLevelCount() const { return (node_count_); }

    /// \brief return the absolute name for the node which this
    /// \c DomainTreeNodeChain currently refers to.
    ///
    /// The chain must not be empty.
    ///
    /// \exception isc::BadValue the chain is empty.
    /// \exception std::bad_alloc memory allocation for the new name fails.
    isc::dns::Name getAbsoluteName() const {
        if (isEmpty()) {
            isc_throw(isc::BadValue,
711
712
                      "DomainTreeNodeChain::getAbsoluteName is "
                      "called on an empty chain");
713
714
        }

715
        const DomainTreeNode<T, DT>* top_node = top();
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
        isc::dns::Name absolute_name = top_node->getName();
        int node_count = node_count_ - 1;
        while (node_count > 0) {
            top_node = nodes_[node_count - 1];
            absolute_name = absolute_name.concatenate(top_node->getName());
            --node_count;
        }
        return (absolute_name);
    }

private:
    // the following private functions check invariants about the internal
    // state using assert() instead of exception.  The state of a chain
    // can only be modified by operations within this file, so if any of the
    // assumptions fails it means an internal bug.

    /// \brief return whether node chain has node in it.
    ///
    /// \exception None
    bool isEmpty() const { return (node_count_ == 0); }

    /// \brief return the top node for the node chain
    ///
    /// DomainTreeNodeChain store all the nodes along top node to
    /// root node of DomainTree
    ///
    /// \exception None
743
    const DomainTreeNode<T, DT>* top() const {
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
        assert(!isEmpty());
        return (nodes_[node_count_ - 1]);
    }

    /// \brief pop the top node from the node chain
    ///
    /// After pop, up/super node of original top node will be
    /// the top node
    ///
    /// \exception None
    void pop() {
        assert(!isEmpty());
        --node_count_;
    }

    /// \brief add the node into the node chain
    ///
    /// If the node chain isn't empty, the node should be
    /// the sub domain of the original top node in node chain
    /// otherwise the node should be the root node of DomainTree.
    ///
    /// \exception None
766
    void push(const DomainTreeNode<T, DT>* node) {
767
768
769
770
771
        assert(node_count_ < RBT_MAX_LEVEL);
        nodes_[node_count_++] = node;
    }

private:
772
773
774
    // The max label count for one domain name is Name::MAX_LABELS
    // (128).  Since each node in domaintree stores at least one label,
    // it's also equal to the possible maximum level.
775
776
777
    const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS;

    int node_count_;
778
779
    const DomainTreeNode<T, DT>* nodes_[RBT_MAX_LEVEL];
    const DomainTreeNode<T, DT>* last_compared_;
780
781
782
783
784
785
786
787
788
789
790
    isc::dns::NameComparisonResult last_comparison_;
};


// note: the following class description is documented using multiline comments
// because the verbatim diagram contain a backslash, which could be interpreted
// as escape of newline in singleline comment.
/**
 *  \brief \c DomainTree class represents all the domains with the same suffix.
 *      It can be used to store the domains in one zone, for example.
 *
791
792
793
794
795
 *  DomainTree is a generic map from domain names to any kind of
 *  data. Internally, it uses a red-black tree. However, it isn't one
 *  tree containing everything.  Subdomains are trees, so this structure
 *  is recursive - trees inside trees.  But, from the interface point of
 *  view, it is opaque data structure.
796
797
798
 *
 *  \c DomainTree splits the domain space into hierarchy red black trees; nodes
 * in one tree has the same base name. The benefit of this struct is that:
799
 *  - Enhances the query performance compared with one big flat red black tree.
800
801
802
 *  - Decreases the memory footprint, as it doesn't store the suffix labels
 *      multiple times.
 *
803
804
805
806
807
 * Depending on different usage, domaintree will support different
 * search policies.  Whether to return an empty node to end user is one
 * policy among them.  The default policy is to NOT return an empty node
 * to end user; to change the behavior, specify \c true for the
 * constructor parameter \c returnEmptyNode.
808
809
810
811
812
813
 * \note The search policy only affects the \c find() behavior of DomainTree.
 * When inserting one name into DomainTree, if the node with the name already
 * exists in the DomainTree and it's an empty node which doesn't have any data,
 * the \c insert() method will still return \c ALREADYEXISTS regardless of
 * the search policy.
 *
814
815
816
817
818
819
820
 * The template parameters taken by \c DomainTree are \c T (the type of
 * data which is stored by the tree) and \c DT (a type whose instance is
 * used to destroy data stored in the tree). <code>operator()</code> is
 * called on a \c DT instance and passed a pointer to the data
 * (<code>T*</code>) to be destroyed. This method should be written to
 * accept \c NULL arguments.
 *
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
 * \anchor diagram
 *
 * with the following names:
 *  - a
 *  - b
 *  - c
 *  - x.d.e.f
 *  - z.d.e.f
 *  - g.h
 *  - o.w.y.d.e.f
 *  - p.w.y.d.e.f
 *  - q.w.y.d.e.f
 *
 * the tree will look like:
 *  \verbatim
                                .
                                |
                                b
                              /   \
                             a    d.e.f
                                    /|\
                                   c | g.h
                                     |
                                    w.y
                                    /|\
                                   x | z
                                     |
                                     p
                                    / \
                                   o   q
   \endverbatim
 *  \todo
 *  - add remove interface
 */
855
template <typename T, typename DT>
856
class DomainTree : public boost::noncopyable {
857
    friend class DomainTreeNode<T, DT>;
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
public:
    /// \brief The return value for the \c find() and insert() methods
    enum Result {
        SUCCESS,    ///< Insert was successful
        /// \brief The node returned from find mathes exactly the name given
        EXACTMATCH,
        PARTIALMATCH, ///< A superdomain node was found
        NOTFOUND,   ///< Not even any superdomain was found
        /// \brief Returned by insert() if a node of the name already exists
        ALREADYEXISTS,
    };

    /// \brief Allocate and construct \c DomainTree
    ///
    /// This static method allocates memory for a new \c DomainTree object
    /// from the given memory segment, constructs the object, and returns
    /// a pointer to it.
    ///
    /// \throw std::bad_alloc Memory allocation fails.
    ///
    /// \param mem_sgmt A \c MemorySegment from which memory for the new
    /// \c DomainTree is allocated.
    static DomainTree* create(util::MemorySegment& mem_sgmt,
881
                              bool return_empty_node = false)
882
    {
883
884
        void* p = mem_sgmt.allocate(sizeof(DomainTree<T, DT>));
        return (new(p) DomainTree<T, DT>(return_empty_node));
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
    }

    /// \brief Destruct and deallocate \c DomainTree
    ///
    /// This method also destroys and deallocates all nodes inserted to the
    /// tree.
    ///
    /// \note The memory segment (\c mem_sgmt) must be the same one that
    /// was originally used to allocate memory for the tree (and for all
    /// nodes inserted to the tree, due to the requirement of \c insert()),
    /// since the tree itself doesn't maintain a reference to the segment.
    /// This is not a robust interface, but since we plan to share the tree
    /// structure by multiple processes via shared memory or possibly allow
    /// the memory image to be dumped to a file for later reload, there
    /// doesn't seem to be an easy way to store such reference in the data
    /// itself.  We should probably consider a wrapper interface that
    /// encapsulates the corresponding segment and always use it for any
    /// allocation/deallocation of tree related data (the tree itself, their
    /// nodes, and node data) to keep the usage as safe as possible.
    ///
    /// \throw none
    ///
    /// \param mem_sgmt The \c MemorySegment that allocated memory for
908
909
    /// \c tree and for all nodes inserted to the tree.
    /// \param tree A non NULL pointer to a valid \c DomainTree object
910
911
    /// that was originally created by the \c create() method (the behavior
    /// is undefined if this condition isn't met).
912
    static void destroy(util::MemorySegment& mem_sgmt,
913
914
915
916
                        DomainTree<T, DT>* tree) {
        tree->deleteAllNodes(mem_sgmt);
        tree->~DomainTree<T, DT>();
        mem_sgmt.deallocate(tree, sizeof(DomainTree<T, DT>));
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
    }

private:
    /// \name Constructor and Destructor
    //@{
    /// \brief The constructor.
    ///
    /// An object of this class is always expected to be created by the
    /// allocator (\c create()), so the constructor is hidden as private.
    ///
    /// It never throws an exception.
    explicit DomainTree(bool returnEmptyNode = false);

    /// \brief The destructor.
    ///
    /// An object of this class is always expected to be destroyed explicitly
933
    /// by \c destroy(), so the destructor is hidden as private.
934
935
936
937
938
939
940
941
942
943
944
945
946
947
    ///
    /// \note DomainTree is not intended to be inherited so the destructor
    /// is not virtual
    ~DomainTree();
    //@}

public:

    /// \name Find methods
    ///
    /// \brief Find the node that gives a longest match against the given name.
    ///
    /// \anchor find
    ///
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
    /// These methods search the DomainTree for a node whose name is
    /// longest against name. The found node, if any, is returned via
    /// the node pointer.
    ///
    /// By default, nodes that don't have data (see
    /// DomainTreeNode::isEmpty) are ignored and the result can be
    /// NOTFOUND even if there's a node whose name matches.  If the \c
    /// DomainTree is constructed with its \c returnEmptyNode parameter
    /// being \c true, empty nodes will also be match candidates.
    ///
    /// \note Even when \c returnEmptyNode is \c true, not all empty
    /// nodes in terms of the DNS protocol may necessarily be found by
    /// this method.  For example, in the \ref diagram shown in the
    /// class description, the name y.d.e.f is logically contained in
    /// the tree as part of the node w.y, but the \c find() variants
    /// cannot find the former for the search key of y.d.e.f, no matter
    /// how the \c DomainTree is constructed.  The caller of this method
    /// must use a different way to identify the hidden match when
    /// necessary.
    ///
    /// These methods involve operations on names that can throw an
    /// exception.  If that happens the exception will be propagated to
    /// the caller.  The callback function should generally not throw an
    /// exception, but if it throws, the exception will be propagated to
    /// the caller.
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
    ///
    /// The \c name parameter says what should be found. The node parameter
    /// is output-only, and in case of EXACTMATCH or PARTIALMATCH, it is set
    /// to a pointer to the found node.
    ///
    /// They return:
    ///  - EXACTMATCH when a node with the same name as requested exists.
    ///  - PARTIALMATCH when a node with the same name does not exist (or is
    ///    empty), but there's a (nonempty) superdomain of the requested one.
    ///    The superdomain with longest name is returned through the node
    ///    parameter. Beware that if you store a zone in the tree, you may get
    ///    PARTIALMATCH with zone apex when the given domain name is not there.
    ///    You should not try to delegate into another zone in that case.
    ///  - NOTFOUND if there's no node with the same name nor any superdomain
    ///    of it. In that case, node parameter is left intact.
    //@{

    /// \brief Simple find.
    ///
    /// Acts as described in the \ref find section.
993
    Result find(const isc::dns::Name& name,
994
995
                DomainTreeNode<T, DT>** node) const {
        DomainTreeNodeChain<T, DT> node_path;
996
997
998
999
1000
1001
1002
1003
        const isc::dns::LabelSequence ls(name);
        return (find<void*>(ls, node, node_path, NULL, NULL));
    }

    /// \brief Simple find returning immutable node.
    ///
    /// Acts as described in the \ref find section, but returns immutable node
    /// pointer.
1004
    Result find(const isc::dns::Name& name,
1005
1006
1007
                const DomainTreeNode<T, DT>** node) const {
        DomainTreeNodeChain<T, DT> node_path;
        DomainTreeNode<T, DT> *target_node = NULL;
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
        const isc::dns::LabelSequence ls(name);
        Result ret = (find<void*>(ls, &target_node, node_path, NULL, NULL));
        if (ret != NOTFOUND) {
            *node = target_node;
        }
        return (ret);
    }

    /// \brief Simple find, with node_path tracking
    ///
    /// Acts as described in the \ref find section.
1019
1020
    Result find(const isc::dns::Name& name, DomainTreeNode<T, DT>** node,
                DomainTreeNodeChain<T, DT>& node_path) const
1021
1022
1023
1024
1025
1026
1027
1028
1029
    {
        const isc::dns::LabelSequence ls(name);
        return (find<void*>(ls, node, node_path, NULL, NULL));
    }

    /// \brief Simple find returning immutable node, with node_path tracking
    ///
    /// Acts as described in the \ref find section, but returns immutable node
    /// pointer.
1030
1031
    Result find(const isc::dns::Name& name, const DomainTreeNode<T, DT>** node,
                DomainTreeNodeChain<T, DT>& node_path) const
1032
    {
1033
        DomainTreeNode<T, DT> *target_node = NULL;
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
        const isc::dns::LabelSequence ls(name);
        Result ret = (find<void*>(ls, &target_node, node_path, NULL, NULL));
        if (ret != NOTFOUND) {
            *node = target_node;
        }
        return (ret);
    }

    /// \brief Simple find returning immutable node.
    ///
    /// Acts as described in the \ref find section, but returns immutable
    /// node pointer.
    template <typename CBARG>
    Result find(const isc::dns::Name& name,
1048
1049
1050
                const DomainTreeNode<T, DT>** node,
                DomainTreeNodeChain<T, DT>& node_path,
                bool (*callback)(const DomainTreeNode<T, DT>&, CBARG),
1051
1052
                CBARG callback_arg) const
    {
1053
        DomainTreeNode<T, DT>* target_node = NULL;
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
        const isc::dns::LabelSequence ls(name);
        Result ret = find(ls, &target_node, node_path, callback,
                          callback_arg);
        if (ret != NOTFOUND) {
            *node = target_node;
        }
        return (ret);
    }

    /// \brief Find with callback and node chain
    /// \anchor callback
    ///
    /// This version of \c find() is specifically designed for the backend
    /// of the \c InMemoryZoneFinder class, and implements all necessary
    /// features for that purpose.  Other applications shouldn't need these
    /// additional features, and should normally use the simpler versions.
    ///
    /// This version of \c find() calls the callback whenever traversing (on
    /// the way from root down the tree) a marked node on the way down through
    /// the domain namespace (see \c DomainTreeNode::FLAG_CALLBACK).
    ///
    /// Also, this version takes a \c LabelSequence object, not a \c Name
    /// object to be as efficient as possible; operations on the former
    /// needed for the search are generally much more efficient than those
    /// for the latter.  Since \c Name objects are more commonly used
    /// in other parts of the implementation, other versions take a \c Name
    /// and convert it to \c LabelSequence.  This conversion is cheap,
    /// while the other direction isn't, and since there would be cases
    /// where an implementation primarily handles \c LabelSequence objects
    /// as an efficient representation of names, it would make most sense
    /// to provide the interface that takes \c LabelSequence.
    ///
    /// If you return true from the callback, the search is stopped and a
    /// PARTIALMATCH is returned with the given node. Note that this node
    /// doesn't really need to be the one with longest possible match.
    ///
    /// The callback is not called for the node which matches exactly
    /// (EXACTMATCH is returned). This is typically the last node in the
    /// traversal during a successful search.
    ///
    /// This callback mechanism was designed with zone cut (delegation)
    /// processing in mind. The marked nodes would be the ones at delegation
    /// points. It is not expected that any other applications would need
    /// callbacks; they should use the versions of find without callbacks.
    /// The callbacks are not general functors for the same reason - we don't
    /// expect it to be needed.
    ///
    /// Another special feature of this version is the ability to record
    /// more detailed information regarding the search result.
    ///
    /// This information will be returned via the \c node_path parameter,
    /// which is an object of class \c DomainTreeNodeChain.
    /// The passed parameter must be empty.
    ///
    /// On success, the node sequence stored in \c node_path will contain all
    /// the ancestor nodes from the found node towards the root.
    /// For example, if we look for o.w.y.d.e.f in the example \ref diagram,
    /// \c node_path will contain w.y and d.e.f; the \c top() node of the
    /// chain will be o, w.y and d.e.f will be stored below it.
    ///
1114
1115
1116
1117
1118
1119
    /// This feature can be used to get the absolute name for a node; to
    /// do so, we need to travel upside from the node toward the root,
    /// concatenating all ancestor labels.  A node chain can also be
    /// used to find the next and previous nodes of a given node in the
    /// entire DomainTree; the \c nextNode() and \c previousNode()
    /// methods take a node chain as a parameter.
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
    ///
    /// \exception isc::BadValue node_path is not empty.
    ///
    /// \param target_labels_orig Target to be found
    /// \param node On success (either \c EXACTMATCH or \c PARTIALMATCH)
    ///     it will store a pointer to the matching node
    /// \param node_path Other search details will be stored (see the
    ///        description)
    /// \param callback If non- \c NULL, a call back function to be called
    ///     at marked nodes (see the description).
    /// \param callback_arg A caller supplied argument to be passed to
    ///     \c callback.
    ///
    /// \return As in the description, but in case of callback returning
    ///     \c true, it returns immediately with the current node.
    template <typename CBARG>
    Result find(const isc::dns::LabelSequence& target_labels_orig,
1137
1138
1139
                DomainTreeNode<T, DT>** node,
                DomainTreeNodeChain<T, DT>& node_path,
                bool (*callback)(const DomainTreeNode<T, DT>&, CBARG),
1140
1141
1142
1143
1144
1145
1146
1147
                CBARG callback_arg) const;

    /// \brief Simple find returning immutable node.
    ///
    /// Acts as described in the \ref find section, but returns immutable
    /// node pointer.
    template <typename CBARG>
    Result find(const isc::dns::LabelSequence& target_labels,
1148
1149
1150
                const DomainTreeNode<T, DT>** node,
                DomainTreeNodeChain<T, DT>& node_path,
                bool (*callback)(const DomainTreeNode<T, DT>&, CBARG),
1151
1152
                CBARG callback_arg) const
    {
1153
        DomainTreeNode<T, DT>* target_node = NULL;
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
        Result ret = find(target_labels, &target_node, node_path,
                          callback, callback_arg);
        if (ret != NOTFOUND) {
            *node = target_node;
        }
        return (ret);
    }
    //@}

    /// \brief return the next bigger node in DNSSEC order from a given node
    /// chain.
    ///
    /// This method identifies the next bigger node of the node currently
    /// referenced in \c node_path and returns it.
    /// This method also updates the passed \c node_path so that it will store
    /// the path for the returned next node.
    /// It will be convenient when we want to iterate over the all nodes
    /// of \c DomainTree; we can do this by calling this method repeatedly
    /// starting from the root node.
    ///
1174
1175
1176
1177
    /// \note \c nextNode() will iterate over all the nodes in
    /// DomainTree including empty nodes. If empty node isn't desired,
    /// it's easy to add logic to check return node and keep invoking \c
    /// nextNode() until the non-empty node is retrieved.
1178
1179
1180
    ///
    /// \exception isc::BadValue node_path is empty.
    ///
1181
1182
    /// \param node_path A node chain that stores all the nodes along
    /// the path from root to node.
1183
    ///
1184
1185
    /// \return An \c DomainTreeNode that is next bigger than \c node;
    /// if \c node is the largest, \c NULL will be returned.
1186
1187
    const DomainTreeNode<T, DT>*
    nextNode(DomainTreeNodeChain<T, DT>& node_path) const;
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208

    /// \brief return the next smaller node in DNSSEC order from a node
    ///     searched by DomainTree::find().
    ///
    /// This acts similarly to \c nextNode(), but it walks in the other
    /// direction. But unlike \c nextNode(), this can start even if the
    /// node requested by \c find() was not found. In that case, it will
    /// identify the node that is previous to the queried name.
    ///
    /// \note \c previousNode() will iterate over all the nodes in DomainTree
    /// including empty nodes. If empty node isn't desired, it's easy to add
    /// logic to check return node and keep invoking \c previousNode() until the
    /// non-empty node is retrieved.
    ///
    /// \exception isc::BadValue node_path is empty.
    ///
    /// \param node_path A node chain that stores all the nodes along the path
    /// from root to node and the result of \c find(). This will get modified.
    /// You should not use the node_path again except for repetitive calls
    /// of this method.
    ///
1209
1210
    /// \return An \c DomainTreeNode that is next smaller than \c node;
    /// if \c node is the smallest, \c NULL will be returned.
1211
1212
    const DomainTreeNode<T, DT>*
    previousNode(DomainTreeNodeChain<T, DT>& node_path) const;
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242

    /// \brief Get the total number of nodes in the tree
    ///
    /// It includes nodes internally created as a result of adding a domain
    /// name that is a subdomain of an existing node of the tree.
    /// This function is mainly intended to be used for debugging.
    int getNodeCount() const { return (node_count_); }

    /// \name Debug function
    //@{
    /// \brief Print the nodes in the trees.
    ///
    /// \param os A \c std::ostream object to which the tree is printed.
    /// \param depth A factor of the initial indentation.  Each line
    /// will begin with space character repeating <code>5 * depth</code>
    /// times.
    void dumpTree(std::ostream& os, unsigned int depth = 0) const;

    /// \brief Print the nodes in the trees for processing with
    /// Graphviz's dot.
    ///
    /// \param os A \c std::ostream object to which the tree is printed.
    /// \param show_pointers Show node and parent pointers in the node
    void dumpDot(std::ostream& os, bool show_pointers = false) const;
    //@}

    /// \name Modify functions
    //@{
    /// \brief Insert the domain name into the tree.
    ///
1243
1244
1245
1246
1247
1248
    /// It either finds an already existing node of the given name, or
    /// inserts a new one if none exists yet. In any case, the \c
    /// inserted_node parameter is set to point to that node. You can
    /// fill data into it or modify it.  So, if you don't know if a node
    /// exists or not and you need to modify it, just call insert and
    /// act by the result.
1249
    ///
1250
1251
1252
    /// Please note that the tree can add some empty nodes by itself, so
    /// don't assume that if you didn't insert a node of that name it
    /// doesn't exist.
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
    ///
    /// This method normally involves resource allocation.  If it fails
    /// the corresponding standard exception will be thrown.
    ///
    /// This method does not provide the strong exception guarantee in its
    /// strict sense; if an exception is thrown in the middle of this
    /// method, the internal structure may change.  However, it should
    /// still retain the same property as a mapping container before this
    /// method is called.  For example, the result of \c find() should be
    /// the same.  This method provides the weak exception guarantee in its
    /// normal sense.
    ///
    /// \param mem_sgmt A \c MemorySegment object for allocating memory of
    /// a new node to be inserted.  Must be the same segment as that used
    /// for creating the tree itself.
    /// \param name The name to be inserted into the tree.
    /// \param inserted_node This is an output parameter and is set to the
    ///     node.
    ///
    /// \return
    ///  - SUCCESS The node was added.
    ///  - ALREADYEXISTS There was already a node of that name, so it was not
    ///     added.
    Result insert(util::MemorySegment& mem_sgmt, const isc::dns::Name& name,
1277
                  DomainTreeNode<T, DT>** inserted_node);
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295

    /// \brief Delete all tree nodes.
    ///
    /// \throw none.
    ///
    /// \param mem_sgmt The \c MemorySegment object used to insert the nodes
    /// (which was also used for creating the tree due to the requirement of
    /// \c inert()).
    void deleteAllNodes(util::MemorySegment& mem_sgmt);

    /// \brief Swaps two tree's contents.
    ///
    /// This and \c other trees must have been created with the same
    /// memory segment (see the discussion in \c create()); otherwise the
    /// behavior is undefined.
    ///
    /// This acts the same as many std::*.swap functions, exchanges the
    /// contents. This doesn't throw anything.
1296
    void swap(DomainTree<T, DT>& other) {
1297
1298
1299
1300
1301
1302
1303
1304
        std::swap(root_, other.root_);
        std::swap(node_count_, other.node_count_);
    }
    //@}

private:
    /// \name DomainTree balance functions
    //@{
1305
    void
1306
1307
    insertRebalance(typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
                    DomainTreeNode<T, DT>* node);
1308

1309
1310
1311
    DomainTreeNode<T, DT>*
    rightRotate(typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
                DomainTreeNode<T, DT>* node);
1312

1313
1314
1315
    DomainTreeNode<T, DT>*
    leftRotate(typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
               DomainTreeNode<T, DT>* node);
1316
1317
1318
1319
1320
    //@}

    /// \name Helper functions
    //@{
    /// \brief delete tree whose root is equal to node
1321
    void deleteHelper(util::MemorySegment& mem_sgmt,
1322
                      DomainTreeNode<T, DT> *node,
1323
                      const DT& deleter);
1324
1325

    /// \brief Print the information of given DomainTreeNode.
1326
    void dumpTreeHelper(std::ostream& os, const DomainTreeNode<T, DT>* node,
1327
1328
1329
                        unsigned int depth) const;

    /// \brief Print the information of given DomainTreeNode for dot.
1330
    int dumpDotHelper(std::ostream& os, const DomainTreeNode<T, DT>* node,
1331
1332
1333
1334
1335
1336
1337
                      int* nodecount, bool show_pointers) const;

    /// \brief Indentation helper function for dumpTree
    static void indent(std::ostream& os, unsigned int depth);

    /// Split one node into two nodes for "prefix" and "suffix" parts of
    /// the labels of the original node, respectively.  The given node
1338
1339
1340
1341
1342
    /// will hold the prefix, while a newly created node will hold the prefix.
    /// Note that the original node still represents the same domain name in
    /// the entire tree.  This ensures that a pointer to a node keeps its
    /// semantics even if the tree structure is changed (as long as the node
    /// itself remains valid).
1343
    void nodeFission(util::MemorySegment& mem_sgmt, DomainTreeNode<T, DT>& node,
1344
1345
1346
1347
                     const isc::dns::LabelSequence& new_prefix,
                     const isc::dns::LabelSequence& new_suffix);
    //@}

1348
    typename DomainTreeNode<T, DT>::DomainTreeNodePtr root_;
1349
1350
    /// the node count of current tree
    unsigned int node_count_;
1351
    /// search policy for domaintree
1352
1353
1354
    const bool needsReturnEmptyNode_;
};

1355
template <typename T, typename DT>
1356
DomainTree<T, DT>::DomainTree(bool returnEmptyNode) :
1357
1358
1359
1360
1361
1362
    root_(NULL),
    node_count_(0),
    needsReturnEmptyNode_(returnEmptyNode)
{
}

1363
template <typename T, typename DT>
1364
DomainTree<T, DT>::~DomainTree() {
1365
1366
1367
    assert(node_count_ == 0);
}

1368
template <typename T, typename DT>
1369
void
1370
DomainTree<T, DT>::deleteHelper(util::MemorySegment& mem_sgmt,
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
                                DomainTreeNode<T, DT>* root,
                                const DT& deleter) {
    while (root != NULL) {
        // If there is a left, right or down node, walk into it and
        // iterate.
        if (root->getLeft() != NULL) {
            DomainTreeNode<T, DT>* node = root;
            root = root->getLeft();
            node->left_ = NULL;
        } else if (root->getRight() != NULL) {
            DomainTreeNode<T, DT>* node = root;
            root = root->getRight();
            node->right_ = NULL;
        } else if (root->getDown() != NULL) {
            DomainTreeNode<T, DT>* node = root;
            root = root->getDown();
            node->down_ = NULL;
1388
        } else {
1389
1390
1391
1392
            // There are no left, right or down nodes, so we can
            // free this one and go back to its parent.
            DomainTreeNode<T, DT>* node = root;
            root = root->getParent();
1393
            deleter(mem_sgmt, node->data_.get());
1394
1395
            DomainTreeNode<T, DT>::destroy(mem_sgmt, node);
            --node_count_;
1396
1397
1398
1399
        }
    }
}

1400
template <typename T, typename DT>
1401
template <typename CBARG>
1402
1403
1404
1405
1406
typename DomainTree<T, DT>::Result
DomainTree<T, DT>::find(const isc::dns::LabelSequence& target_labels_orig,
                       DomainTreeNode<T, DT>** target,
                       DomainTreeNodeChain<T, DT>& node_path,
                       bool (*callback)(const DomainTreeNode<T, DT>&, CBARG),
1407
                       CBARG callback_arg) const
1408
1409
{
    if (!node_path.isEmpty()) {
1410
1411
        isc_throw(isc::BadValue,
                  "DomainTree::find is given a non empty chain");
1412
1413
    }

1414
    DomainTreeNode<T, DT>* node = root_.get();
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
    Result ret = NOTFOUND;
    dns::LabelSequence target_labels(target_labels_orig);

    while (node != NULL) {
        node_path.last_compared_ = node;
        node_path.last_comparison_ = target_labels.compare(node->getLabels());
        const isc::dns::NameComparisonResult::NameRelation relation =
            node_path.last_comparison_.getRelation();

        if (relation == isc::dns::NameComparisonResult::EQUAL) {
            if (needsReturnEmptyNode_ || !node->isEmpty()) {
                node_path.push(node);
                *target = node;
                ret = EXACTMATCH;
            }
            break;
        } else if (relation == isc::dns::NameComparisonResult::NONE) {
            // If the two labels have no hierarchical relationship in terms
            // of matching, we should continue the binary search.
            node = (node_path.last_comparison_.getOrder() < 0) ?
                node->getLeft() : node->getRight();
        } else {
            if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
                if (needsReturnEmptyNode_ || !node->isEmpty()) {
                    ret = PARTIALMATCH;
                    *target = node;
                    if (callback != NULL &&
1442
                        node->getFlag(DomainTreeNode<T, DT>::FLAG_CALLBACK)) {
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
                        if ((callback)(*node, callback_arg)) {
                            break;
                        }
                    }
                }
                node_path.push(node);
                target_labels.stripRight(
                    node_path.last_comparison_.getCommonLabels());
                node = node->getDown();
            } else {
                break;
            }
        }
    }

    return (ret);
}

1461
template <typename T, typename DT>
1462
1463
const DomainTreeNode<T, DT>*
DomainTree<T, DT>::nextNode(DomainTreeNodeChain<T, DT>& node_path) const {
1464
    if (node_path.isEmpty()) {
1465
1466
        isc_throw(isc::BadValue,
                  "DomainTree::nextNode is given an empty chain");
1467
1468
    }

1469
    const DomainTreeNode<T, DT>* node = node_path.top();
1470
1471
    // if node has sub domain, the next domain is the smallest
    // domain in sub domain tree
1472
    const DomainTreeNode<T, DT>* down = node->getDown();
1473
    if (down != NULL) {
1474
        const DomainTreeNode<T, DT>* left_most = down;
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
        while (left_most->getLeft() != NULL) {
            left_most = left_most->getLeft();
        }
        node_path.push(left_most);
        return (left_most);
    }

    // try to find a successor.
    // if no successor found move to up level, the next successor
    // is the successor of up node in the up level tree, if
    // up node doesn't have successor we gonna keep moving to up
    // level
    while (!node_path.isEmpty()) {
1488
        const DomainTreeNode<T, DT>* up_node_successor =
1489
            node_path.top()->successor();
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
        node_path.pop();
        if (up_node_successor != NULL) {
            node_path.push(up_node_successor);
            return (up_node_successor);
        }
    }

    return (NULL);
}

1500
template <typename T, typename DT>
1501
1502
const DomainTreeNode<T, DT>*
DomainTree<T, DT>::previousNode(DomainTreeNodeChain<T, DT>& node_path) const {
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
    if (getNodeCount() == 0) {
        // Special case for empty trees. It would look every time like
        // we didn't search, because the last compared is empty. This is
        // a slight hack and not perfect, but this is better than throwing
        // on empty tree. And we probably won't meet an empty tree in practice
        // anyway.
        return (NULL);
    }
    if (node_path.last_compared_ == NULL) {
        isc_throw(isc::BadValue,
                  "DomainTree::previousNode() called before find()");
    }

    // If the relation isn't EQUAL, it means the find was called previously
    // and didn't find the exact node. Therefore we need to locate the place
    // to start iterating the chain of domains.
    //
    // The logic here is not too complex, we just need to take care to handle
    // all the cases and decide where to go from there.
    switch (node_path.last_comparison_.getRelation()) {
        case dns::NameComparisonResult::COMMONANCESTOR:
        case dns::NameComparisonResult::NONE:
            // We compared with a leaf in the tree and wanted to go to one of
            // the children. But the child was not there. It now depends on the
            // direction in which we wanted to go.
            if (node_path.last_comparison_.getOrder() < 0) {
                // We wanted to go left. So the one we compared with is
                // the one higher than we wanted. If we just put it into
                // the node_path, then the following algorithm below will find
                // the smaller one.
                //
                // This is exactly the same as with superdomain below.
                // Therefore, we just fall through to the next case.
            } else {
                // We wanted to go right. That means we want to output the
                // one which is the largest in the tree defined by the
                // compared one (it is either the compared one, or some
                // subdomain of it). There probably is not an easy trick
                // for this, so we just find the correct place.
1542
                const DomainTreeNode<T, DT>* current(node_path.last_compared_);
1543
1544
1545
1546
1547
                while (current != NULL) {
                    node_path.push(current);
                    // Go a level down and as much right there as possible
                    current = current->getDown();
                    if (current != NULL) {
1548
                        const DomainTreeNode<T, DT>* right;
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
                        while ((right = current->getRight()) != NULL) {
                            current = right;
                        }
                    }
                }
                // Now, the one on top of the path is the one we want. We
                // return it now and leave it there, so we can search for
                // previous of it the next time we'are called.
                node_path.last_comparison_ =
                    dns::NameComparisonResult(0, 0,
                                              dns::NameComparisonResult::EQUAL);
                return (node_path.top());
            }
            // No break; here - we want to fall through. See above.
        case dns::NameComparisonResult::SUPERDOMAIN:
            // This is the case there's a "compressed" node and we looked for
            // only part of it. The node itself is larger than we wanted, but
            // if we put it to the node_path and then go one step left from it,
            // we get the correct result.
            node_path.push(node_path.last_compared_);
            // Correct the comparison result, so we won't trigger this case
            // next time previousNode is called. We already located the correct
            // place to start. The value is partly nonsense, but that doesn't
            // matter any more.
            node_path.last_comparison_ =
                dns::NameComparisonResult(0, 0,
                                          dns::NameComparisonResult::EQUAL);
            break;
        case dns::NameComparisonResult::SUBDOMAIN:
            // A subdomain means we returned the one above the searched one
            // already and it is on top of the stack. This is was smaller
            // than the one already, but we want to return yet smaller one.
            // So we act as if it was EQUAL.
            break;
        case dns::NameComparisonResult::EQUAL:
            // The find gave us an exact match or the previousNode was called
            // already, which located the exact node. The rest of the function
            // goes one domain left and returns it for us.
            break;
    }

    // So, the node_path now contains the path to a node we want previous for.
    // We just need to go one step left.

    if (node_path.isEmpty()) {
        // We got past the first one. So, we're returning NULL from
        // now on.
        return (NULL);
    }

1599
    const DomainTreeNode<T, DT>* node(node_path.top());
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621

    // Try going left in this tree
    node = node->predecessor();
    if (node == NULL) {
        // We are the smallest ones in this tree. We go one level
        // up. That one is the smaller one than us.

        node_path.pop();
        if (node_path.isEmpty()) {
            // We're past the first one
            return (NULL);
        } else {
            return (node_path.top());
        }
    }

    // Exchange the node at the top of the path, as we move horizontaly
    // through the domain tree
    node_path.pop();
    node_path.push(node);

    // Try going as deep as possible, keeping on the right side of the trees
1622
    const DomainTreeNode<T, DT>* down;
1623
1624
1625
1626
1627
    while ((down = node->getDown()) != NULL) {
        // Move to the tree below
        node = down;
        if (node != NULL) {
            // And get as much to the right of the tree as possible
1628
            const DomainTreeNode<T, DT>* right;
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
            while ((right = node->getRight()) != NULL) {
                node = right;
            }
        }
        // Now, we found the right-most node in the sub-tree, we need to
        // include it in the path
        node_path.push(node);
    }

    // Now, if the current node has no down_ pointer any more, it's the
    // correct one.
    return (node);
}

1643
template <typename T, typename DT>
1644
1645
typename DomainTree<T, DT>::Result
DomainTree<T, DT>::insert(util::MemorySegment& mem_sgmt,
1646
1647
                          const isc::dns::Name& target_name,
                          DomainTreeNode<T, DT>** new_node)
1648
{
1649