hash-it.cc File Reference

Tests for Hash It. More...

#include <gtest/gtest.h>
#include <ahFunctional.H>
#include <ahSort.H>
#include <tpl_dynMapOhash.H>
#include <tpl_dynSetHash.H>
#include <tpl_olhash.H>
#include <tpl_odhash.H>
#include <tpl_lhash.H>
#include <stdexcept>
#include <functional>

Include dependency graph for hash-it.cc:

Go to the source code of this file.

Classes
struct	OHashTest< HashTbl >
struct	EmptyOHashTest< HashTbl >

Typedefs
using	P = pair< size_t, string >
using	HashTypes = Types< MapODhash< size_t, string >, MapOLhash< size_t, string >, DynMapLinHash< size_t, string >, DynMapHash< size_t, string > >

Functions
	TYPED_TEST_CASE_P (OHashTest)
	TYPED_TEST_CASE_P (EmptyOHashTest)
	TYPED_TEST_P (EmptyOHashTest, With_exception)
	TYPED_TEST_P (OHashTest, Without_exception)
	REGISTER_TYPED_TEST_CASE_P (EmptyOHashTest, With_exception)
	REGISTER_TYPED_TEST_CASE_P (OHashTest, Without_exception)
	INSTANTIATE_TYPED_TEST_CASE_P (Empty, EmptyOHashTest, HashTypes)
	INSTANTIATE_TYPED_TEST_CASE_P (NoEmpty, OHashTest, HashTypes)
	TEST (OLhashTable, DoubleHashCtorAndOps)
	TEST (OLhashTable, KeyToBucketRoundTrip)
	TEST (OLhashTable, RemoveThrowsOnMissingKey)
	TEST (OLhashTable, InsertRejectsDuplicate)
	TEST (OLhashTable, RemovePtrMarksDeleted)
	TEST (OLhashTable, NoResizeFillAndSearchMiss)
	TEST (OLhashTable, StatsWithDeletedAndBusy)
	TEST (OLhashTable, RehashKeepsElements)
	TEST (OLhashTable, ConstantHashCollisionsNoResize)
	TEST (OLhashTable, RehashAfterDeletesPreservesLiveKeys)
	TEST (OLhashTable, SearchOrInsertBehavior)
	TEST (OLhashTable, CopyMoveAndSwap)
	TEST (OLhashTable, StatsExtremes)
	TEST (OLhashTable, CleanTableLeavesEmpty)
	TEST (OLhashTable, InsertFailsWhenFullNoResize)
	TEST (OLhashTable, ResizeIncreasesCapacity)
	TEST (OLhashTable, DeletedSlotIsReused)
	TEST (ODhashTable, RemoveMissingInFullTableDoesNotHang)
	TEST (ODhashTable, DuplicateInsertAndSearchOrInsert)
	TEST (ODhashTable, CopyMoveAssignAndSwap)
	TEST (ODhashTable, StatsWithBusyDeletedEmpty)
	TEST (ODhashTable, CustomSecondHashSetter)
	TEST (ODhashTable, StatsAvgVarFinite)
	TEST (ODhashTable, StatsControlledProbes)
	TEST (ODhashTable, RehashWithResizeKeepsElements)
	TEST (ODhashTable, LinearProbePathCovered)
	TEST (ODhashTable, IteratorCollectsAllKeys)
	TEST (LhashTable, BusySlotsAfterLastRemoval)
	TEST (LhashTable, ShrinksWhenLoadFallsBelowLowerAlpha)
	TEST (LhashTable, IteratorDelRemovesAllCollidingBuckets)
	TEST (LhashTable, SearchOrInsertReturnsExisting)
	TEST (LhashTable, MoveSemanticsPreserveContent)
	TEST (LhashTable, InsertRejectsDuplicateAndSearchFinds)
	TEST (LhashTable, SearchNextReturnsNullWhenNoDuplicateKey)
	TEST (LhashTable, IteratorBoundsThrow)
	TEST (LhashTable, EmptyResetsCountersAndBuckets)
	TEST (LhashTable, RemoveAllBucketsFalseKeepsOwnership)
	TEST (LhashTable, SwapExchangesState)
	TEST (LhashTable, SetHashFunctionChangesDistribution)
	TEST (LhashTable, NoResizeModeKeepsCapacity)
	TEST (LhashTable, CustomComparatorActsAsEquality)
	TEST (LhashTable, CurrentAlphaNonZero)

Variables
constexpr size_t	N = 1000

Detailed Description

Tests for Hash It.

