A dynamic table for managing void pointers with index recycling. More...

#include <pointer_table.H>

Collaboration diagram for Pointer_Table:

Public Member Functions
	Pointer_Table (size_t initial_size=0)
	Constructs a Pointer_Table with optional initial capacity.

long	size () const noexcept
	Returns the current capacity of the pointer table.

long	busies () const noexcept
	Returns the number of pointers currently stored.

long	frees () const noexcept
	Returns the number of recyclable indices.

long	get_heap_index () const noexcept
	Returns the current heap index (high water mark).

long	get_threshold () const noexcept
	Returns the threshold size.

bool	is_empty () const noexcept
	Checks if the table is empty.

long	insert_pointer (void *ptr)
	Inserts a pointer and returns its assigned index.

void	remove_pointer (long i)
	Removes the pointer at the given index.

void *	get_pointer (long i) const
	Retrieves the pointer at the given index.

void *	verify_pointer (long i, void *ptr) const
	Verifies that a pointer matches the one stored at an index.

void	clear ()
	Clears all pointers from the table.

Static Public Attributes
static constexpr long	Null_Index = -1
	Sentinel value indicating an invalid or null index.

Private Member Functions
long	allocate_above_heap ()
	Allocates an index from the free table.

void	insert_in_free_table (long i)
	Adds an index to the free table for future reuse.

void	cleanup_free_table (long new_heap_index)
	Removes indices from free_table that are >= new_heap_index.

bool	is_valid_index (long i) const noexcept
	Checks if an index is within valid bounds.

bool	pointer_matches_with_index (long i, const void *ptr) const noexcept
	Checks if a pointer matches the one stored at an index.

bool	invariant () const
	Validates the internal consistency of the data structure.

Private Attributes
DynArray< void * >	pointer_table
	Array mapping indices to pointers.

DynArray< long >	free_table
	Stack of available indices for reuse.

long	num_pointers
	Count of currently stored pointers.

long	heap_index
	Next available index at the heap top.

long	threshold_size
	Minimum size to maintain (prevents excessive shrinking)

Detailed Description

A dynamic table for managing void pointers with index recycling.

Pointer_Table provides efficient storage and retrieval of void pointers using integer indices. When pointers are removed, their indices are recycled for future insertions, preventing unbounded index growth.

The data structure maintains two internal arrays:

A pointer array that maps indices to pointers
A free list that tracks available (recyclable) indices

Thread Safety: This class is NOT thread-safe. External synchronization is required for concurrent access.

Exception Safety

insert_pointer(): Strong guarantee (no state change on failure)
remove_pointer(): Strong guarantee (throws on invalid index)
verify_pointer(): Strong guarantee (throws on mismatch)

Author: Leandro Rabindranath León

Definition at line 110 of file pointer_table.H.

Constructor & Destructor Documentation

◆ Pointer_Table()

Pointer_Table::Pointer_Table ( size_t initial_size = 0 )

inline

Constructs a Pointer_Table with optional initial capacity.

Creates an empty pointer table with the specified initial capacity. The initial_size sets the threshold below which the table will not shrink, preventing excessive memory reallocation for tables that frequently grow and shrink.

Parameters

[in] initial_size Initial capacity and shrink threshold. Defaults to 0 (fully dynamic).

Complexity: O(initial_size) for initialization.

Example: Pointer_Table small_table; // Fully dynamic

Pointer_Table large_table(1000); // Pre-allocated, won't shrink below 1000

Pointer_Table
A dynamic table for managing void pointers with index recycling.
Definition pointer_table.H:111

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

Definition at line 303 of file pointer_table.H.

Member Function Documentation

◆ allocate_above_heap()

long Pointer_Table::allocate_above_heap ( )

inlineprivate

Allocates an index from the free table.

Attempts to reuse a previously freed index from the free table. This supports index recycling to minimize index growth.

Returns: A recyclable index, or Null_Index if none available.

Complexity: O(1) amortized.

Definition at line 137 of file pointer_table.H.

References Aleph::DynArray< T >::cut(), free_table, heap_index, Aleph::maps(), Null_Index, pointer_table, and Aleph::DynArray< T >::size().

Referenced by insert_pointer().

◆ busies()

long Pointer_Table::busies ( ) const

inlinenoexcept

Returns the number of pointers currently stored.

Returns: The count of non-null pointer entries.

Complexity: O(1).

Definition at line 332 of file pointer_table.H.

References num_pointers.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ cleanup_free_table()

void Pointer_Table::cleanup_free_table ( long new_heap_index )

inlineprivate

Removes indices from free_table that are >= new_heap_index.

When the heap contracts, indices that were in the free table but are now beyond the heap boundary must be removed. This maintains the invariant that all free_table indices are valid.

Parameters

[in] new_heap_index The new heap boundary.

Complexity: O(n) where n is the size of free_table.

Definition at line 184 of file pointer_table.H.

References Aleph::DynArray< T >::cut(), free_table, Aleph::maps(), and Aleph::DynArray< T >::size().

Referenced by remove_pointer().

◆ clear()

void Pointer_Table::clear ( )

inline

Clears all pointers from the table.

Removes all pointers and resets the table to its initial state. Does NOT delete the pointed-to objects - that is the caller's responsibility.

Complexity: O(n) where n is the current capacity.

Example: Pointer_Table table;

// ... insert many pointers ...

// Clear without deleting pointed objects

table.clear();

assert(table.is_empty());

Pointer_Table::is_empty
bool is_empty() const noexcept
Checks if the table is empty.
Definition pointer_table.H:377

Pointer_Table::clear
void clear()
Clears all pointers from the table.
Definition pointer_table.H:572

Definition at line 572 of file pointer_table.H.

References Aleph::DynArray< T >::cut(), free_table, heap_index, invariant(), Aleph::maps(), num_pointers, pointer_table, and threshold_size.

Referenced by TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ frees()

long Pointer_Table::frees ( ) const

inlinenoexcept

Returns the number of recyclable indices.

These are indices that were previously used but are now available for reuse via insert_pointer().

Returns: The count of free (recyclable) indices.

Complexity: O(1).

Definition at line 344 of file pointer_table.H.

References free_table, and Aleph::DynArray< T >::size().

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ get_heap_index()

long Pointer_Table::get_heap_index ( ) const

inlinenoexcept

Returns the current heap index (high water mark).

The heap index represents the next available index at the top of the allocation. All valid indices are in [0, heap_index).

Returns: The current heap index.

Complexity: O(1).

Definition at line 356 of file pointer_table.H.

References heap_index.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ get_pointer()

void * Pointer_Table::get_pointer ( long i ) const

inline

Retrieves the pointer at the given index.

Returns the pointer stored at index i without any validation. Use verify_pointer() if you need to confirm the pointer matches an expected value.

Parameters

[in] i The index to retrieve.

Returns: The pointer at index i, or nullptr if the slot is free.

Exceptions

std::range_error If i is out of valid range.

Complexity: O(1).

Definition at line 499 of file pointer_table.H.

References ah_range_error_if, heap_index, is_valid_index(), Aleph::maps(), and pointer_table.

◆ get_threshold()

long Pointer_Table::get_threshold ( ) const

inlinenoexcept

Returns the threshold size.

The threshold is the minimum size the table maintains. The table will not shrink below this size.

Returns: The threshold size.

Complexity: O(1).

Definition at line 368 of file pointer_table.H.

References threshold_size.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ insert_in_free_table()

void Pointer_Table::insert_in_free_table ( long i )

inlineprivate

Adds an index to the free table for future reuse.

Marks the given index as available by setting its pointer to nullptr and adding it to the free table stack.

Parameters

[in] i The index to mark as free. Must be valid and in use.

Precondition: 0 <= i < heap_index; pointer_table[i] != nullptr (index must be in use)

Complexity: O(1) amortized.

Definition at line 165 of file pointer_table.H.

References free_table, heap_index, Aleph::maps(), pointer_table, and Aleph::DynArray< T >::size().

Referenced by remove_pointer().

◆ insert_pointer()

long Pointer_Table::insert_pointer ( void * ptr )

inline

Inserts a pointer and returns its assigned index.

Adds the given pointer to the table, either reusing a previously freed index or allocating a new one at the heap top.

