Function ComputeMaxElements

src/minisketch/src/false_positives.h:91–106

}

size_t ComputeMaxElements(uint32_t bits, size_t capacity, uint32_t fpbits) {
    if (bits == 0) return 0;
    // Start with max_elements=capacity, and decrease max_elements until the corresponding capacity is capacity.
    size_t max_elements = capacity;
    while (true) {
        size_t capacity_for_max_elements = ComputeCapacity(bits, max_elements, fpbits);
        CHECK_SAFE(capacity_for_max_elements >= capacity);
        if (capacity_for_max_elements <= capacity) return max_elements;
        size_t adjust = capacity_for_max_elements - capacity;
        // Decrementing max_elements by N will at most decrement the corresponding capacity by N.
        // As the observed capacity is adjust too high, we can safely decrease max_elements by adjust.
        // If that brings us into negative max_elements territory, no solution exists and we return 0.
        if (max_elements < adjust) return 0;
        max_elements -= adjust;
    }
}

}  // namespace