boost/lockfree/detail/freelist.hpp

   1 //  lock-free freelist
   2 //
   3 //  Copyright (C) 2008, 2009, 2011 Tim Blechmann
   4 //
   5 //  Distributed under the Boost Software License, Version 1.0. (See
   6 //  accompanying file LICENSE_1_0.txt or copy at
   7 //  http://www.boost.org/LICENSE_1_0.txt)
   8
   9 //  Disclaimer: Not a Boost library.
  10
  11 #ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
  12 #define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
  13
  14 #include <boost/lockfree/detail/tagged_ptr.hpp>
  15
  16 #include <boost/lockfree/detail/atomic.hpp>
  17 #include <boost/noncopyable.hpp>
  18
  19 #include <boost/mpl/map.hpp>
  20 #include <boost/mpl/apply.hpp>
  21 #include <boost/mpl/at.hpp>
  22 #include <boost/type_traits/is_pod.hpp>
  23
  24 #include <algorithm>            /* for std::min */
  25
  26 namespace boost
  27 {
  28 namespace lockfree
  29 {
  30 namespace detail
  31 {
  32
  33 struct freelist_node
  34 {
  35     tagged_ptr<freelist_node> next;
  36 };
  37
  38 template <typename T,
  39           bool allocate_may_allocate,
  40           typename Alloc = std::allocator<T>
  41          >
  42 class freelist_stack:
  43     Alloc
  44 {
  45     typedef tagged_ptr<freelist_node> tagged_node_ptr;
  46
  47 public:
  48     freelist_stack (std::size_t n = 0):
  49         pool_(tagged_node_ptr(NULL))
  50     {
  51         reserve_unsafe(n);
  52     }
  53
  54     void reserve (std::size_t count)
  55     {
  56         for (std::size_t i = 0; i != count; ++i) {
  57             T * node = Alloc::allocate(1);
  58             deallocate(node);
  59         }
  60     }
  61
  62     void reserve_unsafe (std::size_t count)
  63     {
  64         for (std::size_t i = 0; i != count; ++i) {
  65             T * node = Alloc::allocate(1);
  66             deallocate_unsafe(node);
  67         }
  68     }
  69
  70     T * construct (void)
  71     {
  72         T * node = allocate();
  73         if (node)
  74             new(node) T();
  75         return node;
  76     }
  77
  78     template <typename ArgumentType>
  79     T * construct (ArgumentType const & arg)
  80     {
  81         T * node = allocate();
  82         if (node)
  83             new(node) T(arg);
  84         return node;
  85     }
  86
  87     T * construct_unsafe (void)
  88     {
  89         T * node = allocate_unsafe();
  90         if (node)
  91             new(node) T();
  92         return node;
  93     }
  94
  95     template <typename ArgumentType>
  96     T * construct_unsafe (ArgumentType const & arg)
  97     {
  98         T * node = allocate_unsafe();
  99         if (node)
 100             new(node) T(arg);
 101         return node;
 102     }
 103
 104
 105     void destruct (T * n)
 106     {
 107         n->~T();
 108         deallocate(n);
 109     }
 110
 111     void destruct_unsafe (T * n)
 112     {
 113         n->~T();
 114         deallocate_unsafe(n);
 115     }
 116
 117     T * allocate (void)
 118     {
 119         tagged_node_ptr old_pool = pool_.load(memory_order_consume);
 120
 121         for(;;) {
 122             if (!old_pool.get_ptr()) {
 123                 if (allocate_may_allocate)
 124                     return Alloc::allocate(1);
 125                 else
 126                     return 0;
 127             }
 128
 129             freelist_node * new_pool_ptr = old_pool->next.get_ptr();
 130             tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
 131
 132             if (pool_.compare_exchange_weak(old_pool, new_pool)) {
 133                 void * ptr = old_pool.get_ptr();
 134                 return reinterpret_cast<T*>(ptr);
 135             }
 136         }
 137     }
 138
 139     T * allocate_unsafe (void)
 140     {
 141         tagged_node_ptr old_pool = pool_.load(memory_order_relaxed);
 142
 143         if (!old_pool.get_ptr()) {
 144             if (allocate_may_allocate)
 145                 return Alloc::allocate(1);
 146             else
 147                 return 0;
 148         }
 149
 150         freelist_node * new_pool_ptr = old_pool->next.get_ptr();
 151         tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
 152
 153         pool_.store(new_pool, memory_order_relaxed);
 154         void * ptr = old_pool.get_ptr();
 155         return reinterpret_cast<T*>(ptr);
 156     }
 157
 158     void deallocate (T * n)
 159     {
 160         void * node = n;
 161         tagged_node_ptr old_pool = pool_.load(memory_order_consume);
 162         freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
 163
 164         for(;;) {
 165             tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag());
 166             new_pool->next.set_ptr(old_pool.get_ptr());
 167
 168             if (pool_.compare_exchange_weak(old_pool, new_pool))
 169                 return;
 170         }
 171     }
 172
 173     void deallocate_unsafe (T * n)
 174     {
 175         void * node = n;
 176         tagged_node_ptr old_pool = pool_.load(memory_order_relaxed);
 177         freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
 178
 179         tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag());
 180         new_pool->next.set_ptr(old_pool.get_ptr());
 181
 182         pool_.store(new_pool, memory_order_relaxed);
 183     }
 184
 185     ~freelist_stack(void)
 186     {
 187         tagged_node_ptr current (pool_);
 188
 189         while (current) {
 190             freelist_node * current_ptr = current.get_ptr();
 191             if (current_ptr)
 192                 current = current_ptr->next;
 193             Alloc::deallocate((T*)current_ptr, 1);
 194         }
 195     }
 196
 197     bool is_lock_free(void) const
 198     {
 199         return pool_.is_lock_free();
 200     }
 201
 202 private:
 203     atomic<tagged_node_ptr> pool_;
 204 };
 205
 206
 207 } /* namespace detail */
 208
 209
 210 struct caching_freelist_t {};
 211 struct static_freelist_t {};
 212
 213
 214
 215 } /* namespace lockfree */
 216 } /* namespace boost */
 217
 218 #endif /* BOOST_LOCKFREE_FREELIST_HPP_INCLUDED */