Implements a GPU-accelerated skip list data structure optimized for efficient string operations. More...

Inheritance diagram for ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >:

Collaboration diagram for ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >:

Public Types
using	ST = SkipTrie< CHAR_T, CHAR_SIZE_BITS >

using	KEY_T = BitString< CHAR_T, CHAR_SIZE_BITS >

Public Types inherited from SkipTrie< CHAR_T, CHAR_SIZE_BITS >
using	KEY_T = BitString< CHAR_T, CHAR_SIZE_BITS >
	Alias for the key type used in the SkipTrie, based on `BitString`.

Public Member Functions
	ParallelSkipTrie (size_t max_size)
	Constructs a new ParallelSkipTrie with allocated GPU memory for parallel operations.

	~ParallelSkipTrie ()
	Destructor for the ParallelSkipTrie class.

bool	insert (const KEY_T *key) noexcept
	Inserts a new key into the skip list with a randomly generated height.

bool	insert (const KEY_T *key, size_t height) noexcept
	Inserts a new key into the skip list with a specified height.

Public Member Functions inherited from SkipTrie< CHAR_T, CHAR_SIZE_BITS >
	SkipTrie ()
	Constructs an empty SkipTrie.

bool	insert (const KEY_T *key) noexcept
	Inserts a new key into the skip list with a randomly generated height.

bool	insert (const KEY_T *key, size_t height) noexcept
	Inserts a new key into the skip list with a specified height.

bool	contains (const KEY_T *key) const noexcept
	Checks if a specific key exists within the skip list.

bool	remove (const KEY_T *key) noexcept
	Removes a key from the skip list.

std::ostream &	print (std::ostream &os) const noexcept
	Prints a textual representation of the skip list structure, layer by layer, to an output stream.

std::string	to_string () const noexcept
	Generates a string representation of the skip list structure.

size_t	size () const noexcept
	Returns the number of keys currently stored in the skip list.

size_t	height () const noexcept
	Returns the current maximum height of the skip list.

size_t	lcp (const KEY_T *key) const noexcept
	Calculates the Longest Common Prefix (LCP) between a given key and its position in the skip list search path.

size_t	lcp_with_others (const KEY_T *key) const noexcept
	Calculates the maximum Longest Common Prefix (LCP) between a given key and its immediate neighbors (predecessor and successor) at the base level.

std::vector< const KEY_T * >	suffix_search (const KEY_T *key) const noexcept
	Finds all keys in the skip list that have the given key as a prefix.

std::vector< const KEY_T * >	range_search (const KEY_T key1, const KEY_T key2) const noexcept
	Finds all keys within a specified lexicographical range [key1, key2).

std::unordered_map< size_t, size_t >	get_lcp_group_sizes () const noexcept
	Calculates the sizes of groups of consecutive nodes sharing the same LCP value at the base level.

Iterator	begin () const noexcept
	Returns an iterator pointing to the first key in the skip list (at the base level).

Iterator	end () const noexcept
	Returns an iterator pointing past the last key in the skip list (the tail sentinel at the base level).

Static Public Member Functions
static size_t	get_random_height ()
	Generates a random height for a new node based on a geometric distribution.

Static Public Member Functions inherited from SkipTrie< CHAR_T, CHAR_SIZE_BITS >
static size_t	get_random_height ()
	Generates a random height for a new node based on a geometric distribution.

Protected Types
using	EqualOrSuccessor = ST::EqualOrSuccessor
	Alias for the parent class's EqualOrSuccessor struct, used for search results.

using	ResultLCP = ST::ResultLCP
	Alias for the parent class's ResultLCP struct, used for comparison results.

Protected Member Functions
EqualOrSuccessor	find_equal_or_successor (const KEY_T *key, const bool require_level0) const noexcept
	Finds the node containing the exact key or its immediate successor, using parallel comparison.

ResultLCP	compare (const KEY_T key1, const KEY_T key2, size_t lcp) const noexcept
	Compares two keys using GPU-accelerated parallel comparison.

Protected Member Functions inherited from SkipTrie< CHAR_T, CHAR_SIZE_BITS >
void	add_layer () noexcept
	Adds a new, empty layer on top of the current skip list structure.

void	remove_layer () noexcept
	Removes the top-most layer of the skip list if it is empty (contains only sentinels).

std::shared_ptr< Node >	insert_recursive (const KEY_T key, Node curr, size_t height, Direction direction, size_t lcp, size_t current_height) noexcept
	Recursively finds the correct position and inserts links for a new node at a specific level and below.

