path: root/stringsort.c

#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"


/********************
** STRING HEAPSORT **
********************/

static clock_t DoStringSortIteration(unsigned char *arraybase,
		unsigned int numarrays,
		unsigned long arraysize);
static unsigned long *LoadStringArray(unsigned char *strarray,
		unsigned int numarrays,
		unsigned long *strings,
		unsigned long arraysize);
static void stradjust(unsigned long *optrarray,
		unsigned char *strarray,
		unsigned long nstrings,
		unsigned long i,
		unsigned char l);
static void StrHeapSort(unsigned long *optrarray,
		unsigned char *strarray,
		unsigned long numstrings,
		unsigned long bottom,
		unsigned long top);
static int str_is_less(unsigned long *optrarray,
		unsigned char *strarray,
		unsigned long numstrings,
		unsigned long a,
		unsigned long b);
static void strsift(unsigned long *optrarray,
		unsigned char *strarray,
		unsigned long numstrings,
		unsigned long i,
		unsigned long j);

/*****************
** DoStringSort **
******************
** This routine performs the CPU string sort test.
** Arguments:
**      requested_secs = # of seconds to execute test
**      stringspersec = # of strings per second sorted (RETURNED)
*/
void DoStringSort(void)
{
        const char*     context = "CPU:String Sort";
        SortStruct*     strsortstruct = &global_strsortstruct;
        unsigned char*  arraybase = NULL;
        clock_t         total_time = 0;
        int             iterations = 0;

        /*
        ** See if we have to perform self-adjustment code
        */
        if (strsortstruct->adjust == FALSE) {
                strsortstruct->adjust = TRUE;
                /*
                ** Initialize the number of arrays.
                */
                strsortstruct->numarrays = 1;
                while (1) {
                        /*
                        ** Allocate space for array.  We'll add an extra 100
                        ** bytes to protect memory as strings move around
                        ** (this can happen during string adjustment)
                        */
                        arraybase = realloc(arraybase, (strsortstruct->arraysize + 100) * strsortstruct->numarrays);
                        if (!arraybase) {
                               fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
                               exit(1);
                        }

                        /*
                        ** Do an iteration of the string sort.  If the
                        ** elapsed time is less than or equal to the permitted
                        ** minimum, then de-allocate the array, reallocate a
                        ** an additional array, and try again.
                        */
                        if (DoStringSortIteration(arraybase, strsortstruct->numarrays, strsortstruct->arraysize) > global_min_ticks) {
                                break;
                        }

                        ++strsortstruct->numarrays;
                }
        } else {
                /*
                ** We don't have to perform self adjustment code.
                ** Simply allocate the space for the array.
                */
                arraybase = malloc((strsortstruct->arraysize + 100) * strsortstruct->numarrays);
                if (!arraybase) {
                        fprintf(stderr, "Error in %s, could not allocate memory. Exitting...\n", context);
                        exit(1);
                }
        }

        do {
                total_time += DoStringSortIteration(arraybase, strsortstruct->numarrays, strsortstruct->arraysize);
                iterations += strsortstruct->numarrays;
        } while (total_time < strsortstruct->request_secs * CLOCKS_PER_SEC);

        free(arraybase);

        strsortstruct->sortspersec = (double)(iterations * CLOCKS_PER_SEC) / (double)total_time;
}

/**************************
** DoStringSortIteration **
***************************
** This routine executes one iteration of the string
** sort benchmark.  It returns the number of ticks
** Note that this routine also builds the offset pointer
** array.
*/
static clock_t
DoStringSortIteration(unsigned char *arraybase, unsigned int numarrays,unsigned long arraysize)
{
        unsigned long *optrarray;            /* Offset pointer array */
        clock_t start, stop;
        unsigned long nstrings;         /* # of strings in array */
        unsigned int i;                 /* Index */
        unsigned long *tempobase;            /* Temporary offset pointer base */
        unsigned char *tempsbase;            /* Temporary string base pointer */

        /*
        ** Load up the array(s) with random numbers
        */
        optrarray=LoadStringArray(arraybase,numarrays,&nstrings,arraysize);

        /*
        ** Set temp base pointers...they will be modified as the
        ** benchmark proceeds.
        */
        tempobase = optrarray;
        tempsbase = arraybase;

        start = clock();

        for(i = 0; i < numarrays; i++) {
                StrHeapSort(tempobase, tempsbase, nstrings, 0L, nstrings - 1);
                tempobase += nstrings;    /* Advance base pointers */
                tempsbase += arraysize+100;
        }

        stop = clock();

        free(optrarray);

        return stop - start;
}

