#include <stdio.h>
#include <stdint.h>
/*
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <math.h>
*/
#include "nmglobal.h"
#include "nbench1.h"

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

/**************
** DoNumSort **
***************
** This routine performs the CPU numeric sort test.
** NOTE: Last version incorrectly stated that the routine
**  returned result in # of longword sorted per second.
**  Not so; the routine returns # of iterations per sec.
*/

void DoNumSort(void) {
        /* Error context string pointer */
        const char *errorcontext = "CPU:Numeric Sort";
        /* Local pointer to global struct */
        SortStruct * numsortstruct = &global_numsortstruct;

        long accumtime;         /* Accumulated time */
        double iterations;      /* Iteration counter */
        long *arraybase;        /* Base pointers of array */
        int systemerror;        /* For holding error codes */

/*
** 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)
	{
		/*
		** Allocate space for arrays
		*/
		arraybase=(long *)AllocateMemory(sizeof(long) *
			numsortstruct->numarrays * numsortstruct->arraysize,
			&systemerror);
		if(systemerror)
		{       ReportError(errorcontext,systemerror);
			FreeMemory((void *)arraybase,
				  &systemerror);
		}

		/*
		** 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;          /* We're ok...exit */

		FreeMemory((void *)arraybase,&systemerror);
		if(numsortstruct->numarrays++>NUMNUMARRAYS)
		{       printf("CPU:NSORT -- NUMNUMARRAYS hit.\n");
		}
	}
}
else
{       /*
	** Allocate space for arrays
	*/
	arraybase=(long *)AllocateMemory(sizeof(long) *
		numsortstruct->numarrays * numsortstruct->arraysize,
		&systemerror);
	if(systemerror)
	{       ReportError(errorcontext,systemerror);
		FreeMemory((void *)arraybase,
			  &systemerror);
	}

}
/*
** 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+=(double)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.
*/
FreeMemory((void *)arraybase,&systemerror);

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(13L); */
randnum(13);

/*
** Load up first array with randoms
*/
for(i=0L;i<arraysize;i++)
        /* array[i]=randnum(0L); */
	array[i]=randnum((int32_t)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;
	for(i=0L;i<arraysize;i++)
		darray[i]=array[i];
}

return;
}

/****************
** 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,           /* Lower bound */
	unsigned long top)              /* Upper bound */
{
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;                    /* Perform exchange */
	*array=*(array+i);
	*(array+i)=temp;
}
return;
}

/************
** NumSift **
*************
** Peforms the sift operation on a numeric array,
** constructing a heap in the array.
*/
static void NumSift(long *array,/* Array of numbers */
	unsigned long i,        /* Minimum of array */
	unsigned long j)        /* Maximum of array */
{
        unsigned long k;
        unsigned long temp;     /* Used for exchange */

        while ( ( i + i ) <= j ) {
        	k = i + i;
        	if ( k < j ) {
        		if ( array[k] < array[k+1L] ) {
        			++k;
                        }
                }

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