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