pion-net
4.0.9
|
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 */