boost/lockfree/stack.hpp

   1 //  Copyright (C) 2008, 2009, 2010, 2011 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/lockfree/detail/atomic.hpp>
  13 #include <boost/checked_delete.hpp>
  14
  15 #include <boost/static_assert.hpp>
  16 #include <boost/type_traits/is_base_of.hpp>
  17
  18 #include <boost/lockfree/detail/tagged_ptr.hpp>
  19 #include <boost/lockfree/detail/freelist.hpp>
  20 #include <boost/noncopyable.hpp>
  21
  22
  23 namespace boost
  24 {
  25
  26 namespace lockfree
  27 {
  28
  29 /** It uses a freelist for memory management, freed nodes are pushed to the freelist and not returned to
  30  *  the os before the stack is destroyed.
  31  *
  32  *  The memory management of the stack can be controlled via its freelist_t template argument. Two different
  33  *  freelists can be used. struct caching_freelist_t selects a caching freelist, which can allocate more nodes
  34  *  from the operating system, and struct static_freelist_t uses a fixed-sized freelist. With a fixed-sized
  35  *  freelist, the push operation may fail, while with a caching freelist, the push operation may block.
  36  *
  37  * */
  38 template <typename T,
  39           typename freelist_t = caching_freelist_t,
  40           typename Alloc = std::allocator<T>
  41           >
  42 class stack:
  43     boost::noncopyable
  44 {
  45 private:
  46 #ifndef BOOST_DOXYGEN_INVOKED
  47     struct node
  48     {
  49         typedef detail::tagged_ptr<node> tagged_node_ptr;
  50
  51         node(T const & v):
  52             v(v)
  53         {}
  54
  55         tagged_node_ptr next;
  56         T v;
  57     };
  58 #endif
  59
  60     typedef detail::tagged_ptr<node> tagged_node_ptr;
  61
  62     typedef typename Alloc::template rebind<node>::other node_allocator;
  63
  64     typedef typename boost::mpl::if_<boost::is_same<freelist_t, caching_freelist_t>,
  65                                      detail::freelist_stack<node, true, node_allocator>,
  66                                      detail::freelist_stack<node, false, node_allocator>
  67                                      >::type pool_t;
  68
  69 public:
  70     /**
  71      * \return true, if implementation is lock-free.
  72      * */
  73     bool is_lock_free (void) const
  74     {
  75         return tos.is_lock_free() && pool.is_lock_free();
  76     }
  77
  78     //! Construct stack.
  79     stack(void):
  80         tos(tagged_node_ptr(NULL, 0))
  81     {}
  82
  83     //! Construct stack, allocate n nodes for the freelist
  84     explicit stack(std::size_t n):
  85         tos(tagged_node_ptr(NULL, 0))
  86     {
  87         pool.reserve(n);
  88     }
  89
  90     //! Allocate n nodes for freelist
  91     void reserve(std::size_t n)
  92     {
  93         pool.reserve(n);
  94     }
  95
  96     /** Destroys stack, free all nodes from freelist.
  97      *
  98      *  \warning not threadsafe
  99      *
 100      * */
 101     ~stack(void)
 102     {
 103         if (!empty()) {
 104             T dummy;
 105             while(pop(dummy))
 106                 ;
 107         }
 108     }
 109
 110     /** Pushes object t to the fifo. May fail, if the freelist is not able to allocate a new fifo node.
 111      *
 112      * \returns true, if the push operation is successful.
 113      *
 114      * \note Thread-safe and non-blocking
 115      * \warning \b Warning: May block if node needs to be allocated from the operating system
 116      * */
 117     bool push(T const & v)
 118     {
 119         node * newnode = pool.construct(v);
 120
 121         if (newnode == 0)
 122             return false;
 123
 124         tagged_node_ptr old_tos = tos.load(detail::memory_order_relaxed);
 125
 126         for (;;) {
 127             tagged_node_ptr new_tos (newnode, old_tos.get_tag());
 128             newnode->next.set_ptr(old_tos.get_ptr());
 129
 130             if (tos.compare_exchange_weak(old_tos, new_tos))
 131                 return true;
 132         }
 133     }
 134
 135     /** Pops object from stack.
 136      *
 137      * If pop operation is successful, object is written to memory location denoted by ret.
 138      *
 139      * \returns true, if the pop operation is successful, false if stack was empty.
 140      *
 141      * \note Thread-safe and non-blocking
 142      *
 143      * */
 144     bool pop(T & ret)
 145     {
 146         tagged_node_ptr old_tos = tos.load(detail::memory_order_consume);
 147
 148         for (;;) {
 149             if (!old_tos.get_ptr())
 150                 return false;
 151
 152             node * new_tos_ptr = old_tos->next.get_ptr();
 153             tagged_node_ptr new_tos(new_tos_ptr, old_tos.get_tag() + 1);
 154
 155             if (tos.compare_exchange_weak(old_tos, new_tos)) {
 156                 ret = old_tos->v;
 157                 pool.destruct(old_tos.get_ptr());
 158                 return true;
 159             }
 160         }
 161     }
 162
 163     /**
 164      * \return true, if stack is empty.
 165      *
 166      * \warning The state of the stack can be modified by other threads
 167      *
 168      * */
 169     bool empty(void) const
 170     {
 171         return tos.load().get_ptr() == NULL;
 172     }
 173
 174 private:
 175 #ifndef BOOST_DOXYGEN_INVOKED
 176     detail::atomic<tagged_node_ptr> tos;
 177
 178     static const int padding_size = BOOST_LOCKFREE_CACHELINE_BYTES - sizeof(tagged_node_ptr);
 179     char padding[padding_size];
 180
 181     pool_t pool;
 182 #endif
 183 };
 184
 185
 186 } /* namespace lockfree */
 187 } /* namespace boost */
 188
 189 #endif /* BOOST_LOCKFREE_STACK_HPP_INCLUDED */