can 64 entry in 64bucket

mhash.c

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

typedef int key_t;
typedef int value_t;

typedef struct mhash {
  uint64_t exists;
  uint64_t origin;
  key_t *keys;
  value_t *values;
  uint16_t *same_hash;
  int n_buckets;
} mhash;

const int same_hash_size = 16;

uint64_t ror(uint64_t base, int sn, int basesize)
{
  if (sn < 0) sn += basesize;
  uint64_t snbit = (1ll << (sn + 1)) - 1;

  return (((base & snbit) << (basesize - sn)) | (base >> sn))
    & ((1ll << basesize)) - 1;
}

mhash *mh_init(int size) {
  mhash *h = malloc(sizeof(mhash));
  h->n_buckets = size;
  h->exists = 0;
  h->origin = 0;

  h->keys = calloc(size, sizeof(key_t));
  h->values = calloc(size, sizeof(key_t));
  h->same_hash = calloc(size, sizeof(uint16_t));

  return h;
}

#define hash_func(hash) (unsigned int)((key)^((key)<<2)^((key)>>2))
int mh_put(mhash *h, key_t key) {
  int hv = hash_func(key) % h->n_buckets;
  uint64_t hv_bitmap = (1ll << hv);

  if ((h->exists & hv_bitmap) == 0) {
    /* no confilct hash value and entry is fresh  */
    h->exists |= hv_bitmap;
    h->origin |= hv_bitmap;
    h->keys[hv] = key;
    h->same_hash[hv] = 1;
    h->exists |= hv_bitmap;

    return hv;
  }

  if (h->same_hash[hv] & 1) {
    /* useing entry for same hash value */
    uint64_t alorigin = ror(h->exists, hv - same_hash_size, h->n_buckets);
    uint64_t alexits = ror(h->exists, hv, h->n_buckets);
    int empoff = __builtin_ctzll(alexits + 1);
    if (0 && __builtin_popcount(alorigin & ((1 << same_hash_size) - 1)) > 1) {
      empoff = 31 - __builtin_clz((~(uint32_t)alexits) & ((1 << same_hash_size) - 1));
      printf("%d %x\n", empoff, alexits & 0xffff);
    }
    else {
      empoff = __builtin_ctzll(alexits + 1);
    }
    if (empoff > 0 && empoff < same_hash_size) {
      int newent = (empoff + hv) % h->n_buckets;

      h->same_hash[hv] |= (1 << empoff);
      h->exists |= (1ll << newent);
      h->same_hash[newent] = (empoff << 1);
      h->keys[newent] = key;

      return newent;
    }

    /* Oh! fill my entry. Must still from other entry */
    abort();
  }

  /* using entry for other hash value. */
  {
    int eoff = h->same_hash[hv] >> 1;
    int hv2 = (hv - eoff) % h->n_buckets;
    if (hv2 < 0) {
      hv2 += h->n_buckets;
    }
    uint64_t alexits = ror(h->exists, hv2, h->n_buckets);
    int empoff = __builtin_ctzll(alexits + 1);
    if (empoff < same_hash_size) {
      int newent =  (empoff + hv2) % h->n_buckets;
      uint64_t hv_bitmap = 1 << newent;

      h->same_hash[hv2] ^= (1 << eoff); /* Clear old entry */
      h->same_hash[hv2] |= (1 << empoff); /* Set new entry */ 
      h->keys[newent] = h->keys[hv];
      h->values[newent] = h->values[hv];
      h->same_hash[newent] = empoff << 1;
      h->exists |= hv_bitmap;
      h->origin |= hv_bitmap;
     
      h->same_hash[hv] = 1;
      h->keys[hv] = key;
      
      return hv;
    }

    abort();
  }

  return h->n_buckets;
}

int mh_get(mhash *h, key_t key) {
  int hv = hash_func(key) % h->n_buckets;
  uint16_t hbit = h->same_hash[hv];

  if (hbit & 1) {
    for (int i = 0; i >= 0 && i < 16;i = __builtin_ctz(hbit)) {
      int ent =  (i + hv) % h->n_buckets;
      if (h->keys[ent] == key) {
	return ent;
      }
      hbit ^= (1 << i);
    }
  }

  return -1;
}

main(){
  mhash *h = mh_init(64);

  for (int i = 0; i < 64; i++) {
    int ent = mh_put(h, i);
    printf("%d %d \n", i, ent);
    h->values[ent] = i + 1;
  }
  printf("fin\n");

  for (int i = 0; i < 64; i++) {
    int ent = mh_get(h, i);
    printf("%d %d \n", h->values[ent], ent);
  }
}