BIND 10 #2811: Make some DomainTree code updates

[BIND 10 Development]

#2811: Make some DomainTree code updates
-------------------------------------+-------------------------------------
            Reporter:  muks          |                        Owner:
                Type:  enhancement   |  UnAssigned
            Priority:  medium        |                       Status:
           Component:  data source   |  reviewing
            Keywords:                |                    Milestone:  Next-
           Sensitive:  0             |  Sprint-Proposed
         Sub-Project:  DNS           |                   Resolution:
Estimated Difficulty:  0             |                 CVSS Scoring:
         Total Hours:  0             |              Defect Severity:  N/A
                                     |  Feature Depending on Ticket:
                                     |          Add Hours to Ticket:  0
                                     |                    Internal?:  0
-------------------------------------+-------------------------------------
Description changed by muks:

Old description:

> This is a ticket to track some `DomainTree` code updates that I've made
> in a private branch.
>
> * The rebalance-after-insert code is reorganized to make it more
> straightforward to understand, and it's better commented.
>
> * There are tests (with random and sorted data) that verify that the tree
> is balanced, and doesn't go over the red-black theoretical limit. It
> constructs a random large million+ name zone and checks that the distance
> from every node to its subtree root is within limit. This is a check that
> was not implemented and we should have this as performance correctness
> proof, as the DomainTree is so central to our memory datasrc performance.
>
> Though the deletion ticket #2750 is independent, the balance testcase
> will be useful for the deletion work.

New description:

 This is a ticket to track some `DomainTree` code updates that I've made in
 a private branch.

 * The rebalance-after-insert code is reorganized to make it more
 straightforward to understand, and it's better commented.

 * There are tests (with random and sorted data) that verify that the tree
 is balanced, and doesn't go over the red-black theoretical limit. It
 constructs a random large million+ name zone and checks that the distance
 from every node to its subtree root is within limit. This is a check that
 was not implemented and we should have this as performance correctness
 proof, as the DomainTree is so central to our memory datasrc performance.

 * Don't rebalance subtree roots.

 Though the deletion ticket #2750 is independent, the balance testcase will
 be useful for the deletion work.

--

-- 
Ticket URL: <http://bind10.isc.org/ticket/2811#comment:4>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development