On Thu, May 19, 2011 at 05:27:01PM +0000, Thordur Bjornsson wrote: > On Thu, May 19, 2011 at 07:21:21PM +0200, Mike Belopuhov wrote: > > On Thu, May 19, 2011 at 7:12 PM, Thordur Bjornsson <t...@openbsd.org> wrote: > > > On Thu, May 19, 2011 at 07:52:44PM +0300, Michael Pounov wrote: > > >> Add AVL tree implementation and merge few RB tree related macros. > > >> > > >> If you have comments or any claims, please send me feedback > > >> and I will fix them. > > > cool. but tech@ removes attachments, send your diffs inline. > > > > > > I'm assuming you implemented this as a macro a la RB/SPAY in > > > tree.h; > > > > > > That being said, there is already an AVL tree implementation > > > floating around, that's "not macros". > > > > > > I've been beating on it (with some of the RB trees diffs we > > > have in the kernel switched over) for some time, and hopefully > > > it will be committable soon. > > > > > > > what do you need it for? it's pretty much the same as r/b tree. > > do you think that lookup speed up is considerable? > > same questions apply to Michael. > > It's not the same as an r/b tree. > > The main reason for it is to cut down on the code bloat that > the tree.h macros introduce. > > Also, my (limited though, have not done proper networking checks) > show no performance difference.
The networking code is where the performance differences tend to show up the theory is still that gcc manages to inline the comparators -0- -- Some programming languages manage to absorb change, but withstand progress. -- Epigrams in Programming, ACM SIGPLAN Sept. 1982