src/parsec/disk-image/parsec/parsec-benchmark/pkgs/libs/tbblib/src/src/test/test_concurrent_unordered.cpp - public/gem5-resources - Git at Google

 /*
     Copyright 2005-2010 Intel Corporation.  All Rights Reserved.

     This file is part of Threading Building Blocks.

     Threading Building Blocks is free software; you can redistribute it
     and/or modify it under the terms of the GNU General Public License
     version 2 as published by the Free Software Foundation.

     Threading Building Blocks is distributed in the hope that it will be
     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     GNU General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with Threading Building Blocks; if not, write to the Free Software
     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

     As a special exception, you may use this file as part of a free software
     library without restriction.  Specifically, if other files instantiate
     templates or use macros or inline functions from this file, or you compile
     this file and link it with other files to produce an executable, this
     file does not by itself cause the resulting executable to be covered by
     the GNU General Public License.  This exception does not however
     invalidate any other reasons why the executable file might be covered by
     the GNU General Public License.
 */

 /* Some tests in this source file are based on PPL tests provided by Microsoft. */

 #define __TBB_EXTRA_DEBUG 1
 #include "tbb/concurrent_unordered_map.h"
 #include "tbb/parallel_for.h"
 #include "tbb/tick_count.h"
 #include <stdio.h>
 #include "harness.h"
 #include "harness_allocator.h"

 using namespace std;

 typedef local_counting_allocator<debug_allocator<std::pair<const int,int>,std::allocator> > MyAllocator;
 typedef tbb::concurrent_unordered_map<int, int, tbb::tbb_hash<int>, std::equal_to<int>, MyAllocator> Mycumap;
 //typedef tbb::concurrent_unordered_map<int, int> Mycumap;
 //typedef concurrent_unordered_multimap<int, int> Mycummap;

 #define CheckAllocatorE(t,a,f) CheckAllocator(t,a,f,true,__LINE__)
 #define CheckAllocatorA(t,a,f) CheckAllocator(t,a,f,false,__LINE__)
 template<typename MyTable>
 inline void CheckAllocator(MyTable &table, size_t expected_allocs, size_t expected_frees, bool exact = true, int line = 0) {
     typename MyTable::allocator_type a = table.get_allocator();
     REMARK("#%d checking allocators: items %u/%u, allocs %u/%u\n", line,
         unsigned(a.items_allocated), unsigned(a.items_freed), unsigned(a.allocations), unsigned(a.frees) );
     ASSERT( a.items_allocated == a.allocations, NULL); ASSERT( a.items_freed == a.frees, NULL);
     if(exact) {
         ASSERT( a.allocations == expected_allocs, NULL); ASSERT( a.frees == expected_frees, NULL);
     } else {
         ASSERT( a.allocations >= expected_allocs, NULL); ASSERT( a.frees >= expected_frees, NULL);
         ASSERT( a.allocations - a.frees == expected_allocs - expected_frees, NULL );
     }
 }

 template <typename K, typename V = std::pair<const K, K> >
 struct ValueFactory {
     static V make(const K &value) { return V(value, value); }
     static K get(const V& value) { return value.second; }
 };

 template <typename T>
 struct ValueFactory<T, T> {
     static T make(const T &value) { return value; }
     static T get(const T &value) { return value; }
 };

 template <typename T>
 struct Value : ValueFactory<typename T::key_type, typename T::value_type> {};

 #if _MSC_VER
 #pragma warning(disable: 4189) // warning 4189 -- local variable is initialized but not referenced
 #pragma warning(disable: 4127) // warning 4127 -- while (true) has a constant expression in it
 #endif

 template<typename Iterator, typename RangeType>
 std::pair<int,int> CheckRecursiveRange(RangeType range) {
     std::pair<int,int> sum(0, 0); // count, sum
     for( Iterator i = range.begin(), e = range.end(); i != e; ++i ) {
         ++sum.first; sum.second += i->second;
     }
     if( range.is_divisible() ) {
         RangeType range2( range, tbb::split() );
         std::pair<int,int> sum1 = CheckRecursiveRange<Iterator, RangeType>( range );
         std::pair<int,int> sum2 = CheckRecursiveRange<Iterator, RangeType>( range2 );
         sum1.first += sum2.first; sum1.second += sum2.second;
         ASSERT( sum == sum1, "Mismatched ranges after division");
     }
     return sum;
 }

 template <typename T>
 struct SpecialTests {
     static void Test() {}
 };

 template <>
 struct SpecialTests <Mycumap>
 {
     static void Test()
     {
         Mycumap cont;
         const Mycumap &ccont(cont);

         // mapped_type& operator[](const key_type& k);
         cont[1] = 2;

         // bool empty() const;
         ASSERT(!ccont.empty(), "Concurrent container empty after adding an element");

         // size_type size() const;
         ASSERT(ccont.size() == 1, "Concurrent container size incorrect");

         ASSERT(cont[1] == 2, "Concurrent container size incorrect");

         // mapped_type& at( const key_type& k );
         // const mapped_type& at(const key_type& k) const;
         ASSERT(cont.at(1) == 2, "Concurrent container size incorrect");
         ASSERT(ccont.at(1) == 2, "Concurrent container size incorrect");

         // iterator find(const key_type& k);
         Mycumap::const_iterator it = cont.find(1);
         ASSERT(it != cont.end() && Value<Mycumap>::get(*(it)) == 2, "Element with key 1 not properly found");

         REMARK("passed -- specialized concurrent unordered map tests\n");
     }
 };

 template<typename T>
 void test_basic(const char * str)
 {
     T cont;
     const T &ccont(cont);

     // bool empty() const;
     ASSERT(ccont.empty(), "Concurrent container not empty after construction");

     // size_type size() const;
     ASSERT(ccont.size() == 0, "Concurrent container not empty after construction");

     // size_type max_size() const;
     ASSERT(ccont.max_size() > 0, "Concurrent container max size invalid");

     //iterator begin();
     //iterator end();
     ASSERT(cont.begin() == cont.end(), "Concurrent container iterators invalid after construction");
     ASSERT(ccont.begin() == ccont.end(), "Concurrent container iterators invalid after construction");
     ASSERT(cont.cbegin() == cont.cend(), "Concurrent container iterators invalid after construction");

     //std::pair<iterator, bool> insert(const value_type& obj);
     std::pair<typename T::iterator, bool> ins = cont.insert(Value<T>::make(1));
     ASSERT(ins.second == true && Value<T>::get(*(ins.first)) == 1, "Element 1 not properly inserted");

     // bool empty() const;
     ASSERT(!ccont.empty(), "Concurrent container empty after adding an element");

     // size_type size() const;
     ASSERT(ccont.size() == 1, "Concurrent container size incorrect");

     std::pair<typename T::iterator, bool> ins2 = cont.insert(Value<T>::make(1));

     if (T::allow_multimapping)
     {
         // std::pair<iterator, bool> insert(const value_type& obj);
         ASSERT(ins2.second == true && Value<T>::get(*(ins2.first)) == 1, "Element 1 not properly inserted");

         // size_type size() const;
         ASSERT(ccont.size() == 2, "Concurrent container size incorrect");

         // size_type count(const key_type& k) const;
         ASSERT(ccont.count(1) == 2, "Concurrent container count(1) incorrect");

         // std::pair<iterator, iterator> equal_range(const key_type& k);
         std::pair<typename T::iterator, typename T::iterator> range = cont.equal_range(1);
         typename T::iterator it = range.first;
         ASSERT(it != cont.end() && Value<T>::get(*it) == 1, "Element 1 not properly found");
         unsigned int count = 0;
         for (; it != range.second; it++)
         {
             count++;
             ASSERT(Value<T>::get(*it) == 1, "Element 1 not properly found");
         }

         ASSERT(count == 2, "Range doesn't have the right number of elements");
     }
     else
     {
         // std::pair<iterator, bool> insert(const value_type& obj);
         ASSERT(ins2.second == false && ins2.first == ins.first, "Element 1 should not be re-inserted");

         // size_type size() const;
         ASSERT(ccont.size() == 1, "Concurrent container size incorrect");

         // size_type count(const key_type& k) const;
         ASSERT(ccont.count(1) == 1, "Concurrent container count(1) incorrect");

         // std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
         // std::pair<iterator, iterator> equal_range(const key_type& k);
         std::pair<typename T::iterator, typename T::iterator> range = cont.equal_range(1);
         typename T::iterator i = range.first;
         ASSERT(i != cont.end() && Value<T>::get(*i) == 1, "Element 1 not properly found");
         ASSERT(++i == range.second, "Range doesn't have the right number of elements");
     }

     // const_iterator find(const key_type& k) const;
     // iterator find(const key_type& k);
     typename T::iterator it = cont.find(1);
     ASSERT(it != cont.end() && Value<T>::get(*(it)) == 1, "Element 1 not properly found");
     ASSERT(ccont.find(1) == it, "Element 1 not properly found");

     // iterator insert(const_iterator hint, const value_type& obj);
     typename T::iterator it2 = cont.insert(ins.first, Value<T>::make(2));
     ASSERT(Value<T>::get(*it2) == 2, "Element 2 not properly inserted");

     // T(const T& _Umap)
     T newcont = ccont;
     ASSERT(T::allow_multimapping ? (newcont.size() == 3) : (newcont.size() == 2), "Copy construction did not copy the elements properly");

     // size_type unsafe_erase(const key_type& k);
     typename T::size_type size = cont.unsafe_erase(1);
     ASSERT(T::allow_multimapping ? (size == 2) : (size == 1), "Erase did not remove the right number of elements");

     // iterator unsafe_erase(const_iterator position);
     typename T::iterator it4 = cont.unsafe_erase(cont.find(2));
     ASSERT(it4 == cont.end() && cont.size() == 0, "Erase did not remove the last element properly");

     // template<class InputIterator> void insert(InputIterator first, InputIterator last);
     cont.insert(newcont.begin(), newcont.end());
     ASSERT(T::allow_multimapping ? (cont.size() == 3) : (cont.size() == 2), "Range insert did not copy the elements properly");

     // iterator unsafe_erase(const_iterator first, const_iterator last);
     std::pair<typename T::iterator, typename T::iterator> range2 = newcont.equal_range(1);
     newcont.unsafe_erase(range2.first, range2.second);
     ASSERT(newcont.size() == 1, "Range erase did not erase the elements properly");

     // void clear();
     newcont.clear();
     ASSERT(newcont.begin() == newcont.end() && newcont.size() == 0, "Clear did not clear the container");

     // T& operator=(const T& _Umap)
     newcont = ccont;
     ASSERT(T::allow_multimapping ? (newcont.size() == 3) : (newcont.size() == 2), "Assignment operator did not copy the elements properly");

     // void rehash(size_type n);
     newcont.rehash(16);
     ASSERT(T::allow_multimapping ? (newcont.size() == 3) : (newcont.size() == 2), "Rehash should not affect the container elements");

     // float load_factor() const;
     // float max_load_factor() const;
     ASSERT(ccont.load_factor() <= ccont.max_load_factor(), "Load factor invalid");

     // void max_load_factor(float z);
     cont.max_load_factor(16.0f);
     ASSERT(ccont.max_load_factor() == 16.0f, "Max load factor not properly changed");

     // hasher hash_function() const;
     ccont.hash_function();

     // key_equal key_eq() const;
     ccont.key_eq();

     cont.clear();
     CheckAllocatorA(cont, 1, 0); // one dummy is always allocated
     for (int i = 0; i < 256; i++)
     {
         std::pair<typename T::iterator, bool> ins3 = cont.insert(Value<T>::make(i));
         ASSERT(ins3.second == true && Value<T>::get(*(ins3.first)) == i, "Element 1 not properly inserted");
     }
     ASSERT(cont.size() == 256, "Wrong number of elements inserted");
     ASSERT(256 == CheckRecursiveRange<typename T::iterator>(cont.range()).first, NULL);
     ASSERT(256 == CheckRecursiveRange<typename T::const_iterator>(ccont.range()).first, NULL);

     // size_type unsafe_bucket_count() const;
     ASSERT(ccont.unsafe_bucket_count() == 16, "Wrong number of buckets");

     // size_type unsafe_max_bucket_count() const;
     ASSERT(ccont.unsafe_max_bucket_count() > 65536, "Wrong max number of buckets");

     for (unsigned int i = 0; i < 256; i++)
     {
         typename T::size_type buck = ccont.unsafe_bucket(i);

         // size_type unsafe_bucket(const key_type& k) const;
         ASSERT(buck < 16, "Wrong bucket mapping");
     }

     for (unsigned int i = 0; i < 16; i++)
     {
         // size_type unsafe_bucket_size(size_type n);
         ASSERT(cont.unsafe_bucket_size(i) == 16, "Wrong number elements in a bucket");

         // local_iterator unsafe_begin(size_type n);
         // const_local_iterator unsafe_begin(size_type n) const;
         // local_iterator unsafe_end(size_type n);
         // const_local_iterator unsafe_end(size_type n) const;
         // const_local_iterator unsafe_cbegin(size_type n) const;
         // const_local_iterator unsafe_cend(size_type n) const;
         unsigned int count = 0;
         for (typename T::iterator bit = cont.unsafe_begin(i); bit != cont.unsafe_end(i); bit++)
         {
             count++;
         }
         ASSERT(count == 16, "Bucket iterators are invalid");
     }

     // void swap(T&);
     cont.swap(newcont);
     ASSERT(newcont.size() == 256, "Wrong number of elements after swap");
     ASSERT(newcont.count(200) == 1, "Element with key 200 not present after swap");
     ASSERT(newcont.count(16) == 1, "Element with key 16 not present after swap");
     ASSERT(newcont.count(99) == 1, "Element with key 99 not present after swap");
     ASSERT(T::allow_multimapping ? (cont.size() == 3) : (cont.size() == 2), "Wrong number of elements after swap");

     REMARK("passed -- basic %S tests\n", str);

 #if defined (VERBOSE)
     REMARK("container dump debug:\n");
     cont._Dump();
     REMARK("container dump release:\n");
     cont.dump();
     REMARK("\n");
 #endif

     SpecialTests<T>::Test();
 }

 void test_machine() {
     ASSERT(__TBB_ReverseByte(0)==0, NULL );
     ASSERT(__TBB_ReverseByte(1)==0x80, NULL );
     ASSERT(__TBB_ReverseByte(0xFE)==0x7F, NULL );
     ASSERT(__TBB_ReverseByte(0xFF)==0xFF, NULL );
 }

 template<typename T>
 class FillTable: NoAssign {
     T &table;
     const int items;
     typedef std::pair<typename T::iterator, bool> pairIB;
 public:
     FillTable(T &t, int i) : table(t), items(i) {
         ASSERT( !(items&1) && items > 100, NULL);
     }
     void operator()(int threadn) const {
         if( threadn == 0 ) { // Fill even keys forward (single thread)
             bool last_inserted = true;
             for( int i = 0; i < items; i+=2 ) {
                 pairIB pib = table.insert(Value<T>::make(i));
                 ASSERT(Value<T>::get(*(pib.first)) == i, "Element not properly inserted");
                 ASSERT( last_inserted || !pib.second, "Previous key was not inserted but this is inserted" );
                 last_inserted = pib.second;
             }
         } else if( threadn == 1 ) { // Fill even keys backward (single thread)
             bool last_inserted = true;
             for( int i = items-2; i >= 0; i-=2 ) {
                 pairIB pib = table.insert(Value<T>::make(i));
                 ASSERT(Value<T>::get(*(pib.first)) == i, "Element not properly inserted");
                 ASSERT( last_inserted || !pib.second, "Previous key was not inserted but this is inserted" );
                 last_inserted = pib.second;
             }
         } else if( !(threadn&1) ) { // Fill odd keys forward (multiple threads)
             for( int i = 1; i < items; i+=2 ) {
                 pairIB pib = table.insert(Value<T>::make(i));
                 ASSERT(Value<T>::get(*(pib.first)) == i, "Element not properly inserted");
             }
         } else { // Check odd keys backward (multiple threads)
             bool last_found = false;
             for( int i = items-1; i >= 0; i-=2 ) {
                 typename T::iterator it = table.find(i);
                 if( it != table.end() ) { // found
                     ASSERT(Value<T>::get(*it) == i, "Element not properly inserted");
                     last_found = true;
                 } else ASSERT( !last_found, "Previous key was found but this is not" );
             }
         }
     }
 };

 typedef tbb::atomic<unsigned char> AtomicByte;

 template<typename RangeType>
 struct ParallelTraverseBody: NoAssign {
     const int n;
     AtomicByte* const array;
     ParallelTraverseBody( AtomicByte an_array[], int a_n ) :
         n(a_n), array(an_array)
     {}
     void operator()( const RangeType& range ) const {
         for( typename RangeType::iterator i = range.begin(); i!=range.end(); ++i ) {
             int k = i->first;
             ASSERT( k == i->second, NULL );
             ASSERT( 0<=k && k<n, NULL );
             array[k]++;
         }
     }
 };

 void CheckRange( AtomicByte array[], int n ) {
     for( int k=0; k<n; ++k ) {
         if( array[k] != 1 ) {
             REPORT("array[%d]=%d\n", k, int(array[k]));
             ASSERT(false,NULL);
         }
     }
 }

 template<typename T>
 void test_concurrent(const char *tablename) {
     T table;
 #if TBB_USE_ASSERT
     int items = 2000;
 #else
     int items = 100000;
 #endif
     tbb::tick_count t0 = tbb::tick_count::now();
     NativeParallelFor( 16/*min 6*/, FillTable<T>(table, items) );
     tbb::tick_count t1 = tbb::tick_count::now();
     REMARK( "time for filling '%s' by %d items = %g\n", tablename, items, (t1-t0).seconds() );
     ASSERT( int(table.size()) == items, NULL);

     AtomicByte* array = new AtomicByte[items];
     memset( array, 0, items*sizeof(AtomicByte) );

     typename T::range_type r = table.range();
     ASSERT(items == CheckRecursiveRange<typename T::iterator>(r).first, NULL);
     tbb::parallel_for( r, ParallelTraverseBody<typename T::const_range_type>( array, items ));
     CheckRange( array, items );

     const T &const_table = table;
     memset( array, 0, items*sizeof(AtomicByte) );
     typename T::const_range_type cr = const_table.range();
     ASSERT(items == CheckRecursiveRange<typename T::const_iterator>(cr).first, NULL);
     tbb::parallel_for( cr, ParallelTraverseBody<typename T::const_range_type>( array, items ));
     CheckRange( array, items );

     delete[] array;

     table.clear();
     CheckAllocatorA(table, items+1, items); // one dummy is always allocated
 }

 int TestMain () {
     test_machine();
     test_basic<Mycumap>("concurrent unordered map");
     test_concurrent<Mycumap>("concurrent unordered map");
     return Harness::Done;
 }
	/*
	Copyright 2005-2010 Intel Corporation. All Rights Reserved.

	This file is part of Threading Building Blocks.

	Threading Building Blocks is free software; you can redistribute it
	and/or modify it under the terms of the GNU General Public License
	version 2 as published by the Free Software Foundation.

	Threading Building Blocks is distributed in the hope that it will be
	useful, but WITHOUT ANY WARRANTY; without even the implied warranty
	of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with Threading Building Blocks; if not, write to the Free Software
	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA

	As a special exception, you may use this file as part of a free software
	library without restriction. Specifically, if other files instantiate
	templates or use macros or inline functions from this file, or you compile
	this file and link it with other files to produce an executable, this
	file does not by itself cause the resulting executable to be covered by
	the GNU General Public License. This exception does not however
	invalidate any other reasons why the executable file might be covered by
	the GNU General Public License.
	*/

	/* Some tests in this source file are based on PPL tests provided by Microsoft. */

	#define __TBB_EXTRA_DEBUG 1
	#include "tbb/concurrent_unordered_map.h"
	#include "tbb/parallel_for.h"
	#include "tbb/tick_count.h"
	#include <stdio.h>
	#include "harness.h"
	#include "harness_allocator.h"

	using namespace std;

	typedef local_counting_allocator<debug_allocator<std::pair<const int,int>,std::allocator> > MyAllocator;
	typedef tbb::concurrent_unordered_map<int, int, tbb::tbb_hash<int>, std::equal_to<int>, MyAllocator> Mycumap;
	//typedef tbb::concurrent_unordered_map<int, int> Mycumap;
	//typedef concurrent_unordered_multimap<int, int> Mycummap;

	#define CheckAllocatorE(t,a,f) CheckAllocator(t,a,f,true,__LINE__)
	#define CheckAllocatorA(t,a,f) CheckAllocator(t,a,f,false,__LINE__)
	template<typename MyTable>
	inline void CheckAllocator(MyTable &table, size_t expected_allocs, size_t expected_frees, bool exact = true, int line = 0) {
	typename MyTable::allocator_type a = table.get_allocator();
	REMARK("#%d checking allocators: items %u/%u, allocs %u/%u\n", line,
	unsigned(a.items_allocated), unsigned(a.items_freed), unsigned(a.allocations), unsigned(a.frees) );
	ASSERT( a.items_allocated == a.allocations, NULL); ASSERT( a.items_freed == a.frees, NULL);
	if(exact) {
	ASSERT( a.allocations == expected_allocs, NULL); ASSERT( a.frees == expected_frees, NULL);
	} else {
	ASSERT( a.allocations >= expected_allocs, NULL); ASSERT( a.frees >= expected_frees, NULL);
	ASSERT( a.allocations - a.frees == expected_allocs - expected_frees, NULL );
	}
	}

	template <typename K, typename V = std::pair<const K, K> >
	struct ValueFactory {
	static V make(const K &value) { return V(value, value); }
	static K get(const V& value) { return value.second; }
	};

	template <typename T>
	struct ValueFactory<T, T> {
	static T make(const T &value) { return value; }
	static T get(const T &value) { return value; }
	};

	template <typename T>
	struct Value : ValueFactory<typename T::key_type, typename T::value_type> {};

	#if _MSC_VER
	#pragma warning(disable: 4189) // warning 4189 -- local variable is initialized but not referenced
	#pragma warning(disable: 4127) // warning 4127 -- while (true) has a constant expression in it
	#endif

	template<typename Iterator, typename RangeType>
	std::pair<int,int> CheckRecursiveRange(RangeType range) {
	std::pair<int,int> sum(0, 0); // count, sum
	for( Iterator i = range.begin(), e = range.end(); i != e; ++i ) {
	++sum.first; sum.second += i->second;
	}
	if( range.is_divisible() ) {
	RangeType range2( range, tbb::split() );
	std::pair<int,int> sum1 = CheckRecursiveRange<Iterator, RangeType>( range );
	std::pair<int,int> sum2 = CheckRecursiveRange<Iterator, RangeType>( range2 );
	sum1.first += sum2.first; sum1.second += sum2.second;
	ASSERT( sum == sum1, "Mismatched ranges after division");
	}
	return sum;
	}

	template <typename T>
	struct SpecialTests {
	static void Test() {}
	};

	template <>
	struct SpecialTests <Mycumap>
	{
	static void Test()
	{
	Mycumap cont;
	const Mycumap &ccont(cont);

	// mapped_type& operator[](const key_type& k);
	cont[1] = 2;

	// bool empty() const;
	ASSERT(!ccont.empty(), "Concurrent container empty after adding an element");

	// size_type size() const;
	ASSERT(ccont.size() == 1, "Concurrent container size incorrect");

	ASSERT(cont[1] == 2, "Concurrent container size incorrect");

	// mapped_type& at( const key_type& k );
	// const mapped_type& at(const key_type& k) const;
	ASSERT(cont.at(1) == 2, "Concurrent container size incorrect");
	ASSERT(ccont.at(1) == 2, "Concurrent container size incorrect");

	// iterator find(const key_type& k);
	Mycumap::const_iterator it = cont.find(1);
	ASSERT(it != cont.end() && Value<Mycumap>::get(*(it)) == 2, "Element with key 1 not properly found");

	REMARK("passed -- specialized concurrent unordered map tests\n");
	}
	};

	template<typename T>
	void test_basic(const char * str)
	{
	T cont;
	const T &ccont(cont);

	// bool empty() const;
	ASSERT(ccont.empty(), "Concurrent container not empty after construction");

	// size_type size() const;
	ASSERT(ccont.size() == 0, "Concurrent container not empty after construction");

	// size_type max_size() const;
	ASSERT(ccont.max_size() > 0, "Concurrent container max size invalid");

	//iterator begin();
	//iterator end();
	ASSERT(cont.begin() == cont.end(), "Concurrent container iterators invalid after construction");
	ASSERT(ccont.begin() == ccont.end(), "Concurrent container iterators invalid after construction");
	ASSERT(cont.cbegin() == cont.cend(), "Concurrent container iterators invalid after construction");

	//std::pair<iterator, bool> insert(const value_type& obj);
	std::pair<typename T::iterator, bool> ins = cont.insert(Value<T>::make(1));
	ASSERT(ins.second == true && Value<T>::get(*(ins.first)) == 1, "Element 1 not properly inserted");

	// bool empty() const;
	ASSERT(!ccont.empty(), "Concurrent container empty after adding an element");

	// size_type size() const;
	ASSERT(ccont.size() == 1, "Concurrent container size incorrect");

	std::pair<typename T::iterator, bool> ins2 = cont.insert(Value<T>::make(1));

	if (T::allow_multimapping)
	{
	// std::pair<iterator, bool> insert(const value_type& obj);
	ASSERT(ins2.second == true && Value<T>::get(*(ins2.first)) == 1, "Element 1 not properly inserted");

	// size_type size() const;
	ASSERT(ccont.size() == 2, "Concurrent container size incorrect");

	// size_type count(const key_type& k) const;
	ASSERT(ccont.count(1) == 2, "Concurrent container count(1) incorrect");

	// std::pair<iterator, iterator> equal_range(const key_type& k);
	std::pair<typename T::iterator, typename T::iterator> range = cont.equal_range(1);
	typename T::iterator it = range.first;
	ASSERT(it != cont.end() && Value<T>::get(*it) == 1, "Element 1 not properly found");
	unsigned int count = 0;
	for (; it != range.second; it++)
	{
	count++;
	ASSERT(Value<T>::get(*it) == 1, "Element 1 not properly found");
	}

	ASSERT(count == 2, "Range doesn't have the right number of elements");
	}
	else
	{
	// std::pair<iterator, bool> insert(const value_type& obj);
	ASSERT(ins2.second == false && ins2.first == ins.first, "Element 1 should not be re-inserted");

	// size_type size() const;
	ASSERT(ccont.size() == 1, "Concurrent container size incorrect");

	// size_type count(const key_type& k) const;
	ASSERT(ccont.count(1) == 1, "Concurrent container count(1) incorrect");

	// std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
	// std::pair<iterator, iterator> equal_range(const key_type& k);
	std::pair<typename T::iterator, typename T::iterator> range = cont.equal_range(1);
	typename T::iterator i = range.first;
	ASSERT(i != cont.end() && Value<T>::get(*i) == 1, "Element 1 not properly found");
	ASSERT(++i == range.second, "Range doesn't have the right number of elements");
	}

	// const_iterator find(const key_type& k) const;
	// iterator find(const key_type& k);
	typename T::iterator it = cont.find(1);
	ASSERT(it != cont.end() && Value<T>::get(*(it)) == 1, "Element 1 not properly found");
	ASSERT(ccont.find(1) == it, "Element 1 not properly found");

	// iterator insert(const_iterator hint, const value_type& obj);
	typename T::iterator it2 = cont.insert(ins.first, Value<T>::make(2));
	ASSERT(Value<T>::get(*it2) == 2, "Element 2 not properly inserted");

	// T(const T& _Umap)
	T newcont = ccont;
	ASSERT(T::allow_multimapping ? (newcont.size() == 3) : (newcont.size() == 2), "Copy construction did not copy the elements properly");

	// size_type unsafe_erase(const key_type& k);
	typename T::size_type size = cont.unsafe_erase(1);
	ASSERT(T::allow_multimapping ? (size == 2) : (size == 1), "Erase did not remove the right number of elements");

	// iterator unsafe_erase(const_iterator position);
	typename T::iterator it4 = cont.unsafe_erase(cont.find(2));
	ASSERT(it4 == cont.end() && cont.size() == 0, "Erase did not remove the last element properly");

	// template<class InputIterator> void insert(InputIterator first, InputIterator last);
	cont.insert(newcont.begin(), newcont.end());
	ASSERT(T::allow_multimapping ? (cont.size() == 3) : (cont.size() == 2), "Range insert did not copy the elements properly");

	// iterator unsafe_erase(const_iterator first, const_iterator last);
	std::pair<typename T::iterator, typename T::iterator> range2 = newcont.equal_range(1);
	newcont.unsafe_erase(range2.first, range2.second);
	ASSERT(newcont.size() == 1, "Range erase did not erase the elements properly");

	// void clear();
	newcont.clear();
	ASSERT(newcont.begin() == newcont.end() && newcont.size() == 0, "Clear did not clear the container");

	// T& operator=(const T& _Umap)
	newcont = ccont;
	ASSERT(T::allow_multimapping ? (newcont.size() == 3) : (newcont.size() == 2), "Assignment operator did not copy the elements properly");

	// void rehash(size_type n);
	newcont.rehash(16);
	ASSERT(T::allow_multimapping ? (newcont.size() == 3) : (newcont.size() == 2), "Rehash should not affect the container elements");

	// float load_factor() const;
	// float max_load_factor() const;
	ASSERT(ccont.load_factor() <= ccont.max_load_factor(), "Load factor invalid");

	// void max_load_factor(float z);
	cont.max_load_factor(16.0f);
	ASSERT(ccont.max_load_factor() == 16.0f, "Max load factor not properly changed");

	// hasher hash_function() const;
	ccont.hash_function();

	// key_equal key_eq() const;
	ccont.key_eq();

	cont.clear();
	CheckAllocatorA(cont, 1, 0); // one dummy is always allocated
	for (int i = 0; i < 256; i++)
	{
	std::pair<typename T::iterator, bool> ins3 = cont.insert(Value<T>::make(i));
	ASSERT(ins3.second == true && Value<T>::get(*(ins3.first)) == i, "Element 1 not properly inserted");
	}
	ASSERT(cont.size() == 256, "Wrong number of elements inserted");
	ASSERT(256 == CheckRecursiveRange<typename T::iterator>(cont.range()).first, NULL);
	ASSERT(256 == CheckRecursiveRange<typename T::const_iterator>(ccont.range()).first, NULL);

	// size_type unsafe_bucket_count() const;
	ASSERT(ccont.unsafe_bucket_count() == 16, "Wrong number of buckets");

	// size_type unsafe_max_bucket_count() const;
	ASSERT(ccont.unsafe_max_bucket_count() > 65536, "Wrong max number of buckets");

	for (unsigned int i = 0; i < 256; i++)
	{
	typename T::size_type buck = ccont.unsafe_bucket(i);

	// size_type unsafe_bucket(const key_type& k) const;
	ASSERT(buck < 16, "Wrong bucket mapping");
	}

	for (unsigned int i = 0; i < 16; i++)
	{
	// size_type unsafe_bucket_size(size_type n);
	ASSERT(cont.unsafe_bucket_size(i) == 16, "Wrong number elements in a bucket");

	// local_iterator unsafe_begin(size_type n);
	// const_local_iterator unsafe_begin(size_type n) const;
	// local_iterator unsafe_end(size_type n);
	// const_local_iterator unsafe_end(size_type n) const;
	// const_local_iterator unsafe_cbegin(size_type n) const;
	// const_local_iterator unsafe_cend(size_type n) const;
	unsigned int count = 0;
	for (typename T::iterator bit = cont.unsafe_begin(i); bit != cont.unsafe_end(i); bit++)
	{
	count++;
	}
	ASSERT(count == 16, "Bucket iterators are invalid");
	}

	// void swap(T&);
	cont.swap(newcont);
	ASSERT(newcont.size() == 256, "Wrong number of elements after swap");
	ASSERT(newcont.count(200) == 1, "Element with key 200 not present after swap");
	ASSERT(newcont.count(16) == 1, "Element with key 16 not present after swap");
	ASSERT(newcont.count(99) == 1, "Element with key 99 not present after swap");
	ASSERT(T::allow_multimapping ? (cont.size() == 3) : (cont.size() == 2), "Wrong number of elements after swap");

	REMARK("passed -- basic %S tests\n", str);

	#if defined (VERBOSE)
	REMARK("container dump debug:\n");
	cont._Dump();
	REMARK("container dump release:\n");
	cont.dump();
	REMARK("\n");
	#endif

	SpecialTests<T>::Test();
	}

	void test_machine() {
	ASSERT(__TBB_ReverseByte(0)==0, NULL );
	ASSERT(__TBB_ReverseByte(1)==0x80, NULL );
	ASSERT(__TBB_ReverseByte(0xFE)==0x7F, NULL );
	ASSERT(__TBB_ReverseByte(0xFF)==0xFF, NULL );
	}

	template<typename T>
	class FillTable: NoAssign {
	T &table;
	const int items;
	typedef std::pair<typename T::iterator, bool> pairIB;
	public:
	FillTable(T &t, int i) : table(t), items(i) {
	ASSERT( !(items&1) && items > 100, NULL);
	}
	void operator()(int threadn) const {
	if( threadn == 0 ) { // Fill even keys forward (single thread)
	bool last_inserted = true;
	for( int i = 0; i < items; i+=2 ) {
	pairIB pib = table.insert(Value<T>::make(i));
	ASSERT(Value<T>::get(*(pib.first)) == i, "Element not properly inserted");
	ASSERT( last_inserted \|\| !pib.second, "Previous key was not inserted but this is inserted" );
	last_inserted = pib.second;
	}
	} else if( threadn == 1 ) { // Fill even keys backward (single thread)
	bool last_inserted = true;
	for( int i = items-2; i >= 0; i-=2 ) {
	pairIB pib = table.insert(Value<T>::make(i));
	ASSERT(Value<T>::get(*(pib.first)) == i, "Element not properly inserted");
	ASSERT( last_inserted \|\| !pib.second, "Previous key was not inserted but this is inserted" );
	last_inserted = pib.second;
	}
	} else if( !(threadn&1) ) { // Fill odd keys forward (multiple threads)
	for( int i = 1; i < items; i+=2 ) {
	pairIB pib = table.insert(Value<T>::make(i));
	ASSERT(Value<T>::get(*(pib.first)) == i, "Element not properly inserted");
	}
	} else { // Check odd keys backward (multiple threads)
	bool last_found = false;
	for( int i = items-1; i >= 0; i-=2 ) {
	typename T::iterator it = table.find(i);
	if( it != table.end() ) { // found
	ASSERT(Value<T>::get(*it) == i, "Element not properly inserted");
	last_found = true;
	} else ASSERT( !last_found, "Previous key was found but this is not" );
	}
	}
	}
	};

	typedef tbb::atomic<unsigned char> AtomicByte;

	template<typename RangeType>
	struct ParallelTraverseBody: NoAssign {
	const int n;
	AtomicByte* const array;
	ParallelTraverseBody( AtomicByte an_array[], int a_n ) :
	n(a_n), array(an_array)
	{}
	void operator()( const RangeType& range ) const {
	for( typename RangeType::iterator i = range.begin(); i!=range.end(); ++i ) {
	int k = i->first;
	ASSERT( k == i->second, NULL );
	ASSERT( 0<=k && k<n, NULL );
	array[k]++;
	}
	}
	};

	void CheckRange( AtomicByte array[], int n ) {
	for( int k=0; k<n; ++k ) {
	if( array[k] != 1 ) {
	REPORT("array[%d]=%d\n", k, int(array[k]));
	ASSERT(false,NULL);
	}
	}
	}

	template<typename T>
	void test_concurrent(const char *tablename) {
	T table;
	#if TBB_USE_ASSERT
	int items = 2000;
	#else
	int items = 100000;
	#endif
	tbb::tick_count t0 = tbb::tick_count::now();
	NativeParallelFor( 16/min 6/, FillTable<T>(table, items) );
	tbb::tick_count t1 = tbb::tick_count::now();
	REMARK( "time for filling '%s' by %d items = %g\n", tablename, items, (t1-t0).seconds() );
	ASSERT( int(table.size()) == items, NULL);

	AtomicByte* array = new AtomicByte[items];
	memset( array, 0, items*sizeof(AtomicByte) );

	typename T::range_type r = table.range();
	ASSERT(items == CheckRecursiveRange<typename T::iterator>(r).first, NULL);
	tbb::parallel_for( r, ParallelTraverseBody<typename T::const_range_type>( array, items ));
	CheckRange( array, items );

	const T &const_table = table;
	memset( array, 0, items*sizeof(AtomicByte) );
	typename T::const_range_type cr = const_table.range();
	ASSERT(items == CheckRecursiveRange<typename T::const_iterator>(cr).first, NULL);
	tbb::parallel_for( cr, ParallelTraverseBody<typename T::const_range_type>( array, items ));
	CheckRange( array, items );

	delete[] array;

	table.clear();
	CheckAllocatorA(table, items+1, items); // one dummy is always allocated
	}

	int TestMain () {
	test_machine();
	test_basic<Mycumap>("concurrent unordered map");
	test_concurrent<Mycumap>("concurrent unordered map");
	return Harness::Done;
	}