#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <time.h>

#include "cleanbench.h"
#include "randnum.h"


/*********************
** NUMERIC HEAPSORT **
**********************
** This test implements a heapsort algorithm, performed on an
** array of longs.
*/

/*
** The following constant NUMARRAYSIZE determines the
** default # of elements in each numeric array
*/
#define ARRAY_SIZE    8111

static clock_t DoNumSortIteration(long *array, unsigned int num_arrays);
static void LoadNumArrayWithRand(long *array, unsigned int num_arrays);
static void NumHeapSort(long *array, unsigned long bottom, unsigned long top);
static void NumSift(long *array, unsigned long min, unsigned long max);

/**************
** DoNumSort **
***************
** This routine performs the CPU numeric sort test.
*/

double
DoNumSort (void)
{
        long*           array = NULL;
        clock_t         total_time = 0;
        int             iterations = 0;
        static int      num_arrays = 0;
        static bool     is_adjusted = false;

        if (is_adjusted == false) {
                is_adjusted = true;
        	/*
        	** Self-is_adjustedment code. The system begins by sorting 1
        	** array. If it does that in no time, then two arrays
        	** are built and sorted. This process continues until
                ** enough arrays are built to handle the tolerance.
                */

                do {
                        ++num_arrays;

                        array = realloc(array, num_arrays * ARRAY_SIZE * sizeof(long));

                        /*
                        ** Do an iteration of the numeric sort. If the
                        ** elapsed time is less than or equal to the permitted
                        ** minimum, then allocate for more arrays and
                        ** try again.
                        */
                } while (DoNumSortIteration(array, num_arrays) <= MINIMUM_TICKS);
        } else {
                array = malloc(num_arrays * ARRAY_SIZE * sizeof(long));
        }

        /*
        ** All's well if we get here.  Repeatedly perform sorts until the
        ** accumulated elapsed time is greater than # of seconds requested.
        */

        do {
                total_time += DoNumSortIteration(array, num_arrays);
                ++iterations;
        } while (total_time < MINIMUM_SECONDS * CLOCKS_PER_SEC);

        free(array);

        return (double)(iterations * num_arrays * CLOCKS_PER_SEC) / (double)total_time;
}

/***********************
** DoNumSortIteration **
************************
** This routine executes one iteration of the numeric
** sort benchmark.  It returns the number of ticks
** elapsed for the iteration.
*/
static clock_t
DoNumSortIteration(long *array, unsigned int num_arrays)
{
        clock_t start, stop;
        unsigned long i;

        /*
        ** Load up the array with random numbers
        */
        LoadNumArrayWithRand(array, num_arrays);

        start = clock();

        for (i = 0; i < num_arrays; i++) {
        	NumHeapSort(&array[i], 0, ARRAY_SIZE - 1);
        }

        stop = clock();

        return stop - start;
}

/*************************
** LoadNumArrayWithRand **
**************************
** Load up an array with random longs.
*/
static void
LoadNumArrayWithRand(long *array, unsigned int num_arrays)
{
        long i;              /* Used for index */
        long *darray;        /* Destination array pointer */

        /* Initialize the random number generator */
        randnum(13);

        /* Load up first array with randoms */
        for (i = 0; i < ARRAY_SIZE; i++) {
        	array[i] = randnum(0);
        }

        /*
        ** Now, if there's more than one array to load, copy the
        ** first into each of the others.
        */
        darray = array;
        while (--num_arrays) {
                darray += ARRAY_SIZE;
                memcpy(darray, array, ARRAY_SIZE * sizeof(long));
        }
}

/****************
** NumHeapSort **
*****************
** Pass this routine a pointer to an array of long
** integers.  Also pass in minimum and maximum offsets.
** This routine performs a heap sort on that array.
*/
static void
NumHeapSort(long *array, unsigned long bottom, unsigned long top)
{
        unsigned long temp;                     /* Used to exchange elements */
        unsigned long i;                        /* Loop index */

        /*
        ** First, build a heap in the array
        */
        for (i = (top / 2L); i > 0; i--) {
        	NumSift(array, i, top);
        }

        /*
        ** Repeatedly extract maximum from heap and place it at the
        ** end of the array.  When we get done, we'll have a sorted
        ** array.
        */
        for (i = top; i > 0; i--) {
                NumSift(array, bottom, i);

        	temp = *array;
        	*array = *(array + i);
        	*(array + i) = temp;
        }
}

/************
** NumSift **
*************
** Peforms the sift operation on a numeric array,
** constructing a heap in the array.
*/
static void
NumSift(long *array, unsigned long min, unsigned long max)
{
        unsigned long k;
        unsigned long temp;     /* Used for exchange */

        while ( ( min * 2 ) <= max ) {
        	k = min * 2;
        	if ( k < max ) {
        		if ( array[k] < array[k+1L] ) {
        			++k;
                        }
                }

        	if ( array[min] < array[k] ) {
        		temp = array[k];
	        	array[k] = array[min];
		        array[min] = temp;
        		min = k;
        	} else {
                        min = max + 1;
                }
        }
}