/********************
** LoadStringArray **
*********************
** Initialize the string array with random strings of
** varying sizes.
** Returns the pointer to the offset pointer array.
** Note that since we're creating a number of arrays, this
** routine builds one array, then copies it into the others.
*/
static unsigned long *LoadStringArray(unsigned char *strarray, /* String array */
	unsigned int numarrays,                 /* # of arrays */
	unsigned long *nstrings,                /* # of strings */
	unsigned long arraysize)                /* Size of array */
{
unsigned char *tempsbase;            /* Temporary string base pointer */
unsigned long *optrarray;            /* Local for pointer */
unsigned long *tempobase;            /* Temporary offset pointer base pointer */
unsigned long curroffset;       /* Current offset */
int fullflag;                   /* Indicates full array */
unsigned char stringlength;     /* Length of string */
unsigned char i;                /* Index */
unsigned long j;                /* Another index */
unsigned int k;                 /* Yet another index */
unsigned int l;                 /* Ans still one more index */

/*
** Initialize random number generator.
*/
/* randnum(13L); */
randnum((int32_t)13);

/*
** Start with no strings.  Initialize our current offset pointer
** to 0.
*/
*nstrings=0L;
curroffset=0L;
fullflag=0;

do
{
	/*
	** Allocate a string with a random length no
	** shorter than 4 bytes and no longer than
	** 80 bytes.  Note we have to also make sure
	** there's room in the array.
	*/
        /* stringlength=(unsigned char)((1+abs_randwc(76L)) & 0xFFL);*/
	stringlength=(unsigned char)((1+abs_randwc((int32_t)76)) & 0xFFL);
	if((unsigned long)stringlength+curroffset+1L>=arraysize)
	{       stringlength=(unsigned char)((arraysize-curroffset-1L) &
				0xFF);
		fullflag=1;     /* Indicates a full */
	}

	/*
	** Store length at curroffset and advance current offset.
	*/
	*(strarray+curroffset)=stringlength;
	curroffset++;

	/*
	** Fill up the rest of the string with random bytes.
	*/
	for(i=0;i<stringlength;i++)
	{       *(strarray+curroffset)=
		        /* (unsigned char)(abs_randwc((long)0xFE)); */
			(unsigned char)(abs_randwc((int32_t)0xFE));
		curroffset++;
	}

	/*
	** Increment the # of strings counter.
	*/
	*nstrings+=1L;

} while(fullflag==0);

/*
** We now have initialized a single full array.  If there
** is more than one array, copy the original into the
** others.
*/
k=1;
tempsbase=strarray;
while(k<numarrays)
{       tempsbase+=arraysize+100;         /* Set base */
	for(l=0;l<arraysize;l++)
		tempsbase[l]=strarray[l];
	k++;
}

/*
** Now the array is full, allocate enough space for an
** offset pointer array.
*/
optrarray = malloc(*nstrings * sizeof(unsigned long) * numarrays);
if (!optrarray) {
        /* FIXME: add error message */
	free(strarray);
        exit(1);
}

/*
** Go through the newly-built string array, building
** offsets and putting them into the offset pointer
** array.
*/
curroffset=0;
for(j=0;j<*nstrings;j++)
{       *(optrarray+j)=curroffset;
	curroffset+=(unsigned long)(*(strarray+curroffset))+1L;
}

/*
** As above, we've made one copy of the offset pointers,
** so duplicate this array in the remaining ones.
*/
k=1;
tempobase=optrarray;
while(k<numarrays)
{       tempobase+=*nstrings;
	for(l=0;l<*nstrings;l++)
		tempobase[l]=optrarray[l];
	k++;
}

/*
** All done...go home.  Pass local pointer back.
*/
return(optrarray);
}

/**************
** stradjust **
***************
** Used by the string heap sort.  Call this routine to adjust the
** string at offset i to length l.  The members of the string array
** are moved accordingly and the length of the string at offset i
** is set to l.
*/
static void stradjust(unsigned long *optrarray,      /* Offset pointer array */
	unsigned char *strarray,                     /* String array */
	unsigned long nstrings,                         /* # of strings */
	unsigned long i,                                /* Offset to adjust */
	unsigned char l)                                /* New length */
{
unsigned long nbytes;           /* # of bytes to move */
unsigned long j;                /* Index */
int direction;                  /* Direction indicator */
unsigned char adjamount;        /* Adjustment amount */

/*
** If new length is less than old length, the direction is
** down.  If new length is greater than old length, the
** direction is up.
*/
direction=(int)l - (int)*(strarray+*(optrarray+i));
adjamount=(unsigned char)abs(direction);

/*
** See if the adjustment is being made to the last
** string in the string array.  If so, we don't have to
** do anything more than adjust the length field.
*/
if(i==(nstrings-1L))
{       *(strarray+*(optrarray+i))=l;
	return;
}

/*
** Calculate the total # of bytes in string array from
** location i+1 to end of array.  Whether we're moving "up" or
** down, this is how many bytes we'll have to move.
*/
nbytes=*(optrarray+nstrings-1L) +
	(unsigned long)*(strarray+*(optrarray+nstrings-1L)) + 1L -
	*(optrarray+i+1L);

/*
** Calculate the source and the destination.  Source is
** string position i+1.  Destination is string position i+l
** (i+"ell"...don't confuse 1 and l).
** Hand this straight to memmove and let it handle the
** "overlap" problem.
*/
memmove(strarray + *(optrarray + i) + l + 1, strarray + *(optrarray + i + 1), nbytes);

/*
** We have to adjust the offset pointer array.
** This covers string i+1 to numstrings-1.
*/
for(j=i+1;j<nstrings;j++)
	if(direction<0)
		*(optrarray+j)=*(optrarray+j)-adjamount;
	else
		*(optrarray+j)=*(optrarray+j)+adjamount;

/*
** Store the new length and go home.
*/
*(strarray+*(optrarray+i))=l;
return;
}

