genhash.c

Go to the documentation of this file.

/***********************************************************************
 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.
 
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
***********************************************************************/
 
/****************************************************************************
   A general-purpose generic hash table implementation.
 
   Based on implementation previous included in registry.c, but separated
   out so that can be used more generally.  Maybe we should just use glib?
 
      Original author:  David Pfitzner  dwp@mso.anu.edu.au
 
   A hash table maps keys to user data values, using a user-supplied hash
   function to do this efficiently. Here both keys and values are general
   data represented by (void*) pointers. Memory management of both keys
   and data is the responsibility of the caller: that is, the caller must
   ensure that the memory (especially for keys) remains valid (allocated)
   for as long as required (typically, the life of the genhash table).
   (Otherwise, to allocate keys internally would either have to restrict
   key type (e.g., strings), or have user-supplied function to duplicate
   a key type.  See further comments below.)
 
   User-supplied functions required are:
   key_val_func: map key to bucket number given number of buckets; should
                 map keys fairly evenly to range 0 to (num_buckets - 1)
                 inclusive.
 
   key_comp_func: compare keys for equality, necessary for lookups for keys
                  which map to the same genhash value. Keys which compare
                  equal should map to the same hash value. Returns 0 for
                  equality, so can use qsort-type comparison function (but
                  the hash table does not make use of the ordering
                  information if the return value is non-zero).
 
   Some constructors also accept following functions to be registered:
   key_copy_func: This is called when assigning a new value to a bucket.
   key_free_func: This is called when genhash no longer needs key construct.
                  Note that one key construct gets freed even when it is
                  replaced with another that is considered identical by
                  key_comp_func().
   data_copy_func: same as 'key_copy_func', but for data.
   data_free_func: same as 'key_free_func', but for data.
 
   Implementation uses open hashing. Collision resolution is done by
   separate chaining with linked lists. Resize hash table when deemed
   necessary by making and populating a new table.
****************************************************************************/
 
#ifdef HAVE_CONFIG_H
#include <fc_config.h>
#endif
 
#include <string.h>
 
/* utility */
#include "log.h"
#include "mem.h"
#include "shared.h"     /* ARRAY_SIZE */
#include "support.h"
 
#include "genhash.h"
 
#define FULL_RATIO 0.75         /* consider expanding when above this */
#define MIN_RATIO 0.24          /* shrink when below this */
 
struct genhash_entry {
  void *key;
  void *data;
  genhash_val_t hash_val;
  struct genhash_entry *next;
};
 
/* Contents of the opaque type: */
struct genhash {
  struct genhash_entry **buckets;
  genhash_val_fn_t key_val_func;
  genhash_comp_fn_t key_comp_func;
  genhash_copy_fn_t key_copy_func;
  genhash_free_fn_t key_free_func;
  genhash_copy_fn_t data_copy_func;
  genhash_free_fn_t data_free_func;
  size_t num_buckets;
  size_t num_entries;
  bool no_shrink;               /* Do not auto-shrink when set. */
};
 
struct genhash_iter {
  struct iterator vtable;
  struct genhash_entry *const *bucket, *const *end;
  const struct genhash_entry *iterator;
};
 
#define GENHASH_ITER(p) ((struct genhash_iter *) (p))
 
 
/************************************************************************/
genhash_val_t genhash_str_val_func(const char *vkey)
{
  unsigned long result = 0;
 
  for (; *vkey != '\0'; vkey++) {
    result *= 5;
    result += *vkey;
  }
  result &= 0xFFFFFFFF; /* To make results independent of sizeof(long) */
  return result;
}
 
/************************************************************************/
bool genhash_str_comp_func(const char *vkey1, const char *vkey2)
{
  return 0 == strcmp(vkey1, vkey2);
}
 
/************************************************************************/
char *genhash_str_copy_func(const char *vkey)
{
  return fc_strdup(vkey != nullptr ? vkey : "");
}
 
/************************************************************************/
void genhash_str_free_func(char *vkey)
{
  free(vkey);
}
 
