# common/include/boost/lockfree/stack.hpp

    00001 //  Copyright (C) 2008 Tim Blechmann
    00002 //
    00003 //  Distributed under the Boost Software License, Version 1.0. (See
    00004 //  accompanying file LICENSE_1_0.txt or copy at
    00005 //  http://www.boost.org/LICENSE_1_0.txt)
    00006
    00007 //  Disclaimer: Not a Boost library.
    00008
    00009 #ifndef BOOST_LOCKFREE_STACK_HPP_INCLUDED
    00010 #define BOOST_LOCKFREE_STACK_HPP_INCLUDED
    00011
    00012 #include <boost/checked_delete.hpp>
    00013
    00014 #include <boost/static_assert.hpp>
    00015 #include <boost/type_traits/is_base_of.hpp>
    00016
    00017 #include <boost/lockfree/detail/tagged_ptr.hpp>
    00018 #include <boost/lockfree/detail/freelist.hpp>
    00019 #include <boost/noncopyable.hpp>
    00020
    00021
    00022 namespace boost
    00023 {
    00024 namespace lockfree
    00025 {
    00026 template <typename T,
    00027           typename freelist_t = caching_freelist_t,
    00028           typename Alloc = std::allocator<T>
    00029           >
    00030 class stack:
    00031     boost::noncopyable
    00032 {
    00033     struct node
    00034     {
    00035         node(T const & v):
    00036             v(v)
    00037         {}
    00038
    00039         tagged_ptr<node> next;
    00040         T v;
    00041     };
    00042
    00043     typedef tagged_ptr<node> ptr_type;
    00044
    00045     typedef typename Alloc::template rebind<node>::other node_allocator;
    00046 /*     typedef typename detail::select_freelist<node, node_allocator, freelist_t>::type pool_t; */
    00047
    00048     typedef typename boost::mpl::if_<boost::is_same<freelist_t, caching_freelist_t>,
    00049                                      caching_freelist<node, node_allocator>,
    00050                                      static_freelist<node, node_allocator>
    00051                                      >::type pool_t;
    00052
    00053 public:
    00054     static const bool is_lockfree = node::tagged_ptr::is_lockfree;
    00055
    00056     stack(void):
    00057         tos(NULL), pool(128)
    00058     {}
    00059
    00060     explicit stack(std::size_t n):
    00061         tos(NULL), pool(n)
    00062     {}
    00063
    00064     bool push(T const & v)
    00065     {
    00066         node * newnode = alloc_node(v);
    00067
    00068         if (newnode == 0)
    00069             return false;
    00070
    00071         ptr_type old_tos;
    00072         do
    00073         {
    00074             old_tos.set(tos);
    00075             newnode->next.set_ptr(old_tos.get_ptr());
    00076         }
    00077         while (!tos.cas(old_tos, newnode));
    00078
    00079         return true;
    00080     }
    00081
    00082     bool pop(T * ret)
    00083     {
    00084         for (;;)
    00085         {
    00086             ptr_type old_tos;
    00087             old_tos.set(tos);
    00088
    00089             if (!old_tos)
    00090                 return false;
    00091
    00092             node * new_tos = old_tos->next.get_ptr();
    00093
    00094             if (tos.cas(old_tos, new_tos))
    00095             {
    00096                 *ret = old_tos->v;
    00097                 dealloc_node(old_tos.get_ptr());
    00098                 return true;
    00099             }
    00100         }
    00101     }
    00102
    00103     bool empty(void) const
    00104     {
    00105         return tos == NULL;
    00106     }
    00107
    00108 private:
    00109     node * alloc_node(T const & t)
    00110     {
    00111         node * chunk = pool.allocate();
    00112         new(chunk) node(t);
    00113         return chunk;
    00114     }
    00115
    00116     void dealloc_node(node * n)
    00117     {
    00118         n->~node();
    00119         pool.deallocate(n);
    00120     }
    00121
    00122     ptr_type tos;
    00123
    00124     static const int padding_size = 64 - sizeof(ptr_type); /* cache lines on current cpus seem to
    00125                                                             * be 64 byte */
    00126     char padding[padding_size];
    00127
    00128     pool_t pool;
    00129 };
    00130
    00131
    00132 } /* namespace lockfree */
    00133 } /* namespace boost */
    00134
    00135 #endif /* BOOST_LOCKFREE_STACK_HPP_INCLUDED */