OpenHashMap

Hash table/map with in-place open-addressing, storing keys of type K and values of type V.

Keys are immutable except for when they are classes in which case they are head-const (through bin reinterpretation to KeyValueType), This can be overridden by setting keyEqualPred to, for instance, a == b for class keys.

Uses quadratic probing (using triangular numbers) unless usePrimeCapacity in which case a simpler probing is used.

Deletion/Removal of elements is lazy via the bitmap _holesPtr or through assignment of of reserved value of KeyType when KeyType has hole-support via trait isHoleable.

Element iteration via - either byKey, byValue or byKeyValue over OpenHashMap and - byElement over OpenHashset respects taking the container argument either as an l-value or r-value using detected using auto ref-qualified parameter introspected using (__traits(isRef, y)). In the r-value case no reference counting is needed. In the l-value case setting borrowChecked to true adds run-time support for dynamic Rust-style ownership and borrowing between the range and the container.

@safe

struct OpenHashMap (

K

V = void

alias hasher = hashOf

string keyEqualPred = defaultKeyEqualPredOf!(K)

alias Allocator = Mallocator.instance

bool borrowChecked = false

bool useSmallLinearSearch = true

bool usePrimeCapacity = false

) if (

isNullable!K

) {

import core.exception : onOutOfMemoryError;;

import core.internal.traits : hasElaborateDestructor, Unqual;;

import core.internal.traits : hasElaborateDestructor, Unqual;;

import core.lifetime : move;;

import std.traits : hasIndirections, hasFunctionAttributes;;

import std.traits : hasIndirections, hasFunctionAttributes;;

import std.typecons : Nullable;;

template defaultNullKeyConstantOf(T) via import nxt.nullable_traits : defaultNullKeyConstantOf, isNull, nullify;;

bool isNull(T x) via import nxt.nullable_traits : defaultNullKeyConstantOf, isNull, nullify;;

void nullify(T x) via import nxt.nullable_traits : defaultNullKeyConstantOf, isNull, nullify;;

template mustAddGCRange(T) via import nxt.container_traits : mustAddGCRange;;

void gc_addRange(void* p, size_t sz, TypeInfo ti) via import nxt.qcmeman : gc_addRange, gc_removeRange;;

void gc_removeRange(void* p) via import nxt.qcmeman : gc_addRange, gc_removeRange;;

struct PrimeIndex via import nxt.prime_modulo : PrimeIndex, ceilingPrime, moduloPrimeIndex;;

size_t ceilingPrime(size_t value, PrimeIndex primeIndex) via import nxt.prime_modulo : PrimeIndex, ceilingPrime, moduloPrimeIndex;;

size_t moduloPrimeIndex(size_t value, PrimeIndex primeIndex) via import nxt.prime_modulo : PrimeIndex, ceilingPrime, moduloPrimeIndex;;

import std.math.algebraic : nextPow2;;

import std.math : nextPow2;;

size_t triangularProbeFromIndex(T[] haystack, size_t index) via import nxt.probing : triangularProbeFromIndex, triangularProbeFromIndexIncludingHoles, triangularProbeCountFromIndex;;

size_t triangularProbeFromIndexIncludingHoles(T[] haystack, size_t index, size_t holeIndex) via import nxt.probing : triangularProbeFromIndex, triangularProbeFromIndexIncludingHoles, triangularProbeCountFromIndex;;

size_t triangularProbeCountFromIndex(T[] haystack, size_t index) via import nxt.probing : triangularProbeFromIndex, triangularProbeFromIndexIncludingHoles, triangularProbeCountFromIndex;;

static if(!(usePrimeCapacity))

enum bool assumeNonFullHaystack;

import std.functional : binaryFun;;

alias keyEqualPredFn = binaryFun!keyEqualPred;

alias keyEqualPredFn = keyEqualPred;

alias StoreK = void*;

import std.traits : isPointer;;

alias StoreK = void*;

alias StoreK = K;

enum isBorrowChecked;

enum hasAddressLikeKey;

static if(hasAddressLikeKey)

enum hasHoleableKey;

static if(hasAddressLikeKey)

enum holeKeyOffset;

static if(hasAddressLikeKey)

enum holeKeyAddress;

static if(hasAddressLikeKey)

static K holeKeyConstant();

static if(hasAddressLikeKey)

static bool isHoleKeyConstant(K key);

static if(!(hasAddressLikeKey))

static if(isHoleable!K)

enum hasHoleableKey;

static if(!(hasAddressLikeKey))
static if(isHoleable!K)

static K holeKeyConstant();

static if(!(hasAddressLikeKey))
static if(isHoleable!K)

static bool isHoleKeyConstant(K key);

alias Nullifier = typeof(K.init.nullifier);

static if(!(hasAddressLikeKey))

static if(!(isHoleable!K))

static if(__traits(hasMember, K, "nullifier"))

static if(isHoleable!Nullifier)

enum hasHoleableKey;

static if(!(hasAddressLikeKey))
static if(!(isHoleable!K))
static if(__traits(hasMember, K, "nullifier"))
static if(isHoleable!Nullifier)

static K holeKeyConstant();

static if(!(hasAddressLikeKey))
static if(!(isHoleable!K))
static if(__traits(hasMember, K, "nullifier"))
static if(isHoleable!Nullifier)

static bool isHoleKeyConstant(K key);

static if(!(hasAddressLikeKey))

static if(!(isHoleable!K))

static if(__traits(hasMember, K, "nullifier"))

static if(!(isHoleable!Nullifier))

enum hasHoleableKey;

import core.bitop : bts, bt, btr;;

import core.bitop : bts, bt, btr;;

import core.bitop : bts, bt, btr;;

size_t* makeUninitializedBitArray(size_t bitCount) via import nxt.array_help : makeUninitializedBitArray, makeZeroedBitArray, makeReallocatedBitArrayZeroPadded;;

size_t* makeZeroedBitArray(size_t bitCount) via import nxt.array_help : makeUninitializedBitArray, makeZeroedBitArray, makeReallocatedBitArrayZeroPadded;;

size_t* makeReallocatedBitArrayZeroPadded(size_t* input, size_t currentBitCount, size_t newBitCount) via import nxt.array_help : makeUninitializedBitArray, makeZeroedBitArray, makeReallocatedBitArrayZeroPadded;;

static if(!(hasAddressLikeKey))

static if(!(isHoleable!K))

static if(!(__traits(hasMember, K, "nullifier")))

enum hasHoleableKey;

import core.bitop : bts, bt, btr;;

import core.bitop : bts, bt, btr;;

import core.bitop : bts, bt, btr;;

size_t* makeUninitializedBitArray(size_t bitCount) via import nxt.array_help : makeUninitializedBitArray, makeZeroedBitArray, makeReallocatedBitArrayZeroPadded;;

size_t* makeZeroedBitArray(size_t bitCount) via import nxt.array_help : makeUninitializedBitArray, makeZeroedBitArray, makeReallocatedBitArrayZeroPadded;;

size_t* makeReallocatedBitArrayZeroPadded(size_t* input, size_t currentBitCount, size_t newBitCount) via import nxt.array_help : makeUninitializedBitArray, makeZeroedBitArray, makeReallocatedBitArrayZeroPadded;;

enum InsertionStatus;

static if(hasValue)

static inout(K) keyOf(inout(SomeElement) element);

static if(hasValue)

static inout(V) valueOf(inout(T) element);

alias KeyType = K;

alias ValueType = V;

static if(hasValue)

enum nullKeyElement;

static if(hasValue)

static inout(K) keyOf(inout(KeyValueType) element);

enum InsertionStatus;

static if(!(hasValue))

static inout(SomeElement) keyOf(inout(SomeElement) element);

static if(!(hasValue))

enum nullKeyElement;

enum passElementByValue;

template isScopedKeyType(SomeKey);

alias ElementType = T;

static typeof(this) withCapacity(size_t minimumCapacity);

import std.range.primitives : StdElementType = ElementType;;

import std.traits : isIterable, isAssignable;;

import std.traits : isIterable, isAssignable;;

this(T element);

static typeof(this) withElements(R elements);

typeof(this) dup();

bool opEquals(typeof(this) rhs);

static immutable

static if(borrowChecked)

auto borrowedErrorMessage;

void clear();

bool contains(SomeKey key);

bool containsUsingLinearSearch(SomeKey key);

bool containsWithHoleMoving(K key);

InsertionStatus insert(T element);

T insertAndReturnElement(SomeElement element);

void insertN(R elements);

enum bool growInPlaceFlag;

enum growScaleP;

enum growScaleQ;

void reserveExtra(size_t extraCapacity);

static if(hasValue)

InsertionStatus insert(K key, V value);

static if(!hasValue)

const(K)* opBinaryRight(SomeKey key);

static if(!hasValue)

typeof(this) opOpAssign(SomeKey key);

static if(!hasValue)

const(Class) tryGetElementFromCtorParams(Params params);

static if(hasValue)

inout(V)* opBinaryRight(SomeKey key);

static if(hasValue)

inout(V) opIndex(SomeKey key);

static if(hasValue)

inout(V) get(K key, inout(V) defaultValue);

static if(hasValue)

const(K) getKeyRef(SomeKey key, const(K) defaultKey);

static if(hasValue)

V opIndexAssign(V value, K key);

static if(hasValue)

V opIndexOpAssign(Rhs rhs, K key);

bool remove(SomeKey key);

enum bool isRefIterable(T); via import nxt.traits_ex : isRefIterable;;

import std.range.primitives : front;;

size_t rehashingRemoveN(Keys keys);

bool empty [@property getter];

size_t length [@property getter];

size_t binCount [@property getter];

size_t totalProbeCount();

double averageProbeCount();

inout(T)[] rawStore();

static if(hasHoleableKey)

static bool isOccupiedBin(T bin);

}

