compact-quotient-filter.cc File Reference

Comprehensive tests for Compact_Quotient_Filter. More...

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

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

Go to the source code of this file.

Functions
	TEST (CompactQuotientFilterCtor, valid_parameters)
	TEST (CompactQuotientFilterCtor, rejects_invalid_q)
	TEST (CompactQuotientFilterCtor, rejects_invalid_r)
	TEST (CompactQuotientFilterCtor, rejects_q_plus_r_exceeds_64)
	TEST (CompactQuotientFilterCtor, from_capacity_creates_valid_filter)
	TEST (CompactQuotientFilterCtor, from_capacity_rejects_bad_args)
	TEST (CompactQuotientFilterCtor, memory_usage_is_compact)
	TEST (CompactQuotientFilterBasic, insert_and_contains_no_false_negatives)
	TEST (CompactQuotientFilterBasic, absent_elements_usually_not_found)
	TEST (CompactQuotientFilterBasic, duplicate_insert_is_idempotent)
	TEST (CompactQuotientFilterBasic, string_keys)
	TEST (CompactQuotientFilterBasic, small_remainder_bits)
	TEST (CompactQuotientFilterBasic, large_remainder_bits)
	TEST (CompactQuotientFilterDelete, remove_existing_element)
	TEST (CompactQuotientFilterDelete, remove_nonexistent_is_noop)
	TEST (CompactQuotientFilterDelete, remove_all_makes_empty)
	TEST (CompactQuotientFilterDelete, insert_after_remove)
	TEST (CompactQuotientFilterDelete, interleaved_insert_remove)
	TEST (CompactQuotientFilterCapacity, load_factor_computed_correctly)
	TEST (CompactQuotientFilterCapacity, overflow_throws)
	TEST (CompactQuotientFilterCapacity, high_load_factor_still_works)
	TEST (CompactQuotientFilterIntrospection, memory_usage)
	TEST (CompactQuotientFilterIntrospection, false_positive_rate)
	TEST (CompactQuotientFilterIntrospection, estimate_returns_valid_params)
	TEST (CompactQuotientFilterSemantics, copy_preserves_state)
	TEST (CompactQuotientFilterSemantics, move_transfers_state)
	TEST (CompactQuotientFilterSemantics, swap_works)
	TEST (CompactQuotientFilterClear, clears_all_state)
	TEST (CompactQuotientFilterClear, can_reuse_after_clear)
	TEST (CompactQuotientFilterMerge, merge_combines_elements)
	TEST (CompactQuotientFilterMerge, merge_rejects_mismatched_params)
	TEST (CompactQuotientFilterMerge, merge_rejects_mismatched_seed)
	TEST (CompactQuotientFilterMerge, merge_with_overlapping_elements)
	TEST (CompactQuotientFilterFPRate, empirical_fp_rate_within_bounds)
	TEST (CompactQuotientFilterFPRate, low_fp_rate_with_large_r)
	TEST (CompactQuotientFilterStress, random_insertions_and_lookups)
	TEST (CompactQuotientFilterStress, sequential_insert_remove_cycles)
	TEST (CompactQuotientFilterStress, collision_heavy_workload)
	TEST (CompactQuotientFilterEdge, single_slot_filter)
	TEST (CompactQuotientFilterEdge, minimal_remainder_bits)
	TEST (CompactQuotientFilterEdge, maximal_remainder_bits)
	TEST (CompactQuotientFilterEdge, wrap_around_behavior)
	TEST (CompactQuotientFilterComparison, same_behavior_as_standard)
	TEST (CompactQuotientFilterComparison, memory_savings_verified)

Detailed Description

Comprehensive tests for Compact_Quotient_Filter.

Definition in file compact-quotient-filter.cc.

Function Documentation

TEST() [1/44]

TEST	(	CompactQuotientFilterBasic	,
		absent_elements_usually_not_found
	)

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

References Aleph::divide_and_conquer_partition_dp().

TEST() [2/44]

TEST	(	CompactQuotientFilterBasic	,
		duplicate_insert_is_idempotent
	)

Definition at line 141 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [3/44]

TEST	(	CompactQuotientFilterBasic	,
		insert_and_contains_no_false_negatives
	)

Definition at line 111 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [4/44]

TEST	(	CompactQuotientFilterBasic	,
		large_remainder_bits
	)

Definition at line 184 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [5/44]

TEST	(	CompactQuotientFilterBasic	,
		small_remainder_bits
	)

Definition at line 169 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [6/44]

TEST	(	CompactQuotientFilterBasic	,
		string_keys
	)

Definition at line 154 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [7/44]

TEST	(	CompactQuotientFilterCapacity	,
		high_load_factor_still_works
	)

Definition at line 316 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [8/44]

TEST	(	CompactQuotientFilterCapacity	,
		load_factor_computed_correctly
	)

Definition at line 282 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [9/44]

TEST	(	CompactQuotientFilterCapacity	,
		overflow_throws
	)

Definition at line 293 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [10/44]

TEST	(	CompactQuotientFilterClear	,
		can_reuse_after_clear
	)

Definition at line 421 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [11/44]

TEST	(	CompactQuotientFilterClear	,
		clears_all_state
	)

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

References Aleph::divide_and_conquer_partition_dp().

TEST() [12/44]

TEST	(	CompactQuotientFilterComparison	,
		memory_savings_verified
	)

Definition at line 677 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Quotient_Filter< T >::memory_usage().

TEST() [13/44]

