/************************************************************************
 * hash.c
 * Copyright (C) 2002 Marcello Barnaba
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 1, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * FNV rocks.
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <err.h>
#include <errno.h>
#include <sys/types.h>

extern int errno;

#define HASHSIZE	223
#define BUFSZ		64

typedef unsigned long hash_t;

typedef struct nlist
{
    char *name;
    char *defn;
    unsigned short f_o, l_o;
    struct nlist *next;
} Nlist;

static Nlist *hashtab[HASHSIZE];

static __inline__ char *xstrdup(char *s)
{
    char *ret = strdup(s);
    if(!ret)
	err(-1, "out of memory");
    return ret;
}

static __inline__ void *xmalloc(size_t sz)
{
    void *ret = malloc(sz);
    if(!ret)
	err(-1, "out of memory");
    memset(ret, 0x0, sz);
    return ret;
}

static __inline__ void xfree(void *p)
{
    if(p)
	free(p);
}

/* 
 * Fowler / Noll / Vo (FNV) Hash . .
 * Noll, Landon Curt (LCN2)
 * chongo <was here> /\../\
 *
 * #define HASH(sta, end, hash) while(end != sta) { hash = ((hash * 16777619UL) ^ (*end--)) }
 */

#define FNV_prime	16777619UL

__inline__ hash_t fnv_hash(char *s)
{
    hash_t h = 0;
    char *e = s + strlen(s) - 1;

    while(e != s)
	h = ((h * FNV_prime) ^ *e--);

    return h % HASHSIZE;
}

Nlist *lookup(char *s)
{
    Nlist *np = hashtab[fnv_hash(s)];

    for(; np; np = np->next)
	if(strcmp(s, np->name) == 0)
	    return np;
    return NULL;
}

Nlist *insert(char *n, char *d, unsigned short occ)
{
    Nlist *np = lookup(n);

    if(np == NULL)
    {
	Nlist **trav;

	np = xmalloc(sizeof(Nlist));
	np->name = xstrdup(n);
	np->defn = xstrdup(d);
	np->f_o = np->l_o = occ;

	trav = &hashtab[fnv_hash(n)];
	if(*trav)
	{
	    for(; *trav && (*trav)->next; *trav = (*trav)->next);
	    (*trav)->next = np;
	}
	else
	    (*trav) = np;
	return np;
    }
    else if(strcmp(np->defn, d))
    {
	fprintf(stderr, "warning, %s redefined from \"%s\"[%d] to \"%s\"\n",
		n, np->defn, np->l_o, d);
	xfree((void *)np->defn);
	np->defn = xstrdup(d);
	np->l_o = occ;
	return np;
    }
    return NULL;
}

void hash_acquire(char *f)
{
    FILE *in;
    char bufn[BUFSZ], bufd[BUFSZ];
    unsigned int linenum, r;

    memset(hashtab, 0x0, sizeof(hashtab));
    
    if(!f || (f[0] == '-' && f[1] == '\0'))
    {
	in = stdin;
	fprintf(stderr, "using standard input as input stream.\n");
    }
    else if((in = fopen(f, "r")) == NULL)
	err(1, "cannot open input file %s", f);

    linenum = 0;
    while((r = fscanf(in, "%64s -> %64s\n", bufn, bufd)) != EOF)
    {
	linenum++;
	(r == 2) ? 
	    insert(bufn, bufd, linenum) :
	    (void) printf("parse error.\n");
    }
}

void hash_print(void)
{
    unsigned short i = 0;
    Nlist *trav;

    for(; i < HASHSIZE; ++i)
    {
	if((trav = hashtab[i]))
	{
	    printf("hashtab[%d]: ", i);
	    for(; trav; trav = trav->next)
		printf("define %s -> %s; ",
			trav->name, trav->defn);
	    puts("");
	}
    }
}

void hash_query(void)
{
    char buf[BUFSZ];

    printf("insert a word to search into hashtable: ");
    while(fscanf(stdin, "%64s", buf) != EOF)
    {
	Nlist *np;
	((np = lookup(buf))) ? 
	    printf("found in hashtab[%ld]: %-20s | defn: %-20s | f_o: %10d | l_o: %10d\n",
		    fnv_hash(buf), np->name, np->defn, np->f_o, np->l_o) :
	    printf("not found.\n");
        printf("insert a word to search into hashtable: ");
    }
}

static __inline__ void version(char *me)
{
    fprintf(stderr, "%s: version 0.6\n", me);
}

static __inline__ void usage(char *me)
{
    fprintf(stderr, "%s: usage:\n"
	    "  -f <file>  --  use <file> as your input\n"
	    "  -h         --  this crap\n"
	    "  -v         --  version crap\n",
	    me);
}

int main(int argc, char **argv)
{
    char *f = NULL;

    extern int optind, optopt;
    extern char *optarg;

    int c;

    while((c = getopt(argc, argv, "f:vh")) != -1)
    {
	switch(c)
	{
	    case 'f':
		f = xstrdup(optarg);
		break;
	    case 'v':
		version(argv[0]);
		exit(0);
		break;
	    case 'h':
		usage(argv[0]);
		exit(1);
		break;
	    case '?':
		switch(optopt)
		{
		    case 'f':
			exit(1);
		}
	}
    }

    argv += optind;
    argc -= optind;

    hash_acquire(f);

    hash_print();

    hash_query();

    return 0;
}