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
slistcontainer (intrusive singly linked list) should be able to holdMyClassobjects 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 possibleslistimplementation:
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 // ... };