Opened 8 years ago

Closed 8 years ago

#1804 closed task (complete)

update the RBTreeNodeChain class to identify the "previous" node (2nd part)

Reported by: jinmei Owned by: vorner
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: 4 Add Hours to Ticket: 0
Total Hours: 0 Internal?: no


This is the separated part of #1803, that is, implementing
the following part of RBTreeNodeChain::getPreviousNode():

  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.

It could be done in parallel with #1803, but is probably better to
start after #1803.


Change History (5)

comment:1 Changed 8 years ago by jelte

  • Estimated Difficulty changed from 0 to 4

comment:2 Changed 8 years ago by jelte

  • Milestone changed from New Tasks to Sprint-20120515

comment:3 Changed 8 years ago by vorner

I'm not completely sure about the splitting between #1803 and #1804, so this should better wait.

comment:4 Changed 8 years ago by vorner

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

I'm taking this, to stop anybody from implementing again what was done in #1803.

comment:5 Changed 8 years ago by jelte

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

Merged as part of the merge of #1803

Note: See TracTickets for help on using tickets.