BIND 10 #397: Port generic red-black tree (RBT) data structure from BIND-9

[BIND 10 Development]

#397: Port generic red-black tree (RBT) data structure from BIND-9
------------------------------+---------------------------------------------
      Reporter:  zzchen_pku   |        Owner:  jinmei   
          Type:  enhancement  |       Status:  reviewing
      Priority:  major        |    Milestone:           
     Component:  data source  |   Resolution:           
      Keywords:               |    Sensitive:  0        
Estimatedhours:  0.0          |        Hours:  0        
      Billable:  1            |   Totalhours:  0        
      Internal:  0            |  
------------------------------+---------------------------------------------

Comment(by jinmei):

 The current use of NULLNODE doesn't make sense to me:
  - passing a "nullnode" to RBNode constructors makes the code fragile.  If
 the caller omit the parameter or intentionally specifies NULL, many part
 of the code won't work correctly because they assume the specific property
 of the nullnode.  For example, successor() will be broken.
  - btw, the doxygen comment of the constructor doesn't parse to me.
  - in either case, null node determination like this doesn't seem to be
 good:
 {{{
     if (right_ != right_->right_) {
 }}}
    it's an implicit statement and therefore less understandable, and is
 fragile in that it assumes the specific structure of the null node.

 A related note: one of the RBNode constructors were unused.

 I've committed a proposed change to address these concerns (r3617).
 Please check.

 (to be continued)

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