Definition in file hash-it.cc.

Typedef Documentation

HashTypes

using HashTypes = Types<MapODhash<size_t, string>, MapOLhash<size_t, string>, DynMapLinHash<size_t, string>, DynMapHash<size_t, string> >

Definition at line 123 of file hash-it.cc.

P

using P = pair<size_t, string>

Definition at line 53 of file hash-it.cc.

Function Documentation

INSTANTIATE_TYPED_TEST_CASE_P() [1/2]

INSTANTIATE_TYPED_TEST_CASE_P	(	Empty	,
		EmptyOHashTest	,
		HashTypes
	)

INSTANTIATE_TYPED_TEST_CASE_P() [2/2]

INSTANTIATE_TYPED_TEST_CASE_P	(	NoEmpty	,
		OHashTest	,
		HashTypes
	)

REGISTER_TYPED_TEST_CASE_P() [1/2]

REGISTER_TYPED_TEST_CASE_P	(	EmptyOHashTest	,
		With_exception
	)

REGISTER_TYPED_TEST_CASE_P() [2/2]

REGISTER_TYPED_TEST_CASE_P	(	OHashTest	,
		Without_exception
	)

TEST() [1/42]

TEST	(	LhashTable	,
		BusySlotsAfterLastRemoval
	)

Definition at line 569 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [2/42]

TEST	(	LhashTable	,
		CurrentAlphaNonZero
	)

Definition at line 863 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [3/42]

TEST	(	LhashTable	,
		CustomComparatorActsAsEquality
	)

Definition at line 841 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [4/42]

TEST	(	LhashTable	,
		EmptyResetsCountersAndBuckets
	)

Definition at line 739 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, Aleph::Dlink::insert(), k, and tbl.

TEST() [5/42]

TEST	(	LhashTable	,
		InsertRejectsDuplicateAndSearchFinds
	)

Definition at line 672 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [6/42]

TEST	(	LhashTable	,
		IteratorBoundsThrow
	)

Definition at line 714 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Dlink::insert(), and tbl.

TEST() [7/42]

TEST	(	LhashTable	,
		IteratorDelRemovesAllCollidingBuckets
	)

Definition at line 617 of file hash-it.cc.

References Aleph::Dlink::del(), Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, k, and tbl.

TEST() [8/42]

TEST	(	LhashTable	,
		MoveSemanticsPreserveContent
	)

Definition at line 653 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::GenLhashTable< Key, BucketType, Cmp >::insert(), and Aleph::GenLhashTable< Key, BucketType, Cmp >::is_empty().

TEST() [9/42]

TEST	(	LhashTable	,
		NoResizeModeKeepsCapacity
	)

Definition at line 825 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, Aleph::Dlink::insert(), k, and tbl.

TEST() [10/42]

TEST	(	LhashTable	,
		RemoveAllBucketsFalseKeepsOwnership
	)

Definition at line 755 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [11/42]

TEST	(	LhashTable	,
		SearchNextReturnsNullWhenNoDuplicateKey
	)

Definition at line 691 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [12/42]

TEST	(	LhashTable	,
		SearchOrInsertReturnsExisting
	)

Definition at line 637 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [13/42]

TEST	(	LhashTable	,
		SetHashFunctionChangesDistribution
	)

Definition at line 803 of file hash-it.cc.

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

TEST() [14/42]

TEST	(	LhashTable	,
		ShrinksWhenLoadFallsBelowLowerAlpha
	)

Definition at line 591 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [15/42]

TEST	(	LhashTable	,
		SwapExchangesState
	)

Definition at line 771 of file hash-it.cc.

References Aleph::GenLhashTable< Key, BucketType, Cmp >::capacity(), Aleph::divide_and_conquer_partition_dp(), Aleph::GenLhashTable< Key, BucketType, Cmp >::insert(), Aleph::GenLhashTable< Key, BucketType, Cmp >::remove(), Aleph::GenLhashTable< Key, BucketType, Cmp >::search(), Aleph::GenLhashTable< Key, BucketType, Cmp >::size(), and Aleph::GenLhashTable< Key, BucketType, Cmp >::swap().

TEST() [16/42]

TEST	(	ODhashTable	,
		CopyMoveAssignAndSwap
	)

Definition at line 445 of file hash-it.cc.

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

TEST() [17/42]

TEST	(	ODhashTable	,
		CustomSecondHashSetter
	)

Definition at line 490 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), k, Aleph::ODhashTable< Key, Cmp >::set_second_hash_fct(), and tbl.

