Extends the ZipTrie class to incorporate parallel key comparisons leveraging GPU acceleration (CUDA). More...

Inheritance diagram for ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >:

Collaboration diagram for ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >:

Public Types
using	ZT = ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >
	Alias for the base ZipTrie class template instantiation for brevity.

using	LCP_T = typename ZT::LCP_T
	Alias for the LCP type used, inherited from the base class (`ZipTrie::LCP_T`).

using	KEY_T = typename ZT::KEY_T
	Alias for the Key type used, inherited from the base class (`ZipTrie::KEY_T`).

using	SearchResults = typename ZT::SearchResults
	Removes a node with a given key from the zip tree. (Not implemented)

Public Types inherited from ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >
using	LCP_T = std::conditional_t< MEMORY_EFFICIENT, MemoryEfficientLCP, unsigned >
	The type used to store Longest Common Prefix values.

using	KEY_T = BitString< CHAR_T, CHAR_SIZE_BITS >
	The type used for keys, an instantiation of the `BitString` template.

Public Member Functions
	ParallelZipTrie (unsigned max_size, unsigned max_lcp_length)
	Constructs a ParallelZipTrie.

	~ParallelZipTrie ()
	Destructor for ParallelZipTrie.

void	insert (const KEY_T *key) noexcept
	Inserts a key into the parallel zip trie using parallel comparison logic.

SearchResults	search (const KEY_T *key) const noexcept override
	Performs a search for a key within the ParallelZipTrie using parallel comparison logic.

unsigned	size () const noexcept
	Returns the number of nodes (keys) currently stored in the trie.

Public Member Functions inherited from ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >
	ZipTrie (unsigned max_size, unsigned max_lcp_length) noexcept
	Constructs an empty ZipTrie.

int	get_depth (const KEY_T *key) const noexcept
	Calculates the depth of a given key in the trie.

int	height () const noexcept
	Calculates the height of the trie.

double	get_average_height () const noexcept
	Calculates the average depth of all nodes currently in the trie.

unsigned	size () const noexcept
	Returns the number of nodes (keys) currently stored in the trie.

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

LCP_T	lcp (const KEY_T *key) const noexcept
	Finds the Longest Common Prefix (LCP) between the search key and the path taken in the trie.

void	insert (const KEY_T *key) noexcept
	Inserts a key into the zip trie.

const RANK_T &	get_root_rank () const noexcept
	Removes a node with a given key from the zip tree. (Not implemented)

void	set (const KEY_T *key, RANK_T rank, unsigned left, unsigned right, LCP_T predecessor_lcp, LCP_T successor_lcp) noexcept
	Directly adds a pre-constructed bucket to the internal storage vector.

void	set_root_index (unsigned root_index) noexcept
	Directly sets the root index of the trie.

void	to_dot (const std::string &file_path) const noexcept
	Generates a DOT language representation of the trie structure for visualization.

Protected Types
using	AncestorLCPs = typename ZT::AncestorLCPs
	Alias for the `AncestorLCPs` struct from the base class `ZipTrie`.

using	Bucket = typename ZT::Bucket
	Alias for the `Bucket` (node) struct from the base class `ZipTrie`.

using	ComparisonResult = typename ZT::ComparisonResult
	Alias for the `ComparisonResult` struct from the base class `ZipTrie`.

Protected Member Functions
MemoryEfficientLCP	get_memory_efficient_lcp (size_t num) const noexcept
	Using declaration for the LCP approximation helper (if `MEMORY_EFFICIENT` is true) from `ZipTrie`.

template<typename CompareFunction >
SearchResults	search_recursive (const KEY_T *key, CompareFunction compare_func) const noexcept
	Using declaration for the recursive search helper from the base class `ZipTrie`.

template<typename CompareFunction >
unsigned	insert_recursive (Bucket *x, unsigned x_index, unsigned v_index, AncestorLCPs ancestor_lcps, CompareFunction compare_func) noexcept
	Using declaration for the recursive insert helper from the base class `ZipTrie`.

std::optional< ComparisonResult >	k_compare_prefix_check (const Bucket &v, const AncestorLCPs &ancestor_lcps, size_t &out_start_lcp_val) const noexcept
	Using declaration for the LCP prefix check optimization helper from `ZipTrie`.

