Hello!

I had a discussion with David Goulet about RB trees [0]. More particularly about the usage of RB trees for some Tor operations like [1] or HSDir cache.

David said that Nick wants to use a FreeBSD implementation - is this one[2]? If it is, I think it could be hard for new contributors like me to maintain/write/debug code using it. Since inline functions are as fast as macros [3], is it conceivable to use functional implementation instead of macro implementation? If it is, I can propose a generic C implementation of RB tree.

It seems that Tor uses some kind of hashmap [4]. What about using hashmaps with RB tree as bucket and thus ensure bounded time complexity?

In some cases, it could be interesting to store RB tree nodes in hashmap to ensure lookup in O(1) while keeping entries sorted.

Regards, L.

[0] https://en.wikipedia.org/wiki/Red%E2%80%93black_tree [1] https://trac.torproject.org/projects/tor/ticket/13739 [2] https://github.com/freebsd/freebsd/blob/master/sys/sys/tree.h [3] https://gcc.gnu.org/onlinedocs/gcc/Inline.html [4] https://gitweb.torproject.org/tor.git/tree/src/common/container.h