Hi Pavel, Nice to see you've found time to the the review. I will reply the comments that I'll consider most important: 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?
(Is a map like intrusive container possible, btw?)
I think a map-like intrusive structure is not very useful. A iset with a value type that has std::pair interface is enough, the advanced search functions can be used to compare the key part with the value type.
* More examples, e.g. one example per every combination of hooks and containers, just to have something to copy, paste and play.
"Every combination" might be too much ;-) but when presenting each container, I might add example using different hooks.
================================================================ One existing library that implement intrusive containers is Data Object Library (http://www.codefarms.com/dol.htm, also http://www.codefarms.com/ptl.htm).
This library uses external, preprocessor like, tool to generate code that handles lifetime management of the data. It meansd that you create an object, add into into how many containers you want and when it is removed from the last container then it gets automagically deleted.
Author of the library claimed development time speedup 10x comparing to classical manual lifetime management.
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.
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.
================================================================ Naming conventions:
* I would personally prefere names like boost::intrusive_slist. The ilist is too easy to overlook and this type of naming is used way too often to cause confusion.
Ok. People consider boost::intrusive::slist good enough, but I have no problem with the names.
* The code snippets should not use generic names as Vector or List for the same reason.
Ok.
* ilist_auto_base_hook etc.: it is not really clear whether the class is intended to be base (it would end with _base).
It's difficult to find a meaningful short name. I think list_base_hook is good enough, but suggestions are welcome.
Perhaps auto_removing_i[ntrusive_]list_base. The word "hook" looks as unnecessary. The member hook may look like: auto_removing_i[ntrusive_]list_support.
Others have proposed using a single class using template parameters to specify the linking policy (safe, normal, auto-unlink).
1. overview.html: the sentence
"On the other hand, an intrusive container does not store copies of passed objects, but it stores the objects themselves."
may be better w/o using work store:
"On the other hand, an intrusive container does not insert copies of passed objects, but it references the objects themselves, without copying their data."
or so.
Your phrase is not convinging for me, but I don't find mine good enough.
"If you want to share an object between two containers, you either have to store multiple copies of those objects or you need to use containers of pointers: std::list<Object*>."
append "... or of smart pointers" just to remind this.
Ok.
------------- typo: Boost.Intrusivecontainer - missing space
Ok.
-------------- "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?
________________________________________________________________ 2. concepts.html:
Evry concept here may contain link to a small but complete example.
If is the second page in documentation and it may be bit too scaring for a newbie to get overloaded with abstract concepts w/o seeing what it could be good for.
I will try to link concepts. Others have proposed moving he full concepts page to the end of the documentation and start with an small summay.
The bullet item starting with "Node Traits" is a bit hard to parse:
* the term basic operations may be explained (or at least differenciated from NodeAlgorithms at this point) * "defines the interface" may be better "expects interface"
typo " to its own class" -> "to his own class"
Ok.
"ValueTraits will contain the information to convert user classes in nodes compatible with Node Algorithms."
I am missing what are the user classes converted into (that's that way I parsed it).
Ok. I will try to improve this.
I do not like the term "Pseudo-Intrusive Container" * it suggest something less worth that the "real container" * it gives impression that the essence of intrusiveness is missing here, which it is not, AFAICS
Perhaps "Intrusive Container with auxiliary allocated memory" looks clumsy but it exactly says what it is and nothing more.
I would prefer something shorter ;-)
In concepts summary: the sentence
"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"?
The term "Node" if not defined and assumed implicitly (or from one prior code snippet).
...and this one it's quite difficult to define, I'm afraid.
------------- Possibly the names of the concepts may reflect which concetps are already implemented by the library and which always need to be reimplemented by the user.
All these concepts are implemented by the library, even though some are customizable by the user.
Auto-unlink hooks are mentioned here for the first time but ony in one sencence, As this may be one of the most useful features there ay be a link and/or example so the reader would be able to test it immediatelly.
Ok, a link to the auto-unlink hooks page would be enough.
________________________________________________________________ 4. usage.html:
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?
It may be mentioned that tag does not need to be fully specified.
Ok.
------------- the code snippet with typedef boost::intrusive::ilist_base_hook<Foo>::value_traits<Foo> FooValueTraits;
contradicts the complete example bellow with:
typedef ilist< ilist_base_hook<my_tag>::value_traits<MyClass> > BaseList;
(in what is used as the template parameter of value_traits).
Well, MyClass is a concrete class of the example, so I thought it was not confusing, I could just write MyClass in both examples, if that's less confusing.
"With these features, without any external reference the user can know if the object has been inserted in a container."
- this should mention the API call to find out this information.
Ok.
--------------- 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.
The items: * the programmer needs to efficiently track the construction and destruction of objects * exception safety, especially the no-throw guarantee, is needed
may need bit more context.
The item: * additional memory management should be avoided
may talk rather about the allocation.
I'll try to elaborate a bit more.
//This is a container of abstract values: you can't do this with std::list. typedef boost::intrusive::ilist< Window::value_traits<Window> > win_list;
"abstract value" is what?
Ok. "Abstract class" is maybe more correct?
________________________________________________________________ 6. auto_unlink_hooks.html:
"non-constant time containers" - should have backlink to information what it is.
Ok.
---------------- "If several threads are using the same container, removing the object is thread-unsafe."
I guess that is true for removing an item from container explicitly.
I will improve it. The difference is that removing explicitly can be executed with a locked mutex, whereas the destructor is not explicitly called, will be automatically executed and the user might forget this operation.
----------------
"Container contents change silently without touching the container directly. This can lead to surprising effects."
touching => referencing This can lead ... =>
Touching is not referencing. Touching should say "modifying"
The bool used for SafeMode template parameter may be replaced by an enum and symbolic name.
Ok.
ilist_auto_base_hook<>::linked()
may be is_linked() or is_in_container().
is_linked() sounds good. No problem to change it.
--------------- Possible change in API: the second and third template parameters may be merged into one, like:
template<class ValueTraits, class SizeType = std::size_t> class islist;
and for no constant size() used as
ilist<a_tag, boost::size_not_kept>
I've already explained that I consider these properties orthogonal. You might not have a constant-time size but still need a non trivial std::size_t to give support for allocator based non-intrusive containers.
Explanation why the islist is circular and what impact it has on semantics is missing.
Others prefer to remove this reference and not say how it's implemented. I think this should be the case with list/slist/set-containers that can be implemented differently. If more containers are added, like irbtree/avl_tree or similar, this should be explained.
It would be interesting to hear whether the "two-way pointers" (e.g. http://www.semantics.org/code.html#flist) could be used together with Boost.Intrusive Containers.
I will investigate it.
________________________________________________________________ 9. iset_imultiset.html:
"Boost.Intrusive also offers associative containers that can be very useful when creating more complex associative containers,..."
- this is like saying a class may be used to built more complex classes, i.e. redundant (unless I am missing something).
Ok. I´ll remove it.
OT question: could a intrusive container with the data be ROMable? This may be mentioned somewhere.
I don't think so, because an intrusive container must modify the objects.
________________________________________________________________ 10. iunordered_set_iunordered_multiset.html:
memory allocator may be added as template parameter. If someone has really critical need for speed he may employ a zone allocator.
I prefer maintaining memory allocator out of Intrusive. I think this is the correct approach to maintain, even with pseudo-intrusive containers.
________________________________________________________________ 11. advanced_lookups_insertions.html:
"advanced lookup" may be named "matching by partial key", "advanced insertions" could be "optimized insertion".
The lookup by partial key is employed by at least one other library, if found it may be referenced.
Apart from partial keys other types comparable with the value type can be used, so I don't like this term.
________________________________________________________________ 12. erasing_and_destroying.html: [snip] Possible problems with the approach here:
* it is not possible to enforce that the objects destroyed were dynamically allocated.
* it is dangerous when object is part of more than one intrusive container.
* the names remove_and_destroy, erase_and_destroy and clear_and_destroy are not very helpful.
Some have proposed "dispose". I think this feature is really useful to easily build non-intrusive containers above intrusive containers.
________________________________________________________________ 13. clone_from.html: [snip] I noticed the documentation does not mention copyability and assignability of the data handled by intrusive containers. Pehaps the intro should inform what is possible, what is recommended and what dangers there are.
The data handled by intrusive containers have no restrictions. It can be non-copyable and non-moveable, as it's explained in the documentation.
One needs to remember that the cloned container needs to be destroyed explicitly and manually. It feels rather dangerous.
Just like the container from you cloned ;-) That's how intrusive containers work. Your clone function could have just allocate a vector of objects and return a reference instead of calling new.
class X { ... };
X x;
ilist<X> c1; ilist<X> c2; c1.push_back(x);
c1.clone_from(c1, ...); // will work
c1 first clears the target container, so there is nothing to clone.
X x1; X x2;
ilist<X> c3; ilist<X> c4; c3.push_back(x1); c4.push_back(x2);
// will this crash? // (the destroyed will try to delete the local x1) c3.clone_from(c4, ...);
The cloner will not try to delte the local x1, it will just call your destroyer function. Obviously, if you are using local objects this will crash, but with intrusive containers the programmer has the responsibility of memory issues.
________________________________________________________________ 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"?
Boost.Smart Pointers is permitted here or not?
No.
The docs may say why Boost.Smart Pointers are not useful here.
The docs already state that the smart pointers need to have the same ownership semantics as raw pointers. But i will explicitly say the Boost.SmartPointer classes are not compatible.
________________________________________________________________ 15. obtaining_iterators_from_values.html [snip] ------------
The docs may say what is this feature good for (traversal, yes, but bit complicated as one needs to keep the first obtained iterator).
An iterator is the key to access to STL algorithms. If you have the value, you have access to STL algorithms.
Something as ability to get the end() and begin(), that would be a killer feature.
I'm afraid this will be difficult.
"local iterators" - a term I never saw before. Without knowing what it is I do not get half of the content here.
It's in the hash table proposal for C++0x.
-----------
Now I understand that the node algorithms + traits are like building blocks of the library (or are they completely separate?).
These are building blocks, but they can be used for other tasks where containers are not suitable.
Custom ValueTraits example:
"...we only need an extra pointer..."
w/o the "extra".
Ok.
Invalid comment in example code (on the bottom of this section): //Now test both lists
Ok.
------------ ValueTraits::value_type vs. NodeTraits::node
- could be named "reusing primitive intrusive operations for different values"
"Reusing node algorithms for different values" might be better.
Boost.Intrusive in space constrained environments
- here may be a table listing (again) the overhead or calculation of the overhead for list/slist/... node and of list/slist/... container.
I will add this as a separate chapter.
"For example, the programmer can use Boost.Intrusive to manage old data structures whose definition can't be changed."
-> ...can customize parts of Boost.Intrusive ...
Ok.
________________________________________________________________ 19. acknowledgments.html:
Joaquin M. Lopez Munoz - some diacritics is missing, doesn't?
Yes. I still don't know how to insert them in Quickbook, maybe a UTF editor is needed to achieve this. In the header HTML style scape sequences can be used, but not in the documentation body. Don't worry Joaquín, I'll fix that ;-)
why is ilist(const ilist &); listed in public interface if it is not implemented? Dtto operator=().
Boostbook/Doxygen error. Recently fixed in CVS thanks to Eric Niebler.
void push_back(value_type &) ;
- why non-const reference? Coudn't it make problems when an temporary is used as the parameter?
Const refernece has no sense with intrusive containers, because the value has to be modified. Temporaries can't bind to non-const references.
Possibly shift(integer how_much = 1) member could be added that would move begin() and end().
Use case: list of tasks to be processed repeatedly.
I'll think about this.
"Containers also know that the a value can be silently erased..." - what does it mean "they know" - that empty() has worse O complexity?
No just that they must cope with the fact that between two operations, the number of present nodes might have changed. For example, the size can't be internally stored (because it would be invalidated if an auto-unlink value operates between two operations).
* Example using BOOST_FOREACH could be added somewhere.
I'm not a big fan of it ;-(
* Does Boost.Assign work with this library?
No idea. But I plan to maintain the library without many dependencies or compile-time overhead.
* 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)
* Does the library (in debug mode) detect adding the same object multiple times into the same container?
If you are use safe-mode or auto-unlink hooks, yes.
* perhaps a header with forward declarations could be added into the library, like boost/intrusive_containers_fwd.hpp.
Ok.
________________________________________________________________ EOF
Thanks for your thorough review. Professional, as always, Regards, Ion