BIND 10 #1803: update the RBTreeNodeChain class to identify the "previous" node

[BIND 10 Development]

#1803: update the RBTreeNodeChain class to identify the "previous" node
-------------------------------------+-------------------------------------
            Reporter:  jinmei        |                        Owner:
                Type:  task          |                       Status:  new
            Priority:  medium        |                    Milestone:  New
           Component:  data source   |  Tasks
           Sensitive:  0             |                     Keywords:
         Sub-Project:  DNS           |              Defect Severity:  N/A
Estimated Difficulty:  0             |  Feature Depending on Ticket:  in-
         Total Hours:  0             |  memory NSEC
                                     |          Add Hours to Ticket:  0
                                     |                    Internal?:  0
-------------------------------------+-------------------------------------
 This is necessary for in-memory NSEC, and will be the trickiest part of
 the entire feature.

 What I'd do is as follows (which is not the only way to implement
 this).  This will be pretty big, so I propose separating the step
 "1" below from others.  Even without this step some other tasks can be
 done.

 Introduce two new private members to `RBTreeNodeChain`:

 {{{#!c++
     const RBNode<T>* cursor_node_;
     int cursor_level_;
 }}}

 These values are invalid (NULL and -1 or something) until the
 following new method is called:

 {{{#!c++
 template <typename T>
 const RBNode<T>* RBTreeNodeChain::getPreviousNode();
 }}}

 When first time it's called after find(), it identifies the node in
 the tree whose corresponding name is the closest (but not equal) to
 the qname of find() in the sorted list of zone names smaller than the
 qname (that is, that's the node for the "previous name" of the qname).
 Then cursor_node_ is set to the identified node, and cursor_level_ is
 set to the level in the nodes_ array corresponding to that node.  The
 method returns a pointer to the identified cursor_node_.

 This process is complicated and depends on how the preceding find()
 ends:

 1. if last_comparison_.getRelation() is COMMONANCESTOR,
    last_comparison_.getCommonLabels() is 1, last_compared_.getLength() !=
 1,
    (the condition so far means the search stops due to a binary search
    and last_comparison_.getOrder() > 0, then that means find() stopped
    by seeing a node whose name (corresponding to last_compared_) is
    smaller than the qname.  This node may or may not be "the previous
    node".  Identify the real previous node as described in the
    following comment of BIND 9's lib/dns/rbt.c:
 {{{#!c
                                  * If the stop node is less, it is not
                                  * necessarily the predecessor.  If the
 stop
                                  * node has a down pointer, then the real
                                  * predecessor is at the end of a level
 below
                                  * (not necessarily the next level).
                                  * Move down levels until the rightmost
 node
                                  * does not have a down pointer.
 }}}

 2. otherwise, last_compared_ corresponds to either the qname or the
    immediate successor (wrt DNSSEC order) of the qname.  Identify the
    "previous node" of it using the same algorithm as BIND 9's
    lib/dns/rbt.c:dns_rbtnodechain_prev() (our rbtree is simpler so we
    may be able to simplify some part of it).

 In the second and later calls of this method, it will identify the
 node in the rbtree corresponding to the previous name of cursor_node_
 wrt the DNSSEC order, and returns a pointer to that node.
 cursor_node_ and cursor_level_ are updated accordingly (so this method
 cannot be a const member function).  This node can be identified using
 the same algorithm as case 2 above.

 This method can be called repeatedly to examine "previous" nodes
 toward the zone origin.

 Carefully test all cases in the algorithm.  Also don't forget what
 should happen if it's called beyond the very root of the tree.

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