>If I have a fairly good connection I can measure your WAN load anyway using
Across some country you don't have a farirly good connection (definetly
not from here at least 8). The ip++ is asking for writing an user-friendly
application to tell the user the network throughtput of the TCP/IP stack
of the linux machine of your friend.
>> It would be nice to write an AVL common code (exactly as I did with the
>> RB-tree some time ago when I replaced the page-cache and buffer cache
>> hashtable with two rb-trees). Rewriting the AVL code each time we need it
>> it's not nice IMHO.
>
>We have 3 AVL trees if this goes in so yes
My rb-tree linux-kernel librarian is been rock solid and I _never_ (yes
strange agreed 8) had a problem with it since the first boot of my rb-tree
capable kernels. I did hard testing and benchs in userspace before moving
them to the kernel.
The rb-trees are sligtly faster in insert/removal but they are bit slower
in the query. So actually the best for the vmas is still the AVL as the
hit operation is the query (and quite frankly the vmas are so delicate
that I am not sure Linus would like such a conversion even if RBs would
make more sense...). For the IP instead it looks like to me that rbs would
be the best as inserction/removal is O(log(n)).
I provide the same interface which list.h provides (with the rb_entry()
which gives you the original type starting from the rb entry). A rb entry
only have the parent,color,left,right fields. Ah the MM downside of the RB
tress is that they will waste 4 more bytes per entry then AVL ones just
to store one more bit :(. I tried to use one bit of the other pointers but
such programming is painful and not very portable.
If you think that RB may be useful (I think yes) please let me know and
I'll be glad to provide you a simple patch to add the RBs to the kernel.
For misc usage (where it's not obvious that inserction/removals happens
very less frequently than queries) RB are better than AVL (it's not a case
set/map in the STL are using RBtrees as underlying data structure).
Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/