/* this program has two main functions. INSERT inserts N integers into
a hash table of size LENGTH (defined below)
N is an input to the program. The table holds keys which are random integers
as well as a pointer to a Linked List of items which collide at this location.

Our hash function simply takes the key modulo the table size.

It also has a function  SEARCH which looks up N random keys in the tabel
created by INSERT (in this version the call to SEARCh is commented out)

The program is set up to count the number of probes used in these experiments
and to time them.
*/

#define LENGTH 1048576  /* Table size */
#define REPEAT 6   /* number of times to run the experiment */


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


struct ENTRY
{
 int            key;
 struct ENTRY * pointer;
}
Table[LENGTH];

int N; /* number of items to be inserted */


int insert(void)
/* this function inserts the entries in the hash table */
{
 struct ENTRY  *new, *old;
 unsigned int  count, i, index, key, not_inserted;

 count = 0;  /* this counts the number of probes to insert all items. should be removed
                when doing timing experiments */

 for(i = 0; i < N; i++)
 {
  key = random(); /* get the next key to insert */
  index = key % LENGTH;
  new = old = Table + index;
  not_inserted = 1; /* flag to check when done */

  while(new != 0 && not_inserted)
           /* look for current key, or end of linked list */
  {
   count++; /* increment probe count */

   if(new->key == -1) /* check if Table entry is empty */
   {
    new->key = key;  /* insert new key */
    not_inserted = 0;
   }
   else if(new->key == key) not_inserted = 0;  /* duplicate of key found */
   else
   {
    old = new;
    new = new->pointer; /* advance pointer to next entry */
   }
  }

  if(not_inserted) /* no duplicate found and table entry full */
  {
   count++;

           /* add new key to the end of the LL */
   new = (struct ENTRY *)malloc(sizeof(struct ENTRY));
   new->key = key;
   new->pointer = 0;
   old->pointer = new;
  }
 }

 printf("insert probes : %f\n", count / (float)N);
 return(count);
}


int search(void)
  /* looks up N random keys in the table */
{
 unsigned int  count, i, index, key;
 struct ENTRY  *pointer;

 count = 0;

 for(i = 0; i < N; i++)
 {
  key = random();
  index = key % LENGTH;
  pointer = Table + index;

  while(pointer != 0)
  {
   count++;

   if(pointer->key == key) break;
   pointer = pointer->pointer;
  }
 }

 printf("search probes : %f\n", count / (float)N);
 return(count);
}

void main(void)
{
 unsigned int  count_insert, count_search, i, j;
 float total, time;
 struct ENTRY  *new, *old;
 clock_t start; /* timing variable */

 count_insert = count_search = 0;

printf(" input n = the total number of keys to be inserted \n");
scanf("%d", &N);


 total = 0.0;

 for(i = 0; i < REPEAT; i++)  /* loop to do experiment multiple times */
 {
  for(j = 0; j < LENGTH; j++) /* initialize hash table */
  {
   Table[j].key = -1; /* -1 is an empty key slot */
   Table[j].pointer = 0;
  }
 start = clock(); /* begin timing by setting start to the current time */

  count_insert += insert(); /* counts total probes for insert */
 //  count_search += search(); 
 // search routine not used here

time = ((double)(clock()-start))/((double)CLOCKS_PER_SEC);
    printf("time= %g\n", time);

total += time;

  for(j = 0; j < LENGTH; j++) /* free allocated nodes */
  {
   new = Table[j].pointer;
   while(new != 0)
   {
    old = new;
    new = new->pointer;
    free(old);
   }
  }
 }

 printf("average insert probe : %f\n", count_insert / (float)N / REPEAT);
printf("average time= %g\n", total/ (double) REPEAT);
}