bool shouldUseCompactTable(size_t num_hosts, uint64_t table_size) {

#ifdef MAGLEV_LB_FORCE_ORIGINAL_IMPL

  return false;

  if (num_hosts > MaglevTable::MaxNumberOfHostsForCompactMaglev) {

  constexpr size_t shared_ptr_size = sizeof(HostConstSharedPtr);

  const uint64_t original_maglev_cost = shared_ptr_size * table_size;

  const uint64_t compact_maglev_cost =

      shared_ptr_size * num_hosts + ((absl::bit_width(num_hosts) * table_size) / 8);

  return compact_maglev_cost < original_maglev_cost;

}

                    bool use_hostname_for_hashing, MaglevLoadBalancerStats& stats) {

    MaglevTableSharedPtr maglev_table;

    if (shouldUseCompactTable(normalized_host_weights.size(), table_size)) {

      maglev_table =

          std::make_shared<CompactMaglevTable>(normalized_host_weights, max_normalized_weight,

                                               table_size, use_hostname_for_hashing, stats);

      ENVOY_LOG(debug, "creating compact maglev table given table size {} and number of hosts {}",

                table_size, normalized_host_weights.size());

    } else {

      maglev_table =

          std::make_shared<OriginalMaglevTable>(normalized_host_weights, max_normalized_weight,

                                                table_size, use_hostname_for_hashing, stats);

      ENVOY_LOG(debug, "creating original maglev table given table size {} and number of hosts {}",

                table_size, normalized_host_weights.size());

    }

    return maglev_table;

  }

                                         const LegacyMaglevLbProto& lb_config) {

  LoadBalancerConfigHelper::convertHashLbConfigTo(common_lb_config, lb_config_);

  if (common_lb_config.has_locality_weighted_lb_config()) {

    lb_config_.mutable_locality_weighted_lb_config();

  }

  if (lb_config.has_table_size()) {

    *lb_config_.mutable_table_size() = lb_config.table_size();

  }

}

    : TypedHashLbConfigBase(lb_config.consistent_hashing_lb_config().hash_policy(), regex_engine,

                            creation_status),

      lb_config_(lb_config) {}

                                       double max_normalized_weight) {

  HashingLoadBalancerSharedPtr maglev_lb =

      MaglevFactory::createMaglevTable(normalized_host_weights, max_normalized_weight, table_size_,

                                       use_hostname_for_hashing_, stats_);

  if (hash_balance_factor_ == 0) {

    return maglev_lb;

  }

  return std::make_shared<BoundedLoadHashingLoadBalancer>(

      maglev_lb, std::move(normalized_host_weights), hash_balance_factor_);

}

    bool use_hostname_for_hashing) {

  if (normalized_host_weights.empty()) {

    ENVOY_LOG(debug, "maglev: normalized hosts weights is empty, skipping building table");

    return;

  }

  std::vector<std::tuple<absl::string_view, HostConstSharedPtr, double>> sorted_host_weights;

  sorted_host_weights.reserve(normalized_host_weights.size());

  for (const auto& host_weight : normalized_host_weights) {

    const auto& host = host_weight.first;

    const absl::string_view key_to_hash = hashKey(host, use_hostname_for_hashing);

    ASSERT(!key_to_hash.empty());

    sorted_host_weights.emplace_back(key_to_hash, host_weight.first, host_weight.second);

  }

  std::sort(sorted_host_weights.begin(), sorted_host_weights.end());

  std::vector<TableBuildEntry> table_build_entries;

  table_build_entries.reserve(normalized_host_weights.size());

  for (const auto& sorted_host_weight : sorted_host_weights) {

    const auto& key_to_hash = std::get<0>(sorted_host_weight);

    const auto& host = std::get<1>(sorted_host_weight);

    const auto& weight = std::get<2>(sorted_host_weight);

    table_build_entries.emplace_back(host, HashUtil::xxHash64(key_to_hash) % table_size_,

                                     (HashUtil::xxHash64(key_to_hash, 1) % (table_size_ - 1)) + 1,

                                     weight);

  }

  constructImplementationInternals(table_build_entries, max_normalized_weight);

  uint64_t min_entries_per_host = table_size_;

  uint64_t max_entries_per_host = 0;

  for (const auto& entry : table_build_entries) {

    min_entries_per_host = std::min(entry.count_, min_entries_per_host);

    max_entries_per_host = std::max(entry.count_, max_entries_per_host);

  }

  stats_.min_entries_per_host_.set(min_entries_per_host);

  stats_.max_entries_per_host_.set(max_entries_per_host);

  if (ENVOY_LOG_CHECK_LEVEL(trace)) {

}

    std::vector<TableBuildEntry>& table_build_entries, double max_normalized_weight) {

  table_.resize(table_size_);

  uint64_t table_index = 0;

  for (uint32_t iteration = 1; table_index < table_size_; ++iteration) {

    for (uint64_t i = 0; i < table_build_entries.size() && table_index < table_size_; i++) {

      TableBuildEntry& entry = table_build_entries[i];

      if (iteration * entry.weight_ < entry.target_weight_) {

        continue;

      }

      entry.target_weight_ += max_normalized_weight;

      uint64_t c = permutation(entry);

      while (table_[c] != nullptr) {

        entry.next_++;

        c = permutation(entry);

      }

      table_[c] = entry.host_;

      entry.next_++;

      entry.count_++;

      table_index++;

    }

  }

}

    : MaglevTable(table_size, stats),

      table_(absl::bit_width(normalized_host_weights.size()), table_size) {

  constructMaglevTableInternal(normalized_host_weights, max_normalized_weight,

                               use_hostname_for_hashing);

}

    std::vector<TableBuildEntry>& table_build_entries, double max_normalized_weight) {

  host_table_.reserve(table_build_entries.size());

  for (const auto& entry : table_build_entries) {

    host_table_.emplace_back(entry.host_);

  }

  host_table_.shrink_to_fit();

  std::vector<bool> occupied(table_size_, false);

  uint64_t table_index = 0;

  for (uint32_t iteration = 1; table_index < table_size_; ++iteration) {

    for (uint32_t i = 0; i < table_build_entries.size() && table_index < table_size_; i++) {

      TableBuildEntry& entry = table_build_entries[i];

      if (iteration * entry.weight_ < entry.target_weight_) {

        continue;

      }

      entry.target_weight_ += max_normalized_weight;

      uint32_t c = static_cast<uint32_t>(permutation(entry));

      while (occupied[c]) {

        entry.next_++;

        c = static_cast<uint32_t>(permutation(entry));

      }

      table_.set(c, i);

      occupied[c] = true;

      entry.next_++;

      entry.count_++;

      table_index++;

    }

  }

}

