// Perfect hashing in CLRS, 2nd ed, 245-249

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

int *keyInput;
int *keySort,*hTable,hTableA,hTableB;
int hTableP;
long long int hTableAll;
int seed,n;

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 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;
}
}

void buildPerfectHash()
{
int i,j,k,sub,slot,length;
int newSize;
int a,b;
long long int aLL;
int count[15]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

hTableP=0;
for (i=0;i<n;i++)
{
  if (keyInput[i]>hTableP)
    hTableP=keyInput[i];
  hTable[i]=0;
}
hTableP=nextPrime(hTableP+1);
hTableAll=hTableA=1+labs(random())%(hTableP-1);
hTableB=labs(random())%hTableP;

// Counting sort
for (i=0;i<n;i++)
  hTable[((hTableAll*keyInput[i]+hTableB)%hTableP)%n]++;
for (i=1;i<n;i++)
  hTable[i]+=hTable[i-1];
for (i=0;i<n;i++)
  keySort[--hTable[((hTableAll*keyInput[i]+hTableB)%hTableP)%n]]=keyInput[i];

// Count the number of items for each subtable
for (i=0;i<n;i++)
  hTable[i]=0;
for (i=0;i<n;i++)
  hTable[((hTableAll*keySort[i]+hTableB)%hTableP)%n]++;
newSize=n;
for (i=0;i<n;i++)
  if (hTable[i]>0) {
    if (hTable[i]==1)
      newSize+=2;
    else
      newSize+=3+hTable[i]*hTable[i];
    }

hTable=(int*) realloc((void*) hTable,newSize*sizeof(int));
if (!hTable)
{
  printf("realloc failed %d\n",__LINE__);
  exit(0);
}
printf("realloc for %lu more permanent bytes\n",(newSize-n)*sizeof(int));
printf("final structure will use %.3f bytes per key\n",
  ((float) newSize)*sizeof(int)/n);
  

k=0;   //start of next group of keys
sub=n; //start of next subarray
for (i=0;i<n;i++)
  if (hTable[i]==0)
  {
    count[0]++;
    hTable[i]=(-1);
  }
  else if (hTable[i]==1)
  {
    count[1]++;
    hTable[sub]=1;              // size of subarray
    hTable[sub+1]=keySort[k++]; // only 1 key slot in subarray
    hTable[i]=sub;              // points to subarray
    sub+=2;                     // next subarray
  }
  else
  {
    length=hTable[i];
    if (length<14)
      count[length]++;
    else
      count[14]++;
    for (;;)
    {
      aLL=a=1+labs(random())%(hTableP-1);
      b=labs(random())%hTableP;
      for (j=0;j<length*length;j++)
        hTable[sub+3+j]=(-1);
      for (j=k;j<k+length;j++)
      {
        slot=((aLL*keySort[j]+b)%hTableP)%(length*length);
        if (hTable[sub+3+slot]==keySort[j])
          continue;
        if (hTable[sub+3+slot]!=(-1))
          break;
        hTable[sub+3+slot]=keySort[j];
      }
      if (j==k+length)
        break;
    }
    hTable[sub]=length;
    hTable[sub+1]=a;
    hTable[sub+2]=b;
    hTable[i]=sub;
    k+=length;
    sub+=3+length*length;
  }
printf("Subarray statistics:\n");
for (i=0;i<14;i++)
  printf("Number with %d keys is %d\n",i,count[i]);
printf("Number with >=14 keys is %d\n",count[14]);
}

void verifyPerfectHash()
{
int i,j,k,sub,slot,length;
int a,b;
long long int aLL;

for (i=0;i<n;i++)
{
  k=keyInput[i];
  j=((hTableAll*k+hTableB)%hTableP)%n;
  if (hTable[j]==(-1))
  {
    printf("No subarray for key %d\n",__LINE__);
    exit(0);
  }
  sub=hTable[j];
  length=hTable[sub];
  if (length==1)
  {
    if (hTable[sub+1]==k)
      continue;
    if (hTable[sub+1]==(-1))
    {
      printf("Key mapped to empty slot %d\n",__LINE__);
      exit(0);
    }
    printf("Key's slot contains different key %d\n",__LINE__);
    exit(0);
  }
  else
  {
    aLL=a=hTable[sub+1];
    b=hTable[sub+2];
    slot=((aLL*k+b)%hTableP)%(length*length);
    if (hTable[sub+3+slot]==k)
      continue;
    if (hTable[sub+3+slot]==(-1))
    {
      printf("Key mapped to empty slot %d\n",__LINE__);
      exit(0);
    }
    printf("Key's slot contains different key %d\n",__LINE__);
    exit(0);
  }
}
}

int main()
{
int i;
float startTime;

printf("Enter seed and number of keys\n");
scanf("%d %d",&seed,&n);
srandom(seed);
keyInput=(int*) malloc(n*sizeof(int)); // temp
keySort=(int*) malloc(n*sizeof(int));  // temp
hTable=(int*) malloc(n*sizeof(int));   // permanent
if (!keyInput || !keySort || !hTable)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
printf("malloc'ed %lu temporary bytes\n",2*n*sizeof(int));
printf("malloc'ed %lu permanent bytes\n",n*sizeof(int));
for (i=0;i<n;i++)
{
  keyInput[i]=labs(random());
  if (n<=50)
    printf("key %d is %d\n",i,keyInput[i]);
}

startTime=CPUtime();
buildPerfectHash();
printf("Time to build perfect hash structure %.3f\n",
  CPUtime()-startTime);

startTime=CPUtime();
verifyPerfectHash();
printf("Time to retrieve each key once %.3f\n",
  CPUtime()-startTime);

free(hTable);
free(keyInput);
free(keySort);
}