termhash.c

#include "whistlepig.h"

static const int HASH_PRIME_SIZE = 32;

static const uint32_t prime_list[] = {
  0ul,          3ul,          11ul,         23ul,         53ul,
  97ul,         193ul,        389ul,        769ul,        1543ul,
  3079ul,       6151ul,       12289ul,      24593ul,      49157ul,
  98317ul,      196613ul,     393241ul,     786433ul,     1572869ul,
  3145739ul,    6291469ul,    12582917ul,   25165843ul,   50331653ul,
  100663319ul,  201326611ul,  402653189ul,  805306457ul,  1610612741ul,
  3221225473ul, 4294967291ul
};

#define isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
#define isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
#define iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
#define set_isdel_false(flag, i) (flag[i>>4]&=~(uint32_t)(1ul<<((i&0xfU)<<1)))
#define set_isempty_false(flag, i) (flag[i>>4]&=~(uint32_t)(2ul<<((i&0xfU)<<1)))
#define set_isboth_false(flag, i) (flag[i>>4]&=~(uint32_t)(3ul<<((i&0xfU)<<1)))
#define set_isdel_true(flag, i) (flag[i>>4]|=(uint32_t)(1ul<<((i&0xfU)<<1)))

static const double HASH_UPPER = 0.77;

static uint32_t hash_term(term t) {
  return t.word_s ^ t.field_s;
}

static int term_equals(term a, term b) {
  return a.word_s == b.word_s && a.field_s == b.field_s;
}

void termhash_init(termhash* h) {
  h->n_buckets_idx = 1;
  h->n_buckets = prime_list[h->n_buckets_idx];
  h->upper_bound = (uint32_t)(h->n_buckets * HASH_UPPER + 0.5);
  h->size = h->n_occupied = 0;
  memset(TERMHASH_FLAGS(h), 0xaa, ((h->n_buckets>>4) + 1) * sizeof(uint32_t));
}

#define OFFSET(a, b) (long)((uint8_t*)a - (uint8_t*)b)
// set flags, keys and vals to correct locations based on h->n_buckets
/*
static void termhash_dump(termhash* h) {
  for(uint32_t i = 0; i < h->n_buckets; i++) {
    if(isempty(h->flags, i)) printf("%u:\n", i);
    else if(isdel(h->flags, i)) printf("%u: [deleted]", i);
    else {
      term t = h->keys[i];
      printf("%u: (%u,%u)\n", i, t.field_s, t.word_s);
    }
  }
}
*/

/*
static void kh_destroy_##name(kh_##name##_t *h) {
  if (h) {
    free(h->keys); free(h->flags);
    free(h->vals);
    free(h);
  }
}

static void kh_clear_##name(kh_##name##_t *h) {
  if (h && h->flags) {
    memset(h->flags, 0xaa, ((h->n_buckets>>4) + 1) * sizeof(uint32_t));
    h->size = h->n_occupied = 0;
  }
}
*/

uint32_t termhash_get(termhash *h, term key) {
  uint32_t* flags = TERMHASH_FLAGS(h);
  term* keys = TERMHASH_KEYS(h);

  if(h->n_buckets) {
    uint32_t inc, k, i, last;
    k = hash_term(key); i = k % h->n_buckets;
    inc = 1 + k % (h->n_buckets - 1); last = i;
    while (!isempty(flags, i) && (isdel(flags, i) || !term_equals(keys[i], key))) {
      if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets;
      else i += inc;
      if (i == last) return h->n_buckets;
    }
    return iseither(flags, i)? h->n_buckets : i;
  }
  else return 0;
}

