BIND 10 #2150: allow RBTree::find() to start at a lower level

[BIND 10 Development]

#2150: allow RBTree::find() to start at a lower level
-------------------------------------+-------------------------------------
            Reporter:  jinmei        |                        Owner:
                Type:  task          |                       Status:  new
            Priority:  medium        |                    Milestone:  New
           Component:  Unclassified  |  Tasks
           Sensitive:  0             |                     Keywords:
         Sub-Project:  DNS           |              Defect Severity:  N/A
Estimated Difficulty:  0             |  Feature Depending on Ticket:
         Total Hours:  0             |  scalable inmemory
                                     |          Add Hours to Ticket:  0
                                     |                    Internal?:  0
-------------------------------------+-------------------------------------
 We should consider an extension to RBTree::find() so that we can
 specify the start point of the search (instead of the very root of the
 tree-of-tree) in the form of `RBTreeNodeChain`.  This version of
 find() would take a `LabelSequence` (non absolute) and
 `RBTreeNodeChain`, and start from the top (deepest) node of the chain
 until it finds the given label sequence below the start point.  The
 passed node chain will be revised to store the new result on top of
 the given one.

 This will make the wildcard search more efficient:
 {{{#!cpp
             // Now the wildcard should be the best match.
             const Name wildcard(Name("*").concatenate(
                                     node_path.getAbsoluteName()));

             // Clear the node_path so that we don't keep incorrect (NSEC)
             // context
             node_path.clear();
             DomainTree::Result result(domains_.find(wildcard, &node,
                                                     node_path));
 }}}

 because we wouldn't have to concatenate names or labels and would be
 able to skip a first few levels of tree-of-tree search.

 I also guess we can use the same optimization for making some NSEC
 search more efficient.

 I suggest considering doing this task before #2110.

-- 
Ticket URL: <http://bind10.isc.org/ticket/2150>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development