void CompactMaglevTable::logMaglevTable(bool use_hostname_for_hashing) const {

  for (uint64_t i = 0; i < table_size_; ++i) {

    const uint32_t index = table_.get(i);

    ASSERT(index < host_table_.size(), "Compact MaglevTable index into host table out of range");

    const auto& host = host_table_[index];

    const absl::string_view key_to_hash = hashKey(host, use_hostname_for_hashing);

    ENVOY_LOG(trace, "maglev: i={} address={} host={}", i, host->address()->asString(),

              key_to_hash);

  }

}

    : table_size_(table_size), stats_(stats) {}

HostSelectionResponse OriginalMaglevTable::chooseHost(uint64_t hash, uint32_t attempt) const {

  if (table_.empty()) {

    return {nullptr};

  }

  if (attempt > 0) {

    hash ^= ~0ULL - attempt + 1;

  }

  return {table_[hash % table_size_]};

}

HostSelectionResponse CompactMaglevTable::chooseHost(uint64_t hash, uint32_t attempt) const {

  if (host_table_.empty()) {

    return {nullptr};

  }

  if (attempt > 0) {

    hash ^= ~0ULL - attempt + 1;

  }

  const uint32_t index = table_.get(hash % table_size_);

  ASSERT(index < host_table_.size(), "Compact MaglevTable index into host table out of range");

  return {host_table_[index]};

}

uint64_t MaglevTable::permutation(const TableBuildEntry& entry) {

  return (entry.offset_ + (entry.skip_ * entry.next_)) % table_size_;

}

    : ThreadAwareLoadBalancerBase(priority_set, stats, runtime, random, healthy_panic_threshold,

                                  config.has_locality_weighted_lb_config(), std::move(hash_policy)),

      scope_(scope.createScope("maglev_lb.")), stats_(generateStats(*scope_)),

          PROTOBUF_GET_WRAPPED_OR_DEFAULT(config, table_size, MaglevTable::DefaultTableSize)),

          config.has_consistent_hashing_lb_config()

              ? config.consistent_hashing_lb_config().use_hostname_for_hashing()

              : false),

      hash_balance_factor_(PROTOBUF_GET_WRAPPED_OR_DEFAULT(config.consistent_hashing_lb_config(),

                                                           hash_balance_factor, 0)) {

  ENVOY_LOG(debug, "maglev table size: {}", table_size_);

  if (!Primes::isPrime(table_size_)) {

    throw EnvoyException("The table size of maglev must be prime number");

  }

}

MaglevLoadBalancerStats MaglevLoadBalancer::generateStats(Stats::Scope& scope) {

  return {ALL_MAGLEV_LOAD_BALANCER_STATS(POOL_GAUGE(scope))};

}