LCP_T	convert_lcp (size_t val) const noexcept
	Using declaration for the LCP value conversion helper from `ZipTrie`.

Protected Member Functions inherited from ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >
MemoryEfficientLCP	get_memory_efficient_lcp (size_t num) const noexcept
	Converts a standard LCP length (`size_t`) into the `MemoryEfficientLCP` format.

template<typename CompareFunction >
SearchResults	search_recursive (const KEY_T *key, CompareFunction compare_func) const noexcept
	Recursive helper function for the public `search` method.

template<typename CompareFunction >
unsigned	insert_recursive (Bucket *x, unsigned x_index, unsigned v_index, AncestorLCPs ancestor_lcps, CompareFunction compare_func) noexcept
	Recursive helper function for inserting a new node `x`.

std::optional< ComparisonResult >	k_compare_prefix_check (const Bucket &v, const AncestorLCPs &ancestor_lcps, size_t &out_start_lcp_val) const noexcept
	Performs an initial check based on ancestor LCPs before full key comparison (k-compare optimization).

LCP_T	convert_lcp (size_t val) const noexcept
	Converts an exact LCP length (e.g., number of matching characters/bits) to the `LCP_T` type.

Protected Attributes
unsigned	_root_index
	Using declaration for the root index from the base class `ZipTrie`.

unsigned	_max_lcp_length
	Using declaration for the maximum LCP length storage from the base class `ZipTrie`.

uint8_t	_log_max_size
	Using declaration for the log max size storage from the base class `ZipTrie`.

std::vector< Bucket >	_buckets
	Using declaration for the node storage vector (`std::vector<Bucket>`) from the base class `ZipTrie`.

Protected Attributes inherited from ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >
unsigned	_root_index
	Index of the root node within the `_buckets` vector. Initialized to `NULLPTR` for an empty trie.

unsigned	_max_lcp_length
	Stores the maximum possible LCP length provided during construction.

uint8_t	_log_max_size
	Stores the approximate log base 2 of the `max_size` provided during construction.

std::vector< Bucket >	_buckets
	A contiguous vector storing all the nodes (`Bucket`s) of the trie.

Static Protected Attributes
static constexpr unsigned	NULLPTR
	Using declaration for the null pointer constant (`unsigned`) from the base class `ZipTrie`.

Static Protected Attributes inherited from ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >
static constexpr unsigned	NULLPTR = std::numeric_limits<unsigned>::max()
	Represents a null child pointer index using the maximum value of `unsigned`.

Private Member Functions
ComparisonResult	k_compare (const KEY_T *x, const Bucket &v, const AncestorLCPs &ancestor_lcps, size_t &comparison_size, size_t &max_copied) const noexcept
	Performs key comparison using parallel logic, overriding the base class `k_compare`.

Private Attributes
uintmax_t *	d_a
	Pointer to device memory buffer 'a', used as primary input/output for parallel key comparisons (e.g., via `BitString::par_k_compare`).

uintmax_t *	d_largeblock
	Pointer to auxiliary device memory buffer ('largeblock'), used as temporary storage or workspace during parallel key comparisons by kernels like `par_find_mismatch`.

Detailed Description

template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>
class ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >

Extends the ZipTrie class to incorporate parallel key comparisons leveraging GPU acceleration (CUDA).

This class inherits the core structure and logic of ZipTrie but overrides key comparison-related methods (k_compare, search, insert) to utilize a parallel comparison function (par_k_compare from BitString). It manages CUDA device memory buffers (d_a, d_largeblock) required for these parallel comparisons, allocating them in the constructor and freeing them in the destructor. This allows for potentially faster trie operations when comparing long keys, at the cost of requiring CUDA-enabled hardware and managing GPU memory. The LCP-based prefix check optimization (k_compare_prefix_check) from the base class is still utilized to avoid unnecessary parallel comparisons when possible.

Template Parameters

CHAR_T	The underlying character type used in the keys (`BitString`).
MEMORY_EFFICIENT	If true, uses `MemoryEfficientLCP`; otherwise, uses `unsigned` for LCP storage.
RANK_T	The type used for node ranks (default: `GeometricRank`).
CHAR_SIZE_BITS	The number of significant bits per character in `CHAR_T`.

