assembly-hashmap 0.1.0

A single-threaded u64→u64 hashmap with x86-64 assembly operations and Rust-side growth.
Documentation
/* Portable reference implementation of get/put/remove.
 *
 * native/hashmap.S is the real implementation; this exists so the test suite
 * can run on non-x86-64 hosts and as an executable spec to diff the assembly
 * against. The Makefile links this only when uname -m is not x86_64, so a
 * passing `make test` here says nothing about the assembly. Any change to the
 * algorithm must be made in both files. */

#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;
    /* __builtin_clz on 32-bit: empty_before fits in 16 bits, clz has 16 extra. */
    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;
}