/*****************************************************************************
 * mktable - table-building program to ease table maintenance problems
 *
 * DESCRIPTION
 *	Several parts of the FORTRAN compiler need large tables.
 *	For example, the lexer contains tables of keywords and multicharacter
 *	tokens; the intrinsic-function handler contains a table of all the
 *	FORTRAN intrinsic functions.
 *	Maintaining these tables can be aggravating, since they are typically
 *	large and involve lots of drudge work (like changing many sequentially-
 *	numbered macro definitions) to modify.
 *
 *	`mktable' can be used to build tables automatically as part of the
 *	usual compiler building process.  Its usages and semantics are as
 *	follows.
 *
 *	`mktable' takes a "table" file on its standard input.  Each line of
 *	the table file has one of the following forms:
 *
 *		# commentary information
 *		"key-string" [index-macro-name [arbitrary-stuff]]
 *		<blank line>
 *
 *	The key string and arbitrary-stuff form the contents of a single
 *	table record.  The index-macro-name is #define'd to be the index
 *	of the given record in the table.  If the index-macro-name is absent or
 *	is an empty string ("") then no macro definition is produced for the
 *	record.
 *
 *	`mktable' produces its output on four files:
 *		mktable.keys: the key string
 *		mktable.defs: #define <index_macro_name> <index to mktable.keys>
 *		mktable.indx: contains the initialization part of a definition
 *			for an index array for key-letter indexed tables,
 *			or the initialization part of a collision-resolution
 *			table for linear-list hashed tables.
 *			(not generated for sorted or _open-addressed tables.)
 *		mktable.info: contains arbitrary-stuff
 *
 *	For example, if the table to be defined were named "symtab" and the
 *	table being constructed was of the "sorted" type (suitable for binary
 *	search),
 *
 *		# contents of symtab:
 *		"alpha" ST_ALPHA	2, 4, MONADIC
 *		"gamma"	ST_GAMMA	2, 3, MONADIC
 *		"delta" ST_DELTA	2, 1, DYADIC
 *		"epsilon"
 *
 *	then `mktable' produces the following in mktable.keys:
 *
 *		"alpha","delta","epsilon","gamma"
 *
 *	and the following in mktable.defs:
 *
 *		#define ST_ALPHA 0
 *		#define ST_DELTA 1
 *		#define ST_GAMMA 2
 *
 *	and in mktable.info :
 *
 *		{2, 4, MONADIC}, {2, 1, DYADIC}, {0}, {2, 3, MONADIC}
 *
 *	The files might be included in a C source program in the
 *	following way:
 *
 *		#include "mktable.defs"
 *		...
 *		char	*symname[] = {
 *		#	include	"mktable.keys"
 *			};
 *		struct syminfo
 *			{
 *			int size;
 *			int cycles;
 *			int arity;
 *			};
 *		struct syminfo symtab[] = {
 *		#	include "mktable.info"
 *			};
 *
 *	The `mktable' command itself is used in one of the following ways:
 *
 *	mktable "open" size <tablefile
 *		This form creates an _open-addressed hash table, keyed on
 *		the string fields at the beginning of each record in the
 *		table file.  The hash function used is the absolute value
 *		of the sum of all the characters in a key, modulo the table
 *		size.  The collision resolution function is simply one plus
 *		the last hash, modulo the table size.
 *		Since some of the entries in the hash table may be empty,
 *		and `mktable' has no way of knowing how to fill them,
 *		one of the records supplied by the user will be replicated
 *		in the empty entries with its key value set to NULL.
 *		"table.c" will be created with the hash table itself, and
 *		"table.h" will be created with index-macro definitions that
 *		may be used to index directly into the table in "table.c".
 *
 *	mktable "hashed" size <tablefile
 *		This form creates a hash table keyed on the string fields
 *		at the beginning of each table file record.  The hash function
 *		is the absolute value of the sum of all the characters in a
 *		key, modulo the table size.  Collision resolution is handled
 *		with linear chaining, as follows:  If two keys hash to the
 *		same table location, the first one will be placed in the table,
 *		and the corresponding entry of the collision resolution vector
 *		will contain the (integer) index of the next table slot to be
 *		checked for the hash synonym.  When the collision resolution
 *		vector entry is -1, the end of the chain has been reached.
 *		Note that since all entries are stored in the main table, the
 *		`size' must be at least as large as the number of entries.
 *		As with _open addressing, some slots in the table may be
 *		padded with a replicated entry (key value set to NULL).
 *		"table.c" receives the hash table.  "table.h" receives the
 *		index-macro definitions that will index into the table in
 *		"table.c".  "tabindex.c" receives the conflict resolution
 *		vector.
 *
 *	mktable "sorted" <tablefile
 *		This form creates a table sorted in ascending order, keyed
 *		on the string fields at the beginning of each record in the
 *		table file.  Comparisons are ordered according to the ASCII
 *		values of the characters being compared.
 *		"table.c" will be created with the sorted table itself, and
 *		"table.h" will be created with index-macro definitions that
 *		may be used to index directly into the table in "table.c".
 *
 *	mktable "key-letter" <tablefile
 *		This form creates a key-letter-indexed table.
 *		The string fields serve as the
 *		key letter.  An auxiliary table indexed from 'A' to 'Z'+1
 *		gives the starting index of all the entries whose keys begin
 *		with each letter (the last entry duplicates the entry for 'Z').
 *		"table.c" will contain the sorted table.  "tabindex.c" will
 *		contain the auxiliary index table information.  "table.h" will
 *		contain the index-macro definitions that may be used to index
 *		directly into the "table.c" table.
 *		Note that key-letter tables are sorted in a peculiar way;
 *		in ascending order by first letter of the key, but descending
 *		order by the remainder of the key.  This is required by
 *		FORTRAN, to insure that longer keywords are matched before
 *		shorter keywords that are initial substrings of the longer
 *		keywords.
 *		Also note that the key strings themselves are missing the first
 *		char, since by indexing into the table, we are always assured
 *		of having matched the first char.
 *
 * AUTHOR
 *      February, 1984		Allen Akin
 *
 * MODIFICATIONS
 *	March 8, 1984		Allen Akin
 *		Added linear-list resolved hashing.
 *****************************************************************************/

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

