2 of 1; half a nybble of another

Originally published on the old depletionmode / 2of1 blog (archived copy).

Here’s some code for a simple C hashtable.

The hashtable uses *char ** for keys, allows any type of data to be stored, allows for an arbitrary size and uses linked-lists for collision handling.

hash.h
(Download here)

listing text

/* simple hashtable
 * David Kaplan <david[at]2of1.org>, 2011
 *
 * mem = (16 + 8 * size + 24 * entries) bytes [64-bit]
 * mem = (8 + 4 * size + 12 * entries) bytes [32-bit]
 *
 * some sizes for reference [64-bit]
 * 2^8  = 16K [probably too small - depending on use]
 * 2^16 = 512K [even bigger would be better]
 * 2^24 = 128MB [probably a bit too much]
 * 2^32 = 32GB [whooooa! watch that heap space!]
 *
 * the hashtable uses basic linked-lists for handling collisions
 */
 
#define HT_MAX_KEYLEN 50
 
struct ht_node {
  void *val;
  char *key;
  struct ht_node *nxt;
};
 
typedef struct ht {
  struct ht_node **tbl;
  int size;
} HT;
 
HT *ht_create(int size);                    /* allocate hashtable mem */
void ht_destroy(HT *ht);                    /* free hashtable mem */
void *ht_get(HT *ht, char *key);            /* retrieve entry */
void ht_put(HT *ht, char *key, void *val);  /* store entry */
void ht_remove(HT *ht, char *key);          /* remove entry */

hash.c
(Download here)

listing text

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
#include <string.h>
 
#include "hash.h"
 
unsigned long _hash(char *key)
{
  /* djb2 */
  unsigned long hash = 5381;
  int c;
 
  while (c = *key++)
    hash = ((hash << 5) + hash) + c;
 
  return hash;
}
 
HT *ht_create(int size)
{
  HT *ht = malloc(sizeof(HT));
 
  ht->size = size;
 
  ht->tbl = calloc(1, size * sizeof(struct ht_node *));
 
  return ht;
}
 
void ht_destroy(HT *ht)
{
  if (!ht) return;
 
  int i;
  for (i = 0; i < ht->size; i++) {
    struct ht_node *n = ht->tbl[i];
    while (n) {
      struct ht_node *n_old = n;
 
      n = n->nxt;
 
      free(n_old->key);
      n_old->key = NULL;
      free(n_old);
      n_old = NULL;
    }
  }
 
  free(ht->tbl);
  free(ht);
 
  ht = NULL;
}
 
void *ht_get(HT *ht, char *key)
{
  if (!ht) return NULL;
 
  unsigned long idx = _hash(key) % ht->size;
 
  struct ht_node *n = ht->tbl[idx];
  while (n) {
    if (strncmp(key, n->key, HT_MAX_KEYLEN) == 0)
      return n->val;
 
    n = n->nxt;
  }
 
  return NULL;
}
 
void ht_put(HT *ht, char *key, void *val)
{
  if (!ht) return;
 
  unsigned long idx = _hash(key) % ht->size;
 
  struct ht_node *n_new = calloc(1, sizeof(struct ht_node));
  n_new->val = val;
  n_new->key = calloc(1, strnlen(key, HT_MAX_KEYLEN) + 1);
  strcpy(n_new->key, key);
 
  n_new->nxt = ht->tbl[idx];
  ht->tbl[idx] = n_new;
}
 
void ht_remove(HT *ht, char *key)
{
  if (!ht) return;
 
  unsigned long idx = _hash(key) % ht->size;
 
  struct ht_node *p = NULL, *n = ht->tbl[idx];
  while (n) {
    if (strncmp(key, n->key, HT_MAX_KEYLEN) == 0) {
      if (p)
        p->nxt = n->nxt;
 
      free (n->key);
      n->key = NULL;
 
      if (ht->tbl[idx] == n)
        ht->tbl[idx] = NULL;
 
      free (n);
      n = NULL;
 
      break;
    }
 
    p = n;
    n = n->nxt;
  }
}