See also: ZipTrie; BitString::par_k_compare

Definition at line 42 of file ParallelZipTrie.cuh.

Member Typedef Documentation

◆ AncestorLCPs

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::AncestorLCPs = typename ZT::AncestorLCPs

protected

Alias for the AncestorLCPs struct from the base class ZipTrie.

Definition at line 137 of file ParallelZipTrie.cuh.

◆ Bucket

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::Bucket = typename ZT::Bucket

protected

Alias for the Bucket (node) struct from the base class ZipTrie.

Definition at line 139 of file ParallelZipTrie.cuh.

◆ ComparisonResult

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::ComparisonResult = typename ZT::ComparisonResult

protected

Alias for the ComparisonResult struct from the base class ZipTrie.

Definition at line 141 of file ParallelZipTrie.cuh.

◆ KEY_T

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::KEY_T = typename ZT::KEY_T

Alias for the Key type used, inherited from the base class (ZipTrie::KEY_T).

Definition at line 51 of file ParallelZipTrie.cuh.

◆ LCP_T

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::LCP_T = typename ZT::LCP_T

Alias for the LCP type used, inherited from the base class (ZipTrie::LCP_T).

Definition at line 49 of file ParallelZipTrie.cuh.

◆ SearchResults

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::SearchResults = typename ZT::SearchResults

Removes a node with a given key from the zip tree. (Not implemented)

Parameters

key	key of node to remove

Returns: true if a node was removed, false otherwise

Note: This functionality is declared but not implemented. Requires implementing 'unzip' operations.

Alias for the SearchResults struct defined in the base ZipTrie class.

Definition at line 106 of file ParallelZipTrie.cuh.

◆ ZT

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::ZT = ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>

Alias for the base ZipTrie class template instantiation for brevity.

Definition at line 46 of file ParallelZipTrie.cuh.

Constructor & Destructor Documentation

◆ ParallelZipTrie()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::ParallelZipTrie	(	unsigned	max_size,
		unsigned	max_lcp_length
	)

Constructs a ParallelZipTrie.

Initializes the base ZipTrie and allocates necessary CUDA device memory buffers (d_a, d_largeblock) required for the parallel key comparisons (BitString::par_k_compare). The size of the allocated buffers is determined by the max_lcp_length parameter.

Parameters

max_size	Hint for reserving memory for the expected maximum number of nodes (passed to base class constructor).
max_lcp_length	The maximum possible LCP length (in characters/bits), used for device memory allocation size calculation.

See also: alloc_to_device; alloc_large_block_to_device_s

Definition at line 195 of file ParallelZipTrie.cuh.

                                                                                                                            :
    ZT(max_size, max_lcp_length) // Call base class constructor
{
    // Calculate required device buffer size in words based on max LCP length.
    size_t max_lcp_length_words = (max_lcp_length + KEY_T::ALPHA - 1) / KEY_T::ALPHA;
 
    // Allocate the primary device buffer.
    d_a = alloc_to_device<uintmax_t>(max_lcp_length_words);
    // Allocate the auxiliary large block buffer (size calculation might depend on the parallel algorithm used).
    // Use large block device allocation for temporary storage in parallel operations
    d_largeblock = alloc_large_block_to_device(max_lcp_length_words);
}

◆ ~ParallelZipTrie()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::~ParallelZipTrie ( )

Destructor for ParallelZipTrie.

Frees the CUDA device memory buffers (d_a, d_largeblock) allocated in the constructor.

See also: device_free

Definition at line 209 of file ParallelZipTrie.cuh.

{
    // Free the allocated device memory buffers.
    device_free(d_a);
    device_free(d_largeblock);
}

Member Function Documentation

◆ convert_lcp()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::LCP_T ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::convert_lcp ( size_t val ) const

inlineprotectednoexcept

Using declaration for the LCP value conversion helper from ZipTrie.

Definition at line 492 of file ZipTrie.hpp.

