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

[BIND 10 Development]

#2150: Allow DomainTree::find() to start at a lower level
-------------------------------------+-------------------------------------
                   Reporter:         |                 Owner:  muks
  jinmei                             |                Status:  reviewing
                       Type:  task   |             Milestone:
                   Priority:         |  Sprint-20120918
  medium                             |            Resolution:
                  Component:         |             Sensitive:  0
  Unclassified                       |           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      |
-------------------------------------+-------------------------------------
Description changed by muks:

Old description:

> (revised on Aug29: based on our current progress I suspect we don't
> have time to do it before the September release).
>
> 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.

New description:

 (revised on Aug29: based on our current progress I suspect we don't
 have time to do it before the September release).

 We should consider an extension to DomainTree::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 `DomainTreeNodeChain`.  This version of
 find() would take a `LabelSequence` (non absolute) and
 `DomainTreeNodeChain`, 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#comment:10>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development