Hi Henri,


On 8/23/16 5:54 PM, Henri Verbeet wrote:
On 15 August 2016 at 21:57, Jacek Caban <jacek@codeweavers.com> wrote:

Well, the original code was written the way it was because of
simplicity more than anything else. The part that's performance
critical is wine_rb_get(), but that depends largely on the performance
of the compare function. Inserts and removals shouldn't be slow of
course, but I think it's reasonable to balance performance against
simplicity there. If in practice there are concrete performance
advantages to doing it a different way we could of course reconsider
that.

Sure, my patches address mostly friendly and more flexible API (more about that bellow), so let's concentrate on that.

One of the things I don't like about these patches is that I think
full-blown parent pointers make it harder to reason about the code.
Similarly, I don't think the amount of branching and fiddling with
flags in e.g. wine_rb_remove() is an improvement. I realise those are
pretty subjective considerations,

Yes, those are subjective. I find the new code actually cleaner and easier to follow and I have some subjective thoughts about the other solution as well. How about we both skip those subjective considerations? If you have concrete improvements suggestions, I'm happy to address them.

and the patches do work as intended in my tests. Any performance differences I found seemed to be within
the margin of error. Nevertheless, would the attached patch work for
you?

Not really. I obviously considered something along those lines, you could have asked before writing the patch. This solution wouldn't allow something I'm planning as a follow up, which is friendly (callback free) iterations. Something like WINE_RB_FOR_EACH_SAFE/WINE_RB_FOR_EACH_ENTRY_SAFE macros (just like their list.h counterparts) is just a matter of adding those defines with my patches.

Also ordered iterations would be an useful addition. I had usage example in my very recent jscript work, when I missed something like that and I ended up having simplicity-oriented ad-hoc solution. It would be nice to change that. Macros WINE_RB_FOR_EACH/WINE_RB_FOR_EACH_ENTRY doing ordered, mutation-safe, iterations would be straightforward with my patches. They are exactly what I needed.

Also, being able to efficiently iterate to the next node (something like wine_rb_next(), which could cope with tree mutations) is important if we want to use it for any of IDispatchEx implementations.

Jacek