#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <sys/resource.h>

/*
#define TABSIZE 2000000
#define TABSIZELESS1 (TABSIZE - 1)
*/

int TABSIZE=20000000;

int *hash;
int n;

int nextPrime(int x)
{
// Find a prime number >= x
int work,k,remainder,quotient;

if (x%2==1)
  work=x;
else
  work=x+1;

while (1)
{
  for (k=3; ;k+=2)
  {
    remainder=work%k;
    if (remainder==0)
      break;
    quotient=work/k;
    if (quotient<k)
      return work;
  }

  work+=2;
}
}

int generateRandom(minRange,maxRange)
int minRange,maxRange;
{
/* returns value x in range minRange <= x <= maxRange */
return minRange+labs(random()) % (maxRange-minRange+1);
}

float CPUtime()
{
  struct rusage rusage;
  getrusage(RUSAGE_SELF,&rusage);
  return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
    + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

int hashfunction(int key)
{
return (key % TABSIZE);
}

int increment(int key)
{
int work;

work = 1+key % (TABSIZE-1);
return work;
}

void initTable()
{
int i;
n = 0;
for (i=0;i<TABSIZE;i++)
  hash[i] = (-1);
}

int insert (int key, int r[])
{
int i, ii, inc, init, j, jj;

init = hashfunction(key);
inc = increment(key);
for (i=0;i<=TABSIZE;i++)
{
//  printf("trying to add just %d to total of probe lengths\n",i+1);
  for (j=i;j>=0;j--)
  {
    jj = (init + inc * j) % TABSIZE;
    ii = (jj + increment(r[jj]) * (i - j)) % TABSIZE;
//    printf("i=%d j=%d jj=%d ii=%d\n",i,j,jj,ii);
    if (r[ii] == (-1))
    {
      r[ii] = r[jj];
      r[jj] = key;
      n++;
      return i+1;
    }
  }
}
printf("insert failed\n");
return 999999999;
}

void doInserts()
{
int key;
int i, j, k;
int probelengthtotal=0;
float startCPU;

startCPU=CPUtime();

for (k=1;k<=0.99*TABSIZE;k++)
{
//  scanf("%d",&key);
  key=generateRandom(0,100*TABSIZE);
  probelengthtotal+=insert(key, hash);
/*
  printf("hash=%d increment=%d\n",hashfunction(key),increment(key));
  for (i=0;i<TABSIZE;i++)
    printf("%d %d\n",i, hash[i]);
*/
  if (k%200000==0)
    printf("%.3f l.f. probelengthtotal=%d expected=%.3f CPU %.3f\n",
      ((float) k)/TABSIZE,probelengthtotal,
      ((float)probelengthtotal)/n,(CPUtime()-startCPU));
}
printf("%.3f l.f. probelengthtotal=%d expected=%.3f CPU %.3f\n",
      ((float) k)/TABSIZE,probelengthtotal,
      ((float)probelengthtotal)/n,(CPUtime()-startCPU));
}

void doRetrievals()
{
int key;
int i,j,k,wc=0,probes,totalProbes=0;
float startCPU;
int count[31];

for (i=0;i<31;i++)
  count[i]=0;
startCPU=CPUtime();
for (k=1;k<=0.99*TABSIZE;k++)
{
  key=generateRandom(0,100*TABSIZE);
  i=hashfunction(key);
  j=increment(key);
  probes=1;
  while (hash[i]!=key && hash[i]!=(-1))
  {
    probes++;
    i=(i+j)%TABSIZE;
  }
  if (hash[i]==(-1))
  {
    printf("Key missing!\n");
    exit(0);
  }
  if (probes<30)
    count[probes]++;
  else
    count[30]++;
  if (probes>wc)
    wc=probes;
  totalProbes+=probes;
}
printf("Retrievals took %.3f secs\n",CPUtime()-startCPU);
printf("Worst case probes is %d\n",wc);
printf("Total probes %d\n",totalProbes);
printf("Expected probes is %.3f\n",((float)totalProbes)/n);
printf("Probe counts:\n");
for (i=1;i<30;i++)
  printf("Number of keys using %d probes is %d\n",i,count[i]);
printf("Number of keys using >=30 probes is %d\n",count[30]);
}

int main()
{
int seed;

TABSIZE=nextPrime(TABSIZE);
hash=(int*) malloc(TABSIZE*sizeof(int));
if (!hash)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
printf("Enter seed:\n");
scanf("%d",&seed);
initTable();
srandom(seed);
doInserts();
srandom(seed);
doRetrievals();
}