{
    if constexpr (MEMORY_EFFICIENT) {
        // If memory efficiency is enabled, call the approximation function.
        return get_memory_efficient_lcp(val);
    } else {
        // Otherwise, just cast the exact value to the LCP type (unsigned).
        // Ensure the value fits; consider potential truncation if LCP_T were smaller than size_t.
        return static_cast<LCP_T>(val);
    }
}

◆ get_memory_efficient_lcp()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

MemoryEfficientLCP ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::get_memory_efficient_lcp ( size_t num ) const

inlineprotectednoexcept

Using declaration for the LCP approximation helper (if MEMORY_EFFICIENT is true) from ZipTrie.

Definition at line 391 of file ZipTrie.hpp.

{
    // Handle LCPs smaller than the log of max size directly.
    if (num < _log_max_size)
    {
        // Store the exact value in 'multiple', with exponent 0.
        return { 0, static_cast<uint8_t>(num) };
    }
 
    // Otherwise, calculate exponent and multiple for approximation.
    MemoryEfficientLCP lcp;
    lcp.exp_of_2 = std::log2(num / _log_max_size);
    lcp.multiple = num / (1u << lcp.exp_of_2);
 
    return lcp;
}

◆ insert()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

void ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::insert ( const KEY_T * key )

noexcept

Inserts a key into the parallel zip trie using parallel comparison logic.

This method overrides the base class insert. It adds the key with a random rank to the internal storage (_buckets) and then calls the recursive insertion helper (insert_recursive), providing a comparison function lambda that utilizes the parallel k_compare implementation of this class. The parallel k_compare leverages BitString::par_k_compare for GPU acceleration when beneficial.

Parameters

key	Pointer to the new key to insert. Must be non-null and point to a valid `KEY_T` object.

Warning: Key Lifetime: The lifetime of the object pointed to by key must exceed the lifetime of the ParallelZipTrie.; Uniqueness: Assumes keys are unique. Inserting duplicate keys results in the insertion being skipped, but the initially added bucket might remain unused in storage.

See also: insert_recursive; k_compare(const KEY_T*, const Bucket&, const AncestorLCPs&, size_t&, size_t&) const; RANK_T::get_random

Definition at line 292 of file ParallelZipTrie.cuh.

{
    // Initialize state variables for the parallel comparison process.
    size_t comparison_size = KEY_T::MIN_PAR_COMPARE_CHAR_SIZE;
    size_t max_copied = 0;
 
    // Add a new bucket for the key with a random rank to the storage vector.
    _buckets.push_back({ key, RANK_T::get_random() });
    unsigned new_node_index = _buckets.size() - 1;
 
    // Define the parallel comparison lambda, capturing state by reference.
    auto parallel_compare = [&](const KEY_T* k, const Bucket& v, const AncestorLCPs& ancestor_lcps)
        {
            return k_compare(k, v, ancestor_lcps, comparison_size, max_copied);
        };
 
    // Call the inherited recursive insert function to place the node and perform zip operations.
    // Pass the new node details, initial empty ancestor LCPs, and the parallel comparison lambda.
    // Update the root index, as it might change due to zip operations.
    _root_index = insert_recursive(&_buckets[new_node_index], new_node_index, _root_index, {}, parallel_compare);
}

◆ insert_recursive()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

template<typename CompareFunction >

unsigned ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::insert_recursive	(	Bucket *	x,
		unsigned	x_index,
		unsigned	v_index,
		AncestorLCPs	ancestor_lcps,
		CompareFunction	compare_func
	)

protectednoexcept

Using declaration for the recursive insert helper from the base class ZipTrie.

Definition at line 433 of file ZipTrie.hpp.

{
    // Base case: Reached a null pointer, meaning this is the insertion spot.
    if (v_index == NULLPTR)
    {
        // Set the ancestor LCPs for the new node 'x' based on the path taken.
        x->ancestor_lcps = ancestor_lcps;
        // Return the index of the new node 'x', indicating it's the root of this (now non-empty) subtree.
        return x_index;
    }
 
    // Get a reference to the current node 'v'.
    Bucket& v_node = _buckets[v_index];
 
    // Compare the new key 'x->key' with the current node's key 'v_node.key'.
    auto [ comparison, lcp ] = compare_func(x->key, v_node, ancestor_lcps);
 
    // If keys are equal, the key already exists. Do not insert duplicates.
    // Return the current node's index, leaving the subtree unchanged.
    if (comparison == std::strong_ordering::equal)
    {
        // Note: Could potentially update value associated with key here if storing values.
        // Since we only store keys, we just return.
        // Also, need to handle the bucket pushed back in `insert`. A robust implementation
        // might check for existence *before* adding to _buckets or remove the unused bucket here.
        // Current implementation leaves the unused bucket if key exists.
        // We should pop the unused bucket here.
        if (x_index == _buckets.size() - 1) { // Check if it's the last one added
            _buckets.pop_back(); // Remove the unused bucket
        } // Else, if not the last, it's harder to remove without messing up indices.
 
        return v_index;
    }
 
    // Navigate left or right based on the comparison result.
    if (comparison == std::strong_ordering::less)
    {
        // Go left. Recursively insert into the left subtree.
        // Update the ancestor LCPs for the recursive call: predecessor stays the same,
        // successor becomes the max of the current path's successor and the LCP just computed.
        unsigned subroot_index = insert_recursive(x, x_index, v_node.left, { ancestor_lcps.predecessor, std::max(ancestor_lcps.successor, lcp) }, compare_func);
 
        // If the recursive call returned an index other than the original left child,
        // it means the structure below changed.
        if (subroot_index == x_index && x->rank >= v_node.rank)
        {
            v_node.left = x->right; // v adopts x's right child as its left child.
            x->right = v_index;     // x takes v as its right child.
            // Update LCPs stored *in the nodes* due to the structural change.
            // v's predecessor LCP is now the LCP computed between x and v.
            v_node.ancestor_lcps.predecessor = lcp;
            // x's ancestor LCPs become those passed into this level (ancestor_lcps).
            x->ancestor_lcps = ancestor_lcps;
            // Return x_index as the new root of this subtree.
            return x_index;
        }
        else
        {
            // Simply update v's left child pointer to the returned subtree root.
            v_node.left = subroot_index;
        }
        // If subroot_index == v_node.left, the left subtree structure didn't change relative to v.
    }
    else // comparison == std::strong_ordering::greater
    {
        // Go right. Recursively insert into the right subtree.
        // Update ancestor LCPs: successor stays same, predecessor updates.
        unsigned subroot_index = insert_recursive(x, x_index, v_node.right, { std::max(ancestor_lcps.predecessor, lcp), ancestor_lcps.successor }, compare_func);
 
        // If the recursive call returned an index other than the original right child.
        if (subroot_index == x_index && x->rank >= v_node.rank)
        {
            v_node.right = x->left; // v adopts x's left child as its right child.
            x->left = v_index;      // x takes v as its left child.
            // Update LCPs stored in the nodes.
            v_node.ancestor_lcps.successor = lcp; // v's successor LCP is now the computed LCP.
            x->ancestor_lcps = ancestor_lcps;     // x inherits parent's LCPs.
            // Return x_index as the new root.
            return x_index;
        }
        else
        {
            v_node.right = subroot_index;
        }
        // If subroot_index == v_node.right, the right subtree structure didn't change relative to v.
    }
 
    return v_index;
}

◆ k_compare()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::ComparisonResult ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::k_compare	(	const KEY_T *	x,
		const Bucket &	v,
		const AncestorLCPs &	ancestor_lcps,
		size_t &	comparison_size,
		size_t &	max_copied
	)		const

inlineprivatenoexcept

Performs key comparison using parallel logic, overriding the base class k_compare.

This method implements the core parallel comparison strategy for ParallelZipTrie. It first leverages the inherited k_compare_prefix_check optimization. If a full comparison is necessary, it iteratively calls the BitString::par_k_compare function, which performs the comparison on the GPU. The comparison_size parameter controls the chunk size (number of characters) compared in each parallel step and is adapted dynamically: it increases if blocks match to compare larger chunks next time, and decreases if a mismatch is found to potentially refine the LCP more quickly in subsequent comparisons within the same search/insert operation.

Parameters

	x	Pointer to the key being searched for or inserted.
	v	Constant reference to the current node (`Bucket`) being compared against.
	ancestor_lcps	The LCPs computed along the path from the root down to `v`'s parent.
[in,out]	comparison_size	Controls the block size (number of characters) for the parallel comparison step. Its value is adapted based on the comparison outcome.
[in,out]	max_copied	Tracks state related to data copied to device memory (`d_a`) by `par_k_compare` to potentially optimize subsequent copies within the same search/insert operation.

Returns: ComparisonResult A struct containing the relative ordering (comparison) of x vs v and the calculated Longest Common Prefix (lcp) between them (converted to LCP_T).

Note: This method directly interacts with the BitString::par_k_compare function and relies on the device memory buffers d_a and d_largeblock managed by this class.

See also: ZT::k_compare_prefix_check; BitString::par_k_compare; convert_lcp

Definition at line 217 of file ParallelZipTrie.cuh.

{
    size_t start_lcp_val = 0; // Initialize LCP offset for comparison.
 
    if (auto prefix_result = k_compare_prefix_check(v, ancestor_lcps, start_lcp_val))
    {
        return *prefix_result; // Return early if comparison decided by LCPs.
    }
 
    // Initialize comparison result and final LCP with the value from prefix check.
    std::strong_ordering final_comparison = std::strong_ordering::equal;
    size_t final_lcp_val = start_lcp_val;
 
    // Iteratively call parallel compare until a mismatch is found or keys are fully compared.
    while (true)
    {
        // Call the parallel comparison function provided by the KEY_T (BitString) class.
        // Pass the keys, current LCP offset, comparison block size, device buffers, and copy tracker.
        auto [current_comparison, next_lcp] = x->par_k_compare(
            *v.key, final_lcp_val, comparison_size,
            d_a, d_largeblock, max_copied);
 
        // Update the overall comparison result and the total LCP found so far.
        final_comparison = current_comparison;
        final_lcp_val = next_lcp;
 
        // If the current block compared equal...
        if (final_comparison == std::strong_ordering::equal)
        {
            // Check if we have compared the entire length of both keys.
            // If keys are fully compared and equal, break the loop.
            if (final_lcp_val == x->size() && final_lcp_val == v.key->size())
            {
                break;
            }
 
            // Otherwise, keys matched so far but aren't finished.
            // Increase the comparison size (e.g., double it) for the next iteration to potentially speed up.
            comparison_size *= 2;
            // Continue to the next iteration to compare the next block.
            continue;
        }
 
        // Mismatch found (comparison is less or greater).
        // Reduce the comparison size for future comparisons (adaptive strategy).
        // Ensure it doesn't go below a minimum threshold.
        comparison_size = std::max(KEY_T::MIN_PAR_COMPARE_CHAR_SIZE, comparison_size / 2);
        // Break the loop as the final comparison result is determined.
        break;
    }
 
    // Convert the final exact LCP length to the appropriate LCP_T format and return the result.
    return { final_comparison, convert_lcp(final_lcp_val) };
}

◆ k_compare_prefix_check()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

std::optional< typename ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::ComparisonResult > ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::k_compare_prefix_check	(	const Bucket &	v,
		const AncestorLCPs &	ancestor_lcps,
		size_t &	out_start_lcp_val
	)		const

protectednoexcept

Using declaration for the LCP prefix check optimization helper from ZipTrie.

Definition at line 478 of file ZipTrie.hpp.

