Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Node algorithms with custom NodeTraits

Intrusive singly linked list algorithms
Intrusive doubly linked list algorithms
Intrusive red-black tree algorithms
Intrusive splay tree algorithms
Intrusive avl tree algorithms
Intrusive treap algorithms

As explained in the Concepts section, Boost.Intrusive containers are implemented using node algorithms that work on generic nodes.

Sometimes, the use of intrusive containers is expensive for some environments and the programmer might want to avoid all the template instantiations related to Boost.Intrusive containers. However, the user can still benefit from Boost.Intrusive using the node algorithms, because some of those algorithms, like red-black tree algorithms, are not trivial to write.

All node algorithm classes are templatized by a NodeTraits class. This class encapsulates the needed internal type declarations and operations to make a node compatible with node algorithms. Each type of node algorithms has its own requirements:

Intrusive singly linked list algorithms

These algorithms are static members of the circular_slist_algorithms class: 

template<class NodeTraits>
struct circular_slist_algorithms;

An empty list is formed by a node whose pointer to the next node points to itself. circular_slist_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:

Typedefs:

  • node: The type of the node that forms the circular list
  • node_ptr: The type of a pointer to a node (usually node*)
  • const_node_ptr: The type of a pointer to a const node (usually const node*)

Static functions:

  • static node_ptr get_next(const_node_ptr n);: Returns a pointer to the next node stored in "n".
  • static void set_next(node_ptr n, node_ptr next);: Sets the pointer to the next node stored in "n" to "next".

Once we have a node traits configuration we can use Boost.Intrusive algorithms with our nodes: 

#include <boost/intrusive/circular_slist_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node *next_;
   //other members...
};

//Define our own slist_node_traits
struct my_slist_node_traits
{
   typedef my_node                                 node;
   typedef my_node *                               node_ptr;
   typedef const my_node *                         const_node_ptr;
   static node_ptr get_next(const_node_ptr n)      {  return n->next_;  }
   static void set_next(node_ptr n, node_ptr next) {  n->next_ = next;  }
};

int main()
{
   typedef boost::intrusive::circular_slist_algorithms<my_slist_node_traits> algo;
   my_node one, two, three;

   //Create an empty singly linked list container:
   //"one" will be the first node of the container
   algo::init_header(&one);
   assert(algo::count(&one) == 1);

   //Now add a new node
   algo::link_after(&one, &two);
   assert(algo::count(&one) == 2);

   //Now add a new node after "one"
   algo::link_after(&one, &three);
   assert(algo::count(&one) == 3);

   //Now unlink the node after one
   algo::unlink_after(&one);
   assert(algo::count(&one) == 2);

   //Now unlink two
   algo::unlink(&two);
   assert(algo::count(&one) == 1);

   return 0;
}

For a complete list of functions see circular_slist_algorithms reference.

Intrusive doubly linked list algorithms

These algorithms are static members of the circular_list_algorithms class: 

template<class NodeTraits>
struct circular_list_algorithms;

An empty list is formed by a node whose pointer to the next node points to itself. circular_list_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:

Typedefs:

  • node: The type of the node that forms the circular list
  • node_ptr: The type of a pointer to a node (usually node*)
  • const_node_ptr: The type of a pointer to a const node (usually const node*)

Static functions:

  • static node_ptr get_next(const_node_ptr n);: Returns a pointer to the next node stored in "n".
  • static void set_next(node_ptr n, node_ptr next);: Sets the pointer to the next node stored in "n" to "next".
  • static node_ptr get_previous(const_node_ptr n);: Returns a pointer to the previous node stored in "n".
  • static void set_previous(node_ptr n, node_ptr prev);: Sets the pointer to the previous node stored in "n" to "prev".

Once we have a node traits configuration we can use Boost.Intrusive algorithms with our nodes: 

#include <boost/intrusive/circular_list_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node *next_, *prev_;
   //other members...
};

//Define our own list_node_traits
struct my_list_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;
   static node_ptr get_next(const_node_ptr n)         {  return n->next_;  }
   static void set_next(node_ptr n, node_ptr next)    {  n->next_ = next;  }
   static node *get_previous(const_node_ptr n)        {  return n->prev_;  }
   static void set_previous(node_ptr n, node_ptr prev){  n->prev_ = prev;  }
};

int main()
{
   typedef boost::intrusive::circular_list_algorithms<my_list_node_traits> algo;
   my_node one, two, three;

   //Create an empty doubly linked list container:
   //"one" will be the first node of the container
   algo::init_header(&one);
   assert(algo::count(&one) == 1);

   //Now add a new node before "one"
   algo::link_before(&one, &two);
   assert(algo::count(&one) == 2);

   //Now add a new node after "two"
   algo::link_after(&two, &three);
   assert(algo::count(&one) == 3);

   //Now unlink the node after one
   algo::unlink(&three);
   assert(algo::count(&one) == 2);

   //Now unlink two
   algo::unlink(&two);
   assert(algo::count(&one) == 1);

   //Now unlink one
   algo::unlink(&one);
   assert(algo::count(&one) == 1);

   return 0;
}

For a complete list of functions see circular_list_algorithms reference.

Intrusive red-black tree algorithms

These algorithms are static members of the rbtree_algorithms class: 

template<class NodeTraits>
struct rbtree_algorithms;

An empty tree is formed by a node whose pointer to the parent node is null, the left and right node pointers point to itself, and whose color is red. rbtree_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:

Typedefs:

  • node: The type of the node that forms the circular rbtree
  • node_ptr: The type of a pointer to a node (usually node*)
  • const_node_ptr: The type of a pointer to a const node (usually const node*)
  • color: The type that can store the color of a node

Static functions:

  • static node_ptr get_parent(const_node_ptr n);: Returns a pointer to the parent node stored in "n".
  • static void set_parent(node_ptr n, node_ptr p);: Sets the pointer to the parent node stored in "n" to "p".
  • static node_ptr get_left(const_node_ptr n);: Returns a pointer to the left node stored in "n".
  • static void set_left(node_ptr n, node_ptr l);: Sets the pointer to the left node stored in "n" to "l".
  • static node_ptr get_right(const_node_ptr n);: Returns a pointer to the right node stored in "n".
  • static void set_right(node_ptr n, node_ptr r);: Sets the pointer to the right node stored in "n" to "r".
  • static color get_color(const_node_ptr n);: Returns the color stored in "n".
  • static void set_color(node_ptr n, color c);: Sets the color stored in "n" to "c".
  • static color black();: Returns a value representing the black color.
  • static color red();: Returns a value representing the red color.

Once we have a node traits configuration we can use Boost.Intrusive algorithms with our nodes: 

#include <boost/intrusive/rbtree_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node(int i = 0)
      :  int_(i)
   {}
   my_node *parent_, *left_, *right_;
   int      color_;
   //other members
   int      int_;
};

//Define our own rbtree_node_traits
struct my_rbtree_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;
   typedef int                                        color;
   static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }
   static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }
   static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }
   static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }
   static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }
   static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }
   static color get_color(const_node_ptr n)           {  return n->color_;    }
   static void set_color(node_ptr n, color c)         {  n->color_ = c;       }
   static color black()                               {  return color(0);     }
   static color red()                                 {  return color(1);     }
};

struct node_ptr_compare
{
   bool operator()(const my_node *a, const my_node *b)
   {  return a->int_ < b->int_;  }
};

int main()
{
   typedef boost::intrusive::rbtree_algorithms<my_rbtree_node_traits> algo;
   my_node header, two(2), three(3);

   //Create an empty rbtree container:
   //"header" will be the header node of the tree
   algo::init_header(&header);

   //Now insert node "two" in the tree using the sorting functor
   algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());

   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());

   //Now take the first node (the left node of the header)
   my_node *n = header.left_;
   assert(n == &two);

   //Now go to the next node
   n = algo::next_node(n);
   assert(n == &three);

   //Erase a node just using a pointer to it
   algo::unlink(&two);

   //Erase a node using also the header (faster)
   algo::erase(&header, &three);
   return 0;
}

For a complete list of functions see rbtree_algorithms reference.

Intrusive splay tree algorithms

These algorithms are static members of the splaytree_algorithms class: 

template<class NodeTraits>
struct splaytree_algorithms;

An empty tree is formed by a node whose pointer to the parent node is null, and whose left and right nodes pointers point to itself. splaytree_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:

Typedefs:

  • node: The type of the node that forms the circular splaytree
  • node_ptr: The type of a pointer to a node (usually node*)
  • const_node_ptr: The type of a pointer to a const node (usually const node*)

