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:

 > '''Meta Comments'''
 > Was it developed test driven?
 To be honest, the implementation is written by me and test code is written
 by Jerry, we will
 change the mode
 >
 > '''General Comments'''
 >  - I still don't understand why we need to rewrite the whole logic
 >    from the scratch.  This is complicated stuff by nature, so doing it
 >    from the scratch only seems to increase the risk of introducing
 >    bugs.
 I have modify the code from really tree in tree to the bind9 design, use
 down node to
 point to the sub tree, and remove the recursive code. I think the code
 isn't totally new
 compared with bind9, the idea is same. Bind9 code consist of a lot of
 logic except just simple tree, so it will be more simpler for me to write,
 but it really cost your more review effort.

 >  - A related point: the current design seems to be much less efficient
 >    in many points.  ....

 For efficiency problem, I have remove the recursive code, use boost pool
 to manage the memory, so if we delete the whole tree, this is no need to
 walk through the whole tree from node to node. Also the creation and
 destroy tree node will be more efficient.


 >  - As we discussed before, I'm personally against using
 >    boost::noncopyable in a public header file.  ....
 I think we should depend less on boost compile part, but if only needs
 head file, I don't see the difference between depending on one file and
 more files.


 >  - Admitting this may be a matter of taste, this type of syntax looks
 >    awkward, and reduces code readability (by confusing the reader) to ..
 Yes, it's avoid the mistake that make assignment but when we really want
 to do comparison. It decrease the readability of the code, since compiler
 can avoid that, I have remove that kink code


 >  - I'm afraid it's not a good idea to store raw "type-T" data in
 >    RBNode.  ....

 T hasn't to be real data, it can be a shard_ptr.


 >  - class naming: it may be better to introduce one level of
 >    abstraction than "red black tree", because from user's point of...
 I do not totally understand it, if what we will provide the class memory
 data base, we
 should add another abstraction, so user don't need to know what concrete
 data struct we use. but
 this part code is red black tree porting.


 >  - documentation in general: we need two types of documentation: one
 >    for API users, and the other for developers who try to read/modify
 >    the code.
 I will add more comments for user who want to modify the code


 >
 > '''operator- for Name'''
 >  - technically, an unnamed namespace shouldn't be used in a public
 >    header file because it would easily cause breaking the C
 I have move it into a inner namespace, originally it with the macro all
 reside
 in cpp file, i forget to modify them.


 > '''RBNode class'''
 > '''RBTree class'''
 No magic number is used
 Use boost::object_pool to management memory to keep code exception safe
 The variables in function is modified to more meaningful name
 The erase logic is modified that when delete node with down pointer,
 instead just set it
 to shadow, if it has only one child, it will merge with its down node.
 PrintTree rename to dumpTree, several mistake is removed
 Shadow node cann't be seen by end user, because from user perspective, if
 I insert four names into the rbtree, I don't expect get five or even more
 names from it.


 Add iterator into rbtree to support iterate the whole tree, next step can
 modify ''erase'' and ''find'' to return or use iterator.

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