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:  hanfeng  
          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            |  
------------------------------+---------------------------------------------
Changes (by jinmei):

  * owner:  jinmei => hanfeng


Comment:

 Some more generic comments.  I'll give this ticket back to the author at
 this point because we'll need some substantial changes.

  - there seem to be many points we can make things (method
    parameter, temporary variables in a function, etc).  please
    "constify" things wherever possible.
  - IMO we shouldn't use C-style cast.  also, apparently these casts
    are to remove const, but (if possible) it's much better if we can
    (re)organize the code so that we don't have to break constness in
    the first place.  I'd suggest revisiting the logic to see if we can
    achieve what we do without relying on const_cast.
  - overall the code doesn't seem to be exception safe where it
    involves resource allocation.  for example, the following code
    fragment isn't exception safe.
 {{{
                     current->setDownTree(new RBTree());
                     RBNode* sub_root;
                     current->down_->insert(sub_name, &sub_root);
 }}}
    because insert() also involves resource allocation and it can throw
    on failure.  Furthermore, even if we make it exception safe in a
    straightforward way, the resulting code won't provide strong
    exception guarantee, i.e., if an exception is thrown the tree
    structure cannot always revert to the original state.  The original
    BIND 9 implementation ensures this property.  We'll probably need
    the same for this structure.

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