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

From: Pavel Vozenilek (pavel_vozenilek_at_[hidden])
Date: 2007-03-22 18:57:53

"Ion Gaztañaga" wrote:
Pavel Vozenilek wrote:

_________________________________________________________
> > * An vector-like pseudo-intrusive container may be added.
> >   It is superfluous but people may like it more than lists.
>
> Well, a vector is not even pseudo-intrusive, because it has no nodes.
> std::vector<> + allocator is not sufficient in your opinion?
>
What I mean is a container that provides operator[].

Possibly something what keeps an auxiliary array
in container and where hook has either
* one back-pointer into the internal array inside container
  (to allow iterator::operator+(int)).
* or one back pointer to the container + integer index
  (this would allow range checking)

> ================================================================
> > One existing library that implement intrusive containers is Data Object
> > Library
> > (http://www.codefarms.com/dol.htm, also 
> > http://www.codefarms.com/ptl.htm).
> >
> > jjLib (http://sourceforge.net/projects/jjlib/)
> > is based on the same pronciples and also uses external
> > code generator.
>
> I will look these for ideas and new features.
>
The online documentation is not perfect.

The author had written book
Taming C++: Pattern Classes and Persistence for Large Projects,
 Jiri Soukup, 1994, ACCU review:
http://www.accu.org/bookreviews/public/reviews/t/t001196.htm).
where the library and the intrusive technique is described.

The open source library is underdocumented but source is available.

_________________________________________________________
> > What I imagine as potentially possible is for the
> > Intrusive Container library (or its complement)
> > to completely manage lifetime of inserted objects:
> >
> > * when an object is removed from the last container
> >   it gets automatically deleted.
>
> This would need an embedded reference counted hook. but these reference
> count should be shared between all the hooks of a value type (including
> hoooks from base classes). Not an easy task to do in standard C++, I
> guess ;-), but I will put it in my investigation list.
>

I though about it a bit more since I wrote the review and here's
how I would structure it (provided it is all technically feasible):

The library would provide containers and hooks parametrized
by one more parameter: a boolean OwnsData
(alternatively differently named containes could exist):

The containers not owning the data would:
  * Never ever destroy the data.
  * Cloning, assignment and copy construction won't be provided.
  * Erase/etc container methods would only unlink the container's hook.

The containers owning data would:
 * Always own the data collectively (the last owner destroys it)
 * Assume the data was *always* allocated with new.
 * The cloning/assignement/copy constructor may be provided,
   employing copy constructor or the value and new/delete.
   (I personally would avoid it too as the semantic is too complicated.)

* The value would provide few API functions , e.g.
      * move_value_from_one_container_to_another(),
      * extract_value_out_of_all_containers()
         (similar to std::auto_ptr::release)
     * possibly some pin_value/unpin_value wrapped in a RAII

 * Auto-hooking would behave as it does now. After the last
   hook is unlinked there reference to the value will became invalid.

 * Explicit manual delete of the value would auto-unlink the object first.

 * Erase/etc container methods would unlink the hook
   and delete the value itself if it is not owned anymore.

There would be no way to mistakenly insert a value parametrized
to be owned into non-owning container and vice versa.

This approach is (roughly) semantically equivalent to what the
libraries above offer for lifetime management.

_________________________________________________________
> > "In intrusive containers you don't store a copy of an object,
> > but rather the original object itself."
> >
> > may be better reworded to avoid "store" which usually implies copying.
>
> Ok, but which other word would you use?
>
E.g.

In intrusive containers you don't copy an object into the container
but rather the original object gets linked together with the other
objects in the container.

A schema of slist owning two three values may be the best
description.

_________________________________________________________
> > "Node Algorithm: A class containing typedefs and static functions
> > that manage a group of nodes."
> >
> > - the word "manage" is used for the first tima and may
> > mean quite a many things.
>
> Something like "...that define basic operations that can be applied to a
> groups of nodes"?
>
yeah

________________________________________________________________
> > Possibly this page may contain a link
> >    to complete examples of all possible combinations, e.g.:
> >
> > * node with base hook
> > * node with several base hooks
> > * node with member hook
> > * node with several member hooks
>
> Don't you think this is a bit too much? Do you think an example using
> both (base and member) is too confusing?
>

The prototypical benefactor of such examples
is someone who wrote some code, it didn't work
so he, in the act of desperation, starts to look for working
minimal example to go up.

I go though this regularly.

________________________________________________________________
> > The safe mode (probably) applies to single hook, not for
> > situations with two or more hooks.
>
> No, the safe mode is applied for every hook. If you try to insert an
> object in a container and it's already inserted in another container
> that uses the same hook, the code will assert.
>

I actually intended to write that a value may have more than
one hook and that the text in usage.html should not talk
about the whole object.

 ________________________________________________________________
> 14. using_smart_pointers.html
>
> offset pointer should not be called smart pointer.

Why not? Smart pointers don't need to be related with lifetime
management issues, as I understand the term. How would you call
offset_ptr, a "pointer class"?
----------------

I do not like usage of the word "smart" being expanded.
Here "pointer-like object" or, uggh, "pseudopointer" could be used.

 ________________________________________________________________
> > * Does the library works together with Boost.Serialization?
>
> No. Deserialization would be also a problem. How will be the objects
> created? (intrusive containers don't manage memory)
>
The owning containers (as defined above) would allow (de)serialization.

Thinking of it the current containers should be serializable now assuming:
* the values (physically stored elsewhere) are serialized too
* the values were not cloned

/Pavel