Category : C Source Code
Archive   : CSRC2.ZIP
Filename : PERF1.C

 
Output of file : PERF1.C contained in archive : CSRC2.ZIP
#include
#include

#define EOS '\0'
#define FALSE 0
#define TRUE 1
#define VOID int

#define IO_ERROR 1
#define DOALARM 0
#define CREATE fopen


#define MAXKEYS 100 /* Maximum number of keys */
#define MAXCHARS 127 /* Maximum number of char's */
#define UNDEF -1 /* the undefined value */

typedef struct keyword {
int len; /* Keyword length */
char last; /* Last byte of keyword */
char word[1]; /* Keyword text */
} KEYWORD;

/*
* Define some frequently used operations as macros:
* hash(p) returns the hash value for this keyword
* used(n) TRUE if this hash value is in use or illegal
* defined(c) TRUE if this character is defined
*/

#define hash(p) (value[p->word[0]] + p->len + value[p->last])
#define used(n) ((n > tablesize || n < 0) ? TRUE : mapped[n])
#define defined(c) (c != UNDEF)

char cval[MAXCHARS]; /* All possible characters */
short cused[MAXCHARS]; /* count of often char used */
short order[MAXKEYS]; /* ordering of key words by subscript */
short neworder[MAXKEYS]; /* the new supposedly improved ordering */
short hashval[MAXKEYS]; /* current hashvalue of the key word */
short value[MAXCHARS]; /* associated value of the character */
int mapped[MAXKEYS]; /* track which table entries are in use */
char name[50]; /* bigger than any keyword should be */


KEYWORD *keywds[MAXKEYS];

extern long time();
extern char *ctime();
extern int aredefined();
extern char *strchr();

int debug = 0;
int nkeys = sizeof(keywds) / (sizeof (KEYWORD));
int tablesize = sizeof(keywds) / (sizeof (KEYWORD));
short trys = 0;
int nletters = 0;
short kilotrys = 0;
int atime = 10 * 60; /* default alarm status 10 min. */
char *klimit = NULL;
char *textp = NULL;
long bigcount = 0;
short depth = 0;
short k_now = 0; /* value of k for status report */
int nosort = FALSE; /* -n sets nosort TRUE */
long start, stop; /* the start and finish times */
short vlimit = 0;
short keylimit = 0;
short tlimit = 0;
char *output = NULL; /* Output file if set */

char letters[37]; /* string of defined chars */
char *letend = letters; /* -> free space in letters[] */


main(argc,argv)
int argc;
char *argv[];
{
getoptions(argc, argv);
start = time(NULL);
/*alarm(atime); */ /* status every N secs */
setup();
dosort();
printf("The search ordering is\n");
prntorder();
if (search(0)) {
/* alarm(0);*/
printf("\nSuccess! Associated Char Values Follow:\n");
prntvals();
prnthash();
printf("\n");
if (output != NULL)
dooutput();
}
else {
/* alarm(0); */
printf("\nFailed to find char values for hash function\n");
}
printf("Total search invocations = %ld, max depth = %d\n",
bigcount, depth);
stop = time(NULL);
printf(" Started %s", ctime(&start));
printf("Finished %s", ctime(&stop));
}


