Compile time inverse indexing in C++

inverse-index.cpp

#include <cstdint>
#include <string_view>
#include <memory>

constexpr uint32_t fnv_1a(std::string_view sv) {
  uint32_t hash = 0x811c9dc5;
  for (char c : sv) {
    hash ^= (uint8_t)c;
    hash *= 0x01000193;
  }
  return hash;
}

constexpr uint32_t compute_shift(uint32_t x) {
  uint32_t res = 1;
  uint32_t shift = 31;
  while (res < x) {
    res <<= 1;
    --shift;
  }
  return shift;
}

template<uint32_t N>
struct InverseIndex {
  static constexpr uint32_t ht_shift = compute_shift(N);
  static constexpr uint32_t ht_size = 1 << (32 - ht_shift);

  const std::string_view (*idx_map)[N];
  uint32_t keys[ht_size];

  constexpr InverseIndex(const std::string_view (*map)[N]) : idx_map{map}, keys{{0}} {
    for (uint32_t i = 0; i < N; ++i) {
      uint32_t h = fnv_1a((*map)[i]) >> ht_shift;
      while (keys[h]) {
        h = (h + 1) & (ht_size - 1);
      }
      keys[h] = i + 1;
    }
  }

  constexpr uint32_t operator[](std::string_view sv) const {
    uint32_t h = fnv_1a(sv) >> ht_shift;
    while (keys[h] && (*idx_map)[keys[h] - 1] != sv) {
      h = (h + 1) & (ht_size - 1);
    }
    return keys[h] - 1;
  }
};

template<>
struct InverseIndex<0> {
  const std::string_view *idx_map;
  const uint32_t ht_shift;
  const uint32_t ht_size;
  const std::unique_ptr<uint32_t[]> keys;

  constexpr InverseIndex(const std::string_view *map, uint32_t count)
    : idx_map{map},
      ht_shift{(uint32_t)__builtin_clz(count - 1) - 1},
      ht_size{(uint32_t)1 << (32 - ht_shift)},
      keys{std::make_unique<uint32_t[]>(ht_size)} {
    for (uint32_t i = 0; i < count; ++i) {
      uint32_t h = fnv_1a(map[i]) >> ht_shift;
      while (keys[h]) {
        h = (h + 1) & (ht_size - 1);
      }
      keys[h] = i + 1;
    }
  }

  constexpr uint32_t operator[](std::string_view sv) const {
    uint32_t h = fnv_1a(sv) >> ht_shift;
    while (keys[h] && idx_map[keys[h] - 1] != sv) {
      h = (h + 1) & (ht_size - 1);
    }
    return keys[h] - 1;
  }
};

enum WeekDay {
  WEEKDAY_MONDAY = 0,
  WEEKDAY_TUESDAY,
  WEEKDAY_WEDNESDAY,
  WEEKDAY_THURSDAY,
  WEEKDAY_FRIDAY,
  WEEKDAY_SATURDAY,
  WEEKDAY_SUNDAY,
  WEEKDAY_COUNT,
};

constexpr std::string_view WeekDay_str[WEEKDAY_COUNT] = {
  "Monday",
  "Tuesday",
  "Wednesday",
  "Thursday",
  "Friday",
  "Saturday",
  "Sunday"
};

constexpr InverseIndex<WEEKDAY_COUNT> inv = {&WeekDay_str};
static_assert(inv["Monday"] == WEEKDAY_MONDAY);
static_assert(inv["Tuesday"] == WEEKDAY_TUESDAY);
static_assert(inv["Wednesday"] == WEEKDAY_WEDNESDAY);
static_assert(inv["Thursday"] == WEEKDAY_THURSDAY);
static_assert(inv["Friday"] == WEEKDAY_FRIDAY);
static_assert(inv["Saturday"] == WEEKDAY_SATURDAY);
static_assert(inv["Sunday"] == WEEKDAY_SUNDAY);
static_assert(inv["Anything"] == -1);
static_assert(inv["Else"] == -1);