Could you please review the code and tell me if there are any problems? You can find the code at github. Thank you very much in advantage.

Could you please review the code and tell me if there are any problems? You can find the code at GitHub.

##Code

The code consists of a Makefile, a source file file ht.c and a header file ht.h. The file main.c is a simple test program that reports the amount of entries moved on average to fill in entries into a hashtable at least twice the size of the entries.

###Makefile

OUT=main
OBJ=ht.o main.o

$(OUT): $(OBJ)

.PHONY: clean

clean:
    $(RM) $(OBJ) $(OUT)

###ht.c

/* hash table */

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

#include "ht.h"

struct ht {
    int bits;
    uint32_t randoms[256];
    ht_value_t table[];
};

/* state for xorshift rng */
static uint32_t xstate = 0;

#define BITMASK(bits) ((bits) == 32 ? 0xffffffff : (1<<(bits))-1)
#define MODINC(bits,index) (((index)+1) & BITMASK(bits))

static void init_xorshift(void) {
    if (xstate == 0) xstate = time(NULL);
}

static uint32_t xorshift(void) {
  xstate ^= xstate << 13;
  xstate ^= xstate >> 17;
  xstate ^= xstate << 5;
  return xstate;
}

static uint32_t hash(ht_t *ht,ht_key_t key) {
    union { ht_key_t key; uint8_t bytes[8]; } ukey;
    int i;
    uint32_t accum = 0;

    ukey.key = key;
    for (i=0;i<8;i++) accum ^= ht->randoms[ukey.bytes[i]];

    return accum;
}

/* tweakable based on actual way to retrieve key */
static ht_key_t get_key(ht_value_t val) {
    return *val;
}

ht_t *ht_new(int bits) {
    ht_t *ht;
    int i,bitmask;

    if (bits < 0 || bits >= 32) return NULL;

    ht = malloc(sizeof*ht + (1<<bits)*sizeof*ht->table);

    ht->bits = bits;

    init_xorshift();

    /* initiate hash function */
    bitmask = BITMASK(bits);
    for (i=255;i>=0;i--) ht->randoms[i] = xorshift()&bitmask;

    memset(ht->table,0,1<<bits);

    return ht;
}

void ht_free(ht_t *ht) {
    free(ht);
}

int ht_put(ht_t *ht,ht_key_t key,ht_value_t value) {
    uint32_t index = hash(ht,key);
    ht_value_t tmp;
    int iters = 0;

    while (ht->table[index] != NULL && get_key(ht->table[index]) != key) {
        tmp = ht->table[index];
        ht->table[index] = value;
        index = MODINC(ht->bits,index);
        value = tmp;
        iters++;
    }

    ht->table[index] = value;

    return iters;
}

int ht_del(ht_t *ht,ht_key_t key) {
    uint32_t hkey = hash(ht,key), index, tindex;
    ht_key_t ckey;
    int iters = 0;

    for (index = hkey;;index = MODINC(ht->bits,index)) {
        if (ht->table[index] == NULL) return -1;
        ckey = get_key(ht->table[index]);
        if (hash(ht,ckey) != hkey) return -1;
        if (ckey == key) break;
    }

    ht->table[index] = NULL;

    while(ht->table[index]!=NULL&&hash(ht,get_key(ht->table[index]))==hkey){
        tindex = index;
        index = MODINC(ht->bits,index);
        ht->table[tindex] = ht->table[index];
        ht->table[index] = NULL;
        iters++;
    }

    return iters;
}

ht_value_t ht_get(ht_t *ht,ht_key_t key) {
    uint32_t hkey = hash(ht,key), index = hkey, ckey;

    while (ht->table[index] != NULL
      && hash(ht,ckey = get_key(ht->table[index])) == hkey) {
        if (ckey == key) return ht->table[index];
        index = MODINC(ht->bits,index);
    }

    return NULL;
}

###ht.h

/* hash table */

#ifndef HT_H
#define HT_H

typedef struct ht ht_t;
typedef uint64_t ht_key_t;
typedef ht_key_t *ht_value_t;

ht_t *ht_new(int bits);
/* ht_put and ht_del return number of items moved or -1 if key
 * already exists (ht_put) / not found (ht_get).
 * ht_value_t must point to the same key we used at insertion */
int ht_put(ht_t*,ht_key_t,ht_value_t);
int ht_del(ht_t*,ht_key_t);
ht_value_t ht_get(ht_t*,ht_key_t);
void ht_free(ht_t*);

#endif /* HT_H */

###main.c

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

#include "ht.h"

int main(int argc,char *argv[]) {
    int count, i, bits=0;
    int misses = 0;
    ht_key_t *values;

    srandom(time(NULL));

    if (argc != 2 || sscanf(argv[1],"%d",&count) != 1) return EXIT_FAILURE;

    for (i=count;i;bits++)i>>=1;
    ht_t *ht = ht_new(bits);

    values = malloc(count*sizeof*values);

    for (i=count;i>0;i--) {
        values[i] = random();
        misses += ht_put(ht,values[i],values+i);
    }

    printf("%.2f\n",misses/(float)count);
    return EXIT_SUCCESS;
}