pointer_table_test.cc File Reference

Exhaustive tests for Pointer_Table class. More...

#include <gtest/gtest.h>
#include <vector>
#include <set>
#include <random>
#include <algorithm>
#include <stdexcept>
#include <pointer_table.H>

Include dependency graph for pointer_table_test.cc:

Go to the source code of this file.

Classes
class	PointerTableConstructionTest
class	PointerTableInsertTest
class	PointerTableRemoveTest
class	PointerTableRecyclingTest
class	PointerTableHeapContractionTest
class	PointerTableVerifyTest
class	PointerTableGetTest
class	PointerTableClearTest
class	PointerTableThresholdTest
class	PointerTableEdgeCasesTest
class	PointerTableStressTest
class	PointerTableConsistencyTest
class	PointerTableConstTest
class	PointerTableMemoryPatternTest
class	PointerTableRegressionTest

Functions
	TEST_F (PointerTableConstructionTest, DefaultConstructor)
	TEST_F (PointerTableConstructionTest, ConstructorWithInitialSize)
	TEST_F (PointerTableConstructionTest, ConstructorWithZeroSize)
	TEST_F (PointerTableConstructionTest, ConstructorWithLargeSize)
	TEST_F (PointerTableInsertTest, InsertSinglePointer)
	TEST_F (PointerTableInsertTest, InsertMultiplePointers)
	TEST_F (PointerTableInsertTest, InsertSamePointerTwice)
	TEST_F (PointerTableInsertTest, InsertManyPointers)
	TEST_F (PointerTableRemoveTest, RemoveSinglePointer)
	TEST_F (PointerTableRemoveTest, RemoveFromMiddle)
	TEST_F (PointerTableRemoveTest, RemoveFromEnd)
	TEST_F (PointerTableRemoveTest, RemoveFromBeginning)
	TEST_F (PointerTableRemoveTest, RemoveAllPointers)
	TEST_F (PointerTableRemoveTest, RemoveInvalidIndexThrows)
	TEST_F (PointerTableRemoveTest, RemoveAlreadyFreeIndexThrows)
	TEST_F (PointerTableRecyclingTest, RecyclesSingleIndex)
	TEST_F (PointerTableRecyclingTest, RecyclesMultipleIndices)
	TEST_F (PointerTableRecyclingTest, RecyclesBeforeGrowingHeap)
	TEST_F (PointerTableHeapContractionTest, BasicHeapContraction)
	TEST_F (PointerTableHeapContractionTest, HeapContractionWithFreeTableCleanup)
	TEST_F (PointerTableHeapContractionTest, MultipleContractionLevels)
	TEST_F (PointerTableHeapContractionTest, ContractionAfterRemovingConsecutive)
	TEST_F (PointerTableVerifyTest, VerifyCorrectPointer)
	TEST_F (PointerTableVerifyTest, VerifyIncorrectPointerThrows)
	TEST_F (PointerTableVerifyTest, VerifyInvalidIndexThrows)
	TEST_F (PointerTableVerifyTest, VerifyAfterRemoveThrows)
	TEST_F (PointerTableGetTest, GetValidPointer)
	TEST_F (PointerTableGetTest, GetMultiplePointers)
	TEST_F (PointerTableGetTest, GetInvalidIndexThrows)
	TEST_F (PointerTableGetTest, GetFreedSlotReturnsNull)
	TEST_F (PointerTableClearTest, ClearEmptyTable)
	TEST_F (PointerTableClearTest, ClearNonEmptyTable)
	TEST_F (PointerTableClearTest, ClearPreservesThreshold)
	TEST_F (PointerTableClearTest, ClearWithFreeEntries)
	TEST_F (PointerTableThresholdTest, DoesNotShrinkBelowThreshold)
	TEST_F (PointerTableThresholdTest, ZeroThresholdAllowsFullShrink)
	TEST_F (PointerTableEdgeCasesTest, RemoveOnlyElement)
	TEST_F (PointerTableEdgeCasesTest, AlternatingInsertRemove)
	TEST_F (PointerTableEdgeCasesTest, RemoveInReverseOrder)
	TEST_F (PointerTableEdgeCasesTest, RemoveInForwardOrder)
	TEST_F (PointerTableStressTest, RandomOperations)
	TEST_F (PointerTableStressTest, InterleavedPatterns)
	TEST_F (PointerTableStressTest, MassiveGrowthAndShrink)
	TEST_F (PointerTableStressTest, HeapContractionStress)
	TEST_F (PointerTableConsistencyTest, CountsRemainConsistent)
	TEST_F (PointerTableConsistencyTest, HeapIndexNeverExceedsBusiesPlusFrees)
	TEST (PointerTableNullIndexTest, NullIndexIsNegative)
	TEST_F (PointerTableConstTest, ConstMethodsWork)
	TEST_F (PointerTableMemoryPatternTest, SawtoothPattern)
	TEST_F (PointerTableMemoryPatternTest, FragmentedPattern)
	TEST_F (PointerTableRegressionTest, BugFix_FreeTableNotCleanedOnContraction)
	TEST_F (PointerTableRegressionTest, BugFix_CompleteContractionCleansAllFree)
