//====================================================================
// hash.c++
//
// Copyright 1993, Silicon Graphics, Inc.
// All Rights Reserved.
//
// This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
// the contents of this file may not be disclosed to third parties, copied or
// duplicated in any form, in whole or in part, without the prior written
// permission of Silicon Graphics, Inc.
//
// RESTRICTED RIGHTS LEGEND:
// Use, duplication or disclosure by the Government is subject to restrictions
// as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
// and Computer Software clause at DFARS 252.227-7013, and/or in similar or
// successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
// rights reserved under the Copyright Laws of the United States.
//====================================================================

#include <stdlib.h>
#include <string.h>
#include "libbank.h"

/*
 * A simple and mediocre hash table implementation.
 * 
 * This version no longer can overflow the table and get
 * stuck in an infinite loop.  Now each hash table entry
 * is a linked list so all entries that hash to the same
 * address are just appended to the linked list.
 *
 * With a table size of 1024, we could support over 1000
 * sounds each with its own wave, keymap, and env with
 * an average of 5 entries per hash table address.
 */

#define	TABLESIZE	1024		/* must be a power of 2 */
#define M1		71
#define M2		578393
#define M3		358723

static id *	hashtable[TABLESIZE];

static id *	appendNewEntry (int i, int lextype, char *, int len);
static id *	resolveCollision (int i, char *);
static int	hash (char *);


id *ICSymTab::Enter(int lextype, char *str, int len)
{
    int		i = hash (str);
    id *	entry = hashtable[i];

    if (entry == NULL || (entry = resolveCollision (i, str)) == NULL)
	entry = appendNewEntry (i, lextype, str, len);
            
    return entry;
}


/*
 * This returns an integer hash value for a string.
 * Value is guaranteed to be a valid table index.
 */
static int
hash(char *str)
{
    char c;
    int h = 0;
    while ((c = *str++) != '\0')
        h = (h * M1 + (int) c);
    
    return h & (TABLESIZE - 1);
}


/*
 * This allocates memory for a new entry, initializes
 * its fields, and appends it to the hash table address's
 * linked list.
 */
static id *
appendNewEntry (int i, int lextype, char * str, int len)
{
    id *	newentry;
    id *	entry;

    // allocate and init an id entry
    newentry = new id;
    newentry->next = NULL;
    newentry->lextype = lextype;
    newentry->name = (char *) malloc (len+1);
    strcpy (newentry->name, str);

    // append entry to the hash table location
    if (hashtable[i] == NULL)
	hashtable[i] = newentry;
    else
    {
	entry = hashtable[i];

	while (entry)
	{
	    if (entry->next == NULL)
	    {
		entry->next = newentry;
		break;
	    }
	    entry = entry->next;
	}
    }

    return newentry;
}


/*
 * This routine resolves a hash table address
 * with one or more entries linked onto its list.
 * Returns a matched entry id or NULL if no
 * match is made.
 */
static id *
resolveCollision (int i, char * str)
{
    id * entry = hashtable[i];

    while (entry)
    {
	if (!strcmp(entry->name, str))
	    break;

	entry = entry->next;
    }

    return entry;
}