//====================================================================
// AeInstHash.c++
//
// based on hash.c++ in PR/tools/audio/banktools/libbank/
//
// 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 <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "AeInstHash.h"
#include "AeInstFile.h"

extern verbose;


AeInstHash::AeInstHash (void)
{
    int	i;

    for (i=0; i<kTableSize; i++)
	hashtable[i] = NULL;
}

AeInstHash::~AeInstHash (void)
{
#ifndef NDEBUG
    if (0)	// disable completely for release
    {
	AeInstID *	id;
	int		i;
	int		nCollisions = 0;
	int		nEmpty = 0;

	for (i=0; i<kTableSize; i++)
	{
	    if (id = hashtable[i])
	    {
		printf ("%d: ", i);
		while (id)
		{
		    printf ("%s -> ", id->name);
		    id = id->next;
		    if (id) nCollisions++;
		}
		printf ("NULL\n");
	    }
	    else
		nEmpty++;
	}
	printf ("\n# collisions = %d\n# empty = %d\n", nCollisions, nEmpty);
    }
#endif
}


//
// A simple and mediocre hash table implementation.  This will go into
// an infinite loop when the hash table fills up.
//
AeInstID *
AeInstHash::Enter (int lextype, char * str, int len)
{
    int		i = hash (str);
    AeInstID *	id = hashtable[i];

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


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

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

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

	while (id)
	{
	    if (id->next == NULL)
	    {
		id->next = newid;
		break;
	    }
	    id = id->next;
	}
    }

    return newid;
}


//
// 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.
//
AeInstID *
AeInstHash::resolveCollision (int i, char * str)
{
    AeInstID * id = hashtable[i];

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

	id = id->next;
    }

    return id;
}


//
// This returns an integer hash value for a string.
// Value is guaranteed to be a valid table index.
//
int
AeInstHash::hash (char * str)
{
    char c;
    int h = 0;

    while ((c = *str++) != '\0')
        h = (h * M1 + (int) c);

    return h & (kTableSize - 1);
}