odhash.cc File Reference

Tests for Odhash. More...

#include <gtest/gtest.h>
#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 1154 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 104 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 109 of file odhash.cc.

References r, and Aleph::snd_hash_fct().

Referenced by TEST().

TEST() [1/43]

TEST	(	ODhashTable	,
		All
	)

Definition at line 1254 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [2/43]

TEST	(	ODhashTable	,
		ContainsOrInsert_WithCollisions
	)

Definition at line 720 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [3/43]

TEST	(	ODhashTable	,
		CopyAssignment
	)

Definition at line 901 of file odhash.cc.

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

TEST() [4/43]

TEST	(	ODhashTable	,
		CopyConstructor
	)

Definition at line 861 of file odhash.cc.

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

TEST() [5/43]

TEST	(	ODhashTable	,
		Debug_SearchOrInsertBug
	)

Definition at line 810 of file odhash.cc.

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

TEST() [6/43]

TEST	(	ODhashTable	,
		DuplicateInsertReturnsNull
	)

Definition at line 982 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [7/43]

TEST	(	ODhashTable	,
		EmptyTableOperations
	)

Definition at line 956 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [8/43]

TEST	(	ODhashTable	,
		Exists
	)

Definition at line 1264 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [9/43]

TEST	(	ODhashTable	,
		Filter
	)

Definition at line 1274 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [10/43]

TEST	(	ODhashTable	,
		Find
	)

Definition at line 1010 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [11/43]

TEST	(	ODhashTable	,
		ForEach
	)

Definition at line 1242 of file odhash.cc.

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

TEST() [12/43]

TEST	(	ODhashTable	,
		Fuzz_InterleavedOperations
	)

Definition at line 524 of file odhash.cc.

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

TEST() [13/43]

TEST	(	ODhashTable	,
		Fuzz_RandomOperationsWithOracle
	)

Definition at line 290 of file odhash.cc.

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

TEST() [14/43]

TEST	(	ODhashTable	,
		HasAndContains
	)

Definition at line 995 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [15/43]

TEST	(	ODhashTable	,
		IteratorBasic
	)

Definition at line 1088 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [16/43]

TEST	(	ODhashTable	,
		IteratorDelete
	)

Definition at line 1127 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [17/43]

TEST	(	ODhashTable	,
		IteratorEmpty
	)

Definition at line 1106 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [18/43]

TEST	(	ODhashTable	,
		IteratorSingleElement
	)

Definition at line 1114 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [19/43]

TEST	(	ODhashTable	,
		KeyToBucketRoundTrip
	)

Definition at line 144 of file odhash.cc.

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

TEST() [20/43]

TEST	(	ODhashTable	,
		ManualRehash
	)

Definition at line 1027 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [21/43]

TEST	(	ODhashTable	,
		Map
	)

Definition at line 115 of file odhash.cc.

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

TEST() [22/43]

TEST	(	ODhashTable	,
		MoveAssignment
	)

Definition at line 920 of file odhash.cc.

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

TEST() [23/43]

TEST	(	ODhashTable	,
		MoveConstructor
	)

Definition at line 883 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [24/43]

TEST	(	ODhashTable	,
		ProbeCounterCleanup_ChainCleanup
	)

Definition at line 1220 of file odhash.cc.

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

TEST() [25/43]

TEST	(	ODhashTable	,
		ProbeCounterCleanup_LastInChainBecomesEmpty
	)

Definition at line 1170 of file odhash.cc.

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

TEST() [26/43]

TEST	(	ODhashTable	,
		ProbeCounterCleanup_MiddleStaysDeleted
	)

Definition at line 1196 of file odhash.cc.

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

TEST() [27/43]

TEST	(	ODhashTable	,
		RemoveNonExistentDoesNotRehash
	)

Definition at line 254 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [28/43]

TEST	(	ODhashTable	,
		RemoveNonExistentKeyPreservesTableIntegrity
	)

Definition at line 162 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [29/43]

TEST	(	ODhashTable	,
		RemoveWithExternalKey
	)

Definition at line 208 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [30/43]

TEST	(	ODhashTable	,
		RemoveWithInternalKey
	)

Definition at line 233 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [31/43]

TEST	(	ODhashTable	,
		ResizeDown
	)

Definition at line 1069 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [32/43]

TEST	(	ODhashTable	,
		ResizeUp
	)

Definition at line 1052 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [33/43]

TEST	(	ODhashTable	,
		SearchOrInsert_WithDeletedEntries
	)

Definition at line 678 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [34/43]

TEST	(	ODhashTable	,
		SelfAssignment
	)

Definition at line 939 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [35/43]

TEST	(	ODhashTable	,
		Simplest
	)

Definition at line 49 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [36/43]

TEST	(	ODhashTable	,
		SingleElement
	)

Definition at line 968 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [37/43]

TEST	(	ODhashTable	,
		Stress_FillAndEmpty
	)

Definition at line 372 of file odhash.cc.

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

TEST() [38/43]

TEST	(	ODhashTable	,
		Stress_InsertRemoveCycles
	)

Definition at line 446 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [39/43]

TEST	(	ODhashTable	,
		Stress_ManyCollisions
	)

Definition at line 410 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [40/43]

TEST	(	ODhashTable	,
		Stress_ResizeOperations
	)

Definition at line 477 of file odhash.cc.

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

TEST() [41/43]

TEST	(	ODhashTable	,
		Stress_SearchOrInsertWithDeleted
	)

Definition at line 754 of file odhash.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [42/43]

TEST	(	ODhashTable	,
		Stress_StringKeys
	)

Definition at line 629 of file odhash.cc.

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

TEST() [43/43]

TEST	(	ODhashTable	,
		Stress_WithAutoResize
	)

Definition at line 580 of file odhash.cc.

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