mergesort.cpp File Reference

Mergesort example. More...

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

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 45 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 113 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 30 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 37 of file mergesort.cpp.

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

Variable Documentation

boost::mutex m_io_monitor

Definition at line 28 of file mergesort.cpp.