From 1fa9357768c1b4b2301b7341656dbc81e531c9f6 Mon Sep 17 00:00:00 2001
From: Matt Turner <mattst88@gmail.com>
Date: Tue, 11 Nov 2008 22:34:57 +0000
Subject: -- Split nbench1.c into component files -- Combine wordcat.h with
 huffman routines in huffman.c -- Readd NNET.DAT (oops) -- Update Makefile to
 build component files

git-svn-id: svn://mattst88.com/svn/cleanbench/trunk@3 0d43b9a7-5ab2-4d7b-af9d-f64450cef757
---
 stringsort.c | 575 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 575 insertions(+)
 create mode 100644 stringsort.c

(limited to 'stringsort.c')

diff --git a/stringsort.c b/stringsort.c
new file mode 100644
index 0000000..5d7c67d
--- /dev/null
+++ b/stringsort.c
@@ -0,0 +1,575 @@
+#include <stdint.h>
+/*#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <strings.h>
+#include <math.h>*/
+#include "nmglobal.h"
+#include "nbench1.h"
+
+#ifdef DEBUG
+static int numsort_status=0;
+static int stringsort_status=0;
+#endif
+
+/********************
+** STRING HEAPSORT **
+********************/
+
+/*****************
+** 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)
+{
+
+SortStruct *strsortstruct;      /* Local for sort structure */
+unsigned char *arraybase;            /* Base pointer of char array */
+long accumtime;                 /* Accumulated time */
+double iterations;              /* # of iterations */
+char *errorcontext;             /* Error context string pointer */
+int systemerror;                /* For holding error code */
+
+/*
+** Link to global structure
+*/
+strsortstruct=&global_strsortstruct;
+
+/*
+** Set the error context
+*/
+errorcontext="CPU:String Sort";
+
+/*
+** See if we have to perform self-adjustment code
+*/
+if(strsortstruct->adjust==0)
+{
+	/*
+	** 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=(unsigned char *)AllocateMemory((strsortstruct->arraysize+100L) *
+			(long)strsortstruct->numarrays,&systemerror);
+		if(systemerror)
+		{       ReportError(errorcontext,systemerror);
+		}
+
+		/*
+		** 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;          /* We're ok...exit */
+
+		FreeMemory((void *)arraybase,&systemerror);
+		strsortstruct->numarrays+=1;
+	}
+}
+else
+{
+	/*
+	** We don't have to perform self adjustment code.
+	** Simply allocate the space for the array.
+	*/
+	arraybase=(unsigned char *)AllocateMemory((strsortstruct->arraysize+100L) *
+		(long)strsortstruct->numarrays,&systemerror);
+	if(systemerror)
+	{       ReportError(errorcontext,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=(double)0.0;
+
+do {
+	accumtime+=DoStringSortIteration(arraybase,
+				strsortstruct->numarrays,
+				strsortstruct->arraysize);
+	iterations+=(double)strsortstruct->numarrays;
+} while(TicksToSecs(accumtime)<strsortstruct->request_secs);
+
+/*
+** Clean up, calculate results, and go home.
+** Set flag to show we don't need to rerun adjustment code.
+*/
+FreeMemory((void *)arraybase,&systemerror);
+strsortstruct->sortspersec=iterations / (double)TicksToFracSecs(accumtime);
+if(strsortstruct->adjust==0)
+	strsortstruct->adjust=1;
+#ifdef DEBUG
+if (stringsort_status==0) printf("String sort: OK\n");
+stringsort_status=0;
+#endif
+return;
+}
+
+/**************************
+** 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 unsigned long DoStringSortIteration(unsigned char *arraybase,
+		unsigned int numarrays,unsigned long arraysize)
+{
+unsigned long *optrarray;            /* Offset pointer array */
+unsigned long elapsed;          /* Elapsed ticks */
+unsigned long nstrings;         /* # of strings in array */
+int syserror;                   /* System error code */
+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 the stopwatch
+*/
+elapsed=StartStopwatch();
+
+/*
+** Execute heapsorts
+*/
+for(i=0;i<numarrays;i++)
+{       StrHeapSort(tempobase,tempsbase,nstrings,0L,nstrings-1);
+	tempobase+=nstrings;    /* Advance base pointers */
+	tempsbase+=arraysize+100;
+}
+
+/*
+** Record elapsed time
+*/
+elapsed=StopStopwatch(elapsed);
+
+#ifdef DEBUG
+{
+	unsigned long i;
+	for(i=0;i<nstrings-1;i++)
+	{       /*
+		** Compare strings to check for proper
+		** sort.
+		*/
+		if(str_is_less(optrarray,arraybase,nstrings,i+1,i))
+		{       printf("Sort Error\n");
+			stringsort_status=1;
+                        break;
+		}
+	}
+}
+#endif
+
+/*
+** Release the offset pointer array built by
+** LoadStringArray()
+*/
+FreeMemory((void *)optrarray,&syserror);
+
+/*
+** Return elapsed ticks.
+*/
+return(elapsed);
+}
+
+/********************
+** 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 */
+int systemerror;                /* For holding error code */
+
+/*
+** 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=(unsigned long *)AllocateMemory(*nstrings * sizeof(unsigned long) *
+		numarrays,
+		&systemerror);
+if(systemerror)
+{       ReportError("CPU:Stringsort",systemerror);
+	FreeMemory((void *)strarray,&systemerror);
+}
+
+/*
+** 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.
+*/
+MoveMemory((void *)(strarray+*(optrarray+i)+l+1),
+	(void *)(strarray+*(optrarray+i+1)),
+	(unsigned long)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;
+	MoveMemory((void *)&temp[0], /* Perform exchange */
+		(void *)strarray,
+		(unsigned long)(tlen+1));
+
+
+	/* string[0]=string[i] */
+	tlen=*(strarray+*(optrarray+i));
+	stradjust(optrarray,strarray,numstrings,0,tlen);
+	MoveMemory((void *)strarray,
+		(void *)(strarray+*(optrarray+i)),
+		(unsigned long)(tlen+1));
+
+	/* string[i]=temp */
+	tlen=temp[0];
+	stradjust(optrarray,strarray,numstrings,i,tlen);
+	MoveMemory((void *)(strarray+*(optrarray+i)),
+		(void *)&temp[0],
+		(unsigned long)(tlen+1));
+
+}
+return;
+}
+
+/****************
+** 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));
+		MoveMemory((void *)&temp[0],
+			(void *)(strarray+*(optrarray+k)),
+			(unsigned long)(tlen+1));
+
+		/* string[k]=string[i] */
+		tlen=*(strarray+*(optrarray+i));
+		stradjust(optrarray,strarray,numstrings,k,tlen);
+		MoveMemory((void *)(strarray+*(optrarray+k)),
+			(void *)(strarray+*(optrarray+i)),
+			(unsigned long)(tlen+1));
+
+		/* string[i]=temp */
+		tlen=temp[0];
+		stradjust(optrarray,strarray,numstrings,i,tlen);
+		MoveMemory((void *)(strarray+*(optrarray+i)),
+			(void *)&temp[0],
+			(unsigned long)(tlen+1));
+		i=k;
+	}
+	else
+		i=j+1;
+}
+return;
+}
-- 
cgit v1.2.3