cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize > Struct Template Reference

Addition/Subtraction-based hashing strategy for cuckoo filters (ASCF). More...

Static Public Member Functions
template<typename H >
static __host__ __device__ uint64_t	hash64 (const H &key)
	Computes a 64-bit hash of the key.
static __host__ __device__ cuda::std::tuple< size_t, size_t, TagType, TagType >	getCandidateBucketsAndFPs (const KeyType &key, size_t numBuckets)
	Computes fingerprint and candidate buckets using ADD/SUB operations.
static __host__ __device__ size_t	getAlternateBucket (size_t bucket, TagType fp, size_t numBuckets)
	Computes alternate bucket using ADD/SUB operations.
static size_t	calculateNumBuckets (size_t capacity)
	Calculates number of buckets without requiring power of two.

Static Public Attributes
static constexpr size_t	fpMask = (1ULL << bitsPerTag) - 1
static constexpr bool	usesChoiceBit = false
static constexpr char	name [] = "AddSubAltBucketPolicy"

Detailed Description

template<typename KeyType, typename TagType, size_t bitsPerTag, size_t bucketSize>
struct cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >

Addition/Subtraction-based hashing strategy for cuckoo filters (ASCF).

This implements the scheme from "Additive and Subtractive Cuckoo Filters" paper which uses ADD/SUB operations instead of XOR, allowing for non-power-of-two bucket counts and better space efficiency.

The filter is conceptually divided into two blocks of equal size.

• Block 0: buckets [0, numBuckets/2)
• Block 1: buckets [numBuckets/2, numBuckets)

Definition at line 99 of file bucket_policies.cuh.

Member Function Documentation

calculateNumBuckets()

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

static size_t cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::calculateNumBuckets ( size_t  capacity )

inlinestatic

Calculates number of buckets without requiring power of two.

The total number is rounded to ensure it's even (for equal block sizes).

Definition at line 174 of file bucket_policies.cuh.

                                                       {
        auto requiredBuckets = std::ceil(static_cast<double>(capacity) / bucketSize);
 
        // Round up to next even number to ensure equal block sizes
        if (static_cast<size_t>(requiredBuckets) % 2 != 0) {
            requiredBuckets += 1;
        }
 
        return static_cast<size_t>(requiredBuckets);
    }

getAlternateBucket()

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

static __host__ __device__ size_t cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::getAlternateBucket ( size_t  bucket, TagType  fp, size_t  numBuckets  )

inlinestatic

Computes alternate bucket using ADD/SUB operations.

If current bucket is in block 0, alternate is in block 1 (use ADD). If current bucket is in block 1, alternate is in block 0 (use SUB).

Parameters

bucket	Current bucket index
fp	Fingerprint value
numBuckets	Total number of buckets

Returns

Alternate bucket index

Definition at line 159 of file bucket_policies.cuh.

                                                                     {
        const size_t bucketsPerBlock = numBuckets / 2;
        const uint64_t fpHash = hash64(fp) % bucketsPerBlock;
 
        if (bucket < bucketsPerBlock) {
            return ((bucket + fpHash) % bucketsPerBlock) + bucketsPerBlock;
        } else {
            return (bucket - fpHash) % bucketsPerBlock;
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

getCandidateBucketsAndFPs()

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

static __host__ __device__ cuda::std::tuple< size_t, size_t, TagType, TagType > cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::getCandidateBucketsAndFPs ( const KeyType &  key, size_t  numBuckets  )

inlinestatic

Computes fingerprint and candidate buckets using ADD/SUB operations.

The first bucket is in block 0, computed from the hash. The second bucket is in block 1, computed by adding the fingerprint hash to the first bucket index (with wraparound within block 1).

Parameters

key	Key to hash
numBuckets	Total number of buckets (should be even for proper block division)

Returns

A tuple of (bucket1, bucket2, fingerprintForBucket1, fingerprintForBucket2)

Definition at line 129 of file bucket_policies.cuh.

                                                                     {
        const uint64_t h = hash64(key);
 
        // Upper 32 bits for the fingerprint
        const uint32_t h_fp = h >> 32;
        const uint32_t masked = h_fp & fpMask;
        const auto fp = TagType(masked == 0 ? 1 : masked);
 
        // Lower 32 bits for bucket index in block 0
        const uint32_t h_bucket = h & 0xFFFFFFFF;
        const size_t bucketsPerBlock = numBuckets / 2;
 
        const size_t i1 = h_bucket % bucketsPerBlock;
        const size_t i2 = getAlternateBucket(i1, fp, numBuckets);
 
        return {i1, i2, fp, fp};
    }

Here is the call graph for this function:

hash64()

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

template<typename H >

static __host__ __device__ uint64_t cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::hash64 ( const H &  key )

inlinestatic

Computes a 64-bit hash of the key.

Template Parameters

H	Type of the key.

Parameters

key	The key to hash.

Returns

uint64_t The 64-bit hash value.

Definition at line 113 of file bucket_policies.cuh.

                                                             {
        return xxhash::xxhash64(key);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

fpMask

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

constexpr size_t cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::fpMask = (1ULL << bitsPerTag) - 1

staticconstexpr

Definition at line 100 of file bucket_policies.cuh.

name

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

constexpr char cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::name[] = "AddSubAltBucketPolicy"

staticconstexpr

Definition at line 104 of file bucket_policies.cuh.

usesChoiceBit

template<typename KeyType , typename TagType , size_t bitsPerTag, size_t bucketSize>

constexpr bool cuckoogpu::AddSubAltBucketPolicy< KeyType, TagType, bitsPerTag, bucketSize >::usesChoiceBit = false

staticconstexpr

Definition at line 102 of file bucket_policies.cuh.

---

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

• bucket_policies.cuh