summaryrefslogtreecommitdiffstats
path: root/src/boost/libs/lockfree
diff options
context:
space:
mode:
Diffstat (limited to 'src/boost/libs/lockfree')
-rw-r--r--src/boost/libs/lockfree/examples/Jamfile.v213
-rw-r--r--src/boost/libs/lockfree/examples/queue.cpp69
-rw-r--r--src/boost/libs/lockfree/examples/spsc_queue.cpp62
-rw-r--r--src/boost/libs/lockfree/examples/stack.cpp70
-rw-r--r--src/boost/libs/lockfree/index.html13
-rw-r--r--src/boost/libs/lockfree/meta/libraries.json14
-rw-r--r--src/boost/libs/lockfree/test/Jamfile.v244
-rw-r--r--src/boost/libs/lockfree/test/freelist_test.cpp233
-rw-r--r--src/boost/libs/lockfree/test/queue_bounded_stress_test.cpp27
-rw-r--r--src/boost/libs/lockfree/test/queue_fixedsize_stress_test.cpp28
-rw-r--r--src/boost/libs/lockfree/test/queue_interprocess_test.cpp57
-rw-r--r--src/boost/libs/lockfree/test/queue_test.cpp194
-rw-r--r--src/boost/libs/lockfree/test/queue_unbounded_stress_test.cpp27
-rw-r--r--src/boost/libs/lockfree/test/spsc_queue_stress_test.cpp222
-rw-r--r--src/boost/libs/lockfree/test/spsc_queue_test.cpp407
-rw-r--r--src/boost/libs/lockfree/test/stack_bounded_stress_test.cpp27
-rw-r--r--src/boost/libs/lockfree/test/stack_fixedsize_stress_test.cpp28
-rw-r--r--src/boost/libs/lockfree/test/stack_interprocess_test.cpp57
-rw-r--r--src/boost/libs/lockfree/test/stack_test.cpp219
-rw-r--r--src/boost/libs/lockfree/test/stack_unbounded_stress_test.cpp28
-rw-r--r--src/boost/libs/lockfree/test/tagged_ptr_test.cpp58
-rw-r--r--src/boost/libs/lockfree/test/test_common.hpp145
-rw-r--r--src/boost/libs/lockfree/test/test_helpers.hpp110
23 files changed, 2152 insertions, 0 deletions
diff --git a/src/boost/libs/lockfree/examples/Jamfile.v2 b/src/boost/libs/lockfree/examples/Jamfile.v2
new file mode 100644
index 000000000..1868a4d23
--- /dev/null
+++ b/src/boost/libs/lockfree/examples/Jamfile.v2
@@ -0,0 +1,13 @@
+# (C) Copyright 2009: Tim Blechmann
+# Distributed under the Boost Software License, Version 1.0.
+# (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+project boost/lockfree/example
+ : requirements
+ <library>../../thread/build//boost_thread/
+ <library>../../atomic/build//boost_atomic
+ ;
+
+exe queue : queue.cpp ;
+exe stack : stack.cpp ;
+exe spsc_queue : spsc_queue.cpp ;
diff --git a/src/boost/libs/lockfree/examples/queue.cpp b/src/boost/libs/lockfree/examples/queue.cpp
new file mode 100644
index 000000000..9e599dbba
--- /dev/null
+++ b/src/boost/libs/lockfree/examples/queue.cpp
@@ -0,0 +1,69 @@
+// Copyright (C) 2009 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+//[queue_example
+#include <boost/thread/thread.hpp>
+#include <boost/lockfree/queue.hpp>
+#include <iostream>
+
+#include <boost/atomic.hpp>
+
+boost::atomic_int producer_count(0);
+boost::atomic_int consumer_count(0);
+
+boost::lockfree::queue<int> queue(128);
+
+const int iterations = 10000000;
+const int producer_thread_count = 4;
+const int consumer_thread_count = 4;
+
+void producer(void)
+{
+ for (int i = 0; i != iterations; ++i) {
+ int value = ++producer_count;
+ while (!queue.push(value))
+ ;
+ }
+}
+
+boost::atomic<bool> done (false);
+void consumer(void)
+{
+ int value;
+ while (!done) {
+ while (queue.pop(value))
+ ++consumer_count;
+ }
+
+ while (queue.pop(value))
+ ++consumer_count;
+}
+
+int main(int argc, char* argv[])
+{
+ using namespace std;
+ cout << "boost::lockfree::queue is ";
+ if (!queue.is_lock_free())
+ cout << "not ";
+ cout << "lockfree" << endl;
+
+ boost::thread_group producer_threads, consumer_threads;
+
+ for (int i = 0; i != producer_thread_count; ++i)
+ producer_threads.create_thread(producer);
+
+ for (int i = 0; i != consumer_thread_count; ++i)
+ consumer_threads.create_thread(consumer);
+
+ producer_threads.join_all();
+ done = true;
+
+ consumer_threads.join_all();
+
+ cout << "produced " << producer_count << " objects." << endl;
+ cout << "consumed " << consumer_count << " objects." << endl;
+}
+//]
diff --git a/src/boost/libs/lockfree/examples/spsc_queue.cpp b/src/boost/libs/lockfree/examples/spsc_queue.cpp
new file mode 100644
index 000000000..6c6adc172
--- /dev/null
+++ b/src/boost/libs/lockfree/examples/spsc_queue.cpp
@@ -0,0 +1,62 @@
+// Copyright (C) 2009 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+//[spsc_queue_example
+#include <boost/thread/thread.hpp>
+#include <boost/lockfree/spsc_queue.hpp>
+#include <iostream>
+
+#include <boost/atomic.hpp>
+
+int producer_count = 0;
+boost::atomic_int consumer_count (0);
+
+boost::lockfree::spsc_queue<int, boost::lockfree::capacity<1024> > spsc_queue;
+
+const int iterations = 10000000;
+
+void producer(void)
+{
+ for (int i = 0; i != iterations; ++i) {
+ int value = ++producer_count;
+ while (!spsc_queue.push(value))
+ ;
+ }
+}
+
+boost::atomic<bool> done (false);
+
+void consumer(void)
+{
+ int value;
+ while (!done) {
+ while (spsc_queue.pop(value))
+ ++consumer_count;
+ }
+
+ while (spsc_queue.pop(value))
+ ++consumer_count;
+}
+
+int main(int argc, char* argv[])
+{
+ using namespace std;
+ cout << "boost::lockfree::queue is ";
+ if (!spsc_queue.is_lock_free())
+ cout << "not ";
+ cout << "lockfree" << endl;
+
+ boost::thread producer_thread(producer);
+ boost::thread consumer_thread(consumer);
+
+ producer_thread.join();
+ done = true;
+ consumer_thread.join();
+
+ cout << "produced " << producer_count << " objects." << endl;
+ cout << "consumed " << consumer_count << " objects." << endl;
+}
+//]
diff --git a/src/boost/libs/lockfree/examples/stack.cpp b/src/boost/libs/lockfree/examples/stack.cpp
new file mode 100644
index 000000000..ba1230269
--- /dev/null
+++ b/src/boost/libs/lockfree/examples/stack.cpp
@@ -0,0 +1,70 @@
+// Copyright (C) 2009 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+//[stack_example
+#include <boost/thread/thread.hpp>
+#include <boost/lockfree/stack.hpp>
+#include <iostream>
+
+#include <boost/atomic.hpp>
+
+boost::atomic_int producer_count(0);
+boost::atomic_int consumer_count(0);
+
+boost::lockfree::stack<int> stack(128);
+
+const int iterations = 1000000;
+const int producer_thread_count = 4;
+const int consumer_thread_count = 4;
+
+void producer(void)
+{
+ for (int i = 0; i != iterations; ++i) {
+ int value = ++producer_count;
+ while (!stack.push(value))
+ ;
+ }
+}
+
+boost::atomic<bool> done (false);
+
+void consumer(void)
+{
+ int value;
+ while (!done) {
+ while (stack.pop(value))
+ ++consumer_count;
+ }
+
+ while (stack.pop(value))
+ ++consumer_count;
+}
+
+int main(int argc, char* argv[])
+{
+ using namespace std;
+ cout << "boost::lockfree::stack is ";
+ if (!stack.is_lock_free())
+ cout << "not ";
+ cout << "lockfree" << endl;
+
+ boost::thread_group producer_threads, consumer_threads;
+
+ for (int i = 0; i != producer_thread_count; ++i)
+ producer_threads.create_thread(producer);
+
+ for (int i = 0; i != consumer_thread_count; ++i)
+ consumer_threads.create_thread(consumer);
+
+ producer_threads.join_all();
+ done = true;
+
+ consumer_threads.join_all();
+
+ cout << "produced " << producer_count << " objects." << endl;
+ cout << "consumed " << consumer_count << " objects." << endl;
+}
+//]
diff --git a/src/boost/libs/lockfree/index.html b/src/boost/libs/lockfree/index.html
new file mode 100644
index 000000000..ccee53f70
--- /dev/null
+++ b/src/boost/libs/lockfree/index.html
@@ -0,0 +1,13 @@
+<html>
+<head>
+<meta http-equiv="refresh" content="0; URL=../../doc/html/lockfree.html">
+</head>
+<body>
+Automatic redirection failed, please go to
+<a href="../../doc/html/lockfree.html">../../doc/html/lockfree.html</a> &nbsp;<hr>
+<p>&copy; Copyright Beman Dawes, 2001</p>
+<p>Distributed under the Boost Software License, Version 1.0. (See accompanying
+file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy
+at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</p>
+</body>
+</html>
diff --git a/src/boost/libs/lockfree/meta/libraries.json b/src/boost/libs/lockfree/meta/libraries.json
new file mode 100644
index 000000000..fb65281d2
--- /dev/null
+++ b/src/boost/libs/lockfree/meta/libraries.json
@@ -0,0 +1,14 @@
+{
+ "key": "lockfree",
+ "name": "Lockfree",
+ "authors": [
+ "Tim Blechmann"
+ ],
+ "description": "Lockfree data structures.",
+ "category": [
+ "Concurrent"
+ ],
+ "maintainers": [
+ "Tim Blechmann <tim -at- klingt.org>"
+ ]
+}
diff --git a/src/boost/libs/lockfree/test/Jamfile.v2 b/src/boost/libs/lockfree/test/Jamfile.v2
new file mode 100644
index 000000000..8ce4189c3
--- /dev/null
+++ b/src/boost/libs/lockfree/test/Jamfile.v2
@@ -0,0 +1,44 @@
+# (C) Copyright 2010: Tim Blechmann
+# Distributed under the Boost Software License, Version 1.0.
+# (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+import testing ;
+
+lib boost_chrono ;
+lib boost_interprocess ;
+lib boost_system ;
+lib boost_thread ;
+lib boost_unit_test_framework ;
+
+project
+ : source-location .
+ : requirements
+ <library>../../test/build//boost_unit_test_framework
+ <library>../../atomic/build//boost_atomic
+ ;
+
+
+rule test_all
+{
+ local all_rules = ;
+
+ for local fileb in [ glob *.cpp ]
+ {
+ all_rules += [ run $(fileb)
+ : # additional args
+ : # test-files
+ : # requirements
+ <toolset>acc:<linkflags>-lrt
+ <toolset>acc-pa_risc:<linkflags>-lrt
+ <target-os>windows,<toolset>gcc:<linkflags>"-lole32 -loleaut32 -lpsapi -ladvapi32"
+ <host-os>hpux,<toolset>gcc:<linkflags>"-Wl,+as,mpas"
+ <library>../../thread/build//boost_thread/
+ <threading>multi
+ <link>static
+ ] ;
+ }
+
+ return $(all_rules) ;
+}
+
+test-suite lockfree : [ test_all r ] : <threading>multi ;
diff --git a/src/boost/libs/lockfree/test/freelist_test.cpp b/src/boost/libs/lockfree/test/freelist_test.cpp
new file mode 100644
index 000000000..4eb9c5c4d
--- /dev/null
+++ b/src/boost/libs/lockfree/test/freelist_test.cpp
@@ -0,0 +1,233 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// enables error checks via dummy::~dtor
+#define BOOST_LOCKFREE_FREELIST_INIT_RUNS_DTOR
+
+#include <boost/lockfree/detail/freelist.hpp>
+#include <boost/lockfree/queue.hpp>
+
+#include <boost/foreach.hpp>
+#include <boost/thread.hpp>
+#include <boost/scoped_ptr.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include <set>
+
+#include "test_helpers.hpp"
+
+using boost::lockfree::detail::atomic;
+
+atomic<bool> test_running(false);
+
+struct dummy
+{
+ dummy(void)
+ {
+ if (test_running.load(boost::lockfree::detail::memory_order_relaxed))
+ assert(allocated == 0);
+ allocated = 1;
+ }
+
+ ~dummy(void)
+ {
+ if (test_running.load(boost::lockfree::detail::memory_order_relaxed))
+ assert(allocated == 1);
+ allocated = 0;
+ }
+
+ size_t padding[2]; // for used for the freelist node
+ int allocated;
+};
+
+template <typename freelist_type,
+ bool threadsafe,
+ bool bounded>
+void run_test(void)
+{
+ freelist_type fl(std::allocator<int>(), 8);
+
+ std::set<dummy*> nodes;
+
+ dummy d;
+ if (bounded)
+ test_running.store(true);
+
+ for (int i = 0; i != 4; ++i) {
+ dummy * allocated = fl.template construct<threadsafe, bounded>();
+ BOOST_REQUIRE(nodes.find(allocated) == nodes.end());
+ nodes.insert(allocated);
+ }
+
+ BOOST_FOREACH(dummy * d, nodes)
+ fl.template destruct<threadsafe>(d);
+
+ nodes.clear();
+ for (int i = 0; i != 4; ++i)
+ nodes.insert(fl.template construct<threadsafe, bounded>());
+
+ BOOST_FOREACH(dummy * d, nodes)
+ fl.template destruct<threadsafe>(d);
+
+ for (int i = 0; i != 4; ++i)
+ nodes.insert(fl.template construct<threadsafe, bounded>());
+
+ if (bounded)
+ test_running.store(false);
+}
+
+template <bool bounded>
+void run_tests(void)
+{
+ run_test<boost::lockfree::detail::freelist_stack<dummy>, true, bounded>();
+ run_test<boost::lockfree::detail::freelist_stack<dummy>, false, bounded>();
+ run_test<boost::lockfree::detail::fixed_size_freelist<dummy>, true, bounded>();
+}
+
+BOOST_AUTO_TEST_CASE( freelist_tests )
+{
+ run_tests<false>();
+ run_tests<true>();
+}
+
+template <typename freelist_type, bool threadsafe>
+void oom_test(void)
+{
+ const bool bounded = true;
+ freelist_type fl(std::allocator<int>(), 8);
+
+ for (int i = 0; i != 8; ++i)
+ fl.template construct<threadsafe, bounded>();
+
+ dummy * allocated = fl.template construct<threadsafe, bounded>();
+ BOOST_REQUIRE(allocated == NULL);
+}
+
+BOOST_AUTO_TEST_CASE( oom_tests )
+{
+ oom_test<boost::lockfree::detail::freelist_stack<dummy>, true >();
+ oom_test<boost::lockfree::detail::freelist_stack<dummy>, false >();
+ oom_test<boost::lockfree::detail::fixed_size_freelist<dummy>, true >();
+ oom_test<boost::lockfree::detail::fixed_size_freelist<dummy>, false >();
+}
+
+
+template <typename freelist_type, bool bounded>
+struct freelist_tester
+{
+ static const int size = 128;
+ static const int thread_count = 4;
+#ifndef BOOST_LOCKFREE_STRESS_TEST
+ static const int operations_per_thread = 1000;
+#else
+ static const int operations_per_thread = 100000;
+#endif
+
+ freelist_type fl;
+ boost::lockfree::queue<dummy*> allocated_nodes;
+
+ atomic<bool> running;
+ static_hashed_set<dummy*, 1<<16 > working_set;
+
+
+ freelist_tester(void):
+ fl(std::allocator<int>(), size), allocated_nodes(256)
+ {}
+
+ void run()
+ {
+ running = true;
+
+ if (bounded)
+ test_running.store(true);
+ boost::thread_group alloc_threads;
+ boost::thread_group dealloc_threads;
+
+ for (int i = 0; i != thread_count; ++i)
+ dealloc_threads.create_thread(boost::bind(&freelist_tester::deallocate, this));
+
+ for (int i = 0; i != thread_count; ++i)
+ alloc_threads.create_thread(boost::bind(&freelist_tester::allocate, this));
+ alloc_threads.join_all();
+ test_running.store(false);
+ running = false;
+ dealloc_threads.join_all();
+ }
+
+ void allocate(void)
+ {
+ for (long i = 0; i != operations_per_thread; ++i) {
+ for (;;) {
+ dummy * node = fl.template construct<true, bounded>();
+ if (node) {
+ bool success = working_set.insert(node);
+ assert(success);
+ allocated_nodes.push(node);
+ break;
+ }
+ }
+ }
+ }
+
+ void deallocate(void)
+ {
+ for (;;) {
+ dummy * node;
+ if (allocated_nodes.pop(node)) {
+ bool success = working_set.erase(node);
+ assert(success);
+ fl.template destruct<true>(node);
+ }
+
+ if (running.load() == false)
+ break;
+
+#ifdef __VXWORKS__
+ boost::thread::yield();
+#endif
+ }
+
+ dummy * node;
+ while (allocated_nodes.pop(node)) {
+ bool success = working_set.erase(node);
+ assert(success);
+ fl.template destruct<true>(node);
+ }
+ }
+};
+
+template <typename Tester>
+void run_tester()
+{
+ boost::scoped_ptr<Tester> tester (new Tester);
+ tester->run();
+}
+
+
+BOOST_AUTO_TEST_CASE( unbounded_freelist_test )
+{
+ typedef freelist_tester<boost::lockfree::detail::freelist_stack<dummy>, false > test_type;
+ run_tester<test_type>();
+}
+
+
+BOOST_AUTO_TEST_CASE( bounded_freelist_test )
+{
+ typedef freelist_tester<boost::lockfree::detail::freelist_stack<dummy>, true > test_type;
+ run_tester<test_type>();
+}
+
+BOOST_AUTO_TEST_CASE( fixed_size_freelist_test )
+{
+ typedef freelist_tester<boost::lockfree::detail::fixed_size_freelist<dummy>, true > test_type;
+ run_tester<test_type>();
+}
diff --git a/src/boost/libs/lockfree/test/queue_bounded_stress_test.cpp b/src/boost/libs/lockfree/test/queue_bounded_stress_test.cpp
new file mode 100644
index 000000000..aa882ce1f
--- /dev/null
+++ b/src/boost/libs/lockfree/test/queue_bounded_stress_test.cpp
@@ -0,0 +1,27 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/queue.hpp>
+
+#include <boost/scoped_ptr.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include "test_common.hpp"
+
+BOOST_AUTO_TEST_CASE( queue_test_bounded )
+{
+ typedef queue_stress_tester<true> tester_type;
+ boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) );
+
+ boost::lockfree::queue<long> q(128);
+ tester->run(q);
+}
diff --git a/src/boost/libs/lockfree/test/queue_fixedsize_stress_test.cpp b/src/boost/libs/lockfree/test/queue_fixedsize_stress_test.cpp
new file mode 100644
index 000000000..8ae46f275
--- /dev/null
+++ b/src/boost/libs/lockfree/test/queue_fixedsize_stress_test.cpp
@@ -0,0 +1,28 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/queue.hpp>
+
+#include <boost/scoped_ptr.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include "test_common.hpp"
+
+
+BOOST_AUTO_TEST_CASE( queue_test_fixed_size )
+{
+ typedef queue_stress_tester<> tester_type;
+ boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) );
+
+ boost::lockfree::queue<long, boost::lockfree::capacity<8> > q;
+ tester->run(q);
+}
diff --git a/src/boost/libs/lockfree/test/queue_interprocess_test.cpp b/src/boost/libs/lockfree/test/queue_interprocess_test.cpp
new file mode 100644
index 000000000..78c0ce9fc
--- /dev/null
+++ b/src/boost/libs/lockfree/test/queue_interprocess_test.cpp
@@ -0,0 +1,57 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <cstdlib> //std::system
+#include <sstream>
+
+#include <boost/interprocess/managed_shared_memory.hpp>
+#include <boost/lockfree/queue.hpp>
+#include <boost/thread/thread.hpp>
+
+using namespace boost::interprocess;
+typedef allocator<int, managed_shared_memory::segment_manager> ShmemAllocator;
+typedef boost::lockfree::queue<int,
+ boost::lockfree::allocator<ShmemAllocator>,
+ boost::lockfree::capacity<2048>
+ > queue;
+
+int main (int argc, char *argv[])
+{
+ if(argc == 1){
+ struct shm_remove
+ {
+ shm_remove() { shared_memory_object::remove("boost_queue_interprocess_test_shm"); }
+ ~shm_remove(){ shared_memory_object::remove("boost_queue_interprocess_test_shm"); }
+ } remover;
+
+ managed_shared_memory segment(create_only, "boost_queue_interprocess_test_shm", 262144);
+ ShmemAllocator alloc_inst (segment.get_segment_manager());
+
+ queue * q = segment.construct<queue>("queue")(alloc_inst);
+ for (int i = 0; i != 1024; ++i)
+ q->push(i);
+
+ std::string s(argv[0]); s += " child ";
+ if(0 != std::system(s.c_str()))
+ return 1;
+
+ while (!q->empty())
+ boost::thread::yield();
+ return 0;
+ } else {
+ managed_shared_memory segment(open_only, "boost_queue_interprocess_test_shm");
+ queue * q = segment.find<queue>("queue").first;
+
+ int from_queue;
+ for (int i = 0; i != 1024; ++i) {
+ bool success = q->pop(from_queue);
+ assert (success);
+ assert (from_queue == i);
+ }
+ segment.destroy<queue>("queue");
+ }
+ return 0;
+}
diff --git a/src/boost/libs/lockfree/test/queue_test.cpp b/src/boost/libs/lockfree/test/queue_test.cpp
new file mode 100644
index 000000000..79f6f0ed2
--- /dev/null
+++ b/src/boost/libs/lockfree/test/queue_test.cpp
@@ -0,0 +1,194 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/lockfree_forward.hpp>
+
+#include <boost/lockfree/queue.hpp>
+#include <boost/thread.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include <memory>
+
+#include "test_helpers.hpp"
+
+using namespace boost;
+using namespace boost::lockfree;
+using namespace std;
+
+BOOST_AUTO_TEST_CASE( simple_queue_test )
+{
+ queue<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+
+ BOOST_REQUIRE(f.empty());
+ f.push(1);
+ f.push(2);
+
+ int i1(0), i2(0);
+
+ BOOST_REQUIRE(f.pop(i1));
+ BOOST_REQUIRE_EQUAL(i1, 1);
+
+ BOOST_REQUIRE(f.pop(i2));
+ BOOST_REQUIRE_EQUAL(i2, 2);
+ BOOST_REQUIRE(f.empty());
+}
+
+BOOST_AUTO_TEST_CASE( simple_queue_test_capacity )
+{
+ queue<int, capacity<64> > f;
+
+ BOOST_WARN(f.is_lock_free());
+
+ BOOST_REQUIRE(f.empty());
+ f.push(1);
+ f.push(2);
+
+ int i1(0), i2(0);
+
+ BOOST_REQUIRE(f.pop(i1));
+ BOOST_REQUIRE_EQUAL(i1, 1);
+
+ BOOST_REQUIRE(f.pop(i2));
+ BOOST_REQUIRE_EQUAL(i2, 2);
+ BOOST_REQUIRE(f.empty());
+}
+
+
+BOOST_AUTO_TEST_CASE( unsafe_queue_test )
+{
+ queue<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ int i1(0), i2(0);
+
+ f.unsynchronized_push(1);
+ f.unsynchronized_push(2);
+
+ BOOST_REQUIRE(f.unsynchronized_pop(i1));
+ BOOST_REQUIRE_EQUAL(i1, 1);
+
+ BOOST_REQUIRE(f.unsynchronized_pop(i2));
+ BOOST_REQUIRE_EQUAL(i2, 2);
+ BOOST_REQUIRE(f.empty());
+}
+
+
+BOOST_AUTO_TEST_CASE( queue_consume_one_test )
+{
+ queue<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ f.push(1);
+ f.push(2);
+
+#ifdef BOOST_NO_CXX11_LAMBDAS
+ bool success1 = f.consume_one(test_equal(1));
+ bool success2 = f.consume_one(test_equal(2));
+#else
+ bool success1 = f.consume_one([] (int i) {
+ BOOST_REQUIRE_EQUAL(i, 1);
+ });
+
+ bool success2 = f.consume_one([] (int i) {
+ BOOST_REQUIRE_EQUAL(i, 2);
+ });
+#endif
+
+ BOOST_REQUIRE(success1);
+ BOOST_REQUIRE(success2);
+
+ BOOST_REQUIRE(f.empty());
+}
+
+BOOST_AUTO_TEST_CASE( queue_consume_all_test )
+{
+ queue<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ f.push(1);
+ f.push(2);
+
+#ifdef BOOST_NO_CXX11_LAMBDAS
+ size_t consumed = f.consume_all(dummy_functor());
+#else
+ size_t consumed = f.consume_all([] (int i) {
+ });
+#endif
+
+ BOOST_REQUIRE_EQUAL(consumed, 2u);
+
+ BOOST_REQUIRE(f.empty());
+}
+
+
+BOOST_AUTO_TEST_CASE( queue_convert_pop_test )
+{
+ queue<int*> f(128);
+ BOOST_REQUIRE(f.empty());
+ f.push(new int(1));
+ f.push(new int(2));
+ f.push(new int(3));
+ f.push(new int(4));
+
+ {
+ int * i1;
+
+ BOOST_REQUIRE(f.pop(i1));
+ BOOST_REQUIRE_EQUAL(*i1, 1);
+ delete i1;
+ }
+
+
+ {
+ boost::shared_ptr<int> i2;
+ BOOST_REQUIRE(f.pop(i2));
+ BOOST_REQUIRE_EQUAL(*i2, 2);
+ }
+
+ {
+#ifdef BOOST_NO_AUTO_PTR
+ unique_ptr<int> i3;
+#else
+ auto_ptr<int> i3;
+#endif
+ BOOST_REQUIRE(f.pop(i3));
+
+ BOOST_REQUIRE_EQUAL(*i3, 3);
+ }
+
+ {
+ boost::shared_ptr<int> i4;
+ BOOST_REQUIRE(f.pop(i4));
+
+ BOOST_REQUIRE_EQUAL(*i4, 4);
+ }
+
+
+ BOOST_REQUIRE(f.empty());
+}
+
+BOOST_AUTO_TEST_CASE( reserve_test )
+{
+ typedef boost::lockfree::queue< void* > memory_queue;
+
+ memory_queue ms(1);
+ ms.reserve(1);
+ ms.reserve_unsafe(1);
+}
diff --git a/src/boost/libs/lockfree/test/queue_unbounded_stress_test.cpp b/src/boost/libs/lockfree/test/queue_unbounded_stress_test.cpp
new file mode 100644
index 000000000..10b70e2ba
--- /dev/null
+++ b/src/boost/libs/lockfree/test/queue_unbounded_stress_test.cpp
@@ -0,0 +1,27 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/queue.hpp>
+
+#include <boost/scoped_ptr.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include "test_common.hpp"
+
+BOOST_AUTO_TEST_CASE( queue_test_unbounded )
+{
+ typedef queue_stress_tester<false> tester_type;
+ boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) );
+
+ boost::lockfree::queue<long> q(128);
+ tester->run(q);
+}
diff --git a/src/boost/libs/lockfree/test/spsc_queue_stress_test.cpp b/src/boost/libs/lockfree/test/spsc_queue_stress_test.cpp
new file mode 100644
index 000000000..a63afd0e5
--- /dev/null
+++ b/src/boost/libs/lockfree/test/spsc_queue_stress_test.cpp
@@ -0,0 +1,222 @@
+// Copyright (C) 2011-2013 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/spsc_queue.hpp>
+#include <boost/thread.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include <iostream>
+#include <memory>
+
+#include "test_helpers.hpp"
+#include "test_common.hpp"
+
+using namespace boost;
+using namespace boost::lockfree;
+using namespace std;
+
+#ifndef BOOST_LOCKFREE_STRESS_TEST
+static const boost::uint32_t nodes_per_thread = 100000;
+#else
+static const boost::uint32_t nodes_per_thread = 100000000;
+#endif
+
+struct spsc_queue_tester
+{
+ spsc_queue<int, capacity<128> > sf;
+
+ boost::lockfree::detail::atomic<long> spsc_queue_cnt, received_nodes;
+
+// In VxWorks one RTP just supports 65535 objects
+#ifndef __VXWORKS__
+ static_hashed_set<int, 1<<16 > working_set;
+#else
+ static_hashed_set<int, 1<<15 > working_set;
+#endif
+
+ spsc_queue_tester(void):
+ spsc_queue_cnt(0), received_nodes(0)
+ {}
+
+ void add(void)
+ {
+ for (boost::uint32_t i = 0; i != nodes_per_thread; ++i) {
+ int id = generate_id<int>();
+ working_set.insert(id);
+
+ while (sf.push(id) == false)
+ {}
+
+ ++spsc_queue_cnt;
+ }
+ running = false;
+ }
+
+ bool get_element(void)
+ {
+ int data;
+ bool success = sf.pop(data);
+
+ if (success) {
+ ++received_nodes;
+ --spsc_queue_cnt;
+ bool erased = working_set.erase(data);
+ assert(erased);
+ return true;
+ } else
+ return false;
+ }
+
+ boost::lockfree::detail::atomic<bool> running;
+
+ void get(void)
+ {
+ for(;;) {
+ bool success = get_element();
+ if (!running && !success)
+ break;
+ }
+
+ while ( get_element() );
+ }
+
+ void run(void)
+ {
+ running = true;
+
+ BOOST_REQUIRE(sf.empty());
+
+ boost::thread reader(boost::bind(&spsc_queue_tester::get, this));
+ boost::thread writer(boost::bind(&spsc_queue_tester::add, this));
+ cout << "reader and writer threads created" << endl;
+
+ writer.join();
+ cout << "writer threads joined. waiting for readers to finish" << endl;
+
+ reader.join();
+
+ BOOST_REQUIRE_EQUAL(received_nodes, nodes_per_thread);
+ BOOST_REQUIRE_EQUAL(spsc_queue_cnt, 0);
+ BOOST_REQUIRE(sf.empty());
+ BOOST_REQUIRE(working_set.count_nodes() == 0);
+ }
+};
+
+BOOST_AUTO_TEST_CASE( spsc_queue_test_caching )
+{
+ boost::shared_ptr<spsc_queue_tester> test1(new spsc_queue_tester);
+ test1->run();
+}
+
+struct spsc_queue_tester_buffering
+{
+ spsc_queue<int, capacity<128> > sf;
+
+ boost::lockfree::detail::atomic<long> spsc_queue_cnt;
+
+// In VxWorks one RTP just supports 65535 objects
+#ifndef __VXWORKS__
+ static_hashed_set<int, 1<<16 > working_set;
+#else
+ static_hashed_set<int, 1<<15 > working_set;
+#endif
+
+ boost::lockfree::detail::atomic<size_t> received_nodes;
+
+ spsc_queue_tester_buffering(void):
+ spsc_queue_cnt(0), received_nodes(0)
+ {}
+
+ static const size_t buf_size = 5;
+
+ void add(void)
+ {
+ boost::array<int, buf_size> input_buffer;
+ for (boost::uint32_t i = 0; i != nodes_per_thread; i+=buf_size) {
+ for (size_t i = 0; i != buf_size; ++i) {
+ int id = generate_id<int>();
+ working_set.insert(id);
+ input_buffer[i] = id;
+ }
+
+ size_t pushed = 0;
+
+ do {
+ pushed += sf.push(input_buffer.c_array() + pushed,
+ input_buffer.size() - pushed);
+ } while (pushed != buf_size);
+
+ spsc_queue_cnt+=buf_size;
+ }
+ running = false;
+ }
+
+ bool get_elements(void)
+ {
+ boost::array<int, buf_size> output_buffer;
+
+ size_t popd = sf.pop(output_buffer.c_array(), output_buffer.size());
+
+ if (popd) {
+ received_nodes += popd;
+ spsc_queue_cnt -= popd;
+
+ for (size_t i = 0; i != popd; ++i) {
+ bool erased = working_set.erase(output_buffer[i]);
+ assert(erased);
+ }
+
+ return true;
+ } else
+ return false;
+ }
+
+ boost::lockfree::detail::atomic<bool> running;
+
+ void get(void)
+ {
+ for(;;) {
+ bool success = get_elements();
+ if (!running && !success)
+ break;
+ }
+
+ while ( get_elements() );
+ }
+
+ void run(void)
+ {
+ running = true;
+
+ boost::thread reader(boost::bind(&spsc_queue_tester_buffering::get, this));
+ boost::thread writer(boost::bind(&spsc_queue_tester_buffering::add, this));
+ cout << "reader and writer threads created" << endl;
+
+ writer.join();
+ cout << "writer threads joined. waiting for readers to finish" << endl;
+
+ reader.join();
+
+ BOOST_REQUIRE_EQUAL(received_nodes, nodes_per_thread);
+ BOOST_REQUIRE_EQUAL(spsc_queue_cnt, 0);
+ BOOST_REQUIRE(sf.empty());
+ BOOST_REQUIRE(working_set.count_nodes() == 0);
+ }
+};
+
+
+BOOST_AUTO_TEST_CASE( spsc_queue_test_buffering )
+{
+ boost::shared_ptr<spsc_queue_tester_buffering> test1(new spsc_queue_tester_buffering);
+ test1->run();
+}
+
diff --git a/src/boost/libs/lockfree/test/spsc_queue_test.cpp b/src/boost/libs/lockfree/test/spsc_queue_test.cpp
new file mode 100644
index 000000000..99f393f05
--- /dev/null
+++ b/src/boost/libs/lockfree/test/spsc_queue_test.cpp
@@ -0,0 +1,407 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/spsc_queue.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include <iostream>
+#include <memory>
+
+#include "test_helpers.hpp"
+#include "test_common.hpp"
+
+using namespace boost;
+using namespace boost::lockfree;
+using namespace std;
+
+BOOST_AUTO_TEST_CASE( simple_spsc_queue_test )
+{
+ spsc_queue<int, capacity<64> > f;
+
+ BOOST_REQUIRE(f.empty());
+ f.push(1);
+ f.push(2);
+
+ int i1(0), i2(0);
+
+ BOOST_REQUIRE(f.pop(i1));
+ BOOST_REQUIRE_EQUAL(i1, 1);
+
+ BOOST_REQUIRE(f.pop(i2));
+ BOOST_REQUIRE_EQUAL(i2, 2);
+ BOOST_REQUIRE(f.empty());
+}
+
+BOOST_AUTO_TEST_CASE( simple_spsc_queue_test_compile_time_size )
+{
+ spsc_queue<int> f(64);
+
+ BOOST_REQUIRE(f.empty());
+ f.push(1);
+ f.push(2);
+
+ int i1(0), i2(0);
+
+ BOOST_REQUIRE(f.pop(i1));
+ BOOST_REQUIRE_EQUAL(i1, 1);
+
+ BOOST_REQUIRE(f.pop(i2));
+ BOOST_REQUIRE_EQUAL(i2, 2);
+ BOOST_REQUIRE(f.empty());
+}
+
+BOOST_AUTO_TEST_CASE( ranged_push_test )
+{
+ spsc_queue<int> stk(64);
+
+ int data[2] = {1, 2};
+
+ BOOST_REQUIRE_EQUAL(stk.push(data, data + 2), data + 2);
+
+ int out;
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1);
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2);
+ BOOST_REQUIRE(!stk.pop(out));
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_consume_one_test )
+{
+ spsc_queue<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ f.push(1);
+ f.push(2);
+
+#ifdef BOOST_NO_CXX11_LAMBDAS
+ bool success1 = f.consume_one(test_equal(1));
+ bool success2 = f.consume_one(test_equal(2));
+#else
+ bool success1 = f.consume_one([] (int i) {
+ BOOST_REQUIRE_EQUAL(i, 1);
+ });
+
+ bool success2 = f.consume_one([] (int i) {
+ BOOST_REQUIRE_EQUAL(i, 2);
+ });
+#endif
+
+ BOOST_REQUIRE(success1);
+ BOOST_REQUIRE(success2);
+
+ BOOST_REQUIRE(f.empty());
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_consume_all_test )
+{
+ spsc_queue<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ f.push(1);
+ f.push(2);
+
+#ifdef BOOST_NO_CXX11_LAMBDAS
+ size_t consumed = f.consume_all(dummy_functor());
+#else
+ size_t consumed = f.consume_all([] (int i) {
+ });
+#endif
+
+ BOOST_REQUIRE_EQUAL(consumed, 2u);
+
+ BOOST_REQUIRE(f.empty());
+}
+
+enum {
+ pointer_and_size,
+ reference_to_array,
+ iterator_pair,
+ output_iterator_
+};
+
+BOOST_AUTO_TEST_CASE( spsc_queue_capacity_test )
+{
+ spsc_queue<int, capacity<2> > f;
+
+ BOOST_REQUIRE(f.push(1));
+ BOOST_REQUIRE(f.push(2));
+ BOOST_REQUIRE(!f.push(3));
+
+ spsc_queue<int> g(2);
+
+ BOOST_REQUIRE(g.push(1));
+ BOOST_REQUIRE(g.push(2));
+ BOOST_REQUIRE(!g.push(3));
+}
+
+template <typename QueueType>
+void spsc_queue_avail_test_run(QueueType & q)
+{
+ BOOST_REQUIRE_EQUAL( q.write_available(), 16 );
+ BOOST_REQUIRE_EQUAL( q.read_available(), 0 );
+
+ for (size_t i = 0; i != 8; ++i) {
+ BOOST_REQUIRE_EQUAL( q.write_available(), 16 - i );
+ BOOST_REQUIRE_EQUAL( q.read_available(), i );
+
+ q.push( 1 );
+ }
+
+ // empty queue
+ int dummy;
+ while (q.pop(dummy))
+ {}
+
+ for (size_t i = 0; i != 16; ++i) {
+ BOOST_REQUIRE_EQUAL( q.write_available(), 16 - i );
+ BOOST_REQUIRE_EQUAL( q.read_available(), i );
+
+ q.push( 1 );
+ }
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_avail_test )
+{
+ spsc_queue<int, capacity<16> > f;
+ spsc_queue_avail_test_run(f);
+
+ spsc_queue<int> g(16);
+ spsc_queue_avail_test_run(g);
+}
+
+
+template <int EnqueueMode>
+void spsc_queue_buffer_push_return_value(void)
+{
+ const size_t xqueue_size = 64;
+ const size_t buffer_size = 100;
+ spsc_queue<int, capacity<100> > rb;
+
+ int data[xqueue_size];
+ for (size_t i = 0; i != xqueue_size; ++i)
+ data[i] = (int)i*2;
+
+ switch (EnqueueMode) {
+ case pointer_and_size:
+ BOOST_REQUIRE_EQUAL(rb.push(data, xqueue_size), xqueue_size);
+ break;
+
+ case reference_to_array:
+ BOOST_REQUIRE_EQUAL(rb.push(data), xqueue_size);
+ break;
+
+ case iterator_pair:
+ BOOST_REQUIRE_EQUAL(rb.push(data, data + xqueue_size), data + xqueue_size);
+ break;
+
+ default:
+ assert(false);
+ }
+
+ switch (EnqueueMode) {
+ case pointer_and_size:
+ BOOST_REQUIRE_EQUAL(rb.push(data, xqueue_size), buffer_size - xqueue_size);
+ break;
+
+ case reference_to_array:
+ BOOST_REQUIRE_EQUAL(rb.push(data), buffer_size - xqueue_size);
+ break;
+
+ case iterator_pair:
+ BOOST_REQUIRE_EQUAL(rb.push(data, data + xqueue_size), data + buffer_size - xqueue_size);
+ break;
+
+ default:
+ assert(false);
+ }
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_buffer_push_return_value_test )
+{
+ spsc_queue_buffer_push_return_value<pointer_and_size>();
+ spsc_queue_buffer_push_return_value<reference_to_array>();
+ spsc_queue_buffer_push_return_value<iterator_pair>();
+}
+
+template <int EnqueueMode,
+ int ElementCount,
+ int BufferSize,
+ int NumberOfIterations
+ >
+void spsc_queue_buffer_push(void)
+{
+ const size_t xqueue_size = ElementCount;
+ spsc_queue<int, capacity<BufferSize> > rb;
+
+ int data[xqueue_size];
+ for (size_t i = 0; i != xqueue_size; ++i)
+ data[i] = (int)i*2;
+
+ std::vector<int> vdata(data, data + xqueue_size);
+
+ for (int i = 0; i != NumberOfIterations; ++i) {
+ BOOST_REQUIRE(rb.empty());
+ switch (EnqueueMode) {
+ case pointer_and_size:
+ BOOST_REQUIRE_EQUAL(rb.push(data, xqueue_size), xqueue_size);
+ break;
+
+ case reference_to_array:
+ BOOST_REQUIRE_EQUAL(rb.push(data), xqueue_size);
+ break;
+
+ case iterator_pair:
+ BOOST_REQUIRE_EQUAL(rb.push(data, data + xqueue_size), data + xqueue_size);
+ break;
+
+ default:
+ assert(false);
+ }
+
+ int out[xqueue_size];
+ BOOST_REQUIRE_EQUAL(rb.pop(out, xqueue_size), xqueue_size);
+ for (size_t i = 0; i != xqueue_size; ++i)
+ BOOST_REQUIRE_EQUAL(data[i], out[i]);
+ }
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_buffer_push_test )
+{
+ spsc_queue_buffer_push<pointer_and_size, 7, 16, 64>();
+ spsc_queue_buffer_push<reference_to_array, 7, 16, 64>();
+ spsc_queue_buffer_push<iterator_pair, 7, 16, 64>();
+}
+
+template <int EnqueueMode,
+ int ElementCount,
+ int BufferSize,
+ int NumberOfIterations
+ >
+void spsc_queue_buffer_pop(void)
+{
+ const size_t xqueue_size = ElementCount;
+ spsc_queue<int, capacity<BufferSize> > rb;
+
+ int data[xqueue_size];
+ for (size_t i = 0; i != xqueue_size; ++i)
+ data[i] = (int)i*2;
+
+ std::vector<int> vdata(data, data + xqueue_size);
+
+ for (int i = 0; i != NumberOfIterations; ++i) {
+ BOOST_REQUIRE(rb.empty());
+ BOOST_REQUIRE_EQUAL(rb.push(data), xqueue_size);
+
+ int out[xqueue_size];
+ vector<int> vout;
+
+ switch (EnqueueMode) {
+ case pointer_and_size:
+ BOOST_REQUIRE_EQUAL(rb.pop(out, xqueue_size), xqueue_size);
+ break;
+
+ case reference_to_array:
+ BOOST_REQUIRE_EQUAL(rb.pop(out), xqueue_size);
+ break;
+
+ case output_iterator_:
+ BOOST_REQUIRE_EQUAL(rb.pop(std::back_inserter(vout)), xqueue_size);
+ break;
+
+ default:
+ assert(false);
+ }
+
+ if (EnqueueMode == output_iterator_) {
+ BOOST_REQUIRE_EQUAL(vout.size(), xqueue_size);
+ for (size_t i = 0; i != xqueue_size; ++i)
+ BOOST_REQUIRE_EQUAL(data[i], vout[i]);
+ } else {
+ for (size_t i = 0; i != xqueue_size; ++i)
+ BOOST_REQUIRE_EQUAL(data[i], out[i]);
+ }
+ }
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_buffer_pop_test )
+{
+ spsc_queue_buffer_pop<pointer_and_size, 7, 16, 64>();
+ spsc_queue_buffer_pop<reference_to_array, 7, 16, 64>();
+ spsc_queue_buffer_pop<output_iterator_, 7, 16, 64>();
+}
+
+// Test front() and pop()
+template < typename Queue >
+void spsc_queue_front_pop(Queue& queue)
+{
+ queue.push(1);
+ queue.push(2);
+ queue.push(3);
+
+ // front as ref and const ref
+ int& rfront = queue.front();
+ const int& crfront = queue.front();
+
+ BOOST_REQUIRE_EQUAL(1, rfront);
+ BOOST_REQUIRE_EQUAL(1, crfront);
+
+ int front = 0;
+
+ // access element pushed first
+ front = queue.front();
+ BOOST_REQUIRE_EQUAL(1, front);
+
+ // front is still the same
+ front = queue.front();
+ BOOST_REQUIRE_EQUAL(1, front);
+
+ queue.pop();
+
+ front = queue.front();
+ BOOST_REQUIRE_EQUAL(2, front);
+
+ queue.pop(); // pop 2
+
+ bool pop_ret = queue.pop(); // pop 3
+ BOOST_REQUIRE(pop_ret);
+
+ pop_ret = queue.pop(); // pop on empty queue
+ BOOST_REQUIRE( ! pop_ret);
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_buffer_front_and_pop_runtime_sized_test )
+{
+ spsc_queue<int, capacity<64> > queue;
+ spsc_queue_front_pop(queue);
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_buffer_front_and_pop_compiletime_sized_test )
+{
+ spsc_queue<int> queue(64);
+ spsc_queue_front_pop(queue);
+}
+
+BOOST_AUTO_TEST_CASE( spsc_queue_reset_test )
+{
+ spsc_queue<int, capacity<64> > f;
+
+ BOOST_REQUIRE(f.empty());
+ f.push(1);
+ f.push(2);
+
+ f.reset();
+
+ BOOST_REQUIRE(f.empty());
+}
diff --git a/src/boost/libs/lockfree/test/stack_bounded_stress_test.cpp b/src/boost/libs/lockfree/test/stack_bounded_stress_test.cpp
new file mode 100644
index 000000000..55d097fba
--- /dev/null
+++ b/src/boost/libs/lockfree/test/stack_bounded_stress_test.cpp
@@ -0,0 +1,27 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/stack.hpp>
+
+#include <boost/scoped_ptr.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include "test_common.hpp"
+
+BOOST_AUTO_TEST_CASE( stack_test_bounded )
+{
+ typedef queue_stress_tester<true> tester_type;
+ boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) );
+
+ boost::lockfree::stack<long> q(128);
+ tester->run(q);
+}
diff --git a/src/boost/libs/lockfree/test/stack_fixedsize_stress_test.cpp b/src/boost/libs/lockfree/test/stack_fixedsize_stress_test.cpp
new file mode 100644
index 000000000..688af3081
--- /dev/null
+++ b/src/boost/libs/lockfree/test/stack_fixedsize_stress_test.cpp
@@ -0,0 +1,28 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/stack.hpp>
+
+#include <boost/scoped_ptr.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include "test_common.hpp"
+
+
+BOOST_AUTO_TEST_CASE( stack_test_fixed_size )
+{
+ typedef queue_stress_tester<> tester_type;
+ boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) );
+
+ boost::lockfree::stack<long, boost::lockfree::capacity<8> > q;
+ tester->run(q);
+}
diff --git a/src/boost/libs/lockfree/test/stack_interprocess_test.cpp b/src/boost/libs/lockfree/test/stack_interprocess_test.cpp
new file mode 100644
index 000000000..1a60e63f4
--- /dev/null
+++ b/src/boost/libs/lockfree/test/stack_interprocess_test.cpp
@@ -0,0 +1,57 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <cstdlib> //std::system
+#include <sstream>
+
+#include <boost/interprocess/managed_shared_memory.hpp>
+#include <boost/lockfree/stack.hpp>
+#include <boost/thread/thread.hpp>
+
+using namespace boost::interprocess;
+typedef allocator<int, managed_shared_memory::segment_manager> ShmemAllocator;
+typedef boost::lockfree::stack<int,
+ boost::lockfree::allocator<ShmemAllocator>,
+ boost::lockfree::capacity<2048>
+ > stack;
+
+int main (int argc, char *argv[])
+{
+ if(argc == 1){
+ struct shm_remove
+ {
+ shm_remove() { shared_memory_object::remove("MySharedMemory"); }
+ ~shm_remove(){ shared_memory_object::remove("MySharedMemory"); }
+ } remover;
+
+ managed_shared_memory segment(create_only, "MySharedMemory", 65536);
+ ShmemAllocator alloc_inst (segment.get_segment_manager());
+
+ stack * queue = segment.construct<stack>("stack")(alloc_inst);
+ for (int i = 0; i != 1024; ++i)
+ queue->push(i);
+
+ std::string s(argv[0]); s += " child ";
+ if(0 != std::system(s.c_str()))
+ return 1;
+
+ while (!queue->empty())
+ boost::thread::yield();
+ return 0;
+ } else {
+ managed_shared_memory segment(open_only, "MySharedMemory");
+ stack * queue = segment.find<stack>("stack").first;
+
+ int from_queue;
+ for (int i = 0; i != 1024; ++i) {
+ bool success = queue->pop(from_queue);
+ assert (success);
+ assert (from_queue == 1023 - i);
+ }
+ segment.destroy<stack>("stack");
+ }
+ return 0;
+}
diff --git a/src/boost/libs/lockfree/test/stack_test.cpp b/src/boost/libs/lockfree/test/stack_test.cpp
new file mode 100644
index 000000000..303222b67
--- /dev/null
+++ b/src/boost/libs/lockfree/test/stack_test.cpp
@@ -0,0 +1,219 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+
+#include <boost/thread.hpp>
+#include <boost/lockfree/stack.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include "test_helpers.hpp"
+
+BOOST_AUTO_TEST_CASE( simple_stack_test )
+{
+ boost::lockfree::stack<long> stk(128);
+
+ stk.push(1);
+ stk.push(2);
+ long out;
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2);
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1);
+ BOOST_REQUIRE(!stk.pop(out));
+}
+
+BOOST_AUTO_TEST_CASE( unsafe_stack_test )
+{
+ boost::lockfree::stack<long> stk(128);
+
+ stk.unsynchronized_push(1);
+ stk.unsynchronized_push(2);
+ long out;
+ BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 2);
+ BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 1);
+ BOOST_REQUIRE(!stk.unsynchronized_pop(out));
+}
+
+BOOST_AUTO_TEST_CASE( ranged_push_test )
+{
+ boost::lockfree::stack<long> stk(128);
+
+ long data[2] = {1, 2};
+
+ BOOST_REQUIRE_EQUAL(stk.push(data, data + 2), data + 2);
+
+ long out;
+ BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 2);
+ BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 1);
+ BOOST_REQUIRE(!stk.unsynchronized_pop(out));
+}
+
+BOOST_AUTO_TEST_CASE( ranged_unsynchronized_push_test )
+{
+ boost::lockfree::stack<long> stk(128);
+
+ long data[2] = {1, 2};
+
+ BOOST_REQUIRE_EQUAL(stk.unsynchronized_push(data, data + 2), data + 2);
+
+ long out;
+ BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 2);
+ BOOST_REQUIRE(stk.unsynchronized_pop(out)); BOOST_REQUIRE_EQUAL(out, 1);
+ BOOST_REQUIRE(!stk.unsynchronized_pop(out));
+}
+
+BOOST_AUTO_TEST_CASE( fixed_size_stack_test )
+{
+ boost::lockfree::stack<long, boost::lockfree::capacity<128> > stk;
+
+ stk.push(1);
+ stk.push(2);
+ long out;
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2);
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1);
+ BOOST_REQUIRE(!stk.pop(out));
+ BOOST_REQUIRE(stk.empty());
+}
+
+BOOST_AUTO_TEST_CASE( fixed_size_stack_test_exhausted )
+{
+ boost::lockfree::stack<long, boost::lockfree::capacity<2> > stk;
+
+ stk.push(1);
+ stk.push(2);
+ BOOST_REQUIRE(!stk.push(3));
+ long out;
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2);
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1);
+ BOOST_REQUIRE(!stk.pop(out));
+ BOOST_REQUIRE(stk.empty());
+}
+
+BOOST_AUTO_TEST_CASE( bounded_stack_test_exhausted )
+{
+ boost::lockfree::stack<long> stk(2);
+
+ stk.bounded_push(1);
+ stk.bounded_push(2);
+ BOOST_REQUIRE(!stk.bounded_push(3));
+ long out;
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 2);
+ BOOST_REQUIRE(stk.pop(out)); BOOST_REQUIRE_EQUAL(out, 1);
+ BOOST_REQUIRE(!stk.pop(out));
+ BOOST_REQUIRE(stk.empty());
+}
+
+BOOST_AUTO_TEST_CASE( stack_consume_one_test )
+{
+ boost::lockfree::stack<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ f.push(1);
+ f.push(2);
+
+#ifdef BOOST_NO_CXX11_LAMBDAS
+ bool success1 = f.consume_one(test_equal(2));
+ bool success2 = f.consume_one(test_equal(1));
+#else
+ bool success1 = f.consume_one([] (int i) {
+ BOOST_REQUIRE_EQUAL(i, 2);
+ });
+
+ bool success2 = f.consume_one([] (int i) {
+ BOOST_REQUIRE_EQUAL(i, 1);
+ });
+#endif
+
+ BOOST_REQUIRE(success1);
+ BOOST_REQUIRE(success2);
+
+ BOOST_REQUIRE(f.empty());
+}
+
+BOOST_AUTO_TEST_CASE( stack_consume_all_test )
+{
+ boost::lockfree::stack<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ f.push(1);
+ f.push(2);
+
+#ifdef BOOST_NO_CXX11_LAMBDAS
+ size_t consumed = f.consume_all(dummy_functor());
+#else
+ size_t consumed = f.consume_all([] (int i) {
+ });
+#endif
+
+ BOOST_REQUIRE_EQUAL(consumed, 2u);
+
+ BOOST_REQUIRE(f.empty());
+}
+
+BOOST_AUTO_TEST_CASE( stack_consume_all_atomic_test )
+{
+ boost::lockfree::stack<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ f.push(1);
+ f.push(2);
+ f.push(3);
+
+#ifdef BOOST_NO_CXX11_LAMBDAS
+ size_t consumed = f.consume_all_atomic(dummy_functor());
+#else
+ size_t consumed = f.consume_all_atomic([] (int i) {
+ });
+#endif
+
+ BOOST_REQUIRE_EQUAL(consumed, 3u);
+
+ BOOST_REQUIRE(f.empty());
+}
+
+
+BOOST_AUTO_TEST_CASE( stack_consume_all_atomic_reversed_test )
+{
+ boost::lockfree::stack<int> f(64);
+
+ BOOST_WARN(f.is_lock_free());
+ BOOST_REQUIRE(f.empty());
+
+ f.push(1);
+ f.push(2);
+ f.push(3);
+
+#ifdef BOOST_NO_CXX11_LAMBDAS
+ size_t consumed = f.consume_all_atomic_reversed(dummy_functor());
+#else
+ size_t consumed = f.consume_all_atomic_reversed([] (int i) {
+ });
+#endif
+
+ BOOST_REQUIRE_EQUAL(consumed, 3u);
+
+ BOOST_REQUIRE(f.empty());
+}
+
+
+BOOST_AUTO_TEST_CASE( reserve_test )
+{
+ typedef boost::lockfree::stack< void* > memory_stack;
+
+ memory_stack ms(1);
+ ms.reserve(1);
+ ms.reserve_unsafe(1);
+}
diff --git a/src/boost/libs/lockfree/test/stack_unbounded_stress_test.cpp b/src/boost/libs/lockfree/test/stack_unbounded_stress_test.cpp
new file mode 100644
index 000000000..98d975173
--- /dev/null
+++ b/src/boost/libs/lockfree/test/stack_unbounded_stress_test.cpp
@@ -0,0 +1,28 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/lockfree/stack.hpp>
+
+#include <boost/scoped_ptr.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+#include "test_common.hpp"
+
+
+BOOST_AUTO_TEST_CASE( stack_test_unbounded )
+{
+ typedef queue_stress_tester<false> tester_type;
+ boost::scoped_ptr<tester_type> tester(new tester_type(4, 4) );
+
+ boost::lockfree::stack<long> q(128);
+ tester->run(q);
+}
diff --git a/src/boost/libs/lockfree/test/tagged_ptr_test.cpp b/src/boost/libs/lockfree/test/tagged_ptr_test.cpp
new file mode 100644
index 000000000..4ce1dd741
--- /dev/null
+++ b/src/boost/libs/lockfree/test/tagged_ptr_test.cpp
@@ -0,0 +1,58 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <limits>
+
+#include <boost/lockfree/detail/tagged_ptr.hpp>
+
+#define BOOST_TEST_MAIN
+#ifdef BOOST_LOCKFREE_INCLUDE_TESTS
+#include <boost/test/included/unit_test.hpp>
+#else
+#include <boost/test/unit_test.hpp>
+#endif
+
+BOOST_AUTO_TEST_CASE( tagged_ptr_test )
+{
+ using namespace boost::lockfree::detail;
+ int a(1), b(2);
+
+ typedef tagged_ptr<int>::tag_t tag_t;
+ const tag_t max_tag = (std::numeric_limits<tag_t>::max)();
+
+ {
+ tagged_ptr<int> i (&a, 0);
+ tagged_ptr<int> j (&b, 1);
+
+ i = j;
+
+ BOOST_REQUIRE_EQUAL(i.get_ptr(), &b);
+ BOOST_REQUIRE_EQUAL(i.get_tag(), 1);
+ }
+
+ {
+ tagged_ptr<int> i (&a, 0);
+ tagged_ptr<int> j (i);
+
+ BOOST_REQUIRE_EQUAL(i.get_ptr(), j.get_ptr());
+ BOOST_REQUIRE_EQUAL(i.get_tag(), j.get_tag());
+ }
+
+ {
+ tagged_ptr<int> i (&a, 0);
+ BOOST_REQUIRE_EQUAL(i.get_tag() + 1, i.get_next_tag());
+ }
+
+ {
+ tagged_ptr<int> j (&a, max_tag);
+ BOOST_REQUIRE_EQUAL(j.get_next_tag(), 0);
+ }
+
+ {
+ tagged_ptr<int> j (&a, max_tag - 1);
+ BOOST_REQUIRE_EQUAL(j.get_next_tag(), max_tag);
+ }
+}
diff --git a/src/boost/libs/lockfree/test/test_common.hpp b/src/boost/libs/lockfree/test/test_common.hpp
new file mode 100644
index 000000000..2db41a847
--- /dev/null
+++ b/src/boost/libs/lockfree/test/test_common.hpp
@@ -0,0 +1,145 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <cassert>
+#include <iostream>
+#include "test_helpers.hpp"
+
+#include <boost/array.hpp>
+#include <boost/thread.hpp>
+
+namespace impl {
+
+using boost::array;
+using namespace boost;
+using namespace std;
+
+template <bool Bounded = false>
+struct queue_stress_tester
+{
+ static const unsigned int buckets = 1<<13;
+#ifndef BOOST_LOCKFREE_STRESS_TEST
+ static const long node_count = 5000;
+#else
+ static const long node_count = 500000;
+#endif
+ const int reader_threads;
+ const int writer_threads;
+
+ boost::lockfree::detail::atomic<int> writers_finished;
+
+ static_hashed_set<long, buckets> data;
+ static_hashed_set<long, buckets> dequeued;
+ array<std::set<long>, buckets> returned;
+
+ boost::lockfree::detail::atomic<int> push_count, pop_count;
+
+ queue_stress_tester(int reader, int writer):
+ reader_threads(reader), writer_threads(writer), push_count(0), pop_count(0)
+ {}
+
+ template <typename queue>
+ void add_items(queue & stk)
+ {
+ for (long i = 0; i != node_count; ++i) {
+ long id = generate_id<long>();
+
+ bool inserted = data.insert(id);
+ assert(inserted);
+
+ if (Bounded)
+ while(stk.bounded_push(id) == false) {
+#ifdef __VXWORKS__
+ thread::yield();
+#endif
+ }
+ else
+ while(stk.push(id) == false) {
+#ifdef __VXWORKS__
+ thread::yield();
+#endif
+ }
+ ++push_count;
+ }
+ writers_finished += 1;
+ }
+
+ boost::lockfree::detail::atomic<bool> running;
+
+ template <typename queue>
+ bool consume_element(queue & q)
+ {
+ long id;
+ bool ret = q.pop(id);
+
+ if (!ret)
+ return false;
+
+ bool erased = data.erase(id);
+ bool inserted = dequeued.insert(id);
+ assert(erased);
+ assert(inserted);
+ ++pop_count;
+ return true;
+ }
+
+ template <typename queue>
+ void get_items(queue & q)
+ {
+ for (;;) {
+ bool received_element = consume_element(q);
+ if (received_element)
+ continue;
+
+ if ( writers_finished.load() == writer_threads )
+ break;
+
+#ifdef __VXWORKS__
+ thread::yield();
+#endif
+ }
+
+ while (consume_element(q));
+ }
+
+ template <typename queue>
+ void run(queue & stk)
+ {
+ BOOST_WARN(stk.is_lock_free());
+ writers_finished.store(0);
+
+ thread_group writer;
+ thread_group reader;
+
+ BOOST_REQUIRE(stk.empty());
+
+ for (int i = 0; i != reader_threads; ++i)
+ reader.create_thread(boost::bind(&queue_stress_tester::template get_items<queue>, this, boost::ref(stk)));
+
+ for (int i = 0; i != writer_threads; ++i)
+ writer.create_thread(boost::bind(&queue_stress_tester::template add_items<queue>, this, boost::ref(stk)));
+
+ std::cout << "threads created" << std::endl;
+
+ writer.join_all();
+
+ std::cout << "writer threads joined, waiting for readers" << std::endl;
+
+ reader.join_all();
+
+ std::cout << "reader threads joined" << std::endl;
+
+ BOOST_REQUIRE_EQUAL(data.count_nodes(), (size_t)0);
+ BOOST_REQUIRE(stk.empty());
+
+ BOOST_REQUIRE_EQUAL(push_count, pop_count);
+ BOOST_REQUIRE_EQUAL(push_count, writer_threads * node_count);
+ }
+};
+
+}
+
+using impl::queue_stress_tester;
diff --git a/src/boost/libs/lockfree/test/test_helpers.hpp b/src/boost/libs/lockfree/test/test_helpers.hpp
new file mode 100644
index 000000000..882fa1c45
--- /dev/null
+++ b/src/boost/libs/lockfree/test/test_helpers.hpp
@@ -0,0 +1,110 @@
+// Copyright (C) 2011 Tim Blechmann
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_LOCKFREE_TEST_HELPERS
+#define BOOST_LOCKFREE_TEST_HELPERS
+
+#include <set>
+#include <boost/array.hpp>
+#include <boost/lockfree/detail/atomic.hpp>
+#include <boost/thread.hpp>
+
+#include <boost/cstdint.hpp>
+
+template <typename int_type>
+int_type generate_id(void)
+{
+ static boost::lockfree::detail::atomic<int_type> generator(0);
+ return ++generator;
+}
+
+template <typename int_type, size_t buckets>
+class static_hashed_set
+{
+
+public:
+ int calc_index(int_type id)
+ {
+ // knuth hash ... does not need to be good, but has to be portable
+ size_t factor = size_t((float)buckets * 1.616f);
+
+ return ((size_t)id * factor) % buckets;
+ }
+
+ bool insert(int_type const & id)
+ {
+ std::size_t index = calc_index(id);
+
+ boost::lock_guard<boost::mutex> lock (ref_mutex[index]);
+
+ std::pair<typename std::set<int_type>::iterator, bool> p;
+ p = data[index].insert(id);
+
+ return p.second;
+ }
+
+ bool find (int_type const & id)
+ {
+ std::size_t index = calc_index(id);
+
+ boost::lock_guard<boost::mutex> lock (ref_mutex[index]);
+
+ return data[index].find(id) != data[index].end();
+ }
+
+ bool erase(int_type const & id)
+ {
+ std::size_t index = calc_index(id);
+
+ boost::lock_guard<boost::mutex> lock (ref_mutex[index]);
+
+ if (data[index].find(id) != data[index].end()) {
+ data[index].erase(id);
+ assert(data[index].find(id) == data[index].end());
+ return true;
+ }
+ else
+ return false;
+ }
+
+ std::size_t count_nodes(void) const
+ {
+ std::size_t ret = 0;
+ for (int i = 0; i != buckets; ++i) {
+ boost::lock_guard<boost::mutex> lock (ref_mutex[i]);
+ ret += data[i].size();
+ }
+ return ret;
+ }
+
+private:
+ boost::array<std::set<int_type>, buckets> data;
+ mutable boost::array<boost::mutex, buckets> ref_mutex;
+};
+
+struct test_equal
+{
+ test_equal(int i):
+ i(i)
+ {}
+
+ void operator()(int arg) const
+ {
+ BOOST_REQUIRE_EQUAL(arg, i);
+ }
+
+ int i;
+};
+
+struct dummy_functor
+{
+ void operator()(int /* arg */) const
+ {
+ }
+};
+
+
+#endif