Concepts explained

This section will expand the explanation of previously presented basic concepts before explaining the customization options of Boost.Intrusive.

Node Algorithms: A set of static functions that implement basic operations on a group of nodes: initialize a node, link_mode_type a node to a group of nodes, unlink a node from another group of nodes, etc. For example, a circular singly linked list is a group of nodes, where each node has a pointer to the next node. Node Algorithms just require a NodeTraits template parameter and they can work with any NodeTraits class that fulfills the needed interface. As an example, here is a class that implements operations7' to manage a group of nodes forming a circular singly linked list:

template<class NodeTraits>
struct my_slist_algorithms
{
   typedef typename NodeTraits::node_ptr       node_ptr;
   typedef typename NodeTraits::const_node_ptr const_node_ptr;

   //Get the previous node of "this_node"
   static node_ptr get_prev_node(node_ptr this_node)
   {
      node_ptr p = this_node;
      while (this_node != NodeTraits::get_next(p))
         p = NodeTraits::get_next(p);
      return p;
   }

   // number of elements in the group of nodes containing "this_node"
   static std::size_t count(const_node_ptr this_node) 
   {
      std::size_t result = 0;
      const_node_ptr p = this_node;
      do{
         p = NodeTraits::get_next(p);
         ++result;
      } while (p != this_node);
      return result;
   }

   // More operations
   // ...
};

Node Traits: A class that encapsulates the basic information and operations on a node within a group of nodes: the type of the node, a function to obtain the pointer to the next node, etc. Node Traits specify the configuration information Node Algorithms need. Each type of Node Algorithm expects an interface that compatible Node Traits classes must implement. As an example, this is the definition of a Node Traits class that is compatible with the previously presented my_slist_algorithms:

struct my_slist_node_traits
{
   //The type of the node
   struct node
   {
      node *next_;
   };      
  
   typedef node *       node_ptr;
   typedef const node * const_node_ptr;

   //A function to obtain a pointer to the next node
   static node_ptr get_next(const_node_ptr n)
   {  return n->next_;  }  

   //A function to set the pointer to the next node
   static void set_next(node_ptr n, node_ptr next)
   {  n->next_ = next;  }  
};

Hook: A class that the user must add as a base class or as a member to his own class to make that class insertable in an intrusive container. Usually the hook contains a node object that will be used to form the group of nodes: For example, the following class is a Hook that the user can add as a base class, to make the user class compatible with a singly linked list container:

class my_slist_base_hook
      //This hook contains a node, that will be used
      //to link the user object in the group of nodes
   : private my_slist_node_traits::node
{
   typedef my_slist_node_traits::node_ptr       node_ptr;
   typedef my_slist_node_traits::const_node_ptr const_node_ptr;

   //Converts the generic node to the hook
   static my_slist_base_hook *to_hook_ptr(node_ptr p)
   {  return static_cast<my_slist_base_hook*>(p); }

   //Returns the generic node stored by this hook
   node_ptr to_node_ptr()
   { return static_cast<node *const>(this); }

   // More operations
   // ...
};

//To make MyClass compatible with an intrusive singly linked list
//derive our class from the hook.
class MyClass
   :  public my_slist_base_hook
{
   void set(int value);
   int get() const;

   private:
   int value_;
};

Intrusive Container: A container that offers a STL-like interface to store user objects. An intrusive container can be templatized to store different value types that use different hooks. An intrusive container is also more elaborate than a group of nodes: it can store the number of elements to achieve constant-time size information, it can offer debugging facilities, etc. For example, an slist container (intrusive singly linked list) should be able to hold MyClass objects that might have decided to store the hook as a base class or as a member. Internally, the container will use Node Algorithms to implement its operations, and an intrusive container is configured using a template parameter called ValueTraits. ValueTraits will contain the information to convert user classes in nodes compatible with Node Algorithms. For example, this a possible slist implementation:

template<class ValueTraits, ...>
class slist
{
   public:
   typedef typename ValueTraits::value_type value_type;

   //More typedefs and functions
   // ...

   //Insert the value as the first element of the list
   void push_front (reference value) 
   {
      node_ptr to_insert(ValueTraits::to_node_ptr(value));
      circular_list_algorithms::link_after(to_insert, get_root_node()); 
   }

   // More operations
   // ...
};

Semi-Intrusive Container: A semi-intrusive container is similar to an intrusive container, but apart from the values to be inserted in the container, it needs additional memory (for example, auxiliary arrays or indexes).
Value Traits: As we can see, to make our classes intrusive-friendly we add a simple hook as a member or base class. The hook contains a generic node that will be inserted in a group of nodes. Node Algorithms just work with nodes and don't know anything about user classes. On the other hand, an intrusive container needs to know how to obtain a node from a user class, and also the inverse operation. So we can define ValueTraits as the glue between user classes and nodes required by Node Algorithms. Let's see a possible implementation of a value traits class that glues MyClass and the node stored in the hook:

struct my_slist_derivation_value_traits
{
   public:
   typedef slist_node_traits           node_traits;
   typedef MyClass                     value_type;
   typedef node_traits::node_ptr       node_ptr;
   typedef value_type*                 pointer;
   //...

   //Converts user's value to a generic node
   static node_ptr to_node_ptr(reference value)
   { return static_cast<slist_base_hook &>(value).to_node_ptr(); }

   //Converts a generic node into user's value
   static value_type *to_value_ptr(node_traits::node *n) 
   { static_cast<value_type*>(slist_base_hook::to_hook_ptr(n)); }

   // More operations
   // ...
};

Boost C++ Libraries

Concepts explained