[boost] [intrusive] Review

From: Guillaume Melquiond (guillaume.melquiond_at_[hidden])
Date: 2007-03-19 06:50:32

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

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.

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 >
Then you specialize your containers, so that the size is not stored when
the type is void. If you think void is not descriptive enough, you can
replace it with a dummy type called no_constant_time_size, or whatever.

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.

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. Especially since you already provide an
optimized lower_bound function, which can be used without creating the
value.

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?

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.

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.

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.

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

* Now for the review itself.

- What is your evaluation of the design?

The concept of intrusive containers is sound, and the library is really
generic. Some bits of the interface may require a bit of tuning (see the
first two points above).

- What is your evaluation of the implementation?

The implementation looks good. I especially appreciated the fact that
the default classes were relying on void* to reduce code duplication.

- 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.

- What is your evaluation of the potential usefulness of the library?

It can be extremely useful for some algorithms, when elements have only
one owner but you want them to be part of several structures.

- Did you try to use the library? With what compiler? Did you have any
problems?

I exercised the library by building a non-intrusive multiset upon it. I
compiled with GCC 4.1. The implementation was a bit slower than the
original std::multiset, but nothing too worrying. I didn't encounter any
problem: thanks to the intrusive library, the implementation was
straightforward.

- How much effort did you put into your evaluation? A glance?
  A quick reading? In-depth study?

In-depth study.

- 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.

- 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.

Best regards,

Guillaume