Constructors

this this(T element): Make with the element element.

Destructor

~this ~this(): Destruct.

Postblit

this(this) this(this): No copying.

Members

Aliases

ElementType alias ElementType = T: Undocumented in source.
KeyType alias KeyType = K: Type of key stored.
Nullifier alias Nullifier = typeof(K.init.nullifier): Undocumented in source.
StoreK alias StoreK = void*: Undocumented in source.
StoreK alias StoreK = void*: Undocumented in source.
StoreK alias StoreK = K: Undocumented in source.
T alias T = K: Undocumented in source.
ValueType alias ValueType = V: Type of value stored.
keyEqualPredFn alias keyEqualPredFn = binaryFun!keyEqualPred: Undocumented in source.
keyEqualPredFn alias keyEqualPredFn = keyEqualPred: Undocumented in source.

Enums

InsertionStatus enum InsertionStatus: Map insertion status.
InsertionStatus enum InsertionStatus: Set insertion status.

Functions

averageProbeCount double averageProbeCount()
clear void clear(): Empty.
contains bool contains(SomeKey key): Check if element is stored.
containsUsingLinearSearch bool containsUsingLinearSearch(SomeKey key): Check if element is stored.
containsWithHoleMoving bool containsWithHoleMoving(K key): Check if element is stored. Move found element to a hole if possible.
dup typeof(this) dup()
get inout(V) get(K key, inout(V) defaultValue): Get value of key or defaultValue if key not present (and therefore nothrow).
getKeyRef const(K) getKeyRef(SomeKey key, const(K) defaultKey): Get reference to key-part of stored element at key, if present, otherwise return defaultKey.
insert InsertionStatus insert(T element): Insert element, being either a key-value (map-case) or a just a key (set-case).
insert InsertionStatus insert(K key, V value): Insert or replace value at key.
insertAndReturnElement T insertAndReturnElement(SomeElement element): Insert element, being either a key-value (map-case) or a just a key (set-case).
insertN void insertN(R elements): Insert elements, all being either a key-value (map-case) or a just a key (set-case).
opBinaryRight const(K)* opBinaryRight(SomeKey key): Undocumented in source. Be warned that the author may not have intended to support it.
opBinaryRight inout(V)* opBinaryRight(SomeKey key): Undocumented in source. Be warned that the author may not have intended to support it.
opEquals bool opEquals(typeof(this) rhs): Equality.
opIndex inout(V) opIndex(SomeKey key): Indexing.
opIndexAssign V opIndexAssign(V value, K key): Supports the syntax aa[key] = value;.
opIndexOpAssign V opIndexOpAssign(Rhs rhs, K key): Undocumented in source. Be warned that the author may not have intended to support it.
opOpAssign typeof(this) opOpAssign(SomeKey key): Undocumented in source. Be warned that the author may not have intended to support it.
rawStore inout(T)[] rawStore(): Unsafe access to raw store.
rehashingRemoveN size_t rehashingRemoveN(Keys keys): Remove all elements matching keys followed by a rehash.
remove bool remove(SomeKey key): Remove element.
reserveExtra void reserveExtra(size_t extraCapacity): Reserve rom for extraCapacity number of extra buckets.
totalProbeCount size_t totalProbeCount()
tryGetElementFromCtorParams const(Class) tryGetElementFromCtorParams(Params params): Try to retrieve class-element of type Class constructed with parameters params.