/************************************************************************/
#define MIN_BUCKETS 29  /* Historical purposes. */
static size_t genhash_calc_num_buckets(size_t num_entries)
{
  /* A bunch of prime numbers close to successive elements of the sequence
   * A_n = 3 * 2 ^ n; to be used for table sizes. */
  static const size_t sizes[] = {
    MIN_BUCKETS,          53,         97,           193,
    389,       769,       1543,       3079,         6151,
    12289,     24593,     49157,      98317,        196613,
    393241,    786433,    1572869,    3145739,      6291469,
    12582917,  25165843,  50331653,   100663319,    201326611,
    402653189, 805306457, 1610612741, 3221225473ul, 4294967291ul
  };
  const size_t *pframe = sizes, *pmid;
  int fsize = ARRAY_SIZE(sizes) - 1, lpart;
 
  num_entries <<= 1; /* breathing room */
 
  while (fsize > 0) {
    lpart = fsize >> 1;
    pmid = pframe + lpart;
    if (*pmid < num_entries) {
      pframe = pmid + 1;
      fsize = fsize - lpart - 1;
    } else {
      fsize = lpart;
    }
  }
  return *pframe;
}
 
/************************************************************************/
static struct genhash *
genhash_new_nbuckets(genhash_val_fn_t key_val_func,
                     genhash_comp_fn_t key_comp_func,
                     genhash_copy_fn_t key_copy_func,
                     genhash_free_fn_t key_free_func,
                     genhash_copy_fn_t data_copy_func,
                     genhash_free_fn_t data_free_func,
                     size_t num_buckets)
{
  struct genhash *pgenhash = fc_malloc(sizeof(*pgenhash));
 
  log_debug("New genhash table with %lu buckets",
            (long unsigned) num_buckets);
 
  pgenhash->buckets = fc_calloc(num_buckets, sizeof(*pgenhash->buckets));
  pgenhash->key_val_func = key_val_func;
  pgenhash->key_comp_func = key_comp_func;
  pgenhash->key_copy_func = key_copy_func;
  pgenhash->key_free_func = key_free_func;
  pgenhash->data_copy_func = data_copy_func;
  pgenhash->data_free_func = data_free_func;
  pgenhash->num_buckets = num_buckets;
  pgenhash->num_entries = 0;
  pgenhash->no_shrink = FALSE;
 
  return pgenhash;
}
 
/************************************************************************/
struct genhash *
genhash_new_nentries_full(genhash_val_fn_t key_val_func,
                          genhash_comp_fn_t key_comp_func,
                          genhash_copy_fn_t key_copy_func,
                          genhash_free_fn_t key_free_func,
                          genhash_copy_fn_t data_copy_func,
                          genhash_free_fn_t data_free_func,
                          size_t nentries)
{
  return genhash_new_nbuckets(key_val_func, key_comp_func,
                              key_copy_func, key_free_func,
                              data_copy_func, data_free_func,
                              genhash_calc_num_buckets(nentries));
}
 
/************************************************************************/
struct genhash *genhash_new_nentries(genhash_val_fn_t key_val_func,
                                     genhash_comp_fn_t key_comp_func,
                                     size_t nentries)
{
  return genhash_new_nbuckets(key_val_func, key_comp_func,
                              nullptr, nullptr, nullptr, nullptr,
                              genhash_calc_num_buckets(nentries));
}
 
/************************************************************************/
struct genhash *genhash_new_full(genhash_val_fn_t key_val_func,
                                 genhash_comp_fn_t key_comp_func,
                                 genhash_copy_fn_t key_copy_func,
                                 genhash_free_fn_t key_free_func,
                                 genhash_copy_fn_t data_copy_func,
                                 genhash_free_fn_t data_free_func)
{
  return genhash_new_nbuckets(key_val_func, key_comp_func,
                              key_copy_func, key_free_func,
                              data_copy_func, data_free_func, MIN_BUCKETS);
}
 
/************************************************************************/
struct genhash *genhash_new(genhash_val_fn_t key_val_func,
                            genhash_comp_fn_t key_comp_func)
{
  return genhash_new_nbuckets(key_val_func, key_comp_func,
                              nullptr, nullptr, nullptr, nullptr, MIN_BUCKETS);
}
 