Parameters

[in] ptr The pointer to insert. May be nullptr (though this is discouraged as it complicates removal).

Returns: The index assigned to the pointer. Use this index for subsequent remove_pointer() or verify_pointer() calls.

Warning: Inserting nullptr is allowed but discouraged. It makes it impossible to distinguish between a free slot and an intentionally stored nullptr.

Complexity: O(1) amortized.

Example: Pointer_Table table;

int* p = new int(42);

long idx = table.insert_pointer(p);

// idx can now be used to retrieve or remove p

Pointer_Table::insert_pointer
long insert_pointer(void *ptr)
Inserts a pointer and returns its assigned index.
Definition pointer_table.H:405

Definition at line 405 of file pointer_table.H.

References allocate_above_heap(), heap_index, invariant(), Aleph::maps(), Null_Index, num_pointers, and pointer_table.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ invariant()

bool Pointer_Table::invariant ( ) const

inlineprivate

Validates the internal consistency of the data structure.

Checks that all invariants hold:

If empty: heap_index within threshold, free_table empty
If not empty: top of heap contains a non-null pointer
All free_table indices are valid and point to nullptr
num_pointers equals (heap_index - free_table.size())

Returns: true if all invariants hold, false otherwise.

Note: This method is intended for debugging and assertions. It has O(n) complexity due to free_table validation.

Definition at line 252 of file pointer_table.H.

References free_table, heap_index, Aleph::maps(), num_pointers, pointer_table, and Aleph::DynArray< T >::size().

Referenced by clear(), insert_pointer(), and remove_pointer().

◆ is_empty()

bool Pointer_Table::is_empty ( ) const

inlinenoexcept

Checks if the table is empty.

Returns: true if no pointers are stored, false otherwise.

Complexity: O(1).

Definition at line 377 of file pointer_table.H.

References num_pointers.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ is_valid_index()

bool Pointer_Table::is_valid_index ( long i ) const

inlineprivatenoexcept

Checks if an index is within valid bounds.

An index is valid if it is non-negative and less than the current heap index (the high water mark).

Parameters

[in] i The index to validate.

Returns: true if the index is within bounds, false otherwise.

Complexity: O(1).

Definition at line 217 of file pointer_table.H.

References heap_index, and Aleph::maps().

Referenced by get_pointer(), pointer_matches_with_index(), remove_pointer(), and verify_pointer().

◆ pointer_matches_with_index()

bool Pointer_Table::pointer_matches_with_index	(	long	i,
		const void *	ptr
	)		const

inlineprivatenoexcept

Checks if a pointer matches the one stored at an index.

Parameters

[in]	i	The index to check. Must be valid.
[in]	ptr	The pointer to compare against.

Returns: true if the stored pointer equals ptr, false otherwise.

Precondition: is_valid_index(i) must be true.

Complexity: O(1).

Definition at line 233 of file pointer_table.H.

References is_valid_index(), Aleph::maps(), and pointer_table.

Referenced by verify_pointer().

◆ remove_pointer()

void Pointer_Table::remove_pointer ( long i )

inline

Removes the pointer at the given index.

Removes the pointer at index i from the table. The index becomes available for reuse by subsequent insert_pointer() calls.

If the removed index is at the top of the heap, the heap contracts automatically, potentially freeing memory.

Parameters

[in] i The index of the pointer to remove.

Exceptions

std::range_error	If `i` is out of valid range.
std::domain_error	If index `i` is already free (nullptr).

Complexity: O(1) amortized for typical removals. O(n) worst case when removing from heap top triggers cleanup of free_table.

Example: Pointer_Table table;

int* p = new int(42);

long idx = table.insert_pointer(p);

delete p;

table.remove_pointer(idx); // Index now available for reuse

Pointer_Table::remove_pointer
void remove_pointer(long i)
Removes the pointer at the given index.
Definition pointer_table.H:449

Definition at line 449 of file pointer_table.H.

References ah_domain_error_if, ah_range_error_if, cleanup_free_table(), Aleph::DynArray< T >::cut(), heap_index, insert_in_free_table(), invariant(), is_valid_index(), Aleph::maps(), num_pointers, pointer_table, Aleph::DynArray< T >::size(), and threshold_size.

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ size()

