Hashing strings for faster comparisons

	String may be stored in a hash table, after which the strings
	are identified with a pointer, called a [[Strip]]. Equal
	strings have equal pointers. The hashing alogorithm is set up
	in such a way that it is also easy to compare strings
	case-independently. There are two routines (macros) that do
	this:

	[[hfcase_eq]] is an `unreliable' function, in the sense that a
	return of [[FALSE]] means that the strings are indeed unequal,
	but a return of [[TRUE]] has a small chance of being incorrect.

	[[hcase_eq]] is its reliable counterpart.

	To convert from string to Strip: [[str2strip(char *s)]]; to
	convert from Strip to string: [[strip2str(Strip s)]]

	The size of the hash table is always a compromise. It must be
	as large as possible to minimize the risk of collisions, but
	it must also occupy a reasonable amount of memory.

	The hash function computes a number for a string by combining
	the lower 7 of the 8 bits of each of the characters.
	Discarding the 5th bit has the effect of mapping upper and
	lowercase characters to the same hash code.

<<*>>=
#include <config.h>
#include "heap.e"
#include "equal.e"
#include "uppercase.e"

EXPORT typedef struct _Strip {
    char *s;
    unsigned int hashix;
    struct _Strip *next;
} *Strip;

#define HASHSIZE 5003
EXPORTDEF(HASHSIZE)

static Strip table[HASHSIZE];
static unsigned int init1[HASHSIZE], init2[HASHSIZE];
static unsigned int ninit = 0;

#define hfcase_eq(a, b) ((a)->hashix == (b)->hashix)
EXPORTDEF(hfcase_eq(a, b))

#define hcase_eq(a, b) (hfcase_eq(a, b) ? case_eq((a)->s, (b)->s) : FALSE)
EXPORTDEF(hcase_eq(a, b))

#define strip2str(x) ((x) ? (x)->s : "")
EXPORTDEF(strip2str(x))

#define strip2hash(x) ((x) ? (x)->hashix : 0)
EXPORTDEF(strip2hash(x))

static unsigned int hashfunc(const char *name)
{
    const char *p;
    unsigned int h = 0, g;
    
    for (p = name; *p; p++) {
	h = (h << 4) + (*p) & 0337;
	if (g = h & (unsigned int) 0xf0000000) {
	    h = h ^ (g >> 24);
	    h = h ^ g;
	}
    }
    return h % HASHSIZE;
}

EXPORT Strip str2strip(const char *s)
{
    unsigned int h;
    Strip p;

    h = hashfunc(s);
    /*
     * Check if table[h] is initialized; if not, initialize it
     */
    if (init1[h] >= ninit || init2[init1[h]] != h) {
	init2[init1[h] = ninit++] = h;
	table[h] = NULL;
    }
    /*
     * See if the string is already in the table
     */
    for (p = table[h]; p; p = p->next)
	if (eq(s, p->s)) return p;
    /*
     * Not found; create new table entry
     */
    new(p);
    p->s = newstring(s);
    p->hashix = h;
    p->next = table[h];
    table[h] = p;
    return p;
}


#define MAXSTRIP 1024				/* Arbitrary restriction */


EXPORT Strip strn2strip(const char *s, int n)
{
    char t[MAXSTRIP];

    t[0] = '\0';
    strncat(t, s, n);
    return str2strip(t);
}


EXPORT Strip stru2strip(const char *s)
{
    char t[MAXSTRIP];

    strcpy(t, s);
    uppercase(t);
    return str2strip(t);
}


EXPORT Strip strnu2strip(const char *s, int n)
{
    char t[MAXSTRIP];

    t[0] = '\0';
    strncat(t, s, n);
    uppercase(t);
    return str2strip(t);
}