Direction	iter_layer (const KEY_T key, Node &curr, Direction direction, size_t &lcp) const noexcept
	Iterates horizontally along a single layer to find the node preceding the insertion/search point for a given key.

virtual NodeLCP	find_first (const KEY_T *key, const bool require_level0=false) const noexcept
	Finds the node containing the exact key, returning the node and the search path LCP.

Protected Attributes
size_t	m_max_size
	Maximum total size of keys that can be stored, used for GPU memory allocation.

uintmax_t *	d_a
	Device (GPU) memory for parallel string comparison operations.

uintmax_t *	d_largeblock
	Large block of device (GPU) memory for more complex parallel operations.

size_t	m_comparison_size
	Current size (in characters) used for parallel comparisons, adjusted dynamically.

size_t	m_max_copied
	Tracks the maximum number of characters copied to the GPU during comparison operations.

Protected Attributes inherited from SkipTrie< CHAR_T, CHAR_SIZE_BITS >
size_t	m_size
	Stores the total number of keys (nodes) in the base level of the skip list.

size_t	m_height
	Stores the current maximum height (number of levels) of the skip list.

std::shared_ptr< Node >	m_head = nullptr
	Shared pointer to the head sentinel node of the top-most layer.

std::shared_ptr< Node >	m_lower_head = nullptr
	Shared pointer to the head sentinel node of the base layer (level 0).

std::shared_ptr< Node >	m_lower_tail = nullptr
	Shared pointer to the tail sentinel node of the base layer (level 0).

Additional Inherited Members
Related Symbols inherited from SkipTrie< CHAR_T, CHAR_SIZE_BITS >
template<typename CHAR_T , unsigned CHAR_SIZE_BITS>
std::ostream &	operator<< (std::ostream &os, const SkipTrie< CHAR_T, CHAR_SIZE_BITS > &ssl)
	Overload of the stream insertion operator (`<<`) for `SkipTrie`.

Detailed Description

template<typename CHAR_T, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>
class ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >

Implements a GPU-accelerated skip list data structure optimized for efficient string operations.

This class extends SkipTrie by implementing parallel comparison operations using CUDA. The primary performance enhancement comes from parallel key comparison (par_k_compare), which offloads string comparison work to the GPU. This is particularly effective for long strings or large datasets where sequential comparisons would otherwise become a bottleneck. The class maintains GPU memory buffers for performing these parallel operations efficiently.

Template Parameters

CHAR_T	The underlying character type used in the keys (`BitString`).
CHAR_SIZE_BITS	The number of significant bits per character in `CHAR_T`. Defaults to `sizeof(CHAR_T) * 8`.

See also: SkipTrie; BitString

Definition at line 46 of file ParallelSkipTrie.cuh.

Member Typedef Documentation

◆ EqualOrSuccessor

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::EqualOrSuccessor = ST::EqualOrSuccessor

protected

Alias for the parent class's EqualOrSuccessor struct, used for search results.

Definition at line 113 of file ParallelSkipTrie.cuh.

◆ KEY_T

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::KEY_T = BitString<CHAR_T, CHAR_SIZE_BITS>

Definition at line 51 of file ParallelSkipTrie.cuh.

◆ ResultLCP

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::ResultLCP = ST::ResultLCP

protected

Alias for the parent class's ResultLCP struct, used for comparison results.

Definition at line 129 of file ParallelSkipTrie.cuh.

◆ ST

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::ST = SkipTrie<CHAR_T, CHAR_SIZE_BITS>

Definition at line 49 of file ParallelSkipTrie.cuh.

Constructor & Destructor Documentation

◆ ParallelSkipTrie()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::ParallelSkipTrie ( size_t max_size )

Constructs a new ParallelSkipTrie with allocated GPU memory for parallel operations.

Initializes the skip list structure and allocates GPU memory buffers for parallel string comparisons. The size of the allocated memory is determined by the max_size parameter.

Parameters

max_size The maximum total size (in characters) of keys that will be stored in the trie, used to allocate sufficient GPU memory for parallel comparison operations.

Definition at line 150 of file ParallelSkipTrie.cuh.

    : ST(), m_max_size(max_size)
{
    // Calculate number of words needed to store max_size characters
    // Use ceiling division (max_size / ALPHA + potential remainder)
    size_t max_size_words = (max_size + KEY_T::ALPHA - 1) / KEY_T::ALPHA;
    
    // Allocate device memory for string comparison operations
    d_a = alloc_to_device<uintmax_t>(max_size_words);
    
    // Allocate larger block for more complex parallel operations
    d_largeblock = alloc_large_block_to_device(max_size_words);
}

