hash.c

Go to the documentation of this file.

#include "config.h"
#include <ctype.h>
#include <stdbool.h>
#include "hash.h"
#include "memory.h"
#include "string2.h"

#define SOME_PRIME 149711

static size_t gen_string_hash(union HashKey key, size_t num_elems)
{
  size_t hash = 0;
  const unsigned char *s = (const unsigned char *) key.strkey;

  while (*s != '\0')
    hash += ((hash << 7) + *s++);
  hash = (hash * SOME_PRIME) % num_elems;

  return hash;
}

static int cmp_string_key(union HashKey a, union HashKey b)
{
  return mutt_str_cmp(a.strkey, b.strkey);
}

static size_t gen_case_string_hash(union HashKey key, size_t num_elems)
{
  size_t hash = 0;
  const unsigned char *s = (const unsigned char *) key.strkey;

  while (*s != '\0')
    hash += ((hash << 7) + tolower(*s++));
  hash = (hash * SOME_PRIME) % num_elems;

  return hash;
}

static int cmp_case_string_key(union HashKey a, union HashKey b)
{
  return mutt_istr_cmp(a.strkey, b.strkey);
}

static size_t gen_int_hash(union HashKey key, size_t num_elems)
{
  return (key.intkey % num_elems);
}

static int cmp_int_key(union HashKey a, union HashKey b)
{
  if (a.intkey == b.intkey)
    return 0;
  if (a.intkey < b.intkey)
    return -1;
  return 1;
}

static struct HashTable *hash_new(size_t num_elems)
{
  struct HashTable *table = mutt_mem_calloc(1, sizeof(struct HashTable));
  if (num_elems == 0)
    num_elems = 2;
  table->num_elems = num_elems;
  table->table = mutt_mem_calloc(num_elems, sizeof(struct HashElem *));
  return table;
}

static struct HashElem *union_hash_insert(struct HashTable *table,
                                          union HashKey key, int type, void *data)
{
  if (!table)
    return NULL; // LCOV_EXCL_LINE

  struct HashElem *he = mutt_mem_calloc(1, sizeof(struct HashElem));
  size_t hash = table->gen_hash(key, table->num_elems);
  he->key = key;
  he->data = data;
  he->type = type;

  if (table->allow_dups)
  {
    he->next = table->table[hash];
    table->table[hash] = he;
  }
  else
  {
    struct HashElem *tmp = NULL, *last = NULL;

    for (tmp = table->table[hash], last = NULL; tmp; last = tmp, tmp = tmp->next)
    {
      const int rc = table->cmp_key(tmp->key, key);
      if (rc == 0)
      {
        FREE(&he);
        return NULL;
      }
      if (rc > 0)
        break;
    }
    if (last)
      last->next = he;
    else
      table->table[hash] = he;
    he->next = tmp;
  }
  return he;
}

static struct HashElem *union_hash_find_elem(const struct HashTable *table, union HashKey key)
{
  if (!table)
    return NULL; // LCOV_EXCL_LINE

  size_t hash = table->gen_hash(key, table->num_elems);
  struct HashElem *he = table->table[hash];
  for (; he; he = he->next)
  {
    if (table->cmp_key(key, he->key) == 0)
      return he;
  }
  return NULL;
}

static void *union_hash_find(const struct HashTable *table, union HashKey key)
{
  if (!table)
    return NULL; // LCOV_EXCL_LINE
  struct HashElem *he = union_hash_find_elem(table, key);
  if (he)
    return he->data;
  return NULL;
}

static void union_hash_delete(struct HashTable *table, union HashKey key, const void *data)
{
  if (!table)
    return; // LCOV_EXCL_LINE

  size_t hash = table->gen_hash(key, table->num_elems);
  struct HashElem *he = table->table[hash];
  struct HashElem **last = &table->table[hash];

  while (he)
  {
    if (((data == he->data) || !data) && (table->cmp_key(he->key, key) == 0))
    {
      *last = he->next;
      if (table->hdata_free)
        table->hdata_free(he->type, he->data, table->hdata);
      if (table->strdup_keys)
        FREE(&he->key.strkey);
      FREE(&he);

      he = *last;
    }
    else
    {
      last = &he->next;
      he = he->next;
    }
  }
}

struct HashTable *mutt_hash_new(size_t num_elems, HashFlags flags)
{
  struct HashTable *table = hash_new(num_elems);
  if (flags & MUTT_HASH_STRCASECMP)
  {
    table->gen_hash = gen_case_string_hash;
    table->cmp_key = cmp_case_string_key;
  }
  else
  {
    table->gen_hash = gen_string_hash;
    table->cmp_key = cmp_string_key;
  }
  if (flags & MUTT_HASH_STRDUP_KEYS)
    table->strdup_keys = true;
  if (flags & MUTT_HASH_ALLOW_DUPS)
    table->allow_dups = true;
  return table;
}

struct HashTable *mutt_hash_int_new(size_t num_elems, HashFlags flags)
{
  struct HashTable *table = hash_new(num_elems);
  table->gen_hash = gen_int_hash;
  table->cmp_key = cmp_int_key;
  if (flags & MUTT_HASH_ALLOW_DUPS)
    table->allow_dups = true;
  return table;
}

void mutt_hash_set_destructor(struct HashTable *table, hash_hdata_free_t fn, intptr_t fn_data)
{
  if (!table)
    return;
  table->hdata_free = fn;
  table->hdata = fn_data;
}

struct HashElem *mutt_hash_typed_insert(struct HashTable *table,
                                        const char *strkey, int type, void *data)
{
  if (!table || !strkey)
    return NULL;

  union HashKey key;
  key.strkey = table->strdup_keys ? mutt_str_dup(strkey) : strkey;
  return union_hash_insert(table, key, type, data);
}

struct HashElem *mutt_hash_insert(struct HashTable *table, const char *strkey, void *data)
{
  return mutt_hash_typed_insert(table, strkey, -1, data);
}

struct HashElem *mutt_hash_int_insert(struct HashTable *table, unsigned int intkey, void *data)
{
  if (!table)
    return NULL;
  union HashKey key;
  key.intkey = intkey;
  return union_hash_insert(table, key, -1, data);
}

void *mutt_hash_find(const struct HashTable *table, const char *strkey)
{
  if (!table || !strkey)
    return NULL;
  union HashKey key;
  key.strkey = strkey;
  return union_hash_find(table, key);
}

struct HashElem *mutt_hash_find_elem(const struct HashTable *table, const char *strkey)
{
  if (!table || !strkey)
    return NULL;
  union HashKey key;
  key.strkey = strkey;
  return union_hash_find_elem(table, key);
}

void *mutt_hash_int_find(const struct HashTable *table, unsigned int intkey)
{
  if (!table)
    return NULL;
  union HashKey key;
  key.intkey = intkey;
  return union_hash_find(table, key);
}

struct HashElem *mutt_hash_find_bucket(const struct HashTable *table, const char *strkey)
{
  if (!table || !strkey)
    return NULL;

  union HashKey key;

  key.strkey = strkey;
  size_t hash = table->gen_hash(key, table->num_elems);
  return table->table[hash];
}

void mutt_hash_delete(struct HashTable *table, const char *strkey, const void *data)
{
  if (!table || !strkey)
    return;
  union HashKey key;
  // Copy the key because union_hash_delete() may use it after the HashElem is freed.
  key.strkey = mutt_str_dup(strkey);
  union_hash_delete(table, key, data);
  FREE(&key.strkey);
}

void mutt_hash_int_delete(struct HashTable *table, unsigned int intkey, const void *data)
{
  if (!table)
    return;
  union HashKey key;
  key.intkey = intkey;
  union_hash_delete(table, key, data);
}

void mutt_hash_free(struct HashTable **ptr)
{
  if (!ptr || !*ptr)
    return;

  struct HashTable *table = *ptr;
  struct HashElem *elem = NULL, *tmp = NULL;

  for (size_t i = 0; i < table->num_elems; i++)
  {
    for (elem = table->table[i]; elem;)
    {
      tmp = elem;
      elem = elem->next;
      if (table->hdata_free && tmp->data)
        table->hdata_free(tmp->type, tmp->data, table->hdata);
      if (table->strdup_keys)
        FREE(&tmp->key.strkey);
      FREE(&tmp);
    }
  }
  FREE(&table->table);
  FREE(ptr);
}

struct HashElem *mutt_hash_walk(const struct HashTable *table, struct HashWalkState *state)
{
  if (!table || !state)
    return NULL;

  if (state->last && state->last->next)
  {
    state->last = state->last->next;
    return state->last;
  }

  if (state->last)
    state->index++;

  while (state->index < table->num_elems)
  {
    if (table->table[state->index])
    {
      state->last = table->table[state->index];
      return state->last;
    }
    state->index++;
  }

  state->index = 0;
  state->last = NULL;
  return NULL;
}