TEST() [18/42]

TEST	(	ODhashTable	,
		DuplicateInsertAndSearchOrInsert
	)

Definition at line 432 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [19/42]

TEST	(	ODhashTable	,
		IteratorCollectsAllKeys
	)

Definition at line 549 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [20/42]

TEST	(	ODhashTable	,
		LinearProbePathCovered
	)

Definition at line 540 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [21/42]

TEST	(	ODhashTable	,
		RehashWithResizeKeepsElements
	)

Definition at line 523 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [22/42]

TEST	(	ODhashTable	,
		RemoveMissingInFullTableDoesNotHang
	)

Definition at line 415 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [23/42]

TEST	(	ODhashTable	,
		StatsAvgVarFinite
	)

Definition at line 499 of file hash-it.cc.

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

TEST() [24/42]

TEST	(	ODhashTable	,
		StatsControlledProbes
	)

Definition at line 508 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [25/42]

TEST	(	ODhashTable	,
		StatsWithBusyDeletedEmpty
	)

Definition at line 476 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [26/42]

TEST	(	OLhashTable	,
		CleanTableLeavesEmpty
	)

Definition at line 363 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [27/42]

TEST	(	OLhashTable	,
		ConstantHashCollisionsNoResize
	)

Definition at line 247 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [28/42]

TEST	(	OLhashTable	,
		CopyMoveAndSwap
	)

Definition at line 297 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, OhashCommon< HashTbl, Key >::insert(), Aleph::OLhashTable< Key, Cmp >::search(), OhashCommon< HashTbl, Key >::size(), and Aleph::OLhashTable< Key, Cmp >::swap().

TEST() [29/42]

TEST	(	OLhashTable	,
		DeletedSlotIsReused
	)

Definition at line 401 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [30/42]

TEST	(	OLhashTable	,
		DoubleHashCtorAndOps
	)

Definition at line 135 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [31/42]

TEST	(	OLhashTable	,
		InsertFailsWhenFullNoResize
	)

Definition at line 373 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [32/42]

TEST	(	OLhashTable	,
		InsertRejectsDuplicate
	)

Definition at line 175 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [33/42]

TEST	(	OLhashTable	,
		KeyToBucketRoundTrip
	)

Definition at line 155 of file hash-it.cc.

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

TEST() [34/42]

TEST	(	OLhashTable	,
		NoResizeFillAndSearchMiss
	)

Definition at line 198 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [35/42]

TEST	(	OLhashTable	,
		RehashAfterDeletesPreservesLiveKeys
	)

Definition at line 263 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [36/42]

TEST	(	OLhashTable	,
		RehashKeepsElements
	)

Definition at line 231 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [37/42]

TEST	(	OLhashTable	,
		RemovePtrMarksDeleted
	)

Definition at line 186 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TEST() [38/42]

TEST	(	OLhashTable	,
		RemoveThrowsOnMissingKey
	)

Definition at line 168 of file hash-it.cc.

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

TEST() [39/42]

TEST	(	OLhashTable	,
		ResizeIncreasesCapacity
	)

Definition at line 384 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [40/42]

TEST	(	OLhashTable	,
		SearchOrInsertBehavior
	)

Definition at line 287 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TEST() [41/42]

TEST	(	OLhashTable	,
		StatsExtremes
	)

Definition at line 343 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, and Aleph::hash_default_upper_alpha.

TEST() [42/42]

TEST	(	OLhashTable	,
		StatsWithDeletedAndBusy
	)

Definition at line 208 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::hash_default_lower_alpha, Aleph::hash_default_upper_alpha, and tbl.

TYPED_TEST_CASE_P() [1/2]

TYPED_TEST_CASE_P

(

EmptyOHashTest

)

TYPED_TEST_CASE_P() [2/2]

TYPED_TEST_CASE_P

(

OHashTest

)

TYPED_TEST_P() [1/2]

TYPED_TEST_P	(	EmptyOHashTest	,
		With_exception
	)

Definition at line 82 of file hash-it.cc.

References Aleph::divide_and_conquer_partition_dp(), and tbl.

TYPED_TEST_P() [2/2]

TYPED_TEST_P	(	OHashTest	,
		Without_exception
	)

Definition at line 91 of file hash-it.cc.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynList< T >::empty(), l, FunctionalMethods< Container, T >::maps(), N, Aleph::sort(), and tbl.

Variable Documentation

N

constexpr size_t N = 1000

constexpr

Definition at line 55 of file hash-it.cc.

Referenced by TYPED_TEST_P().