Re: [boost] Review of Intrusive library begins today March 12

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-15 12:53:20

Kevin Sopp wrote:
> Hi,

Hi Kevin,

>>   - What is your evaluation of the design?
> 
> Outstanding, I think Ion really outdid himself with this one ;)
> intrusive lib has become much more than I had ever hoped for and it's
> really ready for primetime now.

Thanks.

 > It provides customizability at every imaginable point. Using
 > node_traits and value_traits this can be done very cleanly,
 > additionally one can choose between constant/linear time size() member
 > function. The one thing that really struck my eye the first time I
 > read the docs was that I could define the size type for the
 > containers. I never really needed something other than std::size_t but
 > I've read about embedded programmers that use 16 bit pointers for
 > small collections and so only need a 16 bit size type. Of course with
 > intrusive library you can use 16 bit pointers if you desire.

Customizability was a major goal. I wanted Intrusive to be useful not 
only to insert objects in containers, but also to write memory 
algorithms that need to store free chunks of memory in intrusive 
red-black trees. Even allow tricks like storing flags in the unused bits 
of a pointer used in node algorithms.

The size type customization is also provided to ease the implementation 
of STL-like non-intrusive containers above intrusive containers. In 
STL-like containers, container::size_type is a typedef for 
allocator::size_type, which might not be std::size_t.

> The one thing that still annoys me is the 'i' prefix. Really, now that
> everything is in the intrusive namespace I think it should be dropped.
> The first time I saw it, it reminded me of the 'I' prefix some people
> use for interface classes.

Ok. The question is if intrusive containers should be in the 
boost::intrusive namespace or they should be include in the first level 
boost:: namespace. If they remain in boost::intrusive, I will remove the 
i prefix if reviewers agree.

>>   - What is your evaluation of the implementation?
> [snip]
> 
> A couple of things I noticed after examining the library again today:
 >
 > [snip]

Thanks, I will add them.

>>   - What is your evaluation of the documentation?
> [snip]
 >
> I agree with Samuel Debionne that the Concepts part can be improved. I
> really liked the summary at the end of the Concepts section. Maybe
> this should stay where it is (with one more/or a bit longer sentence
> for each concept) and then put the detailed description of the
> Concepts at the end of the documentation. Then the reader will know
> what the traits are for and can move on. Customizing the traits is
> more advanved and should be at the end.

Ok. I will need to rework all this stuff, so I think your proposal seems 
reasonable. Include the summary first to have the very basic definitions 
for the basic uses of the library. Include the full explanations before 
the advanced uses and custom nodes. Thanks.

>>   - What is your evaluation of the potential usefulness of the
>>   library?
>>   - Did you try to use the library?  With what compiler?  Did
>>   you have any problems?
> 
> Very useful, been waiting for this a long time. In fact I started to
> use it back in december to implement a cache system using the
> ihash_set now iunordered_set.

This was done to unify names with standard containers.

> While this one required some boilerplate code to handle a resizable
> bucket array I was positively surprised that the two functions
> suggested_upper_bucket_count() and suggested_lower_bucket_count() were
> provided. The library lends you a helping hand wherever it can.

Basically, depending on the implementation, some numbers are better than 
others (some implementations use a dummy end bucket, others not). So I 
think that the implementation itself knows better than the user the 
optimized length of the bucket array. Some implementations might prefer 
power of two values instead of prime numbers. Glad to hear you find them 
useful.

> It compiles cleanly on mingw/gcc4.1 and linux/gcc4.1.2.
> I stumbled upon a compiler error in mingw/gcc4.1: I declared a name
> tag for the hook in a class but upon instantiation gcc errors out with
> 'iunordered_set_base_hook<expression error>'. Putting the tag outside
> of the class remedied the situation. I haven't examined this behavior
> any further. I declare the value type that derives from the hook
> inside the class too, I think this could be the reason.

The old versions used a number to distinguish the hooks when more than a 
base hook was used. I recently changed that following Joaquin's good 
advices, because tags make tag collisions harder. Thanks for the report.

>>   - Do you think the library should be accepted as a Boost library?
> 
> Without a doubt I think it should be accepted. I believe the code is
> easy to maintain and would be welcome to many programmers.

Thanks for you review and your vote ;-). I'd like to get suggestions and 
improvements from users to expand the library. Including more intrusive 
or pseudo-intrusive containers (avl trees, other hash implementations, 
non-circular lists and singly linked lists...) would be nice. I hope to 
include all the needed building blocks to make non-intrusive container 
implementations easier.

> Kevin

Regards,

Ion