Pasted

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <time.h>
 
void quicksort (int *A, int len);
 
#define MIN_LENGTH 4
 
int DEBUG;
 
typedef struct
{
  int *array;
  int left;
  int right;
  int tid;
} thread_data_t;
 
int number_of_threads;
pthread_mutex_t lock_number_of_threads;
 
int
my_comp (const void *larg, const void *rarg)
{
  int l = *(int *) larg;
  int r = *(int *) rarg;
  if (l < r)
    {
      return -1;
    }
  else if (l == r)
    {
      return 0;
    }
  return 1;
}
 
void
merge (int *data, int left, int right, int tid)
{
  if (DEBUG)
    {
      printf ("[%d] Merging %d to %d\n", tid, left, right);
    }
  int ctr = 0;
  int i = left;
  int mid = left + ((right - left) / 2);
  int j = mid + 1;
  int *c = (int *) malloc ((right - left + 1) * sizeof (int));
  while (i <= mid && j <= right)
    {
      if (data[i] <= data[j])
    {
      c[ctr++] = data[i++];
    }
      else
    {
      c[ctr++] = data[j++];
    }
    }
  if (i == mid + 1)
    {
      while (j <= right)
    {
      c[ctr++] = data[j++];
    }
    }
  else
    {
      while (i <= mid)
    {
      c[ctr++] = data[i++];
    }
    }
  i = left;
  ctr = 0;
  while (i <= right)
    {
      data[i++] = c[ctr++];
    }
  free (c);
  return;
}
 
void *
merge_sort_threaded (void *arg)
{
  thread_data_t *data = (thread_data_t *) arg;
  int l = data->left;
  int r = data->right;
  int t = data->tid;
  if (r - l + 1 <= MIN_LENGTH)
    {
      if (DEBUG)
    {
      printf ("[%d] Calling qsort(%d, %d).\n", t, l, r);
    }
      qsort (data->array + l, r - l + 1, sizeof (int), my_comp);
    }
  else
    {
      int m = l + ((r - l) / 2);
      thread_data_t data_0;
      data_0.left = l;
      data_0.right = m;
      data_0.array = data->array;
      pthread_mutex_lock (&lock_number_of_threads);
      data_0.tid = number_of_threads++;
      pthread_mutex_unlock (&lock_number_of_threads);
      pthread_t thread0;
                   NULL,
                   merge_sort_threaded,
                   &data_0);
      if (rc)
    {
      if (DEBUG)
        {
              data_0.tid);
        }
      qsort (data->array + l, m - l + 1, sizeof (int), my_comp);
    }
      thread_data_t data_1;
      data_1.left = m + 1;
      data_1.right = r;
      data_1.array = data->array;
      pthread_mutex_lock (&lock_number_of_threads);
      data_1.tid = number_of_threads++;
      pthread_mutex_unlock (&lock_number_of_threads);
      pthread_t thread1;
      if (rc)
    {
      if (DEBUG)
        {
              data_1.tid);
        }
      qsort (data->array + m + 1, r - m, sizeof (int), my_comp);
    }
    {
      pthread_join (thread0, NULL);
    }
    {
      pthread_join (thread1, NULL);
    }
      merge (data->array, l, r, t);
    }
  pthread_exit (NULL);
  return NULL;
}
 
void
merge_sort (int *array, int start, int finish)
{
  thread_data_t data;
  data.array = array;
  data.left = start;
  data.right = finish;
 
  number_of_threads = 0;
  pthread_mutex_init (&lock_number_of_threads, NULL);
  data.tid = 0;
  pthread_t thread;
               NULL,
               merge_sort_threaded,
               &data);
  if (rc)
    {
      if (DEBUG)
    {
    }
      qsort (array + start, finish - start + 1, sizeof (int), my_comp);
    }
  pthread_join (thread, NULL);
  return;
}
 
 
 
 
int
max (int *a, int n, int i, int j, int k)
{
  int m = i;
  if (j < n && a[j] > a[m])
    {
      m = j;
    }
  if (k < n && a[k] > a[m])
    {
      m = k;
    }
  return m;
}
 
void
downheap (int *a, int n, int i)
{
  while (1)
    {
      int j = max (a, n, i, 2 * i + 1, 2 * i + 2);
      if (j == i)
    {
      break;
    }
      int t = a[i];
      a[i] = a[j];
      a[j] = t;
      i = j;
    }
}
 
void
heapsort (int *a, int n)
{
  int i;
  for (i = (n - 2) / 2; i >= 0; i--)
    {
      downheap (a, n, i);
    }
  for (i = 0; i < n; i++)
    {
      int t = a[n - i - 1];
      a[n - i - 1] = a[0];
      a[0] = t;
      downheap (a, n - i - 1, 0);
    }
}
 