Manifest constants

growScaleP enum growScaleP;: Numerator for grow scale.
growScaleQ enum growScaleQ;: Denominator for grow scale.
hasAddressLikeKey enum hasAddressLikeKey;: Is true iff K is an address, in which case holes are represented by a specific value holeKeyConstant.
hasHoleableKey enum hasHoleableKey;: Undocumented in source.
hasHoleableKey enum hasHoleableKey;: Undocumented in source.
hasHoleableKey enum hasHoleableKey;: Undocumented in source.
hasHoleableKey enum hasHoleableKey;: Undocumented in source.
hasHoleableKey enum hasHoleableKey;: Undocumented in source.
hasValue enum hasValue;: In the hash map case, V is non-void, and a value is stored alongside the key of type K.
holeKeyAddress enum holeKeyAddress;: Undocumented in source.
holeKeyOffset enum holeKeyOffset;: Undocumented in source.
isBorrowChecked enum isBorrowChecked;: Undocumented in source.
nullKeyElement enum nullKeyElement;: Undocumented in source.
nullKeyElement enum nullKeyElement;: Undocumented in source.
passElementByValue enum passElementByValue;: TODO remove when https://github.com/dlang/dmd/pull/11000 has been merged

Properties

binCount size_t binCount [@property getter]: Get bin count.
empty bool empty [@property getter]: Check if empty.
length size_t length [@property getter]: Get length (read-only).

