compact-cuckoo-filter.cc File Reference

Comprehensive tests for Compact_Cuckoo_Filter. More...

#include <gtest/gtest.h>
#include <cuckoo-filter.H>
#include <compact-cuckoo-filter.H>
#include <cstddef>
#include <string>
#include <set>
#include <random>
#include <vector>
#include <algorithm>

Include dependency graph for compact-cuckoo-filter.cc:

Go to the source code of this file.

Functions
	TEST (CompactCuckooFilterCtor, default_construction)
	TEST (CompactCuckooFilterCtor, custom_fingerprint_bits)
	TEST (CompactCuckooFilterCtor, custom_entries_per_bucket)
	TEST (CompactCuckooFilterCtor, memory_usage_is_compact)
	TEST (CompactCuckooFilterBasic, insert_and_contains_no_false_negatives)
	TEST (CompactCuckooFilterBasic, absent_elements_usually_not_found)
	TEST (CompactCuckooFilterBasic, duplicate_insert_stores_twice)
	TEST (CompactCuckooFilterBasic, string_keys)
	TEST (CompactCuckooFilterBasic, small_fingerprint_bits)
	TEST (CompactCuckooFilterBasic, large_fingerprint_bits)
	TEST (CompactCuckooFilterDelete, remove_existing_element)
	TEST (CompactCuckooFilterDelete, remove_nonexistent_is_noop)
	TEST (CompactCuckooFilterDelete, remove_duplicate_removes_one_copy)
	TEST (CompactCuckooFilterDelete, insert_after_remove)
	TEST (CompactCuckooFilterDelete, interleaved_insert_remove)
	TEST (CompactCuckooFilterCapacity, load_factor_computed_correctly)
	TEST (CompactCuckooFilterCapacity, high_load_factor_still_works)
	TEST (CompactCuckooFilterCapacity, insert_fails_when_full)
	TEST (CompactCuckooFilterIntrospection, memory_usage)
	TEST (CompactCuckooFilterIntrospection, load_factor)
	TEST (CompactCuckooFilterSemantics, copy_preserves_state)
	TEST (CompactCuckooFilterSemantics, move_transfers_state)
	TEST (CompactCuckooFilterClear, clears_all_state)
	TEST (CompactCuckooFilterClear, can_reuse_after_clear)
	TEST (CompactCuckooFilterFPRate, empirical_fp_rate_within_bounds)
	TEST (CompactCuckooFilterFPRate, low_fp_rate_with_large_fingerprint)
	TEST (CompactCuckooFilterStress, random_insertions_and_lookups)
	TEST (CompactCuckooFilterStress, sequential_insert_remove_cycles)
	TEST (CompactCuckooFilterStress, many_duplicates)
	TEST (CompactCuckooFilterEdge, tiny_filter)
	TEST (CompactCuckooFilterEdge, minimal_fingerprint_bits)
	TEST (CompactCuckooFilterEdge, maximal_fingerprint_bits)
	TEST (CompactCuckooFilterEdge, single_entry_per_bucket)
	TEST (CompactCuckooFilterComparison, same_behavior_as_standard)
	TEST (CompactCuckooFilterComparison, memory_savings_verified)
	TEST (CompactCuckooFilterComparison, performance_characteristics)

Detailed Description

Comprehensive tests for Compact_Cuckoo_Filter.

Definition in file compact-cuckoo-filter.cc.

Function Documentation

TEST() [1/36]

TEST	(	CompactCuckooFilterBasic	,
		absent_elements_usually_not_found
	)

Definition at line 107 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [2/36]

TEST	(	CompactCuckooFilterBasic	,
		duplicate_insert_stores_twice
	)

Definition at line 124 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [3/36]

TEST	(	CompactCuckooFilterBasic	,
		insert_and_contains_no_false_negatives
	)

Definition at line 94 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [4/36]

TEST	(	CompactCuckooFilterBasic	,
		large_fingerprint_bits
	)

Definition at line 165 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [5/36]

TEST	(	CompactCuckooFilterBasic	,
		small_fingerprint_bits
	)

Definition at line 153 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [6/36]

TEST	(	CompactCuckooFilterBasic	,
		string_keys
	)

Definition at line 138 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [7/36]