#define MAXRECORDS	300		/* maximum-size table we can handle */
#define MAXLINE		82		/* maximum line length (incl "\n\0") */

#define HASHED		0		/* flag used by table loader */
#define LINEAR		1		/* ditto */
#define OPENADDR	2		/* ditto */

#define KEYFILE         "mktable.key"   /* name of table output file */
#define DEFFILE         "mktable.def"   /* name of index defs output file */
#define INDEXFILE       "mktable.ind"   /* name of table index output file */
#define INFOFILE        "mktable.inf"   /* gots the infos in it */

typedef struct rec
{
    char *key;		/* key-string field */
    char *id;		/* index macro identifier */
    char *other;	/* other stuff in the record - output untouched */
    struct rec *link;	/* pointer to next record in hash synonyms list */
} Rec_t;

int	Upper = 0;

FILE *Fkeys, *Findex, *Fdefs, *Finfo;

/************************************************************************/
/* Function Prototypes							*/
/************************************************************************/
void main (int argc, char **argv);
void usage (void);
void error(char * message);
void open_addr(int size);
void hash_linear(int size);
void sorted(void);
void key_letter(void);
int load(Rec_t *record, int method, int size);
void startoutput(void);
void endoutput(void);
void outrec(Rec_t *rec);
void outdef(char *name, int value);
void outinx(int value);
void sortrec(Rec_t **rptr, int size);
int	hash(register char *name);


/************************************************************************/
/* Program code								*/
/************************************************************************/
void main (int argc, char **argv)
{
    if (argc <= 1)
	usage();

    if(strcmp(argv[1], "-U") == 0)
    {
	Upper = 1;
	argv++;
	argc--;
    }
    if (strcmp(argv[1], "open") == 0)
    {
	if (argc != 3)
	    usage();
	open_addr(atoi(argv[2]));
    }
    else if (strcmp(argv[1], "hashed") == 0)
    {
	if (argc != 3)
	    usage();
	hash_linear(atoi(argv[2]));
    }
    else if (strcmp(argv[1], "sorted") == 0)
    {
	if (argc != 2)
	    usage();
	sorted();
    }
    else if (strcmp(argv[1], "key-letter") == 0)
    {
	if (argc != 2)
	    usage();
	key_letter();
    }
    else
	usage();
    exit(0);
}

void usage (void)
{
    error(
  "usage: mktable (open SIZE | hashed SIZE | sorted | key-letter) <table-master"
        );
}

