GitLab

it effectively makes this branch with trac517 (which has been merged to
master since then).  it will help merge this branch to master.

also resolved trivial conflicts in src/lib/datasrc/tests/rbtree_unittest.cc.

This reverts commit 1ab958cd.

Actually, it turns out to be much simpler than originally thought on top
of the RBTreeNodeChain extensions made on this branch so far.

 - new methods were added to RBTreeNodeChain
 - RBTreeNodeChain::clear() was also added, mainly for the convenience of tests

In the latest usage we don't need to copy RBTreeNodeChain objects.
It would be safer to disable copy unless/until we see need for it.

 - construct the backend rbtree with the 'empty okay' mode
 - return NXRRSET if the found node is empty

After looking at the BIND 9 code more closely, I found we can complete this
task with the advanced feature such as getting "next node".  So I'm
incorporating changes in #517 that are necessary for this task:
 - the 'return empty node' swith
 - revised interface with 'node chain' (we don't need a chain for this task,
   but we'll need an additional parameter for find() to record some details
   about the search)

The incorporated part has been already reviewed, so this change
doesn't have to be reviewed explicitly.

 - added more documentation while removing obsolete ones
 - use assert() for private functions because the invariants should now be
   guaranteed
 - remove the dedicated exceptions as a result and use generic ones
 - added more tests for invalid cases

 - check invalid chain explicitly in the method.  use a generic exception
   on violation.
 - updated doc

 - not all nodes were tested.  fixed it.
 - confirmed nextNode() returns NULL at the end of the tree.

 - the new tests confirm the maximum possible levels of RBTree/node chain.
 - the new method: getLevelCount() helps the tests.

Also added some more documentation.

 - removed redundant space at EOL
 - fixed usual breakage: s/foo &/foo& /

(checking PARTIALMATCH on rbtree_expose_empty_node)