Opened 7 years ago

Closed 7 years ago

#2150 closed task (fixed)

Allow DomainTree::find() to start at a lower level

Reported by: jinmei Owned by: muks
Priority: medium Milestone: Sprint-20120918
Component: Unclassified Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity: N/A
Sub-Project: DNS Feature Depending on Ticket: scalable inmemory
Estimated Difficulty: 5 Add Hours to Ticket: 0
Total Hours: 0 Internal?: no

Description (last modified by muks)

(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:

            // 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.

Subtickets

Change History (15)

comment:1 Changed 7 years ago by shane

  • Milestone changed from New Tasks to Next-Sprint-Proposed

comment:2 Changed 7 years ago by jinmei

  • Milestone set to Next-Sprint-Proposed

comment:3 Changed 7 years ago by jinmei

  • Description modified (diff)

comment:4 Changed 7 years ago by jelte

  • Milestone changed from Next-Sprint-Proposed to Sprint-20120918

comment:5 Changed 7 years ago by muks

  • Owner set to muks
  • Status changed from new to assigned

Picking bug.

comment:6 Changed 7 years ago by muks

  • Owner changed from muks to UnAssigned
  • Status changed from assigned to reviewing

Up for review.

comment:7 follow-up: Changed 7 years ago by muks

This has to be patched to DomainTree too btw, but I'll do that once RBTree is reviewed and ready.

comment:8 in reply to: ↑ 7 Changed 7 years ago by jinmei

Replying to muks:

This has to be patched to DomainTree too btw, but I'll do that once RBTree is reviewed and ready.

We'll only need it for DomainTree. Let's not tweak RBTree any
more and do focus on updating DomainTree exclusively. Once the
current update tasks are done, RBTree will be gone.

If no one started review, I suggest moving the changes to
DomainTree and reverting changes to RBTree (which will make review
process easier).

I also wonder why we chose this task for this sprint...I thought it's
a kind of optional optimization, and I'm afraid we don't have time for
optional things at this stage. Maybe too late though...

comment:9 Changed 7 years ago by jinmei

  • Owner changed from UnAssigned to muks

comment:10 Changed 7 years ago by muks

  • Description modified (diff)
  • Summary changed from allow RBTree::find() to start at a lower level to Allow DomainTree::find() to start at a lower level

comment:11 Changed 7 years ago by muks

  • Owner changed from muks to UnAssigned

Moved changes to DomainTree class. This is now in the trac2150_2 branch afresh so that the RBTree class is untouched.

comment:12 follow-up: Changed 7 years ago by jelte

  • Owner changed from UnAssigned to muks

Looks good, I have a few suggestions for additional tests;

  • the other failure case for node_path and labelsequence absoluteness (i.e. an empty path and a non-absolute labelsequence) if this isn't tested somewhere else yet
  • a child that is more than one node away from top() (btw it looks like the tree overview at the start of the unit tests file is wrong?)
  • a search for a labelsequence from a lower node that would have a different result would it have been started in a different node or absolute (to make sure it doesn't start out higher anyway).

comment:13 in reply to: ↑ 12 Changed 7 years ago by muks

  • Owner changed from muks to jelte

Hi Jelte

Replying to jelte:

Looks good, I have a few suggestions for additional tests;

  • the other failure case for node_path and labelsequence absoluteness (i.e. an empty path and a non-absolute labelsequence) if this isn't tested somewhere else yet

Added, but I thought the other tests took care of it! :)

  • a child that is more than one node away from top() (btw it looks like the tree overview at the start of the unit tests file is wrong?)

From top, I am guessing you mean chain.top(). Added. :)

The tree diagram looks ok to me. What do you think is wrong with it? In case you want to see what it really is like, make a fstream and call dtree_expose_empty_node.dumpDot() on it. Run it through GraphViz?'s dot utility (dot -Tpng foo.dot > foo.png) and you can compare this and the text tree diagram.

  • a search for a labelsequence from a lower node that would have a different result would it have been started in a different node or absolute (to make sure it doesn't start out higher anyway).

Added. :)

comment:14 Changed 7 years ago by jelte

  • Owner changed from jelte to muks

Ah, I was just confused about the format of the trees.

Looks ok, this can be merged as well.

comment:15 Changed 7 years ago by muks

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

Merged to master in commit e46d39396cca6ed4b401a265383e5f89b9b7c7f0:

* 5b8f36f[2150] Add a diagram of the DomainTree after the node has been added
* dc8237b [2150] Add test to find the same non-absolute label sequence at two different places
* 4e25ff7 [2150] Find a relative label sequence that's more than 1 node away from chain.top()
* 65ef868 [2150] Check label sequence to see that it's correct
* 0ccc72e [2150] Clear chain before re-use
* 0b66c1d [2150] Check that non-absolute label sequence + empty chain throws in find()
* 3c03d32 [2150] Allow DomainTree::find() to start at a lower level

Resolving as fixed. Thank you for the reviews Jelte.

Note: See TracTickets for help on using tickets.