/*****************************************************************************
 ** FILE	: hash.c
 ** AUTHOR	: Peter Eussen 
 ** DATE        : 21 Dec 1997
 ** VERSION	: 1.0
 ** DESCRIPTION : A set of routines to store and retrieve records needed by
 **               the generation process. It can handle an unlimited amount
 **               of tables if required, varying in size.
 ** MODIFICATIONS:
 **
 ***************************************************************************/
#define HASH_C
#include <stdlib.h>
#include <stdio.h>
#include "hash.h"
#include "gen.h"

/****************************************************************************
 ** freeHashRecord: Releases memory in a  hash Record.
 ** 
 ** input parameters:
 **    hashRecord * = Pointer to a record that needs to be freed.
 ** output parameters:
 **    none.
 ***************************************************************************/
void freeHashRecord(hashRecord *ptr)
{   if (ptr == NULL)
       return;

    /* Free all pointers in the data structure */
    if (ptr->id != NULL)
       xfree(ptr->id,REC_CHAR);
 
    /* Free the ptr */
    xfree(ptr,REC_HRECORD);
}

/***************************************************************************
 ** createHashRecord: Creates a record for the given id
 **
 ** input parameters:
 **     id   = identification for this record.
 ** output parameters:
 **     NULL         = memory allocation failed.
 **     hashRecord * = pointer to the record.
 **************************************************************************/
hashRecord *createHashRecord(char *id,long idnum)
{   hashRecord *p;

    /* if we were to allow NULL type keys, we would have a problem with 
     * calculating a hash index and with retrieving the record, so we check
     * to make sure it doesnt happen in any case
     */
    if (id == NULL)			
       return NULL;

    p = memAlloc(hashRecord,1,REC_HRECORD);
    if (p != NULL)
    {   /* Ok, we have reserved a record for this key, now copy the key into
         * the id field. But first allocate enough bytes to allocate the key
         * since the length of the keys can differ drastically in size (this
         * code can handle almost all type of keys if you modify the 
         * calHashKey function.
         */
        p->id = memAlloc(char,strlen(id) + 1,REC_CHAR);
        p->idnumber = idnum;
        strcpy(p->id,id);
        /* Little bit of protection for ourselves. Make all records all
         * lowercase to prevent Zonename confusion.
         */
        lowercase(p->id);
    }
    return p;
}

/****************************************************************************
 ** createHashTable: Creates a hash table, with the given size, how original! 
 **
 ** Input parameters:
 **    size_t size = The size of the table.
 ** Output parameters:
 **    hashTable * = pointer to the main hashtable record, or NULL if the
 **                  table wasn't created for some reason.
 ****************************************************************************/
hashTable *createHashTable(size_t size)
{   hashTable  *thashTableptr;		/* Temporary hashTable pointer */
    hashRecord **thashRecordptr;	/* Temporary hashRecord Pointer */
    hashRecord *p;			/* I couldnt figure out how to get
					 * memAlloc working so i did it with
					 * this pointer
					 */

    /* First we try to reserve space for the overall hashTable record type.
     * If this fails, then we don't have to try attempting to allocate space
     * for the table.
     */
    if ((thashTableptr = (hashTable *) memAlloc(hashTable,1,REC_HTABLE)) != NULL) 
    {   /* We have the hashTable record available now, now lets see if we
         * have enough memory to create the table.
         */
        thashRecordptr = memAlloc((p),size,REC_HRECORD);

        if (thashRecordptr != NULL)
        {   thashTableptr->size = size;
            thashTableptr->hashtable = thashRecordptr;
            /* Since memAlloc uses calloc, we dont have to set all pointers to
             * NULL, since calloc does that for us.
             */
        }
        else
        {   /* allocation of hashtable failed, release memory of reserved 
             * hashTable record.
             */
            xfree(thashTableptr,REC_HTABLE);
            thashTableptr = NULL;
        }
    }
    return thashTableptr;
}

/******************************************************************************
 ** calcHashKey: Calculates the hashkey from a character string. Since much of
 **             the performance of the hashtable will depend on this, the 
 **             calculation of the key may have to be different than the way
 **             it is now.. it all depends on the size of the table and the
 **             keys.
 ** 
 ** input parameters: 
 **     char   *id  = string that is used to calculate the hashIndex
 **     size_t size = size of the table.
 ** output parameters:
 **     hashKey  = hash key.
 *****************************************************************************/