Static functions

holeKeyConstant K holeKeyConstant()
holeKeyConstant K holeKeyConstant(): Undocumented in source. Be warned that the author may not have intended to support it.
holeKeyConstant K holeKeyConstant(): Undocumented in source. Be warned that the author may not have intended to support it.
isHoleKeyConstant bool isHoleKeyConstant(K key): Undocumented in source. Be warned that the author may not have intended to support it.
isHoleKeyConstant bool isHoleKeyConstant(K key): Undocumented in source. Be warned that the author may not have intended to support it.
isHoleKeyConstant bool isHoleKeyConstant(K key): Undocumented in source. Be warned that the author may not have intended to support it.
isOccupiedBin bool isOccupiedBin(T bin): Undocumented in source. Be warned that the author may not have intended to support it.
keyOf inout(K) keyOf(inout(SomeElement) element): Get key part of element.
keyOf inout(K) keyOf(inout(KeyValueType) element): Get key part.
keyOf inout(SomeElement) keyOf(inout(SomeElement) element): Get key part of element.
valueOf inout(V) valueOf(inout(T) element): Get value part of element.
withCapacity typeof(this) withCapacity(size_t minimumCapacity): Make with room for storing at least minimumCapacity number of elements.
withElements typeof(this) withElements(R elements): Make with the elements elements.

