domaintree.h 78.3 KB
 Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44  #include #include #include #include #include #include #include #include #include #include #include namespace isc { namespace datasrc { namespace memory {  Mukund Sivaraman committed Jul 31, 2012 45 46 /// Forward declare DomainTree class here is convinent for following /// friend class declare inside DomainTreeNode and DomainTreeNodeChain  Mukund Sivaraman committed Jul 31, 2012 47 template  Mukund Sivaraman committed Jul 31, 2012 48 49 class DomainTree;  Mukund Sivaraman committed Jul 31, 2012 50 51 /// \brief \c DomainTreeNode is used by DomainTree to store any data /// related to one domain name.  Mukund Sivaraman committed Jul 31, 2012 52 ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 56 ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 61 ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 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. ///  Mukund Sivaraman committed Jul 31, 2012 69 70 /// One special kind of node is non-terminal node. It has subdomains /// with RRsets, but doesn't have any RRsets itself.  Mukund Sivaraman committed Jul 31, 2012 71 ///  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 81 /// bits of the "flags" field.  Mukund Sivaraman committed Jul 31, 2012 82 template  Mukund Sivaraman committed Jul 31, 2012 83 84 class DomainTreeNode : public boost::noncopyable { private:  Mukund Sivaraman committed Jul 31, 2012 85 86  /// The DomainTreeNode is meant for use from within DomainTree, so /// it has access to it.  Mukund Sivaraman committed Jul 31, 2012 87  friend class DomainTree;  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 93  typedef boost::interprocess::offset_ptr >  Mukund Sivaraman committed Jul 31, 2012 94  DomainTreeNodePtr;  Mukund Sivaraman committed Jul 31, 2012 95 96 97  /// \name Constructors ///  Mukund Sivaraman committed Jul 31, 2012 98 99  /// \note The existence of a DomainTreeNode without a DomainTree is /// meaningless. Therefore the constructors are private.  Mukund Sivaraman committed Jul 31, 2012 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. ///  Mukund Sivaraman committed Jul 31, 2012 112 113  /// The only valid usage of the returned pointer is to pass it to /// the corresponding constructor of \c dns::LabelSequence.  Mukund Sivaraman committed Jul 31, 2012 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 ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 134  static DomainTreeNode* create(util::MemorySegment& mem_sgmt,  Mukund Sivaraman committed Jul 31, 2012 135 136 137  const dns::LabelSequence& labels) { const size_t labels_len = labels.getSerializedLength();  Mukund Sivaraman committed Jul 31, 2012 138 139  void* p = mem_sgmt.allocate(sizeof(DomainTreeNode) + labels_len); DomainTreeNode* node = new(p) DomainTreeNode(labels_len);  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 149 150  /// \c node. /// \param node A non NULL pointer to a valid \c DomainTreeNode object  Mukund Sivaraman committed Jul 31, 2012 151 152  /// that was originally created by the \c create() method (the behavior /// is undefined if this condition isn't met).  Mukund Sivaraman committed Jul 31, 2012 153  static void destroy(util::MemorySegment& mem_sgmt,  Mukund Sivaraman committed Jul 31, 2012 154 155 156 157  DomainTreeNode* node) { const size_t labels_capacity = node->labels_capacity_; node->~DomainTreeNode(); mem_sgmt.deallocate(node,  Mukund Sivaraman committed Jul 31, 2012 158  sizeof(DomainTreeNode) + labels_capacity);  Mukund Sivaraman committed Jul 31, 2012 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. ///  Mukund Sivaraman committed Jul 31, 2012 230 231  /// You should not delete the data, it is deleted when the tree is /// destroyed.  JINMEI Tatuya committed Aug 20, 2012 232  T* getData() { return (data_.get()); }  Mukund Sivaraman committed Jul 31, 2012 233 234  /// \brief Return the data stored in this node (const).  JINMEI Tatuya committed Aug 20, 2012 235  const T* getData() const { return (data_.get()); }  Mukund Sivaraman committed Jul 31, 2012 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.  JINMEI Tatuya committed Aug 20, 2012 242  bool isEmpty() const { return (!data_); }  Mukund Sivaraman committed Jul 31, 2012 243 244 245 246  //@} /// \name Setter functions. //@{  Mukund Sivaraman committed Jul 31, 2012 247   Mukund Sivaraman committed Aug 02, 2012 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.  Mukund Sivaraman committed Aug 03, 2012 251 252  /// \param mem_sgmt The \c MemorySegment that allocated memory for /// the node data.  Mukund Sivaraman committed Aug 02, 2012 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.  Mukund Sivaraman committed Aug 03, 2012 257  void setData(util::MemorySegment& mem_sgmt, T* data, T** old_data = NULL) {  Mukund Sivaraman committed Aug 02, 2012 258 259 260 261  if (old_data != NULL) { *old_data = data; } else { const DT deleter;  JINMEI Tatuya committed Aug 20, 2012 262  deleter(mem_sgmt, data_.get());  Mukund Sivaraman committed Aug 02, 2012 263  }  Mukund Sivaraman committed Jul 31, 2012 264 265  data_ = data; }  Mukund Sivaraman committed Jul 31, 2012 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 ///  Mukund Sivaraman committed Jul 31, 2012 316  /// See the description of \c DomainTree::find() at \ref callback  Mukund Sivaraman committed Jul 31, 2012 317 318 319 320 321 322 323 324  /// about callbacks. /// /// These methods never throw an exception. //@{ /// Return if callback is enabled at the node. //@}  Mukund Sivaraman committed Jul 31, 2012 325  /// \brief Define node color  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 367  const DomainTreeNode* getUpperNode() const;  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 385  const DomainTreeNode* successor() const;  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 402  const DomainTreeNode* predecessor() const;  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 415 416 417 418 419  const DomainTreeNode* abstractSuccessor(typename DomainTreeNode::DomainTreeNodePtr DomainTreeNode::*left, typename DomainTreeNode::DomainTreeNodePtr DomainTreeNode::*right)  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 432  DomainTreeNode* getParent() {  Mukund Sivaraman committed Jul 31, 2012 433 434 435  return (parent_.get()); } /// \brief Access the parent_ as bare pointer, const.  Mukund Sivaraman committed Jul 31, 2012 436  const DomainTreeNode* getParent() const {  Mukund Sivaraman committed Jul 31, 2012 437 438 439 440  return (parent_.get()); } DomainTreeNodePtr left_; /// \brief Access the left_ as bare pointer.  Mukund Sivaraman committed Jul 31, 2012 441  DomainTreeNode* getLeft() {  Mukund Sivaraman committed Jul 31, 2012 442 443 444  return (left_.get()); } /// \brief Access the left_ as bare pointer, const.  Mukund Sivaraman committed Jul 31, 2012 445  const DomainTreeNode* getLeft() const {  Mukund Sivaraman committed Jul 31, 2012 446 447 448 449  return (left_.get()); } DomainTreeNodePtr right_; /// \brief Access the right_ as bare pointer.  Mukund Sivaraman committed Jul 31, 2012 450  DomainTreeNode* getRight() {  Mukund Sivaraman committed Jul 31, 2012 451 452 453  return (right_.get()); } /// \brief Access the right_ as bare pointer, const.  Mukund Sivaraman committed Jul 31, 2012 454  const DomainTreeNode* getRight() const {  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 470  DomainTreeNode* getDown() {  Mukund Sivaraman committed Jul 31, 2012 471 472 473  return (down_.get()); } /// \brief Access the down_ as bare pointer, const.  Mukund Sivaraman committed Jul 31, 2012 474  const DomainTreeNode* getDown() const {  Mukund Sivaraman committed Jul 31, 2012 475 476 477  return (down_.get()); }  Mukund Sivaraman committed Jul 31, 2012 478  /// \brief Data stored here.  JINMEI Tatuya committed Aug 20, 2012 479  boost::interprocess::offset_ptr data_;  Mukund Sivaraman committed Jul 31, 2012 480   Mukund Sivaraman committed Jul 31, 2012 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); };  Mukund Sivaraman committed Jul 31, 2012 501 template  Mukund Sivaraman committed Jul 31, 2012 502 DomainTreeNode::DomainTreeNode(size_t labels_capacity) :  Mukund Sivaraman committed Jul 31, 2012 503 504 505 506  parent_(NULL), left_(NULL), right_(NULL), down_(NULL),  Mukund Sivaraman committed Jul 31, 2012 507  data_(NULL),  Mukund Sivaraman committed Jul 31, 2012 508 509 510 511 512  flags_(FLAG_RED | FLAG_SUBTREE_ROOT), labels_capacity_(labels_capacity) { }  Mukund Sivaraman committed Jul 31, 2012 513 template  Mukund Sivaraman committed Jul 31, 2012 514 DomainTreeNode::~DomainTreeNode() {  Mukund Sivaraman committed Jul 31, 2012 515 516 }  Mukund Sivaraman committed Jul 31, 2012 517 template  Mukund Sivaraman committed Jul 31, 2012 518 519 520 const DomainTreeNode* DomainTreeNode::getUpperNode() const { const DomainTreeNode* current = this;  Mukund Sivaraman committed Jul 31, 2012 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()); }  Mukund Sivaraman committed Jul 31, 2012 531 template  Mukund Sivaraman committed Jul 31, 2012 532 533 534 535 536 const DomainTreeNode* DomainTreeNode::abstractSuccessor(typename DomainTreeNode::DomainTreeNodePtr DomainTreeNode::*left, typename DomainTreeNode::DomainTreeNodePtr DomainTreeNode::*right)  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 544  const DomainTreeNode* current = this;  Mukund Sivaraman committed Jul 31, 2012 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();  Mukund Sivaraman committed Jul 31, 2012 549  const DomainTreeNode* left_n;  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 559  const DomainTreeNode* parent = current->getParent();  Mukund Sivaraman committed Jul 31, 2012 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); } }  Mukund Sivaraman committed Jul 31, 2012 573 template  Mukund Sivaraman committed Jul 31, 2012 574 575 576 577 const DomainTreeNode* DomainTreeNode::successor() const { return (abstractSuccessor(&DomainTreeNode::left_, &DomainTreeNode::right_));  Mukund Sivaraman committed Jul 31, 2012 578 579 }  Mukund Sivaraman committed Jul 31, 2012 580 template  Mukund Sivaraman committed Jul 31, 2012 581 582 const DomainTreeNode* DomainTreeNode::predecessor() const {  Mukund Sivaraman committed Jul 31, 2012 583  // Swap the left and right pointers for the abstractSuccessor  Mukund Sivaraman committed Jul 31, 2012 584 585  return (abstractSuccessor(&DomainTreeNode::right_, &DomainTreeNode::left_));  Mukund Sivaraman committed Jul 31, 2012 586 587 }  Mukund Sivaraman committed Jul 31, 2012 588 589 /// \brief DomainTreeNodeChain stores detailed information of \c /// DomainTree::find() result.  Mukund Sivaraman committed Jul 31, 2012 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. ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 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. ///  Mukund Sivaraman committed Jul 31, 2012 616 617 /// DomainTreeNodeChain is constructed and manipulated only inside the /// \c DomainTree class.  Mukund Sivaraman committed Jul 31, 2012 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).  Mukund Sivaraman committed Jul 31, 2012 622 template  Mukund Sivaraman committed Jul 31, 2012 623 624 625 class DomainTreeNodeChain { /// DomainTreeNodeChain is initialized by DomainTree, only DomainTree has /// knowledge to manipulate it.  Mukund Sivaraman committed Jul 31, 2012 626  friend class DomainTree;  Mukund Sivaraman committed Jul 31, 2012 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:  Mukund Sivaraman committed Jul 31, 2012 646 647  DomainTreeNodeChain(const DomainTreeNodeChain&); DomainTreeNodeChain& operator=(const DomainTreeNodeChain&);  Mukund Sivaraman committed Jul 31, 2012 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; }  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 669  ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 673 674  /// /// \exception None  Mukund Sivaraman committed Jul 31, 2012 675  const DomainTreeNode* getLastComparedNode() const {  Mukund Sivaraman committed Jul 31, 2012 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,  Mukund Sivaraman committed Jul 31, 2012 711 712  "DomainTreeNodeChain::getAbsoluteName is " "called on an empty chain");  Mukund Sivaraman committed Jul 31, 2012 713 714  }  Mukund Sivaraman committed Jul 31, 2012 715  const DomainTreeNode* top_node = top();  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 743  const DomainTreeNode* top() const {  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 766  void push(const DomainTreeNode* node) {  Mukund Sivaraman committed Jul 31, 2012 767 768 769 770 771  assert(node_count_ < RBT_MAX_LEVEL); nodes_[node_count_++] = node; } private:  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 775 776 777  const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS; int node_count_;  Mukund Sivaraman committed Jul 31, 2012 778 779  const DomainTreeNode* nodes_[RBT_MAX_LEVEL]; const DomainTreeNode* last_compared_;  Mukund Sivaraman committed Jul 31, 2012 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. *  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 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:  Mukund Sivaraman committed Jul 31, 2012 799  * - Enhances the query performance compared with one big flat red black tree.  Mukund Sivaraman committed Jul 31, 2012 800 801 802  * - Decreases the memory footprint, as it doesn't store the suffix labels * multiple times. *  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 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. *  Mukund Sivaraman committed Jul 31, 2012 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). operator() is * called on a \c DT instance and passed a pointer to the data * (T*) to be destroyed. This method should be written to * accept \c NULL arguments. *  Mukund Sivaraman committed Jul 31, 2012 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 */  Mukund Sivaraman committed Jul 31, 2012 855 template  Mukund Sivaraman committed Jul 31, 2012 856 class DomainTree : public boost::noncopyable {  Mukund Sivaraman committed Jul 31, 2012 857  friend class DomainTreeNode;  Mukund Sivaraman committed Jul 31, 2012 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,  Mukund Sivaraman committed Aug 03, 2012 881  bool return_empty_node = false)  Mukund Sivaraman committed Jul 31, 2012 882  {  Mukund Sivaraman committed Jul 31, 2012 883 884  void* p = mem_sgmt.allocate(sizeof(DomainTree)); return (new(p) DomainTree(return_empty_node));  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 908 909  /// \c tree and for all nodes inserted to the tree. /// \param tree A non NULL pointer to a valid \c DomainTree object  Mukund Sivaraman committed Jul 31, 2012 910 911  /// that was originally created by the \c create() method (the behavior /// is undefined if this condition isn't met).  Mukund Sivaraman committed Jul 31, 2012 912  static void destroy(util::MemorySegment& mem_sgmt,  Mukund Sivaraman committed Jul 31, 2012 913 914 915 916  DomainTree* tree) { tree->deleteAllNodes(mem_sgmt); tree->~DomainTree(); mem_sgmt.deallocate(tree, sizeof(DomainTree));  Mukund Sivaraman committed Jul 31, 2012 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  JINMEI Tatuya committed Aug 13, 2012 933  /// by \c destroy(), so the destructor is hidden as private.  Mukund Sivaraman committed Jul 31, 2012 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 ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 993  Result find(const isc::dns::Name& name,  Mukund Sivaraman committed Jul 31, 2012 994 995  DomainTreeNode** node) const { DomainTreeNodeChain node_path;  Mukund Sivaraman committed Jul 31, 2012 996 997 998 999 1000 1001 1002 1003  const isc::dns::LabelSequence ls(name); return (find(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.  Mukund Sivaraman committed Jul 31, 2012 1004  Result find(const isc::dns::Name& name,  Mukund Sivaraman committed Jul 31, 2012 1005 1006 1007  const DomainTreeNode** node) const { DomainTreeNodeChain node_path; DomainTreeNode *target_node = NULL;  Mukund Sivaraman committed Jul 31, 2012 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018  const isc::dns::LabelSequence ls(name); Result ret = (find(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.  Mukund Sivaraman committed Jul 31, 2012 1019 1020  Result find(const isc::dns::Name& name, DomainTreeNode** node, DomainTreeNodeChain& node_path) const  Mukund Sivaraman committed Jul 31, 2012 1021 1022 1023 1024 1025 1026 1027 1028 1029  { const isc::dns::LabelSequence ls(name); return (find(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.  Mukund Sivaraman committed Jul 31, 2012 1030 1031  Result find(const isc::dns::Name& name, const DomainTreeNode** node, DomainTreeNodeChain& node_path) const  Mukund Sivaraman committed Jul 31, 2012 1032  {  Mukund Sivaraman committed Jul 31, 2012 1033  DomainTreeNode *target_node = NULL;  Mukund Sivaraman committed Jul 31, 2012 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047  const isc::dns::LabelSequence ls(name); Result ret = (find(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 Result find(const isc::dns::Name& name,  Mukund Sivaraman committed Jul 31, 2012 1048 1049 1050  const DomainTreeNode** node, DomainTreeNodeChain& node_path, bool (*callback)(const DomainTreeNode&, CBARG),  Mukund Sivaraman committed Jul 31, 2012 1051 1052  CBARG callback_arg) const {  Mukund Sivaraman committed Jul 31, 2012 1053  DomainTreeNode* target_node = NULL;  Mukund Sivaraman committed Jul 31, 2012 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. ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 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 Result find(const isc::dns::LabelSequence& target_labels_orig,  Mukund Sivaraman committed Jul 31, 2012 1137 1138 1139  DomainTreeNode** node, DomainTreeNodeChain& node_path, bool (*callback)(const DomainTreeNode&, CBARG),  Mukund Sivaraman committed Jul 31, 2012 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 Result find(const isc::dns::LabelSequence& target_labels,  Mukund Sivaraman committed Jul 31, 2012 1148 1149 1150  const DomainTreeNode** node, DomainTreeNodeChain& node_path, bool (*callback)(const DomainTreeNode&, CBARG),  Mukund Sivaraman committed Jul 31, 2012 1151 1152  CBARG callback_arg) const {  Mukund Sivaraman committed Jul 31, 2012 1153  DomainTreeNode* target_node = NULL;  Mukund Sivaraman committed Jul 31, 2012 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. ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 1178 1179 1180  /// /// \exception isc::BadValue node_path is empty. ///  Mukund Sivaraman committed Jul 31, 2012 1181 1182  /// \param node_path A node chain that stores all the nodes along /// the path from root to node.  Mukund Sivaraman committed Jul 31, 2012 1183  ///  Mukund Sivaraman committed Jul 31, 2012 1184 1185  /// \return An \c DomainTreeNode that is next bigger than \c node; /// if \c node is the largest, \c NULL will be returned.  Mukund Sivaraman committed Jul 31, 2012 1186 1187  const DomainTreeNode* nextNode(DomainTreeNodeChain& node_path) const;  Mukund Sivaraman committed Jul 31, 2012 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. ///  Mukund Sivaraman committed Jul 31, 2012 1209 1210  /// \return An \c DomainTreeNode that is next smaller than \c node; /// if \c node is the smallest, \c NULL will be returned.  Mukund Sivaraman committed Jul 31, 2012 1211 1212  const DomainTreeNode* previousNode(DomainTreeNodeChain& node_path) const;  Mukund Sivaraman committed Jul 31, 2012 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 5 * depth /// 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. ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 1249  ///  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 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,  Mukund Sivaraman committed Jul 31, 2012 1277  DomainTreeNode** inserted_node);  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 1296  void swap(DomainTree& other) {  Mukund Sivaraman committed Jul 31, 2012 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 //@{  Mukund Sivaraman committed Jul 31, 2012 1305  void  Mukund Sivaraman committed Jul 31, 2012 1306 1307  insertRebalance(typename DomainTreeNode::DomainTreeNodePtr* root, DomainTreeNode* node);  Mukund Sivaraman committed Jul 31, 2012 1308   Mukund Sivaraman committed Jul 31, 2012 1309 1310 1311  DomainTreeNode* rightRotate(typename DomainTreeNode::DomainTreeNodePtr* root, DomainTreeNode* node);  Mukund Sivaraman committed Jul 31, 2012 1312   Mukund Sivaraman committed Jul 31, 2012 1313 1314 1315  DomainTreeNode* leftRotate(typename DomainTreeNode::DomainTreeNodePtr* root, DomainTreeNode* node);  Mukund Sivaraman committed Jul 31, 2012 1316 1317 1318 1319 1320  //@} /// \name Helper functions //@{ /// \brief delete tree whose root is equal to node  Mukund Sivaraman committed Jul 31, 2012 1321  void deleteHelper(util::MemorySegment& mem_sgmt,  Mukund Sivaraman committed Jul 31, 2012 1322  DomainTreeNode *node,  Mukund Sivaraman committed Jul 31, 2012 1323  const DT& deleter);  Mukund Sivaraman committed Jul 31, 2012 1324 1325  /// \brief Print the information of given DomainTreeNode.  Mukund Sivaraman committed Jul 31, 2012 1326  void dumpTreeHelper(std::ostream& os, const DomainTreeNode* node,  Mukund Sivaraman committed Jul 31, 2012 1327 1328 1329  unsigned int depth) const; /// \brief Print the information of given DomainTreeNode for dot.  Mukund Sivaraman committed Jul 31, 2012 1330  int dumpDotHelper(std::ostream& os, const DomainTreeNode* node,  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Aug 02, 2012 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).  Mukund Sivaraman committed Jul 31, 2012 1343  void nodeFission(util::MemorySegment& mem_sgmt, DomainTreeNode& node,  Mukund Sivaraman committed Jul 31, 2012 1344 1345 1346 1347  const isc::dns::LabelSequence& new_prefix, const isc::dns::LabelSequence& new_suffix); //@}  Mukund Sivaraman committed Jul 31, 2012 1348  typename DomainTreeNode::DomainTreeNodePtr root_;  Mukund Sivaraman committed Jul 31, 2012 1349 1350  /// the node count of current tree unsigned int node_count_;  Mukund Sivaraman committed Jul 31, 2012 1351  /// search policy for domaintree  Mukund Sivaraman committed Jul 31, 2012 1352 1353 1354  const bool needsReturnEmptyNode_; };  Mukund Sivaraman committed Jul 31, 2012 1355 template  Mukund Sivaraman committed Jul 31, 2012 1356 DomainTree::DomainTree(bool returnEmptyNode) :  Mukund Sivaraman committed Jul 31, 2012 1357 1358 1359 1360 1361 1362  root_(NULL), node_count_(0), needsReturnEmptyNode_(returnEmptyNode) { }  Mukund Sivaraman committed Jul 31, 2012 1363 template  Mukund Sivaraman committed Jul 31, 2012 1364 DomainTree::~DomainTree() {  Mukund Sivaraman committed Jul 31, 2012 1365 1366 1367  assert(node_count_ == 0); }  Mukund Sivaraman committed Jul 31, 2012 1368 template  Mukund Sivaraman committed Jul 31, 2012 1369 void  Mukund Sivaraman committed Jul 31, 2012 1370 DomainTree::deleteHelper(util::MemorySegment& mem_sgmt,  Mukund Sivaraman committed Aug 03, 2012 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387  DomainTreeNode* 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* node = root; root = root->getLeft(); node->left_ = NULL; } else if (root->getRight() != NULL) { DomainTreeNode* node = root; root = root->getRight(); node->right_ = NULL; } else if (root->getDown() != NULL) { DomainTreeNode* node = root; root = root->getDown(); node->down_ = NULL;  Mukund Sivaraman committed Jul 31, 2012 1388  } else {  Mukund Sivaraman committed Aug 03, 2012 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* node = root; root = root->getParent();  JINMEI Tatuya committed Aug 20, 2012 1393  deleter(mem_sgmt, node->data_.get());  Mukund Sivaraman committed Aug 03, 2012 1394 1395  DomainTreeNode::destroy(mem_sgmt, node); --node_count_;  Mukund Sivaraman committed Jul 31, 2012 1396 1397 1398 1399  } } }  Mukund Sivaraman committed Jul 31, 2012 1400 template  Mukund Sivaraman committed Jul 31, 2012 1401 template  Mukund Sivaraman committed Jul 31, 2012 1402 1403 1404 1405 1406 typename DomainTree::Result DomainTree::find(const isc::dns::LabelSequence& target_labels_orig, DomainTreeNode** target, DomainTreeNodeChain& node_path, bool (*callback)(const DomainTreeNode&, CBARG),  Mukund Sivaraman committed Jul 31, 2012 1407  CBARG callback_arg) const  Mukund Sivaraman committed Jul 31, 2012 1408 1409 { if (!node_path.isEmpty()) {  Mukund Sivaraman committed Jul 31, 2012 1410 1411  isc_throw(isc::BadValue, "DomainTree::find is given a non empty chain");  Mukund Sivaraman committed Jul 31, 2012 1412 1413  }  Mukund Sivaraman committed Jul 31, 2012 1414  DomainTreeNode* node = root_.get();  Mukund Sivaraman committed Jul 31, 2012 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 &&  Mukund Sivaraman committed Jul 31, 2012 1442  node->getFlag(DomainTreeNode::FLAG_CALLBACK)) {  Mukund Sivaraman committed Jul 31, 2012 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); }  Mukund Sivaraman committed Jul 31, 2012 1461 template  Mukund Sivaraman committed Jul 31, 2012 1462 1463 const DomainTreeNode* DomainTree::nextNode(DomainTreeNodeChain& node_path) const {  Mukund Sivaraman committed Jul 31, 2012 1464  if (node_path.isEmpty()) {  Mukund Sivaraman committed Jul 31, 2012 1465 1466  isc_throw(isc::BadValue, "DomainTree::nextNode is given an empty chain");  Mukund Sivaraman committed Jul 31, 2012 1467 1468  }  Mukund Sivaraman committed Jul 31, 2012 1469  const DomainTreeNode* node = node_path.top();  Mukund Sivaraman committed Jul 31, 2012 1470 1471  // if node has sub domain, the next domain is the smallest // domain in sub domain tree  Mukund Sivaraman committed Jul 31, 2012 1472  const DomainTreeNode* down = node->getDown();  Mukund Sivaraman committed Jul 31, 2012 1473  if (down != NULL) {  Mukund Sivaraman committed Jul 31, 2012 1474  const DomainTreeNode* left_most = down;  Mukund Sivaraman committed Jul 31, 2012 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()) {  Mukund Sivaraman committed Jul 31, 2012 1488  const DomainTreeNode* up_node_successor =  Mukund Sivaraman committed Jul 31, 2012 1489  node_path.top()->successor();  Mukund Sivaraman committed Jul 31, 2012 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); }  Mukund Sivaraman committed Jul 31, 2012 1500 template  Mukund Sivaraman committed Jul 31, 2012 1501 1502 const DomainTreeNode* DomainTree::previousNode(DomainTreeNodeChain& node_path) const {  Mukund Sivaraman committed Jul 31, 2012 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.  Mukund Sivaraman committed Jul 31, 2012 1542  const DomainTreeNode* current(node_path.last_compared_);  Mukund Sivaraman committed Jul 31, 2012 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) {  Mukund Sivaraman committed Jul 31, 2012 1548  const DomainTreeNode* right;  Mukund Sivaraman committed Jul 31, 2012 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); }  Mukund Sivaraman committed Jul 31, 2012 1599  const DomainTreeNode* node(node_path.top());  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 1622  const DomainTreeNode* down;  Mukund Sivaraman committed Jul 31, 2012 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  Mukund Sivaraman committed Jul 31, 2012 1628  const DomainTreeNode* right;  Mukund Sivaraman committed Jul 31, 2012 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); }  Mukund Sivaraman committed Jul 31, 2012 1643 template  Mukund Sivaraman committed Jul 31, 2012 1644 1645 typename DomainTree::Result DomainTree::insert(util::MemorySegment& mem_sgmt,  Mukund Sivaraman committed Aug 02, 2012 1646 1647  const isc::dns::Name& target_name, DomainTreeNode** new_node)  Mukund Sivaraman committed Jul 31, 2012 1648 {  Mukund Sivaraman committed Jul 31, 2012 1649