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

#include "nmglobal.h"
#include "nbench1.h"


/*********************
** NUMERIC HEAPSORT **
**********************
** This test implements a heapsort algorithm, performed on an
** array of longs.
*/
static unsigned long 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)
{
        /* Error context string pointer */
        const char *context = "CPU:Numeric Sort";
        /* Local pointer to global struct */
        SortStruct * numsortstruct = &global_numsortstruct;

        long accumtime;         /* Accumulated time */
        double iterations;      /* Iteration counter */
        long *arraybase = NULL; /* Base pointers of array */

        /*
        ** See if we need to do self adjustment code.
        */
        if (numsortstruct->adjust == 0) {
        	/*
        	** 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.
        */
        accumtime = 0L;
        iterations = 0.0;

        do {
                accumtime += DoNumSortIteration(arraybase, numsortstruct->arraysize, numsortstruct->numarrays);
                iterations += 1.0;
        } while ( TicksToSecs(accumtime) < numsortstruct->request_secs );

        /*
        ** Clean up, calculate results, and go home.  Be sure to
        ** show that we don't have to rerun adjustment code.
        */
        free(arraybase);

        numsortstruct->sortspersec = iterations * (double)numsortstruct->numarrays / TicksToFracSecs(accumtime);

        if (numsortstruct->adjust == 0) {
                numsortstruct->adjust = 1;
        }
}

/***********************
** DoNumSortIteration **
************************
** This routine executes one iteration of the numeric
** sort benchmark.  It returns the number of ticks
** elapsed for the iteration.
*/
static unsigned long
DoNumSortIteration(long *arraybase, unsigned long arraysize, unsigned int numarrays)
{
        unsigned long elapsed;          /* Elapsed ticks */
        unsigned long i;

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

        /*
        ** Start the stopwatch
        */
        elapsed = StartStopwatch();

        /*
        ** Execute a heap of heapsorts
        */
        for (i = 0; i < numarrays; i++) {
        	NumHeapSort(arraybase + i * arraysize, 0L, arraysize - 1L);
        }

        /*
        ** Get elapsed time
        */
        elapsed = StopStopwatch(elapsed);

        return(elapsed);
}

/*************************
** LoadNumArrayWithRand **
**************************
** Load up an array with random longs.
*/
static void
LoadNumArrayWithRand(long *array,               /* Pointer to arrays */
		unsigned long arraysize,
		unsigned int numarrays)         /* # of elements in array */
{
        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;
                }
        }
}