text: #include "MinimizerIndex.hpp"
  
  MinimizerIndex::MinimizerIndex() :  table_keys(nullptr), table_tinyv(nullptr), table_tinyv_sz(nullptr),
                                      size_(0), pop(0), num_empty(0)  {
  
      empty_key.set_empty();
      deleted_key.set_deleted();
  
      const size_t l_lck_block_sz = lck_block_sz;
  
      init_tables(std::max(static_cast<size_t>(1024), l_lck_block_sz));
  }
  
  MinimizerIndex::MinimizerIndex(const size_t sz) :   table_keys(nullptr), table_tinyv(nullptr), table_tinyv_sz(nullptr),
                                                      size_(0), pop(0), num_empty(0) {
  
      empty_key.set_empty();
      deleted_key.set_deleted();
  
      const size_t l_lck_block_sz = lck_block_sz;
  
      init_tables(std::max(static_cast<size_t>(1.2 * sz), l_lck_block_sz));
  }
  
  MinimizerIndex::MinimizerIndex(const MinimizerIndex& o) :   size_(o.size_), pop(o.pop), num_empty(o.num_empty),
                                                              empty_key(o.empty_key), deleted_key(o.deleted_key) {
  
      table_keys = new Minimizer[size_];
      table_tinyv = new packed_tiny_vector[size_];
      table_tinyv_sz = new uint8_t[size_];
  
      lck_min = vector<SpinLock>(o.lck_min.size());
  
      std::copy(o.table_keys, o.table_keys + size_, table_keys);
  
      for (size_t i = 0; i < size_; ++i){
  
          table_tinyv_sz[i] = packed_tiny_vector::FLAG_EMPTY;
          table_tinyv[i].copy(table_tinyv_sz[i], o.table_tinyv[i], o.table_tinyv_sz[i]);
      }
  }
  
  MinimizerIndex::MinimizerIndex(MinimizerIndex&& o){
  
      size_ = o.size_;
      pop = o.pop;
      num_empty = o.num_empty;
  
      empty_key = o.empty_key;
      deleted_key = o.deleted_key;
  
      table_keys = o.table_keys;
      table_tinyv = o.table_tinyv;
      table_tinyv_sz = o.table_tinyv_sz;
  
      lck_min = vector<SpinLock>(o.lck_min.size());
  
      o.table_keys = nullptr;
      o.table_tinyv = nullptr;
      o.table_tinyv_sz = nullptr;
  
      o.clear();
  }
  
  MinimizerIndex& MinimizerIndex::operator=(const MinimizerIndex& o) {
  
      if (this != &o) {
  
          clear();
  
          size_ = o.size_;
          pop = o.pop;
          num_empty = o.num_empty;
  
          empty_key = o.empty_key;
          deleted_key = o.deleted_key;
  
          table_keys = new Minimizer[size_];
          table_tinyv = new packed_tiny_vector[size_];
          table_tinyv_sz = new uint8_t[size_];
  
          lck_min = vector<SpinLock>(o.lck_min.size());
  
          std::copy(o.table_keys, o.table_keys + size_, table_keys);
  
          for (size_t i = 0; i < size_; ++i){
  
              table_tinyv_sz[i] = packed_tiny_vector::FLAG_EMPTY;
              table_tinyv[i].copy(table_tinyv_sz[i], o.table_tinyv[i], o.table_tinyv_sz[i]);
          }
      }
  
      return *this;
  }
  
  MinimizerIndex& MinimizerIndex::operator=(MinimizerIndex&& o){
  
      if (this != &o) {
  
          clear();
  
          size_ = o.size_;
          pop = o.pop;
          num_empty = o.num_empty;
  
          empty_key = o.empty_key;
          deleted_key = o.deleted_key;
  
          table_keys = o.table_keys;
          table_tinyv = o.table_tinyv;
          table_tinyv_sz = o.table_tinyv_sz;
  
          lck_min = vector<SpinLock>(o.lck_min.size());
  
          o.table_keys = nullptr;
          o.table_tinyv = nullptr;
          o.table_tinyv_sz = nullptr;
  
          o.clear();
      }
  
      return *this;
  }
  
  MinimizerIndex::~MinimizerIndex() {
  
      clear();
  }
  
  void MinimizerIndex::clear() {
  
      if (table_tinyv != nullptr){
  
          for (size_t i = 0; i < size_; ++i) table_tinyv[i].destruct(table_tinyv_sz[i]);
      }
  
      clear_tables();
  
      lck_min.clear();
      lck_edit_table.release_all();
  }
  
  MinimizerIndex::iterator MinimizerIndex::find(const Minimizer& key) {
  
      const size_t end_table = size_-1;
  
      size_t h = key.hash() & end_table;
      size_t i = 0;
  
      while (i != size_) {
  
          if ((table_keys[h] == empty_key) || (table_keys[h] == key)) break;
  
          h = (h+1) & end_table;
          ++i;
      }
  
      if ((i != size_) && (table_keys[h] == key)) return iterator(this, h);
  
      return iterator(this);
  }
  
  MinimizerIndex::const_iterator MinimizerIndex::find(const Minimizer& key) const {
  
      const size_t end_table = size_-1;
  
      size_t h = key.hash() & end_table;
      size_t i = 0;
  
      while (i != size_) {
  
          if ((table_keys[h] == empty_key) || (table_keys[h] == key)) break;
  
          h = (h+1) & end_table;
          ++i;
      }
  
      if ((i != size_) && (table_keys[h] == key)) return const_iterator(this, h);
  
      return const_iterator(this);
  }
  
  MinimizerIndex::iterator MinimizerIndex::find(const size_t h) {
  
      if ((h < size_) && (table_keys[h] != empty_key) && (table_keys[h] != deleted_key)) return iterator(this, h);
  
      return iterator(this);
  }
  
  MinimizerIndex::const_iterator MinimizerIndex::find(const size_t h) const {
  
      if ((h < size_) && (table_keys[h] != empty_key) && (table_keys[h] != deleted_key)) return const_iterator(this, h);
  
      return const_iterator(this);
  }
  
  MinimizerIndex::iterator MinimizerIndex::erase(const_iterator it) {
  
      if (it == end()) return end();
  
      table_keys[it.h] = deleted_key;
      table_tinyv[it.h].destruct(table_tinyv_sz[it.h]);
      table_tinyv_sz[it.h] = packed_tiny_vector::FLAG_EMPTY;
  
      --pop;
  
      return ++iterator(this, it.h); // return pointer to next element
  }
  
  size_t MinimizerIndex::erase(const Minimizer& minz) {
  
      const size_t end_table = size_-1;
      const size_t oldpop = pop;
  
      size_t h = minz.hash() & end_table;
      size_t i = 0;
  
      while (i != size_) {
  
          if ((table_keys[h] == empty_key) || (table_keys[h] == minz)) break;
  
          h = (h+1) & end_table;
          ++i;
      }
  
      if ((i != size_) && (table_keys[h] == minz)){
  
          table_keys[h] = deleted_key;
          table_tinyv[h].destruct(table_tinyv_sz[h]);
          table_tinyv_sz[h] = packed_tiny_vector::FLAG_EMPTY;
  
          --pop;
      }
  
      return oldpop - pop;
  }
  
  pair<MinimizerIndex::iterator, bool> MinimizerIndex::insert(const Minimizer& key, const packed_tiny_vector& v, const uint8_t& flag) {
  
      if ((5 * num_empty) < size_) reserve(2 * size_); // if more than 80% full, resize
  
      bool is_deleted = false;
  
      const size_t end_table = size_-1;
      const size_t h = key.hash() & end_table;
  
      size_t h1 = h;
      size_t h2;
  
      while (true) {
  
          if (table_keys[h1] == empty_key) {
  
              is_deleted ? (h1 = h2) : --num_empty;
  
              table_keys[h1] = key;
              table_tinyv_sz[h1] = packed_tiny_vector::FLAG_EMPTY;
  
              table_tinyv[h1].copy(table_tinyv_sz[h1], v, flag);
  
              ++pop;
  
              return {iterator(this, h1), true};
          }
          else if (table_keys[h1] == key){
  
              return {iterator(this, h1), false};
          }
          else if (!is_deleted && (table_keys[h1] == deleted_key)) {
  
              is_deleted = true;
              h2 = h1;
          }
  
          h1 = (h1+1) & end_table;
      }
  }
  
  void MinimizerIndex::init_threads() {
  
      lck_min = vector<SpinLock>((size_ + lck_block_sz - 1) / lck_block_sz);
  
      pop_p = pop;
      num_empty_p = num_empty;
  }
  
  void MinimizerIndex::release_threads() {
  
      pop = pop_p;
      num_empty = num_empty_p;
  
      lck_min.clear();
      lck_edit_table.release_all();
  }
  
  MinimizerIndex::iterator MinimizerIndex::find_p(const Minimizer& key) {
  
      lck_edit_table.acquire_reader();
  
      const size_t end_table = size_-1;
  
      size_t i = 0;
      size_t h = key.hash() & end_table;
      size_t id_block = h >> lck_block_div_shift;
  
      lck_min[id_block].acquire();
  
      while (i != size_) {
  
          if ((h >> lck_block_div_shift) != id_block){
  
              lck_min[id_block].release();
              id_block = h >> lck_block_div_shift;
              lck_min[id_block].acquire();
          }
  
          if (table_keys[h] == empty_key){
  
              lck_min[id_block].release();
              lck_edit_table.release_reader();
  
              iterator(this);
          }
          else if (table_keys[h] == key) return iterator(this, h);
  
          h = (h+1) & end_table;
          ++i;
      }
  
      lck_min[id_block].release();
      lck_edit_table.release_reader();
  
      return iterator(this);
  }
  
  MinimizerIndex::const_iterator MinimizerIndex::find_p(const Minimizer& key) const {
  
      lck_edit_table.acquire_reader();
  
      const size_t end_table = size_-1;
  
      size_t i = 0;
      size_t h = key.hash() & end_table;
      size_t id_block = h >> lck_block_div_shift;
  
      lck_min[id_block].acquire();
  
      while (i != size_) {
  
          if ((h >> lck_block_div_shift) != id_block){
  
              lck_min[id_block].release();
              id_block = h >> lck_block_div_shift;
              lck_min[id_block].acquire();
          }
  
          if (table_keys[h] == empty_key){
  
              lck_min[id_block].release();
              lck_edit_table.release_reader();
  
              const_iterator(this);
          }
          else if (table_keys[h] == key) return const_iterator(this, h);
  
          h = (h+1) & end_table;
          ++i;
      }
  
      lck_min[id_block].release();
      lck_edit_table.release_reader();
  
      return const_iterator(this);
  }
  
  MinimizerIndex::iterator MinimizerIndex::find_p(const size_t h) {
  
      lck_edit_table.acquire_reader();
  
      if (h < size_){
  
          const size_t id_block = h >> lck_block_div_shift;
  
          lck_min[id_block].acquire();
  
          if ((table_keys[h] != empty_key) && (table_keys[h] != deleted_key)) return iterator(this, h);
  
          lck_min[id_block].release();
      }
  
      lck_edit_table.release_reader();
  
      return iterator(this);
  }
  
  MinimizerIndex::const_iterator MinimizerIndex::find_p(const size_t h) const {
  
      lck_edit_table.acquire_reader();
  
      if (h < size_){
  
          const size_t id_block = h >> lck_block_div_shift;
  
          lck_min[id_block].acquire();
  
          if ((table_keys[h] != empty_key) && (table_keys[h] != deleted_key)) return const_iterator(this, h);
  
          lck_min[id_block].release();
      }
  
      lck_edit_table.release_reader();
  
      return const_iterator(this);
  }
  
  void MinimizerIndex::release_p(const_iterator it) const {
  
      if (it != end()){
  
          lck_min[it.h >> lck_block_div_shift].release();
          lck_edit_table.release_reader();
      }
  }
  
  void MinimizerIndex::release_p(iterator it) {
  
      if (it != end()){
  
          lck_min[it.h >> lck_block_div_shift].release();
          lck_edit_table.release_reader();
      }
  }
  
  size_t MinimizerIndex::erase_p(const Minimizer& minz) {
  
      lck_edit_table.acquire_reader();
  
      const size_t end_table = size_ - 1;
  
      size_t i = 0;
      size_t h = minz.hash() & end_table;
      size_t id_block = h >> lck_block_div_shift;
      size_t l_pop = pop;
  
      lck_min[id_block].acquire();
  
      while (i != size_) {
  
          if ((h >> lck_block_div_shift) != id_block){
  
              lck_min[id_block].release();
              id_block = h >> lck_block_div_shift;
              lck_min[id_block].acquire();
          }
  
          if (table_keys[h] == empty_key){
  
              lck_min[id_block].release();
              lck_edit_table.release_reader();
  
              return 0;
          }
          else if (table_keys[h] == minz) break;
  
          h = (h+1) & end_table;
          ++i;
      }
  
      if ((i != size_) && (table_keys[h] == minz)){
  
          table_keys[h] = deleted_key;
          table_tinyv[h].destruct(table_tinyv_sz[h]);
          table_tinyv_sz[h] = packed_tiny_vector::FLAG_EMPTY;
  
          lck_min[id_block].release();
  
          --pop;
      }
  
      l_pop -= pop;
  
      lck_edit_table.release_reader();
  
      return l_pop;
  }
  
  pair<MinimizerIndex::iterator, bool> MinimizerIndex::insert_p(const Minimizer& key, const packed_tiny_vector& v, const uint8_t& flag) {
  
      bool is_deleted = false;
  
      lck_edit_table.acquire_reader();
  
      if ((5 * num_empty_p) < size_){
  
          lck_edit_table.release_reader();
          lck_edit_table.acquire_writer();
  
          reserve(2 * size_); // if more than 80% full, resize
  
          pop_p = pop;
          num_empty_p = num_empty;
  
          lck_edit_table.release_writer_acquire_reader();
      }
  
      const size_t end_table = size_-1;
      const size_t h = key.hash() & end_table;
  
      size_t id_block = h >> lck_block_div_shift;
  
      size_t h1 = h;
      size_t h2;
  
      lck_min[id_block].acquire();
  
      while (true) {
  
          if ((h1 >> lck_block_div_shift) != id_block){
  
              lck_min[id_block].release();
              id_block = h1 >> lck_block_div_shift;
              lck_min[id_block].acquire();
          }
  
          if (table_keys[h1] == empty_key) {
  
              if (is_deleted){
  
                  const size_t id_block2 = h2 >> lck_block_div_shift;
  
                  if (id_block2 == id_block) h1 = h2;
                  else {
  
                      lck_min[id_block2].acquire();
  
                      if (table_keys[h2] == deleted_key){
  
                          lck_min[id_block].release();
                          h1 = h2;
                      }
                      else {
  
                          lck_min[id_block2].release();
                          --num_empty_p;
                      }
                  }
              }
              else --num_empty_p;
  
              table_keys[h1] = key;
              table_tinyv_sz[h1] = packed_tiny_vector::FLAG_EMPTY;
  
              table_tinyv[h1].copy(table_tinyv_sz[h1], v, flag);
  
              ++pop_p;
  
              return {iterator(this, h1), true};
          }
          else if (table_keys[h1] == key){
  
              return {iterator(this, h1), false};
          }
          else if (!is_deleted && (table_keys[h1] == deleted_key)) {
  
              is_deleted = true;
              h2 = h1;
          }
  
          h1 = (h1+1) & end_table;
      }
  
      lck_min[id_block].release(); // Just for safety
      lck_edit_table.release_reader(); // Just for safety
  }
  
  MinimizerIndex::iterator MinimizerIndex::begin() {
  
      iterator it(this);
      it.operator++();
      return it;
  }
  
  MinimizerIndex::const_iterator MinimizerIndex::begin() const {
  
      const_iterator it(this);
      it.operator++();
      return it;
  }
  
  MinimizerIndex::iterator MinimizerIndex::end() {
  
      return iterator(this);
  }
  
  MinimizerIndex::const_iterator MinimizerIndex::end() const {
  
      return const_iterator(this);
  }
  
  void MinimizerIndex::clear_tables() {
  
      if (table_keys != nullptr) {
  
          delete[] table_keys;
          table_keys = nullptr;
      }
  
      if (table_tinyv != nullptr) {
  
          delete[] table_tinyv;
          table_tinyv = nullptr;
      }
  
      if (table_tinyv_sz != nullptr) {
  
          delete[] table_tinyv_sz;
          table_tinyv_sz = nullptr;
      }
  
      size_ = 0;
      pop  = 0;
      num_empty = 0;
  }
  
  void MinimizerIndex::init_tables(const size_t sz) {
  
      clear_tables();
  
      pop = 0;
      size_ = rndup(sz);
      num_empty = size_;
  
      table_keys = new Minimizer[size_];
      table_tinyv = new packed_tiny_vector[size_];
      table_tinyv_sz = new uint8_t[size_];
  
      std::fill(table_keys, table_keys + size_, empty_key);
  
      memset(table_tinyv_sz, packed_tiny_vector::FLAG_EMPTY, size_ * sizeof(uint8_t));
  }
  
  void MinimizerIndex::reserve(const size_t sz) {
  
      if (sz <= size_) return;
  
      Minimizer* old_table_keys = table_keys;
      packed_tiny_vector* old_table_tinyv = table_tinyv;
      uint8_t* old_table_tinyv_sz = table_tinyv_sz;
  
      const size_t old_size_ = size_;
  
      size_ = rndup(sz);
      pop = 0;
      num_empty = size_;
  
      table_keys = new Minimizer[size_];
      table_tinyv = new packed_tiny_vector[size_];
      table_tinyv_sz = new uint8_t[size_];
  
      if (!lck_min.empty()) lck_min = vector<SpinLock>((size_ + lck_block_sz - 1) / lck_block_sz);
  
      std::fill(table_keys, table_keys + size_, empty_key);
  
      memset(table_tinyv_sz, packed_tiny_vector::FLAG_EMPTY, size_ * sizeof(uint8_t));
  
      for (size_t i = 0; i < old_size_; ++i) {
  
          if (old_table_keys[i] != empty_key && old_table_keys[i] != deleted_key){
  
              insert(old_table_keys[i], old_table_tinyv[i], old_table_tinyv_sz[i]);
  
              old_table_tinyv[i].destruct(old_table_tinyv_sz[i]);
          }
      }
  
      delete[] old_table_keys;
      delete[] old_table_tinyv;
      delete[] old_table_tinyv_sz;
  }
  
  const size_t MinimizerIndex::lck_block_sz = 64;
  const size_t MinimizerIndex::lck_block_div_shift = 6;
  