mi_bloom_filter.hpp

#ifndef BTLLIB_MI_BLOOM_FILTER_HPP
#define BTLLIB_MI_BLOOM_FILTER_HPP
 
#include "nthash.hpp"
#include "status.hpp"
 
// clang-format off
// NOLINTBEGIN llvm-include-order
#include <limits>
#include "cpptoml.h"
// NOLINTEND llvm-include-order
// clang-format on
 
#include <climits>
#include <cstdlib>
 
#include <sdsl/bit_vector_il.hpp>
#include <sdsl/rank_support.hpp>
 
namespace btllib {
 
static const char* const MI_BLOOM_FILTER_SIGNATURE = "[BTLMIBloomFilter_v2]";
 
static const unsigned PLACEHOLDER_NEWLINES_MIBF = 50;
 
class MIBloomFilterInitializer
{
 
public:
  MIBloomFilterInitializer(const std::string& path,
                           const std::string& signature)
    : path(path)
    , ifs_id_arr(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_id_arr;
  std::shared_ptr<cpptoml::table> table;
 
  MIBloomFilterInitializer(const MIBloomFilterInitializer&) = delete;
  MIBloomFilterInitializer(MIBloomFilterInitializer&&) = default;
 
  MIBloomFilterInitializer& operator=(const MIBloomFilterInitializer&) = delete;
  MIBloomFilterInitializer& operator=(MIBloomFilterInitializer&&) = default;
 
private:
  std::shared_ptr<cpptoml::table> parse_header(const std::string& signature);
};
 
template<typename T>
class MIBloomFilter
{
public:
  static const T MASK = T(1) << (sizeof(T) * 8 - 1);
  static const T ANTI_MASK = (T)~MASK;
 
  static const T STRAND = T(1) << (sizeof(T) * 8 - 2);
  static const T ANTI_STRAND = (T)~STRAND;
 
  static const T ID_MASK = ANTI_STRAND & ANTI_MASK;
 
  static const unsigned BLOCKSIZE = 512;
 
  MIBloomFilter() {}
 
  MIBloomFilter(size_t bv_size, unsigned hash_num, std::string hash_fn = "");
 
  MIBloomFilter(sdsl::bit_vector& bit_vector,
                unsigned hash_num,
                std::string hash_fn = "");
 
  explicit MIBloomFilter(const std::string& path);
 
  void complete_bv_insertion();
 
  void complete_id_insertion() { id_insertion_completed = true; }
 
  void insert_bv(const uint64_t* hashes);
 
  void insert_bv(const std::vector<uint64_t>& hashes)
  {
    insert_bv(hashes.data());
  }
 
  bool bv_contains(const uint64_t* hashes);
 
  bool bv_contains(const std::vector<uint64_t>& hashes)
  {
    return bv_contains(hashes.data());
  }
 
  void insert_id(const uint64_t* hashes, const T& id);
 
  void insert_id(const std::vector<uint64_t>& hashes, const T& id)
  {
    insert_id(hashes.data(), id);
  }
 
  std::vector<T> get_id(const uint64_t* hashes);
 
  std::vector<T> get_id(const std::vector<uint64_t>& hashes)
  {
    return get_id(hashes.data());
  }
 
  void insert_saturation(const uint64_t* hashes, const T& id);
 
  void insert_saturation(const std::vector<uint64_t>& hashes, const T& id)
  {
    insert_saturation(hashes.data(), id);
  }
 
  void save(const std::string& path);
 
  uint64_t get_pop_cnt();
 
  uint64_t get_pop_saturated_cnt();
 
  unsigned get_hash_num() const { return hash_num; }
 
  unsigned get_k() const { return kmer_size; }
 
  const std::string& get_hash_fn() const { return hash_fn; }
 
  std::vector<size_t> get_id_occurence_count(const bool& include_saturated);
 
  static size_t calc_optimal_size(size_t entries,
                                  unsigned hash_num,
                                  double occupancy);
 
private:
  MIBloomFilter(const std::shared_ptr<MIBloomFilterInitializer>& mibfi);
  static void save(const std::string& path,
                   const cpptoml::table& table,
                   const char* data,
                   size_t n);
  std::vector<uint64_t> get_rank_pos(const uint64_t* hashes) const;
  uint64_t get_rank_pos(const uint64_t hash) const
  {
    return bv_rank_support(hash % il_bit_vector.size());
  }
  std::vector<T> get_data(const std::vector<uint64_t>& rank_pos) const;
  T get_data(const uint64_t& rank) const { return id_array[rank]; }
  void set_data(const uint64_t& pos, const T& id);
  void set_saturated(const uint64_t* hashes);
 
  size_t id_array_size = 0;
  size_t bv_size = 0;
  unsigned kmer_size = 0;
  unsigned hash_num = 0;
  std::string hash_fn;
 
  sdsl::bit_vector bit_vector;
  sdsl::bit_vector_il<BLOCKSIZE> il_bit_vector;
  sdsl::rank_support_il<1> bv_rank_support;
  std::unique_ptr<std::atomic<uint16_t>[]> counts_array;
  std::unique_ptr<std::atomic<T>[]> id_array;
 
  bool bv_insertion_completed = false, id_insertion_completed = false;
};
 
} // namespace btllib
 
#include "mi_bloom_filter-inl.hpp"
 
#endif