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

Comment(by jinmei):

 Replying to [comment:12 hanfeng]:
 > why did you make it really a "tree of trees"?
 > I really haven't read the code in bind9 about the rbtree, it's a little
 bit long and hard to understand. So I just get the document from Shane
 about what tree gonna looks like after insert a bunch of domain names and
 refer to your branch. So from this point of view, this is not a simple
 porting, I write it according to my understanding. The reason why i make
 it a real tree in tree is that from implementation point of view, It's
 more natural. With the recursive data struct the code is less but much
 easier to understand.
 >
 So, basically everything was written from the scratch?

 BTW this is one of the things that should be documented as a design
 decision.

 > "RBT" is not only intended to store RRsets. ....
 > This is my misunderstand about the rbtree, so if it doesn't intended to
 only store rrsets but anything which related to one domain name, the
 interface of it should be modified and maybe we can make it a template
 class. I will finish the modification in two days.
 >
 More importantly we cannot assume an existence of an "NS" record to
 identify a partial match.  You'll need some non trivial tricks such as
 BIND 9's "rbtnodechain" or manipulating parent pointers.  Specifically, we
 cannot simply do the following in RBTree::findHelper()
 {{{
             } else if (NameComparisonResult::SUBDOMAIN == relation) {
                 if (node->isDelegate()) {
                     *tree = (RBTree*)this;
                     *ret = node;
                     return (RBTree::FINDREFERRAL);
                 } else if ...
 }}}

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