◆ ~ParallelSkipTrie()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::~ParallelSkipTrie ( )

Destructor for the ParallelSkipTrie class.

Frees all GPU memory allocated for parallel comparison operations, including the device arrays used for string comparison.

Definition at line 165 of file ParallelSkipTrie.cuh.

{
    // Free GPU memory allocated for string comparison
    device_free(d_a);
    
    // Free GPU memory allocated for large block operations
    device_free(d_largeblock);
}

Member Function Documentation

◆ compare()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

auto ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::compare	(	const KEY_T *	key1,
		const KEY_T *	key2,
		size_t	lcp
	)		const

protectedvirtualnoexcept

Compares two keys using GPU-accelerated parallel comparison.

Overrides the parent class's method to use GPU-accelerated string comparison. Uses BitString::par_k_compare to perform the comparison on the GPU, significantly improving performance for long strings. Adaptively adjusts the comparison size (m_comparison_size) based on comparison results, doubling it when more characters need to be compared and halving it (but not below minimum) when the comparison is complete.

Parameters

key1	Pointer to the first `BitString` key.
key2	Pointer to the second `BitString` key.
lcp	The length of the known common prefix (in characters) from which to start the comparison.

Returns: ResultLCP A struct containing the comparison result (std::strong_ordering) and the total LCP length found.

See also: SkipTrie::compare; BitString::par_k_compare

Reimplemented from SkipTrie< CHAR_T, CHAR_SIZE_BITS >.

Definition at line 175 of file ParallelSkipTrie.cuh.

{
    // Initialize result with equality and starting LCP value
    ResultLCP result = { std::strong_ordering::equal, lcp };
 
    while (true)
    {
        // Perform parallel comparison on GPU using the current comparison size
        // This is the core GPU-accelerated operation that makes ParallelSkipTrie faster
        auto [comparison, next_lcp] = key1->par_k_compare(*key2, lcp, m_comparison_size, d_a, d_largeblock, m_max_copied);
 
        // Update the result with comparison outcome and new LCP length
        result.result = comparison;
        result.lcp = next_lcp;
 
        if (comparison == std::strong_ordering::equal)
        {
            // If both keys match completely, we're done
            if (result.lcp == key1->size() && result.lcp == key2->size())
            {
                return result;
            }
 
            // Keys match so far but are longer - double comparison size for next iteration
            // This adaptive sizing improves performance by processing more characters at once
            m_comparison_size *= 2;
            lcp = result.lcp;
        }
        else
        {
            // Found a difference between keys, exit the loop
            break;
        }
    }
 
    // Halve comparison size for future operations, but don't go below minimum
    // This adapts the comparison granularity for optimal performance
    m_comparison_size = std::max(KEY_T::MIN_PAR_COMPARE_CHAR_SIZE, m_comparison_size / 2);
 
    return result;
}

◆ find_equal_or_successor()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::EqualOrSuccessor ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::find_equal_or_successor	(	const KEY_T *	key,
		const bool	require_level0
	)		const

protectedvirtualnoexcept

Finds the node containing the exact key or its immediate successor, using parallel comparison.

Overrides the parent class's method to initialize GPU comparison parameters before performing the search. Resets the comparison state (m_comparison_size and m_max_copied) before delegating to the parent class implementation.

Parameters

key	A pointer to the `BitString` key to search for.
require_level0	If true, ensures the search descends fully to level 0 before returning the node.

Returns: EqualOrSuccessor A struct containing the found node (match or successor), an equality flag, and the search path LCP.

Note: This method resets the LCP calculation state as part of its operation.

See also: SkipTrie::find_equal_or_successor

Reimplemented from SkipTrie< CHAR_T, CHAR_SIZE_BITS >.

Definition at line 238 of file ParallelSkipTrie.cuh.

{
    // Reset GPU comparison parameters to their initial values
    // This ensures consistent behavior across multiple search operations
    m_comparison_size = KEY_T::MIN_PAR_COMPARE_CHAR_SIZE;
    m_max_copied = 0;
 
    // Delegate to parent class implementation after initializing GPU parameters
    // The actual comparisons will use the overridden compare() method which uses GPU acceleration
    return ST::find_equal_or_successor(key, require_level0);
}

◆ get_random_height()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

size_t SkipTrie< CHAR_T, CHAR_SIZE_BITS >::get_random_height ( )

static

