FIxed aux node operations in SplitListSet
authorkhizmax <libcds.dev@gmail.com>
Fri, 16 Sep 2016 21:32:04 +0000 (00:32 +0300)
committerkhizmax <libcds.dev@gmail.com>
Fri, 16 Sep 2016 21:32:04 +0000 (00:32 +0300)
Added stress tests  for FreeList

22 files changed:
cds/intrusive/details/base.h
cds/intrusive/details/split_list_base.h
cds/intrusive/free_list.h
cds/intrusive/free_list_cached.h [new file with mode: 0644]
cds/intrusive/free_list_selector.h
cds/intrusive/free_list_tagged.h
cds/intrusive/split_list.h
cds/intrusive/split_list_nogc.h
cds/intrusive/split_list_rcu.h
projects/Win/vc14/cds.sln
projects/Win/vc14/cds.vcxproj
projects/Win/vc14/cds.vcxproj.filters
projects/Win/vc14/stress-freelist.vcxproj [new file with mode: 0644]
projects/Win/vc14/stress-freelist.vcxproj.filters [new file with mode: 0644]
projects/Win/vc14/stress-stack.vcxproj.filters
test/stress/CMakeLists.txt
test/stress/data/test-debug.conf
test/stress/data/test-express.conf
test/stress/data/test.conf
test/stress/freelist/CMakeLists.txt [new file with mode: 0644]
test/stress/freelist/put_get.cpp [new file with mode: 0644]
test/stress/freelist/put_get_single.cpp [new file with mode: 0644]

