core.internal.newaa

template implementation of associative arrays.

Copyright

License

Authors

Martin Nowak, Steven Schveighoffer, Rainer Schuetze

derived from rt/aaA.d

var _aaVersion GROW_DEN GROW_FAC GROW_NUM HASH_DELETED HASH_EMPTY HASH_FILLED_MARK INIT_DEN INIT_NUM INIT_NUM_BUCKETS SHRINK_DEN SHRINK_NUM

tmpl pure_hashOf pure_keyEqual Unconstify

struct _noV2 AA AARange Bucket Entry Impl

fn _aaClear _aaDup _aaEqual _aaGetHash _aaGetX _aaKeys _aaMove _aaOpEqual _aaRange _aaRangeEmpty _aaRangeFrontKey _aaRangeFrontValue _aaRangePopFront _aaRehash _aaValues _d_aaApply _d_aaApply2 _d_aaDel _d_aaEqual _d_aaGetRvalueX _d_aaGetY _d_aaIn _d_aaLen _d_aaNew _d_assocarrayliteralTX _newEntry _refAA _toAA compat_key gc_inFinalizer makeAA mix nextpow2 talign

Types 6

structAA(K, V)

AA wrapper

Fields

Impl!(K, V) * impl

Methods

bool empty() @property const pure nothrow @nogc @safe

size_t length() @property const pure nothrow @nogc @safe

structEntry(K, V)

Fields

K key

V value

private structImpl(K, V)

Fields

Bucket[] buckets

uint used

uint deleted

const(TypeInfo) entryTI

uint firstUsed

uint keysz

uint valsz

uint valoff

Flags flags

size_t delegate(scope ref const K) nothrow pure @nogc @safe hashFn

Methods

size_t length() @property const pure nothrow @nogc @safe

size_t dim() @property const pure nothrow @nogc @safe

size_t mask() @property const pure nothrow @nogc @safe

size_t findSlotInsert(size_t hash) const pure nothrow @nogc @safe

inout(Bucket) * findSlotLookup(K2)(size_t hash, scope ref const K2 key) inout pure @safe nothrow

void grow() pure nothrow @safe

void shrink() pure nothrow @safe

void resize(size_t ndim) pure nothrow @safe

void clear() pure nothrow

size_t calcHash(K2)(ref K2 key) const nothrow pure @nogc @safe

Bucket[] allocBuckets(size_t dim) pure nothrow @safe

Constructors

this(size_t sz /* = INIT_NUM_BUCKETS */)

Nested Templates

Flags

private structBucket(K, V)

Fields

size_t hash

Entry!(K, V) * entry

Methods

bool empty() @property const

bool deleted() @property const

bool filled() @property const @safe

private struct_noV2

structAARange(K, V)

_aaRange implements a ForwardRange

Fields

Impl!(Key, Value) * impl

size_t idx

Functions 48

fnref _refAA(K, V)(ref V[K] aa) @trusted

fnauto _toAA(K, V)(const V[K] aa) @trusted

fnauto _toAA(K, V)(inout V[K] aa) @trusted

fnauto _toAA(K, V)(shared const V[K] aa) @trusted

fnauto _toAA(K, V)(shared V[K] aa) @trusted

fnauto _toAA(K, V)(immutable V[K] aa) @trusted

private fnref compat_key(K, K2)(ref K2 key)

private fnvoid _aaMove(V)(ref V src, ref V dst) @trusted

fnEntry!(K, V) * _newEntry(K, V)(ref K key, auto ref V value)

fnEntry!(K, V) * _newEntry(K, V, K2)(ref K2 key)

private fnsize_t talign(size_t tsize, size_t algn) @safe pure nothrow @nogc

private fnsize_t mix(size_t h) @safe pure nothrow @nogc

private fnsize_t nextpow2(const size_t n) pure nothrow @nogc @safe

fnV[K] _d_aaNew(K, V)()Allocate associative array data. Called for `new SomeAA` expression. Returns: A new associative array. Note: not supported in CTFE

fnsize_t _d_aaLen(K, V)(inout V[K] a)Determine number of entries in associative array. Note: emulated by the compiler during CTFE

fnV * _d_aaGetY(K, V, T : V1[K1], K1, V1, K2)(auto ref scope T aa, auto ref K2 key, out bool found)Lookup key in aa. Called only from implementation of (aa[key]) expressions when value is mutable. Params: aa = associative array key = reference to the key value found = returns whether the key was...

fnV * _aaGetX(K, V, K2, V2)(auto ref scope V[K] a, auto ref K2 key, out bool found, lazy V2 v2)Lookup key in aa. Called only from implementation of require, update and daaGetY Params: a = associative array key = reference to the key value found = true if the value was found v2 = if key not f...

