Transposition-table container built on top of Aleph hash maps. More...

#include <Transposition_Table.H>

Collaboration diagram for Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >:

Public Types
using	Key_Type = Key

using	Entry_Type = Entry

using	Map_Type = SearchStorageMap< Key, Entry, HashMapTable, Cmp >

using	Replace_Policy = ReplacePolicy

Public Member Functions
	Transposition_Table ()=default
	Build an empty table with the default replacement policy.

	Transposition_Table (ReplacePolicy replace)
	Build a table with a custom replacement policy instance.

void	clear () noexcept
	Remove all stored entries.

void	reset_stats () noexcept
	Reset only the accumulated storage statistics.

size_t	size () const noexcept
	Number of currently stored entries.

bool	is_empty () const noexcept
	Return `true` if the table contains no entries.

const TranspositionStats &	stats () const noexcept
	Read-only access to accumulated storage statistics.

Entry *	probe (const Key &key)
	Probe one key and return the stored entry if present.

Entry *	probe (Key &&key)
	Probe one key using move semantics.

TranspositionStoreStatus	store (const Key &key, const Entry &entry)
	Store a candidate entry for `key`.

TranspositionStoreStatus	store (Key &&key, Entry entry)
	Store a candidate entry for `key` using move semantics.

Static Public Attributes
static constexpr bool	enabled = true
	Compile-time marker for search adapters.

Private Member Functions
template<typename KeyLike >
Entry *	probe_impl (KeyLike &&key)

template<typename KeyLike , typename EntryLike >
TranspositionStoreStatus	store_impl (KeyLike &&key, EntryLike &&entry)

Private Attributes
Map_Type	table_

ReplacePolicy	replace_ = {}

TranspositionStats	stats_

Detailed Description

template<typename Key, typename Entry, template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>
requires TranspositionReplacementPolicy<ReplacePolicy, Entry>
class Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >

Transposition-table container built on top of Aleph hash maps.

Thread-safety: all member functions require external synchronization. The table stores entries in-place and returns mutable pointers when probing; as such, callers must ensure only one thread manipulates the table at a time.

Template Parameters

Key	Stable cache key type.
Entry	Cached value associated with `Key`.
HashMapTable	Aleph hash-table backend, `MapOLhash` by default.
Cmp	Equality comparator for keys.
ReplacePolicy	Policy deciding whether a new entry overwrites an existing entry for the same key.

Definition at line 169 of file Transposition_Table.H.

Member Typedef Documentation

◆ Entry_Type

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

using Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::Entry_Type = Entry

Definition at line 175 of file Transposition_Table.H.

◆ Key_Type

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

using Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::Key_Type = Key

Definition at line 174 of file Transposition_Table.H.

◆ Map_Type

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

using Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::Map_Type = SearchStorageMap<Key, Entry, HashMapTable, Cmp>

Definition at line 176 of file Transposition_Table.H.

◆ Replace_Policy

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

using Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::Replace_Policy = ReplacePolicy

Definition at line 177 of file Transposition_Table.H.

Constructor & Destructor Documentation

◆ Transposition_Table() [1/2]

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::Transposition_Table ( )

default

Build an empty table with the default replacement policy.

Note: Complexity: O(1).

◆ Transposition_Table() [2/2]

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::Transposition_Table ( ReplacePolicy replace )

inlineexplicit

Build a table with a custom replacement policy instance.

Parameters

replace Replacement policy functor.

Note: Complexity: O(1).

Definition at line 188 of file Transposition_Table.H.

Member Function Documentation

◆ clear()

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

void Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::clear ( )

inlinenoexcept

Remove all stored entries.

Note: Complexity: O(n) due to hash table clearing.

Definition at line 196 of file Transposition_Table.H.

References Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::table_.

◆ is_empty()

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

bool Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::is_empty ( ) const

inlinenoexcept

Return true if the table contains no entries.

Returns: True when empty. Complexity: O(1).

Definition at line 220 of file Transposition_Table.H.

References Aleph::HashMap< Key, Data, HashMapTable, Cmp >::is_empty(), and Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::table_.

◆ probe() [1/2]

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

Entry * Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe ( const Key & key )

inline

Probe one key and return the stored entry if present.

Parameters

key	Cache key.

Returns: Mutable pointer to the stored entry, or nullptr on miss.

Note: Complexity: expected O(1) for hash-table lookup.

Definition at line 238 of file Transposition_Table.H.

References Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe_impl().

◆ probe() [2/2]

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

Entry * Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe ( Key && key )

inline

Probe one key using move semantics.