index 03673dc..4e2b156 100644 (file)
@@ -320,6 +320,9 @@ namespace intrusive {
     /** @defgroup cds_intrusive_list List
         @ingroup cds_intrusive_containers
     */
+    /** @defgroup cds_intrusive_freelist Free-list
+        @ingroup cds_intrusive_containers
+    */
 
     //@cond
     template <typename List>
index fa36827..a10a50f 100644 (file)
@@ -306,25 +306,21 @@ namespace cds { namespace intrusive {
             //@endcond
 
         public:
-            typedef GC      gc;         ///< Garbage collector
-            typedef Node    node_type;  ///< Bucket node type
-            typedef atomics::atomic<node_type *> table_entry;  ///< Table entry type
+            typedef GC       gc;         ///< Garbage collector
+            typedef Node     node_type;  ///< Bucket node type
             typedef typename options::allocator allocator; ///< allocator
+            typedef typename options::memory_model  memory_model; ///< Memory model for atomic operations
+            typedef typename options::free_list free_list; ///< Free-list
 
-            /// Bucket table allocator
-            typedef cds::details::Allocator< table_entry, allocator > bucket_table_allocator;
-
-            /// Memory model for atomic operations
-            typedef typename options::memory_model  memory_model;
+            /// Auxiliary node type
+            struct aux_node_type: public node_type, public free_list::node
+            {};
 
-            /// Free-list
-            typedef typename options::free_list free_list;
+            typedef atomics::atomic<aux_node_type *> table_entry;  ///< Table entry type
+            typedef cds::details::Allocator< table_entry, allocator > bucket_table_allocator; ///< Bucket table allocator
 
         protected:
             //@cond
-            struct aux_node_type: public node_type, public free_list::node
-            {};
-
             const size_t   m_nLoadFactor; ///< load factor (average count of items per bucket)
             const size_t   m_nCapacity;   ///< Bucket table capacity
             table_entry *  m_Table;       ///< Bucket table
@@ -383,14 +379,14 @@ namespace cds { namespace intrusive {
             }
 
             /// Returns head node of bucket \p nBucket
-            node_type * bucket( size_t nBucket ) const
+            aux_node_type * bucket( size_t nBucket ) const
             {
                 assert( nBucket < capacity() );
                 return m_Table[ nBucket ].load(memory_model::memory_order_acquire);
             }
 
             /// Set \p pNode as a head of bucket \p nBucket
-            void bucket( size_t nBucket, node_type * pNode )
+            void bucket( size_t nBucket, aux_node_type * pNode )
             {
                 assert( nBucket < capacity() );
                 assert( bucket( nBucket ) == nullptr );
@@ -399,7 +395,7 @@ namespace cds { namespace intrusive {
             }
 
             /// Allocates auxiliary node; can return \p nullptr if the table exhausted
-            node_type* alloc_aux_node()
+            aux_node_type* alloc_aux_node()
             {
                 if ( m_nAuxNodeAllocated.load( memory_model::memory_order_relaxed ) < capacity() ) {
                     // alloc next free node from m_auxNode
@@ -418,7 +414,7 @@ namespace cds { namespace intrusive {
             }
 
             /// Places node type to free-list
-            void free_aux_node( node_type* p )
+            void free_aux_node( aux_node_type* p )
             {
                 m_freeList.put( static_cast<aux_node_type*>( p ));
             }
@@ -476,14 +472,15 @@ namespace cds { namespace intrusive {
             /// Free-list
             typedef typename options::free_list free_list;
 
-        protected:
-            //@cond
-            typedef atomics::atomic<node_type *>    table_entry;    ///< Table entry type
-            typedef atomics::atomic<table_entry *>  segment_type;   ///< Bucket table segment type
-
+            /// Auxiliary node type
             class aux_node_type: public node_type, public free_list::node
             {};
 
+        protected:
+            //@cond
+            typedef atomics::atomic<aux_node_type *> table_entry;    ///< Table entry type
+            typedef atomics::atomic<table_entry *>   segment_type;   ///< Bucket table segment type
+
             struct aux_node_segment {
                 atomics::atomic< size_t > aux_node_count; // how many aux nodes allocated from the segment
                 aux_node_segment*         next_segment;
@@ -568,7 +565,7 @@ namespace cds { namespace intrusive {
             }
 
             /// Returns head node of the bucket \p nBucket
-            node_type * bucket( size_t nBucket ) const
+            aux_node_type * bucket( size_t nBucket ) const
             {
                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
                 assert( nSegment < m_metrics.nSegmentCount );
@@ -580,7 +577,7 @@ namespace cds { namespace intrusive {
             }
 
             /// Set \p pNode as a head of bucket \p nBucket
-            void bucket( size_t nBucket, node_type * pNode )
+            void bucket( size_t nBucket, aux_node_type * pNode )
             {
                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
                 assert( nSegment < m_metrics.nSegmentCount );
@@ -597,7 +594,7 @@ namespace cds { namespace intrusive {
             }
 
             /// Allocates auxiliary node; can return \p nullptr if the table exhausted
-            node_type* alloc_aux_node()
+            aux_node_type* alloc_aux_node()
             {
                 for ( ;; ) {
                     aux_node_segment* aux_segment = m_auxNodeList.load( memory_model::memory_order_relaxed );
@@ -628,7 +625,7 @@ namespace cds { namespace intrusive {
             }
 
             /// Places auxiliary node type to free-list
-            void free_aux_node( node_type* p )
+            void free_aux_node( aux_node_type* p )
             {
                 m_freeList.put( static_cast<aux_node_type*>( p ));
             }
index 113610a..0ac727b 100644 (file)
@@ -36,7 +36,7 @@
 namespace cds { namespace intrusive {
 
     /// Lock-free free list
-    /** @ingroup cds_intrusive_helper
+    /** @ingroup cds_intrusive_freelist
 
         Free list is a helper class intended for reusing objects instead of freeing them completely; 
         this avoids the overhead of \p malloc(), and also avoids its worst-case behavior of taking an operating system lock.
diff --git a/cds/intrusive/free_list_cached.h b/cds/intrusive/free_list_cached.h
new file mode 100644 (file)
index 0000000..ef80887
--- /dev/null
@@ -0,0 +1,192 @@
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
+#define CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
+
+#include <cds/algo/atomic.h>
+#include <cds/opt/options.h>
+#include <cds/user_setup/cache_line.h>
+#include <cds/details/type_padding.h>
+
+#include <thread>
+#include <functional>
+
+namespace cds { namespace intrusive {
+
+    /// Cached free list
+    /** @ingroup cds_intrusive_freelist
+
+        The class that is a wrapper over other \p FreeList contains a small cache of free elements.
+        Before placing a new item into underlying \p FreeList the cached free-list tryes
+        to put that item into the cache if its corresponding slot is empty. The slot is calculated by
+        current thread id:
+        \code
+        int slot = std::hash<std::thread::id>()( std::this_thread::get_id() ) & (CacheSize - 1);
+        \endcode
+
+        When getting the free-list checks the corresponding cache slot. If it is not empty, its
+        contents is returned.
+
+        In some cases such simple algorithm significantly reduces \p FreeList contention.
+
+        Template parameters:
+        - \p FreeList - a free-list implementation: \p FreeList, \p TaggedFreeList
+        - \p CacheSize - size of cache, a small power-of-two number, default is 16
+        - \p Padding - padding of cache elements for solving false sharing, default is \p cds::c_nCacheLineSize
+    */
+    template <typename FreeList, size_t CacheSize = 16, unsigned Padding = cds::c_nCacheLineSize >
+    class CachedFreeList
+    {
+    public:
+        typedef FreeList free_list_type;    ///< Undelying free-list type
+        typedef typename free_list_type::node node; ///< Free-list node
+
+        static size_t const c_cache_size = CacheSize;   ///< Cache size
+        static unsigned const c_padding = Padding;      ///< Cache element padding
+
+        static_assert( c_cache_size >= 4, "Cache size is too small" );
+        static_assert( (c_cache_size & (c_cache_size - 1)) == 0, "CacheSize must be power of two" );
+        static_assert( (c_padding & (c_padding - 1)) == 0, "Padding must be power-of-two");
+
+    public:
+        /// Creates empty free list
+        CachedFreeList()
+        {
+            for ( auto& i: m_cache )
+                i.store( nullptr, atomics::memory_order_relaxed );
+        }
+
+        /// Destroys the free list. Free-list must be empty.
+        /**
+            @warning dtor does not free elements of the list.
+            To free elements you should manually call \p clear() with an appropriate disposer.
+        */
+        ~CachedFreeList()
+        {
+            assert( empty());
+        }
+
+        /// Puts \p pNode to the free list
+        void put( node* pNode )
+        {
+            // try to put into free cell of cache
+            node* expect = nullptr;
+            if ( m_cache[ get_hash() ].compare_exchange_weak( expect, pNode, atomics::memory_order_release, atomics::memory_order_relaxed ))
+                return;
+
+            // cache cell is not empty - use free-list
+            m_freeList.put( pNode );
+        }
+
+        /// Gets a node from the free list. If the list is empty, returns \p nullptr
+        node * get()
+        {
+            // try get from cache
+            atomics::atomic<node*>& cell = m_cache[ get_hash() ];
+            node* p = cell.load( atomics::memory_order_relaxed );
+            if ( p && cell.compare_exchange_weak( p, nullptr, atomics::memory_order_acquire, atomics::memory_order_relaxed ))
+                return p;
+
+            // try read from free-list
+            p = m_freeList.get();
+            if ( p )
+                return p;
+
+            // iterate the cache
+            for ( auto& cell : m_cache ) {
+                p = cell.load( atomics::memory_order_relaxed );
+                if ( p && cell.compare_exchange_weak( p, nullptr, atomics::memory_order_acquire, atomics::memory_order_relaxed ))
+                    return p;
+            }
+
+            return m_freeList.get();
+        }
+
+        /// Checks whether the free list is empty
+        bool empty() const
+        {
+            if ( !m_freeList.empty() )
+                return false;
+
+            for ( auto& cell : m_cache ) {
+                node* p = cell.load( atomics::memory_order_relaxed );
+                if ( p )
+                    return false;
+            }
+
+            return true;
+        }
+
+        /// Clears the free list (not atomic)
+        /**
+            For each element \p disp disposer is called to free memory.
+            The \p Disposer interface:
+            \code
+            struct disposer
+            {
+                void operator()( FreeList::node * node );
+            };
+            \endcode
+
+            This method must be explicitly called before the free list destructor.
+        */
+        template <typename Disposer>
+        void clear( Disposer disp )
+        {
+            m_freeList.clear( disp );
+            for ( auto& cell : m_cache ) {
+                node* p = cell.load( atomics::memory_order_relaxed );
+                if ( p ) {
+                    disp( p );
+                    cell.store( nullptr, atomics::memory_order_relaxed );
+                }
+            }
+        }
+
+    private:
+        //@cond
+        size_t get_hash()
+        {
+            return std::hash<std::thread::id>()( std::this_thread::get_id() ) & (c_cache_size - 1);
+        }
+        //@endcond
+    private:
+        //@cond
+        typedef typename cds::details::type_padding< atomics::atomic<node*>, c_padding >::type array_item;
+        array_item m_cache[ c_cache_size ];
+        free_list_type  m_freeList;
+        //@endcond
+    };
+
+}} // namespace cds::intrusive
+//@endcond
+
+#endif // CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
index d407b26..25297ba 100644 (file)
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_INTRUSIVE_FREE_LIST_SELECTOR_H
index ab71e8f..d8b9376 100644 (file)
@@ -36,7 +36,8 @@
 namespace cds { namespace intrusive {
 
     /// Lock-free free list based on tagged pointers (required double-width CAS)
-    /** @ingroup cds_intrusive_helper
+    /** @ingroup cds_intrusive_freelist
+
         This variant of \p FreeList is intended for processor architectures that support double-width CAS.
         It uses <a href="https://en.wikipedia.org/wiki/Tagged_pointer">tagged pointer</a> technique to solve ABA problem.
 
index 0025811..7f3892b 100644 (file)
@@ -258,7 +258,6 @@ namespace cds { namespace intrusive {
         //@cond
         typedef typename ordered_list::node_type    list_node_type;  ///< Node type as declared in ordered list
         typedef split_list::node<list_node_type>    node_type;       ///< split-list node type
-        typedef node_type                           aux_node_type;   ///< dummy node type
 
         /// Split-list node traits
         /**
@@ -271,11 +270,13 @@ namespace cds { namespace intrusive {
         typedef typename split_list::details::bucket_table_selector<
             traits::dynamic_bucket_table
             , gc
-            , aux_node_type
+            , node_type
             , opt::allocator< typename traits::allocator >
             , opt::memory_model< memory_model >
             , opt::free_list< typename traits::free_list >
         >::type bucket_table;
+
+        typedef typename bucket_table::aux_node_type aux_node_type;   ///< auxiliary node type
         //@endcond
 
     protected:
@@ -287,7 +288,7 @@ namespace cds { namespace intrusive {
             typedef typename base_class::auxiliary_head       bucket_head_type;
 
         public:
-            bool insert_at( aux_node_type * pHead, value_type& val )
+            bool insert_at( aux_node_type* pHead, value_type& val )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
index f4f146f..ef8acbe 100644 (file)
@@ -96,9 +96,9 @@ namespace cds { namespace intrusive {
             "cds::atomicity::empty_item_counter is not allowed as a item counter");
 
     protected:
+        //@cond
         typedef typename ordered_list::node_type  list_node_type;  ///< Node type as declared in ordered list
         typedef split_list::node<list_node_type>  node_type;       ///< split-list node type
-        typedef node_type                         aux_node_type; ///< dummy node type
 
         /// Split-list node traits
         /**
@@ -107,16 +107,17 @@ namespace cds { namespace intrusive {
         */
         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
 
-        //@cond
         /// Bucket table implementation
         typedef typename split_list::details::bucket_table_selector<
             traits::dynamic_bucket_table
             , gc
-            , aux_node_type
+            , node_type
             , opt::allocator< typename traits::allocator >
             , opt::memory_model< memory_model >
         >::type bucket_table;
 
+        typedef typename bucket_table::aux_node_type aux_node_type; ///< dummy node type
+
         typedef typename ordered_list::iterator list_iterator;
         typedef typename ordered_list::const_iterator list_const_iterator;
         //@endcond
@@ -704,10 +705,12 @@ namespace cds { namespace intrusive {
 
     protected:
         //@cond
-        typedef typename cds::details::type_padding< bucket_table, traits::padding >::type padded_bucket_table;
+        static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
+
+        typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
         padded_bucket_table     m_Buckets;          ///< bucket table
 
-        typedef typename cds::details::type_padding< ordered_list_wrapper, traits::padding>::type padded_ordered_list;
+        typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
         padded_ordered_list     m_List;             ///< Ordered list containing split-list items
 
         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
index 9791aa2..17df965 100644 (file)
@@ -132,9 +132,9 @@ namespace cds { namespace intrusive {
                         "cds::atomicity::empty_item_counter is not allowed as a item counter");
 
     protected:
+        //@cond
         typedef typename ordered_list::node_type    list_node_type;  ///< Node type as declared in ordered list
         typedef split_list::node<list_node_type>    node_type;       ///< split-list node type
-        typedef node_type                           aux_node_type; ///< dummy node type
 
         /// Split-list node traits
         /**
@@ -143,16 +143,17 @@ namespace cds { namespace intrusive {
         */
         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
 
-        //@cond
         /// Bucket table implementation
         typedef typename split_list::details::bucket_table_selector<
             traits::dynamic_bucket_table
             , gc
-            , aux_node_type
+            , node_type
             , opt::allocator< typename traits::allocator >
             , opt::memory_model< memory_model >
         >::type bucket_table;
 
+        typedef typename bucket_table::aux_node_type aux_node_type; ///< auxiliary node type
+
         //@endcond
 
     protected:
@@ -1090,10 +1091,12 @@ namespace cds { namespace intrusive {
 
     protected:
         //@cond
-        typedef typename cds::details::type_padding< bucket_table, traits::padding >::type padded_bucket_table;
+        static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
+
+        typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
         padded_bucket_table     m_Buckets;          ///< bucket table
 
-        typedef typename cds::details::type_padding< ordered_list_wrapper, traits::padding>::type padded_ordered_list;
+        typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
         padded_ordered_list     m_List;             ///< Ordered list containing split-list items
 
         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
index ace405a..decb0e1 100644 (file)
@@ -233,6 +233,12 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-set-iteration", "str
                {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239}\r
        EndProjectSection\r
 EndProject\r
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-freelist", "stress-freelist.vcxproj", "{79A6845E-85BF-4000-94FF-9DF2473460D4}"\r
+       ProjectSection(ProjectDependencies) = postProject\r
+               {A34CED07-A442-4FA1-81C4-F8B9CD3C832B} = {A34CED07-A442-4FA1-81C4-F8B9CD3C832B}\r
+               {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239}\r
+       EndProjectSection\r
+EndProject\r
 Global\r
        GlobalSection(SolutionConfigurationPlatforms) = preSolution\r
                Debug|Win32 = Debug|Win32\r
@@ -615,6 +621,18 @@ Global
                {31952FA8-A303-4A0B-94C4-ABA5A8A6DBCE}.Release|Win32.Build.0 = Release|Win32\r
                {31952FA8-A303-4A0B-94C4-ABA5A8A6DBCE}.Release|x64.ActiveCfg = Release|x64\r
                {31952FA8-A303-4A0B-94C4-ABA5A8A6DBCE}.Release|x64.Build.0 = Release|x64\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.Debug|Win32.ActiveCfg = Debug|Win32\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.Debug|Win32.Build.0 = Debug|Win32\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.Debug|x64.ActiveCfg = Debug|x64\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.Debug|x64.Build.0 = Debug|x64\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.DebugVLD|Win32.ActiveCfg = DebugVLD|Win32\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.DebugVLD|Win32.Build.0 = DebugVLD|Win32\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.DebugVLD|x64.ActiveCfg = DebugVLD|x64\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.DebugVLD|x64.Build.0 = DebugVLD|x64\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.Release|Win32.ActiveCfg = Release|Win32\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.Release|Win32.Build.0 = Release|Win32\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.Release|x64.ActiveCfg = Release|x64\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4}.Release|x64.Build.0 = Release|x64\r
        EndGlobalSection\r
        GlobalSection(SolutionProperties) = preSolution\r
                HideSolutionNode = FALSE\r
@@ -654,6 +672,7 @@ Global
                {1BB746AC-7856-4E59-9430-51177621DC35} = {7D3EE35B-185D-40B5-88C2-7F9933426978}\r
                {24DF3B87-387E-4EFC-BDE0-8DAD279FE19A} = {7D3EE35B-185D-40B5-88C2-7F9933426978}\r
                {31952FA8-A303-4A0B-94C4-ABA5A8A6DBCE} = {0D83E8C7-97D1-4BA1-928A-6846E7089652}\r
+               {79A6845E-85BF-4000-94FF-9DF2473460D4} = {10E1FAF2-904D-405E-8AB5-6878A1B03346}\r
        EndGlobalSection\r
        GlobalSection(DPCodeReviewSolutionGUID) = preSolution\r
                DPCodeReviewSolutionGUID = {00000000-0000-0000-0000-000000000000}\r
index acd0a6c..5b7e85c 100644 (file)
     <ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_hp.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_rcu.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\free_list.h" />\r
+    <ClInclude Include="..\..\..\cds\intrusive\free_list_cached.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\free_list_selector.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\free_list_tagged.h" />\r
     <ClInclude Include="..\..\..\cds\intrusive\impl\ellen_bintree.h" />\r
index e59bf01..14f3e2e 100644 (file)
     <Filter Include="Header Files\cds\intrusive">\r
       <UniqueIdentifier>{7226715d-6777-4c01-8e66-83b3885c00c1}</UniqueIdentifier>\r
     </Filter>\r
-    <Filter Include="Resource Files">\r
-      <UniqueIdentifier>{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}</UniqueIdentifier>\r
-      <Extensions>rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx</Extensions>\r
-    </Filter>\r
     <Filter Include="Header Files\cds\compiler\clang">\r
       <UniqueIdentifier>{ae97048d-bd62-4ff2-be28-3c84338e7186}</UniqueIdentifier>\r
     </Filter>\r
     <ClInclude Include="..\..\..\cds\intrusive\free_list_selector.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
+    <ClInclude Include="..\..\..\cds\intrusive\free_list_cached.h">\r
+      <Filter>Header Files\cds\intrusive</Filter>\r
+    </ClInclude>\r
   </ItemGroup>\r
 </Project>
\ No newline at end of file
diff --git a/projects/Win/vc14/stress-freelist.vcxproj b/projects/Win/vc14/stress-freelist.vcxproj
new file mode 100644 (file)
index 0000000..221700d
--- /dev/null
@@ -0,0 +1,239 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <ItemGroup Label="ProjectConfigurations">
+    <ProjectConfiguration Include="DebugVLD|Win32">
+      <Configuration>DebugVLD</Configuration>
+      <Platform>Win32</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="DebugVLD|x64">
+      <Configuration>DebugVLD</Configuration>
+      <Platform>x64</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Debug|Win32">
+      <Configuration>Debug</Configuration>
+      <Platform>Win32</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Release|Win32">
+      <Configuration>Release</Configuration>
+      <Platform>Win32</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Debug|x64">
+      <Configuration>Debug</Configuration>
+      <Platform>x64</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Release|x64">
+      <Configuration>Release</Configuration>
+      <Platform>x64</Platform>
+    </ProjectConfiguration>
+  </ItemGroup>
+  <ItemGroup>
+    <ClCompile Include="..\..\..\test\stress\freelist\put_get.cpp" />
+    <ClCompile Include="..\..\..\test\stress\freelist\put_get_single.cpp" />
+    <ClCompile Include="..\..\..\test\stress\main.cpp" />
+  </ItemGroup>
+  <PropertyGroup Label="Globals">
+    <ProjectGuid>{79A6845E-85BF-4000-94FF-9DF2473460D4}</ProjectGuid>
+    <Keyword>Win32Proj</Keyword>
+    <RootNamespace>stress_freelist</RootNamespace>
+    <WindowsTargetPlatformVersion>8.1</WindowsTargetPlatformVersion>
+    <ProjectName>stress-freelist</ProjectName>
+  </PropertyGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" />
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>false</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <WholeProgramOptimization>true</WholeProgramOptimization>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>false</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <WholeProgramOptimization>true</WholeProgramOptimization>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
+  <ImportGroup Label="ExtensionSettings">
+  </ImportGroup>
+  <ImportGroup Label="Shared">
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'" Label="PropertySheets">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'" Label="PropertySheets">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <PropertyGroup Label="UserMacros" />
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+    <LinkIncremental>true</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+    <TargetName>$(ProjectName)_d</TargetName>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">
+    <LinkIncremental>true</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+    <TargetName>$(ProjectName)_d</TargetName>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+    <LinkIncremental>true</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+    <TargetName>$(ProjectName)_d</TargetName>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'">
+    <LinkIncremental>true</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+    <TargetName>$(ProjectName)_d</TargetName>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+    <LinkIncremental>false</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+    <LinkIncremental>false</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+  </PropertyGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation>true</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation>true</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation>true</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation>true</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+    <ClCompile>
+      <WarningLevel>Level3</WarningLevel>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <Optimization>MaxSpeed</Optimization>
+      <FunctionLevelLinking>true</FunctionLevelLinking>
+      <IntrinsicFunctions>true</IntrinsicFunctions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <EnableCOMDATFolding>true</EnableCOMDATFolding>
+      <OptimizeReferences>true</OptimizeReferences>
+      <GenerateDebugInformation>true</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtest.lib;stress-framework.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+    <ClCompile>
+      <WarningLevel>Level3</WarningLevel>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <Optimization>MaxSpeed</Optimization>
+      <FunctionLevelLinking>true</FunctionLevelLinking>
+      <IntrinsicFunctions>true</IntrinsicFunctions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <EnableCOMDATFolding>true</EnableCOMDATFolding>
+      <OptimizeReferences>true</OptimizeReferences>
+      <GenerateDebugInformation>true</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtest.lib;stress-framework.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
+  <ImportGroup Label="ExtensionTargets">
+  </ImportGroup>
+</Project>
\ No newline at end of file
diff --git a/projects/Win/vc14/stress-freelist.vcxproj.filters b/projects/Win/vc14/stress-freelist.vcxproj.filters
new file mode 100644 (file)
index 0000000..d7e0247
--- /dev/null
@@ -0,0 +1,24 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <ItemGroup>
+    <Filter Include="Source Files">
+      <UniqueIdentifier>{4FC737F1-C7A5-4376-A066-2A32D752A2FF}</UniqueIdentifier>
+      <Extensions>cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx</Extensions>
+    </Filter>
+    <Filter Include="Header Files">
+      <UniqueIdentifier>{93995380-89BD-4b04-88EB-625FBE52EBFB}</UniqueIdentifier>
+      <Extensions>h;hh;hpp;hxx;hm;inl;inc;xsd</Extensions>
+    </Filter>
+  </ItemGroup>
+  <ItemGroup>
+    <ClCompile Include="..\..\..\test\stress\main.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
+    <ClCompile Include="..\..\..\test\stress\freelist\put_get.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
+    <ClCompile Include="..\..\..\test\stress\freelist\put_get_single.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
+  </ItemGroup>
+</Project>
\ No newline at end of file
index 9cae1e9..501850f 100644 (file)
@@ -9,10 +9,6 @@
       <UniqueIdentifier>{93995380-89BD-4b04-88EB-625FBE52EBFB}</UniqueIdentifier>\r
       <Extensions>h;hh;hpp;hxx;hm;inl;inc;xsd</Extensions>\r
     </Filter>\r
-    <Filter Include="Resource Files">\r
-      <UniqueIdentifier>{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}</UniqueIdentifier>\r
-      <Extensions>rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms</Extensions>\r
-    </Filter>\r
   </ItemGroup>\r
   <ItemGroup>\r
     <ClCompile Include="..\..\..\test\stress\main.cpp">\r
index 8801787..7aa703d 100644 (file)
@@ -21,6 +21,7 @@ include_directories(
     ${CMAKE_CURRENT_SOURCE_DIR}
 )
 
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/freelist)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/map)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/pqueue)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/queue)
@@ -29,6 +30,7 @@ add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/stack)
 
 add_custom_target( stress-all
     DEPENDS
+        stress-freelist
         stress-map
         stress-pqueue
         stress-queue
index c72fb21..961a650 100644 (file)
@@ -272,3 +272,7 @@ CuckooProbesetThreshold=0
 # *** FeldmanHashMap properties\r
 FeldmanMapHeadBits=8\r
 FeldmanMapArrayBits=4\r
+\r
+[free_list]\r
+ThreadCount=4\r
+PassCount=100000
\ No newline at end of file
index 0590d3f..1ec6aa1 100644 (file)
@@ -266,3 +266,7 @@ CuckooProbesetThreshold=0
 # *** FeldmanHashMap properties\r
 FeldmanMapHeadBits=8\r
 FeldmanMapArrayBits=4\r
+\r
+[free_list]\r
+ThreadCount=4\r
+PassCount=1000000
\ No newline at end of file
index e6ab618..565e448 100644 (file)
@@ -264,3 +264,7 @@ CuckooProbesetThreshold=0
 # *** FeldmanHashMap properties\r
 FeldmanMapHeadBits=10\r
 FeldmanMapArrayBits=4\r
+\r
+[free_list]\r
+ThreadCount=4\r
+PassCount=1000000
\ No newline at end of file
diff --git a/test/stress/freelist/CMakeLists.txt b/test/stress/freelist/CMakeLists.txt
new file mode 100644 (file)
index 0000000..32d549a
--- /dev/null
@@ -0,0 +1,22 @@
+set(PACKAGE_NAME stress-freelist)
+
+set(CDSSTRESS_FREELIST_SOURCES
+    ../main.cpp
+    put_get.cpp
+    put_get_single.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_FREELIST_SOURCES} $<TARGET_OBJECTS:${CDSSTRESS_FRAMEWORK_LIBRARY}>)
+target_link_libraries(${PACKAGE_NAME} 
+    ${CDS_SHARED_LIBRARY}
+    ${GTEST_LIBRARY}
+    ${Boost_THREAD_LIBRARY}
+    ${Boost_SYSTEM_LIBRARY}
+    ${CMAKE_THREAD_LIBS_INIT}
+)
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
\ No newline at end of file
diff --git a/test/stress/freelist/put_get.cpp b/test/stress/freelist/put_get.cpp
new file mode 100644 (file)
index 0000000..0859361
--- /dev/null
@@ -0,0 +1,183 @@
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#include <cds_test/stress_test.h>
+
+#include <cds/intrusive/free_list.h>
+#include <cds/intrusive/free_list_cached.h>
+#include <cds/intrusive/free_list_tagged.h>
+
+namespace {
+    class put_get: public cds_test::stress_fixture
+    {
+    protected:
+        static size_t s_nThreadCount;
+        static size_t s_nPassCount;
+        static size_t const c_nArraySize = 100;
+
+        template <typename FreeList >
+        struct value_type: public FreeList::node
+        {
+            size_t  counter;
+
+            value_type()
+                : counter(0) 
+            {}
+        };
+
+        template <class FreeList>
+        class Worker: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+        public:
+            FreeList&           m_FreeList;
+            size_t              m_nSuccess = 0;
+
+        public:
+            Worker( cds_test::thread_pool& pool, FreeList& s )
+                : base_class( pool )
+                , m_FreeList( s )
+            {}
+
+            Worker( Worker& src )
+                : base_class( src )
+                , m_FreeList( src.m_FreeList )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Worker( *this );
+            }
+
+            virtual void test()
+            {
+                typedef value_type<FreeList> item_type;
+                item_type* arr[ c_nArraySize ];
+
+                for ( size_t pass = 0; pass < s_nPassCount; ++pass ) {
+                    size_t n = 0;
+                    item_type* p;
+
+                    while ( (p = static_cast<item_type*>( m_FreeList.get())) != nullptr ) {
+                        p->counter++;
+                        arr[n] = p;
+                        ++m_nSuccess;
+                        ++n;
+                    }
+
+                    for ( size_t i = 0; i < n; ++i )
+                        m_FreeList.put( arr[i] );
+                }
+            }
+        };
+
+    public:
+        static void SetUpTestCase()
+        {
+            cds_test::config const& cfg = get_config( "free_list" );
+
+            s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
+            s_nPassCount = cfg.get_size_t( "PassCount", s_nPassCount );
+
+            if ( s_nThreadCount == 0 )
+                s_nThreadCount = 1;
+            if ( s_nPassCount == 0 )
+                s_nPassCount = 1000;
+        }
+        //static void TearDownTestCase();
+
+    protected:
+
+        template <typename FreeList>
+        void test( FreeList& list )
+        {
+            cds_test::thread_pool& pool = get_pool();
+
+            value_type<FreeList> arr[c_nArraySize];
+
+            for ( auto& i : arr )
+                list.put( &i );
+
+            pool.add( new Worker<FreeList>( pool, list ), s_nThreadCount );
+
+            propout() << std::make_pair( "work_thread", s_nThreadCount )
+                      << std::make_pair( "pass_count", s_nPassCount );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            // analyze result
+            size_t nTotal = 0;
+            for ( auto const& i : arr )
+                nTotal += i.counter;
+
+            size_t nSuccess = 0;
+            for ( size_t threadNo = 0; threadNo < pool.size(); ++threadNo )
+                nSuccess += static_cast<Worker<FreeList>&>( pool.get( threadNo )).m_nSuccess;
+
+            EXPECT_EQ( nSuccess, nTotal );
+
+            list.clear( []( typename FreeList::node* ) {} );
+        }
+    };
+
+    size_t put_get::s_nThreadCount = 4;
+    size_t put_get::s_nPassCount = 100000;
+
+#define CDSSTRESS_FREELIST_F( name, freelist_type ) \
+    TEST_F( put_get, name ) \
+    { \
+        freelist_type fl; \
+        test( fl ); \
+    }
+
+    CDSSTRESS_FREELIST_F( FreeList, cds::intrusive::FreeList )
+
+    typedef cds::intrusive::CachedFreeList<cds::intrusive::FreeList> cached_free_list;
+    CDSSTRESS_FREELIST_F( CachedFreeList, cached_free_list )
+
+    TEST_F( put_get, TaggetFreeList )
+    {
+        struct tagged_ptr {
+            void* p;
+            uintptr_t tag;
+        };
+
+        atomics::atomic<tagged_ptr> tp;
+        if ( tp.is_lock_free() ) {
+            cds::intrusive::TaggedFreeList fl;
+            test( fl );
+        }
+        else
+            std::cout << "Double-width CAS is not supported\n";
+    }
+
+} // namespace
diff --git a/test/stress/freelist/put_get_single.cpp b/test/stress/freelist/put_get_single.cpp
new file mode 100644 (file)
index 0000000..c7d3335
--- /dev/null
@@ -0,0 +1,163 @@
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#include <cds_test/stress_test.h>
+
+#include <cds/intrusive/free_list.h>
+#include <cds/intrusive/free_list_cached.h>
+#include <cds/intrusive/free_list_tagged.h>
+
+namespace {
+    class put_get_single: public cds_test::stress_fixture
+    {
+    protected:
+        static size_t s_nThreadCount;
+        static size_t s_nPassCount;
+
+        template <typename FreeList >
+        struct value_type: public FreeList::node
+        {
+            size_t  counter;
+
+            value_type()
+                : counter(0) 
+            {}
+        };
+
+        template <class FreeList>
+        class Worker: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+        public:
+            FreeList&           m_FreeList;
+            size_t              m_nSuccess = 0;
+
+        public:
+            Worker( cds_test::thread_pool& pool, FreeList& s )
+                : base_class( pool )
+                , m_FreeList( s )
+            {}
+
+            Worker( Worker& src )
+                : base_class( src )
+                , m_FreeList( src.m_FreeList )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Worker( *this );
+            }
+
+            virtual void test()
+            {
+                typedef value_type<FreeList> item_type;
+
+                for ( size_t pass = 0; pass < s_nPassCount; ++pass ) {
+                    item_type* p;
+                    while ( (p = static_cast<item_type*>( m_FreeList.get())) == nullptr );
+                    p->counter++;
+                    m_FreeList.put( p );
+                }
+            }
+        };
+
+    public:
+        static void SetUpTestCase()
+        {
+            cds_test::config const& cfg = get_config( "free_list" );
+
+            s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
+            s_nPassCount = cfg.get_size_t( "PassCount", s_nPassCount );
+
+            if ( s_nThreadCount == 0 )
+                s_nThreadCount = 1;
+            if ( s_nPassCount == 0 )
+                s_nPassCount = 1000;
+        }
+        //static void TearDownTestCase();
+
+    protected:
+
+        template <typename FreeList>
+        void test( FreeList& list )
+        {
+            cds_test::thread_pool& pool = get_pool();
+
+            value_type<FreeList> item;;
+            list.put( &item );
+
+            pool.add( new Worker<FreeList>( pool, list ), s_nThreadCount );
+
+            propout() << std::make_pair( "work_thread", s_nThreadCount )
+                      << std::make_pair( "pass_count", s_nPassCount );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            // analyze result
+            EXPECT_EQ( item.counter, s_nPassCount * s_nThreadCount );
+
+            list.clear( []( typename FreeList::node* ) {} );
+        }
+    };
+
+    size_t put_get_single::s_nThreadCount = 4;
+    size_t put_get_single::s_nPassCount = 100000;
+
+#define CDSSTRESS_FREELIST_F( name, freelist_type ) \
+    TEST_F( put_get_single, name ) \
+    { \
+        freelist_type fl; \
+        test( fl ); \
+    }
+
+    CDSSTRESS_FREELIST_F( FreeList, cds::intrusive::FreeList )
+
+    typedef cds::intrusive::CachedFreeList<cds::intrusive::FreeList> cached_free_list;
+    CDSSTRESS_FREELIST_F( CachedFreeList, cached_free_list )
+
+    TEST_F( put_get_single, TaggetFreeList )
+    {
+        struct tagged_ptr {
+            void* p;
+            uintptr_t tag;
+        };
+
+        atomics::atomic<tagged_ptr> tp;
+        if ( tp.is_lock_free() ) {
+            cds::intrusive::TaggedFreeList fl;
+            test( fl );
+        }
+        else
+            std::cout << "Double-width CAS is not supported\n";
+    }
+
+} // namespace