// Gonnet & Munro's Binary Tree Rehashing
// based on Pascal code in Gonnet & Baeza-Yates book.
// Iterative-deepening for search, but only costs a constant factor.
// BPW, July 2011
// Cleaned up and added conditional compilation for Brent's method, May 2012

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

//#define BRENT

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(int minRange,int 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 h1(int key)
// Computes initial slot for hash
{
return (key % TABSIZE);
}

int h2(int key)
// Computes offset for rest of probe sequence
{
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 probelengthtotal=0;

int maxkeysmoved=0,keysmoved;

int searchMoveBrent(int init,int inc,int level, int r[])
// Attempt to move key at r[init] ahead by level probes,
// where inc is its offset.
// level may be 0, since a rehashed -1 does not have to move.
// Brent's version - may move only one previous key!!!!!
{
int i,inc1,j,k;

// Find new empty slot for key at r[init]
i=(init+inc*level)%TABSIZE;
if (r[i]==(-1))
  return i;  // Successful search
return -1;   // No place to move key
}

int searchMove(int init,int inc,int level, int r[])
// Attempt to move key at r[init] ahead by level probes,
// where inc is its offset.
// level may be 0, since a rehashed -1 does not have to move.
{
int i,inc1,j,k;

// Find new empty slot for key at r[init]
i=(init+inc*level)%TABSIZE;
if (r[i]==(-1))
  return i;  // Successful search

// Besides moving key at r[init], also move key from new slot for r[init].
// On each iteration of this loop, the number of probes for r[init] decreases.
for (j=level-1;j>=0;j--)
{
  // Determine possible victim
  i=(init+inc*j)%TABSIZE;
  // Determine offset for the victim
  inc1=h2(r[i]);
  // Can victim move ahead level-j-1 probes?
#ifdef BRENT
#warning "using Brent's simplified rehash instead of Gonnet's general rehash.
  k=searchMoveBrent((i+inc1)%TABSIZE,inc1,level-j-1,r);  // No recursion!
#else
  k=searchMove((i+inc1)%TABSIZE,inc1,level-j-1,r);  // Recursion!
#endif
  if (k>(-1))
  { // A hole was found (or created), move forward in probe sequence
    keysmoved++;
    r[k]=r[i];
    return i;
  }
}

return -1; // Could not find hole
}

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

keysmoved=0;
init = h1(key);
inc = h2(key);
i=0;    // Number of probes added on to probe sequences for all keys.
j=(-1); // The slot where key will be placed.
while (i<=n && j<0 && n<TABSIZE)
{
  j=searchMove(init,inc,i,r);
  i++;
}
if (j>(-1))
{ // A hole was found (or created), insert key
  r[j]=key;
  probelengthtotal+=i;
  n++;
}
else
{
  printf("table is full\n");
  exit(0);
}
if (keysmoved>maxkeysmoved)
{
  maxkeysmoved=keysmoved;
  printf("maxkeysmoved is now %d\n",maxkeysmoved);
}
}

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

startCPU=CPUtime();

for (k=1;k<=0.99*TABSIZE;k++)
{
//  scanf("%d",&key);
  key=generateRandom(0,100*TABSIZE);

/*
i=h1(key);
j=h2(key);
while (hash[i]!=key && hash[i]!=(-1))
  i=(i+j)%TABSIZE;

if (hash[i]!=(-1))
{
  printf("Duplicate key! k=%d key=%d\n",k,key);
  //exit(0);
}
*/

  insert(key, hash);
/*
  printf("hash=%d h2=%d\n",h1(key),h2(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=h1(key);
  j=h2(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);
printf("TABSIZE is %d\n",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();
}