Opened 7 years ago

Closed 7 years ago

#2054 closed defect (fixed)

make sure RBTree nodeFission() preserves the name of the original node

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

Description

Implement this note:

// Note: when we redesign this (still keeping the basic concept), we should
// change this part so the newly created node will be used for the inserted
// name (and therefore the name for the existing node doesn't change).
// Otherwise, things like shortcut links between nodes won't work.

We could do it at the time of implementing the memory-scalable version
of rbtree, but assuming we still need some initial design work first,
it probably makes sense to do this cleanup at the moment, so we won't
inherit this flaw in the new implementation.

Subtickets

Change History (15)

comment:1 follow-up: Changed 7 years ago by vorner

Do we really want to have a red-black tree in the redesigned version? In my understanding, there are better options, like AVL tree (the update takes slightly longer, but it is better balanced, therefore faster to search).

comment:2 Changed 7 years ago by muks

Aren't both O(log N) to find where to insert? Does it matter which one we use (constant factor change in heights)?

comment:3 Changed 7 years ago by vorner

Yes, they are both O(log N). But the constant factors do matter when we are on the performance sensitive path. The red-black tree can be up to twice deeper than AVL one.

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

Replying to vorner:

Do we really want to have a red-black tree in the redesigned version?

The use of red-black tree(-based tree) is not a given condition. If
we have a better option we can switch. However:

In my understanding, there are better options, like AVL tree (the update takes slightly longer, but it is better balanced, therefore faster to search).

  • I personally think it makes more sense to complete this version basically just by making it more memory-efficient rather than also revising the algorithm more fundamentally.
  • The performance tradeoff between search and update does not seem to be very obvious to me. We're basically trying to improve query processing performance by reducing the number of looks, and the smaller number (maybe even one) of tree lookup won't be a dominant part in the entire query processing. Meanwhile, now that our in-memory data source is going to be more dynamic, update performance may matter much than before.

comment:5 Changed 7 years ago by jinmei

  • Milestone set to Next-Sprint-Proposed

comment:6 Changed 7 years ago by jinmei

This will also help the memory-efficient version of RBTree cleaner.
See the comment of nodeFission() at branch trac2091b.

comment:7 Changed 7 years ago by jelte

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

comment:8 Changed 7 years ago by muks

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

Picking.

comment:9 Changed 7 years ago by muks

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

Up for review.

comment:10 Changed 7 years ago by jinmei

Please make sure all subtle cases are covered by tests.

This branch doesn't seem to have new tests, and I suspect we need
some additional tests to cover all possible cases.

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

It was only the left-child's fission case that needed an additional test. It has been added now. The others are covered by the rest of the tests.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 7 years ago by jinmei

Replying to muks:

It was only the left-child's fission case that needed an additional test. It has been added now. The others are covered by the rest of the tests.

It mostly looks okay, except the documentation should also be updated.
I've committed a suggested change. If you're okay with it, please
merge.

p.s. Please don't forget merging this change to memory/domaintree.h
when it's ready.

p.p.s. please consider picking up an open review request before
proceeding to yet another development task. From a quick look #2136
has been open for quite some time.

comment:13 Changed 7 years ago by jinmei

  • Owner changed from UnAssigned to muks

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

Replying to jinmei:

Replying to muks:

It was only the left-child's fission case that needed an additional test. It has been added now. The others are covered by the rest of the tests.

It mostly looks okay, except the documentation should also be updated.
I've committed a suggested change. If you're okay with it, please
merge.

This looks fine.

p.s. Please don't forget merging this change to memory/domaintree.h
when it's ready.

*nod*. I've added a comment in #2105 to do this.

p.p.s. please consider picking up an open review request before
proceeding to yet another development task. From a quick look #2136
has been open for quite some time.

Will look at the review queue after I'm done with current bugs.

comment:15 Changed 7 years ago by muks

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

Merged to master in commit 4f9f077ffae95f15f162d8f640c4896fe56b7934:

* dca052b [2054] suggested doc update for nodeFission().
* 72539e9 [2054] Add an additional node fission testcase for left-child case
* a82d0b1 [2054] Justify comments
* e9eec8d [2054] In nodeFission(), use the newly created node for the inserted name

Resolving as fixed. Thank you for the reviews Jinmei.

Note: See TracTickets for help on using tickets.