# common/include/boost/lockfree/detail/freelist.hpp

    00001 //  lock-free freelist
    00002 //
    00003 //  Copyright (C) 2008, 2009 Tim Blechmann
    00004 //
    00005 //  Distributed under the Boost Software License, Version 1.0. (See
    00006 //  accompanying file LICENSE_1_0.txt or copy at
    00007 //  http://www.boost.org/LICENSE_1_0.txt)
    00008
    00009 //  Disclaimer: Not a Boost library.
    00010
    00011 #ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
    00012 #define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
    00013
    00014 #include <boost/lockfree/detail/tagged_ptr.hpp>
    00015 #include <boost/lockfree/atomic_int.hpp>
    00016 #include <boost/noncopyable.hpp>
    00017
    00018 #include <boost/mpl/map.hpp>
    00019 #include <boost/mpl/apply.hpp>
    00020 #include <boost/mpl/at.hpp>
    00021 #include <boost/type_traits/is_pod.hpp>
    00022
    00023 #include <algorithm>            /* for std::min */
    00024
    00025 namespace boost
    00026 {
    00027 namespace lockfree
    00028 {
    00029 namespace detail
    00030 {
    00031
    00032 template <typename T, typename Alloc = std::allocator<T> >
    00033 class dummy_freelist:
    00034     private boost::noncopyable,
    00035     private Alloc
    00036 {
    00037 public:
    00038     T * allocate (void)
    00039     {
    00040         return Alloc::allocate(1);
    00041     }
    00042
    00043     void deallocate (T * n)
    00044     {
    00045         Alloc::deallocate(n, 1);
    00046     }
    00047 };
    00048
    00049 } /* namespace detail */
    00050
    00052 template <typename T,
    00053           std::size_t maximum_size = 64,
    00054           typename Alloc = std::allocator<T> >
    00055 class freelist:
    00056     private detail::dummy_freelist<T, Alloc>
    00057 {
    00058     struct freelist_node
    00059     {
    00060         lockfree::tagged_ptr<freelist_node> next;
    00061     };
    00062
    00063     typedef lockfree::tagged_ptr<freelist_node> tagged_ptr;
    00064
    00065 public:
    00066     freelist(void):
    00067         pool_(NULL)
    00068     {}
    00069
    00070     explicit freelist(std::size_t initial_nodes):
    00071         pool_(NULL)
    00072     {
    00073         for (std::size_t i = 0; i != std::min(initial_nodes, maximum_size); ++i)
    00074         {
    00075             T * node = detail::dummy_freelist<T, Alloc>::allocate();
    00076             deallocate(node);
    00077         }
    00078     }
    00079
    00080     ~freelist(void)
    00081     {
    00082         free_memory_pool();
    00083     }
    00084
    00085     T * allocate (void)
    00086     {
    00087         for(;;)
    00088         {
    00089             tagged_ptr old_pool(pool_);
    00090
    00091             if (!old_pool)
    00092                 return detail::dummy_freelist<T, Alloc>::allocate();
    00093
    00094             freelist_node * new_pool = old_pool->next.get_ptr();
    00095
    00096             if (pool_.cas(old_pool, new_pool))
    00097             {
    00098                 --free_list_size;
    00099                 return reinterpret_cast<T*>(old_pool.get_ptr());
    00100             }
    00101         }
    00102     }
    00103
    00104     void deallocate (T * n)
    00105     {
    00106         if (free_list_size > maximum_size)
    00107         {
    00108             detail::dummy_freelist<T, Alloc>::deallocate(n);
    00109             return;
    00110         }
    00111
    00112         for(;;)
    00113         {
    00114             tagged_ptr old_pool (pool_);
    00115
    00116             freelist_node * new_pool = reinterpret_cast<freelist_node*>(n);
    00117
    00118             new_pool->next.set_ptr(old_pool.get_ptr());
    00119
    00120             if (pool_.cas(old_pool, new_pool))
    00121             {
    00122                 --free_list_size;
    00123                 return;
    00124             }
    00125         }
    00126     }
    00127
    00128 private:
    00129     void free_memory_pool(void)
    00130     {
    00131         tagged_ptr current (pool_);
    00132
    00133         while (current)
    00134         {
    00135             freelist_node * n = current.get_ptr();
    00136             current.set(current->next);
    00137             detail::dummy_freelist<T, Alloc>::deallocate(reinterpret_cast<T*>(n));
    00138         }
    00139     }
    00140
    00141     tagged_ptr pool_;
    00142     atomic_int<unsigned long> free_list_size;
    00143 };
    00144
    00145 template <typename T, typename Alloc = std::allocator<T> >
    00146 class caching_freelist:
    00147     private detail::dummy_freelist<T, Alloc>
    00148 {
    00149     struct freelist_node
    00150     {
    00151         lockfree::tagged_ptr<freelist_node> next;
    00152     };
    00153
    00154     typedef lockfree::tagged_ptr<freelist_node> tagged_ptr;
    00155
    00156 public:
    00157     caching_freelist(void):
    00158         pool_(NULL)
    00159     {}
    00160
    00161     explicit caching_freelist(std::size_t initial_nodes):
    00162         pool_(NULL)
    00163     {
    00164         for (std::size_t i = 0; i != initial_nodes; ++i)
    00165         {
    00166             T * node = detail::dummy_freelist<T, Alloc>::allocate();
    00167             deallocate(node);
    00168         }
    00169     }
    00170
    00171     ~caching_freelist(void)
    00172     {
    00173         free_memory_pool();
    00174     }
    00175
    00176     T * allocate (void)
    00177     {
    00178         for(;;)
    00179         {
    00180             tagged_ptr old_pool(pool_);
    00181
    00182             if (!old_pool)
    00183                 return detail::dummy_freelist<T, Alloc>::allocate();
    00184
    00185             freelist_node * new_pool = old_pool->next.get_ptr();
    00186
    00187             if (pool_.cas(old_pool, new_pool))
    00188                 return reinterpret_cast<T*>(old_pool.get_ptr());
    00189         }
    00190     }
    00191
    00192     void deallocate (T * n)
    00193     {
    00194         for(;;)
    00195         {
    00196             tagged_ptr old_pool (pool_);
    00197
    00198             freelist_node * new_pool = reinterpret_cast<freelist_node*>(n);
    00199
    00200             new_pool->next.set_ptr(old_pool.get_ptr());
    00201
    00202             if (pool_.cas(old_pool,new_pool))
    00203                 return;
    00204         }
    00205     }
    00206
    00207 private:
    00208     void free_memory_pool(void)
    00209     {
    00210         tagged_ptr current (pool_);
    00211
    00212         while (current)
    00213         {
    00214             freelist_node * n = current.get_ptr();
    00215             current.set(current->next);
    00216             detail::dummy_freelist<T, Alloc>::deallocate(reinterpret_cast<T*>(n));
    00217         }
    00218     }
    00219
    00220     tagged_ptr pool_;
    00221 };
    00222
    00223 template <typename T, typename Alloc = std::allocator<T> >
    00224 class static_freelist:
    00225     private Alloc
    00226 {
    00227     struct freelist_node
    00228     {
    00229         lockfree::tagged_ptr<freelist_node> next;
    00230     };
    00231
    00232     typedef lockfree::tagged_ptr<freelist_node> tagged_ptr;
    00233
    00234 public:
    00235     explicit static_freelist(std::size_t max_nodes):
    00236         pool_(NULL), total_nodes(max_nodes)
    00237     {
    00238         chunks = Alloc::allocate(max_nodes);
    00239         for (std::size_t i = 0; i != max_nodes; ++i)
    00240         {
    00241             T * node = chunks + i;
    00242             deallocate(node);
    00243         }
    00244     }
    00245
    00246     ~static_freelist(void)
    00247     {
    00248         Alloc::deallocate(chunks, total_nodes);
    00249     }
    00250
    00251     T * allocate (void)
    00252     {
    00253         for(;;)
    00254         {
    00255             tagged_ptr old_pool(pool_);
    00256
    00257             if (!old_pool)
    00258                 return 0;       /* allocation fails */
    00259
    00260             freelist_node * new_pool = old_pool->next.get_ptr();
    00261
    00262             if (pool_.cas(old_pool, new_pool))
    00263                 return reinterpret_cast<T*>(old_pool.get_ptr());
    00264         }
    00265     }
    00266
    00267     void deallocate (T * n)
    00268     {
    00269         for(;;)
    00270         {
    00271             tagged_ptr old_pool (pool_);
    00272
    00273             freelist_node * new_pool = reinterpret_cast<freelist_node*>(n);
    00274
    00275             new_pool->next.set_ptr(old_pool.get_ptr());
    00276
    00277             if (pool_.cas(old_pool,new_pool))
    00278                 return;
    00279         }
    00280     }
    00281
    00282 private:
    00283     tagged_ptr pool_;
    00284
    00285     const std::size_t total_nodes;
    00286     T* chunks;
    00287 };
    00288
    00289
    00290 struct caching_freelist_t {};
    00291 struct static_freelist_t {};
    00292
    00293 namespace detail
    00294 {
    00295
    00296 #if 0
    00297 template <typename T, typename Alloc, typename tag>
    00298 struct select_freelist
    00299 {
    00300 private:
    00301     typedef typename Alloc::template rebind<T>::other Allocator;
    00302
    00303     typedef typename boost::lockfree::caching_freelist<T, Allocator> cfl;
    00304     typedef typename boost::lockfree::static_freelist<T, Allocator> sfl;
    00305
    00306     typedef typename boost::mpl::map<
    00307         boost::mpl::pair < caching_freelist_t, cfl/* typename boost::lockfree::caching_freelist<T, Alloc> */ >,
    00308         boost::mpl::pair < static_freelist_t,  sfl/* typename boost::lockfree::static_freelist<T, Alloc> */ >,
    00309         int
    00310         > freelists;
    00311 public:
    00312     typedef typename boost::mpl::at<freelists, tag>::type type;
    00313 };
    00314 #endif
    00315
    00316 } /* namespace detail */
    00317 } /* namespace lockfree */
    00318 } /* namespace boost */
    00319
    00320 #endif /* BOOST_LOCKFREE_FREELIST_HPP_INCLUDED */