path: root/stringsort.c

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


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

/*
** The following constant STRINGARRAYSIZE determines
** the default # of bytes allocated to each string array.
*/
#define ARRAY_SIZE 8111


static clock_t DoStringSortIteration(unsigned char *array,
		unsigned int num_arrays);
static unsigned long *LoadStringArray(unsigned char *strarray,
		unsigned int num_arrays,
		unsigned long *strings);
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 top);
static int str_is_less(unsigned long *optrarray,
		unsigned char *strarray,
		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 **
*****************/
double
DoStringSort(void)
{
        unsigned char*  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;
                /*
                ** Initialize the number of arrays.
                */
                do {
                        ++num_arrays;
                        /*
                        ** Allocate space for array.  We'll add an extra 100
                        ** bytes to protect memory as strings move around
                        ** (this can happen during string adjustment)
                        */
                        array = realloc(array, (ARRAY_SIZE + 100) * num_arrays);

                        /*
                        ** 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.
                        */
                } while (DoStringSortIteration(array, num_arrays) <= MINIMUM_TICKS);
        } else {
                /*
                ** We don't have to perform self adjustment code.
                ** Simply allocate the space for the array.
                */
                array = malloc((ARRAY_SIZE + 100) * num_arrays);
        }

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

        free(array);

        return (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 *array, unsigned int num_arrays)
{
        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(array,num_arrays,&nstrings);

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

        start = clock();

        for(i = 0; i < num_arrays; i++) {
                StrHeapSort(tempobase, tempsbase, nstrings, nstrings - 1);
                tempobase += nstrings;    /* Advance base pointers */
                tempsbase += ARRAY_SIZE + 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 num_arrays,                 /* # of arrays */
	unsigned long *nstrings)                /* # of strings */
{
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>=ARRAY_SIZE)
	{       stringlength=(unsigned char)((ARRAY_SIZE-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<num_arrays)
{       tempsbase += ARRAY_SIZE + 100;         /* Set base */
	for (l = 0; l < ARRAY_SIZE; 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) * num_arrays);

/*
** 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<num_arrays)
{       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 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 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,k,k+1L))
			++k;
	if(str_is_less(optrarray,strarray,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;
}
}