void
quicksort (int *A, int len)
{
  if (len < 2)
    return;
 
  int pivot = A[len / 2];
 
  int i, j;
  for (i = 0, j = len - 1;; i++, j--)
    {
      while (A[i] < pivot)
    i++;
      while (A[j] > pivot)
    j--;
 
      if (i >= j)
    break;
 
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
 
  quicksort (A, i);
  quicksort (A + i, len - i);
}
 
 
 
 
int
main ()
{
 
 
 
  printf ("Select benchmark mode");
  printf ("\n(1) Multthread Mergesort (Using POPCNT)\n");
  printf ("(2) Singlethread Heapsort (Using BMI)\n");
  printf ("(3) Exit\n");
 
  int selval, mode;
  scanf ("%d", &selval);
  if (selval < 1 || selval > 3)
    {
      printf ("Invalid input.. aborting!");
      return 0;
    }
  mode = selval;
  printf ("\nSimple Heapsort benchmarking tool\n");
  printf ("\nCopyright (C) 2017  Fabian Druschke (Knogle)");
  printf
  printf
    ("\nThis is free software, and you are welcome to redistribute it \n \n \n");
    if (selval == 3)
    {
      return 1;
    }
  sleep (3);
  if (mode == 1)
    {
      int size = 100000000, loop, qrand;
      int *array;
      array = (int *) malloc (size * sizeof (int));
      if (array != NULL)
    {
      if ((size * sizeof (int)) < 1000)
        {
          printf ("\n %lu Bytes allocated\n", (size * sizeof (int)));
        }
      else if ((size * sizeof (int)) >= 1000)
        {
          printf ("\n %lu Kilobytes allocated\n",
              ((size * sizeof (int)) / 1000));
        }
      else if ((size * sizeof (int)) >= 1000 * 1000)
        {
          printf ("\n %lu Megabytes allocated\n",
              ((size * sizeof (int)) / 1000 * 1000));
        }
      sleep (1);
      printf ("\nFilling array.\n");
      sleep (3);
      srand ( time(NULL) );
      for (loop = 0; loop < size; loop++)
        {
          qrand = rand () % 20;
          array[loop] = qrand;
          printf ("%d", qrand);
        }
    }
      else
    printf ("\nKein freier Speicher vorhanden.\n");
 
      printf ("\nMerge Sort..\n");
      clock_t t;
      t = clock ();
      merge_sort (array, 0, size - 1);
      for (loop = 0; loop < size; loop++)
    {
      printf ("%d", array[loop]);
    }
      if ((size * sizeof (int)) < 1000)
    {
      printf ("\n %lu Bytes wurden freigegeben\n", (size * sizeof (int)));
    }
      else if ((size * sizeof (int)) >= 1000)
    {
      printf ("\n %lu Kilobytes wurden freigegeben\n",
          ((size * sizeof (int)) / 1000));
    }
      else if ((size * sizeof (int)) >= 1000 * 1000)
    {
      printf ("\n %lu Megabytes wurden freigegeben\n",
          ((size * sizeof (int)) / 1000 * 1000));
    }
      t = clock () - t;
      printf ("Sorting took %f seconds to finish \n", time_taken);
      double score = (sizeof (int) / time_taken);
      printf ("Your total score: %f", score * 1000);
      printf ("\nPress ENTER to exit");
      getchar ();
      pthread_mutex_destroy (&lock_number_of_threads);
      free (array);
 
    }
  if (mode == 2)
    {
      int size = 100000000, loop, qrand;
      int *array;
      array = (int *) malloc (size * sizeof (int));
      if (array != NULL)
    {
      if ((size * sizeof (int)) < 1000)
        {
          printf ("\n %lu Bytes allocated\n", (size * sizeof (int)));
        }
      else if ((size * sizeof (int)) >= 1000)
        {
          printf ("\n %lu Kilobytes allocated\n",
              ((size * sizeof (int)) / 1000));
        }
      else if ((size * sizeof (int)) >= 1000 * 1000)
        {
          printf ("\n %lu Megabytes allocated\n",
              ((size * sizeof (int)) / 1000 * 1000));
        }
      sleep (1);
      printf ("\nFilling array.\n");
      sleep (3);
      srand ( time(NULL) );
      for (loop = 0; loop < size; loop++)
        {
          qrand = rand () % 20;
          array[loop] = qrand;
          printf ("%d", qrand);
        }
    }
      else
    printf ("\nKein freier Speicher vorhanden.\n");
      printf ("\n\n");
      printf ("\nHeapsort..\n");
      sleep (3);
      clock_t t;
      t = clock ();
      heapsort (array, size);
      for (loop = 0; loop < size; loop++)
    {
      printf ("%d", array[loop]);
    }
      if ((size * sizeof (int)) < 1000)
    {
      printf ("\n %lu Bytes reallocated\n", (size * sizeof (int)));
    }
      else if ((size * sizeof (int)) >= 1000)
    {
      printf ("\n %lu Kilobytes reallocated\n",
          ((size * sizeof (int)) / 1000));
    }
      else if ((size * sizeof (int)) >= 1000 * 1000)
    {
      printf ("\n %lu Megabytes reallocated\n",
          ((size * sizeof (int)) / 1000 * 1000));
    }
      free (array);
      t = clock () - t;
      printf ("Sorting took %f seconds to finish \n", time_taken);
      double score = (sizeof (int) / time_taken);
      printf ("Your total score: %f", score * 1000);
      printf ("\nPress ENTER to exit");
      getchar();
    }
 
  return 0;
}