hashKey calcHashKey(char *id,size_t tablesize)
{  hashKey tempkey=1;
   int     i;

   for (i = 0; id[i] != '\0'; i++)
   {   if (id[i] == '@')
          continue;

       if ((i+1 % 3) > 0)
          tempkey += (long) id[i] * tempkey;
       else
          tempkey *= (long) id[i];
   }

   /* Mod tablesize to ensure the returned index lies within the table limit,
    * so we don't get SIGSEGV's etc. The functio above can give results
    * ranging from 90 till 2 Billion (long int limit). Only way it will crash
    * is when the multiplication goes above 2 Billion.
    */
   return tempkey % tablesize;		
}

/*****************************************************************************
 ** addHashRecord: Adds a record to the table
 ** 
 ** Input parameters:
 **     hashRecord * = A pointer to the record that should be added.
 **     hashTable  * = A pointer into which the record should be added.
 ** Output parameters:
 **     -1 = Faulty parameters give to the function.
 **     0  = Eep! the record was already in the hashtable.
 **     1  = Record has been added. 
 *****************************************************************************/
int addHashRecord(hashRecord *newptr, hashTable *to)
{   hashKey index;
    
    /* Not even going to consider adding in these situations
     */
    if (newptr == NULL || newptr->id == NULL || to == NULL)
       return -1;

    /* If there already is a record with this ID, then we can't add it. We
     * have to have an unique id for each Record.
     */
    if (findHashRecord(newptr->id,to) != NULL)
       return 0;

    /* Calculate a key for the id so we can start inserting it in the right
     * place.
     */
    index = calcHashKey(newptr->id,to->size);
   
    /* This is for debugging of the hashtable only. The number of collisions
     * should be as small as possible when inserting, cause that will mean
     * lookup will be more succesfull as well.
     */
    if (to->hashtable[index] != NULL)
       to->insertcollisions++;

    /* Simply insert it at the top, so we dont need to check for collisions
     */ 
    newptr->next = to->hashtable[index];
    to->hashtable[index] = newptr;
    to->elems_stored++;
    return 1; 
}

/*****************************************************************************
 ** findHashRecord: Finds a hashtable record for a given id.
 **
 ** input parameters:
 **    id       = identifier for that record.
 **    hashTable= The table in which it supposidly was stored.
 ** output parameters:
 **    NULL        = record not found, or table is non-exsistant
 **    HashRecord *= pointer to the hashrecord for that id.
 ***************************************************************************/
hashRecord *findHashRecord(char *id,hashTable *table)
{   hashKey    key;
    hashRecord *tptr;

    if (id == NULL || table == NULL)
       return NULL;		/* Can't find anything with NULL's */

    /* Find the index within the hash table we should be able to find the key
     * if its inserted.
     */
    key = calcHashKey(id,table->size);

    tptr = table->hashtable[key];

    /* Now loop through the possible linked list at this position in the 
     * hashtable. If the id is in this list, then we return a pointer to
     * that record.
     */
    while (tptr != NULL)
    {   if (tptr->id[0] == id[0] && tptr->id[strlen(tptr->id)-1] == id[strlen(id)-1])
          if (strcmp(id,tptr->id) == 0)
             return tptr;

        /* This is for debugging only. It counts the amount of failed lookups 
         * its to do before the record requested is found. 
         */
        table->findcollisions++;
        tptr = tptr->next;
    }

    /* Key not found in chain, or there was no chain at this key.
     */
    return NULL;
}

/****************************************************************************
 ** deleteHashRecord: Deletes a record from the hashtable
 **
 ** input parameters:
 **    id    = String to identify the record that needs to be deleted.
 **    from  = Table where the record should be deleted from.
 ** output parameters:
 **    -1    = invalid parameters
 **    0     = record not found.
 **    1     = record deleted.
 **************************************************************************/
