#include <stdio.h>
#include "userdefs.h"
#include "hashdefs.h"
#define FALSE 0
#define TRUE  1

/*  HASHLIB.C         
    Peter Dill        
    
      HASHLIB.C is a collection of functions to define, create, and manipulate
    a generic hashtable. A hash table is an array whose indexes are related
    to the data stored there. This allows an element to be found in the time
    it takes to compute the index (called hashing) regardless of the number
    of items stored. This is contrast to a binary tree where the time to find
    an item can be log(base 2)n or a linked list, n. 
      Different keys can generate the same hashindex, so when a collision 
    occures a linked list is made. So if the ratio of hashtable slots to
    items stored rises, preformance denegrates toward a linked list case.
      The memory for the hashtable here is calloc'ed so its size is determined
    by calling program. 
      The hashtable is generic in the sence that the type of items it stores
    is determined by the definition of 'element' that the user provides in
    "userdefs.h". The hashtable contains pointers to a structure called
    'packet' which contains an 'element' and a pointer to another 'packet'.
    This allows for a linked list. The definition of 'packet' is in
    "hashdefs.h".
    
   For a program to interface with the functions four things are needed:
 
   1. external typedef needed for `element' which is the type for the user
      data. Placed in "userdefs.h"
   2. retkey() is an externally defined function which returns the key field
      of an instance of `*element'.
   3. copyelement() copies arg2 to arg1 where the args are of type element.
   4. deleteelement() which takes a pointer to an element and deletes the 
      dynamically allocated memory, if any, associated with it.
   These functions are placed in a file with the rest of the user code.
   
   Remember to compile and link with long integers.
*/

extern char* malloc();
extern char* calloc();

long TableSize;
struct packet **ht;


#define computehash1(k,h)\
for (;(k[ii] != '\0') && (ii < 4); ii++)\
  {\
    c1 <<= 7;\
    c1 |= k[ii];\
  }\
for (;(k[ii] != '\0') && (ii < 8); ii++)\
  {\
    c2 <<= 7;\
    c2 |= k[ii];\
  }
      
#define computehash2(k,h)\
for (;(k[ii] != '\0') && (ii < 12); ii++)\
  {\
    c3 <<= 7;\
    c3 |= k[ii];\
  }\
c3 <<= 2;\
c2 <<= 1;\
h = (c1 ^ c2 ^ c3) % TableSize;


void deletechain(lst)
  struct packet  *lst;
  {
    struct packet *cur, *next;
    
    if ( (cur = lst) == NULL)
        return;
    for (next = cur->next; next != NULL; cur = next, next = next->next)
      {
        deleteelement(&(cur->data));
        free (cur); 
      }
    deleteelement(&(cur->data));
    free (cur);
  }

struct packet* makepacket(dt)
  element  *dt;
  {
    struct packet *ptr;
    
    ptr = (struct packet*) malloc ((long) sizeof (struct packet));
    if (ptr == NULL)
      {
        puts("\n could not allocate memory");
        return(FALSE);
      }
    ptr->next = NULL;
    copyelement(&(ptr->data), dt);
    return(ptr);
  }
  
  /* input is the size for the new hash table. The return value is true if
      the table was sucessfully made. It is desireable to have the size
      equal to the maximum number of elements to be stored in the array.
  */
short makehash(size)
  long size;
  {
    long    i;
    
    if ( ((size >>1) <<1) == size)
        size += 1;     /* change to an odd */
    TableSize = size;   /* global, user wont have to keep passing the value*/
    ht = (struct packet**) calloc(size, sizeof(struct packet*) );
    if (ht == NULL)
      {
        fprintf(stderr,"\n Could not allocate memory for a  %d table",
            TableSize);
        return(FALSE);
      }
    if (ht[3] != NULL)
        for (i=0; i < TableSize; i++)
            ht[i] = 0;  /* make sure the pointers are zeroed just in case */
    return (TRUE);
  }

  /* Input is a pointer to an element. If record with a same key as that of
     the input element is already in the table the item will not be added.
     Otherwise a new record is created with the same field as those of the
     input and is added to the table at the end of a list. A pointer to this
     new record is returned. NULL indicates a failure.
  */
