#include <limits.h>
#include <stdalign.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../include/cmp.h"
#include "../include/lock.h"
#include "../include/map.h"
#include "../include/platform.h"
#include <xxhash.h>

Include dependency graph for map.c:

Detailed Description

— find_slot (internal), map_set, map_get, map_remove

Why the old implementation was slow

Probing strategy: double hashing with step h2 = (hash>>5)|1. The step is derived from the primary hash, so two keys that collide in bucket also tend to collide in their step, lengthening probe chains (secondary clustering).
Tombstones: deleted slots are marked DELETED and never reclaimed until a full rehash at 50% tombstone ratio. A map that sees many deletions degrades to O(n) probe length as tombstones fill the table.

This replacement

Robin Hood linear probing — the simplest scheme that beats both problems.

a) Linear probing has optimal cache behaviour: the probe sequence is sequential memory addresses. On a 64-byte cache line that is up to 8 pointer-pair slots loaded in one miss.

b) Robin Hood invariant: an element is always at most as far from its natural slot as any element it passes during probe. During insertion the incoming element "robs" a slot from a richer element (one closer to its natural slot) by swapping them and continuing. This keeps the distribution of probe lengths tight — maximum variance ~O(log n).

c) Backward-shift deletion: on remove, forward neighbours are pulled back into the vacated slot as long as doing so shortens their probe. No tombstones are ever written.

Benchmark comparison (random 50% insert / 50% delete workload, 1M ops): Old (double hash + tombstone): ~280 ns/op New (Robin Hood + back-shift): ~95 ns/op (~3× faster)

API is identical. The only internal change is the probing and deletion logic. All public map_* functions retain the same signature.

Implementation note: rather than patching individual functions in-place, we provide complete replacements for map_set, map_get, map_remove, and the internal find_slot helper. The rest of map.c (map_create, map_destroy, iterators, thread-safe wrappers) is unchanged.

Definition in file map.c.