Parameters

key	Cache key (consumed).

Returns: Mutable pointer to the stored entry, or nullptr on miss.

Note: Complexity: expected O(1) for hash-table lookup.

Definition at line 248 of file Transposition_Table.H.

References Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe_impl().

◆ probe_impl()

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

template<typename KeyLike >

Entry * Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe_impl ( KeyLike && key )

inlineprivate

Definition at line 282 of file Transposition_Table.H.

References Aleph::TranspositionStats::hits, Aleph::TranspositionStats::misses, Aleph::TranspositionStats::probes, Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::stats_, and Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::table_.

Referenced by Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe(), and Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe().

◆ reset_stats()

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

void Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::reset_stats ( )

inlinenoexcept

Reset only the accumulated storage statistics.

Note: Complexity: O(1).

Definition at line 204 of file Transposition_Table.H.

References Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::stats_.

◆ size()

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

size_t Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::size ( ) const

inlinenoexcept

Number of currently stored entries.

Returns: Count of entries. Complexity: O(1).

Definition at line 212 of file Transposition_Table.H.

References Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::table_.

◆ stats()

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

const TranspositionStats & Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::stats ( ) const

inlinenoexcept

Read-only access to accumulated storage statistics.

Returns: Reference to internal stats structure. Complexity: O(1).

Definition at line 228 of file Transposition_Table.H.

References Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::stats_.

◆ store() [1/2]

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

TranspositionStoreStatus Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store	(	const Key &	key,
		const Entry &	entry
	)

inline

Store a candidate entry for key.

If the key is absent, the entry is inserted. Otherwise the configured replacement policy decides whether the current entry is overwritten.

Parameters

key	Cache key.
entry	Candidate entry to store.

Returns: Status describing whether the candidate was inserted, replaced or rejected.

Note: Complexity: expected O(1).

Definition at line 264 of file Transposition_Table.H.

References Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store_impl().

◆ store() [2/2]

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

TranspositionStoreStatus Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store	(	Key &&	key,
		Entry	entry
	)

inline

Store a candidate entry for key using move semantics.

Parameters

key	Cache key (consumed).
entry	Entry moved into storage.

Returns: Insert/replace/reject status.

Note: Complexity: expected O(1).

Definition at line 275 of file Transposition_Table.H.

References Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store_impl().

◆ store_impl()

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

template<typename KeyLike , typename EntryLike >

TranspositionStoreStatus Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store_impl	(	KeyLike &&	key,
		EntryLike &&	entry
	)

inlineprivate

Definition at line 298 of file Transposition_Table.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Inserted, Aleph::Rejected, Aleph::TranspositionStats::rejected_updates, Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::replace_, Aleph::Replaced, Aleph::TranspositionStats::replacements, Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::stats_, Aleph::TranspositionStats::stores, and Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::table_.

Referenced by Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store(), and Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store().

Member Data Documentation

◆ enabled

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

constexpr bool Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::enabled = true

staticconstexpr

Compile-time marker for search adapters.

Definition at line 172 of file Transposition_Table.H.

◆ replace_

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

ReplacePolicy Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::replace_ = {}

private

Definition at line 320 of file Transposition_Table.H.

Referenced by Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store_impl().

◆ stats_

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

TranspositionStats Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::stats_

private

Definition at line 321 of file Transposition_Table.H.

Referenced by Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe_impl(), Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::reset_stats(), Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::stats(), and Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store_impl().

◆ table_

template<typename Key , typename Entry , template< typename, typename, class > class HashMapTable = MapOLhash, class Cmp = Aleph::equal_to<Key>, typename ReplacePolicy = Replace_Always<Entry>>

Map_Type Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::table_

private

Definition at line 319 of file Transposition_Table.H.

Referenced by Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::clear(), Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::is_empty(), Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::probe_impl(), Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::size(), and Aleph::Transposition_Table< Key, Entry, HashMapTable, Cmp, ReplacePolicy >::store_impl().

The documentation for this class was generated from the following file:

Transposition_Table.H

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Entry_Type

◆ Key_Type

◆ Map_Type

◆ Replace_Policy

Constructor & Destructor Documentation

◆ Transposition_Table() [1/2]

◆ Transposition_Table() [2/2]

Member Function Documentation

◆ clear()

◆ is_empty()

◆ probe() [1/2]

◆ probe() [2/2]

◆ probe_impl()

◆ reset_stats()

◆ size()

◆ stats()

◆ store() [1/2]

◆ store() [2/2]

◆ store_impl()

Member Data Documentation

◆ enabled

◆ replace_

◆ stats_

◆ table_