#include "hashmap.h"
#include "hashmap_impl.h"
#include <stdint.h>
#include <string.h>
#define GROUP HM_GROUP
#define HASH_MUL HM_HASH_MUL
#define EMPTY HM_EMPTY
#define DELETED HM_DELETED
static uint64_t hash_key(uint64_t key) { return key * HASH_MUL; }
static uint8_t h2_of(uint64_t hash) { return (uint8_t)(hash >> 57); }
static void set_ctrl(HashMap *m, size_t index, uint8_t ctrl) {
size_t index2 = ((index - GROUP) & (size_t)m->bucket_mask) + GROUP;
m->ctrl[index] = ctrl;
m->ctrl[index2] = ctrl;
}
static int probe_find(const HashMap *m, uint64_t key, uint64_t hash, size_t *out,
size_t *insert_slot) {
size_t mask = (size_t)m->bucket_mask;
size_t pos = (size_t)hash & mask;
size_t stride = 0;
uint8_t h2 = h2_of(hash);
int have_insert = 0;
size_t first_insert = 0;
for (;;) {
for (size_t i = 0; i < GROUP; i++) {
uint8_t c = m->ctrl[pos + i];
if (c == h2) {
size_t idx = (pos + i) & mask;
if (m->slots[idx * 2] == key) {
*out = idx;
return 1;
}
}
}
if (!have_insert) {
for (size_t i = 0; i < GROUP; i++) {
if (m->ctrl[pos + i] & 0x80u) {
first_insert = (pos + i) & mask;
have_insert = 1;
break;
}
}
}
{
int empty = 0;
for (size_t i = 0; i < GROUP; i++) {
if (m->ctrl[pos + i] == EMPTY) {
empty = 1;
break;
}
}
if (empty) {
if (insert_slot) {
*insert_slot = have_insert ? first_insert : (size_t)-1;
}
return 0;
}
}
stride += GROUP;
pos = (pos + stride) & mask;
}
}
hm_option hm_get(const HashMap *map, uint64_t key) {
hm_option o = {0, 0};
uint64_t hash = hash_key(key);
size_t idx;
if (probe_find(map, key, hash, &idx, NULL)) {
o.present = 1;
o.value = map->slots[idx * 2 + 1];
}
return o;
}
enum insert_mode {
INSERT_OVERWRITE,
INSERT_IF_ABSENT,
REPLACE_ONLY,
};
static hm_option insert_with_mode(HashMap *map, uint64_t key, uint64_t value,
enum insert_mode mode) {
hm_option o = {0, 0};
uint64_t hash = hash_key(key);
size_t idx;
size_t slot = (size_t)-1;
if (probe_find(map, key, hash, &idx, &slot)) {
o.present = 1;
o.value = map->slots[idx * 2 + 1];
if (mode != INSERT_IF_ABSENT) {
map->slots[idx * 2 + 1] = value;
}
return o;
}
if (mode == REPLACE_ONLY) {
return o;
}
if (slot == (size_t)-1) {
o.present = 2;
return o;
}
uint8_t old = map->ctrl[slot];
if (map->growth_left == 0 && old == EMPTY) {
o.present = 2;
return o;
}
if (old == EMPTY) {
map->growth_left--;
}
set_ctrl(map, slot, h2_of(hash));
map->slots[slot * 2] = key;
map->slots[slot * 2 + 1] = value;
map->items++;
return o;
}
hm_option hm_put(HashMap *map, uint64_t key, uint64_t value) {
return insert_with_mode(map, key, value, INSERT_OVERWRITE);
}
hm_option hm_put_if_absent(HashMap *map, uint64_t key, uint64_t value) {
return insert_with_mode(map, key, value, INSERT_IF_ABSENT);
}
hm_option hm_get_or_insert(HashMap *map, uint64_t key, uint64_t value) {
return insert_with_mode(map, key, value, INSERT_IF_ABSENT);
}
hm_option hm_replace(HashMap *map, uint64_t key, uint64_t value) {
return insert_with_mode(map, key, value, REPLACE_ONLY);
}
hm_option hm_remove(HashMap *map, uint64_t key) {
hm_option o = {0, 0};
uint64_t hash = hash_key(key);
size_t idx;
if (!probe_find(map, key, hash, &idx, NULL)) {
return o;
}
o.present = 1;
o.value = map->slots[idx * 2 + 1];
size_t mask = (size_t)map->bucket_mask;
size_t index_before = (idx - GROUP) & mask;
unsigned empty_before = 0;
for (size_t i = 0; i < GROUP; i++) {
if (map->ctrl[index_before + i] == EMPTY) {
empty_before |= 1u << i;
}
}
unsigned empty_after = 0;
for (size_t i = 0; i < GROUP; i++) {
if (map->ctrl[idx + i] == EMPTY) {
empty_after |= 1u << i;
}
}
unsigned lz = empty_before ? (unsigned)__builtin_clz(empty_before) - 16u : 16u;
unsigned tz = empty_after ? (unsigned)__builtin_ctz(empty_after) : 16u;
uint8_t ctrl;
if (lz + tz >= GROUP) {
ctrl = DELETED;
} else {
map->growth_left++;
ctrl = EMPTY;
}
set_ctrl(map, idx, ctrl);
map->items--;
return o;
}
uint64_t hm_contains(const HashMap *map, uint64_t key) {
size_t idx;
return (uint64_t)probe_find(map, key, hash_key(key), &idx, NULL);
}
size_t hm_len(const HashMap *map) { return (size_t)map->items; }
size_t hm_capacity(const HashMap *map) { return (size_t)map->cap_items; }
void hm_clear(HashMap *map) {
size_t ctrl_bytes = (size_t)map->bucket_mask + 1 + GROUP;
memset(map->ctrl, EMPTY, ctrl_bytes);
map->items = 0;
map->growth_left = map->cap_items;
}
uint64_t hm_iter_next(const HashMap *map, size_t *cursor, uint64_t *key,
uint64_t *value) {
size_t buckets = (size_t)map->bucket_mask + 1;
while (*cursor < buckets) {
size_t index = (*cursor)++;
if ((map->ctrl[index] & 0x80u) == 0) {
*key = map->slots[index * 2];
*value = map->slots[index * 2 + 1];
return 1;
}
}
return 0;
}