setup()
{
register KEYWORD *kp;
register int c;
register int i,j;
int len;

printf("\n Type in number of keywords :");
scanf("%d",j);
printf("%\nType your keywords:\n");

for (i = 0;i if (i >= MAXKEYS) {
printf("Too many keys, %d max.\n", MAXKEYS);
exit(IO_ERROR);
}
len = strlen(name);
kp = (KEYWORD *) malloc(sizeof (KEYWORD) + len);
if (kp == NULL) {
printf("Out of room allocating keywords\n");
exit(IO_ERROR);
}
keywds[i] = kp;
kp->len = len;
kp->last = name[len - 1];
strcpy(&kp->word[0], name);
}
nkeys = (keylimit == 0) ? i : keylimit;

for (i = 0; i < MAXKEYS; i++) {
hashval[i] = UNDEF;
order[i] = i;
mapped[i] = FALSE;
}

for (i = 0; i < MAXCHARS; i++) {
cval[i] = 0;
value[i] = UNDEF;
}

if (!precheck()) {
printf("Perfect hash search terminated\n");
exit(IO_ERROR);
}

for (i = 0; i < nkeys; i++) {
c = keywds[i]->word[0]; /* Get first char of keyword */
cval[c] = c; /* Remember this one used */
if (cused[c] == 0) /* If it's the first time, */
++nletters; /* Count unique letters */
++cused[c]; /* count how often letter used */
c = keywds[i]->last; /* Get last char of keyword */
cval[c] = c; /* And do the same for it */
if (cused[c] == 0)
++nletters;
++cused[c];
}

tablesize = (tlimit == 0 ? MAXKEYS : tlimit);
printf("Perfect hash function finder, CDH Ver. 2.9\n");
printf("Start time = %s", ctime(&start));
printf("%d keywords, %d distinct letters.\n",
nkeys, nletters);
nletters = (vlimit > 0) ? vlimit : nletters;
printf("The associated char value limit is %d\n", nletters);
printf("The table size limit is %d\n", tablesize);

}


dosort()
{
register KEYWORD *kp;
register int i, j;
int k, m;
int newvalues;

if (nosort) {
printf("No presorting of keywords.\n");
return;
}

/*
* first order by sum of frequencies of occurrences of each
* keys 1st and last letter
*/

for (i = 0; i < nkeys; i++) {
kp = keywds[i];
order[i] = cused[kp->word[0]] + cused[kp->last];
}
for (m = 0; m < nkeys; m++) {
for (k = -1, i = 0; i < nkeys; i++) {
if (order[i] > k) {
k = order[i];
j = i; /* remember keywd subscript */
}
}
order[j] = 0;
neworder[m] = j;
}
for (i=0; i < nkeys; i++)
order[i] = neworder[i];
if (debug > 2) {
printf("After first ordering\n");
prntorder();
}

/*
* The second ordering follows, keywds whose values are
* defined by keywds earlier in the order are placed
* immediately after they are defined. This causes hash
* value conflicts to occur as early during the search
* as possible.
*/

letend = letters;
letters[0] = EOS;
merge(order[0]); /* prime the pump */
neworder[0] = order[0];
order[0] = UNDEF;
for (i = 1; i < nkeys;) {
for (newvalues = TRUE; newvalues;) {
newvalues = FALSE;
for (k = 0; k < nkeys; k++) {
if (order[k] == UNDEF)
continue;
if (aredefined(order[k])) {
neworder[i++] = order[k];
order[k] = UNDEF;
continue;
}
}
for (k = 0; k < nkeys; k++) {
if (order[k] != UNDEF) {
neworder[i++] = order[k];
merge(order[k]);
order[k] = UNDEF;
newvalues = TRUE;
break;
}
}
}
}
for (i = 0; i < nkeys; i++)
order[i] = neworder[i];
if (precheck() == FALSE) {
printf("OOPS - call a Guru, the presort botched it\n");
prntorder();
exit(IO_ERROR);
}
}


/*
* merge - adds keywd letters to the string of those defined.
* This could be speeded up, but it's not a critical-path function.
*/

VOID merge(n)
int n;
{
register KEYWORD *kp;

kp = keywds[n];
if (debug > 2)
printf("merging in %s\n", kp->word);
if (strchr(letters, kp->word[0]) == NULL) {
*letend++ = kp->word[0];
*letend = EOS;
}
if (strchr(letters, kp->last) != NULL) {
*letend++ = kp->last;
*letend = EOS;
}
}

/*
* aredefined - see if 1st & last char of keywd are defined
*/

int aredefined(n)
int n;
{
register KEYWORD *kp;

kp = keywds[n];
if (strchr(letters, kp->word[0]) != NULL
&& strchr(letters, kp->last) != NULL)
return (TRUE);
else return (FALSE);
}


/*
* precheck - all keywds length,1st and last char disjoint
*/

