Boost logo

Boost :

From: Henri Bavestrello (henri.bavestrello_at_[hidden])
Date: 2007-03-20 16:11:54

Dear all,
this being my a first post/review, I hope that it is not too "stupid" ;-).
I have been using this library since last October (actually the latest
version of Olaf Krzikalla that wast uploaded by Ion Gaztañaga in the Vault
around that time) in our Finite Element code. I mainly used the iset/imultiset
containers of that version to somehow emulate an intrusive map:
unfortunately as during looking-up phases I had to create a whole
dummy ojbect initialized with the key searched for to be able to use the
imultiset::find method; I decided to implement an intrusive map (imap)
modifying the red-black tree implementation that comes with the library,
something like:
template<typename Key,
          typename Access,
          typename KeyExtractor,
          typename Compare = std::less<Key>,
          bool clear_on_dtor = true>
class imap : boost::noncopyable
     // typedef

     // select the type of the tree (red-black or avl)
     // depending on the type of the tree hook (i.e. rb_node, avl_node)
     // for instance, a user class UserClass to be used into 2 imap (one using
     // a rb_tree, the other an avl_tree) is defined as
     // class UserClass : public imap_node_d<Tag, unlink_dtor, rbtree_node>,
                          public imap_node_d<Tag, unlink_dtor, avltree_node>
     typedef typename itree_dispatcher<Key,
                                       typename Access::itree_node
>::value_type tree_type;

     tree_type m_tree; // the actual tree structure
    // etc ...
borrowing the keyExtractor concept from the Boost.MultiIndex library.
(being a "baby" in the library/template world, I kind of follow existing
boost libraries design).
I am happy to see that with this new version of the library, I can directly use
the iset container taking advantage of the find(key, comp) method ;-). Also, the
iset container instantiation is simpler as the Compare operator actually
combines the comparison operator and the key extractor.
It may be help full in the example about the iset/imultiset container that the
two container uses different type (currently they both use MyClass int_ data
member as key), and make use of the iset/imultiset::find(key, comp) method.

- What is your evaluation of the design?
I am not qualified enough to say much about it, except that it was easy to use:
creating a container was easy, even with legacy classes. The use of node and
value traits really make customization easy. As for performance oriented code, I
like the presence of insert_check and insert_commit methods of the associative
intrusive containers. I always feel that similar methods were missing from the
STL associative containers.

- What is your evaluation of the implementation?
It is well above my standard ;-). It is well documented and it was quite easy to
navigate through the code.

- What is your evaluation of the potential usefulness of the library?
I find it useful. I agree that this is a kind of "low-level" library and you
have to be aware of what you are doing with it, but it may be worth it in some

- Did you try to use the library? With what compiler? Did you have any
Yes. I used the library with gcc 4.1 and intel icc 9.1 under linux. I didn't
have any problems with the library.

- How much effort did you put into your evaluation? A glance?
    A quick reading? In-depth study?
I have been using the previous version of this library for a couple of months
now. Even though, this new version have been quite upgraded, it was quite easy
to plug it into our code (creating an intrusive map as a wrapper around iset
went smoothly).

- Are you knowledgeable about the problem domain?
I am no expert on containers, but as a user in the HPC community, I well aware
of problems like data locality and cache trashing.

- Do you think the library should be accepted as a Boost library?
Yes. I will definitively use it; and as an other review wrote, I will maintained
my own copy, it is not ...

I really would like to thank very much the authors for their great work.

Best regards,

Institute for Computational & Mathematical Engineering
Stanford University
P.S.: when I implemented the tree methods, I also ran into the problem of
having a constant time size method and allowing the node to unlink
itself from the tree (by calling either node::unlink() or the destructor 
operator). Looking at the original unlink_and_rebalance() method in the rb_node 
class of Olaf Krzikalla's implementation:
void rbtree_node::unlink_and_rebalance()
   rbtree_node* h = this->parent();
   if (h != 0) { // this node is linked
      // go up the tree until the header node
      while (!is_header (h))
         h = h->parent();
      this->remove (*h); // h is the header node
  I figured that the node that unlinks itself knows "implicitly" from
which tree it actually unlinks itself: rbtree_node::unlink_and_rebalance()
starts from the node and goes up the tree until it reaches the tree's header 
node. So to allow both nodes to unlink themselves with a constant time map/tree 
size() method, the tree nodes counter can be actually be embeded into the tree's 
header node which is derived from the rb_node class; and uses a cast in the
rbtree_node::unlink_and_rebalance() method. More precisely, something
likes that:
class rbtree_node
   void unlink_and_rebalance(); // see below
   // other needed methods
    //All needed data member: parent pointer, color, etc ...
class rb_header : public rbtree_node
   rb_header() : rbtree_node(0) { } // rbtree_node(0) makes a header node
   size_t node_count() const { }
   void incr_node_count(ssize_t n) { }
   rb_header() : rbtree_node(0), m_node_count(0) { }
   size_t node_count() const { return m_node_count; }
   void incr_node_count(ssize_t n) { m_node_count += n; }
   size_t m_node_count;
void rbtree_node::unlink_and_rebalance()
   rbtree_node* h = this->parent();
   if (h != 0) { // this node is linked
      // go up the tree until the header node
      while (!is_header (h))
         h = h->parent();
      this->remove (*h); // h is the header node
template<typename Key, typename Access, typename KeyExtractor, typename Compare>
class iRb_tree
     // typedef ...
     // private typedef
     // data member
     rb_header     m_header; // node counter embeded into it if
     key_compare   m_key_compare;
     key_extractor m_key_extractor;
     // some methods that use the nodes'count embeded into the header node
     iterator insert(link_ptr y, const_value_ref val, bool link_left)
       link_ptr z(node(val));
       tree_node::link_and_balance(z, y, link_left, m_header);
       return iterator(z);
     size_type size() const
       return m_header.node_count();
       return std::distance(begin(), end());
   // etc ...
I am not sure if this applicable with the new intrusive library that
uses "generalized pointer"; but if it is, it may allow to have both
constant time size method and auto-unlink node in intrusive containers
that use an rb tree (or avl tree) as underlaying implementation.

Boost list run by bdawes at, gregod at, cpdaniel at, john at