int	main (int argc, char **argv)

Detailed Description

Exhaustive tests for Pointer_Table class.

These tests cover all operations including edge cases and critical scenarios:

• Basic operations (insert, remove, verify)
• Index recycling behavior
• Heap contraction with free_table cleanup (critical bug fix)
• Exception handling
• Stress tests with random operations
• Memory management and threshold behavior

Definition in file pointer_table_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 1112 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST()

TEST	(	PointerTableNullIndexTest	,
		NullIndexIsNegative
	)

Definition at line 938 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::Null_Index.

TEST_F() [1/51]

TEST_F	(	PointerTableClearTest	,
		ClearEmptyTable
	)

Definition at line 558 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::busies(), Pointer_Table::clear(), Pointer_Table::frees(), and Pointer_Table::is_empty().

TEST_F() [2/51]

TEST_F	(	PointerTableClearTest	,
		ClearNonEmptyTable
	)

Definition at line 568 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::busies(), Pointer_Table::clear(), Pointer_Table::frees(), Pointer_Table::get_heap_index(), Pointer_Table::insert_pointer(), and Pointer_Table::is_empty().

TEST_F() [3/51]

TEST_F	(	PointerTableClearTest	,
		ClearPreservesThreshold
	)

Definition at line 583 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::clear(), Pointer_Table::get_threshold(), Pointer_Table::insert_pointer(), and Pointer_Table::is_empty().

TEST_F() [4/51]

TEST_F	(	PointerTableClearTest	,
		ClearWithFreeEntries
	)

Definition at line 595 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::clear(), Pointer_Table::frees(), Pointer_Table::insert_pointer(), Pointer_Table::is_empty(), and Pointer_Table::remove_pointer().

TEST_F() [5/51]

TEST_F	(	PointerTableConsistencyTest	,
		CountsRemainConsistent
	)

Definition at line 883 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [6/51]

TEST_F	(	PointerTableConsistencyTest	,
		HeapIndexNeverExceedsBusiesPlusFrees
	)

Definition at line 912 of file pointer_table_test.cc.

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

TEST_F() [7/51]

TEST_F	(	PointerTableConstructionTest	,
		ConstructorWithInitialSize
	)

Definition at line 79 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::busies(), Pointer_Table::frees(), Pointer_Table::get_heap_index(), Pointer_Table::get_threshold(), and Pointer_Table::is_empty().

TEST_F() [8/51]

TEST_F	(	PointerTableConstructionTest	,
		ConstructorWithLargeSize
	)

Definition at line 98 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::get_threshold(), and Pointer_Table::is_empty().

TEST_F() [9/51]

TEST_F	(	PointerTableConstructionTest	,
		ConstructorWithZeroSize
	)

Definition at line 90 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::get_threshold(), and Pointer_Table::is_empty().

TEST_F() [10/51]

TEST_F	(	PointerTableConstructionTest	,
		DefaultConstructor
	)

Definition at line 67 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::busies(), Pointer_Table::frees(), Pointer_Table::get_heap_index(), Pointer_Table::get_threshold(), Pointer_Table::is_empty(), and Pointer_Table::size().

TEST_F() [11/51]

TEST_F	(	PointerTableConstTest	,
		ConstMethodsWork
	)

Definition at line 954 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::busies(), Pointer_Table::frees(), Pointer_Table::get_heap_index(), Pointer_Table::get_threshold(), Pointer_Table::insert_pointer(), Pointer_Table::is_empty(), and Pointer_Table::size().

TEST_F() [12/51]

TEST_F	(	PointerTableEdgeCasesTest	,
		AlternatingInsertRemove
	)

Definition at line 673 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [13/51]

TEST_F	(	PointerTableEdgeCasesTest	,
		RemoveInForwardOrder
	)

Definition at line 708 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [14/51]

TEST_F	(	PointerTableEdgeCasesTest	,
		RemoveInReverseOrder
	)

Definition at line 686 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [15/51]

TEST_F	(	PointerTableEdgeCasesTest	,
		RemoveOnlyElement
	)

Definition at line 662 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::insert_pointer().

TEST_F() [16/51]

TEST_F	(	PointerTableGetTest	,
		GetFreedSlotReturnsNull
	)

Definition at line 538 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [17/51]

TEST_F	(	PointerTableGetTest	,
		GetInvalidIndexThrows
	)

Definition at line 530 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [18/51]

TEST_F	(	PointerTableGetTest	,
		GetMultiplePointers
	)

Definition at line 519 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [19/51]

TEST_F	(	PointerTableGetTest	,
		GetValidPointer
	)

Definition at line 511 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::insert_pointer().

TEST_F() [20/51]

TEST_F	(	PointerTableHeapContractionTest	,
		BasicHeapContraction
	)

