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:27 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.
 >
 We don't necessarily have to have an additional abstraction layer (while
 it depends on the definition of "layer").  What I meant is to define
 something like "NameMap" class with keeping all the internals that the
 current RBTree class has.

 But I'm okay with keeping the name at the moment, especially if the
 intended use is to keep the definition semi-private (i.e., not installing
 the header file) and revisit the issue later.

 > >  - 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.
 >
 We do use boost for_each, but are very carful not to use them in
 public header files (we only use it in .cc's).  That also applies to,
 for example, lexical_cast.  As I mentioned, two of 79 header files
 include boost/function.hpp, but in my understanding we'd rather avoid
 relying on it, and that's why (in my understanding) Jelte avoided to
 use it in his writable data source work.

 > >  - 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
 >
 Ah, I see, I was certainly not very accurate, sorry.  What I actually
 meant was "empty non terminals".

 > c.a.b. 86400 A 1.1.1.1
 > If we
 > >>dig @localhost a.b A
 > BIND9 will return NOERROR instead of NXDOMAIN.

 with an empty answer section, yes.  Now, assume we also have

 d.a.b. 86400 A 192.0.2.1

 Then our rbt will look like this:

 {{{
    a.b (shadow)
     |
     c
    / \
  nul  d
 }}}

 We should still return the NOERROR + empty answer to "dig a.b A".  How can
 we make it possible with our current rbt backend?  As far as I understand
 it we cannot distinguish the result from "NXDOMAIN" because "find()" just
 returns NOTFOUND.  (btw, it's also not trivial to do it without d.a.b, but
 that's another question).  We need to detect whether a node "has data"
 anyway, regardless of whether we has explicitly inserted the name for the
 node, and then the notion of shadow is mostly meaningless.

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