Raptor 3.0.1
A fast and space-efficient pre-filter for querying very large collections of nucleotide sequences
 
Loading...
Searching...
No Matches
partition_config.hpp
Go to the documentation of this file.
1// --------------------------------------------------------------------------------------------------
2// Copyright (c) 2006-2023, Knut Reinert & Freie Universität Berlin
3// Copyright (c) 2016-2023, Knut Reinert & MPI für molekulare Genetik
4// This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
5// shipped with this file and also available at: https://github.com/seqan/raptor/blob/main/LICENSE.md
6// --------------------------------------------------------------------------------------------------
7
13#pragma once
14
15#include <bit>
16#include <cstddef>
17#include <cstdint>
18
19namespace raptor
20{
21
23{
24 partition_config(partition_config const &) = default;
26 partition_config & operator=(partition_config const &) = default;
27 partition_config & operator=(partition_config &&) = default;
28 ~partition_config() = default;
29
30 explicit partition_config(size_t const parts) : partitions{parts}
31 {
32 size_t const suffixes = next_power_of_four(partitions);
33 size_t const suffixes_per_part = suffixes / partitions;
34 mask = suffixes - 1;
35 shift_value = std::countr_zero(suffixes_per_part);
36 }
37
38 size_t partitions{};
39 size_t mask{};
40 int shift_value{};
41
42 // The number of suffixes is a power of four.
43 // The number of partitions is a power of two.
44 // The number of suffixes is greater than or equal to the number of partitions.
45 // This means that the number of suffixes per partition is always a power of two.
46 // Therefore, we can do a right shift instead of the division in:
47 // (hash & mask) / suffixes_per_part == partition
48 // The compiler cannot optimize the division to a right shift because suffixes_per_part is a runtime variable.
49 constexpr size_t hash_partition(uint64_t const hash) const
50 {
51 return (hash & mask) >> shift_value;
52 }
53
54 static constexpr size_t next_power_of_four(size_t number)
55 {
56 if (number == 0ULL || number == 1ULL)
57 return 1ULL; // GCOVR_EXCL_LINE
58
59 --number;
60 int const highest_set_bit_pos = std::bit_width(number);
61 int const shift_amount = (highest_set_bit_pos + (highest_set_bit_pos & 1)) - 2;
62 // ( Next multiple of two ) 4 has two zeros
63 return 0b0100ULL << shift_amount;
64 }
65};
66
67} // namespace raptor
Definition partition_config.hpp:23