TEST	(	CompactCuckooFilterCapacity	,
		high_load_factor_still_works
	)

Definition at line 278 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [8/36]

TEST	(	CompactCuckooFilterCapacity	,
		insert_fails_when_full
	)

Definition at line 295 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [9/36]

TEST	(	CompactCuckooFilterCapacity	,
		load_factor_computed_correctly
	)

Definition at line 263 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [10/36]

TEST	(	CompactCuckooFilterClear	,
		can_reuse_after_clear
	)

Definition at line 386 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [11/36]

TEST	(	CompactCuckooFilterClear	,
		clears_all_state
	)

Definition at line 372 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [12/36]

TEST	(	CompactCuckooFilterComparison	,
		memory_savings_verified
	)

Definition at line 591 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [13/36]

TEST	(	CompactCuckooFilterComparison	,
		performance_characteristics
	)

Definition at line 610 of file compact-cuckoo-filter.cc.

References Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), and Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::size().

TEST() [14/36]

TEST	(	CompactCuckooFilterComparison	,
		same_behavior_as_standard
	)

Definition at line 567 of file compact-cuckoo-filter.cc.

References Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::insert(), and Aleph::Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::size().

TEST() [15/36]

TEST	(	CompactCuckooFilterCtor	,
		custom_entries_per_bucket
	)

Definition at line 69 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [16/36]

TEST	(	CompactCuckooFilterCtor	,
		custom_fingerprint_bits
	)

Definition at line 63 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [17/36]

TEST	(	CompactCuckooFilterCtor	,
		default_construction
	)

Definition at line 55 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [18/36]

TEST	(	CompactCuckooFilterCtor	,
		memory_usage_is_compact
	)

Definition at line 75 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [19/36]

TEST	(	CompactCuckooFilterDelete	,
		insert_after_remove
	)

Definition at line 224 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [20/36]

TEST	(	CompactCuckooFilterDelete	,
		interleaved_insert_remove
	)

Definition at line 237 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [21/36]

TEST	(	CompactCuckooFilterDelete	,
		remove_duplicate_removes_one_copy
	)

Definition at line 207 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [22/36]

TEST	(	CompactCuckooFilterDelete	,
		remove_existing_element
	)

Definition at line 181 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [23/36]

TEST	(	CompactCuckooFilterDelete	,
		remove_nonexistent_is_noop
	)

Definition at line 197 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [24/36]

TEST	(	CompactCuckooFilterEdge	,
		maximal_fingerprint_bits
	)

Definition at line 543 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [25/36]

TEST	(	CompactCuckooFilterEdge	,
		minimal_fingerprint_bits
	)

Definition at line 532 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [26/36]

TEST	(	CompactCuckooFilterEdge	,
		single_entry_per_bucket
	)

Definition at line 552 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [27/36]

TEST	(	CompactCuckooFilterEdge	,
		tiny_filter
	)

Definition at line 520 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [28/36]

TEST	(	CompactCuckooFilterFPRate	,
		empirical_fp_rate_within_bounds
	)

Definition at line 407 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [29/36]

TEST	(	CompactCuckooFilterFPRate	,
		low_fp_rate_with_large_fingerprint
	)

Definition at line 429 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [30/36]

TEST	(	CompactCuckooFilterIntrospection	,
		load_factor
	)

Definition at line 324 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [31/36]

TEST	(	CompactCuckooFilterIntrospection	,
		memory_usage
	)

Definition at line 313 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [32/36]

TEST	(	CompactCuckooFilterSemantics	,
		copy_preserves_state
	)

Definition at line 340 of file compact-cuckoo-filter.cc.

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

TEST() [33/36]

TEST	(	CompactCuckooFilterSemantics	,
		move_transfers_state
	)

Definition at line 354 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [34/36]

TEST	(	CompactCuckooFilterStress	,
		many_duplicates
	)

Definition at line 492 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [35/36]

TEST	(	CompactCuckooFilterStress	,
		random_insertions_and_lookups
	)

Definition at line 449 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp(), and rng.

TEST() [36/36]

TEST	(	CompactCuckooFilterStress	,
		sequential_insert_remove_cycles
	)

Definition at line 470 of file compact-cuckoo-filter.cc.

References Aleph::divide_and_conquer_partition_dp().