//-----------------------------------------------------------------------------
// HashTest.c
// Demonstrates comutation of hash codes, and probe sequences.
//
//      compile:  gcc -o HashTest HashTest.c
//
//-----------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>


typedef char* keyType;
typedef uint64_t codeType;


// print_binary_64()
// Prints a hash code as a bit string
void print_binary_64(codeType n) {
    for (int i = 63; i >= 0; i--) {
        printf("%d", (int)((n >> i) & 1));
        if (i % 8 == 0 && i != 0) printf(" ");
    }
    printf("\n");
}

// hash()
// Returns the hash code for key k.
codeType hash(keyType k) { 
   codeType result = 0x2096DB9D4D43C94E; // binary: 0010000010010110110110111001110101001101010000111100100101001110
   codeType nextChar = *k;               // get first char and convert to codeType
   while(nextChar) {                     // while not at end of k
      result ^= nextChar;                //    result = result (exor) nextChar   
      result = (result<<5)|(result>>59); //    left rotate result by 5 bits
      nextChar = *(++k);                 //    get next char and convert to codeType
   }
   return result;
}

// probe()
// Returns the ith term in the probe sequence for code. This function is denoted h(k,i),
// and given in the Dictionary handout, second example in the hash table section.
size_t probe(codeType code, size_t arr_size, size_t i){
   codeType h1 = code & (arr_size-1);              // code % arr_size
   codeType h2 = 2*(code & (arr_size/2 - 1)) + 1;  // 2*(code % arr_size/2) + 1
   return (h1 + i*h2) & (arr_size-1);              // (h1 + i*h2) % arr_size
}

int main(void){
   
   keyType A[] = {"one","two","three","four"};
   int i, j, slot, n=4;
   int tableSize = 8;
   codeType code;

   printf("\n");
   printf("key   : code                 : probe sequence\n");
   printf("-----------------------------------------------------\n");
   for( i=0; i<n; i++ ){
      code = hash(A[i]);
      printf("%-5s : %-20lu : ", A[i], code);
      for( j=0; j<tableSize; j++ ){
         slot = probe(code, tableSize, j);
         printf("%d%s", slot, (j<tableSize-1) ? ", " : "");
      }
      printf("\n");
   }
   printf("\n");

   return EXIT_SUCCESS;
}