data.hash_table ≡

A data structure that maps keys to values using hashing.

template <typename Hash, typename Key>
inline Hash toeplitz_hash(Key key) §

Computes a hash of input keys using an instance of the toeplitz class.

Parameters

```
typename Hash
```
Output hash type
```
typename Key
```
Input key type

template <
    typename Key,
    typename Value,
    auto Depth,
    auto Associativity,
    (Key) -> index_t<(Depth / Associativity)> hash_fn
        = toeplitz_hash<index_t<(Depth / Associativity)>, Key>,
    auto GenerationBits = 4,
    auto MaxIterations = Depth,
    auto DataBanks = 1,
    auto HistorySize = 1,
    auto MaxThreads = 512
    >
class hash_table §

A mapping from Key to Value. Use insert_or_update to insert, lookup, modify, and reset the mapping. The only way to remove entries from the table is to reset the entire table to the initial empty state.

Parameters

```
typename Key
```
```
typename Value
```
```
auto Depth
```
Maximum number of elements that can be stored.
```
auto Associativity
```
Number of locations to consider on each search iteration. Larger values lead to more resource consumption and higher throughput.

(Key) -> index_t<(Depth / Associativity)> hash_fn
    = toeplitz_hash<index_t<(Depth / Associativity)>, Key>

Function that maps a key to a location in the hash table.

```
auto GenerationBits = 4
```
Number of bits to ammortize reset costs. Higher values lead to more resource consumption, and lower the average cost of reset.
```
auto MaxIterations = Depth
```
Maximum number of search iterations before returning an error
```
auto DataBanks = 1
```
Number of banks to store values. If Depth is high, then increasing DataBanks can improve clock frequency.
```
auto HistorySize = 1
```
Size of arrays used to detect hazards. Larger values increase frequency and resource usage.
```
auto MaxThreads = 512
```
Maximum number of threads that can be present inside of insert_or_update concurrently. Caller does not need to ensure this limit is respected. Higher values enable more concurrency which can improve performance if the allocation function compiles to a deep pipeline or if DataBanks is set to a large value. Lower values save resources by using narrower counters to track in-flight threads.

Types

```
struct result §
```
Return value on a successful insert_or_update
Fields
- bool inserted §
  
  True if this is the first time the associated key has been used since the hash table was reset.
- pair<Value, Value> value §
  
  Values in the hash table before and after the lookup When an key is first inserted into the table, value.first is the value returned by allocate_fn.

Methods

```
inline bool test_thread_count(bool reset) §
```
Used to block the first thread of each generation until _threads_in_flight is zero
```
inline 
optional<hash_table::result>
insert_or_update(
    Key key,
    bool reset,
    bool insert_on_miss,
    () -> Value allocate_fn,
    (Value, bool) -> Value access_fn
    ) §
```
Combined function that can be used to:
1. Insert a new (Key, Value) pair.
2. Lookup the Value associated with a Key that is already present in the table.
3. Modify the Value associated with a Key that is already present in the table.
4. Reset the table to the initial state.
Inserts, lookups, and modifications use an iterative search. A hash of the input key is used to determine the starting location for the search. On each iteration, Associativity locations are checked in parallel. If a matching key is found then the hash table runs at full throughput. Otherwise, the search loop proceeds, searching Associativity new locations on each iteration. Callers must ensure there are never concurrent calls to this function from separate call sites. Calls to allocate_fn occur in the same order as calls to insert_or_update.
Arguments
- Key key
  
  Key used to find a location to store the value
- bool reset
  
  True if all elements in the hash table should be removed before performing the search.
- bool insert_on_miss
  
  True if a new (Key, Value) pair should be inserted into the table if a pair with a matching key is not already present.
- () -> Value allocate_fn
  
  Function that is called when a key is inserted into the hash table. Returns a value that is passed to access_fn.
- (Value, bool) -> Value access_fn
  
  Function that accepts a previous value and a bool indicating if an insert occured. Returns a new value to store in the hash table associated with the key. If key was not already present in the table then, the first parameter is the value returned by allocate_fn and the second parameter is true. Otherwise, the first parameter is the value currently stored in the table and the second parameter is false.

Invariants

```
(0 == (Depth % Associativity))
```
All sets must have the same number of elements

(0 == (hash_table::NumSets & (hash_table::NumSets - 1)))

Set count must be a power of 2

```
(MaxIterations > 0)
```
MaxIterations must be positive, otherwise no lookup operation could ever succeed

Index

data.hash_table ≡