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

  * owner:  hanfeng => jinmei


Comment:

 Replying to [comment:36 jinmei]:
 > First, the previous comment about test coverage doesn't seem to be
 > addressed:
 Done
 >
 > '''namespace helper'''
 > Okay, but leave a comment on indent() that the only reason for having
 > it as a member function (even though it doesn't have to get access to
 > the private members) is to hide a helper function.
 comment added

 > '''RBTreeColor'''
 >  - RBTreeColor: it seems this can (should) be non public
 Basically, no matter which RBTree class will be instantiated(according to
 the template parameter)
 they all use the same color, so I put it outside RBNode and RBTree
 template class definition.

 >
 > >>  - type of data_: I don't think it works well.  getting a pointer
 from
 > Hmm, I don't see why we cannot use smart pointers (of course we
 > couldn't call "delete" for example but addressing such things should
 > be quite trivial).
 Now use shared_ptr to save the node data

 > '''RBTree class definition'''
 > Okay, and I'll refactor the resulting code a little bit:
 > {{{
 >                 if (!node->isEmpty()) {
 >                     ret = RBTree<T>::PARTIALMATCH;
 >                     *target = node;
 >                 }
 >                 node = node->down_;
 > }}}
 Modified accordingly.

 > '''nodeFission'''
 > >>  - down_node initialization could be simplified (and more efficient):
 > >
 > There's still redundant re-initialization
 Modified accordingly

 > Also, now that RBNode<T>::swap() isn't used, let's remove them (if
 > it's needed in future, reintroduce it at that point).
 swap is removed

 > The revised logic for the subdomain case looks okay.  Actually, I like
 > the simplified code.  One nit though: as far as I can see we don't
 > need the auto_ptr hack at the end of the function:
 I will keep it. actually, start from memory allocation to
 the end of the function call, we are not sure whether there will be
 exception raised

 >
 > '''RBTree<T>::findHelper'''
 Comment is added.

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