Re: [boost] [intrusive] Review

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-19 14:26:15

Guillaume Melquiond wrote:
> * First, a few points that need to be addressed, or at least commented
> upon, in my opinion.

Here we go.

> The member hooks are parametrized by the class name, and I can't see why
> it is needed. As the matter of fact, the base hooks don't need the type,
> so the member hooks should not either. In my opinion, it is just a waste
> of compile time and of executable space (think run-time or debug type
> information). Moreover, it would make the interface simpler and remove a
> discrepancy between base and member hooks. This is current situation:
>   _base_hook<Tag>::value_traits<Class>
>   _member_hook<Class>::value_traits<&Class::Hook>
> Notice that the Class parameters do not appear at the same place. After
> removing the first template parameter from _member_hook, the traits
> would be accessed by:
>   _base_hook<Tag>::value_traits<Class>
>   _member_hook<>::value_traits<Class, &Class::Hook>
> Now the situation is uniform, the Class parameter always appear as the
> first parameter of value_traits.

The review manager, Joaquin pointed this issue in a pre-review he did. 
You are right, the member_hook does not need any template parameter. The 
only problem is that I don't know how to declare a pointer to member 
where both the parent class and the member are templates. I mean:

The review manager, Joaquin pointed this issue in a pre-review he did. 
You are right, the member_hook does not need any template parameter. The 
only problem is that I don't know how to declare a pointer to member 
where both the parent class and the member are templates. I mean:

template<class T, member_hook T::* P>
class value_traits;

compiles fine, but I just want to have one template parameter

template<member_hook T::* P>
class value_traits;

This is a compilation error. Can C++ deduce both the parent class and 
the pointer to member? I don't see any reason that should forbid this, 
but I can find the right syntax.

> 
> Speaking of the interface, half of the template parameters of the
> intrusive container are used for specifying the type of the variable
> storing the container size. This does not need that many parameters, as
> they don't provide orthogonal features. So just one is enough:
>   template < class Traits, class Cmp, class SizeType = std::size_t >

They are orthogonal. Even if you don't have a member size (non-constant 
member), the `size()` method must return a value and `count()` functions 
in associative containers must also return a size type.

> In the hooks, the assignment operators failing when the destination node
> is already linked feels wrong. I understand what the rationale for iset
> could be: assignment may change ordering of nodes. But for ilist, there
> is no ordering involved, so assignment should be allowed. And for iset,
> it should fail only when the ordering is broken, but I don't think it is
> feasible to verify this condition; so it might be sensible to allow it
> there too.

The problem is that a safe-mode hook must assert if something is not 
properly unlinked. That's why it's called safe-mode hook. If you have a 
class that implements a trivial assignment operator, then if the hook is 
linked, you have two options:

-> the assignment is a no-op (the node is still linked).
-> the assignment asserts. A user can implement a operator= for the node 
that does not call hook's operator= if he wants to just ignore the 
assertion.

But an "assignment" for a hook has no sense: two "safe" hooks can't be 
linked in the same position in a container. The same happens for 
auto-unlink hooks, because they have safe-mode properties.

Do you think this assertion is going to be more problematic? I thought 
this assertion would help users detect programming errors.

> Concerning the advanced insertion functions, I'm not sure if they are
> really useful. It seems to me like the insert_check/commit functions for
> iset are just redundant with the usual way of doing it in the STL:
> calling lower_bound, checking the iterator, and then hinting the
> insertion into the set.

The are useful, believe me! First of all, lower_bound + insert with hint 
is not optimal, since insert with hint must check if the hint is 
correct, so it must execute two comparisons. Second, insert_commit is a 
no-throw function, which is an important property insert with hint does 
not have, because the comparison functor can throw. Apart from that, 
unordered associative containers have not lower_bound, and insert with 
hint has the same cost as insert without hint. I would remove the insert 
with hint function for unordered containers, I wanted to maintain TR1 
unordered containers' interface.

> About auto-unlink hooks, you say that they must be used carefully
> because "removing the object is thread-unsafe". I'm not sure to
> understand what you mean. Even for manual-unlink, it is unsafe to remove
> an object if several threads are using the same container. So is there a
> particular reason to mention it here?

Yes it's unsafe, but a manual-unlink is, well... manual. So you know 
when you are calling it and you can wrap it with a mutex. A destructor 
of a base or member class is not explicitly called, and you can't wrap 
it with a mutex unless you wrap the the destructor of the whole object.

> Concerning assign and copy of intrusive containers, I agree that it
> makes little sense. But only if both containers have the same type. You
> could provide template operators in the case types differ but
> value_types are the same. Notice that I'm talking about doing the
> equivalent of "set2(set1.begin(), set1.end())", so the cumbersome
> clone_from does not work here.

Sorry, I'm missing something here, could you elaborate a bit more? What 
do you mean with "same type" and "types differ but value_types are the 
same"?

> The ilist class provides an assign_and_destroy function. The name is
> misleading, as the function will destroy the old elements and then
> assign new elements. In comparison, all the other _and_destroy functions
> delete the elements acted upon, while assign_and_destroy deletes
> unrelated elements. Perhaps, this function could be removed, as it does
> nothing more than just clear_and_destroy then assign.

I just added "...and_destroy" functions to all functions that erase 
elemnets, but perhaps you are right that assign and destroy does not 
offer anything and the name should perhaps be "destroy_and_assign". I 
don't have any problem to erase it.

> The irbtree class is a nice thing to have, so it shouldn't be hidden as
> a detail, especially as its interface is similar to the ones of the
> other containers.

I find it useful, but I didn't know if reviewers would find it also 
useful. For example, I've implemented Boost.Interprocess containers 
using a tree class, which is based on irbtree. It's an multiple value 
container that has functions that can check for duplicates. This class 
would be a new associative container category similar to "Multiple 
Sorted Associative Container", but offering unique insertion functions.

> Typo in advanced_lookups_insertions.html, "a name it's enough".

Thanks.

> - What is your evaluation of the documentation?
> 
> It contains all the needed information, but it is a bit complicated to
> get at it. In particular, the class references should be directly
> accessible from the main page. The introduction could also benefit from
> explaining what an intrusive container is and why to use it.

Ok.

> - Are you knowledgeable about the problem domain?
> 
> My code is a heavy user of intrusive lists. I never went as far as
> building an intrusive set though, but I do have some use for it.

Glad to hear it.

> - Do you think the library should be accepted as a Boost library?
> 
> Yes, I vote for inclusion. But I would really like the two details I
> mentioned about the interface to be solved before it is engraved in
> stone.

Thanks for the vote. I'm waiting your comments!

Best,

Ion