void error(char * message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void open_addr(int size)
{
    register Rec_t
    *record;		/* points to array storing all records */
    Rec_t
        defrec;			/* "default" record for empty array slot */
    register int
    i;

    if (size <= 0)
	error("hash table size specified is less than zero");
    if ((record = (Rec_t *)calloc(size, sizeof(Rec_t))) == NULL)
	error("insufficient memory for hash table");

    for (i = 0; i < size; ++i)
	record[i].key = NULL;

    if (load(record, OPENADDR, size) == 0)
	error("couldn't find any input records");

    defrec.key = NULL;
    defrec.id = NULL;
    for (i = 0; i < size; ++i)
	if (record[i].key != NULL)
	    break;
    defrec.other = record[i].other;

    startoutput();

    for (i = 0; i < size; ++i)
	if (record[i].key == NULL)
	    outrec(&defrec);
	else
	{
	    outrec(&record[i]);
	    outdef(record[i].id, i);
	}

    endoutput();
    _unlink(INDEXFILE);
}

void hash_linear(int size)
{
    register Rec_t
    *record,	/* stores some records, all buckets */
    *rp;
    Rec_t
        defrec;		/* default record for empty hash table slots */
    register int
    i,
        nextslot,	/* next empty slot in main hash table */
    prev;

    if (size <= 0)
	error("hash table size specified is less than zero");
    if ((record = (Rec_t *)calloc(size, sizeof(Rec_t))) == NULL)
	error("insufficient memory for hash table");

    for (i = 0; i < size; ++i)
    {
	record[i].key = NULL;
	record[i].link = NULL;
    }

    if ((i = load(record, HASHED, size)) == 0)
	error("couldn't find any input records");
    if (i > size)
	error("too many records to hold in table");

    defrec.key = NULL;
    defrec.id = NULL;
    for (i = 0; i < size; ++i)
	if (record[i].key != NULL)
	    break;
    defrec.other = record[i].other;
    defrec.link = NULL;
    /*
 * The `load' routine has built a hash table `record'.
 * Each entry in `record' is either empty (key == NULL) or contains a record.
 * Each record may have a NULL link field, or a link field that points to
 * a hash synonym.
 * With this section of code, we rearrange the linked lists of hash synonyms
 * so that all the entries are stored in `record'.
 */
    nextslot = 0;
    for (i = 0; i < size; ++i)
	if (record[i].key != NULL && record[i].link != NULL &&
	    (record[i].link < record || record[i].link >= record + size))
	    for (prev = i, rp = record[i].link; rp != NULL; rp = rp->link)
	    {
		while (record[nextslot].key != NULL)
		    ++nextslot;
		record[prev].link = &record[nextslot];
		record[nextslot] = *rp;
		prev = nextslot;
	    }

    startoutput();

    for (i = 0; i < size; ++i)
	if (record[i].key == NULL)
	{
	    outrec(&defrec);
	    outinx(-1);
	}
	else
	{
	    outrec(&record[i]);
	    if (record[i].link == NULL)
		outinx(-1);
	    else
		outinx(record[i].link - record);    /* cvt. to inx in table */
	    outdef(record[i].id, i);
	}

    endoutput();
}

void sorted(void)
{
    Rec_t
        record[MAXRECORDS],
        *rptr[MAXRECORDS];
    register int
    i,
        size;

    size = load(record, LINEAR, MAXRECORDS);

    for (i = 0; i < size; ++i)
	rptr[i] = &record[i];

    sortrec(rptr, size);

    startoutput();

    for (i = 0; i < size; ++i)
    {
	outrec(rptr[i]);
	outdef(rptr[i]->id, i);
    }

    endoutput();
    _unlink(INDEXFILE);
}

void key_letter(void)
{
    Rec_t
        record[MAXRECORDS],
        *rptr[MAXRECORDS],
        *temp;
    register int
    i,
        size,
        j,
        k,
        l;
    register char
    lastletter;

    size = load(record, LINEAR, MAXRECORDS);

    for (i = 0; i < size; ++i)
	rptr[i] = &record[i];

    sortrec(rptr, size);

    for (i = 0; i < size; i = j)
    {
	for (j = i; j < size; ++j)
	    if (rptr[i]->key[0] != rptr[j]->key[0])
		break;
	l = j - 1;
	for (k = i; k < l; ++k, --l)
	{
	    temp = rptr[k];
	    rptr[k] = rptr[l];
	    rptr[l] = temp;
	}
    }

    startoutput();

    lastletter = (char)((Upper ? 'A' : '_') - 1);
    for (i = 0; i < size; ++i)
    {
	while (rptr[i]->key[0] > lastletter)
	{
	    outinx(i);
	    ++lastletter;
	}
	outrec(rptr[i]);
	outdef(rptr[i]->id, i);
    }


    for (; lastletter < (char)((Upper ? 'Z' : 'z') + 1); ++lastletter)
	outinx(size);

    endoutput();
}

int load(Rec_t *record, int method, int size)
{
    char *line;
    register char *p;
    int rec, h, chainlen, maxchainlen = 0, collisions = 0;
    Rec_t r;

    for (rec = 0; ; ++rec)
    {
	if ((line = malloc(MAXLINE)) == NULL)
	    error("insufficient memory to load records");

	if (fgets(line, MAXLINE, stdin) == NULL)
	    break;

	if (rec >= size)
	    error("too many records to handle");

	r.key = r.id = r.other = NULL;
	r.link = NULL;

	for (p = line; *p && isspace(*p); ++p)
	    ;
	if (*p != '"')
	{
	    free(line);
	    --rec;
	    continue;
	}
	r.key = ++p;
	for (; *p != '"'; ++p)
	    if(Upper && (islower(*p)))
		*p = (char)toupper(*p);
	*p++ = '\0';

	for (; *p && isspace(*p); ++p)		/* skip space key and id */
	    ;
	if (*p == '"' && *(p + 1) == '"')	/* no id */
	{
	    r.id = NULL;
	    p += 2;
	}
	else if (*p)
	{
	    r.id = p++;				/* id start */
	    for (; *p && ( ! isspace(*p)); ++p)	/* til first space */
		;
	    if(*p)
	    {
		*p++ = '\0';			/* terminate id */
	    }
	}

	for (; *p && isspace(*p); ++p)		/* skip space til other info */
	    ;
	if(*p)
	{
	    r.other = p++;
	    for (; *p != '\n' && *p != '\0'; ++p)
		;
	    *p = '\0';
	}

	if (method == LINEAR)
	    record[rec] = r;
	else if (method == OPENADDR)
	{
	    chainlen = 0;
	    for(h = hash(r.key) % size; record[h].key; h = (h+1) % size)
	    {
		++chainlen;
		++collisions;
	    }
	    maxchainlen = (chainlen < maxchainlen)? maxchainlen: chainlen;
	    record[h] = r;
	}
	else /* method == HASHED */
	{
	    Rec_t
	        *rp;

	    h = hash(r.key) % size;
	    if (record[h].key == NULL)
		record[h] = r;
	    else
	    {
		if ((rp = (Rec_t *)malloc(sizeof(Rec_t))) == NULL)
		    error("insufficient memory to store all records");
		*rp = record[h];
		r.link = rp;
		record[h] = r;
		++collisions;
		chainlen = 1;
		for (rp = &record[h]; rp->link != NULL; rp = rp->link)
		    ++chainlen;
		maxchainlen = (chainlen < maxchainlen)? maxchainlen: chainlen;
	    }
	}
    }

    if (method == HASHED || method == OPENADDR)
	fprintf(stderr, "%d collisions, max chain length %d\n", collisions,
	    maxchainlen);

    return rec;
}

void startoutput(void)
{
    if ((Fkeys = fopen(KEYFILE, "w")) == NULL)
	error("can't open keys output file");
    if ((Findex = fopen(INDEXFILE, "w")) == NULL)
	error("can't open index output file");
    if ((Fdefs = fopen(DEFFILE, "w")) == NULL)
	error("can't open definitions output file");
    if ((Finfo = fopen(INFOFILE, "w")) == NULL)
	error("can't open info output file");
}

void endoutput(void)
{
    fclose(Fkeys);
    fclose(Findex);
    fclose(Fdefs);
    fclose(Finfo);
}

void outrec(Rec_t *rec)
{
    if (rec->key == NULL)
	fprintf(Fkeys, "NULL,\n");
    else
	fprintf(Fkeys, "\"%s\",\n", ((rec->key) + 1));

    if (rec->other == NULL)
	fprintf(Finfo, "{0},\n");
    else
	fprintf(Finfo, "{%s},\n", rec->other);
}

void outdef(char *name, int value)
{
    if (name != NULL)
	fprintf(Fdefs, "#define %s %d\n", name, value);
}

void outinx(int value)
{
    fprintf(Findex, "%d,\n", value);
}
/*
 * Following code defines the hash function used in `mktable' and in
 * the compiler.  Since we must guarantee they are the same function,
 * we use a single source file.
 *
 * `mktable' does not use the standard include file that the compiler
 * uses, so we define the allowable register declarations here.
 */
#define REG1 register
#define REG2 register
#define REG3 register

void sortrec(Rec_t **rptr, int size)
{
    register int
    j,
        i,
        gap;
    int
    strcmp();
    Rec_t
        *temp;

    for (gap = size / 2; gap > 0; gap /= 2)
	for (i = gap; i < size; ++i)
	    for (j = i - gap; j >= 0; j -= gap)
	    {
		if (strcmp(rptr[j]->key, rptr[j + gap]->key) <= 0)
		    break;
		temp = rptr[j];
		rptr[j] = rptr[j + gap];
		rptr[j + gap] = temp;
	    }
}

int	hash(register char *name)
{
    register	int	i;

    i = 0;
    while(*name) {
	i += *name++ ;
    }
    return(i) ;
}