0xDEADBEEF

smallmap.d

struct SmallMap(K, V) {
  struct KV { K key; V value; }
  private ulong size;
  private KV[] arr;
  private std.bitmanip.BitArray occupied;

  this(ulong capacity = 0) {
    arr.length = occupied.length = 1L << core.bitop.bsr(capacity);
  }

  ulong length() { return size; }

  private auto find(K k) {
    auto i = hashOf(k, 1337) & (arr.length - 1);
    while (occupied[i] && arr[i].key != k) {
      i = (i + 1) & (arr.length - 1);
    }
    return i;
  }

  void opIndexAssign(V v, K k) {
    if (size >= arr.length / 2) grow();
    auto i = find(k);
    arr[i] = KV(k, v);
    if (!occupied[i]) size++;
    occupied[i] = true;
  }

  V* opIndex(K k) {
    if (arr.length == 0) return null;
    auto i = find(k);
    return !occupied[i] ? null : &arr[i].value;
  }

  private void grow() {
    auto newMap = SmallMap!(K, V)(max(32, arr.length*2));
    foreach (i, ref kv; arr) {
      if (occupied[i]) newMap[kv.key] = kv.value;
    }
    this = newMap;
  }
}