FrozenKeyIdxBiMap.h

Go to the documentation of this file.

 
#pragma once
 
#include <cstdint>
#include <cstring>
#include <limits>
#include <memory>
#include <optional>
#include <string>
#include <string_view>
#include <vector>
 
#include "error_handling.h"
 
namespace utils
{
 
namespace bimap_detail
{
 
struct HashRsltPack {
  std::uint16_t keylen;
  std::uint32_t hash;
};
 
inline bool operator==(const HashRsltPack& a, const HashRsltPack& b)
{
  return a.keylen == b.keylen && a.hash == b.hash;
}
 
template <int MaxKeyLen = std::numeric_limits<std::uint16_t>::max()>
struct FNV1aHasher {
  static_assert(0 <= MaxKeyLen && MaxKeyLen <= std::numeric_limits<std::uint16_t>::max(),
                "MaxKeyLen can't be encoded by HashRsltPack");
 
  inline static constexpr uint32_t FNV1A_PRIME  = 16777619;
  inline static constexpr uint32_t FNV1A_OFFSET = 2166136261;
 
  static std::optional<HashRsltPack> calc(const char* key)
  {
    std::uint32_t hash = FNV1A_OFFSET;
    for (int i = 0; i <= MaxKeyLen; i++) {  // the `<=` is intentional
      if (key[i] == '\0') {
        return {HashRsltPack{static_cast<uint16_t>(i), hash}};
      }
      hash = (hash ^ key[i]) * FNV1A_PRIME;
    }
    return std::nullopt;
  }
 
  // this mostly exists as a convenience
  static std::optional<HashRsltPack> calc(std::string_view key)
  {
    int len = key.size();
    if (len > MaxKeyLen) {
      return std::nullopt;
    }
    std::uint32_t hash = FNV1A_OFFSET;
    for (int i = 0; i < len; i++) {
      hash = (hash ^ key[i]) * FNV1A_PRIME;
    }
    return {HashRsltPack{static_cast<uint16_t>(len), hash}};
  }
};
 
struct Row {
  // smallest structs members are listed first to minimize struct size
  uint16_t value  = 0;        
  uint16_t keylen = 0;        
  const char* key = nullptr;  
};
 
}  // namespace bimap_detail
 
class FrozenKeyIdxBiMap
{
  // define attributes:
 
  std::shared_ptr<bimap_detail::Row[]> table_rows_;
  std::shared_ptr<uint16_t[]> ordered_row_indices_;
  uint16_t capacity_;
  uint16_t length_;
  uint16_t max_probe_;
 
  // define a few constants
 
  inline static constexpr int LOAD_FACTOR_NUMERATOR   = 2;
  inline static constexpr int LOAD_FACTOR_DENOMINATOR = 3;
  static_assert(LOAD_FACTOR_NUMERATOR <= LOAD_FACTOR_DENOMINATOR);
 
  inline static constexpr int64_t MAX_CAPACITY = static_cast<int64_t>(std::numeric_limits<uint16_t>::max());
  inline static constexpr int64_t MAX_LEN      = MAX_CAPACITY * LOAD_FACTOR_NUMERATOR / LOAD_FACTOR_DENOMINATOR;
 
  inline static constexpr uint16_t MAX_KEY_LEN = 21;
 
 public:  // Interface:
  FrozenKeyIdxBiMap() : table_rows_(nullptr), ordered_row_indices_(nullptr), capacity_(0), length_(0), max_probe_(0) {}
 
  explicit FrozenKeyIdxBiMap(const std::vector<std::string>& keys) noexcept;
 
  std::optional<int> find(const char* key) const noexcept;
  std::optional<int> find(std::string_view key) const noexcept;
  /*
  std::optional<int> find(const std::string& key) const noexcept {
    return this->find(std::string_view(key));
  }*/
 
  std::string inverse_find(int index) const
  {
    uint16_t row_index = ordered_row_indices_.get()[index];
    return {table_rows_.get()[row_index].key};
  }
 
  std::size_t size() const noexcept { return length_; }
};
 
}  // namespace utils