/************************************************************************/
void genhash_destroy(struct genhash *pgenhash)
{
  pgenhash->no_shrink = TRUE;
  genhash_clear(pgenhash);
  free(pgenhash->buckets);
  free(pgenhash);
}
 
/************************************************************************/
static void genhash_resize_table(struct genhash *pgenhash,
                                 size_t new_nbuckets)
{
  struct genhash_entry **new_buckets, **bucket, **end, **slot;
  struct genhash_entry *iter, *next;
 
  fc_assert(new_nbuckets >= pgenhash->num_entries);
 
  new_buckets = fc_calloc(new_nbuckets, sizeof(*pgenhash->buckets));
 
  bucket = pgenhash->buckets;
  end = bucket + pgenhash->num_buckets;
  for (; bucket < end; bucket++) {
    for (iter = *bucket; iter != nullptr; iter = next) {
      slot = new_buckets + (iter->hash_val % new_nbuckets);
      next = iter->next;
      iter->next = *slot;
      *slot = iter;
    }
  }
 
  free(pgenhash->buckets);
  pgenhash->buckets = new_buckets;
  pgenhash->num_buckets = new_nbuckets;
}
 
/************************************************************************/
#define genhash_maybe_expand(htab) genhash_maybe_resize((htab), TRUE)
#define genhash_maybe_shrink(htab) genhash_maybe_resize((htab), FALSE)
static bool genhash_maybe_resize(struct genhash *pgenhash, bool expandingp)
{
  size_t limit, new_nbuckets;
 
  if (!expandingp && pgenhash->no_shrink) {
    return FALSE;
  }
  if (expandingp) {
    limit = FULL_RATIO * pgenhash->num_buckets;
    if (pgenhash->num_entries < limit) {
      return FALSE;
    }
  } else {
    if (pgenhash->num_buckets <= MIN_BUCKETS) {
      return FALSE;
    }
    limit = MIN_RATIO * pgenhash->num_buckets;
    if (pgenhash->num_entries > limit) {
      return FALSE;
    }
  }
 
  new_nbuckets = genhash_calc_num_buckets(pgenhash->num_entries);
 
  log_debug("%s genhash (entries = %lu, buckets =  %lu, new = %lu, "
            "%s limit = %lu)",
            (new_nbuckets < pgenhash->num_buckets ? "Shrinking"
             : (new_nbuckets > pgenhash->num_buckets
                ? "Expanding" : "Rehashing")),
            (long unsigned) pgenhash->num_entries,
            (long unsigned) pgenhash->num_buckets,
            (long unsigned) new_nbuckets,
            expandingp ? "up": "down", (long unsigned) limit);
  genhash_resize_table(pgenhash, new_nbuckets);
  return TRUE;
}
 
 
/************************************************************************/
static inline genhash_val_t genhash_val_calc(const struct genhash *pgenhash,
                                             const void *key)
{
  if (pgenhash->key_val_func != nullptr) {
    return pgenhash->key_val_func(key);
  } else {
    return ((intptr_t) key);
  }
}
 
/************************************************************************/
static inline struct genhash_entry **
genhash_slot_lookup(const struct genhash *pgenhash,
                    const void *key,
                    genhash_val_t hash_val)
{
  struct genhash_entry **slot;
  genhash_comp_fn_t key_comp_func = pgenhash->key_comp_func;
 
  slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
  if (key_comp_func != nullptr) {
    for (; *slot != nullptr; slot = &(*slot)->next) {
      if (hash_val == (*slot)->hash_val
          && key_comp_func((*slot)->key, key)) {
        return slot;
      }
    }
  } else {
    for (; *slot != nullptr; slot = &(*slot)->next) {
      if (key == (*slot)->key) {
        return slot;
      }
    }
  }
  return slot;
}
 
/************************************************************************/
static inline void genhash_default_get(void **pkey, void **data)
{
  if (pkey != nullptr) {
    *pkey = nullptr;
  }
  if (data != nullptr) {
    *data = nullptr;
  }
}
 
