ghash.h hashtable multimap

// avp 2015 simple multiset hash key:value  resolve collisions by LIFO chaining
#ifndef _GHASH_H
#define _GHASH_H

#include <stdlib.h>
#include <stdint.h>
#include <string.h>



/* hash table entry
 * embed it to your data structure
 * для кучи задач этого может оказаться достаточно, но эту же структуру
 * (и даже несколько, по одной для каждой хэш-таблицы)
 * можно встраивать в свои данные,
 * которые станут доступны из разных хэш-таблиц без дублирования
 */
struct gh_entry {
  void *data;
  void *key;
  struct gh_entry *next;
  uint32_t hcode,
    keylen;
};

/**
 * hash_entry - get the user data for this entry (from include/linux/list.h)
 * @ptr:    the &struct hash_entry pointer
 * @type:   the type of the user data (e.g. struct my_data) embedded in this entry
 * @member: the name of the gh_entry within the struct (e.g. entry)
 */
#define hash_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))


// user defined hash-function
typedef uint32_t (*gh_hash)(const void *key, uint32_t keylen);
// user defined keys compare function
typedef int (*gh_equals)(const void *key1, uint32_t key1len,
              const void *key2, uint32_t key2len);
struct gh_table;
// user defined callback (used for remove entry, traverse and destroy table)
typedef void (*gh_ucbf)(struct gh_table *htab, struct gh_entry *entry);

// hash table control block
struct gh_table {
  uint32_t capacity,       // maximum number of buckets
    size;                  // current number of entries
  struct gh_entry **table; // array of LIFO collisions lists
  gh_hash fhash;           // calculate hash for key
  gh_equals equals;        // compare 2 keys, returns 1 if they are equal
};

// macros for lookup/remove char *keys
#define GH_FIND_STR(tab,key) ({char *_k = (char *)(key);    \
      gh_lookup((tab), _k, strlen(_k));})
#define GH_REMOVE_STR(tab,key) ({char *_k = (char *)(key);  \
      gh_remove((tab), _k, strlen(_k));})

// default keys compare function
static int _gh_key_equals (const void *key1, uint32_t key1len,
               const void *key2, uint32_t key2len) {
  return key1len == key2len ? memcmp(key1, key2, key1len) == 0 : 0;
}

// Bernstein -- default hash function (found somewhere on the Internet)
static uint32_t _gh_bernstein (const void *key, uint32_t keylen) {
  uint32_t seed = 1, i;
  const uint8_t * data = (const uint8_t*)key;

  for(i = 0; i < keylen; ++i)
    seed = 33 * seed + data[i];

  return seed;
}

static inline void *memdup (const void *src, size_t len) {
  void *res = malloc(len);
  if (res)
    memcpy(res, src, len);
  return res;
}


/**
 * gh_init --  init new hashtable
 * @capacity: number of backets (collision chains)
 * @fhash: user hash function
 * @fcmp: user keys equal compare function
 * @frem: callback function, called before free() when entry removes from table
 *
 * Returns: 1 -- OK, 0 -- no memory
 */
static int
gh_init (struct gh_table *htab,
     uint32_t capacity, gh_hash fhash, gh_equals fcmp)
{
  if (capacity < 2)
    capacity = 2;

  if ((htab->table = (struct gh_entry **)calloc(htab->capacity = capacity,
                        sizeof(struct gh_entry *)))) {
    htab->size = 0;
    htab->fhash = fhash ? fhash : _gh_bernstein;
    htab->equals = fcmp ? fcmp :_gh_key_equals;
  }

  return htab->table != 0;
}

/**
 * gh_destroy --  free all memory, @htab invalidate
 * @htab: hash table
 * @uf: function, if not NULL, called for each removed entry
 * Note: @uf called after removing gh_entry from chain
 */
static void
gh_destroy (struct gh_table *htab, gh_ucbf uf)
{
  uint32_t i;

  for (i = 0; i < htab->capacity; i++)
    while (htab->table[i]) {
      struct gh_entry *p = htab->table[i];
      htab->table[i] = p->next;
      if (uf)
    uf(htab, p);
    }

  free(htab->table);
  htab->table = 0;
}


/*
  Две функции для перебора элементов таблицы.
  Типичное использование
    for (p = gh_first_entry(&htab); p; p = gh_next_entry(&htab, p))
      ...
 */
/**
 * gh_first_entry -- get first entry
 * @htab:  hash table ptr
 * Returns: ptr to gh_entry or 0 (empty table);
 */
static struct gh_entry *
gh_first_entry (struct gh_table *htab)
{
  uint32_t i;
  if (htab->size)
    for (i = 0; i < htab->capacity; i++)
      if (htab->table[i])
    return htab->table[i];
  return 0;
}

/**
 * gh_next_entry -- get next entry
 * @htab:  hash table ptr
 * @eprev: ptr to VALID gh_entry (returned by gh_first_entry() or similar)
 * Returns: ptr to gh_entry or 0 (no more entries);
 */
static struct gh_entry *
gh_next_entry (struct gh_table *htab, struct gh_entry *eprev)
{
  if (eprev) {
    if (eprev->next)
      return eprev->next;
    uint32_t i = eprev->hcode % htab->capacity + 1;
    for (; i < htab->capacity; i++)
      if (htab->table[i])
    return htab->table[i];
  }
  return 0;
}

/**
 * gh_next_samekey_entry -- get next entry with same key
 * @htab:  hash table ptr
 * @eprev: ptr to VALID gh_entry (returned by gh_first_entry() or similar)
 * Returns: ptr to gh_entry or 0 (no more entries with eprev->key);
 * Note: useful for fetch entries with the same key from multiset
 */
static struct gh_entry *
gh_next_samekey_entry (struct gh_table *htab, struct gh_entry *eprev)
{
  // entry with the same key must be in the same backet
  struct gh_entry *p = eprev ? eprev->next : 0;

  for (; p; p = p->next)
    if (eprev->hcode == p->hcode &&
    htab->equals(eprev->key, eprev->keylen, p->key, p->keylen))
      return p;

  return 0;
}

/**
 * gh_insert --  insert new entry in table
 * @htab:  hash table ptr
 * @ep: ptr to gh_entry with filled .key and .keylen
 * Returns: ptr to gh_entry (@ep)
 * Notes: we do multiset, so never check is the same key in table or not
 *        advise: use strlen() for string keys length,
 *        but insert them with trailing nil (use strdup())
 */
static struct gh_entry *
gh_insert (struct gh_table *htab, struct gh_entry *ep)
{
  if (ep) {
    ep->hcode = htab->fhash(ep->key, ep->keylen);
    uint32_t i = ep->hcode % htab->capacity;
    ep->next = htab->table[i];
    htab->table[i] = ep;
    htab->size++;
  }

  return ep;
}

static inline struct gh_entry *gh_insert_data (struct gh_table *htab,
                           struct gh_entry *ep,
                           void *key,
                           uint32_t keylen,
                           void *data) {
  if (ep) {
    ep->key = key;
    ep->keylen = keylen;
    ep->data = data;
  }
  return gh_insert(htab, ep);
}

static inline struct gh_entry *gh_insert_keydup_data (struct gh_table *htab,
                              struct gh_entry *ep,
                              void *key,
                              uint32_t keylen,
                              void *data) {
  return (key = memdup(key, keylen)) ?
    gh_insert_data(htab, ep, key, keylen, data) : 0;
}

static inline struct gh_entry *gh_insert_strkeydup_data (struct gh_table *htab,
                             struct gh_entry *ep,
                             char *key,
                             void *data) {
  return (key = strdup(key)) ?
    gh_insert_data(htab, ep, key, strlen(key), data) : 0;
}

static inline struct gh_entry *gh_insert_strkey_data (struct gh_table *htab,
                              struct gh_entry *ep,
                              char *key,
                              void *data) {
  return gh_insert_data(htab, ep, key, strlen(key), data);
}

/**
 * gh_lookup --  find entry by key
 * @htab:  hash table ptr
 * @key: ptr to key
 * @keylen: key length in bytes
 * Returns: ptr to gh_entry or 0 (no such key in table)
 */
static struct gh_entry *
gh_lookup (struct gh_table *htab, const void *key, uint32_t keylen)
{
  uint32_t hcode = htab->fhash(key, keylen), i = hcode % htab->capacity;
  struct gh_entry *p = htab->table[i];

  while (p) {
    if (p->hcode == hcode
    && htab->equals(p->key, p->keylen, key, keylen))
      break;
    p = p->next;
  }

  return p;
}



/**
 * gh_remove --  find entry by key and remove it
 * @htab:  hash table ptr
 * @key: ptr to key
 * @keylen: key length in bytes
 * Returns: ptr to gh_entry or 0 (no such key in table)
 */
static struct gh_entry *
gh_remove (struct gh_table *htab, const void *key, uint32_t keylen)
{
  uint32_t hcode = htab->fhash(key, keylen), i = hcode % htab->capacity;
  struct gh_entry *pp = 0, *p = htab->table[i];

  while (p) {
    if (p->hcode == hcode
    && htab->equals(p->key, p->keylen, key, keylen)) {
      if (pp)
    pp->next = p->next;
      else
    htab->table[i] = p->next;
      htab->size--;
      break;
    }
    pp = p;
    p = p->next;
  }

  return p;
}

/**
 * gh_remove_entry --  remove entry from table
 * @htab:  hash table ptr
 * @ep: ptr to VALID gh_entry (returned by gh_first_entry() or similar)
 * Returns: ptr to this gh_entry or 0 (entry not found in table)
 */
static struct gh_entry *
gh_remove_entry (struct gh_table *htab, struct gh_entry *ep)
{
  uint32_t i = ep->hcode % htab->capacity;
  struct gh_entry *pp = 0, *p = htab->table[i];

  while (p) {
    if (p == ep) {
      if (pp)
    pp->next = ep->next;
      else
    htab->table[i] = ep->next;
      htab->size--;
      break;
    }
    pp = p->next;
    p = p->next;
  }

  return p;
}
/**
 * gh_rehash --  change table capacity
 * @htab:  hash table ptr
 * @capacity: new capacity
 * Returns: 1 or 0 (no memory, table not change)
 * Note: if (capacity == 0) capacity = (old_capacity * 3) / 2 + 1
 */
// returns 0 if no memory
static int
gh_rehash (struct gh_table *htab, int capacity)
{
  if (capacity == 0)
    capacity = (htab->capacity * 3) / 2 + 1;
  struct gh_entry **t = (typeof(t))calloc(capacity, sizeof(*t));
  if (!t)
    return 0;

  uint32_t i, j;

  for (i = 0; i < htab->capacity; i++)
    while (htab->table[i]) {
      struct gh_entry *p = htab->table[i];
      htab->table[i] = p->next;
      j = p->hcode % capacity;
      p->next = t[j];
      t[j] = p;
    }

  free(htab->table);
  htab->table = t;
  htab->capacity = capacity;
  return 1;
}


#endif