Static variables

borrowedErrorMessage auto borrowedErrorMessage;: Undocumented in source.

Structs

T struct T: Mutable element reference with mutable constant key and value.

Templates

isScopedKeyType template isScopedKeyType(SomeKey): Is true if an instance of SomeKey that can be implictly cast to K.

Variables

assumeNonFullHaystack enum bool assumeNonFullHaystack;: Setting this true doesn't give measurable speedups so set it to false for now.
growInPlaceFlag enum bool growInPlaceFlag;: Is true iff in-place rehashing during growth should be performed.

Parameters

K: key type
V: value type
hasher: hash function or std.digest Hash
Allocator: memory allocator for bin array
borrowChecked: only activate when it's certain that this won't be moved via std.algorithm.mutation.move()
useSmallLinearSearch: Use linear search instead probing when _store is smaller than linearSearchMaxSize
usePrimeCapacity: Use prime numbers as capacity of hash table enabling better performance of simpler hash-functions

See Also

https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/

https://arxiv.org/abs/1605.04031

https://github.com/Tessil/robin-map

https://github.com/martinus/robin-hood-hashing

https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/

https://en.wikipedia.org/wiki/Lazy_deletion

https://forum.dlang.org/post/ejqhcsvdyyqtntkgzgae@forum.dlang.org https://gankro.github.io/blah/hashbrown-insert/

TODO replace remove branching on passElementByValue when https://github.com/dlang/dmd/pull/11000 has been merged and use in instead

TODO: Disable pragma(inline, true) and rebenchmark

TODO: tests fails when useSmallLinearSearch is set to false

TODO: Use set of Flags (defined here) as template params

Robin-hood case introspect key type for storage of parts of hash alongside nullValue and holeValue. Typically for address-types that doesn't need scanning. Example is Address for implementation of GC. This is a D showcase for code that is difficult to write in C++.

TODO: group nxt.probing functions in Prober struct given as type template param to OpenHashMap

TODO: Make load factor dependent on current capacity or length and perhaps also type and hash-function to get memory efficiency when it matters. Similar to what is recommended in https://ticki.github.io/blog/horrible/.

TODO: For copyable types replace auto ref with logic that only passes by ref when it's faster to do so. See_Also: https://github.com/dlang/dmd/pull/11000

TODO: remove use of static if (__traits(isCopyable, ...)) in cases where compiler can handle more moves

TODO: use mmap allocator when _store.sizeof is larger than at least 8 pages

TODO: use StoreK in store and cast between it and KeyType

TODO: allocate _holesPtr array together with _store to reduce size of OpenHashMap to 3 words when element type doesn't support it

TODO: fix bug in growInPlaceWithCapacity and benchmark

TODO: modify existing unittest for struct Rel { const string name; }

TODO: use allocator.dispose() instead of allocator.deallocate() as in https://github.com/dlang-community/containers

TODO: if hash-function is cast(size_t)(classInstance) always use prime length and shift pointer before hash based on alignof (might not be needed when module prime) to maximize memory locality when adding successively allocated pointers

TODO: add extractElement that moves it out similar to http://en.cppreference.com/w/cpp/container/unordered_set/extract

TODO: add merge or union algorithm here or into container_algorithm.d. See also: http://en.cppreference.com/w/cpp/container/unordered_set/merge. this algorithm moves elements from source if they are not already in this

TODO: Robin-Hood-hashing

TODO: enable borrowChecked unconditionally in version(debug) if and when opMove is implemented, in which case opMove() should assert false if this is borrowed. See: https://github.com/dlang/DIPs/pull/109

TODO: keep only predicates with ref arguments (const scope auto ref) when LDC can optimize those as fast as value passing. add LDC issue for this

TODO: save one word by making _store.length be inferred by primeConstants[_primeIndex] if this is not too costly

TODO: only add one extra element to capacity when assumeNonFullHaystack is true

Meta

Source

See Implementation

nxt open_hashmap aliases

enums

functions

structs

templates

defaultKeyEqualPredOf

variables

isAddress