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:

 Replying to [comment:25 jinmei]:
 >  - exception safety: changing new to object_pool doesn't solve the
 >    essential problem.  See, e.g. nodeFission().  if the code following
 >    the createNode() call throws an exception (and it can throw), the
 >  - A related point: again, whether or not using object_pools,
 >    returning an error code for the "no memory" condition is IMO not a
 >    good idea because it's not consistent with our error handling
 >    convention......
 object pool is removed, whether to use it needs discussion. To handle
 exception safe
 especially bad_alloc, use auto_ptr. So there is NOMEM flag any more

 >  - 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.
 >   - suggestion: drop the idea of shadow; require type T be comparable
 >     with NULL; replace the logic that checks whether the node is
 shadow is removed, <code>find</code>will return non-empty nodes, so to
 distinguish
 NXDOMAIN from empty non-terminal is left to be done in latter sprint.

 >  - documentation is still quite insufficient.  quoting my previous
 >    comments: "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..."
 >  - existing (minor) point that isn't addressed:
 >   - The diagram after the (RBTree) class definition: this should be
 >     included in the doxygen document.
 Add more document and move the diagram into the doxygen part. The document
 maybe still insufficient. It's really my problem, I seldom writing
 comments for my code. If more description should be add to specific
 interface or design, please let me know

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