/************************************************************************/
static inline void genhash_slot_get(struct genhash_entry *const *slot,
                                    void **pkey, void **data)
{
  const struct genhash_entry *entry = *slot;
 
  if (pkey != nullptr) {
    *pkey = entry->key;
  }
  if (data != nullptr) {
    *data = entry->data;
  }
}
 
/************************************************************************/
static inline void genhash_slot_create(struct genhash *pgenhash,
                                       struct genhash_entry **slot,
                                       const void *key, const void *data,
                                       genhash_val_t hash_val)
{
  struct genhash_entry *entry = fc_malloc(sizeof(*entry));
 
  entry->key = (pgenhash->key_copy_func != nullptr
                ? pgenhash->key_copy_func(key) : (void *) key);
  entry->data = (pgenhash->data_copy_func != nullptr
                 ? pgenhash->data_copy_func(data) : (void *) data);
  entry->hash_val = hash_val;
  entry->next = *slot;
  *slot = entry;
}
 
/************************************************************************/
static inline void genhash_slot_free(struct genhash *pgenhash,
                                     struct genhash_entry **slot)
{
  struct genhash_entry *entry = *slot;
 
  if (pgenhash->key_free_func != nullptr) {
    pgenhash->key_free_func(entry->key);
  }
  if (pgenhash->data_free_func != nullptr) {
    pgenhash->data_free_func(entry->data);
  }
 
  *slot = entry->next;
  free(entry);
}
 
/************************************************************************/
static inline void genhash_slot_set(struct genhash *pgenhash,
                                    struct genhash_entry **slot,
                                    const void *key, const void *data)
{
  struct genhash_entry *entry = *slot;
 
  if (pgenhash->key_free_func != nullptr) {
    pgenhash->key_free_func(entry->key);
  }
  if (pgenhash->data_free_func != nullptr) {
    pgenhash->data_free_func(entry->data);
  }
 
  entry->key = (pgenhash->key_copy_func != nullptr
                ? pgenhash->key_copy_func(key) : (void *) key);
  entry->data = (pgenhash->data_copy_func != nullptr
                 ? pgenhash->data_copy_func(data) : (void *) data);
}
 
/************************************************************************/
bool genhash_set_no_shrink(struct genhash *pgenhash, bool no_shrink)
{
  bool old;
 
  old = pgenhash->no_shrink;
  pgenhash->no_shrink = no_shrink;
 
  return old;
}
 
/************************************************************************/
size_t genhash_size(const struct genhash *pgenhash)
{
  return pgenhash->num_entries;
}
 
/************************************************************************/
size_t genhash_capacity(const struct genhash *pgenhash)
{
  return pgenhash->num_buckets;
}
 
/************************************************************************/
struct genhash *genhash_copy(const struct genhash *pgenhash)
{
  struct genhash *new_genhash;
  struct genhash_entry *const *src_bucket, *const *end;
  const struct genhash_entry *src_iter;
  struct genhash_entry **dest_slot, **dest_bucket;
 
  new_genhash = fc_malloc(sizeof(*new_genhash));
 
  /* Copy fields. */
  *new_genhash = *pgenhash;
 
  /* But make fresh buckets. */
  new_genhash->buckets = fc_calloc(new_genhash->num_buckets,
                                   sizeof(*new_genhash->buckets));
 
  /* Let's re-insert all data */
  src_bucket = pgenhash->buckets;
  end = src_bucket + pgenhash->num_buckets;
  dest_bucket = new_genhash->buckets;
 
  for (; src_bucket < end; src_bucket++, dest_bucket++) {
    dest_slot = dest_bucket;
    for (src_iter = *src_bucket; src_iter != nullptr;
         src_iter = src_iter->next) {
      genhash_slot_create(new_genhash, dest_slot, src_iter->key,
                          src_iter->data, src_iter->hash_val);
      dest_slot = &(*dest_slot)->next;
    }
  }
 
  return new_genhash;
}
 