Static functions:

  • static node_ptr get_parent(const_node_ptr n);: Returns a pointer to the parent node stored in "n".
  • static void set_parent(node_ptr n, node_ptr p);: Sets the pointer to the parent node stored in "n" to "p".
  • static node_ptr get_left(const_node_ptr n);: Returns a pointer to the left node stored in "n".
  • static void set_left(node_ptr n, node_ptr l);: Sets the pointer to the left node stored in "n" to "l".
  • static node_ptr get_right(const_node_ptr n);: Returns a pointer to the right node stored in "n".
  • static void set_right(node_ptr n, node_ptr r);: Sets the pointer to the right node stored in "n" to "r".

Once we have a node traits configuration we can use Boost.Intrusive algorithms with our nodes: 

#include <boost/intrusive/splaytree_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node(int i = 0)
      :  int_(i)
   {}
   my_node *parent_, *left_, *right_;
   //other members
   int      int_;
};

//Define our own splaytree_node_traits
struct my_splaytree_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;

   static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }
   static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }
   static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }
   static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }
   static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }
   static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }
};

struct node_ptr_compare
{
   bool operator()(const my_node *a, const my_node *b)
   {  return a->int_ < b->int_;  }
};

int main()
{
   typedef boost::intrusive::splaytree_algorithms<my_splaytree_node_traits> algo;
   my_node header, two(2), three(3);

   //Create an empty splaytree container:
   //"header" will be the header node of the tree
   algo::init_header(&header);

   //Now insert node "two" in the tree using the sorting functor
   algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());

   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());

   //Now take the first node (the left node of the header)
   my_node *n = header.left_;
   assert(n == &two);

   //Now go to the next node
   n = algo::next_node(n);
   assert(n == &three);

   //Erase a node just using a pointer to it
   algo::unlink(&two);

   //Erase a node using also the header (faster)
   algo::erase(&header, &three);
   return 0;
}

For a complete list of functions see splaytree_algorithms reference.

Intrusive avl tree algorithms

avltree_algorithms have the same interface as rbtree_algorithms. 

template<class NodeTraits>
struct avltree_algorithms;

avltree_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:

Typedefs:

  • node: The type of the node that forms the circular avltree
  • node_ptr: The type of a pointer to a node (usually node*)
  • const_node_ptr: The type of a pointer to a const node (usually const node*)
  • balance: A type that can represent 3 balance types (usually an integer)

Static functions:

  • static node_ptr get_parent(const_node_ptr n);: Returns a pointer to the parent node stored in "n".
  • static void set_parent(node_ptr n, node_ptr p);: Sets the pointer to the parent node stored in "n" to "p".
  • static node_ptr get_left(const_node_ptr n);: Returns a pointer to the left node stored in "n".
  • static void set_left(node_ptr n, node_ptr l);: Sets the pointer to the left node stored in "n" to "l".
  • static node_ptr get_right(const_node_ptr n);: Returns a pointer to the right node stored in "n".
  • static void set_right(node_ptr n, node_ptr r);: Sets the pointer to the right node stored in "n" to "r".
  • static balance get_balance(const_node_ptr n);: Returns the balance factor stored in "n".
  • static void set_balance(node_ptr n, balance b);: Sets the balance factor stored in "n" to "b".
  • static balance negative();: Returns a value representing a negative balance factor.
  • static balance zero();: Returns a value representing a zero balance factor.
  • static balance positive();: Returns a value representing a positive balance factor.

Once we have a node traits configuration we can use Boost.Intrusive algorithms with our nodes: 

#include <boost/intrusive/avltree_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node(int i = 0)
      :  int_(i)
   {}
   my_node *parent_, *left_, *right_;
   int balance_;
   //other members
   int      int_;
};

//Define our own avltree_node_traits
struct my_avltree_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;
   typedef int                                        balance;

   static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }
   static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }
   static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }
   static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }
   static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }
   static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }
   static balance get_balance(const_node_ptr n)       {  return n->balance_;  }
   static void set_balance(node_ptr n, balance b)     {  n->balance_ = b;     }
   static balance negative()                          {  return -1; }
   static balance zero()                              {  return 0;  }
   static balance positive()                          {  return 1;  }
};

struct node_ptr_compare
{
   bool operator()(const my_node *a, const my_node *b)
   {  return a->int_ < b->int_;  }
};

