Balanced trees in tinc

[Guus Sliepen]

Hi everybody,

I'm looking into replacing the linked lists in tinc with balanced trees. Using
balanced trees will greatly improve performance for medium to large VPNs. As I
see it, there are several options:

1) Use tsearch()/twalk()/etc functions from glibc.
   + It is in a very standard library
   - It relies solely on callback functions, which sometimes results in
     ugly, awkward code (I tried to use this in subnet.c just now...)
   - Not extendable

2) Use our own tree management code.
   + Optimized for tinc
   - We have to write it our self (I already started though...)

3) Use another library that meets our needs
   + We don't need to do it ourselves then
   - Users must install that library as well

What do you think? Comments please. If you know of some nice and well-known
library that supports balanced trees, please tell me. In the mean time I will be
trying to create some support routines for red-black or AVL trees combined with
a linked list.

-------------------------------------------
Met vriendelijke groet / with kind regards,
  Guus Sliepen <guus at sliepen.warande.net>
-------------------------------------------
See also: http://tinc.nl.linux.org/
          http://www.kernelbench.org/
-------------------------------------------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://brouwer.uvt.nl/pipermail/tinc-devel/attachments/20001112/2c00d135/attachment.pgp