Hi Henri,
On 8/11/16 2:50 PM, Henri Verbeet wrote:
On 10 August 2016 at 16:01, Jacek Caban jacek@codeweavers.com wrote:
include/wine/rbtree.h | 376 +++++++++++++++++++++++++++----------------------- 1 file changed, 200 insertions(+), 176 deletions(-)
Since this patch was assigned to me...
I think this patch has quite a number of unrelated changes,
Implementation details that I change in helper functions affect other parts in such a way, that one patch felt appropriate. Anyway, I sent a split version (at the cost of temporary arguments).
to the point that the patch touches over half of the lines in the file
Yes, that's more or less a rewrite, so it's not surprising.
and I think deletion for example ends up just being a different algorithm.
Yes, that's intentional and there are reasons for that. The algorithm that I used (see implementation from Introduction to Algorithms book for reference) needs only bottom-up traversal once you have the node, which is perfect for following parent chain. Instead of doing rotations on way down and up, we do them just when going up. And, although asymptotically it's the same complexity, it usually needs fewer steps since it stops at the first red parent. Further, the traversal down can be a simple wine_rb_get call (and I intend to change it further so that wine_rb_remove takes wine_rb_entry as an argument, but that's something for future discussion). All that wasn't possible when we had to record the path to root on the stack, but when I had to make significant changes to the function anyway, I think that's a good moment to do full rewrite and take those little advantages.
And while the aforementioned means I didn't look at everything in quite the amount of detail that would otherwise be appropriate, I do think some of those changes make things overly complicated. For example, a straightforward modification to wine_rb_put() would turn it into something like the following:
static inline int wine_rb_put(struct wine_rb_tree *tree, constvoid *key, struct wine_rb_entry *entry) { struct wine_rb_entry **node = &tree->root; struct wine_rb_entry *parent = *node;
while (*node) { int c; if (!(c = tree->functions->compare(key, *node))) return -1; parent = *node; if (c < 0) node = &(*node)->left; else node = &(*node)->right; } entry->flags = WINE_RB_FLAG_RED; entry->parent = parent; entry->left = NULL; entry->right = NULL; *node = entry; wine_rb_fixup(&tree->root, entry); tree->root->flags &= ~WINE_RB_FLAG_RED; return 0; }I think that's much clearer than what this patch does with wine_rb_put().
Well, I don't see why one or another is cleaner, but it indeed slightly reduces the diff, so I changed that.
Thanks, Jacek