/****************
** strheapsort **
*****************
** Pass this routine a pointer to an array of unsigned char.
** The array is presumed to hold strings occupying at most
** 80 bytes (counts a byte count).
** This routine also needs a pointer to an array of offsets
** which represent string locations in the array, and
** an unsigned long indicating the number of strings
** in the array.
*/
static void StrHeapSort(unsigned long *optrarray, /* Offset pointers */
	unsigned char *strarray,             /* Strings array */
	unsigned long numstrings,               /* # of strings in array */
	unsigned long bottom,                   /* Region to sort...bottom */
	unsigned long top)                      /* Region to sort...top */
{
unsigned char temp[80];                 /* Used to exchange elements */
unsigned char tlen;                     /* Temp to hold length */
unsigned long i;                        /* Loop index */


/*
** Build a heap in the array
*/
for(i=(top/2L); i>0; --i)
	strsift(optrarray,strarray,numstrings,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)
{
	strsift(optrarray,strarray,numstrings,0,i);

	/* temp = string[0] */
	tlen=*strarray;
        memmove(&temp[0], strarray, tlen + 1);

	/* string[0]=string[i] */
	tlen=*(strarray+*(optrarray+i));
	stradjust(optrarray,strarray,numstrings,0,tlen);
        memmove(strarray, (strarray + *(optrarray + i)), tlen + 1);

	/* string[i]=temp */
	tlen=temp[0];
	stradjust(optrarray,strarray,numstrings,i,tlen);
        memmove(strarray + *(optrarray + i), &temp[0], tlen + 1);
}
}

/****************
** str_is_less **
*****************
** Pass this function:
**      1) A pointer to an array of offset pointers
**      2) A pointer to a string array
**      3) The number of elements in the string array
**      4) Offsets to two strings (a & b)
** This function returns TRUE if string a is < string b.
*/
static int str_is_less(unsigned long *optrarray, /* Offset pointers */
	unsigned char *strarray,                     /* String array */
	unsigned long numstrings,                       /* # of strings */
	unsigned long a, unsigned long b)                       /* Offsets */
{
int slen;               /* String length */

/*
** Determine which string has the minimum length.  Use that
** to call strncmp().  If they match up to that point, the
** string with the longer length wins.
*/
slen=(int)*(strarray+*(optrarray+a));
if(slen > (int)*(strarray+*(optrarray+b)))
	slen=(int)*(strarray+*(optrarray+b));

slen=strncmp((char *)(strarray+*(optrarray+a)),
		(char *)(strarray+*(optrarray+b)),slen);

if(slen==0)
{
	/*
	** They match.  Return TRUE if the length of a
	** is greater than the length of b.
	*/
	if(*(strarray+*(optrarray+a)) >
		*(strarray+*(optrarray+b)))
		return TRUE;
	return FALSE;
}

if(slen<0) return TRUE;        /* a is strictly less than b */

return FALSE;                  /* Only other possibility */
}

/************
** strsift **
*************
** Pass this function:
**      1) A pointer to an array of offset pointers
**      2) A pointer to a string array
**      3) The number of elements in the string array
**      4) Offset within which to sort.
** Sift the array within the bounds of those offsets (thus
** building a heap).
*/
static void strsift(unsigned long *optrarray,        /* Offset pointers */
	unsigned char *strarray,                     /* String array */
	unsigned long numstrings,                       /* # of strings */
	unsigned long i, unsigned long j)                       /* Offsets */
{
unsigned long k;                /* Temporaries */
unsigned char temp[80];
unsigned char tlen;             /* For string lengths */


while((i+i)<=j)
{
	k=i+i;
	if(k<j)
		if(str_is_less(optrarray,strarray,numstrings,k,k+1L))
			++k;
	if(str_is_less(optrarray,strarray,numstrings,i,k))
	{
		/* temp=string[k] */
		tlen=*(strarray+*(optrarray+k));
		memmove(&temp[0], strarray + *(optrarray + k), tlen+1);

		/* string[k]=string[i] */
		tlen=*(strarray+*(optrarray+i));
		stradjust(optrarray,strarray,numstrings,k,tlen);
		memmove(strarray + *(optrarray + k), strarray + *(optrarray + i), tlen + 1);

		/* string[i]=temp */
		tlen=temp[0];
		stradjust(optrarray,strarray,numstrings,i,tlen);
		memmove(strarray + *(optrarray + i), &temp[0], tlen + 1);
		i=k;
	}
	else
		i=j+1;
}
}