Review of Intrusive Container library - What is your evaluation of the design? I like it pretty much. As far as I can see, it is a clear and flexible design. I'm especially happy about the thoughts expressed in "Design Notes". - What is your evaluation of the implementation? I did not really check the implementation. - What is your evaluation of the documentation? Clear and well structured. It was easy to use the ilist container based on this documentation. The only information I missed when using ilist as described below was a specification of iterator behavior under insertion and deletion. I expect the same guarantees as for node based STL containers, but of course this should be explicitly stated. - What is your evaluation of the potential usefulness of the library? Very useful. Intrusive containers have their place without doubt and having an STL-style and -quality library with great flexibility is a big win in my eyes. - Did you try to use the library? With what compiler? Did you have any problems? I converted some code using a proprietary double linked list template to ilist using auto unlink hooks. This went without problems (besides the usual typos). The code was compiled with CodwWarrior 9 under Mac OS X 10.4.8. I intend to leave this code as it is now and convert other double linked lists to ilist over time, too. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I read about 70% of the non-reference part of the documentation with a bias towards double linked lists. My experiment with ilist is described above. I had only a glance at the source code. - Are you knowledgeable about the problem domain? Not really beyond linked lists. - Do you think the library should be accepted as a Boost library? Definitely yes. Regards, Kai Brüning -- Kai Brüning * Geschäftsführer RagTime GmbH * http://www.ragtime.de Neustraße 69 * 40721 Hilden * Deutschland Tel: [49](0)2103 9657-0 * Fax: [49](0)2103 9657-96 Sitz der Gesellschaft: Hilden * Amtsgericht Düsseldorf HRB 45697 Geschäftsführer: Kai Brüning, Helmut Tschemernjak

