stdhash.c

spines-ns

  }
  return it;
}

inline stdhash_it *stdhash_it_prev(stdhash_it *it) {
  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_HASH_INITED(it->hash));
  STD_BOUNDS_CHECK(IS_LEGAL_IT(it) && it->node_pos != it->hash->begin);
  it->node_pos = prev(it->hash, it->node_pos);
  return it;
}

inline stdhash_it *stdhash_it_retreat(stdhash_it *it, size_t num_retreat) {
  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_HASH_INITED(it->hash));
  STD_BOUNDS_CHECK(IS_LEGAL_IT(it));
  while (num_retreat--) {
    STD_BOUNDS_CHECK(it->node_pos != it->hash->begin);
    it->node_pos = prev(it->hash, it->node_pos);
  }
  return it;
}

inline stdhash_it *stdhash_it_keyed_next(stdhash_it *it) {
  stdhash_node **curr, **end;
  size_t hash_val, offset;

  STD_CONSTRUCT_CHECK(IS_IT_INITED(it) && IS_HASH_INITED(it->hash));
  STD_BOUNDS_CHECK(IS_VALID_IT(it));

  hash((*it->node_pos)->exphcode, it->hash->a, it->hash->b, 
       it->hash->cap_min1, &hash_val, &offset);

  end = it->hash->table_end;
  /* calculate next probe point for that key */
  if ((curr = it->node_pos + offset) >= end)
    curr = it->hash->table + (curr - end);

  while (1) {
    /* no more pairs with same key, return end */
    if (POS_EMPTY(curr)) {
      it->node_pos = end;
      break;
    } 
    /* if POS_INACTIVE(curr) then the exphcode cannot == the iterator's exphcode! */
    if ((*curr)->exphcode == (*it->node_pos)->exphcode &&
	it->hash->equals(NKEY(*curr), NKEY(*it->node_pos))) {
      it->node_pos = curr;
      break;
    }
    /* go to next probe point */
    if ((curr += offset) >= end)
      curr = it->hash->table + (curr - end);
  }
  return it;
}

static inline int stdhash_pconstruct(stdhash *h, size_t sizeof_key, size_t sizeof_val, 
				     stdequals_fcn key_equals, stdhcode_fcn key_hashcode) {
  STD_CONSTRUCT_CHECK(!IS_HASH_INITED(h));

  if (sizeof_key == 0 || key_equals == 0 || key_hashcode == 0)
    return STD_ERROR(STD_ILLEGAL_PARAM);

  h->table       = 0;
  h->table_end   = 0;
  h->begin       = 0;

  h->ksize       = sizeof_key;
  h->vsize       = sizeof_val;
  h->size        = 0;
  h->cap_min1    = (size_t) -1;
  h->high_thresh = 0;
  h->low_thresh  = 0;
  h->num_nodes   = 0;

  h->equals      = key_equals;
  h->hashcode    = key_hashcode;

  INIT_HASH(h);

  return STD_SUCCESS;
}

/******************** stdhash interface ****************************************/

inline int stdhash_construct(stdhash *h, size_t sizeof_key, size_t sizeof_val, 
			     stdequals_fcn key_equals, stdhcode_fcn key_hashcode) {
  int ret = stdhash_pconstruct(h, sizeof_key, sizeof_val, key_equals, key_hashcode);

  if (ret)
    return ret;

  /* randomly seed: uses time() to generate dynamic random */
  stdrand_seed(h->ai, 139812051UL);
  stdrand_seed(h->bi, 89751055UL);

  return STD_SUCCESS;
}

inline int stdhash_construct2(stdhash *h, size_t sizeof_key, size_t sizeof_val, 
			      stdequals_fcn key_equals, stdhcode_fcn key_hashcode, size_t dseed) {
  int ret = stdhash_pconstruct(h, sizeof_key, sizeof_val, key_equals, key_hashcode);

  if (ret)
    return ret;

  /* deterministically seed */
  stdrand_dseed(h->ai, dseed);
  stdrand_dseed(h->bi, ~dseed * 33);

  return STD_SUCCESS;
}

