Skip to content

Instantly share code, notes, and snippets.

@RobertDurfee

RobertDurfee/hashmap.h

Last active October 15, 2020 12:43
Show Gist options
  • Save RobertDurfee/ac78044f70ac03360bad7107a6d6c3b5 to your computer and use it in GitHub Desktop.
Save RobertDurfee/ac78044f70ac03360bad7107a6d6c3b5 to your computer and use it in GitHub Desktop.
Download ZIP
A simple, generic, dynamic hashmap implementation with linear probing in C.
Raw
hashmap.h
#ifndef MAP_H
#define MAP_H
#include <stdint.h> // uint8_t, uint32_t
#include <stdlib.h> // size_t, calloc, free
#include <stdbool.h> // bool
#include <assert.h> // assert
#include <stdio.h> // printf
#define TOKENPASTE(X, Y) X ## Y
#define INDENT(DEPTH) printf("%*c", DEPTH * 2, ' ')
#define MAP_ELEM(MAP) TOKENPASTE(MAP, Elem)
#define MAP_CONS(MAP) TOKENPASTE(MAP, Cons)
#define MAP_CONTAINS_KEY(MAP) TOKENPASTE(MAP, ContainsKey)
#define MAP_REPLACE(MAP) TOKENPASTE(MAP, Replace)
#define MAP_EXPAND(MAP) TOKENPASTE(MAP, Expand)
#define MAP_INSERT(MAP) TOKENPASTE(MAP, Insert)
#define MAP_GET(MAP) TOKENPASTE(MAP, Get)
#define MAP_EQUALS(MAP) TOKENPASTE(MAP, Equals)
#define MAP_DEBUG(MAP) TOKENPASTE(MAP, Debug)
#define MAP_DES(MAP) TOKENPASTE(MAP, Des)
#define MAP_ELEM_UNUSED 0
#define MAP_ELEM_OCCUPIED 1
#define MAP_GEN_DECL(MAP, KEY, VALUE) \
\
struct MAP_ELEM(MAP) { \
uint8_t type; \
KEY key; \
VALUE value; \
}; \
\
struct MAP { \
struct MAP_ELEM(MAP) *elems; \
size_t capacity; \
size_t len; \
}; \
\
struct MAP *MAP_CONS(MAP)(struct MAP *map, size_t capacity); \
\
bool MAP_CONTAINS_KEY(MAP)(const struct MAP *map, KEY key); \
\
void MAP_REPLACE(MAP)(struct MAP *map, KEY key, VALUE value); \
\
void MAP_EXPAND(MAP)(struct MAP *map); \
\
void MAP_INSERT(MAP)(struct MAP *map, KEY key, VALUE value); \
\
VALUE MAP_GET(MAP)(struct MAP *map, KEY key); \
\
bool MAP_EQUALS(MAP)(const struct MAP *a, const struct MAP *b); \
\
void MAP_DEBUG(MAP)(const struct MAP *map, uint32_t depth); \
\
struct MAP *MAP_DES(MAP)(struct MAP *map);
#define MAP_GEN_DEF(MAP, KEY, VALUE, KEY_HASH, KEY_EQUALS, KEY_DEBUG, KEY_DES, VALUE_EQUALS, VALUE_DEBUG, VALUE_DES) \
\
struct MAP *MAP_CONS(MAP)(struct MAP *map, size_t capacity) { \
map->elems = (struct MAP_ELEM(MAP) *)calloc(capacity, sizeof(struct MAP_ELEM(MAP))); \
map->capacity = capacity; \
map->len = 0; \
return map; \
} \
\
bool MAP_CONTAINS_KEY(MAP)(const struct MAP *map, KEY key) { \
size_t hash, i; \
hash = (KEY_HASH(key) % map->capacity) - 1; \
for (i = 0; i < map->capacity; i++) { \
hash = (hash + 1) % map->capacity; \
if (map->elems[hash].type == MAP_ELEM_OCCUPIED && KEY_EQUALS(map->elems[hash].key, key)) { \
return true; \
} else if (map->elems[hash].type == MAP_ELEM_UNUSED) { \
return false; \
} \
} \
return false; \
} \
\
void MAP_REPLACE(MAP)(struct MAP *map, KEY key, VALUE value) { \
size_t hash, i; \
hash = (KEY_HASH(key) % map->capacity) - 1; \
for (i = 0; i < map->capacity; i++) { \
hash = (hash + 1) % map->capacity; \
if (map->elems[hash].type == MAP_ELEM_OCCUPIED && KEY_EQUALS(map->elems[hash].key, key)) { \
map->elems[hash].value = value; \
return; \
} else if (map->elems[hash].type == MAP_ELEM_UNUSED) { \
assert(false && "key does not exist"); \
} \
} \
assert(false && "key does not exist"); \
} \
\
void MAP_EXPAND(MAP)(struct MAP *map) { \
struct MAP_ELEM(MAP) *elems; \
size_t i, j, hash; \
elems = (struct MAP_ELEM(MAP) *)calloc(map->capacity * 2, sizeof(struct MAP_ELEM(MAP))); \
for (i = 0; i < map->capacity; i++) { \
if (map->elems[i].type == MAP_ELEM_OCCUPIED) { \
hash = (KEY_HASH(map->elems[i].key) % (map->capacity * 2)) - 1; \
for (j = 0; j < map->capacity * 2; j++) { \
hash = (hash + 1) % (map->capacity * 2); \
if (elems[hash].type == MAP_ELEM_UNUSED) { \
elems[hash].type = MAP_ELEM_OCCUPIED; \
elems[hash].key = map->elems[i].key; \
elems[hash].value = map->elems[i].value; \
break; \
} \
} \
assert((j < map->capacity * 2) && "key not inserted"); \
} \
} \
free(map->elems); \
map->elems = elems; \
map->capacity *= 2; \
} \
\
void MAP_INSERT(MAP)(struct MAP *map, KEY key, VALUE value) { \
size_t hash, i; \
hash = (KEY_HASH(key) % map->capacity) - 1; \
for (i = 0; i < map->capacity; i++) { \
hash = (hash + 1) % map->capacity; \
if (map->elems[hash].type == MAP_ELEM_OCCUPIED && KEY_EQUALS(map->elems[hash].key, key)) { \
assert(false && "key exists"); \
} else if (map->elems[hash].type == MAP_ELEM_UNUSED) { \
map->elems[hash].type = MAP_ELEM_OCCUPIED; \
map->elems[hash].key = key; \
map->elems[hash].value = value; \
map->len++; \
break; \
} \
} \
assert((i < map->capacity) && "key not inserted"); \
if (3 * map->len > 2 * map->capacity) { \
MAP_EXPAND(MAP)(map); \
} \
} \
\
VALUE MAP_GET(MAP)(struct MAP *map, KEY key) { \
size_t hash, i; \
hash = (KEY_HASH(key) % map->capacity) - 1; \
for (i = 0; i < map->capacity; i++) { \
hash = (hash + 1) % map->capacity; \
if (map->elems[hash].type == MAP_ELEM_OCCUPIED && KEY_EQUALS(map->elems[hash].key, key)) { \
return map->elems[hash].value; \
} else if (map->elems[hash].type == MAP_ELEM_UNUSED) { \
assert(false && "key does not exist"); \
} \
} \
assert(false && "key does not exist"); \
} \
\
bool MAP_EQUALS(MAP)(const struct MAP *a, const struct MAP *b) { \
size_t i; \
if (a->len != b->len) { \
return false; \
} \
for (i = 0; i < a->capacity; i++) { \
if (a->elems[i].type == MAP_ELEM_OCCUPIED) { \
if (!MAP_CONTAINS_KEY(MAP)(b, a->elems[i].key)) { \
return false; \
} \
if (!VALUE_EQUALS(a->elems[i].value, MAP_GET(MAP)((struct MAP *)b, a->elems[i].key))) { \
return false; \
} \
} \
} \
return true; \
} \
\
void MAP_DEBUG(MAP)(const struct MAP *map, uint32_t depth) { \
size_t i; \
printf(#MAP " {\n"); \
for (i = 0; i < map->capacity; i++) { \
if (map->elems[i].type == MAP_ELEM_OCCUPIED) { \
INDENT(depth); printf(" "); KEY_DEBUG(map->elems[i].key, depth + 1); printf(": "); VALUE_DEBUG(map->elems[i].value, depth + 1); printf(",\n"); \
} \
} \
INDENT(depth); printf("}"); \
} \
\
struct MAP *MAP_DES(MAP)(struct MAP *map) { \
size_t i; \
for (i = 0; i < map->capacity; i++) { \
if (map->elems[i].type == MAP_ELEM_OCCUPIED) { \
KEY_DES(map->elems[i].key); \
VALUE_DES(map->elems[i].value); \
} \
} \
free(map->elems); \
map->capacity = 0; \
map->len = 0; \
return map; \
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment