bloom_filter.hpp

#ifndef BTLLIB_BLOOM_FILTER_HPP
#define BTLLIB_BLOOM_FILTER_HPP
 
#include "btllib/nthash.hpp"
 
// clang-format off
// NOLINTBEGIN llvm-include-order
#include <limits>
#include "cpptoml.h"
// NOLINTEND llvm-include-order
// clang-format on
 
#include <atomic>
#include <climits>
#include <cstdint>
#include <fstream>
#include <memory>
#include <string>
#include <vector>
 
namespace btllib {
 
static const uint8_t BIT_MASKS[CHAR_BIT] = {
  // NOLINT
  0x01, 0x02, 0x04, 0x08, // NOLINT
  0x10, 0x20, 0x40, 0x80  // NOLINT
};
 
static const char* const BLOOM_FILTER_SIGNATURE = "[BTLBloomFilter_v6]";
static const char* const KMER_BLOOM_FILTER_SIGNATURE =
  "[BTLKmerBloomFilter_v6]";
static const char* const SEED_BLOOM_FILTER_SIGNATURE =
  "[BTLSeedBloomFilter_v6]";
static const char* const HASH_FN = NTHASH_FN_NAME;
 
static const unsigned MAX_HASH_VALUES = 1024;
static const unsigned PLACEHOLDER_NEWLINES = 50;
 
class BloomFilterInitializer
{
 
public:
  BloomFilterInitializer(const std::string& path, const std::string& signature)
    : path(path)
    , ifs(path)
    , table(parse_header(signature))
  {
  }
 
  static bool check_file_signature(std::ifstream& ifs,
                                   const std::string& expected_signature,
                                   std::string& file_signature);
 
  std::string path;
  std::ifstream ifs;
  std::shared_ptr<cpptoml::table> table;
 
  BloomFilterInitializer(const BloomFilterInitializer&) = delete;
  BloomFilterInitializer(BloomFilterInitializer&&) = default;
 
  BloomFilterInitializer& operator=(const BloomFilterInitializer&) = delete;
  BloomFilterInitializer& operator=(BloomFilterInitializer&&) = default;
 
private:
  std::shared_ptr<cpptoml::table> parse_header(const std::string& signature);
};
 
class BloomFilter
{
 
public:
  BloomFilter() {}
 
  BloomFilter(size_t bytes, unsigned hash_num, std::string hash_fn = "");
 
  explicit BloomFilter(const std::string& path);
 
  BloomFilter(const BloomFilter&) = delete;
  BloomFilter(BloomFilter&&) = delete;
 
  BloomFilter& operator=(const BloomFilter&) = delete;
  BloomFilter& operator=(BloomFilter&&) = delete;
 
  void insert(const uint64_t* hashes);
 
  void insert(const std::vector<uint64_t>& hashes) { insert(hashes.data()); }
 
  bool contains(const uint64_t* hashes) const;
 
  bool contains(const std::vector<uint64_t>& hashes) const
  {
    return contains(hashes.data());
  }
 
  bool contains_insert(const uint64_t* hashes);
 
  bool contains_insert(const std::vector<uint64_t>& hashes)
  {
    return contains_insert(hashes.data());
  }
 
  size_t get_bytes() const { return bytes; }
  uint64_t get_pop_cnt() const;
  double get_occupancy() const;
  unsigned get_hash_num() const { return hash_num; }
  double get_fpr() const;
  const std::string& get_hash_fn() const { return hash_fn; }
 
  void save(const std::string& path);
 
  static void save(const std::string& path,
                   const cpptoml::table& table,
                   const char* data,
                   size_t n);
 
  static bool is_bloom_file(const std::string& path)
  {
    return check_file_signature(path, BLOOM_FILTER_SIGNATURE);
  }
 
  static bool check_file_signature(const std::string& path,
                                   const std::string& signature);
 
private:
  BloomFilter(const std::shared_ptr<BloomFilterInitializer>& bfi);
 
  friend class KmerBloomFilter;
  friend class SeedBloomFilter;
 
  size_t bytes = 0;
  size_t array_size =
    0; // Should be equal to bytes, but not guaranteed by standard
  size_t array_bits = 0;
  unsigned hash_num = 0;
  std::string hash_fn;
  std::unique_ptr<std::atomic<uint8_t>[]> array;
};
 
class KmerBloomFilter
{
 
public:
  KmerBloomFilter() {}
 
  KmerBloomFilter(size_t bytes, unsigned hash_num, unsigned k);
 
  explicit KmerBloomFilter(const std::string& path);
 
  KmerBloomFilter(const KmerBloomFilter&) = delete;
  KmerBloomFilter(KmerBloomFilter&&) = delete;
 
  KmerBloomFilter& operator=(const KmerBloomFilter&) = delete;
  KmerBloomFilter& operator=(KmerBloomFilter&&) = delete;
 
  void insert(const char* seq, size_t seq_len);
 
  void insert(const std::string& seq) { insert(seq.c_str(), seq.size()); }
 
  void insert(const uint64_t* hashes) { bloom_filter.insert(hashes); }
 
  void insert(const std::vector<uint64_t>& hashes)
  {
    bloom_filter.insert(hashes);
  }
 
  unsigned contains(const char* seq, size_t seq_len) const;
 
  unsigned contains(const std::string& seq) const
  {
    return contains(seq.c_str(), seq.size());
  }
 
