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 hanfeng):

 Replying to [comment:25 jinmei]:
 > Actually, there are two issues here.  First: Whether we want to make the
 > rbt stuff externally public or we want to keep it a private helper
 > used only inside our .cc's.  I originally thought the former, but
 > maybe we should at least begin with the latter approach, ...
 To make the rbt stuff externally, to my understanding, we will create one
 abstract map, the key
 of the map is domain name, and the value part can be anything, so the data
 struct behind is replaceable and opaque to end user. Is it what you mean?
 Then the interface will be more like map
 in STL, just the key type is restrict to Name instance. If we want to have
 something like this, after finish rbt tree porting, we can add that
 abstract layer.


 >  - boost noncopyable
 > > 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.
 > >
 > No, the point is that boost is a moving target, and using it in a
 > public header file increases the risk of introducing binary backward
 > incompatibility.  More boost header files to be included, more risks
 > we have.  So, basically, unless it's very difficult to find a
 Yes, boost is moving, new stuff is adding into it. And some part of it is
 absorbed by stand library in the near future. And with class struct
 modified, binary compatibility will be damaged. But there are a lot of
 greate things in boost, shared_ptr is one of them, now I think we have
 also used for_each, maybe bind, functor. If you shared_ptr is used,
 possibly weak_ptr will be used later. for non_copyable, it's code is quite
 simple, we can write it. But do we really want to reinvent the wheel. for
 the compatibility issue, we can includes one version of boost into our
 code base just like asio. And I agree that we should keep the code
 consistent, if we decide to use boost::non_copyable, all the code should
 be modified accordingly.

 >  - NXRRSET vs the notion of "shadow": I pointed this out in my
 >    previous review as part of comment on findHelper().  It's not
 >    addressed yet.
 I am not sure that i understand the problem. So let me clarify my thinking
 about NXDOMAIN & NXRRSET. In case, we have  zone b. and in it, we only
 have c.a.b
 c.a.b. 86400 A 1.1.1.1
 If we
 >>dig @localhost a.b A
 BIND9 will return NOERROR instead of NXDOMAIN.
 If we
 >>dig @localhost c.a.b mx
 BIND9 will return NOERROR

 But if do nsupdate, with
 >>prereq yxdomain a.b
 BIND9 will return NXDOMAIN
 or
 >>prereq yxrrset c.a.b mx
 BIND9 will return NXRRSET
 so for nsupdate, the rcode returned is quite correct. but for dig, I
 don't know why BIND9 return noerror not NXDOMAIN & NXRRSET.

 In principle, one name is think to be not exist, that means it has no
 rrsets with it. Otherwise, if it exists but no some kind of rrset user
 want, we will return NXRRSET, is it correct?

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