int main()
{
   typedef boost::intrusive::avltree_algorithms<my_avltree_node_traits> algo;
   my_node header, two(2), three(3);

   //Create an empty avltree container:
   //"header" will be the header node of the tree
   algo::init_header(&header);

   //Now insert node "two" in the tree using the sorting functor
   algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());

   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());

   //Now take the first node (the left node of the header)
   my_node *n = header.left_;
   assert(n == &two);

   //Now go to the next node
   n = algo::next_node(n);
   assert(n == &three);

   //Erase a node just using a pointer to it
   algo::unlink(&two);

   //Erase a node using also the header (faster)
   algo::erase(&header, &three);
   return 0;
}

For a complete list of functions see avltree_algorithms reference.

Intrusive treap algorithms

treap_algorithms have the same interface as rbtree_algorithms. 

template<class NodeTraits>
struct treap_algorithms;

treap_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:

Typedefs:

  • node: The type of the node that forms the circular treap
  • node_ptr: The type of a pointer to a node (usually node*)
  • const_node_ptr: The type of a pointer to a const node (usually const node*)

Static functions:

  • static node_ptr get_parent(const_node_ptr n);: Returns a pointer to the parent node stored in "n".
  • static void set_parent(node_ptr n, node_ptr p);: Sets the pointer to the parent node stored in "n" to "p".
  • static node_ptr get_left(const_node_ptr n);: Returns a pointer to the left node stored in "n".
  • static void set_left(node_ptr n, node_ptr l);: Sets the pointer to the left node stored in "n" to "l".
  • static node_ptr get_right(const_node_ptr n);: Returns a pointer to the right node stored in "n".
  • static void set_right(node_ptr n, node_ptr r);: Sets the pointer to the right node stored in "n" to "r".

Once we have a node traits configuration we can use Boost.Intrusive algorithms with our nodes: 

#include <boost/intrusive/treap_algorithms.hpp>
#include <cassert>

struct my_node
{
   my_node(int i = 0, int priority = 0)
      :  prio_(priority), int_(i)
   {}
   my_node *parent_, *left_, *right_;
   int prio_;
   //other members
   int      int_;
};

//Define our own treap_node_traits
struct my_treap_node_traits
{
   typedef my_node                                    node;
   typedef my_node *                                  node_ptr;
   typedef const my_node *                            const_node_ptr;

   static node_ptr get_parent(const_node_ptr n)       {  return n->parent_;   }
   static void set_parent(node_ptr n, node_ptr parent){  n->parent_ = parent; }
   static node_ptr get_left(const_node_ptr n)         {  return n->left_;     }
   static void set_left(node_ptr n, node_ptr left)    {  n->left_ = left;     }
   static node_ptr get_right(const_node_ptr n)        {  return n->right_;    }
   static void set_right(node_ptr n, node_ptr right)  {  n->right_ = right;   }
};

struct node_ptr_compare
{  bool operator()(const my_node *a, const my_node *b) {  return a->int_ < b->int_;  }  };

struct node_ptr_priority
{  bool operator()(const my_node *a, const my_node *b) {  return a->prio_ < b->prio_;}  };

int main()
{
   typedef boost::intrusive::treap_algorithms<my_treap_node_traits> algo;
   my_node header, two(2, 5), three(3, 1);

   //Create an empty treap container:
   //"header" will be the header node of the tree
   algo::init_header(&header);

   //Now insert node "two" in the tree using the sorting functor
   algo::insert_equal_upper_bound(&header, &two, node_ptr_compare(), node_ptr_priority());

   //Now insert node "three" in the tree using the sorting functor
   algo::insert_equal_lower_bound(&header, &three, node_ptr_compare(), node_ptr_priority());

   //Now take the first node (the left node of the header)
   my_node *n = header.left_;
   assert(n == &two);

   //Now go to the next node
   n = algo::next_node(n);
   assert(n == &three);

   //Erase a node just using a pointer to it
   algo::unlink(&two, node_ptr_priority());

   //Erase a node using also the header (faster)
   algo::erase(&header, &three, node_ptr_priority());
   return 0;
}

For a complete list of functions see treap_algorithms reference.

Copyright © 2005 Olaf Krzikalla
Copyright © 2006-2015 Ion Gaztanaga

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

PrevUpHomeNext