  bool contains(const uint64_t* hashes) const
  {
    return bloom_filter.contains(hashes);
  }
 
  bool contains(const std::vector<uint64_t>& hashes) const
  {
    return bloom_filter.contains(hashes);
  }
 
  unsigned contains_insert(const char* seq, size_t seq_len);
 
  unsigned contains_insert(const std::string& seq)
  {
    return contains_insert(seq.c_str(), seq.size());
  }
 
  bool contains_insert(const uint64_t* hashes)
  {
    return bloom_filter.contains_insert(hashes);
  }
 
  bool contains_insert(const std::vector<uint64_t>& hashes)
  {
    return bloom_filter.contains_insert(hashes);
  }
 
  size_t get_bytes() const { return bloom_filter.get_bytes(); }
  uint64_t get_pop_cnt() const { return bloom_filter.get_pop_cnt(); }
  double get_occupancy() const { return bloom_filter.get_occupancy(); }
  unsigned get_hash_num() const { return bloom_filter.get_hash_num(); }
  double get_fpr() const { return bloom_filter.get_fpr(); }
  unsigned get_k() const { return k; }
  const std::string& get_hash_fn() const { return bloom_filter.get_hash_fn(); }
  BloomFilter& get_bloom_filter() { return bloom_filter; }
 
  void save(const std::string& path);
 
  static bool is_bloom_file(const std::string& path)
  {
    return btllib::BloomFilter::check_file_signature(
      path, KMER_BLOOM_FILTER_SIGNATURE);
  }
 
private:
  KmerBloomFilter(const std::shared_ptr<BloomFilterInitializer>& bfi);
 
  friend class SeedBloomFilter;
 
  unsigned k = 0;
  BloomFilter bloom_filter;
};
 
class SeedBloomFilter
{
 
public:
  SeedBloomFilter() {}
 
  SeedBloomFilter(size_t bytes,
                  unsigned k,
                  const std::vector<std::string>& seeds,
                  unsigned hash_num_per_seed);
 
  explicit SeedBloomFilter(const std::string& path);
 
  SeedBloomFilter(const SeedBloomFilter&) = delete;
  SeedBloomFilter(SeedBloomFilter&&) = delete;
 
  SeedBloomFilter& operator=(const SeedBloomFilter&) = delete;
  SeedBloomFilter& operator=(SeedBloomFilter&&) = delete;
 
  void insert(const char* seq, size_t seq_len);
 
  void insert(const std::string& seq) { insert(seq.c_str(), seq.size()); }
 
  void insert(const uint64_t* hashes) { kmer_bloom_filter.insert(hashes); }
 
  void insert(const std::vector<uint64_t>& hashes)
  {
    kmer_bloom_filter.insert(hashes);
  }
 
  std::vector<std::vector<unsigned>> contains(const char* seq,
                                              size_t seq_len) const;
 
  std::vector<std::vector<unsigned>> contains(const std::string& seq) const
  {
    return contains(seq.c_str(), seq.size());
  }
 
  bool contains(const uint64_t* hashes) const
  {
    return kmer_bloom_filter.contains(hashes);
  }
 
  bool contains(const std::vector<uint64_t>& hashes) const
  {
    return kmer_bloom_filter.contains(hashes);
  }
 
  std::vector<std::vector<unsigned>> contains_insert(const char* seq,
                                                     size_t seq_len);
 
  std::vector<std::vector<unsigned>> contains_insert(const std::string& seq)
  {
    return contains_insert(seq.c_str(), seq.size());
  }
 
  bool contains_insert(const uint64_t* hashes)
  {
    return kmer_bloom_filter.contains_insert(hashes);
  }
 
  bool contains_insert(const std::vector<uint64_t>& hashes)
  {
    return kmer_bloom_filter.contains_insert(hashes);
  }
 
  size_t get_bytes() const { return kmer_bloom_filter.get_bytes(); }
  uint64_t get_pop_cnt() const { return kmer_bloom_filter.get_pop_cnt(); }
  double get_occupancy() const { return kmer_bloom_filter.get_occupancy(); }
  unsigned get_total_hash_num() const
  {
    return get_hash_num_per_seed() * get_seeds().size();
  }
  double get_fpr() const;
  unsigned get_k() const { return kmer_bloom_filter.get_k(); }
  const std::vector<std::string>& get_seeds() const { return seeds; }
  const std::vector<btllib::hashing_internals::SpacedSeed>& get_parsed_seeds()
    const
  {
    return parsed_seeds;
  }
  unsigned get_hash_num_per_seed() const
  {
    return kmer_bloom_filter.get_hash_num();
  }
  unsigned get_hash_num() const { return get_hash_num_per_seed(); }
  const std::string& get_hash_fn() const
  {
    return kmer_bloom_filter.get_hash_fn();
  }
  KmerBloomFilter& get_kmer_bloom_filter() { return kmer_bloom_filter; }
 
  void save(const std::string& path);
 
  static bool is_bloom_file(const std::string& path)
  {
    return btllib::BloomFilter::check_file_signature(
      path, SEED_BLOOM_FILTER_SIGNATURE);
  }
 
private:
  SeedBloomFilter(const std::shared_ptr<BloomFilterInitializer>& bfi);
 
  std::vector<std::string> seeds;
  std::vector<btllib::hashing_internals::SpacedSeed> parsed_seeds;
  KmerBloomFilter kmer_bloom_filter;
};
 
} // namespace btllib
 
#endif