Chris@16: //  lock-free freelist
Chris@16: //
Chris@16: //  Copyright (C) 2008-2013 Tim Blechmann
Chris@16: //
Chris@16: //  Distributed under the Boost Software License, Version 1.0. (See
Chris@16: //  accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
Chris@16: #define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
Chris@16: 
Chris@16: #include <limits>
Chris@16: #include <memory>
Chris@16: 
Chris@16: #include <boost/array.hpp>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/cstdint.hpp>
Chris@16: #include <boost/noncopyable.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: 
Chris@16: #include <boost/lockfree/detail/atomic.hpp>
Chris@16: #include <boost/lockfree/detail/parameter.hpp>
Chris@16: #include <boost/lockfree/detail/tagged_ptr.hpp>
Chris@16: 
Chris@16: #if defined(_MSC_VER)
Chris@16: #pragma warning(push)
Chris@16: #pragma warning(disable: 4100) // unreferenced formal parameter
Chris@16: #pragma warning(disable: 4127) // conditional expression is constant
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost    {
Chris@16: namespace lockfree {
Chris@16: namespace detail   {
Chris@16: 
Chris@16: template <typename T,
Chris@16:           typename Alloc = std::allocator<T>
Chris@16:          >
Chris@16: class freelist_stack:
Chris@16:     Alloc
Chris@16: {
Chris@16:     struct freelist_node
Chris@16:     {
Chris@16:         tagged_ptr<freelist_node> next;
Chris@16:     };
Chris@16: 
Chris@16:     typedef tagged_ptr<freelist_node> tagged_node_ptr;
Chris@16: 
Chris@16: public:
Chris@16:     typedef tagged_ptr<T> tagged_node_handle;
Chris@16: 
Chris@16:     template <typename Allocator>
Chris@16:     freelist_stack (Allocator const & alloc, std::size_t n = 0):
Chris@16:         Alloc(alloc),
Chris@16:         pool_(tagged_node_ptr(NULL))
Chris@16:     {
Chris@16:         for (std::size_t i = 0; i != n; ++i) {
Chris@16:             T * node = Alloc::allocate(1);
Chris@16: #ifdef BOOST_LOCKFREE_FREELIST_INIT_RUNS_DTOR
Chris@16:             destruct<false>(node);
Chris@16: #else
Chris@16:             deallocate<false>(node);
Chris@16: #endif
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe>
Chris@16:     void reserve (std::size_t count)
Chris@16:     {
Chris@16:         for (std::size_t i = 0; i != count; ++i) {
Chris@16:             T * node = Alloc::allocate(1);
Chris@16:             deallocate<ThreadSafe>(node);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe, bool Bounded>
Chris@16:     T * construct (void)
Chris@16:     {
Chris@16:         T * node = allocate<ThreadSafe, Bounded>();
Chris@16:         if (node)
Chris@16:             new(node) T();
Chris@16:         return node;
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe, bool Bounded, typename ArgumentType>
Chris@16:     T * construct (ArgumentType const & arg)
Chris@16:     {
Chris@16:         T * node = allocate<ThreadSafe, Bounded>();
Chris@16:         if (node)
Chris@16:             new(node) T(arg);
Chris@16:         return node;
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe, bool Bounded, typename ArgumentType1, typename ArgumentType2>
Chris@16:     T * construct (ArgumentType1 const & arg1, ArgumentType2 const & arg2)
Chris@16:     {
Chris@16:         T * node = allocate<ThreadSafe, Bounded>();
Chris@16:         if (node)
Chris@16:             new(node) T(arg1, arg2);
Chris@16:         return node;
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe>
Chris@16:     void destruct (tagged_node_handle tagged_ptr)
Chris@16:     {
Chris@16:         T * n = tagged_ptr.get_ptr();
Chris@16:         n->~T();
Chris@16:         deallocate<ThreadSafe>(n);
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe>
Chris@16:     void destruct (T * n)
Chris@16:     {
Chris@16:         n->~T();
Chris@16:         deallocate<ThreadSafe>(n);
Chris@16:     }
Chris@16: 
Chris@16:     ~freelist_stack(void)
Chris@16:     {
Chris@16:         tagged_node_ptr current = pool_.load();
Chris@16: 
Chris@16:         while (current) {
Chris@16:             freelist_node * current_ptr = current.get_ptr();
Chris@16:             if (current_ptr)
Chris@16:                 current = current_ptr->next;
Chris@16:             Alloc::deallocate((T*)current_ptr, 1);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     bool is_lock_free(void) const
Chris@16:     {
Chris@16:         return pool_.is_lock_free();
Chris@16:     }
Chris@16: 
Chris@16:     T * get_handle(T * pointer) const
Chris@16:     {
Chris@16:         return pointer;
Chris@16:     }
Chris@16: 
Chris@16:     T * get_handle(tagged_node_handle const & handle) const
Chris@16:     {
Chris@16:         return get_pointer(handle);
Chris@16:     }
Chris@16: 
Chris@16:     T * get_pointer(tagged_node_handle const & tptr) const
Chris@16:     {
Chris@16:         return tptr.get_ptr();
Chris@16:     }
Chris@16: 
Chris@16:     T * get_pointer(T * pointer) const
Chris@16:     {
Chris@16:         return pointer;
Chris@16:     }
Chris@16: 
Chris@16:     T * null_handle(void) const
Chris@16:     {
Chris@16:         return NULL;
Chris@16:     }
Chris@16: 
Chris@16: protected: // allow use from subclasses
Chris@16:     template <bool ThreadSafe, bool Bounded>
Chris@16:     T * allocate (void)
Chris@16:     {
Chris@16:         if (ThreadSafe)
Chris@16:             return allocate_impl<Bounded>();
Chris@16:         else
Chris@16:             return allocate_impl_unsafe<Bounded>();
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     template <bool Bounded>
Chris@16:     T * allocate_impl (void)
Chris@16:     {
Chris@16:         tagged_node_ptr old_pool = pool_.load(memory_order_consume);
Chris@16: 
Chris@16:         for(;;) {
Chris@16:             if (!old_pool.get_ptr()) {
Chris@16:                 if (!Bounded)
Chris@16:                     return Alloc::allocate(1);
Chris@16:                 else
Chris@16:                     return 0;
Chris@16:             }
Chris@16: 
Chris@16:             freelist_node * new_pool_ptr = old_pool->next.get_ptr();
Chris@16:             tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_next_tag());
Chris@16: 
Chris@16:             if (pool_.compare_exchange_weak(old_pool, new_pool)) {
Chris@16:                 void * ptr = old_pool.get_ptr();
Chris@16:                 return reinterpret_cast<T*>(ptr);
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <bool Bounded>
Chris@16:     T * allocate_impl_unsafe (void)
Chris@16:     {
Chris@16:         tagged_node_ptr old_pool = pool_.load(memory_order_relaxed);
Chris@16: 
Chris@16:         if (!old_pool.get_ptr()) {
Chris@16:             if (!Bounded)
Chris@16:                 return Alloc::allocate(1);
Chris@16:             else
Chris@16:                 return 0;
Chris@16:         }
Chris@16: 
Chris@16:         freelist_node * new_pool_ptr = old_pool->next.get_ptr();
Chris@16:         tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_next_tag());
Chris@16: 
Chris@16:         pool_.store(new_pool, memory_order_relaxed);
Chris@16:         void * ptr = old_pool.get_ptr();
Chris@16:         return reinterpret_cast<T*>(ptr);
Chris@16:     }
Chris@16: 
Chris@16: protected:
Chris@16:     template <bool ThreadSafe>
Chris@16:     void deallocate (T * n)
Chris@16:     {
Chris@16:         if (ThreadSafe)
Chris@16:             deallocate_impl(n);
Chris@16:         else
Chris@16:             deallocate_impl_unsafe(n);
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     void deallocate_impl (T * n)
Chris@16:     {
Chris@16:         void * node = n;
Chris@16:         tagged_node_ptr old_pool = pool_.load(memory_order_consume);
Chris@16:         freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
Chris@16: 
Chris@16:         for(;;) {
Chris@16:             tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag());
Chris@16:             new_pool->next.set_ptr(old_pool.get_ptr());
Chris@16: 
Chris@16:             if (pool_.compare_exchange_weak(old_pool, new_pool))
Chris@16:                 return;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void deallocate_impl_unsafe (T * n)
Chris@16:     {
Chris@16:         void * node = n;
Chris@16:         tagged_node_ptr old_pool = pool_.load(memory_order_relaxed);
Chris@16:         freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
Chris@16: 
Chris@16:         tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag());
Chris@16:         new_pool->next.set_ptr(old_pool.get_ptr());
Chris@16: 
Chris@16:         pool_.store(new_pool, memory_order_relaxed);
Chris@16:     }
Chris@16: 
Chris@16:     atomic<tagged_node_ptr> pool_;
Chris@16: };
Chris@16: 
Chris@16: class tagged_index
Chris@16: {
Chris@16: public:
Chris@16:     typedef boost::uint16_t tag_t;
Chris@16:     typedef boost::uint16_t index_t;
Chris@16: 
Chris@16:     /** uninitialized constructor */
Chris@16:     tagged_index(void) BOOST_NOEXCEPT //: index(0), tag(0)
Chris@16:     {}
Chris@16: 
Chris@16:     /** copy constructor */
Chris@16: #ifdef BOOST_NO_CXX11_DEFAULTED_FUNCTIONS
Chris@16:     tagged_index(tagged_index const & rhs):
Chris@16:         index(rhs.index), tag(rhs.tag)
Chris@16:     {}
Chris@16: #else
Chris@16:     tagged_index(tagged_index const & rhs) = default;
Chris@16: #endif
Chris@16: 
Chris@16:     explicit tagged_index(index_t i, tag_t t = 0):
Chris@16:         index(i), tag(t)
Chris@16:     {}
Chris@16: 
Chris@16:     /** index access */
Chris@16:     /* @{ */
Chris@16:     index_t get_index() const
Chris@16:     {
Chris@16:         return index;
Chris@16:     }
Chris@16: 
Chris@16:     void set_index(index_t i)
Chris@16:     {
Chris@16:         index = i;
Chris@16:     }
Chris@16:     /* @} */
Chris@16: 
Chris@16:     /** tag access */
Chris@16:     /* @{ */
Chris@16:     tag_t get_tag() const
Chris@16:     {
Chris@16:         return tag;
Chris@16:     }
Chris@16: 
Chris@16:     tag_t get_next_tag() const
Chris@16:     {
Chris@16:         tag_t next = (get_tag() + 1) & (std::numeric_limits<tag_t>::max)();
Chris@16:         return next;
Chris@16:     }
Chris@16: 
Chris@16:     void set_tag(tag_t t)
Chris@16:     {
Chris@16:         tag = t;
Chris@16:     }
Chris@16:     /* @} */
Chris@16: 
Chris@16:     bool operator==(tagged_index const & rhs) const
Chris@16:     {
Chris@16:         return (index == rhs.index) && (tag == rhs.tag);
Chris@16:     }
Chris@16: 
Chris@16:     bool operator!=(tagged_index const & rhs) const
Chris@16:     {
Chris@16:         return !operator==(rhs);
Chris@16:     }
Chris@16: 
Chris@16: protected:
Chris@16:     index_t index;
Chris@16:     tag_t tag;
Chris@16: };
Chris@16: 
Chris@16: template <typename T,
Chris@16:           std::size_t size>
Chris@16: struct compiletime_sized_freelist_storage
Chris@16: {
Chris@16:     // array-based freelists only support a 16bit address space.
Chris@16:     BOOST_STATIC_ASSERT(size < 65536);
Chris@16: 
Chris@16:     boost::array<char, size * sizeof(T)> data;
Chris@16: 
Chris@16:     // unused ... only for API purposes
Chris@16:     template <typename Allocator>
Chris@16:     compiletime_sized_freelist_storage(Allocator const & /* alloc */, std::size_t /* count */)
Chris@16:     {}
Chris@16: 
Chris@16:     T * nodes(void) const
Chris@16:     {
Chris@16:         return reinterpret_cast<T*>(const_cast<char*>(data.data()));
Chris@16:     }
Chris@16: 
Chris@16:     std::size_t node_count(void) const
Chris@16:     {
Chris@16:         return size;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename T,
Chris@16:           typename Alloc = std::allocator<T> >
Chris@16: struct runtime_sized_freelist_storage:
Chris@16:     Alloc
Chris@16: {
Chris@16:     T * nodes_;
Chris@16:     std::size_t node_count_;
Chris@16: 
Chris@16:     template <typename Allocator>
Chris@16:     runtime_sized_freelist_storage(Allocator const & alloc, std::size_t count):
Chris@16:         Alloc(alloc), node_count_(count)
Chris@16:     {
Chris@16:         if (count > 65535)
Chris@16:             boost::throw_exception(std::runtime_error("boost.lockfree: freelist size is limited to a maximum of 65535 objects"));
Chris@16:         nodes_ = Alloc::allocate(count);
Chris@16:     }
Chris@16: 
Chris@16:     ~runtime_sized_freelist_storage(void)
Chris@16:     {
Chris@16:         Alloc::deallocate(nodes_, node_count_);
Chris@16:     }
Chris@16: 
Chris@16:     T * nodes(void) const
Chris@16:     {
Chris@16:         return nodes_;
Chris@16:     }
Chris@16: 
Chris@16:     std::size_t node_count(void) const
Chris@16:     {
Chris@16:         return node_count_;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename T,
Chris@16:           typename NodeStorage = runtime_sized_freelist_storage<T>
Chris@16:          >
Chris@16: class fixed_size_freelist:
Chris@16:     NodeStorage
Chris@16: {
Chris@16:     struct freelist_node
Chris@16:     {
Chris@16:         tagged_index next;
Chris@16:     };
Chris@16: 
Chris@16:     typedef tagged_index::index_t index_t;
Chris@16: 
Chris@16:     void initialize(void)
Chris@16:     {
Chris@16:         T * nodes = NodeStorage::nodes();
Chris@16:         for (std::size_t i = 0; i != NodeStorage::node_count(); ++i) {
Chris@16:             tagged_index * next_index = reinterpret_cast<tagged_index*>(nodes + i);
Chris@16:             next_index->set_index(null_handle());
Chris@16: 
Chris@16: #ifdef BOOST_LOCKFREE_FREELIST_INIT_RUNS_DTOR
Chris@16:             destruct<false>(nodes + i);
Chris@16: #else
Chris@16:             deallocate<false>(static_cast<index_t>(i));
Chris@16: #endif
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16:     typedef tagged_index tagged_node_handle;
Chris@16: 
Chris@16:     template <typename Allocator>
Chris@16:     fixed_size_freelist (Allocator const & alloc, std::size_t count):
Chris@16:         NodeStorage(alloc, count),
Chris@16:         pool_(tagged_index(static_cast<index_t>(count), 0))
Chris@16:     {
Chris@16:         initialize();
Chris@16:     }
Chris@16: 
Chris@16:     fixed_size_freelist (void):
Chris@16:         pool_(tagged_index(NodeStorage::node_count(), 0))
Chris@16:     {
Chris@16:         initialize();
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe, bool Bounded>
Chris@16:     T * construct (void)
Chris@16:     {
Chris@16:         index_t node_index = allocate<ThreadSafe>();
Chris@16:         if (node_index == null_handle())
Chris@16:             return NULL;
Chris@16: 
Chris@16:         T * node = NodeStorage::nodes() + node_index;
Chris@16:         new(node) T();
Chris@16:         return node;
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe, bool Bounded, typename ArgumentType>
Chris@16:     T * construct (ArgumentType const & arg)
Chris@16:     {
Chris@16:         index_t node_index = allocate<ThreadSafe>();
Chris@16:         if (node_index == null_handle())
Chris@16:             return NULL;
Chris@16: 
Chris@16:         T * node = NodeStorage::nodes() + node_index;
Chris@16:         new(node) T(arg);
Chris@16:         return node;
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe, bool Bounded, typename ArgumentType1, typename ArgumentType2>
Chris@16:     T * construct (ArgumentType1 const & arg1, ArgumentType2 const & arg2)
Chris@16:     {
Chris@16:         index_t node_index = allocate<ThreadSafe>();
Chris@16:         if (node_index == null_handle())
Chris@16:             return NULL;
Chris@16: 
Chris@16:         T * node = NodeStorage::nodes() + node_index;
Chris@16:         new(node) T(arg1, arg2);
Chris@16:         return node;
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe>
Chris@16:     void destruct (tagged_node_handle tagged_index)
Chris@16:     {
Chris@16:         index_t index = tagged_index.get_index();
Chris@16:         T * n = NodeStorage::nodes() + index;
Chris@16:         n->~T();
Chris@16:         deallocate<ThreadSafe>(index);
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe>
Chris@16:     void destruct (T * n)
Chris@16:     {
Chris@16:         n->~T();
Chris@16:         deallocate<ThreadSafe>(n - NodeStorage::nodes());
Chris@16:     }
Chris@16: 
Chris@16:     bool is_lock_free(void) const
Chris@16:     {
Chris@16:         return pool_.is_lock_free();
Chris@16:     }
Chris@16: 
Chris@16:     index_t null_handle(void) const
Chris@16:     {
Chris@16:         return static_cast<index_t>(NodeStorage::node_count());
Chris@16:     }
Chris@16: 
Chris@16:     index_t get_handle(T * pointer) const
Chris@16:     {
Chris@16:         if (pointer == NULL)
Chris@16:             return null_handle();
Chris@16:         else
Chris@16:             return static_cast<index_t>(pointer - NodeStorage::nodes());
Chris@16:     }
Chris@16: 
Chris@16:     index_t get_handle(tagged_node_handle const & handle) const
Chris@16:     {
Chris@16:         return handle.get_index();
Chris@16:     }
Chris@16: 
Chris@16:     T * get_pointer(tagged_node_handle const & tptr) const
Chris@16:     {
Chris@16:         return get_pointer(tptr.get_index());
Chris@16:     }
Chris@16: 
Chris@16:     T * get_pointer(index_t index) const
Chris@16:     {
Chris@16:         if (index == null_handle())
Chris@16:             return 0;
Chris@16:         else
Chris@16:             return NodeStorage::nodes() + index;
Chris@16:     }
Chris@16: 
Chris@16:     T * get_pointer(T * ptr) const
Chris@16:     {
Chris@16:         return ptr;
Chris@16:     }
Chris@16: 
Chris@16: protected: // allow use from subclasses
Chris@16:     template <bool ThreadSafe>
Chris@16:     index_t allocate (void)
Chris@16:     {
Chris@16:         if (ThreadSafe)
Chris@16:             return allocate_impl();
Chris@16:         else
Chris@16:             return allocate_impl_unsafe();
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     index_t allocate_impl (void)
Chris@16:     {
Chris@16:         tagged_index old_pool = pool_.load(memory_order_consume);
Chris@16: 
Chris@16:         for(;;) {
Chris@16:             index_t index = old_pool.get_index();
Chris@16:             if (index == null_handle())
Chris@16:                 return index;
Chris@16: 
Chris@16:             T * old_node = NodeStorage::nodes() + index;
Chris@16:             tagged_index * next_index = reinterpret_cast<tagged_index*>(old_node);
Chris@16: 
Chris@16:             tagged_index new_pool(next_index->get_index(), old_pool.get_next_tag());
Chris@16: 
Chris@16:             if (pool_.compare_exchange_weak(old_pool, new_pool))
Chris@16:                 return old_pool.get_index();
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     index_t allocate_impl_unsafe (void)
Chris@16:     {
Chris@16:         tagged_index old_pool = pool_.load(memory_order_consume);
Chris@16: 
Chris@16:         index_t index = old_pool.get_index();
Chris@16:         if (index == null_handle())
Chris@16:             return index;
Chris@16: 
Chris@16:         T * old_node = NodeStorage::nodes() + index;
Chris@16:         tagged_index * next_index = reinterpret_cast<tagged_index*>(old_node);
Chris@16: 
Chris@16:         tagged_index new_pool(next_index->get_index(), old_pool.get_next_tag());
Chris@16: 
Chris@16:         pool_.store(new_pool, memory_order_relaxed);
Chris@16:         return old_pool.get_index();
Chris@16:     }
Chris@16: 
Chris@16:     template <bool ThreadSafe>
Chris@16:     void deallocate (index_t index)
Chris@16:     {
Chris@16:         if (ThreadSafe)
Chris@16:             deallocate_impl(index);
Chris@16:         else
Chris@16:             deallocate_impl_unsafe(index);
Chris@16:     }
Chris@16: 
Chris@16:     void deallocate_impl (index_t index)
Chris@16:     {
Chris@16:         freelist_node * new_pool_node = reinterpret_cast<freelist_node*>(NodeStorage::nodes() + index);
Chris@16:         tagged_index old_pool = pool_.load(memory_order_consume);
Chris@16: 
Chris@16:         for(;;) {
Chris@16:             tagged_index new_pool (index, old_pool.get_tag());
Chris@16:             new_pool_node->next.set_index(old_pool.get_index());
Chris@16: 
Chris@16:             if (pool_.compare_exchange_weak(old_pool, new_pool))
Chris@16:                 return;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void deallocate_impl_unsafe (index_t index)
Chris@16:     {
Chris@16:         freelist_node * new_pool_node = reinterpret_cast<freelist_node*>(NodeStorage::nodes() + index);
Chris@16:         tagged_index old_pool = pool_.load(memory_order_consume);
Chris@16: 
Chris@16:         tagged_index new_pool (index, old_pool.get_tag());
Chris@16:         new_pool_node->next.set_index(old_pool.get_index());
Chris@16: 
Chris@16:         pool_.store(new_pool);
Chris@16:     }
Chris@16: 
Chris@16:     atomic<tagged_index> pool_;
Chris@16: };
Chris@16: 
Chris@16: template <typename T,
Chris@16:           typename Alloc,
Chris@16:           bool IsCompileTimeSized,
Chris@16:           bool IsFixedSize,
Chris@16:           std::size_t Capacity
Chris@16:           >
Chris@16: struct select_freelist
Chris@16: {
Chris@16:     typedef typename mpl::if_c<IsCompileTimeSized,
Chris@16:                                compiletime_sized_freelist_storage<T, Capacity>,
Chris@16:                                runtime_sized_freelist_storage<T, Alloc>
Chris@16:                               >::type fixed_sized_storage_type;
Chris@16: 
Chris@16:     typedef typename mpl::if_c<IsCompileTimeSized || IsFixedSize,
Chris@16:                                fixed_size_freelist<T, fixed_sized_storage_type>,
Chris@16:                                freelist_stack<T, Alloc>
Chris@16:                               >::type type;
Chris@16: };
Chris@16: 
Chris@16: template <typename T, bool IsNodeBased>
Chris@16: struct select_tagged_handle
Chris@16: {
Chris@16:     typedef typename mpl::if_c<IsNodeBased,
Chris@16:                                tagged_ptr<T>,
Chris@16:                                tagged_index
Chris@16:                               >::type tagged_handle_type;
Chris@16: 
Chris@16:     typedef typename mpl::if_c<IsNodeBased,
Chris@16:                                T*,
Chris@16:                                typename tagged_index::index_t
Chris@16:                               >::type handle_type;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: } /* namespace detail */
Chris@16: } /* namespace lockfree */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #if defined(_MSC_VER)
Chris@16: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: #endif /* BOOST_LOCKFREE_FREELIST_HPP_INCLUDED */