/************************************************************************/
void genhash_clear(struct genhash *pgenhash)
{
  struct genhash_entry **bucket, **end;
 
  bucket = pgenhash->buckets;
  end = bucket + pgenhash->num_buckets;
  for (; bucket < end; bucket++) {
    while (*bucket != nullptr) {
      genhash_slot_free(pgenhash, bucket);
    }
  }
 
  pgenhash->num_entries = 0;
  genhash_maybe_shrink(pgenhash);
}
 
/************************************************************************/
bool genhash_insert(struct genhash *pgenhash, const void *key,
                    const void *data)
{
  struct genhash_entry **slot;
  genhash_val_t hash_val;
 
  hash_val = genhash_val_calc(pgenhash, key);
  slot = genhash_slot_lookup(pgenhash, key, hash_val);
  if (*slot != nullptr) {
    return FALSE;
  } else {
    if (genhash_maybe_expand(pgenhash)) {
      /* Recalculate slot. */
      slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
    }
    genhash_slot_create(pgenhash, slot, key, data, hash_val);
    pgenhash->num_entries++;
    return TRUE;
  }
}
 
/************************************************************************/
bool genhash_replace(struct genhash *pgenhash, const void *key,
                     const void *data)
{
  return genhash_replace_full(pgenhash, key, data, nullptr, nullptr);
}
 
/************************************************************************/
bool genhash_replace_full(struct genhash *pgenhash, const void *key,
                          const void *data, void **old_pkey,
                          void **old_pdata)
{
  struct genhash_entry **slot;
  genhash_val_t hash_val;
 
  hash_val = genhash_val_calc(pgenhash, key);
  slot = genhash_slot_lookup(pgenhash, key, hash_val);
  if (*slot != nullptr) {
    /* Replace. */
    genhash_slot_get(slot, old_pkey, old_pdata);
    genhash_slot_set(pgenhash, slot, key, data);
    return TRUE;
  } else {
    /* Insert. */
    if (genhash_maybe_expand(pgenhash)) {
      /* Recalculate slot. */
      slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
    }
    genhash_default_get(old_pkey, old_pdata);
    genhash_slot_create(pgenhash, slot, key, data, hash_val);
    pgenhash->num_entries++;
    return FALSE;
  }
}
 
/************************************************************************/
bool genhash_lookup(const struct genhash *pgenhash, const void *key,
                    void **pdata)
{
  struct genhash_entry **slot;
 
  slot = genhash_slot_lookup(pgenhash, key, genhash_val_calc(pgenhash, key));
  if (*slot != nullptr) {
    genhash_slot_get(slot, nullptr, pdata);
    return TRUE;
  } else {
    genhash_default_get(nullptr, pdata);
    return FALSE;
  }
}
 
/************************************************************************/
bool genhash_remove(struct genhash *pgenhash, const void *key)
{
  return genhash_remove_full(pgenhash, key, nullptr, nullptr);
}
 
/************************************************************************/
bool genhash_remove_full(struct genhash *pgenhash, const void *key,
                         void **deleted_pkey, void **deleted_pdata)
{
  struct genhash_entry **slot;
 
  slot = genhash_slot_lookup(pgenhash, key, genhash_val_calc(pgenhash, key));
  if (*slot != nullptr) {
    genhash_slot_get(slot, deleted_pkey, deleted_pdata);
    genhash_slot_free(pgenhash, slot);
    genhash_maybe_shrink(pgenhash);
 
    fc_assert(0 < pgenhash->num_entries);
 
    pgenhash->num_entries--;
    return TRUE;
  } else {
    genhash_default_get(deleted_pkey, deleted_pdata);
    return FALSE;
  }
}
 
 
/************************************************************************/
bool genhashes_are_equal(const struct genhash *pgenhash1,
                         const struct genhash *pgenhash2)
{
  return genhashes_are_equal_full(pgenhash1, pgenhash2, nullptr);
}
 