int precheck()
{
int pretest;
register KEYWORD *ip, *jp;
short i, j;
short m, k;
char a, b;

pretest = TRUE;
for (m = 0; m < nkeys; m++) {
i = order[m];
ip = keywds[i];
a = ip->word[0];
b = ip->last;
for (k = m + 1; k < nkeys-1; k++) {
j = order[k];
jp = keywds[j];
if (ip->len == jp->len
&& ((a == jp->word[0] && b == jp->last)
|| (a == jp->last && b == jp->word[0]))) {
pretest = FALSE;
printf("Precheck fails on %s and %s\n",
ip->word, jp->word);
}
}
}
return (pretest);
}


/*
* prntorder - printout the current order of the keywords
*/

VOID prntorder()
{
register int i, j;

for (i = 0, j = 0; i < nkeys; i++) {
if ((j + keywds[order[i]]->len) >= 60) {
printf("\n");
j = 0;
}
printf(" %s", keywds[order[i]]->word);
j += keywds[order[i]]->len + 1;
}
printf("\n");
}

/*
* prntvals - prints out the letter associated values
*/

prntvals()
{
register int i, j;

for (i = 0, j = 0; i < MAXCHARS; i++) {
if (cval[i]) {
printf("%s %c =%2d,",
((++j % 10) == 0) ? "\n" : "",
cval[i], value[i]);
}
}
printf("\n");
}


/*
* prnthash - prints out the hash values for the keywds
*/

VOID
prnthash()
{
register int i, j;
register KEYWORD *kp;
int swap;
int hmin;
int hmax;
int spread;


swap = TRUE;
hmin = MAXKEYS;
hmax = 0;
spread = 0;
for (i = 0; i < nkeys; i++) {
j = hashval[i] = hash(keywds[i]);
hmin = (hmin < j) ? hmin : j;
hmax = (hmax > j) ? hmax : j;
order[i] = i;
}
while (swap) { /* plain vanilla bubble sort */
swap = FALSE;
for (i = 0; i < nkeys-1; i++) {
if (hashval[order[i+1]] < hashval[order[i]]) {
swap = TRUE;
j = order[i];
order[i] = order[i+1];
order[i+1] = j;
}
}
}
printf("Hash min = %d, max = %d, spread = %d\n",
hmin, hmax, hmax - hmin + 1);
for (i=0, j=0; i < nkeys; i++, j++) {
kp = keywds[order[i]];
if (j + (kp->len + 5) > 60) {
printf("\n");
j = 0;
}
printf(" %s %d,", kp->word,
hash(keywds[order[i]]));
j += (kp->len + 5);
}
printf("\n");
}

/*
* search - calls itself recursively to find char values
*/

int search(k)
register int k;
{
register KEYWORD *p;
register int j;
int m;
short v1, v2, num;
short sub1, sub2, subn;
int thesame;

thesame = FALSE;
bigcount++;
k_now = k; /* global for status reporting */
if (k >= nkeys) /* hey - we may be all done */
return (TRUE);
if (k > depth) /* global for status reporting */
depth = k; /* keep track of search depth */
m = order[k];
p = keywds[m];
sub1 = p->word[0]; /* sub1 = first letter in word */
sub2 = p->last; /* sub2 = last letter in word */
if (sub1 == sub2)
thesame = TRUE;
v1 = value[sub1];
v2 = value[sub2];
if (defined(v1) && defined(v2)) {
num = hash(p); /* Both letters defined */
if (used(num))
return (FALSE); /* this hash value is in use */
else {
hashval[m] = num; /* install it */
mapped[num] = TRUE;
if (search(k + 1))
return (TRUE);
else {
hashval[m] = UNDEF;
mapped[num] = FALSE;
return (FALSE);
}
}
}
else if (defined(v1)) {
for (j = 0; j <= nletters; j++) {
v2 = j;
num = v1 + p->len + v2;
if (!used(num)) {
hashval[m] = num;
mapped[num] = TRUE;
value[sub2] = v2;
subn = sub2;
if (search(k + 1))
return (TRUE);
else
remove(m, sub2);
}
}
return (FALSE);
}
else if (defined(v2)) {
for (j = 0; j <= nletters; j++) {
v1 = j;
num = v1 + p->len + v2;
if (!used(num)) {
hashval[m] = num;
mapped[num] =TRUE;
value[sub1] = v1;
subn = sub1;
if (search(k + 1))
return (TRUE);
else
remove(m, sub1);
}
}
return (FALSE);
}
else { /* neither defined */
for (j = 0; j <= nletters; j++) {
if (thesame) {
v1 = v2 = j;
num = v1 + p->len + v2;
if (!used(num)) {
hashval[m] = num;
mapped[num] = TRUE;
value[sub1] = v1; /* same as value[sub2] */
subn = sub1;
if (search(k + 1))
return (TRUE);
else
remove(m, subn);
}
}
else {
value[sub1] = j;
if (search(k)) /* if never TRUE thru */
return (TRUE); /* for loop, then FALSE */
else
value[sub1] = UNDEF;
}
}
return (FALSE);
}
}

