get_location.cpp File Reference

Implements raptor::detail::get_location. More...

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <optional>
#include <vector>
#include <hibf/misc/divide_and_ceil.hpp>
#include <hibf/misc/iota_vector.hpp>
#include <raptor/index.hpp>
#include "strong_types.hpp"

Include dependency graph for get_location.cpp:

Enumerations
enum class	raptor::detail::growth_policy : uint8_t { none , limited , unlimited }
	How far an IBF may be grown while looking for space for a new user bin. More...

Functions
std::optional< insert_location >	raptor::detail::find_insert_location (std::vector< ibf_max > const &max_ibf_sizes, size_t const kmer_count, raptor_index< index_structure::hibf > &index)
	Determines where a user bin with kmer_count k-mers should be inserted.
std::optional< insert_location >	raptor::detail::get_location (std::vector< ibf_max > const &max_ibf_sizes, size_t const kmer_count, raptor_index< index_structure::hibf > &index)
	Determines where to store a user bin with kmer_count k-mers, and reserves the technical bins for it.
size_t	raptor::detail::required_technical_bins (required_technical_bins_parameters const &params)
	The number of technical bins needed to store params.elements elements without exceeding params.fpr.
std::optional< size_t >	raptor::detail::try_claim_bins (raptor_index< index_structure::hibf > &index, size_t const ibf_idx, size_t const number_of_bins, growth_policy const policy)
	Claims number_of_bins consecutive technical bins in the IBF at ibf_idx.
void	raptor::detail::update_bookkeeping (bookkeeping_arguments const &args, raptor_index< index_structure::hibf > &index)
	Registers a newly placed user bin in the bookkeeping of its IBF.

Detailed Description

Implements raptor::detail::get_location.

Author

Enrico Seiler <enrico.seiler AT fu-berlin.de>

Enumeration Type Documentation

growth_policy

enum class raptor::detail::growth_policy : uint8_t

strong

How far an IBF may be grown while looking for space for a new user bin.

Enumerator
none	Only use space that is already allocated.
limited	Grow, but at most to tmax + tmax_slack technical bins.
unlimited	Grow without a limit.

Function Documentation

find_insert_location()

std::optional< insert_location > raptor::detail::find_insert_location	(	std::vector< ibf_max > const &	max_ibf_sizes,
		size_t const	kmer_count,
		raptor_index< index_structure::hibf > &	index )

Determines where a user bin with kmer_count k-mers should be inserted.

Candidates are visited in order of how well the user bin fits into them, first without growing any IBF, then allowing growth up to tmax + tmax_slack, and finally allowing unrestricted growth.

Returns

Where to insert the user bin, or std::nullopt if no IBF can take it, or if the index has been resized too often already. Both mean that a full rebuild is unavoidable.

Here is the call graph for this function:

Here is the caller graph for this function:

get_location()

std::optional< insert_location > raptor::detail::get_location	(	std::vector< ibf_max > const &	max_ibf_sizes,
		size_t const	kmer_count,
		raptor_index< index_structure::hibf > &	index )

Determines where to store a user bin with kmer_count k-mers, and reserves the technical bins for it.

Parameters

[in]	max_ibf_sizes	The capacity of each IBF, see raptor::detail::max_ibf_sizes.
[in]	kmer_count	The number of k-mers of the user bin.
[in,out]	index	The index to insert into.

Returns

Where to store the user bin, or std::nullopt if a full rebuild is unavoidable, in which case index is left unchanged.

Here is the call graph for this function:

Here is the caller graph for this function:

required_technical_bins()

size_t raptor::detail::required_technical_bins

(

required_technical_bins_parameters const &

params

)

The number of technical bins needed to store params.elements elements without exceeding params.fpr.

Splitting a user bin over several technical bins lowers the load of each one, but a query has to pass all of them, so the combined FPR shrinks more slowly than the individual one. Hence the number of bins is increased until the combined FPR is within budget.

Mirrors seqan::hibf::hierarchical_interleaved_bloom_filter::number_of_bins.

Here is the call graph for this function:

Here is the caller graph for this function:

try_claim_bins()

std::optional< size_t > raptor::detail::try_claim_bins	(	raptor_index< index_structure::hibf > &	index,
		size_t const	ibf_idx,
		size_t const	number_of_bins,
		growth_policy const	policy )

Claims number_of_bins consecutive technical bins in the IBF at ibf_idx.

Returns

The index of the first claimed bin, or std::nullopt if policy does not permit claiming any.

Growing the IBF is a side effect of claiming bins; policy decides whether that is permitted. Any growth marks the IBF as resized, so every IBF is grown at most once before the index is rebuilt. The top-level IBF is never grown here, because doing so requires a full rebuild; raptor::detail::find_insert_location handles it.

Here is the call graph for this function:

Here is the caller graph for this function:

update_bookkeeping()

void raptor::detail::update_bookkeeping	(	bookkeeping_arguments const &	args,
		raptor_index< index_structure::hibf > &	index )

Registers a newly placed user bin in the bookkeeping of its IBF.

Marks the claimed technical bins as occupied, points them at the new user bin, and grows the per-bin vectors if the user bin was appended at the end. The claimed bins may also be reclaimed ones from the middle of the IBF, in which case the vectors already cover them and only their contents change.

Here is the call graph for this function:

Here is the caller graph for this function: