path: root/src/hashtable.c

/**
 * C hashtable implementation
 *
 * Copyright (C) 2021 Wojtek Kosior
 * Redistribution terms are gathered in the `copyright' file.
 */

/*
 * GENERAL INFO
 *
 * You might want to read the beginning of hashtable.h first.
 *
 * In some places "rehashing" and in other ones "resizing" seemed to
 * be the right word to use. They mean more or less the same.
 *
 * Functions starting with ht_ are part of the API. Internal functions
 * are declared static. I also made some of them inline (either
 * because they were extremely short or only called from 1 place).
 *
 * Hashtable size is always a power of 2.
 *
 * When the hashtable is ¾ full, a new, 2x bigger table is allocated
 * and whenever one of 4 basic operations (adding, removing, setting,
 * getting) occurs, 4 slots are being rehashed from old table into 8
 * slots in new table. Similarly, when hashtable is ¼ full, a new,
 * 2x smaller table is allocated and each of subsequent operations
 * rehashes 8 entries from old table into 4 in new table.
 * This mechanism has been made lazier: getting and removing don't
 * trigger growing of ht even if it's 3/4 full. Similarly, getting,
 * setting and adding don't trigger shrinking.
 * Once resizing is triggered, however, any of the operations will
 * contribute to rehashing. Even if, for example, the operation is
 * ADD and the table is being shrinked.
 * This means, that if we have a hashtable of size n which is ¾ full
 * and growing is triggered, then each subsequent call to
 * ht_{add,rem,get,set}() rehashes some entries and, depending on
 * how frequently and how successfully each of these 4 funcs was
 * called, at the end of resizing we get a size 2n hashtable which is
 * between ¼ and ½ full. Similarly, if shrinking of a ¼ full
 * hashtable of size n is triggered, then after some operations we
 * get a size ½n hashtable, that is somewhere between ¼ and ¾ full.
 * One can see now, that we always keep the hashtable between ¼ and ¾
 * full (with the exception of a minimal size one, that can be empty).
 */

#include "hashtable.h"

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stdbool.h>

#ifdef _USE_INLINE
#define INLINE inline
#else
#define INLINE
#endif

/*
 * We won't shrink hashtable below this size. Newly created one will
 * be this big.
 */
#define MIN_SIZE 4

/* Special value of ht->rehashing_position. */
#define NOT_REHASHING ((ssize_t) -1)

/*
 * Those are possible return values of do_resizing_related_stuff()
 * and rehash_some_entries() (which only returns the first 2).
 */
#define REHASHING_IN_PROGRESS     0
#define REHASHING_NOT_IN_PROGRESS 1
#define REHASHING_NO_MEM          2

/* Struct used to store a pair. */
struct ht_node
{
  const void *key;
  const void *val;
  struct ht_node *next;
};

enum op
  {
    GET,
    GET_THREADSAFE,
    ADD,
    SET,
    REM,
  };

int ht_init(hashtable_t *ht,
	    size_t (*hash)(const void *key),
	    int (*cmp)(const void *key1, const void *key2))
{
  if (!(ht->tab = calloc(MIN_SIZE, sizeof(struct ht_node**))))
    return HT_NO_MEM;

  ht->tab_size = MIN_SIZE;
  ht->rehashing_position = NOT_REHASHING;
  ht->entries = 0;
  ht->hashfunc = hash;
  ht->cmpfunc = cmp;

  return HT_OK;
}

/* First come some utilities :) */

static INLINE size_t min(size_t n1, size_t n2)
{
  return n1 < n2 ? n1 : n2;
}

static INLINE size_t hash2(size_t n)
{
  /* I found this "hash improver" on the internet. */
  n ^= (n >> 20) ^ (n >> 12);
  return n ^ (n >> 7) ^ (n >> 4);
}

/* Below are 2 list-handling utility functions. */
static INLINE struct ht_node *join_lists(struct ht_node *l1,
					 struct ht_node *l2)
{
  if (!l1) return l2;
  if (!l2) return l1;

  struct ht_node *l1_last;

  for (l1_last = l1; l1_last->next; l1_last = l1_last->next);

  /* Append l2 to the end of l1. */
  l1_last->next = l2;

  /* For convenience return the first element of the resulting list. */
  return l1;
}


static INLINE void push(struct ht_node *node, struct ht_node **list)
{
  node->next = *list;
  *list = node;
}

/*
 * The following 2 rehash_* functions are helpers of rehash_some_entries().
 * This func rehashes 1 chain of entries in tab[] into 2 chains in newtab[].
 */
static INLINE void rehash_position_growing(hashtable_t *ht)
{
  /* There are 2 possible new positions of an entry in a 2x bigger ht. */
  struct ht_node *list0 = NULL, *list1 = NULL;

  size_t old_position = ht->rehashing_position,
    new_position0 = old_position,
    new_position1 = old_position | ht->tab_size;

  struct ht_node *pair = ht->tab[old_position], *next_pair;

  while (pair)
    {
      next_pair = pair->next;

      size_t new_position = hash2(ht->hashfunc(pair->key))
	& (ht->new_size - 1);

      push(pair, new_position == new_position1 ? &list1 : &list0);

      pair = next_pair;
    }

  ht->newtab[new_position0] = list0;
  ht->newtab[new_position1] = list1;

  ht->rehashing_position++;
}

/* This func rehashes 2 chains of entries in tab[] into 1 chain in newtab[]. */
static INLINE void rehash_2positions_shrinking(hashtable_t *ht)
{
  size_t new_position = ht->rehashing_position,
    old_position0 = new_position,
    old_position1 = new_position | ht->new_size;

  ht->newtab[new_position] = join_lists(ht->tab[old_position0],
					ht->tab[old_position1]);

  ht->rehashing_position++;
}

/*
 * Rehashes 4(8) positions from tab to newtab. If those were the last
 * enetries to rehash, the function takes care of everything
 * (like deallocating old tab) and returns REHASHING_NOT_IN_PROGRESS.
 * Otherwise, returns REHASHING_IN_PROGRESS.
 * Caller must make sure rehashing was started b4 calling this func.
 */
static int rehash_some_entries(hashtable_t *ht)
{
  int rehashes_left = 4;

  if (ht->new_size > ht->tab_size)                    /* growing ht */
    {
      while(rehashes_left--) rehash_position_growing(ht);
      if (ht->rehashing_position != ht->tab_size)
	return REHASHING_IN_PROGRESS;
    }
  else                                                /* shrinking ht */
    {
      while(rehashes_left--) rehash_2positions_shrinking(ht);
      if (ht->rehashing_position != ht->new_size)
	return REHASHING_IN_PROGRESS;
    }

  /* rehashing finishes */
  ht->rehashing_position = NOT_REHASHING;
  ht->tab_size = ht->new_size;
  free(ht->tab);
  ht->tab = ht->newtab;

  return REHASHING_NOT_IN_PROGRESS;
}

static INLINE bool resizing_taking_place(hashtable_t *ht)
{
  return !(ht->rehashing_position == NOT_REHASHING);
}

void ht_finish_resizing(hashtable_t *ht)
{
  if (resizing_taking_place(ht))
    while (rehash_some_entries(ht) == REHASHING_IN_PROGRESS);
}

static INLINE bool needs_growing(hashtable_t *ht)
{
  return ht->entries >= 3 * ht->tab_size / 4;
}

static INLINE bool needs_shrinking(hashtable_t *ht)
{
  return ht->tab_size > MIN_SIZE
    && ht->entries <= ht->tab_size / 4;
}
/*
 * Each of hashtable operations (add, set, rem, get) should also
 * attempt to do part of resizing. This way resizing operation
 * which is O(n) is distributed among many hashtable accesses
 * each of them still being O(1). Without this the the amortized
 * complexity of ht accesses would still be O(1), but a single access
 * would sometimes be O(n).
 * Other function that adds, sets, gets or removes sth from ht uses
 * this one to do this "part of resizing" mentioned above.
 * This func returns REHASHING_NO_MEM on failed malloc (won't happen
 * for GET or REM operation) and REHASHING_[NOT_]IN_PROGRESS otherwise.
 */
static INLINE int
do_resizing_related_stuff(hashtable_t *ht, const void *key, enum op op)
{
  bool resizing = resizing_taking_place(ht);

  if (!resizing)
    {
      size_t new_size;

      switch (op)
	{
	case GET:
	  goto dont_start_resizing;
	case ADD:
	case SET:
	  if (needs_growing(ht))
	    new_size = ht->tab_size * 2;
	  else
	    goto dont_start_resizing;
	  break;
	default: /* case REM */
	  if (needs_shrinking(ht))
	    new_size = ht->tab_size / 2;
	  else
	    goto dont_start_resizing;
	}

      struct ht_node **newtab;
      if (!(newtab = malloc(new_size * sizeof(struct ht_node*))))
	return op == REM ? REHASHING_NOT_IN_PROGRESS : REHASHING_NO_MEM;

      ht->newtab = newtab;
      ht->new_size = new_size;
      ht->rehashing_position = 0;

      resizing = true;
    }

 dont_start_resizing:

  return resizing ?
    rehash_some_entries(ht) : REHASHING_NOT_IN_PROGRESS;
}

/*
 * This is a chaining hashtable, so each element in the array (table)
 * is actually a list of entries. All operations (adding, removing,
 * etc.) need to find the right list of entries (here called "bucket")
 * for a given key first, so it makes sense to do it in a separate
 * function. The bucket may be in tab or newtab if resizing is taking
 * place. Being informed by the caller if resizing is in progress,
 * this func does not need to check for it by itself.
 */
static INLINE struct ht_node **find_bucket(hashtable_t *ht, const void *key,
					   bool resizing_in_progress)
{
  size_t hash = hash2(ht->hashfunc(key)),
    destination_tab_size, position;

  struct ht_node **destination_tab;

  if (resizing_in_progress)
    /*
     * Here we must check whether our key's bucket is still
     * in ht->tab or already rehashed to ht->newtab.
     */
    {
      size_t smaller_tab_size = min(ht->tab_size, ht->new_size),
	smaller_tab_position = hash & (smaller_tab_size - 1);

      if (smaller_tab_position < ht->rehashing_position)
	{
	  destination_tab = ht->newtab;
	  destination_tab_size = ht->new_size;
	}
      else
	{
	  destination_tab = ht->tab;
	  destination_tab_size = ht->tab_size;
	}
    }
  else
    /* In this case we know, we're working on ht->tab and not newtab. */
    {
      destination_tab = ht->tab;
      destination_tab_size = ht->tab_size;
    }

  position = hash & (destination_tab_size - 1);
  return &destination_tab[position];
}

/*
 * Operations of adding, removing, etc. all work on list of entries
 * (bucket) to wchich key hashes and they have some common logic, so
 * it made sense to make a single function, that does the right
 * operation based on an enum passed to it.
 */
static INLINE int
perform_operation_on_bucket(hashtable_t *ht, struct ht_node **bucket,
			    const void *key, const void *val,
			    void **keyptr, void **valptr,
			    enum op op)
{
  struct ht_node **pairptr, *pair;

  for (pairptr = bucket, pair = *pairptr;
       pair;
       pairptr = &pair->next, pair = pair->next)

    if (!ht->cmpfunc(key, pair->key))
      {
	if (op == ADD)
	  return HT_KEY_PRESENT;

	if (keyptr) *keyptr = (void*) pair->key;
	if (valptr) *valptr = (void*) pair->val;

	switch (op)
	  {
	  case GET:
	  case GET_THREADSAFE:
	    {
	      return HT_OK;
	    }
	  case SET:
	    {
	      pair->key = key;
	      pair->val = val;
	      return HT_OK;
	    }
	  default: /* case REM */
	    {
	      *pairptr = pair->next;
	      free(pair);
	      ht->entries--;
	      return HT_OK;
	    }
	  }
      }

  if (op == GET || op == GET_THREADSAFE || op == REM)
    return HT_KEY_ABSENT;

  /* op == ADD || op == SET */

  struct ht_node *new_pair = malloc(sizeof(struct ht_node));
  if (!new_pair)
    return HT_NO_MEM;

  *new_pair = (struct ht_node) {.key = key, .val = val};
  push(new_pair, bucket);
  ht->entries++;

  return HT_OK;
}

/* Generic function for performing of adding, removing, setting and getting. */
static int perform_operation(hashtable_t *ht, const void *key, const void *val,
			     void **keyptr, void **valptr, enum op op)
{
  bool resizing_in_progress;

  if (op == GET_THREADSAFE) {
    resizing_in_progress = resizing_taking_place(ht);
    goto skip_resizing;
  }

  switch (do_resizing_related_stuff(ht, key, op))
    {
    case REHASHING_IN_PROGRESS:
      resizing_in_progress = true;
      break;
    case REHASHING_NOT_IN_PROGRESS:
      resizing_in_progress = false;
      break;
    default: /* case REHASHING_NO_MEM */
      return HT_NO_MEM;
    }

  struct ht_node **bucket;

 skip_resizing:
  bucket = find_bucket(ht, key, resizing_in_progress);

  return perform_operation_on_bucket(ht, bucket, key, val,
				     keyptr, valptr, op);
}

/* The 5 functions below are the main part of the API. */
int ht_get(hashtable_t *ht, const void *key,
	   void **storedkey, void **val)
{
  return perform_operation(ht, key, NULL, storedkey, val, GET);
}

int ht_get_threadsafe(hashtable_t *ht, const void *key,
		      void **storedkey, void **val)
{
  return perform_operation(ht, key, NULL, storedkey, val,
			   GET_THREADSAFE);
}

int ht_add(hashtable_t *ht, const void *key, const void *val)
{
  return perform_operation(ht, key, val, NULL, NULL, ADD);
}

int ht_set(hashtable_t *ht, const void *key, const void *val,
	   void **oldkey, void **oldval)
{
  return perform_operation(ht, key, val, oldkey, oldval, SET);
}

int ht_rem(hashtable_t *ht, const void *key,
	   void **storedkey, void **val)
{
  return perform_operation(ht, key, NULL, storedkey, val, REM);
}

/*
 * As mentioned in hashtable.h, this func does not deallocate keys
 * nor vals. One could use ht_map_destroy() if that is needed.
 */
void ht_destroy(hashtable_t *ht)
{
  ssize_t position;

  if (!ht->entries)
    goto free_tab;

  ht_finish_resizing(ht);

  struct ht_node **tab = ht->tab;

  for (position = ht->tab_size - 1; position >= 0; position--)
    {
      struct ht_node *pair = tab[position], *nextpair;

      while (pair)
	{
	  nextpair = pair->next;
	  free(pair);
	  pair = nextpair;
	}
    }

 free_tab:
  free(ht->tab);
}

void ht_map(hashtable_t *ht, void *arg,
	    void (*mapfunc)(const void *key, void *val, void *arg))
{
  ssize_t position;

  if (!ht->entries)
    return;

  ht_finish_resizing(ht);

  struct ht_node **tab = ht->tab, *pair;

  for (position = ht->tab_size - 1; position >= 0; position--)
    {
      for (pair = tab[position]; pair; pair = pair->next)
	mapfunc(pair->key, (void*) pair->val, arg);
    }
}

void ht_map_destroy(hashtable_t *ht, void *arg,
		    void (*mapfunc)(void *key, void *val, void *arg))
{
  /*
   * If mapfunc() deallocates keys, the following 2 lines make
   * assumption on ht_destroy(), that it doesn't call ht->hashfunc()
   * or ht->cmpfunc() on keys.
   */
  ht_map(ht, arg, (void (*)(const void*, void*, void*)) mapfunc);
  ht_destroy(ht);
}

/*
 * These 2 functions are for easy making of hashtable with strings as
 * keys. Note that this hash is *not* secure against DoS attacks.
 */
size_t ht_string_hash(const char *key)
{
  size_t i = 0, hash = (size_t) 0xa1bad2dead3beef4;

  do
    {
      char shift = ((unsigned char) key[i]) % sizeof(size_t);
      hash += ((hash >> shift) | (hash << (sizeof(size_t) - shift)))
	^ key[i];
    }
  while (key[i++]);

  return hash;
}

int ht_string_init(hashtable_t *ht)
{
  return ht_init(ht, (size_t (*)(const void*)) &ht_string_hash,
		 (int (*)(const void*, const void*)) &strcmp);
}