[bind10-dev] the responsibility of rbtree in BIND10

[JINMEI Tatuya / 神明達哉]

At Tue, 16 Nov 2010 12:53:34 +0800,
"feng" <hanfeng at cnnic.cn> wrote:

> Now I am porting RBTree from bind9 to bind10.  Instead of porting, I
> am writing the code from scratch, according to the attached
> document, I think the Responsibility of RBTree will be as follows.

Writing it from the scratch is not necessarily a bad thing, but please
be careful.  Doing something complicated like this from the scratch
will be a easy source of buggy behavior.  We should at least
understand the original implementation first, and if there's a reason
to rewrite it instead of porting it on top of the understanding, that
would make sense.  But doing it from the scratch as an *alternative*
to understanding the original code is a risky approach.

> >From outside (who gonna use the tree), it’s a map, the type of the
> >key is domain name (the Name instance in bind10) and the value can
> >be anything, so if used it for one zone, the value will be
> >rrsets. If used for one zone table, the value maybe the pointer of
> >the data source.

This generally matches my understanding (but see the note about
"longest match" below).  Note that the value can be "anything".  So
the implementation currently available in the trac397 branch (which
assumes the data type is a list of RRsets) doesn't realize the
requirement.

> >From implementation point of view, the map is build on red black
> >tree and with one more down pointer which will point to sub domain
> >names .

More accurately, a tree of red black trees.

> with the following domain names, 
[snip]
> Is it what we want?

Something like that, yes (although I didn't check if the resulting
tree is 100% correct).

And, one important feature is that it can provide a "longest match"
interface.  So in this example if we try to find an entry for
"x.g.h", it should return something like a "partial match" (with
pointing to the longest matching entry, which corresponds to the node
"g.h" in the example graph) instead of "not found".

---
JINMEI, Tatuya
Internet Systems Consortium, Inc.