int deleteHashRecord(char *id,hashTable *from)
{  hashKey    key;
   hashRecord *recptr,*t;

   /* We do not store NULL id's and we can't delete from a non-exsistant
    * hashtable.
    */
   if (id == NULL || from == NULL)
      return -1;

   /* First calculate the key and try to find it. So we have the position and
    * a pointer to the record to clearly identify the target when we find it.
    */
   key = calcHashKey(id,from->size);
   recptr = findHashRecord(id,from);

   /* Hmm, the find failed.. That must mean the id is not stored in this table.
    * Nothing to do.. return 0.
    */
   if (recptr == NULL)
      return 0;

   if (from->hashtable[key] == recptr)
   {   /* First see if the one we want to delete is the first in line, cause
        * they always require special attention.
        */
       from->hashtable[key] = recptr->next;
       freeHashRecord(recptr);
       return 1;
   }  
   else
   {   t = from->hashtable[key];

       /* Cycle through the linked list untill we find a record which next 
        * value points to the one we are seeking.
        */
       while (t->next != recptr && t->next != NULL)
         t = t->next;

       if (t->next == recptr)
       {   /* Ok we found it. Now remove the to be deleted record from the
            * linked list and delete it.
            */
           t->next = recptr->next;
           freeHashRecord(recptr);
           from->elems_stored--;
           return 1;
       }
   }

   /* Hmm we reached the end of the linked list and still havent found it, so
    * it must mean that for some reason it cant be found. Well.. nothing to do
    * so return 0.
    */
   return 0;
}
   
/*****************************************************************************
 ** deleteHashTable: Oh my, we're gonna free up some memory here!
 **
 ** input parameters:
 **     thistable = pointer to the table that should be deleted.
 ** output parameters:
 **    -1 = invalid parameter.
 **    1  = The table is history!
 **************************************************************************/
int deleteHashTable(hashTable *thistable)
{   hashRecord *p, *q;
    hashKey    i;

    /* Nothing to delete if the table doesnt exsist. 
     */
    if (thistable == NULL || thistable->hashtable == NULL)
      return -1;

    /* Delete all records in the table 
     */
    for (i=0 ; i < thistable->size; i++)
    {   p = thistable->hashtable[i];
        
        /* Delete all records that are in this entry of the linked list.
         */
        /*printf("Slot %ld\n",i);*/
        while (p != NULL)
        {   q = p->next;
            /*printf("   Freeing: %s\n",p->id);*/
            freeHashRecord(p);
            p = q;
        }
    }

    /* Delete table 
     */
    xfree(thistable->hashtable,REC_HRECORD);
    xfree(thistable,REC_HTABLE);
    return 1;
}

/*****************************************************************************
 ** printHashTableStatistics: Prints some statistics about the usage of the
 **       hashtable, as elements stored and collisions.
 ** 
 ** input parameters:
 **    h = pointer to a valid hashtable.
 *****************************************************************************/
void printHashTableStatistics(hashTable *h)
{    if (h != NULL)
        printf("HashTable statistics:\n"
               " Hash Table size : %d\n"
               " Elements stored : %d\n"
               " Store Collisions: %d\n"
               " Find Collisions : %d\n",
               h->size,h->elems_stored,h->insertcollisions,h->findcollisions);
}

/*****************************************************************************
 ** ymalloc: A memory allocation function which does some checking and 
 **          produces some debugging info for when it occurs. To use this
 **          function call the memAlloc() macro.
 **          memAlloc requires to parameters:
 **              Element: the type or record/datatype you wish to allocate 
 **                       (ie char, hashTable or somesuch).
 **              Number : The number of elements you want to allocate.
 ** input parameters:
 **    size    = size of the record/datatypes structure
 **    nmembers= amount of records/datatypes to reserve (for arrays)
 **    file    = filename of the code file where the error occured.
 **    line    = linenumber of the code file where this function was called
 **              from.
 **
 ** output parameters:
 **    a pointer of the type void that points to the assignmed memory or NULL
 **    if the memory allocation failed.
 *****************************************************************************/
void *ymalloc(size_t size, size_t nmembers,int typenr,char *file, int line)
{   void *ptr;

    ptr = calloc(nmembers,size);
    
    if (ptr == NULL)
    {  fprintf(stderr,"Allocation of memory failed, could not allocate %d bytes\n"
                      "    Total Memory usage: %ld\n"
                      "    Size of element   : %d\n"
                      "    Number of elements: %d\n"
                      "    File: %s    Line: %d\n",nmembers * size,mem_usage,
		      size,nmembers,file,line);
       exit(1);
    }
#ifdef MEMORY_STATISTIC
    updateMemStat(typenr,nmembers);
#endif
    mem_usage += size * nmembers;
    return ptr;
}