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            |  
------------------------------+---------------------------------------------

Comment(by jinmei):

 Replying to [comment:37 hanfeng]:

 Hmm, it compiles without rbtree.cc.  Maybe the addition to Makefile.am was
 a typo?
 >
 I've added some more suggested editorial changes to comments (r3852).
 Please check.
 >
 > > '''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.
 >
 This logic doesn't make sense to me.  First, whether it's in a class or
 not, things that are not supposed to be seen in public shouldn't be
 published in general.  Second, with this logic, any (static) class member
 variable or enum of a templated class would have to be defined outside of
 the class unless they depend on a templated parameter.
 >
 > > >>  - 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
 >
 The bare pointer version of setData() essentially has the same problem of
 the original design and still makes me nervous.  I'd suggest we begin with
 a minimum set of interfaces (i.e. only having the shared pointer version
 of setData() and modify the test code accordingly) and extend it in a
 safer way if and when we see the need for it.
 >
 > > 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
 >
 Okay, but please clarify that in a comment.  Otherwise someone may
 "optimize" it later without understanding the intent.

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