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:34 jinmei]:
 > '''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
 >
 > '''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 :)

 > '''RBNode class definition'''
 >  - shouldn't we make constructors private? (we previously did, and I
 >    think it made sense)
 because deconstructor will be called by auto_ptr, so it has to be public,
 so I move the
 constructor into public, I have move them back to private and give comment

 >  - type of data_: I don't think it works well.  getting a pointer from
 >    a possibly different module and freeing it in the callee (=rbtree)
 >    is a bad practice, because the caller and callee may use different
 >    new/delete.  My suggestion is to impose requirement to T:
 >    - it's assignable and copy constructible (and should be exception
 free)
 >    - comparable to NULL
 >    This effectively means T must be a pointer(-like) type, and if it's
 >    a bare pointer the caller must be responsible for freeing it. (so,
 >    again, effectively it should be a smart pointer type)
 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


 >
 > '''RBTree class definition'''
 >  - this comment is not really correct any more because findHelper()
 >    isn't called recursively:
 invalid comment is removed
 >  - why did you remove const from 'up'?  This essentially changed two
 >    things: changing the type for 'up' from RBTree to RBNode, and
 >    removing the const.  I see the reason for the former.  I don't for
 >    the latter.
 up node has been add const
 >  - Is getNameCount() (and name_count_) really necessary?  After all,
 >    the notion of number of "explicitly added names" is moot, because
 >    our interest is wheth...
 getNameCount is removed
 >
 > '''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

 >   AFAICS we can (should) simply merge empty/non empty cases.
 >  - BTW, maybe shouldn't we use null node also for the down pointer?
 Yes, make the default value of down pointer as NULLNODE, make the code
 more consistent and
 simple, I have modified accordingly

 > '''nodeFission'''
 >  - down_node initialization could be simplified (and more efficient):
 > {{{
 >     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


 > '''dumpTree()'''
 >  - one of my previous currents still stand:
 >   - "tree has node XX" doesn't parse well.  I'd rephrase it "tree has
 >     XX node(s)"
 Modified accordingly
 > '''dumpTreeHelper()'''
 >  - one of my previous currents still stand:
 >    - at the end of the function, it seems we can avoid the if-else by
 >      handling null node case at the beginning of the function: [...]
 Modified accordingly
 > '''set_get_Data test'''
 >  - might better be named "setGetData" based on coding guideline.
 Modified accordingly
 > '''insertNames test'''
 >  - the beginning comment is not true any more "a node is
 >    considered..."  In fact, this test succeeds:
 > {{{
 >     EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("d.e.f"),
 &rbtnode));
 >     // re-add after "explicitly inserted"
 >     EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("d.e.f"),
 &rbtnode));
 > }}}
 >   see also a relevant comment about when to return SUCCEED and when
 ALREADYEXIST
 >  - same note applies to some other comments
 Modified accordingly

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