{
    // Get the LCPs from the current search path.
    auto predecessor_lcp = ancestor_lcps.predecessor;
    auto successor_lcp = ancestor_lcps.successor;
 
    // Determine the maximum LCP encountered on the current search path.
    auto x_max_lcp = std::max(predecessor_lcp, successor_lcp);
    // Determine the corresponding LCP stored in node 'v' (from the path when 'v' was inserted).
    // If the search path's max LCP came from the predecessor side, use v's predecessor LCP, otherwise use v's successor LCP.
    auto corr_v_lcp = (predecessor_lcp > successor_lcp) ? v.ancestor_lcps.predecessor : v.ancestor_lcps.successor;
 
    // If the maximum LCP on the current path (x_max_lcp) differs from the
    // corresponding LCP recorded when node 'v' was inserted (corr_v_lcp)...
    if (x_max_lcp != corr_v_lcp)
    {
        // ...we can determine the order based on which LCP is larger and which path it came from.
        // The logic determines if x should be less or greater than v.
        // `(x_max_lcp > corr_v_lcp)` is true if the current path's LCP is longer.
        // `(predecessor_lcp > successor_lcp)` is true if the current path's max LCP came from the predecessor side.
        // If these booleans match, x is less; otherwise, x is greater.
        std::strong_ordering comparison_result =
            ((x_max_lcp > corr_v_lcp) == (predecessor_lcp > successor_lcp)) ? std::strong_ordering::less : std::strong_ordering::greater;
 
        // The resulting LCP for this comparison is the minimum of the two differing LCPs.
        LCP_T result_lcp = std::min(x_max_lcp, corr_v_lcp);
 
        // Return the determined comparison result and LCP. No need for full key comparison.
        return ComparisonResult{ comparison_result, result_lcp };
    }
 
    // If the LCPs matched (x_max_lcp == corr_v_lcp), we cannot decide the order yet.
    // We need to perform a full key comparison, but we know the keys match up to `x_max_lcp`.
    // Set the starting offset for the key comparison.
    if constexpr (MEMORY_EFFICIENT)
    {
        // If using approximate LCPs, get the actual value.
        out_start_lcp_val = x_max_lcp.value();
    }
    else
    {
        // If using exact LCPs (unsigned), the value is directly usable.
        out_start_lcp_val = x_max_lcp;
    }
 
    // Indicate that a full key comparison should proceed by returning nullopt.
    return std::nullopt;
}

◆ search()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::SearchResults ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::search ( const KEY_T * key ) const

overridevirtualnoexcept

Performs a search for a key within the ParallelZipTrie using parallel comparison logic.

Overrides the base class search method. It initializes state required for parallel comparison (comparison_size, max_copied) and calls the recursive search helper (search_recursive) inherited from the base class. Crucially, it passes a comparison function lambda that invokes the parallel k_compare implementation defined within this ParallelZipTrie class.

Parameters

key	Pointer to the key to search for.

Returns: SearchResults A struct containing the search outcome (found status, LCP, depth).

See also: search_recursive; k_compare(const KEY_T*, const Bucket&, const AncestorLCPs&, size_t&, size_t&) const

Reimplemented from ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >.

Definition at line 273 of file ParallelZipTrie.cuh.

{
    // Initialize state variables for the parallel comparison process.
    size_t comparison_size = KEY_T::MIN_PAR_COMPARE_CHAR_SIZE;
    size_t max_copied = 0; // Tracks device memory copy status/optimization.
 
    // Define a lambda function that captures the current state and calls the parallel k_compare method.
    // This lambda will be passed to the base class's search_recursive helper.
    auto parallel_compare = [&](const KEY_T* k, const Bucket& v, const AncestorLCPs& ancestor_lcps)
        {
            // Note: comparison_size and max_copied are captured by reference, allowing k_compare to modify them.
            return k_compare(k, v, ancestor_lcps, comparison_size, max_copied);
        };
 
    // Call the inherited recursive search function, passing the key and the parallel comparison lambda.
    return search_recursive(key, parallel_compare);
}

◆ search_recursive()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

template<typename CompareFunction >

ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::SearchResults ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::search_recursive	(	const KEY_T *	key,
		CompareFunction	compare_func
	)		const

protectednoexcept

Using declaration for the recursive search helper from the base class ZipTrie.

Definition at line 407 of file ZipTrie.hpp.