fnauto _d_aaGetRvalueX(K, V, K2)(inout V[K] aa, auto ref scope K2 key)Lookup key in aa. Called only from implementation of (aa[key]) expressions when value is not mutable. Params: aa = associative array key = key value Returns: pointer to value if present, null other...

fnauto _d_aaGetRvalueX(K, V, K2)(shared(V[K]) aa, auto ref scope K2 key)ditto

fnauto _d_aaGetRvalueX(K, V, K2)(shared const(V[K]) aa, auto ref scope K2 key)ditto

fnauto _d_aaGetRvalueX(K, V, K2)(immutable(V[K]) aa, auto ref scope K2 key)ditto

fnauto _aaDup(T : V[K], K, V)(T a)Creates a new associative array of the same size and copies the contents of the associative array into it. Params: a = The associative array.

fnauto _d_aaIn(T : V[K], K, V, K2)(inout T a, auto ref scope K2 key)Lookup key in aa. Called only from implementation of (key in aa) expressions. Params: a = associative array opaque pointer key = reference to the key value Returns: pointer to value if present, nul...

private fnbool gc_inFinalizer() pure nothrow @safe

fnauto _d_aaDel(T : V[K], K, V, K2)(T a, auto ref K2 key)Delete entry scope const AA, return true if it was present

fnvoid _aaClear(K, V)(V[K] a)Remove all elements from AA.

fnV[K] _aaRehash(K, V)(V[K] a)Rehash AA

fnauto _aaValues(K, V)(inout V[K] a)Return a GC allocated array of all values

fnauto _aaKeys(K, V)(inout V[K] a)Return a GC allocated array of all keys

fnint _d_aaApply(K, V, DG)(inout V[K] a, DG dg)foreach opApply over all values Note: emulated by the compiler during CTFE

fnint _d_aaApply(K, V, DG)(shared V[K] a, DG dg)

fnint _d_aaApply(K, V, DG)(shared const V[K] a, DG dg)

fnint _d_aaApply(K, V, DG)(immutable V[K] a, DG dg)

fnint _d_aaApply2(K, V, DG)(inout V[K] a, DG dg)foreach opApply over all key/value pairs Note: emulated by the compiler during CTFE

fnint _d_aaApply2(K, V, DG)(shared V[K] a, DG dg)

fnint _d_aaApply2(K, V, DG)(shared const V[K] a, DG dg)

fnint _d_aaApply2(K, V, DG)(immutable V[K] a, DG dg)

fnImpl!(K, V) * _d_assocarrayliteralTX(K, V)(K[] keys, V[] vals)Construct an associative array of type ti from corresponding keys and values. Called for an AA literal `[k1:v1, k2:v2]`. Params: keys = array of keys vals = array of values Returns: A new associati...

fnbool _aaEqual(T : AA!(K, V), K, V)(scope T aa1, scope T aa2)compares 2 AAs for equality

fnbool _d_aaEqual(K, V)(scope const V[K] a1, scope const V[K] a2)compares 2 AAs for equality (compiler hook)

fnbool _aaOpEqual(K, V)(scope /* const */ AA!(K, V) * aa1, scope /* const */ AA!(K, V) * aa2)callback from TypeInfo_AssociativeArray.equals (ignore const for now)

fnhash_t _aaGetHash(K, V)(/* scope const */ AA!(K, V) * paa)compute a hash callback from TypeInfo_AssociativeArray.xtoHash (ignore scope const for now)

fnAARange!(K, V) _aaRange(K, V)(V[K] a)

fnbool _aaRangeEmpty(K, V)(AARange!(K, V) r)

fnK * _aaRangeFrontKey(K, V)(AARange!(K, V) r)

fnV * _aaRangeFrontValue(K, V)(AARange!(K, V) r)

fnvoid _aaRangePopFront(K, V)(ref AARange!(K, V) r)

fnAA!(K, V) makeAA(K, V)(V[K] src) @trusted

Variables 12

varint _aaVersion

AA version for debuggers, bump whenever changing the layout

private enumvarGROW_NUM = 4

private enumvarGROW_DEN = 5

private enumvarSHRINK_NUM = 1

private enumvarSHRINK_DEN = 8

private enumvarGROW_FAC = 4

private enumvarINIT_NUM = (GROW_DEN * SHRINK_NUM + GROW_NUM * SHRINK_DEN) / 2

private enumvarINIT_DEN = SHRINK_DEN * GROW_DEN

private enumvarINIT_NUM_BUCKETS = 8

private enumvarHASH_EMPTY = 0

private enumvarHASH_DELETED = 0x1

private enumvarHASH_FILLED_MARK = size_t(1) << 8 * size_t.sizeof - 1

Templates 3

tmplUnconstify(T : const U, U)

like core.internal.traits.Unconst, but stripping inout, too

tmplpure_hashOf(K)

tmplpure_keyEqual(K1, K2 = K1)