odhash.cc File Reference

Tests for Odhash. More...

#include <gtest/gtest.h>
#include <numeric>
#include <random>
#include <set>
#include <chrono>
#include <tpl_odhash.H>

Include dependency graph for odhash.cc:

Go to the source code of this file.

Classes
struct	MyRecord
struct	MyRecord::Eq
struct	ODhashBucketStats

Functions
	TEST (ODhashTable, Simplest)
size_t	fst_hast (const MyRecord &r) noexcept
size_t	snd_hash (const MyRecord &r) noexcept
	TEST (ODhashTable, Map)
	TEST (ODhashTable, KeyToBucketRoundTrip)
	TEST (ODhashTable, RemoveNonExistentKeyPreservesTableIntegrity)
	TEST (ODhashTable, RemoveWithExternalKey)
	TEST (ODhashTable, RemoveWithInternalKey)
	TEST (ODhashTable, RemoveNonExistentDoesNotRehash)
	TEST (ODhashTable, Fuzz_RandomOperationsWithOracle)
	TEST (ODhashTable, Stress_FillAndEmpty)
	TEST (ODhashTable, Stress_ManyCollisions)
	TEST (ODhashTable, Stress_InsertRemoveCycles)
	TEST (ODhashTable, Stress_ResizeOperations)
	TEST (ODhashTable, Fuzz_InterleavedOperations)
	TEST (ODhashTable, Stress_WithAutoResize)
	TEST (ODhashTable, Stress_StringKeys)
	TEST (ODhashTable, SearchOrInsert_WithDeletedEntries)
	TEST (ODhashTable, ContainsOrInsert_WithCollisions)
	TEST (ODhashTable, Stress_SearchOrInsertWithDeleted)
	TEST (ODhashTable, Debug_SearchOrInsertBug)
	TEST (ODhashTable, CopyConstructor)
	TEST (ODhashTable, MoveConstructor)
	TEST (ODhashTable, CopyAssignment)
	TEST (ODhashTable, MoveAssignment)
	TEST (ODhashTable, SelfAssignment)
	TEST (ODhashTable, EmptyTableOperations)
	TEST (ODhashTable, SingleElement)
	TEST (ODhashTable, DuplicateInsertReturnsNull)
	TEST (ODhashTable, HasAndContains)
	TEST (ODhashTable, Find)
	TEST (ODhashTable, ManualRehash)
	TEST (ODhashTable, ResizeUp)
	TEST (ODhashTable, ResizeDown)
	TEST (ODhashTable, IteratorBasic)
	TEST (ODhashTable, IteratorEmpty)
	TEST (ODhashTable, IteratorSingleElement)
	TEST (ODhashTable, IteratorDelete)
template<typename HashTable >
ODhashBucketStats	count_odhash_bucket_states (const HashTable &tbl)
	TEST (ODhashTable, ProbeCounterCleanup_LastInChainBecomesEmpty)
	TEST (ODhashTable, ProbeCounterCleanup_MiddleStaysDeleted)
	TEST (ODhashTable, ProbeCounterCleanup_ChainCleanup)
	TEST (ODhashTable, ForEach)
	TEST (ODhashTable, All)
	TEST (ODhashTable, Exists)
	TEST (ODhashTable, Filter)

Detailed Description

Tests for Odhash.

Definition in file odhash.cc.

Function Documentation

count_odhash_bucket_states()

template<typename HashTable >

ODhashBucketStats count_odhash_bucket_states

(

const HashTable &

tbl

)

Definition at line 1155 of file odhash.cc.

References ODhashBucketStats::busy, ODhashBucketStats::deleted, ODhashBucketStats::empty, and tbl.

Referenced by TEST(), TEST(), and TEST().

fst_hast()

size_t fst_hast ( const MyRecord &  r )

inlinenoexcept

Definition at line 105 of file odhash.cc.

References Aleph::dft_hash_fct(), and r.

Referenced by TEST().

snd_hash()

size_t snd_hash ( const MyRecord &  r )

inlinenoexcept

Definition at line 110 of file odhash.cc.

References r, and Aleph::snd_hash_fct().

Referenced by TEST().

TEST() [1/43]

TEST	(	ODhashTable	,
		All
	)

Definition at line 1255 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [2/43]

TEST	(	ODhashTable	,
		ContainsOrInsert_WithCollisions
	)

Definition at line 721 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [3/43]

TEST	(	ODhashTable	,
		CopyAssignment
	)

Definition at line 902 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::copy().

TEST() [4/43]

TEST	(	ODhashTable	,
		CopyConstructor
	)

Definition at line 862 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::copy().

TEST() [5/43]

TEST	(	ODhashTable	,
		Debug_SearchOrInsertBug
	)

Definition at line 811 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), k, and tbl.

TEST() [6/43]

TEST	(	ODhashTable	,
		DuplicateInsertReturnsNull
	)

Definition at line 983 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [7/43]

TEST	(	ODhashTable	,
		EmptyTableOperations
	)

Definition at line 957 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [8/43]

