Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#1803 closed task (complete)

update the RBTreeNodeChain class to identify the "previous" node

Reported by: jinmei Owned by: jelte
Priority: medium Milestone: Sprint-20120515
Component: data source Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity: N/A
Sub-Project: DNS Feature Depending on Ticket: in-memory NSEC
Estimated Difficulty: 7 Add Hours to Ticket: 0
Total Hours: 6.49 Internal?: no

Description

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:

    const RBNode<T>* cursor_node_;
    int cursor_level_;

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

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:
                                     * 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.
    
  1. 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.

Subtickets

Change History (10)

comment:1 Changed 8 years ago by jelte

  • Estimated Difficulty changed from 0 to 7

comment:2 Changed 8 years ago by jelte

  • Milestone changed from New Tasks to Sprint-20120515

comment:3 Changed 8 years ago by vorner

  • Owner set to vorner
  • Status changed from new to accepted

comment:4 Changed 8 years ago by vorner

  • Owner changed from vorner to UnAssigned
  • Status changed from accepted to reviewing

It should be ready for review. Because it was not clear to me what the split
with #1804 should be, I just put the whole feature into the #1803 ticket. It
doesn't seem to be that big anyway.

I didn't add the new members, I implemented it in a way similar to the nextNode
was ‒ changing the current node_path (which would be needed anyway with the new
members, the only difference is I destroy the last comparison result during the
processing).

Also, bit of the code is little bit dense, but I hope the comments there help a
little bit to explain it.

comment:5 Changed 8 years ago by muks

  • Owner changed from UnAssigned to muks

I've already been reading this code, so I might as well pick up this bug for review :)

comment:6 Changed 8 years ago by jinmei

lcov indicates that these parts of the code aren't tested:

                        // A small trick. The current may be NULLNODE, but
                        // such node has the right_ pointer and it is equal
                        // to NULLNODE.
                        current = current->right_;

and

        // We got past the first one. So, we're returning NULL from
        // now on.
        return (NULL);

If these are not false positives, please make sure these cases are
covered by tests.

comment:7 Changed 8 years ago by muks

  • Owner changed from muks to vorner

Hi vorner

  1. The previousNode() implementation looks good to me. I have pushed a few minor patches to the tree. The main thing to check are the comment changes. Some of the old rbtree comments were obsolete.
  1. RBNode's successor() and predecessor() are correct. But they should be given direct tests for edgecases. If they are not instantiable from outside, maybe they should be for the sake of being testable.

comment:8 Changed 8 years ago by muks

  • Owner changed from vorner to jelte

Reassigning to jelte for review so it can get into master quickly.

comment:9 Changed 8 years ago by jelte

  • Resolution set to complete
  • Status changed from reviewing to closed

It looked good, and has been merged.

comment:10 Changed 8 years ago by vorner

  • Total Hours changed from 0 to 6.49
Note: See TracTickets for help on using tickets.