olhash.cc File Reference

Tests for Olhash. More...

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

Include dependency graph for olhash.cc:

Go to the source code of this file.

Classes
struct	MyRecord
struct	MyRecord::Eq
struct	BucketStats

Functions
	TEST (OLhashTable, Simplest)
size_t	my_hash (const MyRecord &r) noexcept
	TEST (OLhashTable, Map)
	TEST (OLhashTable, KeyToBucketRoundTrip)
	TEST (OLhashTable, RemoveNonExistentKeyPreservesTableIntegrity)
	TEST (OLhashTable, RemoveWithExternalKey)
	TEST (OLhashTable, RemoveWithInternalKey)
	TEST (OLhashTable, ManyCollisions)
	TEST (OLhashTable, RemoveNonExistentDoesNotChangeCapacity)
	TEST (OLhashTable, Fuzz_RandomOperationsWithOracle)
	TEST (OLhashTable, Stress_FillAndEmpty)
	TEST (OLhashTable, Stress_LinearProbingCollisions)
	TEST (OLhashTable, Stress_InsertRemoveCycles)
	TEST (OLhashTable, Stress_ResizeOperations)
	TEST (OLhashTable, Fuzz_InterleavedOperations)
	TEST (OLhashTable, Stress_WithAutoResize)
template<typename HashTable >
BucketStats	count_bucket_states (const HashTable &tbl)
	TEST (OLhashTable, DeletedCleanup_LastInChainBecomesEmpty)
	TEST (OLhashTable, DeletedCleanup_BackwardPropagation)
	TEST (OLhashTable, DeletedCleanup_MiddleStaysDeleted)
	TEST (OLhashTable, DeletedCleanup_NoAccumulationAfterCycles)
	TEST (OLhashTable, DeletedCleanup_WrapAround)
	TEST (OLhashTable, DeletedCleanup_StressNoAccumulation)
	TEST (OLhashTable, CopyConstructor)
	TEST (OLhashTable, MoveConstructor)
	TEST (OLhashTable, CopyAssignment)
	TEST (OLhashTable, MoveAssignment)
	TEST (OLhashTable, SelfAssignment)
	TEST (OLhashTable, DeletedSlotReuse)
	TEST (OLhashTable, SearchOrInsert_NewKey)
	TEST (OLhashTable, SearchOrInsert_ExistingKey)
	TEST (OLhashTable, ContainsOrInsert_NewKey)
	TEST (OLhashTable, ContainsOrInsert_ExistingKey)
	TEST (OLhashTable, ManualRehash)
	TEST (OLhashTable, ResizeUp)
	TEST (OLhashTable, ResizeDown)
	TEST (OLhashTable, EmptyTableOperations)
	TEST (OLhashTable, SingleElement)
	TEST (OLhashTable, DuplicateInsertReturnsNull)
	TEST (OLhashTable, HasAndContains)
	TEST (OLhashTable, Find)
	TEST (OLhashTable, IteratorBasic)
	TEST (OLhashTable, IteratorEmpty)
	TEST (OLhashTable, IteratorSingleElement)
	TEST (OLhashTable, IteratorDelete)
	TEST (OLhashTable, StatsCorrectness)
	TEST (OLhashTable, ForEach)
	TEST (OLhashTable, All)
	TEST (OLhashTable, Exists)
	TEST (OLhashTable, Filter)

Detailed Description

Tests for Olhash.

Definition in file olhash.cc.

Function Documentation

count_bucket_states()

template<typename HashTable >

BucketStats count_bucket_states

(

const HashTable &

tbl

)

Definition at line 602 of file olhash.cc.

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

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

my_hash()

size_t my_hash ( const MyRecord &  r )

inlinenoexcept

Definition at line 104 of file olhash.cc.

References Aleph::dft_hash_fct(), and r.

Referenced by TEST().

TEST() [1/48]

TEST	(	OLhashTable	,
		All
	)

Definition at line 1237 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [2/48]

TEST	(	OLhashTable	,
		ContainsOrInsert_ExistingKey
	)

Definition at line 981 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [3/48]

TEST	(	OLhashTable	,
		ContainsOrInsert_NewKey
	)

Definition at line 970 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [4/48]

TEST	(	OLhashTable	,
		CopyAssignment
	)

Definition at line 859 of file olhash.cc.

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

TEST() [5/48]

TEST	(	OLhashTable	,
		CopyConstructor
	)

Definition at line 816 of file olhash.cc.

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

TEST() [6/48]

TEST	(	OLhashTable	,
		DeletedCleanup_BackwardPropagation
	)

Definition at line 649 of file olhash.cc.

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

TEST() [7/48]

TEST	(	OLhashTable	,
		DeletedCleanup_LastInChainBecomesEmpty
	)

Definition at line 618 of file olhash.cc.

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

TEST() [8/48]

TEST	(	OLhashTable	,
		DeletedCleanup_MiddleStaysDeleted
	)

Definition at line 684 of file olhash.cc.

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

TEST() [9/48]

TEST	(	OLhashTable	,
		DeletedCleanup_NoAccumulationAfterCycles
	)