inline int stdhash_copy_construct(stdhash *dst, const stdhash *src) {
  stdhash_node **dst_curr;
  size_t cap;

  STD_CONSTRUCT_CHECK(!IS_HASH_INITED(dst) && IS_HASH_INITED(src));

  cap = src->cap_min1 + 1;

  dst->ksize       = src->ksize;
  dst->vsize       = src->vsize;
  dst->size        = src->size;
  dst->cap_min1    = src->cap_min1;
  dst->high_thresh = src->high_thresh;
  dst->low_thresh  = src->low_thresh;
  dst->num_nodes   = src->num_nodes;

  dst->a = src->a;
  dst->b = src->b;
  memcpy(dst->ai, src->ai, sizeof(src->ai));
  memcpy(dst->bi, src->bi, sizeof(src->bi));

  dst->equals   = src->equals;
  dst->hashcode = src->hashcode;

  if (cap != 0) {
    stdhash_node **src_curr = src->table;
    stdhash_node **src_end  = src->table_end;

    if (!(dst->table = (stdhash_node**) calloc(cap, sizeof(stdhash_node*))))
      return STD_ERROR(STD_MEM_FAILURE);

    dst->table_end = dst->table + cap;
    dst->begin     = dst->table + (src->begin - src->table);

    /* make an exact duplicate of the src's hash table */
    for (dst_curr = dst->table; src_curr != src_end; ++src_curr, ++dst_curr)
      if (!POS_EMPTY(src_curr))
	if (!(*dst_curr = make_node(dst, (*src_curr)->exphcode, 
				    (*src_curr)->kv.key, (*src_curr)->kv.value)))
	  goto stdhash_copy_construct_fail;
  } else {
    dst->table     = 0;
    dst->table_end = 0;
    dst->begin     = 0;
  }
  INIT_HASH(dst);
  return STD_SUCCESS;

 stdhash_copy_construct_fail:
  for (; --dst_curr >= dst->table;)
    if (!POS_EMPTY(dst_curr))
      free_node(*dst_curr);

  free(dst->table);
  return STD_ERROR(STD_MEM_FAILURE);
}

inline void stdhash_destruct(stdhash *h) {
  stdhash_node **curr = h->table, **end = h->table_end;

  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));

  for (; curr != end; ++curr)
    if (!POS_EMPTY(curr))
      free_node(*curr);

  if (h->table)
    free(h->table);

  UNINIT_HASH(h);
}

/* Iterator Interface */
inline stdhash_it *stdhash_begin(const stdhash *h, stdhash_it *it) {
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  it->hash     = (stdhash*) h;
  it->node_pos = (stdhash_node**) h->begin;
  INIT_IT(it);
  return it;
}

inline stdhash_it *stdhash_last(const stdhash *h, stdhash_it *it) {
  return stdhash_it_prev(stdhash_end(h, it));
}

inline stdhash_it *stdhash_end(const stdhash *h, stdhash_it *it) {
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  it->hash     = (stdhash*) h;
  it->node_pos = (stdhash_node**) h->table_end;
  INIT_IT(it);
  return it;
}

inline stdhash_it *stdhash_get(const stdhash *h, stdhash_it *it, size_t elem_num) {
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  STD_BOUNDS_CHECK(elem_num <= stdhash_size(h));
  if (elem_num < stdhash_size(h) >> 1)
    return stdhash_it_advance(stdhash_begin(h, it), elem_num);
  else
    return stdhash_it_retreat(stdhash_end(h, it), stdhash_size(h) - elem_num);
}

/* Size and Capacity Information */
inline size_t stdhash_size(const stdhash *h) { 
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  return h->size; 
}

inline stdbool stdhash_empty(const stdhash *h) { 
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  return h->size == 0; 
}

inline size_t stdhash_max_size(const stdhash *h) { 
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  return STD_SIZE_T_MAX >> 2;
}

inline size_t stdhash_key_size(const stdhash *h) { 
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  return h->ksize; 
}

inline size_t stdhash_val_size(const stdhash *h) { 
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  return h->vsize; 
}

inline size_t stdhash_kvp_size(const stdhash *h) {
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));
  return sizeof(stdkvp);
}

/* Size and Capacity Operations */
inline int stdhash_clear(stdhash *h) {
  stdhash_destruct(h);
  h->table       = 0;
  h->table_end   = 0;
  h->begin       = 0;
  h->size        = 0;
  h->cap_min1    = (size_t) -1;
  h->high_thresh = 0;
  h->low_thresh  = 0;
  h->num_nodes   = 0;
  update_params(h);

  INIT_HASH(h);

  return STD_SUCCESS;
}

/* adjusts table to be able to accomadate num_pairs pairs wo/ rehashes */
inline int stdhash_reserve(stdhash *h, size_t num_pairs) {
  size_t new_cap, new_high, new_low;

  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));

  if (get_cap_and_threshs(num_pairs, &new_cap, &new_high, &new_low) != 0)
    return STD_ERROR(STD_MEM_FAILURE);
  else if (h->cap_min1 + 1 >= new_cap)
    return STD_SUCCESS;
  else if (rehash(h, num_pairs) != STD_SUCCESS)
    return STD_ERROR(STD_MEM_FAILURE);

  return STD_SUCCESS;
}

/* adjusts table to be able to fit current size well */
inline int stdhash_rehash(stdhash *h) {
  return stdhash_reserve(h, stdhash_size(h));
}

