On 24.08.2016 12:49, Jacek Caban wrote:
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
(Non-safe) iterator macros with different orders could also be added without bigger code changes, but I assume that alone would still not be sufficient for your requirements. In order to implement safe iterator callbacks (and to get rid of the stack) those parent pointers would really be useful, although they have the disadvantage that they increase memory usage a bit. This makes me wonder if it wouldn't be useful have multiple tree implementations targeting different use-cases and performance requirements.
I assume that there are currently no plans to exchange the RBTree with something else, nevertheless it shouldn't hurt to share some code. I've attached a proof-of-concept patch to replace the RBTree with a Scapegoat tree I wrote a while ago. In contrast to other trees a nice property is that it is not really required to keep the tree balanced all the time, instead we have rebuild operations which will automatically detect it if the performance gets too bad and build a binary search tree. When deleting lots of elements for example we could disable rebuild temporarily to avoid too much overhead. If someone has code to measure performance differences in practice, feel free to give it a try. ;)
Regards, Sebastian