src/parsec/disk-image/parsec/parsec-benchmark/pkgs/libs/tbblib/src/src/test/test_parallel_sort.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.
 */

 #include "tbb/parallel_sort.h"
 #include "tbb/task_scheduler_init.h"
 #include "tbb/concurrent_vector.h"
 #include "harness.h"
 #include <math.h>
 #include <exception>

 #if !TBB_USE_EXCEPTIONS && _MSC_VER
     // Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
     #pragma warning (push)
     #pragma warning (disable: 4530)
 #endif

 #include <algorithm>
 #include <iterator>
 #include <functional>
 #include <string>
 #include <cstring>

 #if !TBB_USE_EXCEPTIONS && _MSC_VER
     #pragma warning (pop)
 #endif

 /** Has tightly controlled interface so that we can verify
     that parallel_sort uses only the required interface. */
 class Minimal {
     int val;
 public:
     Minimal() {}
     void set_val(int i) { val = i; }
     static bool CompareWith (const Minimal &a, const Minimal &b) {
         return (a.val < b.val);
     }
     static bool AreEqual( Minimal &a,  Minimal &b) {
        return a.val == b.val;
     }
 };

 //! Defines a comparison function object for Minimal
 class MinimalCompare {
 public:
     bool operator() (const Minimal &a, const Minimal &b) const {
         return Minimal::CompareWith(a,b);
     }
 };

 //! The default validate; but it uses operator== which is not required
 template<typename RandomAccessIterator>
 bool Validate(RandomAccessIterator a, RandomAccessIterator b, size_t n) {
     for (size_t i = 0; i < n; i++) {
         ASSERT( a[i] == b[i], NULL );
     }
     return true;
 }

 //! A Validate specialized to string for debugging-only
 template<>
 bool Validate<std::string *>(std::string * a, std::string * b, size_t n) {
     for (size_t i = 0; i < n; i++) {
         if ( Verbose && a[i] != b[i]) {
           for (size_t j = 0; j < n; j++) {
               REPORT("a[%llu] == %s and b[%llu] == %s\n", static_cast<unsigned long long>(j), a[j].c_str(), static_cast<unsigned long long>(j), b[j].c_str());
           }
         }
         ASSERT( a[i] == b[i], NULL );
     }
     return true;
 }

 //! A Validate specialized to Minimal since it does not define an operator==
 template<>
 bool Validate<Minimal *>(Minimal *a, Minimal *b, size_t n) {
     for (size_t i = 0; i < n; i++) {
         ASSERT( Minimal::AreEqual(a[i],b[i]), NULL );
     }
     return true;
 }

 //! A Validate specialized to concurrent_vector<Minimal> since it does not define an operator==
 template<>
 bool Validate<tbb::concurrent_vector<Minimal>::iterator>(tbb::concurrent_vector<Minimal>::iterator a,
                                                          tbb::concurrent_vector<Minimal>::iterator b, size_t n) {
     for (size_t i = 0; i < n; i++) {
         ASSERT( Minimal::AreEqual(a[i],b[i]), NULL );
     }
     return true;
 }

 //! used in Verbose mode for identifying which data set is being used
 static std::string test_type;

 //! The default initialization routine.
 /*! This routine assumes that you can assign to the elements from a float.
     It assumes that iter and sorted_list have already been allocated. It fills
     them according to the current data set (tracked by a local static variable).
     Returns true if a valid test has been setup, or false if there is no test to
     perform.
 */

 template < typename RandomAccessIterator, typename Compare >
 bool init_iter(RandomAccessIterator iter, RandomAccessIterator sorted_list, size_t n, const Compare &compare, bool reset) {
     static char test_case = 0;
     const char num_cases = 3;

     if (reset) test_case = 0;

     if (test_case < num_cases) {
         // switch on the current test case, filling the iter and sorted_list appropriately
         switch(test_case) {
             case 0:
                 /* use sin to generate the values */
                 test_type = "sin";
                 for (size_t i = 0; i < n; i++)
                     iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(sin(float(i)));
                 break;
             case 1:
                 /* presorted list */
                 test_type = "pre-sorted";
                 for (size_t i = 0; i < n; i++)
                     iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(i);
                 break;
             case 2:
                 /* reverse-sorted list */
                 test_type = "reverse-sorted";
                 for (size_t i = 0; i < n; i++)
                     iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(n - i);
                 break;
         }

         // pre-sort sorted_list for later validity testing
         std::sort(sorted_list, sorted_list + n, compare);
         test_case++;
         return true;
     }
     return false;
 }

 template < typename T, typename Compare >
 bool init_iter(T * iter, T * sorted_list, size_t n, const Compare &compare, bool reset) {
     static char test_case = 0;
     const char num_cases = 3;

     if (reset) test_case = 0;

     if (test_case < num_cases) {
         // switch on the current test case, filling the iter and sorted_list appropriately
         switch(test_case) {
             case 0:
                 /* use sin to generate the values */
                 test_type = "sin";
                 for (size_t i = 0; i < n; i++)
                     iter[i] = sorted_list[i] = T(sin(float(i)));
                 break;
             case 1:
                 /* presorted list */
                 test_type = "pre-sorted";
                 for (size_t i = 0; i < n; i++)
                     iter[i] = sorted_list[i] = T(i);
                 break;
             case 2:
                 /* reverse-sorted list */
                 test_type = "reverse-sorted";
                 for (size_t i = 0; i < n; i++)
                     iter[i] = sorted_list[i] = T(n - i);
                 break;
         }

         // pre-sort sorted_list for later validity testing
         std::sort(sorted_list, sorted_list + n, compare);
         test_case++;
         return true;
     }
     return false;
 }


 //! The initialization routine specialized to the class Minimal
 /*! Minimal cannot have floats assigned to it.  This function uses the set_val method
 */

 template < >
 bool init_iter(Minimal* iter, Minimal * sorted_list, size_t n, const MinimalCompare &compare, bool reset) {
     static char test_case = 0;
     const char num_cases = 3;

     if (reset) test_case = 0;

     if (test_case < num_cases) {
         switch(test_case) {
             case 0:
                 /* use sin to generate the values */
                 test_type = "sin";
                 for (size_t i = 0; i < n; i++) {
                     iter[i].set_val( int( sin( float(i) ) * 1000.f) );
                     sorted_list[i].set_val( int ( sin( float(i) ) * 1000.f) );
                 }
                 break;
             case 1:
                 /* presorted list */
                 test_type = "pre-sorted";
                 for (size_t i = 0; i < n; i++) {
                     iter[i].set_val( int(i) );
                     sorted_list[i].set_val( int(i) );
                 }
                 break;
             case 2:
                 /* reverse-sorted list */
                 test_type = "reverse-sorted";
                 for (size_t i = 0; i < n; i++) {
                     iter[i].set_val( int(n-i) );
                     sorted_list[i].set_val( int(n-i) );
                 }
                 break;
         }
         std::sort(sorted_list, sorted_list + n, compare);
         test_case++;
         return true;
     }
     return false;
 }

 //! The initialization routine specialized to the class concurrent_vector<Minimal>
 /*! Minimal cannot have floats assigned to it.  This function uses the set_val method
 */

 template < >
 bool init_iter(tbb::concurrent_vector<Minimal>::iterator iter, tbb::concurrent_vector<Minimal>::iterator sorted_list,
                size_t n, const MinimalCompare &compare, bool reset) {
     static char test_case = 0;
     const char num_cases = 3;

     if (reset) test_case = 0;

     if (test_case < num_cases) {
         switch(test_case) {
             case 0:
                 /* use sin to generate the values */
                 test_type = "sin";
                 for (size_t i = 0; i < n; i++) {
                     iter[i].set_val( int( sin( float(i) ) * 1000.f) );
                     sorted_list[i].set_val( int ( sin( float(i) ) * 1000.f) );
                 }
                 break;
             case 1:
                 /* presorted list */
                 test_type = "pre-sorted";
                 for (size_t i = 0; i < n; i++) {
                     iter[i].set_val( int(i) );
                     sorted_list[i].set_val( int(i) );
                 }
                 break;
             case 2:
                 /* reverse-sorted list */
                 test_type = "reverse-sorted";
                 for (size_t i = 0; i < n; i++) {
                     iter[i].set_val( int(n-i) );
                     sorted_list[i].set_val( int(n-i) );
                 }
                 break;
         }
         std::sort(sorted_list, sorted_list + n, compare);
         test_case++;
         return true;
     }
     return false;
 }

 //! The initialization routine specialized to the class string
 /*! strings are created from floats.
 */

 template<>
 bool init_iter(std::string *iter, std::string *sorted_list, size_t n, const std::less<std::string> &compare, bool reset) {
     static char test_case = 0;
     const char num_cases = 1;

     if (reset) test_case = 0;

     if (test_case < num_cases) {
         switch(test_case) {
             case 0:
                 /* use sin to generate the values */
                 test_type = "sin";
                 for (size_t i = 0; i < n; i++) {
                     char buffer[20];
 #if __STDC_SECURE_LIB__>=200411
                     sprintf_s(buffer, sizeof(buffer), "%f", float(sin(float(i))));
 #else
                     sprintf(buffer, "%f", float(sin(float(i))));
 #endif /* _MSC_VER>=1400 */
                     sorted_list[i] = iter[i] = std::string(buffer);
                 }
                 break;
         }
         std::sort(sorted_list, sorted_list + n, compare);
         test_case++;
         return true;
     }
     return false;
 }

 //! The current number of threads in use (for Verbose only)
 static size_t current_p;

 //! The current data type being sorted (for Verbose only)
 static std::string current_type;

 //! The default test routine.
 /*! Tests all data set sizes from 0 to N, all grainsizes from 0 to G=10, and selects from
     all possible interfaces to parallel_sort depending on whether a scratch space and
     compare have been provided.
 */
 template<typename RandomAccessIterator, typename Compare>
 bool parallel_sortTest(size_t n, RandomAccessIterator iter, RandomAccessIterator sorted_list, const Compare *comp) {
     bool passed = true;

     Compare local_comp;

     init_iter(iter, sorted_list, n, local_comp, true);
     do {
         REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
                    static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));
         if (comp != NULL) {
             tbb::parallel_sort(iter, iter + n, local_comp );
          } else {
             tbb::parallel_sort(iter, iter + n );
          }
         if (!Validate(iter, sorted_list, n))
             passed = false;
         REMARK("passed\n");
     } while (init_iter(iter, sorted_list, n, local_comp, false));
     return passed;
 }

 //! The test routine specialize to Minimal, since it does not have a less defined for it
 template<>
 bool parallel_sortTest(size_t n, Minimal * iter, Minimal * sorted_list, const MinimalCompare *compare) {
     bool passed = true;

     if (compare == NULL) return passed;

     init_iter(iter, sorted_list, n, *compare, true);
     do {
         REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
                     static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));

         tbb::parallel_sort(iter, iter + n, *compare );

         if (!Validate(iter, sorted_list, n))
             passed = false;
         REMARK("passed\n");
     } while (init_iter(iter, sorted_list, n, *compare, false));
     return passed;
 }

 //! The test routine specialize to concurrent_vector of Minimal, since it does not have a less defined for it
 template<>
 bool parallel_sortTest(size_t n, tbb::concurrent_vector<Minimal>::iterator iter,
                        tbb::concurrent_vector<Minimal>::iterator sorted_list, const MinimalCompare *compare) {
     bool passed = true;

     if (compare == NULL) return passed;

     init_iter(iter, sorted_list, n, *compare, true);
     do {
         REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
                     static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));

         tbb::parallel_sort(iter, iter + n, *compare );

         if (!Validate(iter, sorted_list, n))
             passed = false;
         REMARK("passed\n");
     } while (init_iter(iter, sorted_list, n, *compare, false));
     return passed;
 }

 //! The main driver for the tests.
 /*! Minimal, float and string types are used.  All interfaces to parallel_sort that are usable
     by each type are tested.
 */
 void Flog() {
     // For each type create:
     // the list to be sorted by parallel_sort (array)
     // the list to be sort by STL sort (array_2)
     // and a less function object

     const size_t N = 50000;

     Minimal *minimal_array = new Minimal[N];
     Minimal *minimal_array_2 = new Minimal[N];
     MinimalCompare minimal_less;

 #if !__TBB_FLOATING_POINT_BROKEN
     float *float_array = new float[N];
     float *float_array_2 = new float[N];
     std::less<float> float_less;

     tbb::concurrent_vector<float> float_cv1;
     tbb::concurrent_vector<float> float_cv2;
     float_cv1.grow_to_at_least(N);
     float_cv2.grow_to_at_least(N);
 #endif /* !__TBB_FLOATING_POINT_BROKEN */

     std::string *string_array = new std::string[N];
     std::string *string_array_2 = new std::string[N];
     std::less<std::string> string_less;

     tbb::concurrent_vector<Minimal> minimal_cv1;
     tbb::concurrent_vector<Minimal> minimal_cv2;
     minimal_cv1.grow_to_at_least(N);
     minimal_cv2.grow_to_at_least(N);


     // run the appropriate tests for each type

     current_type = "Minimal(less)";
     parallel_sortTest(0, minimal_array, minimal_array_2, &minimal_less);
     parallel_sortTest(1, minimal_array, minimal_array_2, &minimal_less);
     parallel_sortTest(10, minimal_array, minimal_array_2, &minimal_less);
     parallel_sortTest(9999, minimal_array, minimal_array_2, &minimal_less);
     parallel_sortTest(50000, minimal_array, minimal_array_2, &minimal_less);

 #if !__TBB_FLOATING_POINT_BROKEN
     current_type = "float (no less)";
     parallel_sortTest(0, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
     parallel_sortTest(1, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
     parallel_sortTest(10, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
     parallel_sortTest(9999, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
     parallel_sortTest(50000, float_array, float_array_2, static_cast<std::less<float> *>(NULL));

     current_type = "float (less)";
     parallel_sortTest(0, float_array, float_array_2, &float_less);
     parallel_sortTest(1, float_array, float_array_2, &float_less);
     parallel_sortTest(10, float_array, float_array_2, &float_less);
     parallel_sortTest(9999, float_array, float_array_2, &float_less);
     parallel_sortTest(50000, float_array, float_array_2, &float_less);

     current_type = "concurrent_vector<float> (no less)";
     parallel_sortTest(0, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
     parallel_sortTest(1, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
     parallel_sortTest(10, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
     parallel_sortTest(9999, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
     parallel_sortTest(50000, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));

     current_type = "concurrent_vector<float> (less)";
     parallel_sortTest(0, float_cv1.begin(), float_cv2.begin(), &float_less);
     parallel_sortTest(1, float_cv1.begin(), float_cv2.begin(), &float_less);
     parallel_sortTest(10, float_cv1.begin(), float_cv2.begin(), &float_less);
     parallel_sortTest(9999, float_cv1.begin(), float_cv2.begin(), &float_less);
     parallel_sortTest(50000, float_cv1.begin(), float_cv2.begin(), &float_less);
 #endif /* !__TBB_FLOATING_POINT_BROKEN */

     current_type = "string (no less)";
     parallel_sortTest(0, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
     parallel_sortTest(1, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
     parallel_sortTest(10, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
     parallel_sortTest(9999, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
     parallel_sortTest(50000, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));

     current_type = "string (less)";
     parallel_sortTest(0, string_array, string_array_2, &string_less);
     parallel_sortTest(1, string_array, string_array_2, &string_less);
     parallel_sortTest(10, string_array, string_array_2, &string_less);
     parallel_sortTest(9999, string_array, string_array_2, &string_less);
     parallel_sortTest(50000, string_array, string_array_2, &string_less);

     current_type = "concurrent_vector<Minimal> (less)";
     parallel_sortTest(0, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
     parallel_sortTest(1, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
     parallel_sortTest(10, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
     parallel_sortTest(9999, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
     parallel_sortTest(50000, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);

     delete [] minimal_array;
     delete [] minimal_array_2;

 #if !__TBB_FLOATING_POINT_BROKEN
     delete [] float_array;
     delete [] float_array_2;
 #endif /* !__TBB_FLOATING_POINT_BROKEN */

     delete [] string_array;
     delete [] string_array_2;
 }

 #include <cstdio>
 #include "harness_cpu.h"

 int TestMain () {
     if( MinThread<1 ) {
         REPORT("Usage: number of threads must be positive\n");
         exit(1);
     }
     for( int p=MinThread; p<=MaxThread; ++p ) {
         if( p>0 ) {
             tbb::task_scheduler_init init( p );
             current_p = p;
             Flog();

             // Test that all workers sleep when no work
             TestCPUUserTime(p);
         }
     }
     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.
	*/

	#include "tbb/parallel_sort.h"
	#include "tbb/task_scheduler_init.h"
	#include "tbb/concurrent_vector.h"
	#include "harness.h"
	#include <math.h>
	#include <exception>

	#if !TBB_USE_EXCEPTIONS && _MSC_VER
	// Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
	#pragma warning (push)
	#pragma warning (disable: 4530)
	#endif

	#include <algorithm>
	#include <iterator>
	#include <functional>
	#include <string>
	#include <cstring>

	#if !TBB_USE_EXCEPTIONS && _MSC_VER
	#pragma warning (pop)
	#endif

	/** Has tightly controlled interface so that we can verify
	that parallel_sort uses only the required interface. */
	class Minimal {
	int val;
	public:
	Minimal() {}
	void set_val(int i) { val = i; }
	static bool CompareWith (const Minimal &a, const Minimal &b) {
	return (a.val < b.val);
	}
	static bool AreEqual( Minimal &a, Minimal &b) {
	return a.val == b.val;
	}
	};

	//! Defines a comparison function object for Minimal
	class MinimalCompare {
	public:
	bool operator() (const Minimal &a, const Minimal &b) const {
	return Minimal::CompareWith(a,b);
	}
	};

	//! The default validate; but it uses operator== which is not required
	template<typename RandomAccessIterator>
	bool Validate(RandomAccessIterator a, RandomAccessIterator b, size_t n) {
	for (size_t i = 0; i < n; i++) {
	ASSERT( a[i] == b[i], NULL );
	}
	return true;
	}

	//! A Validate specialized to string for debugging-only
	template<>
	bool Validate<std::string >(std::string a, std::string * b, size_t n) {
	for (size_t i = 0; i < n; i++) {
	if ( Verbose && a[i] != b[i]) {
	for (size_t j = 0; j < n; j++) {
	REPORT("a[%llu] == %s and b[%llu] == %s\n", static_cast<unsigned long long>(j), a[j].c_str(), static_cast<unsigned long long>(j), b[j].c_str());
	}
	}
	ASSERT( a[i] == b[i], NULL );
	}
	return true;
	}

	//! A Validate specialized to Minimal since it does not define an operator==
	template<>
	bool Validate<Minimal >(Minimal a, Minimal *b, size_t n) {
	for (size_t i = 0; i < n; i++) {
	ASSERT( Minimal::AreEqual(a[i],b[i]), NULL );
	}
	return true;
	}

	//! A Validate specialized to concurrent_vector<Minimal> since it does not define an operator==
	template<>
	bool Validate<tbb::concurrent_vector<Minimal>::iterator>(tbb::concurrent_vector<Minimal>::iterator a,
	tbb::concurrent_vector<Minimal>::iterator b, size_t n) {
	for (size_t i = 0; i < n; i++) {
	ASSERT( Minimal::AreEqual(a[i],b[i]), NULL );
	}
	return true;
	}

	//! used in Verbose mode for identifying which data set is being used
	static std::string test_type;

	//! The default initialization routine.
	/*! This routine assumes that you can assign to the elements from a float.
	It assumes that iter and sorted_list have already been allocated. It fills
	them according to the current data set (tracked by a local static variable).
	Returns true if a valid test has been setup, or false if there is no test to
	perform.
	*/

	template < typename RandomAccessIterator, typename Compare >
	bool init_iter(RandomAccessIterator iter, RandomAccessIterator sorted_list, size_t n, const Compare &compare, bool reset) {
	static char test_case = 0;
	const char num_cases = 3;

	if (reset) test_case = 0;

	if (test_case < num_cases) {
	// switch on the current test case, filling the iter and sorted_list appropriately
	switch(test_case) {
	case 0:
	/* use sin to generate the values */
	test_type = "sin";
	for (size_t i = 0; i < n; i++)
	iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(sin(float(i)));
	break;
	case 1:
	/* presorted list */
	test_type = "pre-sorted";
	for (size_t i = 0; i < n; i++)
	iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(i);
	break;
	case 2:
	/* reverse-sorted list */
	test_type = "reverse-sorted";
	for (size_t i = 0; i < n; i++)
	iter[i] = sorted_list[i] = static_cast<typename std::iterator_traits< RandomAccessIterator >::value_type>(n - i);
	break;
	}

	// pre-sort sorted_list for later validity testing
	std::sort(sorted_list, sorted_list + n, compare);
	test_case++;
	return true;
	}
	return false;
	}

	template < typename T, typename Compare >
	bool init_iter(T * iter, T * sorted_list, size_t n, const Compare &compare, bool reset) {
	static char test_case = 0;
	const char num_cases = 3;

	if (reset) test_case = 0;

	if (test_case < num_cases) {
	// switch on the current test case, filling the iter and sorted_list appropriately
	switch(test_case) {
	case 0:
	/* use sin to generate the values */
	test_type = "sin";
	for (size_t i = 0; i < n; i++)
	iter[i] = sorted_list[i] = T(sin(float(i)));
	break;
	case 1:
	/* presorted list */
	test_type = "pre-sorted";
	for (size_t i = 0; i < n; i++)
	iter[i] = sorted_list[i] = T(i);
	break;
	case 2:
	/* reverse-sorted list */
	test_type = "reverse-sorted";
	for (size_t i = 0; i < n; i++)
	iter[i] = sorted_list[i] = T(n - i);
	break;
	}

	// pre-sort sorted_list for later validity testing
	std::sort(sorted_list, sorted_list + n, compare);
	test_case++;
	return true;
	}
	return false;
	}


	//! The initialization routine specialized to the class Minimal
	/*! Minimal cannot have floats assigned to it. This function uses the set_val method
	*/

	template < >
	bool init_iter(Minimal* iter, Minimal * sorted_list, size_t n, const MinimalCompare &compare, bool reset) {
	static char test_case = 0;
	const char num_cases = 3;

	if (reset) test_case = 0;

	if (test_case < num_cases) {
	switch(test_case) {
	case 0:
	/* use sin to generate the values */
	test_type = "sin";
	for (size_t i = 0; i < n; i++) {
	iter[i].set_val( int( sin( float(i) ) * 1000.f) );
	sorted_list[i].set_val( int ( sin( float(i) ) * 1000.f) );
	}
	break;
	case 1:
	/* presorted list */
	test_type = "pre-sorted";
	for (size_t i = 0; i < n; i++) {
	iter[i].set_val( int(i) );
	sorted_list[i].set_val( int(i) );
	}
	break;
	case 2:
	/* reverse-sorted list */
	test_type = "reverse-sorted";
	for (size_t i = 0; i < n; i++) {
	iter[i].set_val( int(n-i) );
	sorted_list[i].set_val( int(n-i) );
	}
	break;
	}
	std::sort(sorted_list, sorted_list + n, compare);
	test_case++;
	return true;
	}
	return false;
	}

	//! The initialization routine specialized to the class concurrent_vector<Minimal>
	/*! Minimal cannot have floats assigned to it. This function uses the set_val method
	*/

	template < >
	bool init_iter(tbb::concurrent_vector<Minimal>::iterator iter, tbb::concurrent_vector<Minimal>::iterator sorted_list,
	size_t n, const MinimalCompare &compare, bool reset) {
	static char test_case = 0;
	const char num_cases = 3;

	if (reset) test_case = 0;

	if (test_case < num_cases) {
	switch(test_case) {
	case 0:
	/* use sin to generate the values */
	test_type = "sin";
	for (size_t i = 0; i < n; i++) {
	iter[i].set_val( int( sin( float(i) ) * 1000.f) );
	sorted_list[i].set_val( int ( sin( float(i) ) * 1000.f) );
	}
	break;
	case 1:
	/* presorted list */
	test_type = "pre-sorted";
	for (size_t i = 0; i < n; i++) {
	iter[i].set_val( int(i) );
	sorted_list[i].set_val( int(i) );
	}
	break;
	case 2:
	/* reverse-sorted list */
	test_type = "reverse-sorted";
	for (size_t i = 0; i < n; i++) {
	iter[i].set_val( int(n-i) );
	sorted_list[i].set_val( int(n-i) );
	}
	break;
	}
	std::sort(sorted_list, sorted_list + n, compare);
	test_case++;
	return true;
	}
	return false;
	}

	//! The initialization routine specialized to the class string
	/*! strings are created from floats.
	*/

	template<>
	bool init_iter(std::string iter, std::string sorted_list, size_t n, const std::less<std::string> &compare, bool reset) {
	static char test_case = 0;
	const char num_cases = 1;

	if (reset) test_case = 0;

	if (test_case < num_cases) {
	switch(test_case) {
	case 0:
	/* use sin to generate the values */
	test_type = "sin";
	for (size_t i = 0; i < n; i++) {
	char buffer[20];
	#if __STDC_SECURE_LIB__>=200411
	sprintf_s(buffer, sizeof(buffer), "%f", float(sin(float(i))));
	#else
	sprintf(buffer, "%f", float(sin(float(i))));
	#endif /* _MSC_VER>=1400 */
	sorted_list[i] = iter[i] = std::string(buffer);
	}
	break;
	}
	std::sort(sorted_list, sorted_list + n, compare);
	test_case++;
	return true;
	}
	return false;
	}

	//! The current number of threads in use (for Verbose only)
	static size_t current_p;

	//! The current data type being sorted (for Verbose only)
	static std::string current_type;

	//! The default test routine.
	/*! Tests all data set sizes from 0 to N, all grainsizes from 0 to G=10, and selects from
	all possible interfaces to parallel_sort depending on whether a scratch space and
	compare have been provided.
	*/
	template<typename RandomAccessIterator, typename Compare>
	bool parallel_sortTest(size_t n, RandomAccessIterator iter, RandomAccessIterator sorted_list, const Compare *comp) {
	bool passed = true;

	Compare local_comp;

	init_iter(iter, sorted_list, n, local_comp, true);
	do {
	REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
	static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));
	if (comp != NULL) {
	tbb::parallel_sort(iter, iter + n, local_comp );
	} else {
	tbb::parallel_sort(iter, iter + n );
	}
	if (!Validate(iter, sorted_list, n))
	passed = false;
	REMARK("passed\n");
	} while (init_iter(iter, sorted_list, n, local_comp, false));
	return passed;
	}

	//! The test routine specialize to Minimal, since it does not have a less defined for it
	template<>
	bool parallel_sortTest(size_t n, Minimal * iter, Minimal * sorted_list, const MinimalCompare *compare) {
	bool passed = true;

	if (compare == NULL) return passed;

	init_iter(iter, sorted_list, n, *compare, true);
	do {
	REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
	static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));

	tbb::parallel_sort(iter, iter + n, *compare );

	if (!Validate(iter, sorted_list, n))
	passed = false;
	REMARK("passed\n");
	} while (init_iter(iter, sorted_list, n, *compare, false));
	return passed;
	}

	//! The test routine specialize to concurrent_vector of Minimal, since it does not have a less defined for it
	template<>
	bool parallel_sortTest(size_t n, tbb::concurrent_vector<Minimal>::iterator iter,
	tbb::concurrent_vector<Minimal>::iterator sorted_list, const MinimalCompare *compare) {
	bool passed = true;

	if (compare == NULL) return passed;

	init_iter(iter, sorted_list, n, *compare, true);
	do {
	REMARK("%s %s p=%llu n=%llu :",current_type.c_str(), test_type.c_str(),
	static_cast<unsigned long long>(current_p), static_cast<unsigned long long>(n));

	tbb::parallel_sort(iter, iter + n, *compare );

	if (!Validate(iter, sorted_list, n))
	passed = false;
	REMARK("passed\n");
	} while (init_iter(iter, sorted_list, n, *compare, false));
	return passed;
	}

	//! The main driver for the tests.
	/*! Minimal, float and string types are used. All interfaces to parallel_sort that are usable
	by each type are tested.
	*/
	void Flog() {
	// For each type create:
	// the list to be sorted by parallel_sort (array)
	// the list to be sort by STL sort (array_2)
	// and a less function object

	const size_t N = 50000;

	Minimal *minimal_array = new Minimal[N];
	Minimal *minimal_array_2 = new Minimal[N];
	MinimalCompare minimal_less;

	#if !__TBB_FLOATING_POINT_BROKEN
	float *float_array = new float[N];
	float *float_array_2 = new float[N];
	std::less<float> float_less;

	tbb::concurrent_vector<float> float_cv1;
	tbb::concurrent_vector<float> float_cv2;
	float_cv1.grow_to_at_least(N);
	float_cv2.grow_to_at_least(N);
	#endif /* !__TBB_FLOATING_POINT_BROKEN */

	std::string *string_array = new std::string[N];
	std::string *string_array_2 = new std::string[N];
	std::less<std::string> string_less;

	tbb::concurrent_vector<Minimal> minimal_cv1;
	tbb::concurrent_vector<Minimal> minimal_cv2;
	minimal_cv1.grow_to_at_least(N);
	minimal_cv2.grow_to_at_least(N);


	// run the appropriate tests for each type

	current_type = "Minimal(less)";
	parallel_sortTest(0, minimal_array, minimal_array_2, &minimal_less);
	parallel_sortTest(1, minimal_array, minimal_array_2, &minimal_less);
	parallel_sortTest(10, minimal_array, minimal_array_2, &minimal_less);
	parallel_sortTest(9999, minimal_array, minimal_array_2, &minimal_less);
	parallel_sortTest(50000, minimal_array, minimal_array_2, &minimal_less);

	#if !__TBB_FLOATING_POINT_BROKEN
	current_type = "float (no less)";
	parallel_sortTest(0, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
	parallel_sortTest(1, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
	parallel_sortTest(10, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
	parallel_sortTest(9999, float_array, float_array_2, static_cast<std::less<float> *>(NULL));
	parallel_sortTest(50000, float_array, float_array_2, static_cast<std::less<float> *>(NULL));

	current_type = "float (less)";
	parallel_sortTest(0, float_array, float_array_2, &float_less);
	parallel_sortTest(1, float_array, float_array_2, &float_less);
	parallel_sortTest(10, float_array, float_array_2, &float_less);
	parallel_sortTest(9999, float_array, float_array_2, &float_less);
	parallel_sortTest(50000, float_array, float_array_2, &float_less);

	current_type = "concurrent_vector<float> (no less)";
	parallel_sortTest(0, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
	parallel_sortTest(1, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
	parallel_sortTest(10, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
	parallel_sortTest(9999, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));
	parallel_sortTest(50000, float_cv1.begin(), float_cv2.begin(), static_cast<std::less<float> *>(NULL));

	current_type = "concurrent_vector<float> (less)";
	parallel_sortTest(0, float_cv1.begin(), float_cv2.begin(), &float_less);
	parallel_sortTest(1, float_cv1.begin(), float_cv2.begin(), &float_less);
	parallel_sortTest(10, float_cv1.begin(), float_cv2.begin(), &float_less);
	parallel_sortTest(9999, float_cv1.begin(), float_cv2.begin(), &float_less);
	parallel_sortTest(50000, float_cv1.begin(), float_cv2.begin(), &float_less);
	#endif /* !__TBB_FLOATING_POINT_BROKEN */

	current_type = "string (no less)";
	parallel_sortTest(0, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
	parallel_sortTest(1, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
	parallel_sortTest(10, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
	parallel_sortTest(9999, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));
	parallel_sortTest(50000, string_array, string_array_2, static_cast<std::less<std::string> *>(NULL));

	current_type = "string (less)";
	parallel_sortTest(0, string_array, string_array_2, &string_less);
	parallel_sortTest(1, string_array, string_array_2, &string_less);
	parallel_sortTest(10, string_array, string_array_2, &string_less);
	parallel_sortTest(9999, string_array, string_array_2, &string_less);
	parallel_sortTest(50000, string_array, string_array_2, &string_less);

	current_type = "concurrent_vector<Minimal> (less)";
	parallel_sortTest(0, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
	parallel_sortTest(1, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
	parallel_sortTest(10, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
	parallel_sortTest(9999, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);
	parallel_sortTest(50000, minimal_cv1.begin(), minimal_cv2.begin(), &minimal_less);

	delete [] minimal_array;
	delete [] minimal_array_2;

	#if !__TBB_FLOATING_POINT_BROKEN
	delete [] float_array;
	delete [] float_array_2;
	#endif /* !__TBB_FLOATING_POINT_BROKEN */

	delete [] string_array;
	delete [] string_array_2;
	}

	#include <cstdio>
	#include "harness_cpu.h"

	int TestMain () {
	if( MinThread<1 ) {
	REPORT("Usage: number of threads must be positive\n");
	exit(1);
	}
	for( int p=MinThread; p<=MaxThread; ++p ) {
	if( p>0 ) {
	tbb::task_scheduler_init init( p );
	current_p = p;
	Flog();

	// Test that all workers sleep when no work
	TestCPUUserTime(p);
	}
	}
	return Harness::Done;
	}