Definition at line 352 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::insert_pointer().

TEST_F() [21/51]

TEST_F	(	PointerTableHeapContractionTest	,
		ContractionAfterRemovingConsecutive
	)

Definition at line 432 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [22/51]

TEST_F	(	PointerTableHeapContractionTest	,
		HeapContractionWithFreeTableCleanup
	)

Definition at line 368 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [23/51]

TEST_F	(	PointerTableHeapContractionTest	,
		MultipleContractionLevels
	)

Definition at line 406 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [24/51]

TEST_F	(	PointerTableInsertTest	,
		InsertManyPointers
	)

Definition at line 149 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [25/51]

TEST_F	(	PointerTableInsertTest	,
		InsertMultiplePointers
	)

Definition at line 127 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [26/51]

TEST_F	(	PointerTableInsertTest	,
		InsertSamePointerTwice
	)

Definition at line 140 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [27/51]

TEST_F	(	PointerTableInsertTest	,
		InsertSinglePointer
	)

Definition at line 117 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::insert_pointer().

TEST_F() [28/51]

TEST_F	(	PointerTableMemoryPatternTest	,
		FragmentedPattern
	)

Definition at line 1010 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [29/51]

TEST_F	(	PointerTableMemoryPatternTest	,
		SawtoothPattern
	)

Definition at line 982 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [30/51]

TEST_F	(	PointerTableRecyclingTest	,
		RecyclesBeforeGrowingHeap
	)

Definition at line 309 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [31/51]

TEST_F	(	PointerTableRecyclingTest	,
		RecyclesMultipleIndices
	)

Definition at line 292 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [32/51]

TEST_F	(	PointerTableRecyclingTest	,
		RecyclesSingleIndex
	)

Definition at line 278 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::insert_pointer().

TEST_F() [33/51]

TEST_F	(	PointerTableRegressionTest	,
		BugFix_CompleteContractionCleansAllFree
	)

Definition at line 1084 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [34/51]

TEST_F	(	PointerTableRegressionTest	,
		BugFix_FreeTableNotCleanedOnContraction
	)

Definition at line 1048 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::insert_pointer().

TEST_F() [35/51]

TEST_F	(	PointerTableRemoveTest	,
		RemoveAllPointers
	)

Definition at line 233 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [36/51]

TEST_F	(	PointerTableRemoveTest	,
		RemoveAlreadyFreeIndexThrows
	)

Definition at line 258 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [37/51]

TEST_F	(	PointerTableRemoveTest	,
		RemoveFromBeginning
	)

Definition at line 218 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [38/51]

TEST_F	(	PointerTableRemoveTest	,
		RemoveFromEnd
	)

Definition at line 203 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [39/51]

TEST_F	(	PointerTableRemoveTest	,
		RemoveFromMiddle
	)

Definition at line 188 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [40/51]

TEST_F	(	PointerTableRemoveTest	,
		RemoveInvalidIndexThrows
	)

Definition at line 249 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [41/51]

TEST_F	(	PointerTableRemoveTest	,
		RemoveSinglePointer
	)

Definition at line 178 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::insert_pointer().

TEST_F() [42/51]

TEST_F	(	PointerTableStressTest	,
		HeapContractionStress
	)

Definition at line 841 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [43/51]

TEST_F	(	PointerTableStressTest	,
		InterleavedPatterns
	)

Definition at line 788 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [44/51]

TEST_F	(	PointerTableStressTest	,
		MassiveGrowthAndShrink
	)

Definition at line 818 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [45/51]

TEST_F	(	PointerTableStressTest	,
		RandomOperations
	)

Definition at line 743 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and rng.

TEST_F() [46/51]

TEST_F	(	PointerTableThresholdTest	,
		DoesNotShrinkBelowThreshold
	)

Definition at line 621 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::get_threshold(), Pointer_Table::insert_pointer(), Pointer_Table::remove_pointer(), and Pointer_Table::size().

TEST_F() [47/51]

TEST_F	(	PointerTableThresholdTest	,
		ZeroThresholdAllowsFullShrink
	)

Definition at line 637 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Pointer_Table::get_heap_index(), Pointer_Table::insert_pointer(), Pointer_Table::is_empty(), and Pointer_Table::remove_pointer().

TEST_F() [48/51]

TEST_F	(	PointerTableVerifyTest	,
		VerifyAfterRemoveThrows
	)

Definition at line 490 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [49/51]

TEST_F	(	PointerTableVerifyTest	,
		VerifyCorrectPointer
	)

Definition at line 467 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Pointer_Table::insert_pointer().

TEST_F() [50/51]

TEST_F	(	PointerTableVerifyTest	,
		VerifyIncorrectPointerThrows
	)

Definition at line 475 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST_F() [51/51]

TEST_F	(	PointerTableVerifyTest	,
		VerifyInvalidIndexThrows
	)

Definition at line 482 of file pointer_table_test.cc.

References Aleph::blossom_maximum_cardinality_matching().