Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Concepts explained

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

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
   // ...
};
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;  }
};
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_;
};
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
   // ...
};
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
   // ...
};

PrevUpHomeNext