Generates a random height for a new node based on a geometric distribution.

The height determines how many levels the new node will participate in. Uses a static random number generator (geometric distribution with p=0.5).

Returns: size_t The randomly generated height (number of levels above the base level).

Warning: Not thread-safe if called concurrently from multiple threads due to static generator usage.

Definition at line 73 of file SkipTrie.hpp.

{
    // Use static variables for random number generation.
    // Note: Not thread-safe if multiple threads call this concurrently.
    static std::random_device rd; // Obtain a random seed from the hardware device
    static std::mt19937 gen(rd()); // Seed the default random engine
    // static std::mt19937 gen(1); // Use for deterministic testing (fixed seed)
    static std::geometric_distribution<size_t> dist(0.5); // p=0.5 gives 50% chance of 0, 25% of 1, etc.
 
    return dist(gen);
}

◆ insert() [1/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

bool ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::insert ( const KEY_T * key )

noexcept

Inserts a new key into the skip list with a randomly generated height.

Calls get_random_height() to determine the height and then calls the height-specific insert method. Initializes the GPU comparison parameters before delegating to the parent class implementation.

Parameters

key	A pointer to the `BitString` key to insert. The ParallelSkipTrie stores this pointer directly.

Returns: bool True if the key was inserted successfully, false if the key already exists.

Warning: Key Lifetime: The lifetime of the object pointed to by key must exceed the lifetime of the ParallelSkipTrie.

See also: insert(const KEY_T*, size_t); get_random_height()

Definition at line 218 of file ParallelSkipTrie.cuh.

{
    // Call the height-specific insert with a random height
    // This follows skip list standard practice of randomized height assignment
    return insert(key, get_random_height());
}

◆ insert() [2/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

bool ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::insert	(	const KEY_T *	key,
		size_t	height
	)

noexcept

Inserts a new key into the skip list with a specified height.

Initializes the GPU comparison parameters (m_comparison_size, m_max_copied) before calling the parent class's implementation. Uses parallel comparison operations on the GPU for efficient string comparisons during the insertion process.

Parameters

key	A pointer to the `BitString` key to insert. The ParallelSkipTrie stores this pointer directly.
height	The height (number of levels above the base) for the new node.

Returns: bool True if the key was inserted successfully, false if the key already exists.

Warning: Key Lifetime: The lifetime of the object pointed to by key must exceed the lifetime of the ParallelSkipTrie.

See also: SkipTrie::insert

Definition at line 226 of file ParallelSkipTrie.cuh.

{
    // Reset the GPU comparison parameters to their initial values
    // This ensures optimal starting point for parallel comparison operations
    m_comparison_size = KEY_T::MIN_PAR_COMPARE_CHAR_SIZE;
    m_max_copied = 0;
 
    // Delegate to the parent class implementation after initializing GPU parameters
    return ST::insert(key, height);
}

Member Data Documentation

◆ d_a

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

uintmax_t* ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::d_a

protected

Device (GPU) memory for parallel string comparison operations.

Definition at line 101 of file ParallelSkipTrie.cuh.

◆ d_largeblock

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

uintmax_t* ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::d_largeblock

protected

Large block of device (GPU) memory for more complex parallel operations.

Definition at line 104 of file ParallelSkipTrie.cuh.

◆ m_comparison_size

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

size_t ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::m_comparison_size

mutableprotected

Current size (in characters) used for parallel comparisons, adjusted dynamically.

Definition at line 107 of file ParallelSkipTrie.cuh.

◆ m_max_copied

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

size_t ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::m_max_copied

mutableprotected

Tracks the maximum number of characters copied to the GPU during comparison operations.

Definition at line 110 of file ParallelSkipTrie.cuh.

◆ m_max_size

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

size_t ParallelSkipTrie< CHAR_T, CHAR_SIZE_BITS >::m_max_size

protected

Maximum total size of keys that can be stored, used for GPU memory allocation.

Definition at line 98 of file ParallelSkipTrie.cuh.

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

src/ParallelSkipTrie.cuh

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ EqualOrSuccessor

◆ KEY_T

◆ ResultLCP

◆ ST

Constructor & Destructor Documentation

◆ ParallelSkipTrie()

◆ ~ParallelSkipTrie()

Member Function Documentation

◆ compare()

◆ find_equal_or_successor()

◆ get_random_height()

◆ insert() [1/2]

◆ insert() [2/2]

Member Data Documentation

◆ d_a

◆ d_largeblock

◆ m_comparison_size

◆ m_max_copied

◆ m_max_size