hashmap.h

Go to the documentation of this file.

 
#ifndef K
#define K void*
#endif
#ifndef V
#define V void*
#endif
#ifndef HASH_OF
#define HASH_OF(key) (size_t)key
#endif
#ifndef HASHMAP
#define HASHMAP(token) hashmap##_##token
#endif
 
#include <stddef.h>
#include <assert.h>
#include <stdbool.h>


typedef struct HASHMAP(entry_t) {
  K key;
  V value;
} HASHMAP(entry_t);

typedef struct HASHMAP(t) {
  HASHMAP(entry_t) * entries;
  size_t capacity;
  size_t num_entries;
  K nothing;
} HASHMAP(t);


HASHMAP(t) * HASHMAP(new)(size_t capacity, K nothing);

void HASHMAP(free)(HASHMAP(t) * hashmap);

void HASHMAP(put)(HASHMAP(t) * hashmap, K key, V value);

V HASHMAP(get)(HASHMAP(t) * hashmap, K key);

 
static HASHMAP(entry_t) * HASHMAP(get_ideal_address)(HASHMAP(t) * hashmap, K key) {
  HASHMAP(entry_t)* address = hashmap->entries + (HASH_OF(key) % hashmap->capacity);
  assert(address >= hashmap->entries);
  assert(address < hashmap->entries + hashmap->capacity);
  return address;
}

static HASHMAP(entry_t) * HASHMAP(get_actual_address)(HASHMAP(t) * hashmap, K key) {
  HASHMAP(entry_t)* address = HASHMAP(get_ideal_address)(hashmap, key);
  HASHMAP(entry_t)* upper_limit = hashmap->entries + hashmap->capacity;
  while ((address->key != hashmap->nothing) & (address->key != key))
    address++;
  if (address == upper_limit) {
    address = hashmap->entries;
    while ((address->key != hashmap->nothing) & (address->key != key))
      address++;
    if (address == upper_limit)
      return NULL;
  }
  assert(address->key == key || address->key == hashmap->nothing);
  return address;
}

 
HASHMAP(t) * HASHMAP(new)(size_t capacity, K nothing) {
  HASHMAP(entry_t)* entries = (HASHMAP(entry_t)*)malloc((capacity + 1) * sizeof(HASHMAP(entry_t)));
  if (!entries)
    exit(1);
  HASHMAP(t)* ret = (HASHMAP(t)*)malloc(sizeof(HASHMAP(t)));
  if (!ret)
    exit(1);
  // The entry at the end is used as a boundary. It will never again be written to.
  for (size_t i = 0; i < capacity + 1; i++) {
    entries[i].key = nothing;
  }
  ret->entries = entries;
  ret->capacity = capacity;
  ret->num_entries = 0;
  // A second nothing may be required if removal is to be supported and we want to make removal
  // a constant-time operation.
  ret->nothing = nothing;
  return ret;
}
 
void HASHMAP(free)(HASHMAP(t) * hashmap) {
  free(hashmap->entries);
  free(hashmap);
}
 
void HASHMAP(put)(HASHMAP(t) * hashmap, K key, V value) {
  assert(key != hashmap->nothing);
  HASHMAP(entry_t)* write_to = HASHMAP(get_actual_address)(hashmap, key);
  write_to->key = key;
  write_to->value = value;
}
 
V HASHMAP(get)(HASHMAP(t) * hashmap, K key) {
  assert(key != hashmap->nothing);
  HASHMAP(entry_t)* read_from = HASHMAP(get_actual_address)(hashmap, key);
  return read_from->value; // Crash the program if the key cannot be found
}