long Pointer_Table::size ( ) const

inlinenoexcept

Returns the current capacity of the pointer table.

This is the size of the underlying array, not the number of pointers currently stored.

Returns: The current capacity (allocated size).

See also: busies() for the number of stored pointers.

Complexity: O(1).

Definition at line 323 of file pointer_table.H.

References pointer_table, and Aleph::DynArray< T >::size().

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ verify_pointer()

void * Pointer_Table::verify_pointer	(	long	i,
		void *	ptr
	)		const

inline

Verifies that a pointer matches the one stored at an index.

This method is useful for validating that a cached index still refers to the expected pointer, detecting use-after-free or index reuse scenarios.

Parameters

[in]	i	The index to verify.
[in]	ptr	The expected pointer value.

Returns: The pointer if verification succeeds (same as ptr).

Exceptions

std::range_error	If `i` is out of valid range.
std::domain_error	If the stored pointer doesn't match `ptr`.

Complexity: O(1).

Example: Pointer_Table table;

int* p = new int(42);

long idx = table.insert_pointer(p);

// Later, verify the pointer is still valid

try {

void* verified = table.verify_pointer(idx, p);

// Safe to use verified

} catch (const std::domain_error& e) {

// Pointer was replaced or removed

}

Pointer_Table::verify_pointer
void * verify_pointer(long i, void *ptr) const
Verifies that a pointer matches the one stored at an index.
Definition pointer_table.H:539

Definition at line 539 of file pointer_table.H.

References ah_domain_error_if, ah_range_error_if, heap_index, is_valid_index(), Aleph::maps(), and pointer_matches_with_index().

Member Data Documentation

◆ free_table

DynArray<long> Pointer_Table::free_table

private

Stack of available indices for reuse.

Definition at line 122 of file pointer_table.H.

Referenced by allocate_above_heap(), cleanup_free_table(), clear(), frees(), insert_in_free_table(), and invariant().

◆ heap_index

long Pointer_Table::heap_index

private

Next available index at the heap top.

Definition at line 124 of file pointer_table.H.

Referenced by allocate_above_heap(), clear(), get_heap_index(), get_pointer(), insert_in_free_table(), insert_pointer(), invariant(), is_valid_index(), remove_pointer(), and verify_pointer().

◆ Null_Index

constexpr long Pointer_Table::Null_Index = -1

staticconstexpr

Sentinel value indicating an invalid or null index.

This constant is used internally to indicate that no valid index is available (e.g., when the free table is empty).

Definition at line 118 of file pointer_table.H.

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

◆ num_pointers

long Pointer_Table::num_pointers

private

Count of currently stored pointers.

Definition at line 123 of file pointer_table.H.

Referenced by busies(), clear(), insert_pointer(), invariant(), is_empty(), and remove_pointer().

◆ pointer_table

DynArray<void *> Pointer_Table::pointer_table

private

Array mapping indices to pointers.

Definition at line 121 of file pointer_table.H.

Referenced by allocate_above_heap(), clear(), get_pointer(), insert_in_free_table(), insert_pointer(), invariant(), pointer_matches_with_index(), remove_pointer(), and size().

◆ threshold_size

long Pointer_Table::threshold_size

private

Minimum size to maintain (prevents excessive shrinking)

Definition at line 125 of file pointer_table.H.

Referenced by clear(), get_threshold(), and remove_pointer().

The documentation for this class was generated from the following file:

pointer_table.H

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Pointer_Table()

Member Function Documentation

◆ allocate_above_heap()

◆ busies()

◆ cleanup_free_table()

◆ clear()

◆ frees()

◆ get_heap_index()

◆ get_pointer()

◆ get_threshold()

◆ insert_in_free_table()

◆ insert_pointer()

◆ invariant()

◆ is_empty()

◆ is_valid_index()

◆ pointer_matches_with_index()

◆ remove_pointer()

◆ size()

◆ verify_pointer()

Member Data Documentation

◆ free_table

◆ heap_index

◆ Null_Index

◆ num_pointers

◆ pointer_table

◆ threshold_size