TEST	(	ODhashTable	,
		Exists
	)

Definition at line 1265 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [9/43]

TEST	(	ODhashTable	,
		Filter
	)

Definition at line 1275 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [10/43]

TEST	(	ODhashTable	,
		Find
	)

Definition at line 1011 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [11/43]

TEST	(	ODhashTable	,
		ForEach
	)

Definition at line 1243 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::sum(), and tbl.

TEST() [12/43]

TEST	(	ODhashTable	,
		Fuzz_InterleavedOperations
	)

Definition at line 525 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), FAIL, rng, and tbl.

TEST() [13/43]

TEST	(	ODhashTable	,
		Fuzz_RandomOperationsWithOracle
	)

Definition at line 291 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), FAIL, rng, and tbl.

TEST() [14/43]

TEST	(	ODhashTable	,
		HasAndContains
	)

Definition at line 996 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [15/43]

TEST	(	ODhashTable	,
		IteratorBasic
	)

Definition at line 1089 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [16/43]

TEST	(	ODhashTable	,
		IteratorDelete
	)

Definition at line 1128 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [17/43]

TEST	(	ODhashTable	,
		IteratorEmpty
	)

Definition at line 1107 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [18/43]

TEST	(	ODhashTable	,
		IteratorSingleElement
	)

Definition at line 1115 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [19/43]

TEST	(	ODhashTable	,
		KeyToBucketRoundTrip
	)

Definition at line 145 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), OhashCommon< HashTbl, Key >::insert(), and tbl.

TEST() [20/43]

TEST	(	ODhashTable	,
		ManualRehash
	)

Definition at line 1028 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [21/43]

TEST	(	ODhashTable	,
		Map
	)

Definition at line 116 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), fst_hast(), snd_hash(), tbl, and Aleph::to_string().

TEST() [22/43]

TEST	(	ODhashTable	,
		MoveAssignment
	)

Definition at line 921 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), OhashCommon< HashTbl, Key >::insert(), Aleph::ODhashTable< Key, Cmp >::search(), and OhashCommon< HashTbl, Key >::size().

TEST() [23/43]

TEST	(	ODhashTable	,
		MoveConstructor
	)

Definition at line 884 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [24/43]

TEST	(	ODhashTable	,
		ProbeCounterCleanup_ChainCleanup
	)

Definition at line 1221 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), count_odhash_bucket_states(), and tbl.

TEST() [25/43]

TEST	(	ODhashTable	,
		ProbeCounterCleanup_LastInChainBecomesEmpty
	)

Definition at line 1171 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), count_odhash_bucket_states(), and tbl.

TEST() [26/43]

TEST	(	ODhashTable	,
		ProbeCounterCleanup_MiddleStaysDeleted
	)

Definition at line 1197 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), count_odhash_bucket_states(), and tbl.

TEST() [27/43]

TEST	(	ODhashTable	,
		RemoveNonExistentDoesNotRehash
	)

Definition at line 255 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [28/43]

TEST	(	ODhashTable	,
		RemoveNonExistentKeyPreservesTableIntegrity
	)

Definition at line 163 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [29/43]

TEST	(	ODhashTable	,
		RemoveWithExternalKey
	)

Definition at line 209 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [30/43]

TEST	(	ODhashTable	,
		RemoveWithInternalKey
	)

Definition at line 234 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [31/43]

TEST	(	ODhashTable	,
		ResizeDown
	)

Definition at line 1070 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [32/43]

TEST	(	ODhashTable	,
		ResizeUp
	)

Definition at line 1053 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [33/43]

TEST	(	ODhashTable	,
		SearchOrInsert_WithDeletedEntries
	)

Definition at line 679 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [34/43]

TEST	(	ODhashTable	,
		SelfAssignment
	)

Definition at line 940 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [35/43]

TEST	(	ODhashTable	,
		Simplest
	)

Definition at line 50 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [36/43]

TEST	(	ODhashTable	,
		SingleElement
	)

Definition at line 969 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [37/43]

TEST	(	ODhashTable	,
		Stress_FillAndEmpty
	)

Definition at line 373 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::iota(), keys, rng, Aleph::shuffle(), and tbl.

TEST() [38/43]

TEST	(	ODhashTable	,
		Stress_InsertRemoveCycles
	)

Definition at line 447 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [39/43]

TEST	(	ODhashTable	,
		Stress_ManyCollisions
	)

Definition at line 411 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [40/43]

TEST	(	ODhashTable	,
		Stress_ResizeOperations
	)

Definition at line 478 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), rng, and tbl.

TEST() [41/43]

TEST	(	ODhashTable	,
		Stress_SearchOrInsertWithDeleted
	)

Definition at line 755 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [42/43]

TEST	(	ODhashTable	,
		Stress_StringKeys
	)

Definition at line 630 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), random_string(), rng, and tbl.

TEST() [43/43]

TEST	(	ODhashTable	,
		Stress_WithAutoResize
	)

Definition at line 581 of file odhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), rng, and tbl.