Re: [boost] [intrusive] Review

From: Steven Watanabe (steven_at_[hidden])
Date: 2007-03-17 16:12:23

AMDG

Ion Gaztañaga <igaztanaga <at> gmail.com> writes:

> > islist is a terrible name. I automatically read this as a predicate (is 
> > X a list)
> 
> If Intrusive's containers are placed inside boost::intrusive, you would 
> prefer just using boost::instrusive::list, boost::instrusive::slist... 
> (without the i prefix)?

Yes. That's what namespaces are for aren't they?

> > the second template parameter of ilist_base_hook &c. could be an mpl::bool_
> > or better it could be unique type that expresses the meaning better.
> >  struct safe_mode {};
> >  struct fast_mode {};
> 
> Ok. Even an enum could do the job.

Classes interact better with mpl.

> > ilist_hook.hpp line 121
> >  ilist_base_hook& ilist_base_hook::operator=(const ilist_base_hook& );
> > I'm not sure that forbidding assignment of nodes that
> > are linked is a good idea.
> 
> So you would prefer an empty assignment operator?

On second thought, no.  There are several possible
ways that users might want to handle assignment. It's
better to force it to be specified explicitly.  You
might even make the assignment operator private to
be safe.

> > On further reflection the safe mode and non-safe mode variants
> > are sufficiently different to warrant two specializations.
> 
> That can be an option. Other programmers request unifying safe mode/ 
> non-safe mode an auto-unlink classes in the same templated class. So I'm 
> afraid that someone is not going to be happy  I will think about it.

struct safe_mode {};
struct fast_mode {};
struct auto_unlink_mode {};

template<class Tag, class Mode = safe_mode, class Pointer = void*>
struct list_hook;

template<class Tag, class Pointer>
struct list_hook<Tag, safe_mode, Pointer>;
template<class Tag, class Pointer>
struct list_hook<Tag, fast_mode, Pointer>;
template<class Tag, class Pointer>
struct list_hook<Tag, auto_unlink_mode, Pointer>;

> > I suggest this implementation for the default size_type parameter.
> > As it stands, ADL pulls in namespace std for the containers. (ADL
> > pulls in namespace detail, too but there are no fully generic
> > functions in namespace boost::intrusive::detail)
> > 
> > <snip>
> 
> I must admit that I don't know much about ADL but I can't understand why 
> this is problematic. I can understand what "ADL pulls in namespace std 
> for the containers" means:
> 
> template< class ValueTraits
>          , bool  ConstantTimeSize = true
>          , class SizeType         = std::size_t>
> class ilist
>     :  private detail::size_holder<ConstantTimeSize, SizeType>
> 
> is the default parameter "std::size_t" doing harm here?

For class templates ADL looks in the namespaces associated
with all the template arguments.  The result is that an
unqualified call to a function that has the same name as
one in namespace std can unexpectedly call the std function.

> > swap_nodes doesn't handle adjacent nodes correctly.

> > This isn't a problem now

I take that back. It is a problem.

> Thanks for reporting it.

> You are right. I think I should change all clone_from functions to 
> obtain strong guarantee. When dealing with trees, the optimized cloning 
> function does not offer strong guarantee, because the tree is not 
> balanced if the cloner throws an exception. But I think I could find a 
> one offer strong guarantee in that the red-black tree cloning function 
> rebalancing that partially constructed tree.

The strong guarantee is that if the function fails the program
state is unchanged.  A partially constructed tree doesn't meet
this criterion.

> > I don't think that current is a good name for the function
> > that gets an iterator from the value_type.  How about something
> > a little more descriptive like get_iterator, iterator_from, or
> > to_iterator?
> 
> "iterator_from" sounds good.
> 
> > I would prefer to use CRTP for hooks
> >  template<class Derived, class Tag, bool SafeMode, class Pointer>
> >  struct ilist_base_hook;
> 
> Why do you prefer them? To avoid specifying the type in the internal 
> "value_traits"?

Yes.  This is a very minor issue of course.

> 
> > I compared the performance of sort for ilist on a std::random_shuffled
> > set of one million ints with msvc 8.0. (code is attached)
> > 
> >    INTRUSIVE .51 sec
> >    LIST .89 sec
> >    LIST POINTER 1.14 sec
> >    VECTOR .20 sec
> >    VECTOR STABLE .23 sec
> >    VECTOR POINTER .46 sec
> >    VECTOR POINTER STABLE .42 sec
> 
> I consider that intrusive list sorting should be specially compared with 
> STL list sorting, so do you consider these number acceptable? Thanks for 
> the test.

Yes. They are acceptable.

In Christ,
Steven Watanabe