element* inserthash(dt)
  element *dt;
  {
    register unsigned long  c1 = 0, c2 = 0, c3 = 0;
    register short ii=0;
    char   *key;
    unsigned long   hashindex;
    struct packet *ptr, *tmp;
    
    key=retkey(dt);
    computehash1(key,hashindex);
    computehash2(key,hashindex);
    for (tmp = ht[hashindex]; (tmp != NULL); tmp = tmp->next)
        if (strcmp(key, retkey(&(tmp->data))) == 0)
            return (NULL);          /* duplicate element */
    ptr = makepacket(dt);
    if (ptr == NULL)
        return (NULL);
    ptr->next = ht[hashindex];
    ht[hashindex] = ptr;
    return &(ptr->data);    
  }


  /* Deletes the record with the key given by the input parameter. If
     no such record exists then FALSE is returned.
  */
short deletehash(key)
  char  key[];
  {
    register unsigned long  c1 = 0, c2 = 0, c3 = 0;
    register short ii=0;
    unsigned long    hashindex;
    struct packet **ptr, **parent;

    computehash1(key,hashindex);
    computehash2(key,hashindex);
    if (ht[hashindex] == NULL)
        return(FALSE);
    parent = ptr = &(ht[hashindex]);
    while ( (*ptr != NULL) && (strcmp(key, retkey(&((*ptr)->data))) !=0) )
      {
        parent = ptr;
        ptr = &((*ptr)->next);  
      }
    if (*ptr == NULL) 
        return(FALSE);
    if (parent == ptr)               /* item sought is the at the head */        
      {
        ht[hashindex] = ht[hashindex]->next;
        free(*ptr);
      }
    else
      {
        (*parent)->next = (*ptr)->next;
        free(*ptr);
        *ptr = NULL;
      }
    return(TRUE);
  }
 
  /* Returns a pointer to the element that has the key given in the input
     parameter. If no such item is in the table, NULL is returned.
  */
element* findhash(key)
  char  key[];
  {
    register unsigned long  c1 = 0, c2 = 0, c3 = 0;
    register short ii=0;
    unsigned long    hashindex;
    struct packet *ptr;

    computehash1(key,hashindex);
    computehash2(key,hashindex);
    if (ht[hashindex] == NULL)
        return(NULL);
    ptr = ht[hashindex];
    while ( (ptr != NULL) && (strcmp(key, retkey(&(ptr->data))) != 0) )
      {
        ptr = ptr->next;    
      }
    if (ptr == NULL) 
        return(FALSE);
    return(&(ptr->data));   
  }

  /* Used to get access to every item in the table sequentially. Returns
     a pointer to the element which follows in the table the record with 
     the key given by the input parameter. To start pass the value NULL.
     A return value of NULL from the function indicates that all the input 
     parameter was the key for the last item in the table or it wasn't
     present.
  */
element *dumphash(last)
  char  last[];
  {
    register unsigned long  c1 = 0, c2 = 0, c3 = 0;
    register short ii=0;
    unsigned long loc, flag;
    struct packet *pos;
    
    if (last == NULL)
        loc = 0;
    else
      {
        computehash1(last,loc);
        computehash2(last,loc);
        for (flag = FALSE, pos = ht[loc]; pos != NULL;  pos = pos->next)
            if (strcmp(retkey(&(pos->data)), last) == 0)
              {
                flag = TRUE;                
                if (pos->next != NULL)
                    return &(pos->next->data);
              }
        if (flag == FALSE)
            return NULL;
        loc++;
      }
    for ( ;(ht[loc] == NULL) && (loc < TableSize); loc++)
        ;
    if (loc == TableSize)
        return (NULL);
    else
        return &(ht[loc]->data);
  }

  /* called before the user program exits to free all dynamic memory */
void freehashtable()
  {
    long    i;
    
    for(i=0; i<TableSize; i++)
        if (ht[i] != NULL)
            deletechain(ht[i]);
    free(ht);
  }