Definition at line 711 of file olhash.cc.

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

TEST() [10/48]

TEST	(	OLhashTable	,
		DeletedCleanup_StressNoAccumulation
	)

Definition at line 769 of file olhash.cc.

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

TEST() [11/48]

TEST	(	OLhashTable	,
		DeletedCleanup_WrapAround
	)

Definition at line 738 of file olhash.cc.

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

TEST() [12/48]

TEST	(	OLhashTable	,
		DeletedSlotReuse
	)

Definition at line 914 of file olhash.cc.

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

TEST() [13/48]

TEST	(	OLhashTable	,
		DuplicateInsertReturnsNull
	)

Definition at line 1097 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [14/48]

TEST	(	OLhashTable	,
		EmptyTableOperations
	)

Definition at line 1067 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [15/48]

TEST	(	OLhashTable	,
		Exists
	)

Definition at line 1247 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [16/48]

TEST	(	OLhashTable	,
		Filter
	)

Definition at line 1257 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [17/48]

TEST	(	OLhashTable	,
		Find
	)

Definition at line 1125 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [18/48]

TEST	(	OLhashTable	,
		ForEach
	)

Definition at line 1225 of file olhash.cc.

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

TEST() [19/48]

TEST	(	OLhashTable	,
		Fuzz_InterleavedOperations
	)

Definition at line 511 of file olhash.cc.

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

TEST() [20/48]

TEST	(	OLhashTable	,
		Fuzz_RandomOperationsWithOracle
	)

Definition at line 313 of file olhash.cc.

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

TEST() [21/48]

TEST	(	OLhashTable	,
		HasAndContains
	)

Definition at line 1110 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [22/48]

TEST	(	OLhashTable	,
		IteratorBasic
	)

Definition at line 1142 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [23/48]

TEST	(	OLhashTable	,
		IteratorDelete
	)

Definition at line 1181 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [24/48]

TEST	(	OLhashTable	,
		IteratorEmpty
	)

Definition at line 1160 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [25/48]

TEST	(	OLhashTable	,
		IteratorSingleElement
	)

Definition at line 1168 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [26/48]

TEST	(	OLhashTable	,
		KeyToBucketRoundTrip
	)

Definition at line 138 of file olhash.cc.

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

TEST() [27/48]

TEST	(	OLhashTable	,
		ManualRehash
	)

Definition at line 997 of file olhash.cc.

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

TEST() [28/48]

TEST	(	OLhashTable	,
		ManyCollisions
	)

Definition at line 244 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [29/48]

TEST	(	OLhashTable	,
		Map
	)

Definition at line 109 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), my_hash(), tbl, and Aleph::to_string().

TEST() [30/48]

TEST	(	OLhashTable	,
		MoveAssignment
	)

Definition at line 878 of file olhash.cc.

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

TEST() [31/48]

TEST	(	OLhashTable	,
		MoveConstructor
	)

Definition at line 840 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [32/48]

TEST	(	OLhashTable	,
		RemoveNonExistentDoesNotChangeCapacity
	)

Definition at line 278 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [33/48]

TEST	(	OLhashTable	,
		RemoveNonExistentKeyPreservesTableIntegrity
	)

Definition at line 154 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [34/48]

TEST	(	OLhashTable	,
		RemoveWithExternalKey
	)

Definition at line 200 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [35/48]

TEST	(	OLhashTable	,
		RemoveWithInternalKey
	)

Definition at line 225 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [36/48]

TEST	(	OLhashTable	,
		ResizeDown
	)

Definition at line 1048 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [37/48]

TEST	(	OLhashTable	,
		ResizeUp
	)

Definition at line 1031 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [38/48]

TEST	(	OLhashTable	,
		SearchOrInsert_ExistingKey
	)

Definition at line 959 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [39/48]

TEST	(	OLhashTable	,
		SearchOrInsert_NewKey
	)

Definition at line 949 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [40/48]

TEST	(	OLhashTable	,
		SelfAssignment
	)

Definition at line 897 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [41/48]

TEST	(	OLhashTable	,
		Simplest
	)

Definition at line 49 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [42/48]

TEST	(	OLhashTable	,
		SingleElement
	)

Definition at line 1079 of file olhash.cc.

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

TEST() [43/48]

TEST	(	OLhashTable	,
		StatsCorrectness
	)

Definition at line 1200 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [44/48]

TEST	(	OLhashTable	,
		Stress_FillAndEmpty
	)

Definition at line 388 of file olhash.cc.

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

TEST() [45/48]

TEST	(	OLhashTable	,
		Stress_InsertRemoveCycles
	)

Definition at line 458 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [46/48]

TEST	(	OLhashTable	,
		Stress_LinearProbingCollisions
	)

Definition at line 423 of file olhash.cc.

References Aleph::blossom_maximum_cardinality_matching(), and tbl.

TEST() [47/48]

TEST	(	OLhashTable	,
		Stress_ResizeOperations
	)

Definition at line 486 of file olhash.cc.

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

TEST() [48/48]

TEST	(	OLhashTable	,
		Stress_WithAutoResize
	)

Definition at line 563 of file olhash.cc.

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