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

#include "nmglobal.h"
#include "randnum.h"


/*********************
** NUMERIC HEAPSORT **
**********************
** This test implements a heapsort algorithm, performed on an
** array of longs.
*/
static clock_t DoNumSortIteration(long *arraybase, unsigned long arraysize, unsigned int numarrays);
static void LoadNumArrayWithRand(long *array, unsigned long arraysize, unsigned int numarrays);
static inline void NumHeapSort(long *array, unsigned long bottom, unsigned long top);
static inline void NumSift(long *array, unsigned long min, unsigned long max);

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

void
DoNumSort (void)
{
        const char*     context = "CPU:Numeric Sort";
        SortStruct*     numsortstruct = &global_numsortstruct;
        clock_t         total_time = 0;
        int             iterations = 0;
        long*           arraybase = NULL;

        /*
        ** See if we need to do self adjustment code.
        */
        if (numsortstruct->adjust == FALSE) {
                numsortstruct->adjust = TRUE;
        	/*
        	** Self-adjustment 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.
                */
                numsortstruct->numarrays = 1;

                while (1) {
                        arraybase = realloc(arraybase, numsortstruct->numarrays * numsortstruct->arraysize * sizeof(long));
                        if (!arraybase) {
                                fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
                                exit(1);
                        }

                        /*
                        ** 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.
                        */
                        if (DoNumSortIteration(arraybase, numsortstruct->arraysize, numsortstruct->numarrays) > global_min_ticks) {
                                break;
                        }

                        if (numsortstruct->numarrays > NUMNUMARRAYS) {
                                puts("CPU:NSORT -- NUMNUMARRAYS hit.");
                        }
                        ++numsortstruct->numarrays;
                }
        } else {
                arraybase = malloc(numsortstruct->numarrays * numsortstruct->arraysize * sizeof(long));
                if (!arraybase) {
                        fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
                        exit(1);
                }
        }

        /*
        ** 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(arraybase, numsortstruct->arraysize, numsortstruct->numarrays);
                ++iterations;
        } while (total_time < numsortstruct->request_secs * CLOCKS_PER_SEC);

        free(arraybase);

        numsortstruct->sortspersec = (double)(iterations * numsortstruct->numarrays * 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 *arraybase, unsigned long arraysize, unsigned int numarrays)
{
        clock_t start, stop;
        unsigned long i;

        /*
        ** Load up the array with random numbers
        */
        LoadNumArrayWithRand(arraybase, arraysize, numarrays);

        start = clock();

        for (i = 0; i < numarrays; i++) {
        	NumHeapSort(&arraybase[i], 0L, arraysize - 1L);
        }

        stop = clock();

        return stop - start;
}

/*************************
** LoadNumArrayWithRand **
**************************
** Load up an array with random longs.
*/
static void
LoadNumArrayWithRand(long *array, unsigned long arraysize, unsigned int numarrays)
{
        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 < arraysize; 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 (--numarrays) {
                darray += arraysize;
                memcpy(darray, array, arraysize * 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 inline 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 inline 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;
                }
        }
}