[bind10-dev] Using AVL tree instead of red-black tree in DomainTree

[Francis Dupont]

Note there is a different implementation of RB tree in C available
in most BSDs, for instance on FreeBSD in /usr/include/sys/tree.h
(very similar to the weel known queue.h but with RB and splay trees
in place of all list/queue variants). It can be a great help to
understand the bind 9 code according to my experience (even I did
the opposite: copied the BSD code and used the bind 9 one to understand
it).

Regards

Francis Dupont <fdupont at isc.org>

PS: splay trees are funny too and pretty useful when you have no cache
(so I can't see an application in current bind 10 but it is still
something a good programmer should know at least it exists).
PPS: deletion of a large RB tree must be done in a compatible order
to the way it was built. Without this deletion can lead to virtual
memory thrashing. I changed the bind 9 code many years ago to get
.com faster to delete than to build on Linux (:-). Note this applies
only if you don't just throw away memory...