/***************************************************************************
 *  Columbia University Introduction to Computer Programming in C COMS 1003
 *  Hashtable
 *
 *  Copyright (C) 2005 Michael E. Locasto
 *
 *  All rights reserved.
 *
 * $Id: hash.c,v 1.1 2005/11/17 17:19:00 locasto Exp $
 **************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM_ELEMENTS  1001

const char USED = 'U';
const char UNUSED = '\0';

/**
 * Define a template for holding an entry in a hash table 
 */
struct hash_entry
{
   int key;
   int data;
   char used;
   struct hash_entry *next;
};

/* Declare a collection of the hash_entry nodes. 
 * This is the hashtable. Note that memory for NUM_ELEMENTS
 * structures is statically allocated. If this were an array
 * of pointers, then only memory for NUM_ELEMENTS pointers
 * would be allocated.
 */
struct hash_entry hashtable[NUM_ELEMENTS];

void    init_hashtable(void);
void    print_hashtable(void);
int     put(int, int);
int     put_single(int);
void    simple_put(int);
int     get(int);

void print_hashtable(void)
{
   int i = 0;
   struct hash_entry *entry_ptr = NULL;

   for(i=0;i<NUM_ELEMENTS;i++)
   {
      printf("hashtable[%4d] = {",i);
      if(USED==hashtable[i].used)
      {
         printf("%d",hashtable[i].data);
         entry_ptr = hashtable[i].next;
         while(NULL!=entry_ptr)
         {
            printf(" -> %d",entry_ptr->data);
            entry_ptr = entry_ptr->next;
         }
      }
         
      printf("}\n");
   }
   printf("\n");
}

void init_hashtable(void)
{
   int i = 0;
   for(i=0;i<NUM_ELEMENTS;i++)
   {
      hashtable[i].key = 0;
      hashtable[i].data = 0;
      hashtable[i].used = UNUSED;
      hashtable[i].next = NULL;
   }
}

int put_single(int value)
{
   return put(value%NUM_ELEMENTS, value);
}

void simple_put(int value)
{
   int key = value % NUM_ELEMENTS;
   hashtable[key].key = key;
   hashtable[key].used = USED;
   hashtable[key].data = value;
}

/**
 * Insert into the hashtable and replace whatever element was stored
 * at this key location.
 * Look up the location. Allocate new memory for it if need be. 
 */
int put(int key, int value)
{
   int target = 0;
   struct hash_entry *entry_ptr;
   struct hash_entry *previous_entry_ptr;
   struct hash_entry *new_entry_ptr;

   target = key % NUM_ELEMENTS;
   //assert(target<NUM_ELEMENTS && target>=0);
   if(UNUSED == hashtable[target].used)
   {
      hashtable[target].used = USED;
      hashtable[target].key = key;
      hashtable[target].data = value;
      hashtable[target].next = NULL;
   }else{
      //collision
      //need to look at next and see if non-null. traverse
      //down next until you come to null, then add an
      //element
      entry_ptr = hashtable[target].next;
      previous_entry_ptr = entry_ptr;
      while(NULL!=entry_ptr)
      {
         previous_entry_ptr = entry_ptr;
         entry_ptr = entry_ptr->next;
      }
      new_entry_ptr = (struct hash_entry*)malloc(sizeof(struct hash_entry));
      if(NULL==new_entry_ptr)
      {
         fprintf(stderr,"could not allocate memory for new entry");
         return -1;
      } 
      new_entry_ptr->used = USED;
      new_entry_ptr->key = key;
      new_entry_ptr->data = value;
      new_entry_ptr->next = NULL;
      if(NULL==previous_entry_ptr)
      {
         hashtable[target].next = new_entry_ptr;
      }else{
         previous_entry_ptr->next = new_entry_ptr;
      }

   }

   return 0;
}

int get(int key)
{
   return hashtable[key%NUM_ELEMENTS].data;
}

/**
 * Simple hashtable
 *
 * 
 */
int main(int argc, char* argv[])
{
   int i = 0;
   init_hashtable();

   put(2,2);
   put(2,5);
   put(2,7);
   put_single(29);
   put_single(20045);

   simple_put(4100);
   simple_put(100);

   printf("%d\n",get(2));

   /*
   srand(time(NULL));
   for(i=0;i<10000;i++)
   {
      put_single(rand()%500000);
   }
   */

   print_hashtable();
   return 0;
}