BIND 10 #2750: support DomainTree::remove()
BIND 10 Development
do-not-reply at isc.org
Thu Oct 3 07:44:08 UTC 2013
#2750: support DomainTree::remove()
-------------------------------------+-------------------------------------
Reporter: jinmei | Owner: muks
Type: task | Status:
Priority: medium | closed
Component: data source | Milestone:
Keywords: | Sprint-20131015
Sensitive: 0 | Resolution: fixed
Sub-Project: DNS | CVSS Scoring:
Estimated Difficulty: 7 | Defect Severity: N/A
Total Hours: 0 | Feature Depending on Ticket:
| shared memory data source
| Add Hours to Ticket: 0
| Internal?: 0
-------------------------------------+-------------------------------------
Changes (by muks):
* status: reviewing => closed
* resolution: => fixed
Comment:
Merged to `master` branch in commit
`d3dbe8e1643358d4f88cdbb7a16a32fd384b85b1`:
{{{
* 08bc7db [2750] Reduce another layer of find() wrapper
* a0aaef8 [2750] Reduce the number of find() wrappers
* bd9f2d3 [2750] Rename method
* 52d44bc [2750] Invert condition statement, swapping respective blocks
* 339f201 [2750] Re-indent code
* 8b88f18 [2750] Add a test that does a remove() on tree with empty upper
nodes
* b1e65b9 [2750] Add some more checks and comments to .remove test
* c5c85a0 [2750] Don't delete nodes with down pointers
* d79db92 [2750] Handle root of forest case too
* 3984b23 [2750] exchange() nodes only when node to be removed has both
children
* 0edf1c3 [2750] Check that sub-tree roots have the flag set
* 9eeab2e [2750] Remove excess wrapper methods
* 63a7f8b [2750] Add comments in exchange() about asymmetric code
* 8090d2c [2750] Rename variable to lower
* 05b3886 [2750] Introduce getSibling() again as a static function
* 151a2b8 [2750] Use std::max()
* a47c17e [2750] Remove node fusion functionality completely
* a50e423 [2750] Fix typo
* 663bc38 [2750] Test the passed set instead of the tree (true at the end
of the unittest)
* 49c7199 [2750] Simplify code
* 0a5bd2e [2750] Increase number of nodes to 1024
* 8380acd [2750] Remove some temporary tests
* c0e91c5 [2750] Add comprehensive test for DomainTree validity with
insert() and remove()
* b30ae17 [2750] Add a comment describing the test
* e2cb0a3 [2750] Move the RNG to a class variable (so the same RNG can be
reused)
* 63e54b1 [2750] Add methods to check RB tree properties (and use them in
tests)
* da0e9a8 [2750] Replace height check with getHeight() method
* b403553 [2750] Use more optimal form of color testing where possible
* 49fa0ba [2750] Finish documenting the red-black tree remove rebalance
operation
* 7cf3929 [2750] Remove redundant part of condition
* 0467d75 [2750] Add/update RB tree delete rebalancing comments
* 6024678 [2750] Rewrite code to use a similar block as previous case
* 967e79e [2750] Fix tree rotation direction
* ec1cb0b [2750] Remove redundant NULL test
* 1d38fe3 [2750] Reduce code by using getColor()
* 4ee1f33 [2750] Remove redundant condition to check if sibling is black
* d15a492 [2750] Update comment
* 313c564 [2750] Fix overall loop condition in removeRebalance()
* 8a4c8c4 [2750] Add graphs for case 3
* 091b858 [2750] Make various updates (see full log)
* 2a07912 [2750] Update some checks
* 275d632 [2750] Recompute sibling after rotations
* 23078e9 [2750] Remove redundant argument
* 73d7a95 [2750] Simplify condition
* 927411d [2750] Add comments for rebalancing code in remove()
* b6ca9a8 [2750] Add code comments
* 4798d92 [2750] Re-arrange find() methods so that protos come before uses
* 8829d94 [2750] Add documentation
* bf29846 [2750] Check that having 2 nodes in subtree doesn't cause node
fusion
* 8a6e0a6 [2750] Update comment
* 65d3cd2 [2750] Test multiple occurrences of node fusion in a single step
upwards in the forest
* 82fded3 [2750] Add node fusion test where there is data in the parent
node
* 4d5859d [2750] Add node fusion tests
* 99b2d6f [2750] Add a first proper remove() unittest
* 31e8258 [2750] Unify copies of test data
* 1d32d63 [2750] Add initial delete rebalance implementation
* b27c26f [2750] Move common code into a helper method
* 9801de5 [2750] Simplify the code to set the parent-child relationship
* a2bc0e2 [2750] Set the new node's down pointer too
* 8bda455 [2750] Simplify code somewhat
* 6be8194 [2750] Add remove() and tryNodeFusion() implementations
* 038082d [2750] Adjust more pointers to make the exchange complete
* 9184190 [2750] Adjust a few more pointers to make the exchange complete
* 7b722a2 [2750] Add a comment about why down_ is not swapped
* 730aac8 [2750] Start to remove() with initial exchange with a leaf node
* 5ffd53d [2750] Add non-const variants of more find() methods
* 7025053 [2750] Make public method names consistent
* 7f0bb92 [2750] Add getSibling() method
* c369c2c [2750] Add proto for a method to delete a tree node
* 3674f82 [2750] Fix indent level
* 79c66d3 [2750] Add non-const variant of find()
* 9b06e69 [2750] Add non-const variant of largestNode()
* 0b3041d [2750] Add non-const variants of successor() and predecessor()
* 36db9cb [2750] Remove redundant variable
* 4d4b0dc [2750] Add non-const variant of abstractSuccessor()
* 004adb2 [2750] Add non-const variant of getUpperNode()
* 8ee0490 [2750] Add non-const variant of getSubTreeRoot()
}}}
Replying to [comment:22 vorner]:
> What about changing it to something like „The full absolute nodes of the
tree (the tree also contains ".", which is not included in this list)“?
This has been changed in commit `bb0ac07b4621308695146918e37d4f2a68e2a9bd`
on the `master` branch.
The following `ChangeLog` message was pushed for #2750 and #2751 in commit
`acbe4afb25b5f7eb6da8e259d9d8a78526bccd80` on the `master` branch:
{{{
+684. [func] muks, vorner
+ API support to delete zone data has been added. With this,
+ DomainTree and RdataSet which form the central zone data
+ structures of b10-auth allow deletion of names and RR data
+ respectively.
+ (Trac #2750, git d3dbe8e1643358d4f88cdbb7a16a32fd384b85b1)
+ (Trac #2751, git 7430591b4ae4c7052cab86ed17d0221db3b524a8)
+
}}}
Resolving as fixed. Thank you for the reviews Michal.
--
Ticket URL: <http://bind10.isc.org/ticket/2750#comment:23>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development
More information about the bind10-tickets
mailing list