Struct StackHash

A hash table that allocates its memory on RegionAllocator. Good for building a temporary hash tables that will not escape the current scope.

struct StackHash(K, V) ;

Constructors

NameDescription
this Due to the nature of RegionAllocator, you must specify on object creation the approximate number of elements your table will have. Too large a number will waste space and incur poor cache performance. Too low a number will make this struct perform like a linked list. Generally, if you're building a table from some other range, some fraction of the size of that range is a good guess.

Fields

NameTypeDescription
alloc RegionAllocator
freeList StackHash.Node**
rKeys Unqual!K[]
rNext Unqual!(Node*)[]
rVals Unqual!V[]
_length size_t

Properties

NameTypeDescription
length[get] size_t
usedSentinel[get] StackHash.Node*

Methods

NameDescription
allocNode
efficiency
get Attempt to look up a key and return a default value if the key is not present.
getHash
keys Returns a forward range to iterate over the keys of this table. The lifetime of this range must not exceed the lifetime of this StackHash.
newNode
newNode
opApply
opIndex Index an element of the range. If it does not exist, it will be created and initialized to V.init.
opIndexAssign
opIn_r
pushFreeList
remove
values Returns a forward range to iterate over the values of this table. The lifetime of this range must not exceed the lifetime of this StackHash.

Aliases

NameDescription
Node

Examples

auto alloc = newRegionAllocator();
auto ss = StackHash!(uint)(5, alloc);
foreach(i; 0..5) {
    ss[i]++;
}
assert(ss[3] == 1);

Warning

This implementation places removed nodes on an internal free list and recycles them, since there is no way to delete RegionAllocator-allocated data in a non-LIFO order. Therefore, you may not retain the address of a variable stored in a StackHash after deleting it from the StachHash. For example, DO NOT do this: 

SomeType* myPtr = &(myStackHash["foo"]);
myStackHash.remove("foo");
*myPtr = someValue;