/* Hash Operations: O(1) expected, O(n) worst case */
inline stdhash_it *stdhash_find(const stdhash *h, stdhash_it *it, const void *key) {
  size_t hash_val, offset, exphcode = exp_hcode(h->hashcode(key));
  stdhash_node **curr, **end = h->table_end;

  if (stdhash_empty(h)) /* takes care of zero capacity searches (they don't work) */
    return stdhash_end(h, it);

  /* compute hash value and hash offset */
  hash(exphcode, h->a, h->b, h->cap_min1, &hash_val, &offset);
  curr = h->table + hash_val; /* initial probe point */

  while (1) {
    if (POS_EMPTY(curr))      /* empty, so key is not in table */
      return stdhash_end(h, it);

    if ((*curr)->exphcode == exphcode && h->equals(key, NKEY(*curr))) { /* found it */
      it->hash     = (stdhash*) h;
      it->node_pos = (stdhash_node**) curr;
      INIT_IT(it);
      return it;
    }
    if ((curr += offset) >= end) /* go to next probe point */
      curr = h->table + (curr - end);
  }
}

/* can cause side effects when failing: rehash */
inline stdhash_it *stdhash_insert(stdhash *h, stdhash_it *it, const void *key, const void *val) {
  size_t hash_val, offset, exphcode;
  stdhash_node **curr, **end;

  STD_CONSTRUCT_CHECK(IS_HASH_INITED(h));

  /* is a rehash/growth required? return null on failure */
  if (h->num_nodes >= h->high_thresh && rehash(h, stdhash_size(h) + 1) != STD_SUCCESS)
    return (stdhash_it*) STD_ERROR(STD_MEM_FAILURE2);

  exphcode = exp_hcode(h->hashcode(key));
  hash(exphcode, h->a, h->b, h->cap_min1, &hash_val, &offset);
  curr = h->table + hash_val;
  end  = h->table_end;

  while (!(POS_EMPTY(curr) || POS_INACTIVE(curr)))
    if ((curr += offset) >= end)
      curr = h->table + (curr - end);

  if (POS_EMPTY(curr)) { /* insertion point was empty of a node */
    if (!(*curr = make_node(h, exphcode, key, val)))
      return (stdhash_it*) STD_ERROR(STD_MEM_FAILURE2);

    ++h->num_nodes;
  } 
  /* insertion point already contained a (INACTIVE) node */
  else {
    /* free previous occupant of node */
    free((*curr)->kv.key);
    if ((*curr)->kv.value != 0)
      free((*curr)->kv.value);

    if (!init_node(h, *curr, exphcode, key, val))
      return (stdhash_it*) STD_ERROR(STD_MEM_FAILURE2);
  }
  ++h->size;
  if (curr < h->begin)   /* update begin if necessary */
    h->begin = curr;

  if (it != 0) {
    it->hash     = h;
    it->node_pos = curr;
    INIT_IT(it);
  }
  return it;
}

/* removes a particular key-value pair */
inline stdhash_it *stdhash_erase(stdhash_it *it) {
  STD_CONSTRUCT_CHECK(IS_HASH_INITED(it->hash));
  STD_BOUNDS_CHECK(IS_VALID_IT(it));

  (*it->node_pos)->exphcode = 0;                /* mark this node as inactive */

  /* update begin if I am about to remove it */
  if (it->node_pos == it->hash->begin)
    it->hash->begin = next(it->hash, it->hash->begin);

  if (--it->hash->size <= it->hash->low_thresh) /* is shrinkage necessary? */
    rehash(it->hash, it->hash->size);           /* if rehash fails it's ok */

  return stdhash_begin(it->hash, it);           /* always point iterator to begin */
}

/* KISS: removes all key-value pairs that have key as their key,
   returns number of key-value pairs removed.
*/
inline int stdhash_erase_key(stdhash *h, const void *key) {
  stdhash_it search;
  int num_erased;

  for (num_erased = 0; !stdhash_it_is_end(stdhash_find(h, &search, key)); ++num_erased)
    stdhash_erase(&search);

  return num_erased;
}

/* Some good equals-hashcode functions for commonly used key types */
/* key type is int or uint: is this faster or slower than using default fcns? */
stdbool stdhash_int_equals(const void *int1, const void *int2) {
  return *(int*) int1 == *(int*) int2;
}

size_t stdhash_int_hashcode(const void *kint) {
  return (size_t) *(int*) kint;
}

/* key type is C string (pointer to a null terminated array of characters) */
stdbool stdhash_str_equals(const void *str_ptr1, const void *str_ptr2) { 
  return !strcmp(*(const char**) str_ptr1, *(const char**) str_ptr2);
}

size_t stdhash_str_hashcode(const void *str_ptr) {
  const stduint8 *key = *(const stduint8**) str_ptr;
  size_t ret = 0;
  
  while (*key) 
    ret = ret * 33 + *key++;
  
  return ret;
}

#endif /* ifdef STDRAND_EXISTS */