/*
* remove - backup by deleting keywds hash value etc
*/

VOID remove(m, subn)
register short m;
register short subn;
{
if (debug > 6)
printf("removing %s, subn = %d\n", keywds[m]->word, subn);
mapped[hashval[m]] = FALSE;
hashval[m] = UNDEF;
value[subn] = UNDEF;
}

/*
* dooutput writes parser tables to the indicated output file.
*/

char *function[] = {
"",
"int",
"keyword(text)",
"register char\t*text;",
"/*",
" * Look for keyword (string of alpha) in the perfect hash table",
" * Return the index (L_xxx value) or 0 if not found",
" */",
"{",
"\tregister char\t*tp;",
"\tregister int\thash;",
"",
"\tif (*text < FIRST || *text > LAST)",
"\t return (0);",
"\tfor (tp = text; isalpha(*tp); tp++)",
"\t ;",
"\thash = (tp - text);",
"\tif (*--tp < FIRST || *tp > LAST)",
"\t return (0);",
"\thash += (px_assoc - FIRST)[*text] + (px_assoc - FIRST)[*tp];",
"\tif (px_table[hash] == NULL)",
"\t return (0);",
"\tif (strncmp(text, px_table[hash], (tp - text + 1)) != 0)",
"\t return (0);",
"\treturn(hash);",
"}",
"",
NULL,
};


dooutput()
{
FILE *fd;
register char **funp;
register int i;
int first, last, hval;

if ((fd = CREATE(output, "w")) == NULL) {
printf("\n Cannot open %s for output\n",output);
return;
}
fprintf(fd, "#include \n");
fprintf(fd, "#include \n");
for (i = 0; i < nkeys; i++) {
fprintf(fd, "#define\tL_%s\t", keywds[order[i]]->word);
if (keywds[order[i]]->len < 14)
putc('\t', fd);
if (keywds[order[i]]->len < 6)
putc('\t', fd);
fprintf(fd, "%d\n", hash(keywds[order[i]]));
}
for (i = MAXCHARS; --i >= 0 && cval[i] == 0;)
;
last = i;
for (i = 0; i <= last && cval[i] == 0;)
i++;
first = i;
fprintf(fd, "#define FIRST\t'%c'\n", first);
fprintf(fd, "#define LAST\t'%c'\n", last);
fprintf(fd, "static char px_assoc[] = {\n");
while (i <= last) {
fprintf(fd, "\t%d,\t/* '%c' */\n", value[i], i);
i++;
}
fprintf(fd, "};\n");
fprintf(fd, "static char *px_table[] = {\n");
last = 0;
for (i = 0; i < nkeys; i++) {
hval = hash(keywds[order[i]]);
while (last < hval) {
fprintf(fd, "\tNULL,\t\t\t/*%3d\t*/\n", last);
last++;
}
fprintf(fd, "\t\"%s\",\t", keywds[order[i]]->word);
if (keywds[order[i]]->len < 13)
putc('\t', fd);
if (keywds[order[i]]->len < 5)
putc('\t', fd);
fprintf(fd, "/*%3d\t*/\n", hval);
last = hval + 1;
}
fprintf(fd, "};\n");
for (funp = function; *funp != NULL; funp++)
fprintf(fd, "%s\n", *funp);
fclose(fd);
}


