Re: [PATCH 13/14] rbtree.h: Added WINE_RB_FOR_EACH_DESTRUCTOR and WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR helpers for implementing tree destructors.

[Matteo Bruni]

2017-02-13 21:12 GMT+01:00 Jacek Caban <jacek(a)codeweavers.com>:
> Signed-off-by: Jacek Caban <jacek(a)codeweavers.com>
> ---
>  include/wine/rbtree.h | 20 ++++++++++++++------
>  1 file changed, 14 insertions(+), 6 deletions(-)

These sound like the _SAFE variants of our list implementation. Any
reason not to use the same naming here?

[PATCH 13/14] rbtree.h: Added WINE_RB_FOR_EACH_DESTRUCTOR and WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR helpers for implementing tree destructors.

[Jacek Caban]

On 14.02.2017 16:21, Matteo Bruni wrote:
> 2017-02-13 21:12 GMT+01:00 Jacek Caban <jacek(a)codeweavers.com>:
> > Signed-off-by: Jacek Caban <jacek(a)codeweavers.com>
> > ---
> >  include/wine/rbtree.h | 20 ++++++++++++++------
> >  1 file changed, 14 insertions(+), 6 deletions(-)
> > These sound like the _SAFE variants of our list implementation. Any
> > reason not to use the same naming here?

I thought about it. I think that there are different meanings of safety:

1. safe to free current entry (but not necessarily safe to call
wine_rb_remove on it)
2. safe to cause tree mutation like call wine_rb_put or wine_rb_remove
on any other element than current one
3. safe to remove current element (and possibly free it later)

The variant that I implemented is safe only as in (1), while current
WINE_RB_FOR_EACH is safe as in (2).

By analogy, list _SAFE macros are safe as in (3) - you can remove
current element, but generally shouldn't remove random other ones,
because it may be the stored next entry. Also you need to remove element
from the list before freeing it. I wanted to preserve that name if we
ever find a need for macro safe as in (3) in rb tree. Its implementation
for rb trees would look like the one I sent, except it would use regular
order instead of postorder.

That said, I'm happy to rename it if you think there is a better name. I
just think that _SAFE is not the right one.

Thanks,
Jacek

[PATCH 13/14] rbtree.h: Added WINE_RB_FOR_EACH_DESTRUCTOR and WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR helpers for implementing tree destructors.

[Matteo Bruni]

2017-02-14 16:40 GMT+01:00 Jacek Caban <jacek(a)codeweavers.com>:
> On 14.02.2017 16:21, Matteo Bruni wrote:
> > 2017-02-13 21:12 GMT+01:00 Jacek Caban <jacek(a)codeweavers.com>:
> > > Signed-off-by: Jacek Caban <jacek(a)codeweavers.com>
> > > ---
> > >  include/wine/rbtree.h | 20 ++++++++++++++------
> > >  1 file changed, 14 insertions(+), 6 deletions(-)
> > > These sound like the _SAFE variants of our list implementation. Any
> > > reason not to use the same naming here?
>
> I thought about it. I think that there are different meanings of safety:
>
> 1. safe to free current entry (but not necessarily safe to call
> wine_rb_remove on it)
> 2. safe to cause tree mutation like call wine_rb_put or wine_rb_remove
> on any other element than current one
> 3. safe to remove current element (and possibly free it later)
>
> The variant that I implemented is safe only as in (1), while current
> WINE_RB_FOR_EACH is safe as in (2).
>
> By analogy, list _SAFE macros are safe as in (3) - you can remove
> current element, but generally shouldn't remove random other ones,
> because it may be the stored next entry. Also you need to remove element
> from the list before freeing it. I wanted to preserve that name if we
> ever find a need for macro safe as in (3) in rb tree. Its implementation
> for rb trees would look like the one I sent, except it would use regular
> order instead of postorder.

Those are valid points and I didn't appreciate all the nuance there.
Yeah, I'd reserve _SAFE for (3) too and name this one differently (I
don't have any better name to suggest either).

I guess my remaining question is whether it makes sense to just
introduce the _SAFE variant right away, in place of this one. If I'm
not mistaken that would be a bit slower since you'd need to
wine_rb_remove() the elements one by one before freeing them but it
might be more "natural" in a way, since it would match the semantics
of the list. I'm not opposed to this patch in any case.

[PATCH 13/14] rbtree.h: Added WINE_RB_FOR_EACH_DESTRUCTOR and WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR helpers for implementing tree destructors.

[Jacek Caban]

On 14.02.2017 20:03, Matteo Bruni wrote:
> I guess my remaining question is whether it makes sense to just
> introduce the _SAFE variant right away, in place of this one. If I'm
> not mistaken that would be a bit slower since you'd need to
> wine_rb_remove() the elements one by one before freeing them but it
> might be more "natural" in a way, since it would match the semantics
> of the list. I'm not opposed to this patch in any case.

I would prefer sticking with _DESTRUCTOR variant. It's both faster (O(n)
vs O(n log n)) and makes implementing destructor slightly easier. It's
not very strong opinion through.

Thanks,
Jacek