genhash.cpp

Go to the documentation of this file.

/*__            ___                 ***************************************
/   \          /   \          Copyright (c) 1996-2020 Freeciv21 and Freeciv
\_   \        /  __/          contributors. This file is part of Freeciv21.
 _\   \      /  /__     Freeciv21 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 3 of the  License,
       |                              or (at your option) any later version.
     _/     /\                  You should have received  a copy of the GNU
    /o)  (o/\ \_                General Public License along with Freeciv21.
    \_____/ /                     If not, see https://www.gnu.org/licenses/.
      \____/        ********************************************************/
 
#include "genhash.h"
 
// utility
#include "log.h"
#include "shared.h" // ARRAY_SIZE
#include "support.h"
 
#include <cstring>
 
#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(nullptr != vkey ? vkey : "");
}
 
void genhash_str_free_func(char *vkey)
{
#ifdef FREECIV_DEBUG
  fc_assert_ret(nullptr != vkey);
#endif
  delete[] 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)
{
  genhash *pgenhash = new genhash;
 
  log_debug("New genhash table with %lu buckets",
            (long unsigned) num_buckets);
 
  pgenhash->buckets = new genhash_entry *[num_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)
{
  fc_assert_ret(nullptr != pgenhash);
  pgenhash->no_shrink = true;
  genhash_clear(pgenhash);
  delete[] pgenhash->buckets;
  delete pgenhash;
  pgenhash = nullptr;
}
 
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 = new genhash_entry *[new_nbuckets]();
  bucket = pgenhash->buckets;
  end = bucket + pgenhash->num_buckets;
  for (; bucket < end; bucket++) {
    for (iter = *bucket; nullptr != iter; iter = next) {
      slot = new_buckets + (iter->hash_val % new_nbuckets);
      next = iter->next;
      iter->next = *slot;
      *slot = iter;
    }
  }
 
  delete[] 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 (nullptr != pgenhash->key_val_func) {
    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 (nullptr != key_comp_func) {
    for (; nullptr != *slot; slot = &(*slot)->next) {
      if (hash_val == (*slot)->hash_val
          && key_comp_func((*slot)->key, key)) {
        return slot;
      }
    }
  } else {
    for (; nullptr != *slot; slot = &(*slot)->next) {
      if (key == (*slot)->key) {
        return slot;
      }
    }
  }
  return slot;
}
 
static inline void genhash_default_get(void **pkey, void **data)
{
  if (nullptr != pkey) {
    *pkey = nullptr;
  }
  if (nullptr != data) {
    *data = nullptr;
  }
}
 
static inline void genhash_slot_get(struct genhash_entry *const *slot,
                                    void **pkey, void **data)
{
  const struct genhash_entry *entry = *slot;
 
  if (nullptr != pkey) {
    *pkey = entry->key;
  }
  if (nullptr != data) {
    *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)
{
  genhash_entry *entry = new genhash_entry;
 
  entry->key =
      (nullptr != pgenhash->key_copy_func ? pgenhash->key_copy_func(key)
                                          : const_cast<void *>(key));
  entry->data =
      (nullptr != pgenhash->data_copy_func ? pgenhash->data_copy_func(data)
                                           : const_cast<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 (nullptr != pgenhash->key_free_func) {
    ::operator delete[](entry->key);
  }
  if (nullptr != pgenhash->data_free_func) {
    ::operator delete(entry->data);
  }
  *slot = entry->next;
  delete 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 (nullptr != pgenhash->key_free_func) {
    pgenhash->key_free_func(entry->key);
  }
  if (nullptr != pgenhash->data_free_func) {
    pgenhash->data_free_func(entry->data);
  }
  entry->key =
      (nullptr != pgenhash->key_copy_func ? pgenhash->key_copy_func(key)
                                          : const_cast<void *>(key));
  entry->data =
      (nullptr != pgenhash->data_copy_func ? pgenhash->data_copy_func(data)
                                           : const_cast<void *>(data));
}
 
bool genhash_set_no_shrink(struct genhash *pgenhash, bool no_shrink)
{
  bool old;
 
  fc_assert_ret_val(nullptr != pgenhash, false);
  old = pgenhash->no_shrink;
  pgenhash->no_shrink = no_shrink;
  return old;
}
 
size_t genhash_size(const struct genhash *pgenhash)
{
  fc_assert_ret_val(nullptr != pgenhash, 0);
  return pgenhash->num_entries;
}
 
size_t genhash_capacity(const struct genhash *pgenhash)
{
  fc_assert_ret_val(nullptr != pgenhash, 0);
  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;
 
  fc_assert_ret_val(nullptr != pgenhash, nullptr);
 
  new_genhash = new genhash;
 
  // Copy fields.
  *new_genhash = *pgenhash;
 
  // But make fresh buckets.
  new_genhash->buckets = new genhash_entry *[new_genhash->num_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; nullptr != src_iter;
         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;
 
  fc_assert_ret(nullptr != pgenhash);
 
  bucket = pgenhash->buckets;
  end = bucket + pgenhash->num_buckets;
  for (; bucket < end; bucket++) {
    while (nullptr != *bucket) {
      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;
 
  fc_assert_ret_val(nullptr != pgenhash, false);
 
  hash_val = genhash_val_calc(pgenhash, key);
  slot = genhash_slot_lookup(pgenhash, key, hash_val);
  if (nullptr != *slot) {
    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;
 
  fc_assert_action(nullptr != pgenhash,
                   genhash_default_get(old_pkey, old_pdata);
                   return false);
 
  hash_val = genhash_val_calc(pgenhash, key);
  slot = genhash_slot_lookup(pgenhash, key, hash_val);
  if (nullptr != *slot) {
    // 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;
 
  fc_assert_action(nullptr != pgenhash, genhash_default_get(nullptr, pdata);
                   return false);
 
  slot = genhash_slot_lookup(pgenhash, key, genhash_val_calc(pgenhash, key));
  if (nullptr != *slot) {
    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;
 
  fc_assert_action(nullptr != pgenhash,
                   genhash_default_get(deleted_pkey, deleted_pdata);
                   return false);
 
  slot = genhash_slot_lookup(pgenhash, key, genhash_val_calc(pgenhash, key));
  if (nullptr != *slot) {
    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 genhashs_are_equal(const struct genhash *pgenhash1,
                        const struct genhash *pgenhash2)
{
  return genhashs_are_equal_full(pgenhash1, pgenhash2, nullptr);
}
 
bool genhashs_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 (nullptr == pgenhash1 || nullptr == pgenhash2) {
    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; nullptr != iter1; iter1 = iter1->next) {
      slot2 = genhash_slot_lookup(pgenhash2, iter1->key, iter1->hash_val);
      if (nullptr == *slot2
          || (iter1->data != (*slot2)->data
              && (nullptr == data_comp_func
                  || !data_comp_func(iter1->data, (*slot2)->data)))) {
        return false;
      }
    }
  }
 
  return true;
}
 
size_t genhash_iter_sizeof() { return sizeof(struct genhash_iter); }
 
void *genhash_iter_key(const struct iterator *genhash_iter)
{
  struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
  return iter->iterator->key;
}
 
void *genhash_iter_value(const struct iterator *genhash_iter)
{
  struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
  return 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 (nullptr != iter->iterator) {
    return;
  }
 
  for (iter->bucket++; iter->bucket < iter->end; iter->bucket++) {
    if (nullptr != *iter->bucket) {
      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 (nullptr == pgenhash) {
    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 (nullptr != *iter->bucket) {
      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);
}