[tor-dev] RB Trees

[U+039b]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160625/77259070/attachment.sig>