TEST	(	CompactQuotientFilterComparison	,
		same_behavior_as_standard
	)

Definition at line 652 of file compact-quotient-filter.cc.

References Aleph::Quotient_Filter< T >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Quotient_Filter< T >::insert(), seed, and Aleph::Quotient_Filter< T >::size().

TEST() [14/44]

TEST	(	CompactQuotientFilterCtor	,
		from_capacity_creates_valid_filter
	)

Definition at line 82 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Compact_Quotient_Filter< T >::from_capacity().

TEST() [15/44]

TEST	(	CompactQuotientFilterCtor	,
		from_capacity_rejects_bad_args
	)

Definition at line 89 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [16/44]

TEST	(	CompactQuotientFilterCtor	,
		memory_usage_is_compact
	)

Definition at line 96 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [17/44]

TEST	(	CompactQuotientFilterCtor	,
		rejects_invalid_q
	)

Definition at line 65 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [18/44]

TEST	(	CompactQuotientFilterCtor	,
		rejects_invalid_r
	)

Definition at line 71 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [19/44]

TEST	(	CompactQuotientFilterCtor	,
		rejects_q_plus_r_exceeds_64
	)

Definition at line 77 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [20/44]

TEST	(	CompactQuotientFilterCtor	,
		valid_parameters
	)

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

References Aleph::divide_and_conquer_partition_dp().

TEST() [21/44]

TEST	(	CompactQuotientFilterDelete	,
		insert_after_remove
	)

Definition at line 243 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [22/44]

TEST	(	CompactQuotientFilterDelete	,
		interleaved_insert_remove
	)

Definition at line 256 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [23/44]

TEST	(	CompactQuotientFilterDelete	,
		remove_all_makes_empty
	)

Definition at line 229 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [24/44]

TEST	(	CompactQuotientFilterDelete	,
		remove_existing_element
	)

Definition at line 203 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [25/44]

TEST	(	CompactQuotientFilterDelete	,
		remove_nonexistent_is_noop
	)

Definition at line 219 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [26/44]

TEST	(	CompactQuotientFilterEdge	,
		maximal_remainder_bits
	)

Definition at line 627 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [27/44]

TEST	(	CompactQuotientFilterEdge	,
		minimal_remainder_bits
	)

Definition at line 616 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [28/44]

TEST	(	CompactQuotientFilterEdge	,
		single_slot_filter
	)

Definition at line 604 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [29/44]

TEST	(	CompactQuotientFilterEdge	,
		wrap_around_behavior
	)

Definition at line 636 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [30/44]

TEST	(	CompactQuotientFilterFPRate	,
		empirical_fp_rate_within_bounds
	)

Definition at line 495 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [31/44]

TEST	(	CompactQuotientFilterFPRate	,
		low_fp_rate_with_large_r
	)

Definition at line 517 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [32/44]

TEST	(	CompactQuotientFilterIntrospection	,
		estimate_returns_valid_params
	)

Definition at line 349 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Compact_Quotient_Filter< T >::estimate().

TEST() [33/44]

TEST	(	CompactQuotientFilterIntrospection	,
		false_positive_rate
	)

Definition at line 342 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [34/44]

TEST	(	CompactQuotientFilterIntrospection	,
		memory_usage
	)

Definition at line 335 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [35/44]

TEST	(	CompactQuotientFilterMerge	,
		merge_combines_elements
	)

Definition at line 442 of file compact-quotient-filter.cc.

References Aleph::Compact_Quotient_Filter< T >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::insert(), and Aleph::Compact_Quotient_Filter< T >::merge().

TEST() [36/44]

TEST	(	CompactQuotientFilterMerge	,
		merge_rejects_mismatched_params
	)

Definition at line 458 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Compact_Quotient_Filter< T >::merge().

TEST() [37/44]

TEST	(	CompactQuotientFilterMerge	,
		merge_rejects_mismatched_seed
	)

Definition at line 466 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Compact_Quotient_Filter< T >::merge().

TEST() [38/44]

TEST	(	CompactQuotientFilterMerge	,
		merge_with_overlapping_elements
	)

Definition at line 474 of file compact-quotient-filter.cc.

References Aleph::Compact_Quotient_Filter< T >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::insert(), and Aleph::Compact_Quotient_Filter< T >::merge().

TEST() [39/44]

TEST	(	CompactQuotientFilterSemantics	,
		copy_preserves_state
	)

Definition at line 361 of file compact-quotient-filter.cc.

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

TEST() [40/44]

TEST	(	CompactQuotientFilterSemantics	,
		move_transfers_state
	)

Definition at line 376 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [41/44]

TEST	(	CompactQuotientFilterSemantics	,
		swap_works
	)

Definition at line 390 of file compact-quotient-filter.cc.

References Aleph::Compact_Quotient_Filter< T >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Compact_Quotient_Filter< T >::insert(), and Aleph::Compact_Quotient_Filter< T >::swap().

TEST() [42/44]

TEST	(	CompactQuotientFilterStress	,
		collision_heavy_workload
	)

Definition at line 580 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [43/44]

TEST	(	CompactQuotientFilterStress	,
		random_insertions_and_lookups
	)

Definition at line 537 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp(), and rng.

TEST() [44/44]

TEST	(	CompactQuotientFilterStress	,
		sequential_insert_remove_cycles
	)

Definition at line 558 of file compact-quotient-filter.cc.

References Aleph::divide_and_conquer_partition_dp().