/************************************************************************/
bool genhashes_are_equal_full(const struct genhash *pgenhash1,
                              const struct genhash *pgenhash2,
                              genhash_comp_fn_t data_comp_func)
{
  struct genhash_entry *const *bucket1, *const *max1, *const *slot2;
  const struct genhash_entry *iter1;
 
  /* Check pointers. */
  if (pgenhash1 == pgenhash2) {
    return TRUE;
  } else if (pgenhash1 == nullptr || pgenhash2 == nullptr) {
    return FALSE;
  }
 
  /* General check. */
  if (pgenhash1->num_entries != pgenhash2->num_entries
      /* If the key functions is not the same, we cannot know if the
       * keys are equals. */
      || pgenhash1->key_val_func != pgenhash2->key_val_func
      || pgenhash1->key_comp_func != pgenhash2->key_comp_func) {
    return FALSE;
  }
 
  /* Compare buckets. */
  bucket1 = pgenhash1->buckets;
  max1 = bucket1 + pgenhash1->num_buckets;
  for (; bucket1 < max1; bucket1++) {
    for (iter1 = *bucket1; iter1 != nullptr; iter1 = iter1->next) {
      slot2 = genhash_slot_lookup(pgenhash2, iter1->key, iter1->hash_val);
      if (*slot2 == nullptr
          || (iter1->data != (*slot2)->data
              && (data_comp_func == nullptr
                  || !data_comp_func(iter1->data, (*slot2)->data)))) {
        return FALSE;
      }
    }
  }
 
  return TRUE;
}
 
 
/************************************************************************/
size_t genhash_iter_sizeof(void)
{
  return sizeof(struct genhash_iter);
}
 
/************************************************************************/
void *genhash_iter_key(const struct iterator *genhash_iter)
{
  struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
  return (void *) iter->iterator->key;
}
 
/************************************************************************/
void *genhash_iter_value(const struct iterator *genhash_iter)
{
  struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
  return (void *) iter->iterator->data;
}
 
/************************************************************************/
static void genhash_iter_next(struct iterator *genhash_iter)
{
  struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
 
  iter->iterator = iter->iterator->next;
  if (iter->iterator != nullptr) {
    return;
  }
 
  for (iter->bucket++; iter->bucket < iter->end; iter->bucket++) {
    if (*iter->bucket != nullptr) {
      iter->iterator = *iter->bucket;
      return;
    }
  }
}
 
/************************************************************************/
static void *genhash_iter_get(const struct iterator *genhash_iter)
{
  return (void *) genhash_iter;
}
 
/************************************************************************/
static bool genhash_iter_valid(const struct iterator *genhash_iter)
{
  struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
  return iter->bucket < iter->end;
}
 
/************************************************************************/
static inline struct iterator *
genhash_iter_init_common(struct genhash_iter *iter,
                         const struct genhash *pgenhash,
                         void * (*get) (const struct iterator *))
{
  if (pgenhash == nullptr) {
    return invalid_iter_init(ITERATOR(iter));
  }
 
  iter->vtable.next = genhash_iter_next;
  iter->vtable.get = get;
  iter->vtable.valid = genhash_iter_valid;
  iter->bucket = pgenhash->buckets;
  iter->end = pgenhash->buckets + pgenhash->num_buckets;
 
  /* Seek to the first used bucket. */
  for (; iter->bucket < iter->end; iter->bucket++) {
    if (*iter->bucket != nullptr) {
      iter->iterator = *iter->bucket;
      break;
    }
  }
 
  return ITERATOR(iter);
}
 
/************************************************************************/
struct iterator *genhash_iter_init(struct genhash_iter *iter,
                                   const struct genhash *pgenhash)
{
  return genhash_iter_init_common(iter, pgenhash, genhash_iter_get);
}
 
/************************************************************************/
struct iterator *genhash_key_iter_init(struct genhash_iter *iter,
                                       const struct genhash *pgenhash)
{
  return genhash_iter_init_common(iter, pgenhash, genhash_iter_key);
}
 
/************************************************************************/
struct iterator *genhash_value_iter_init(struct genhash_iter *iter,
                                         const struct genhash *pgenhash)
{
  return genhash_iter_init_common(iter, pgenhash, genhash_iter_value);
}