/*VOID status()
{
fprintf(stderr,
"\nSTATUS: key \"%s\" (%d), search calls = %ld, max depth = %d\n",
keywds[k_now]->word, k_now, bigcount, depth);
fflush(stderr);
signal(SIGTERM,status);
signal(SIGALRM,status);
alarm(atime);
}
*/

/*
* G E T O P T I O N S
*
* Generalized command line argument processor. The following
* types of arguments are parsed:
* flags The associated int global is incremented:
* -f f-flag set to 1
* -f123 f-flag set to 123 (no separator)
* -fg f-flag and g-flag incremented.
* values A value must be present. The associated
* int global receives the value:
* -v123 value set to 123
* -v 123 value set to 123
* arguments The associated global (a char *) is
* set to the next argument:
* -f foo argument set to "foo"
*/

#define FLAG 0
#define VALUE 1
#define ARG 2
#define ERROR 3

typedef struct argstruct {
char opt; /* Option byte */
char type; /* FLAG/VALUE/ARG */
char *name; /* What to set if option seen */
char *what; /* String for error message */
} ARGSTRUCT;

static ARGSTRUCT arginfo[] = {
{ 'd', FLAG, (char *)&debug, "debug" },
{ 'a', VALUE, (char *)&atime, "alarm time for status" },
{ 't', VALUE, (char *)&tlimit, "table size limit" },
{ 'v', VALUE, (char *)&vlimit, "associated value limit" },
{ 'k', VALUE, (char *)&keylimit, "keyword limit" },
{ 'n', FLAG, (char *)&nosort, "no sort wanted" },
{ 'o', ARG, (char *)&output, "parser output file" },
{ EOS, ERROR, NULL, NULL },
};

static char *argtype[] = {
"flag", "takes value", "takes argument"
};

getoptions(argc, argv)
int argc;
char **argv;
/*
* Process arg's
*/
{
register char *ap;
register int c;
register ARGSTRUCT *sp;
int i;
int helpneeded;

helpneeded = FALSE;
for (i = 1; i < argc; i++) {
if ((ap = argv[i]) != NULL && *ap == '-') {
argv[i] = NULL;
for (ap++; (c = *ap++) != EOS;) {
if (isupper(c))
c = tolower(c);
sp = arginfo;
while (sp->opt != EOS && sp->opt != c)
sp++;
switch (sp->type) {
case FLAG: /* Set the flag */
if (!isdigit(*ap)) {
(*((int *)sp->name))++;
break;
}
case VALUE: /* -x123 */
if (isdigit(*ap)) {
*((int *)sp->name) = atoi(ap);
*ap = EOS;
}
else if (*ap == EOS && ++i < argc) {
*((int *)sp->name) = atoi(argv[i]);
argv[i] = NULL;
}
else {
fprintf(stderr,
"Bad option '%c%s' (%s)",
c, ap, sp->what);
fprintf(stderr, ", ignored\n");
helpneeded++;
}
break;

case ARG: /* -x foo */
if (++i < argc) {
*((char **) sp->name) = argv[i];
argv[i] = NULL;
}
else {
fprintf(stderr,
"Argument needed for '%c' (%s)",
c, sp->what);
fprintf(stderr, ", ignored\n");
helpneeded++;
}
break;

case ERROR:
fprintf(stderr,
"Unknown option '%c', ignored\n", c);
helpneeded++;
break;
}
}
}
}
if (helpneeded > 0) {
for (sp = arginfo; sp->opt != EOS; sp++) {
fprintf(stderr, "'%c' -- %s (%s)\n",
sp->opt, sp->what, argtype[sp->type]);
}
}
}


char *strchr(string, c)
register char *string;
register char c;
{
do {
if (*string == c)
return (string);
} while (*string++ != EOS);
return (NULL);
}



  3 Responses to “Category : C Source Code
Archive   : CSRC2.ZIP
Filename : PERF1.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/