"Joaquín Mª López Muñoz" The review of Ion Gaztañagas's Intrusive library begins today, (late review, I didn't read any other reviews for the library so far) I support inclusion of the library into Boost. It is work of professional quality, as usual. /Pavel Things that may be changed: * I would personally remove complex and dangerous features as destroying elements from containers and copying and assigning containers. If kept there should be big bold red blinking warnings on the top of respective documentation, something as "WHAT COULD GO WRONG HERE" + examples of how _not_ to do it. More on this bellow. * An vector-like pseudo-intrusive container may be added. It is superfluous but people may like it more than lists. (Is a map like intrusive container possible, btw?) * More examples, e.g. one example per every combination of hooks and containers, just to have something to copy, paste and play. Advanced features may have more examples, including failing ones. The terms in the documentation may be more linked, possibly the glossary may get page of its own. Unsorted notes on the documentation are bellow. ================================================================ 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. 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. I envision something as: class MyData : private inserted_intrusive_containers_counter { boost::intrusive::ilist_member_hook<tag1> hook1; boost::intrusive::ilist_member_hook<tag2> hook2; boost::intrusive::ilist_member_hook<tag3> hook3; public: MyData() : hook1(this), hook2(this), hook3(this) {} }; and whenever the MyData instance is added to another container an internal counter is incremented and whenever it is removed the counter is decremented and when it reaches 0 it self-destroys. ilist<MyData> l1, l2; l1.push_back(*new MyData); l2.push_back(*l1.begin()); l1.clear(); l2.clear(); // object gets deleted now This would be somehow similar to the idiom recommended by the people who wrote Ultima++ (containers are always the owners). ================================================================ 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. * The code snippets should not use generic names as Vector or List for the same reason. * ilist_auto_base_hook etc.: it is not really clear whether the class is intended to be base (it would end with _base). 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. ================================================================ Comments about documentation: they were written as I read the docs for the first time so they look like recorded stream of consciousness. ________________________________________________________________ 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. ------------- "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. ------------- typo: Boost.Intrusivecontainer - missing space -------------- "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. ________________________________________________________________ 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. -------------- 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" ------------ In sentence "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). ----------- Perhaps all newly introduced concepts may be linked to the reference section which formally specifies interface of the class compatible with given concept. Possibly a complete example could be linked. ----------- 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. -------------------- 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. ------------- The term "Node" if not defined and assumed implicitly (or from one prior code snippet). ------------- 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. The documentation does not cover this at all now. E.g. "Value Traits" may be "User Value Traits" or "User Data Traits". -------------- The documentation at this point is not clear (to me) reason for the division between Node Algorithm and Node Traits. The code snippet show both of them as tied (by name) to slist like structure. ________________________________________________________________ 3. presenting_containers.html: In: "Hook constructor initializes the internal data to a well-known safe state and ..." the "internal data" is not defined. ------------- "Non-raw pointers: paragraph - it may be explained what would be advantages of using smart pointers here (I assume the end user soes not see or care about pointers). Mentioning Boost.Shmem offset_ptr together with smart_ptr may be confusing. ------------ 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. ________________________________________________________________ 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 ------------- It may be mentioned that tag does not need to be fully specified. ------------- The documentation may say what are the differences between base- and member-hooks from user point of view and in what situation one may prefere this or that. ------------- 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). --------------- "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. --------------- The safe mode (probably) applies to single hook, not for situations with two or more hooks. ________________________________________________________________ 5. usage_when.html: 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. ------------- In: //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? --------------- The last paragraph about not exposing intrusived containers should have some example. I didn't understood what is the second sentence good for. ________________________________________________________________ 6. auto_unlink_hooks.html: "non-constant time containers" - should have backlink to information what it is. -------------- The mechanism used for auto-unlinking may be described here, with pseudocode or a picture. The text description didn't enlighten me how it is implemented. ---------------- "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. ---------------- "Container contents change silently without touching the container directly. This can lead to surprising effects." touching => referencing This can lead ... => --------------- "safe-mode properties" may be linked ------------- The bool used for SafeMode template parameter may be replaced by an enum and symbolic name. ----------- ilist_auto_base_hook<>::linked() may be is_linked() or is_in_container(). unlink() may be remove_from_container(), the Unix association is not convenient, IMHO. ----------- There should be examples (or linsk to examples) for all possible uses of auto-hooks, e.g.: * auto hook as member * several auto hooks * combination of autohook and "normal" hook ---------- Snippet: //Constant-time size is incompatible with auto-unlink hooks! size => container More explanation and examples could be added as comments. ________________________________________________________________ 7. islist.html: a picture may be handy at this moment. ---------------- "Like the rest of Boost.Intrusive containers, islist has several hook types:" has -> can use or something --------------- "This will tell the intrusive container to insert an additional member..." - it may say what the member size is. --------------- 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> When boost::size_not_kept is detected the ilist may inheric from something else than when anything else is used as SizeType. ---------------- Explanation why the islist is circular and what impact it has on semantics is missing. ------------- 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. ________________________________________________________________ 8. ilist.html: Doubly linked vs. double linked - I am not sure which is the correct spelling, I always used double. ________________________________________________________________ 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). ------------- OT question: could a intrusive container with the data be ROMable? This may be mentioned somewhere. ________________________________________________________________ 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. ________________________________________________________________ 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. ________________________________________________________________ 12. erasing_and_destroying.html: I would say the approach presented here is confusing and should not be provided. I talk about lifetime management elsewhere. 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. ________________________________________________________________ 13. clone_from.html: The introductory paragraph is confusing. ----------- I would not use the work "clone" as it is usually member of the data that are to be cloned. Perhaps copy_from()? ----------- 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. ----------- One needs to remember that the cloned container needs to be destroyed explicitly and manually. It feels rather dangerous. ----------- class X { ... }; X x; ilist<X> c1; ilist<X> c2; c1.push_back(x); c1.clone_from(c1, ...); // will work 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, ...); ----------- This feature looks quite risky. ________________________________________________________________ 14. using_smart_pointers.html offset pointer should not be called smart pointer. ----------- Boost.Smart Pointers is permitted here or not? The docs may say why Boost.Smart Pointers are not useful here. ________________________________________________________________ 15. obtaining_iterators_from_values.html The "intrusive_data" in snipped should be named differently, w/o the word intrusive. ------------- The example may show how e.g. iunordered_set_t::iterator is obtained duriong traversal if ilist. ------------ The docs may say what is this feature good for (traversal, yes, but bit complicated as one needs to keep the first obtained iterator). Something as ability to get the end() and begin(), that would be a killer feature. ------------ "local iterators" - a term I never saw before. Without knowing what it is I do not get half of the content here. ________________________________________________________________ 16. node_algorithms.html: Now thinking about it the term "node algorithm" may be changed to "intrusive container low level support" or so. Node algorithm sounds as something from Boost.Graph. "Node Traits" could be "primitive intrusive operations". ----------- Now I understand that the node algorithms + traits are like building blocks of the library (or are they completely separate?). This may be mentioned in Concepts (I wondered all the time what is was good for) or that part of concepts mayt be moved here. ----------- This page may be named "Low level tools to work with data ready for intrusive data structures" or somethig less clumsy. --------- Possibly this page could be split into three parts (being low level does not mean simple) and visually separated from the rest of documentation (it is about a different library using similar principles, right?) ________________________________________________________________ 17. value_traits.html: "link policy" - term used for the first time. ---------- ValueTraits may be named IntrusiveSupportHelper or IntrusiveTraits or so. Value traits sounds sooo generic and it will be confusing in a large code base. ------- Custom ValueTraits example: "...we only need an extra pointer..." w/o the "extra". "Since we only have two pointers, we can't insert the object in a singly and doubly linked list at the same time." - unclear why this sentence is here. Invalid comment in example code (on the bottom of this section): //Now test both lists "As seen, several key elements of Boost.Intrusive can be reused with custom user types, if the user does not want to use provided Boost.Intrusive facilities." - unclear purpose, truism. ------------ ValueTraits::value_type vs. NodeTraits::node - could be named "reusing primitive intrusive operations for different values" ________________________________________________________________ 18. design_notes.html: 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. -------------- "red-black trees embed the color bit in the parent pointer lower bit, if nodes are two-byte aligned" - OT, is this supported in MultiIndex? -------------- Extending Boost.Intrusive - here perhaps a chart may be added, showing what are the low level tools and who uses what. "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 ... ________________________________________________________________ 19. acknowledgments.html: Joaquin M. Lopez Munoz - some diacritics is missing, doesn't? ________________________________________________________________ 20. ilist.html: why is ilist(const ilist &); listed in public interface if it is not implemented? Dtto operator=(). ------- void push_back(value_type &) ; - why non-const reference? Coudn't it make problems when an temporary is used as the parameter? ------- 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 do not see them listed, are the standalone operators operator==(), operator!=(), ..., swap() implemented? ________________________________________________________________ 21. linking_policy.html: perhaps "internal pointers management policy"? * normal_list -> no_pointer_checks * safe_mode_link: (debug_mode_link?) - it should be said again what happens if the check fails * auto_unlink (self_removing_value?) "Containers also know that the a value can be silently erased..." - what does it mean "they know" - that empty() has worse O complexity? ________________________________________________________________ * Example using BOOST_FOREACH could be added somewhere. * Does Boost.Assign work with this library? * Does the library works together with Boost.Serialization? Would it work correctly with a cloned container? * Does the library (in debug mode) detect adding the same object multiple times into the same container? class X : ... {}; X x; ilist<X> l; l.push_back(x); l.push_back(x); ________________________________________________________________ Code: * perhaps a header with forward declarations could be added into the library, like boost/intrusive_containers_fwd.hpp. ________________________________________________________________ EOF