wp_error* termhash_bump_size(termhash *h) {
  DEBUG("bumping size for term hash at %p with size %u and boundary %p (+%ld)", h, termhash_size(h), h->boundary, (long)((uint8_t*)h->boundary - (uint8_t*)h));
  DEBUG("flags are at %p (+%ld)", TERMHASH_FLAGS(h), OFFSET(TERMHASH_FLAGS(h), h->boundary));
  DEBUG(" keys are at %p (+%ld)", TERMHASH_KEYS(h), OFFSET(TERMHASH_KEYS(h), h->boundary));
  DEBUG(" vals are at %p (+%ld)", TERMHASH_VALS(h), OFFSET(TERMHASH_VALS(h), h->boundary));

  if(h->n_buckets_idx >= (HASH_PRIME_SIZE - 1)) RAISE_ERROR("termhash can't be this big");

  h->n_buckets_idx++;
  uint32_t new_n_buckets = prime_list[h->n_buckets_idx];

  // first make a backup of the old flags in a separate memory region
  size_t flagbaksize = ((h->n_buckets >> 4) + 1) * sizeof(uint32_t);
  uint32_t* flagbaks = malloc(flagbaksize);
  memcpy(flagbaks, TERMHASH_FLAGS(h), flagbaksize);

  // get pointers to the old locations
  term* oldkeys = TERMHASH_KEYS(h);
  posting_list_header* oldvals = TERMHASH_VALS(h);

  // set pointers to the new locations
  uint32_t* newflags = (uint32_t*)h->boundary;
  term* newkeys = (term*)(newflags + ((new_n_buckets >> 4) + 1));
  posting_list_header* newvals = (posting_list_header*)(newkeys + new_n_buckets);

  // move the vals and keys
  memmove(newvals, oldvals, h->n_buckets * sizeof(posting_list_header));
  memmove(newkeys, oldkeys, h->n_buckets * sizeof(term));

  // clear the new flags
  memset(newflags, 0xaa, ((new_n_buckets>>4) + 1) * sizeof(uint32_t));

  // do the complicated stuff from khash.h
  for (unsigned int j = 0; j != h->n_buckets; ++j) {
    if (iseither(flagbaks, j) == 0) {
      term key = newkeys[j];
      posting_list_header val = newvals[j];
      set_isdel_true(flagbaks, j);
      while (1) {
        uint32_t inc, k, i;
        k = hash_term(key);
        i = k % new_n_buckets;
        inc = 1 + k % (new_n_buckets - 1);
        while (!isempty(newflags, i)) {
          if (i + inc >= new_n_buckets) i = i + inc - new_n_buckets;
          else i += inc;
        }
        set_isempty_false(newflags, i);
        if (i < h->n_buckets && iseither(flagbaks, i) == 0) {
          { term tmp = newkeys[i]; newkeys[i] = key; key = tmp; }
          { posting_list_header tmp = newvals[i]; newvals[i] = val; val = tmp; }
          set_isdel_true(flagbaks, i);
        } else {
          newkeys[i] = key;
          newvals[i] = val;
          break;
        }
      }
    }
  }

  free(flagbaks);
  h->n_buckets = new_n_buckets;
  h->n_occupied = h->size;
  h->upper_bound = (uint32_t)(h->n_buckets * HASH_UPPER + 0.5);

  DEBUG("after bump, term hash at %p has size %u and boundary %p (+%ld)", h, termhash_size(h), h->boundary, (long)((uint8_t*)h->boundary - (uint8_t*)h));
  DEBUG("flags are at %p (+%ld)", TERMHASH_FLAGS(h), OFFSET(TERMHASH_FLAGS(h), h->boundary));
  DEBUG(" keys are at %p (+%ld)", TERMHASH_KEYS(h), OFFSET(TERMHASH_KEYS(h), h->boundary));
  DEBUG(" vals are at %p (+%ld)", TERMHASH_VALS(h), OFFSET(TERMHASH_VALS(h), h->boundary));

#ifdef DEBUGOUTPUT
//DEBUG("and now i look like this:");
//termhash_dump(h);
#endif

  return NO_ERROR;
}