{
    // Handle empty trie case.
    if (_root_index == NULLPTR)
    {
        // Return not found, default LCP, depth -1.
        return { false, {}, -1 };
    }
 
    unsigned v_index = _root_index; // Start traversal at the root.
    AncestorLCPs ancestor_lcps = {}; // Initialize ancestor LCPs to zero/default at the root.
    int depth = 0; // Initialize depth counter.
 
    // Iterate down the trie until a null pointer is reached or the key is found.
    while (v_index != NULLPTR)
    {
        // Get a reference to the current node.
        const Bucket& v_node = _buckets[v_index];
 
        // Perform the comparison using the provided comparison function.
        auto [ comparison, lcp ] = compare_func(key, v_node, ancestor_lcps);
 
        // Check if the key is an exact match.
        if (comparison == std::strong_ordering::equal)
        {
            // Key found. Return true, the final LCP, and the current depth.
            return { true, lcp, depth };
        }
 
        // If not equal, decide whether to go left or right.
        if (comparison == std::strong_ordering::less)
        {
            // Go left. Update the successor LCP for the path: it's the maximum of the
            // current successor LCP and the LCP computed in this step.
            ancestor_lcps.successor = std::max(ancestor_lcps.successor, lcp);
            // Move to the left child.
            v_index = v_node.left;
        }
        else // comparison == std::strong_ordering::greater
        {
            // Go right. Update the predecessor LCP similarly.
            ancestor_lcps.predecessor = std::max(ancestor_lcps.predecessor, lcp);
            // Move to the right child.
            v_index = v_node.right;
        }
 
        // Increment depth for the next level.
        ++depth;
    }
 
    // Key not found after traversing the path.
    // Return false, the maximum LCP encountered along the path, and depth -1.
    return { false, std::max(ancestor_lcps.predecessor, ancestor_lcps.successor), -1 };
}

◆ size()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

unsigned ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::size ( ) const

noexcept

Returns the number of nodes (keys) currently stored in the trie.

Inherited directly from the base ZipTrie class via the using declaration.

Returns: unsigned The number of nodes.

Definition at line 183 of file ZipTrie.hpp.

{
    // Simply return the current size of the underlying vector storing the nodes.
    // Note: This assumes no gaps or marked-deleted nodes if removal were implemented differently.
    // If duplicate keys caused buckets to be added but not used in `insert_recursive`,
    // this size might be slightly inflated compared to unique keys. Consider adjusting if duplicates are handled differently.
    return _buckets.size();
}

Member Data Documentation

◆ _buckets

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

std::vector<Bucket> ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::_buckets

protected

Using declaration for the node storage vector (std::vector<Bucket>) from the base class ZipTrie.

Definition at line 379 of file ZipTrie.hpp.

◆ _log_max_size

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

uint8_t ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::_log_max_size

protected

Using declaration for the log max size storage from the base class ZipTrie.

Definition at line 323 of file ZipTrie.hpp.

◆ _max_lcp_length

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

unsigned ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::_max_lcp_length

protected

Using declaration for the maximum LCP length storage from the base class ZipTrie.

Definition at line 317 of file ZipTrie.hpp.

◆ _root_index

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

unsigned ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::_root_index

protected

Using declaration for the root index from the base class ZipTrie.

Definition at line 312 of file ZipTrie.hpp.

◆ d_a

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

uintmax_t* ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::d_a

private

Pointer to device memory buffer 'a', used as primary input/output for parallel key comparisons (e.g., via BitString::par_k_compare).

Definition at line 157 of file ParallelZipTrie.cuh.

◆ d_largeblock

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

uintmax_t* ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::d_largeblock

private

Pointer to auxiliary device memory buffer ('largeblock'), used as temporary storage or workspace during parallel key comparisons by kernels like par_find_mismatch.

Definition at line 159 of file ParallelZipTrie.cuh.

◆ NULLPTR

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

constexpr unsigned ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::NULLPTR

staticconstexprprotected

Using declaration for the null pointer constant (unsigned) from the base class ZipTrie.

Definition at line 326 of file ZipTrie.hpp.

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

src/ParallelZipTrie.cuh

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ AncestorLCPs

◆ Bucket

◆ ComparisonResult

◆ KEY_T

◆ LCP_T

◆ SearchResults

◆ ZT

Constructor & Destructor Documentation

◆ ParallelZipTrie()

◆ ~ParallelZipTrie()

Member Function Documentation

◆ convert_lcp()

◆ get_memory_efficient_lcp()

◆ insert()

◆ insert_recursive()

◆ k_compare()

◆ k_compare_prefix_check()

◆ search()

◆ search_recursive()

◆ size()

Member Data Documentation

◆ _buckets

◆ _log_max_size

◆ _max_lcp_length

◆ _root_index

◆ d_a

◆ d_largeblock

◆ NULLPTR