BIND 10 #2218: update InMemoryZoneFinder::findNSEC3 using memory-efficient version

[BIND 10 Development]

#2218: update InMemoryZoneFinder::findNSEC3 using memory-efficient version
-------------------------------------+-------------------------------------
                   Reporter:         |                 Owner:  jinmei
  jinmei                             |                Status:  reviewing
                       Type:  task   |             Milestone:
                   Priority:         |  Sprint-20120925
  medium                             |            Resolution:
                  Component:  data   |             Sensitive:  0
  source                             |           Sub-Project:  DNS
                   Keywords:         |  Estimated Difficulty:  5
            Defect Severity:  N/A    |           Total Hours:  0
Feature Depending on Ticket:         |
  scalable inmemory                  |
        Add Hours to Ticket:  0      |
                  Internal?:  0      |
-------------------------------------+-------------------------------------

Comment (by jinmei):

 Replying to [comment:10 muks]:

 Some substantial points first:

 > >   - secondly, I don't like to expose too much of `DomainTreeNode`
 > >     internals.  Specifically, I don't like to make predecessor() and
 > >     successor() just for this purpose.  Likewise, I don't like to
 > >     introduce things like getLargestInSubTree() as a public method of
 > >     `DomainTreeNode`.  In general, I prefer extending the node chain
 > >     interfaces for operations that require moving inside the tree.
 >
 > For this case, I want to disagree. `DomainTree` is more or less a BST
 with walking capability. `predecessor()` and `successor()` are basic
 operations on such a data structure, and if there is the use-case, I don't
 think we should force to keep these hidden. The added methods are
 operations on nodes, and are basic operations. I feel adding them in the
 node chain would not be ideal. I thought of adding a method like
 `getNSEC3CoverNode()` to the node chain, but such things seem to be
 misplaced in the `DomainTree`.

 First, regarding `successor()`: at least your revised code doesn't use
 `successor()`, so it can (and I would say should) be private again.
 Next, as for `predecessor()`: you almost reimplemented the logic that
 is already available `DomainTree::previousNode` as a result of using
 `predecessor()`.  Apart from whether it makes sense to expose
 `predecessor()`, the resulting code is duplicate and IMO much more
 unreadable.  The whole re-invented logic can be much more simplified
 if you use previousNode:

 {{{#!cpp
         } else {
             const ZoneNode* last_node = chain.getLastComparedNode();
             while ((covering_node = tree.previousNode(chain)) != NULL &&
                    covering_node->isEmpty()) {
                 ;
             }
             if (covering_node == NULL) {
                 covering_node = last_node->getLargestInSubTree();
             }

             if (!recursive) {   // in non recursive mode, we are done.
 ...
 }}}

 If you agree that this one is simpler and more readable, then we also
 don't need to make `predecessor()` public either, and I'd suggest
 keeping it private.

 > >     Also, due to the special structure of the NSEC3 tree, "in sub
 > >     tree" property is not really necessary.  While exploiting this
 > >     fact itself may be controversial, I personally like to exploit it
 > >     than tweaking the node class (and this code already exploits some
 > >     of the special nature of the NSEC3 anyway).
 >
 > I don't follow what you mean by exploit here. Do you mean not have the
 tree-of-tree structure? `TreeNodeRRset` gets its name directly from the
 node in the tree-of-trees.

 What I meant (re-reading it now, I admit the original comment wasn't
 clear) is that I'd rather define and use something like
 `TreeNode* DomainTree::largestNode()`, which returns the largest node
 in the tree of tree.  In the case of the NSEC3 tree, this should be
 the same as "largest in subtree" (in the subtree of NSEC3 hash names).

 I admit the encapsulation of `DomainTree` isn't really clean, and we
 sometimes allow the applications to use the knowledge of its internal
 structure.  But when possible, I'd like to hide such details as it's a
 "tree of tree" as much as possible, and have applications use
 `DomainTree` just like some kind of abstract container.  The concept
 of "getting the largest entry" can exist for any type of container
 that has the notion of ordering, but `getLargestInSubTree` looks too
 much rely on specific internal details of it.  It might be less likely
 that we'll fundamentally revise the internal details (e.g., like
 changing tree to hash), but if we have choices for some purpose that
 have comparable costs, I'd like to choose the one that can hide
 internal details more.

-- 
Ticket URL: <http://bind10.isc.org/ticket/2218#comment:11>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development