mergesort.cpp File Reference

Mergesort example. More...

#include <boost/threadpool.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/smart_ptr.hpp>
#include <iostream>
#include <sstream>
#include <algorithm>

Include dependency graph for mergesort.cpp:

Go to the source code of this file.

Classes
class	image
class	merge_job< T >

Functions
void	print (string text)
template<class T >
string	to_string (const T &value)
unsigned long	get_ms_diff (boost::xtime &start, boost::xtime &end)
int	main (int argc, char *const argv[])

Variables
boost::mutex	m_io_monitor

Detailed Description

Mergesort example.

This example shows how to use the threadpool library.

Copyright (c) 2005-2006 Philipp Henkel

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)

http://threadpool.sourceforge.net

Definition in file mergesort.cpp.

Function Documentation

unsigned long get_ms_diff	(	boost::xtime &	start,
		boost::xtime &	end
	)

Definition at line 48 of file mergesort.cpp.

{
  boost::xtime::xtime_sec_t start_ms = start.sec * 1000 + start.nsec/1000000; 
  boost::xtime::xtime_sec_t end_ms = end.sec * 1000 + end.nsec/1000000; 
  return static_cast<unsigned long>(end_ms - start_ms);
}

int main	(	int	argc,
		char *const	argv[]
	)

Definition at line 125 of file mergesort.cpp.

{
  print("MAIN: construct thread pool\n");

        

  boost::xtime start;
  boost::xtime_get(&start, boost::TIME_UTC);

  int exponent = 7;
  int data_len = 1 << exponent;  // = pow(2, exponent) 

  print("MAIN: sort array with "+ to_string(data_len) + " elements.\n");

  boost::shared_array<image> data(new image[data_len]);

  // fill array with arbitrary values (not sorted ascendingly)
  for(int i = 0; i < data_len; i++)
  {
    data[i] = image((data_len - i - 1) % 23);
  }


  /***************************/
  /* Standard implementation */
  /***************************/

  pool tp;
  tp.size_controller().resize(5);   

// merge data array
  for(int step = 1; step <= exponent; step++)
  {
    print("\nMAIN: merge step "+ to_string(step)+"\n");

    // divide array into partitions
    int partition_size = 1 << step;
    for(int partition = 0; partition < data_len/partition_size; partition++)
    {
      // sort partition
      boost::shared_ptr<merge_job<image> > job(new merge_job<image>(data, partition*partition_size, partition_size));
      //tp->schedule(prio_task_func(5, boost::bind(&merge_job<image>::run, job)));
      schedule(tp, boost::bind(&merge_job<image>::run, job));
     // schedule(tp, job);
    }
    tp.wait();  // wait until all partitions are sorted
  } 

  boost::xtime end;
  boost::xtime_get(&end, boost::TIME_UTC);              

  print("\nMAIN: duration " + to_string(get_ms_diff(start, end)) + " ms \n");

  print("\nMAIN: check if array is sorted... \n");

  // check if array is sorted ascendingly 
  bool ascending = true;
  for(int i = 0; i < data_len-1; i++)
  {
    if(data[i+1] < data[i])
    {
      ascending = false;
    }
  }

  if(ascending)
  {
    print("\nMAIN: array is sorted\n");
  }
  else
  {
    print("\nMAIN: array is NOT sorted!\n");
  }

  return 0;
}

void print

(

string

text

)

Definition at line 33 of file mergesort.cpp.

{
  boost::mutex::scoped_lock lock(m_io_monitor);
  cout << text;
}

template<class T >

string to_string

(

const T &

value

)

Definition at line 40 of file mergesort.cpp.

{
  ostringstream ost;
  ost << value;
  ost.flush();
  return ost.str();
}

Variable Documentation

boost::mutex m_io_monitor

Definition at line 31 of file mergesort.cpp.