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:

 First, the previous comment about test coverage doesn't seem to be
 addressed:
 http://bind10.isc.org/ticket/397#comment:30

 '''namespace helper'''
 > >  - this will cause duplicate definitions of the functions defined in
 > >    the namespace, resulting in a linker error once more than one .cc
 > indent has been moved to RBTree has a static helper function, name
 > operator plus is made inline
 >
 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.

 '''RBTreeColor'''
 > >  - my previous comment hasn't been addressed:
 > >    - RBTreeColor: a minor point, but why does it start with 1?
 > It's quite personal prefer, no reason :)
 >
 Oops, I referenced the wrong previous comment.  I intended this one:
  - RBTreeColor: it seems this can (should) be non public

 >>  - type of data_: I don't think it works well.  getting a pointer from
 [snip]
 > I quite agree it's bad to split the alloc and dealloc into different
 > class. I think a better
 > way is let end user provider deconstruction functor, since
 boost::functor
 > isn't allowed to use
 > now, so i haven't figure out a clean way to do it. I will keep the
 > simplest design now, and think about it. also current design make some
 > problem to smart point as template parameter
 >
 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).

 '''RBTree class definition'''

  - '''RBTree<T>::findHelper'''
 > >  - this assumption doesn't hold:
 {{{
                 if (node->isEmpty()) {
                     assert(node->down_ != NULL);
 }}}
 > yes the assumption isn't correct, I have fixed it
 >
 Okay, and I'll refactor the resulting code a little bit:
 {{{
                 if (!node->isEmpty()) {
                     ret = RBTree<T>::PARTIALMATCH;
                     *target = node;
                 }
                 node = node->down_;
 }}}

 '''nodeFission'''
 >>  - down_node initialization could be simplified (and more efficient):
 >
 This point isn't addressed.
 {{{
     std::auto_ptr<RBNode<T> > down_node(new RBNode<T>(sub_name));
 }}}
 > >  - do we need to do RBNode::swap()?  After swapping, 3 of the six
 > >    member variables of node and down_node are replaced anyway, and we
 > >    could do the same thing with the same number of lines without using
 > The way you proposed is more efficient, i have modified. But I cann't
 > reuse the nodeFission
 > logic to do new down node creation, since there is no fission at all.
 > Because use NULLNODE as
 > the down node default value, the creation new down node in insert is
 > removed please have a check
 >
 There's still redundant re-initialization
 {{{
     down_node->name_ = sub_name; //<-- we don't need to do this
 }}}

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

 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:
 {{{
     std::auto_ptr<RBNode<T> > node(new RBNode<T>(name));
 }}}
 (but we should probably note that we don't need to do that explicitly)

 '''RBTree<T>::findHelper'''
  - this one still doesn't seem to be addressed: Note: up_node is
    currently unused.  I'm okay with keeping it for
    now though because we'll probably need it soon.  but please leave
    comments about that.

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