2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
32 #define CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
34 #include <cds/algo/atomic.h>
35 #include <cds/opt/options.h>
36 #include <cds/user_setup/cache_line.h>
37 #include <cds/details/type_padding.h>
42 namespace cds { namespace intrusive {
45 /** @ingroup cds_intrusive_freelist
47 The class that is a wrapper over other \p FreeList contains a small cache of free elements.
48 Before placing a new item into underlying \p FreeList the cached free-list tryes
49 to put that item into the cache if its corresponding slot is empty. The slot is calculated by
52 int slot = std::hash<std::thread::id>()( std::this_thread::get_id()) & (CacheSize - 1);
55 When getting the free-list checks the corresponding cache slot. If it is not empty, its
58 In some cases such simple algorithm significantly reduces \p FreeList contention.
61 - \p FreeList - a free-list implementation: \p FreeList, \p TaggedFreeList
62 - \p CacheSize - size of cache, a small power-of-two number, default is 16
63 - \p Padding - padding of cache elements for solving false sharing, default is \p cds::c_nCacheLineSize
65 template <typename FreeList, size_t CacheSize = 16, unsigned Padding = cds::c_nCacheLineSize >
69 typedef FreeList free_list_type; ///< Undelying free-list type
70 typedef typename free_list_type::node node; ///< Free-list node
72 static size_t const c_cache_size = CacheSize; ///< Cache size
73 static unsigned const c_padding = Padding; ///< Cache element padding
75 static_assert( c_cache_size >= 4, "Cache size is too small" );
76 static_assert( (c_cache_size & (c_cache_size - 1)) == 0, "CacheSize must be power of two" );
77 static_assert( (c_padding & (c_padding - 1)) == 0, "Padding must be power-of-two");
80 /// Creates empty free list
83 for ( auto& i: m_cache )
84 i.store( nullptr, atomics::memory_order_relaxed );
87 /// Destroys the free list. Free-list must be empty.
89 @warning dtor does not free elements of the list.
90 To free elements you should manually call \p clear() with an appropriate disposer.
97 /// Puts \p pNode to the free list
98 void put( node* pNode )
100 // try to put into free cell of cache
101 node* expect = nullptr;
102 if ( m_cache[ get_hash() ].compare_exchange_weak( expect, pNode, atomics::memory_order_release, atomics::memory_order_relaxed ))
105 // cache cell is not empty - use free-list
106 m_freeList.put( pNode );
109 /// Gets a node from the free list. If the list is empty, returns \p nullptr
112 // try get from cache
113 atomics::atomic<node*>& cell = m_cache[ get_hash() ];
114 node* p = cell.load( atomics::memory_order_relaxed );
115 if ( p && cell.compare_exchange_weak( p, nullptr, atomics::memory_order_acquire, atomics::memory_order_relaxed ))
118 // try read from free-list
119 p = m_freeList.get();
124 for ( auto& item : m_cache ) {
125 p = item.load( atomics::memory_order_relaxed );
126 if ( p && item.compare_exchange_weak( p, nullptr, atomics::memory_order_acquire, atomics::memory_order_relaxed ))
130 return m_freeList.get();
133 /// Checks whether the free list is empty
136 if ( !m_freeList.empty())
139 for ( auto& cell : m_cache ) {
140 node* p = cell.load( atomics::memory_order_relaxed );
148 /// Clears the free list (not atomic)
150 For each element \p disp disposer is called to free memory.
151 The \p Disposer interface:
155 void operator()( FreeList::node * node );
159 This method must be explicitly called before the free list destructor.
161 template <typename Disposer>
162 void clear( Disposer disp )
164 m_freeList.clear( disp );
165 for ( auto& cell : m_cache ) {
166 node* p = cell.load( atomics::memory_order_relaxed );
169 cell.store( nullptr, atomics::memory_order_relaxed );
178 return std::hash<std::thread::id>()( std::this_thread::get_id()) & (c_cache_size - 1);
183 typedef typename cds::details::type_padding< atomics::atomic<node*>, c_padding >::type array_item;
184 array_item m_cache[ c_cache_size ];
185 free_list_type m_freeList;
189 }} // namespace cds::intrusive
192 #endif // CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H