boost/lockfree/stack.hpp

   1 //  Copyright (C) 2008 Tim Blechmann
   2 //
   3 //  Distributed under the Boost Software License, Version 1.0. (See
   4 //  accompanying file LICENSE_1_0.txt or copy at
   5 //  http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Disclaimer: Not a Boost library.
   8
   9 #ifndef BOOST_LOCKFREE_STACK_HPP_INCLUDED
  10 #define BOOST_LOCKFREE_STACK_HPP_INCLUDED
  11
  12 #include <boost/checked_delete.hpp>
  13
  14 #include <boost/static_assert.hpp>
  15 #include <boost/type_traits/is_base_of.hpp>
  16
  17 #include <boost/lockfree/detail/tagged_ptr.hpp>
  18 #include <boost/lockfree/detail/freelist.hpp>
  19 #include <boost/noncopyable.hpp>
  20
  21
  22 namespace boost
  23 {
  24 namespace lockfree
  25 {
  26 template <typename T,
  27           typename freelist_t = caching_freelist_t,
  28           typename Alloc = std::allocator<T>
  29           >
  30 class stack:
  31     boost::noncopyable
  32 {
  33     struct node
  34     {
  35         typedef tagged_ptr<node> tagged_ptr_t;
  36
  37         node(T const & v):
  38             v(v)
  39         {}
  40
  41         tagged_ptr_t next;
  42         T v;
  43     };
  44
  45     typedef tagged_ptr<node> ptr_type;
  46
  47     typedef typename Alloc::template rebind<node>::other node_allocator;
  48 /*     typedef typename detail::select_freelist<node, node_allocator, freelist_t>::type pool_t; */
  49
  50     typedef typename boost::mpl::if_<boost::is_same<freelist_t, caching_freelist_t>,
  51                                      caching_freelist<node, node_allocator>,
  52                                      static_freelist<node, node_allocator>
  53                                      >::type pool_t;
  54
  55 public:
  56     static const bool is_lockfree = node::tagged_ptr_t::is_lockfree;
  57
  58     stack(void):
  59         tos(NULL), pool(128)
  60     {}
  61
  62     explicit stack(std::size_t n):
  63         tos(NULL), pool(n)
  64     {}
  65
  66     bool push(T const & v)
  67     {
  68         node * newnode = alloc_node(v);
  69
  70         if (newnode == 0)
  71             return false;
  72
  73         ptr_type old_tos;
  74         do
  75         {
  76             old_tos.set(tos);
  77             newnode->next.set_ptr(old_tos.get_ptr());
  78         }
  79         while (!tos.cas(old_tos, newnode));
  80
  81         return true;
  82     }
  83
  84     bool pop(T * ret)
  85     {
  86         for (;;)
  87         {
  88             ptr_type old_tos(tos);
  89
  90             if (!old_tos)
  91                 return false;
  92             read_memory_barrier();
  93
  94             node * new_tos = old_tos->next.get_ptr();
  95
  96             if (tos.cas(old_tos, new_tos))
  97             {
  98                 *ret = old_tos->v;
  99                 dealloc_node(old_tos.get_ptr());
 100                 return true;
 101             }
 102         }
 103     }
 104
 105     bool empty(void) const
 106     {
 107         return tos.get_ptr() == NULL;
 108     }
 109
 110 private:
 111     node * alloc_node(T const & t)
 112     {
 113         node * chunk = pool.allocate();
 114         new(chunk) node(t);
 115         return chunk;
 116     }
 117
 118     void dealloc_node(node * n)
 119     {
 120         n->~node();
 121         pool.deallocate(n);
 122     }
 123
 124     volatile ptr_type tos;
 125
 126     static const int padding_size = 64 - sizeof(ptr_type); /* cache lines on current cpus seem to
 127                                                             * be 64 byte */
 128     char padding[padding_size];
 129
 130     pool_t pool;
 131 };
 132
 133
 134 } /* namespace lockfree */
 135 } /* namespace boost */
 136
 137 #endif /* BOOST_LOCKFREE_STACK_HPP_INCLUDED */