uint32_t termhash_put(termhash *h, term key, int *ret) {
  uint32_t x;
  uint32_t* flags = TERMHASH_FLAGS(h);
  term* keys = TERMHASH_KEYS(h);

  {
#ifdef DEBUGOUTPUT
int num_loops = 0;
#endif
    uint32_t inc, k, i, site, last;
    x = site = h->n_buckets; k = hash_term(key); i = k % h->n_buckets;
    DEBUG("initial hash is %u", k);
    if (isempty(flags, i)) x = i;
    else {
      inc = 1 + k % (h->n_buckets - 1); last = i;
      while (!isempty(flags, i) && (isdel(flags, i) || !term_equals(keys[i], key))) {
#ifdef DEBUGOUTPUT
num_loops++;
#endif
        if (isdel(flags, i)) site = i;
        if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets;
        else i += inc;
        if (i == last) { x = site; break; }
      }
      if ((x == h->n_buckets) && (i == last)) { // out of space
        if(!term_equals(keys[i], key)) {
          *ret = -1;
          return x;
        }
      }
      if (x == h->n_buckets) { // didn't find it on the first try
        if (isempty(flags, i) && site != h->n_buckets) x = site;
        else x = i;
      }
    }
    DEBUG("looped %u times to put", num_loops);
    //DEBUG("x is %u, site is %u, n_buckets is %u", x, site, h->n_buckets);
  }
  if (isempty(flags, x)) {
    keys[x] = key;
    set_isboth_false(flags, x);
    ++h->size; ++h->n_occupied;
    *ret = 1;
  } else if (isdel(flags, x)) {
    keys[x] = key;
    set_isboth_false(flags, x);
    ++h->size;
    *ret = 2;
  }
  else *ret = 0;

#ifdef DEBUGOUTPUT
//DEBUG("after put:");
//termhash_dump(h);
#endif

  return x;
}

void termhash_del(termhash *h, uint32_t x) {
  uint32_t* flags = TERMHASH_FLAGS(h);
  if (x != h->n_buckets && !iseither(flags, x)) {
    set_isdel_true(flags, x);
    --h->size;
  }
}

posting_list_header* termhash_get_val(termhash* h, term t) {
  posting_list_header* vals = TERMHASH_VALS(h);
  uint32_t idx = termhash_get(h, t);
  if(idx == h->n_buckets) return NULL;
  return &vals[idx];
}

wp_error* termhash_put_val(termhash* h, term t, posting_list_header* val) {
  int status;
  posting_list_header* vals = TERMHASH_VALS(h);
  uint32_t loc = termhash_put(h, t, &status);
  DEBUG("put(%u,%u) has status %d and loc %u (error val is %u)", t.field_s, t.word_s, status, loc, h->n_buckets);
  if(status == -1) RAISE_ERROR("out of space in hash");
  memcpy(&vals[loc], val, sizeof(posting_list_header));
  return NO_ERROR;
}

int termhash_needs_bump(termhash* h) {
  return (h->n_occupied >= h->upper_bound);
}

// returns the total size in bytes
//   memory layout: termhash struct, then:
//   ((n_buckets >> 4) + 1) uint32_t's for the flags
//   n_buckets terms for the keys
//   n_buckets posting_list_header for the vals (offsets into postings lists)
static uint32_t size(uint32_t n_buckets) {
  uint32_t size = (uint32_t)sizeof(termhash) +
    (((n_buckets >> 4) + 1) * (uint32_t)sizeof(uint32_t)) +
    (n_buckets * (uint32_t)sizeof(term)) +
    (n_buckets * (uint32_t)sizeof(posting_list_header));

  DEBUG("size of a termhash with %u buckets is %lu + %lu + %lu + %lu = %u",
    n_buckets,
    (long)sizeof(termhash),
    (long)(((n_buckets >> 4) + 1) * sizeof(uint32_t)),
    (long)(n_buckets * sizeof(term)),
    (long)(n_buckets * sizeof(posting_list_header)),
    size);

  return size;
}

uint32_t termhash_size(termhash* h) {
  return size(h->n_buckets);
}

uint32_t termhash_initial_size() {
  return size(prime_list[INITIAL_N_BUCKETS_IDX]);
}

uint32_t termhash_next_size(termhash* h) {
  int next_idx = (h->n_buckets_idx < (HASH_PRIME_SIZE - 1)) ? h->n_buckets_idx + 1 : h->n_buckets_idx;
  return size(prime_list[next_idx]);
}