size_t StatName::dataSize() const {

  if (size_and_data_ == nullptr) {

    return 0;

  }

  return SymbolTable::Encoding::decodeNumber(size_and_data_).first;

}

SymbolTable::Encoding::~Encoding() {

  ASSERT(mem_block_.capacity() == 0);

}

size_t SymbolTable::Encoding::encodingSizeBytes(uint64_t number) {

  size_t num_bytes = 0;

  do {

    ++num_bytes;

    number >>= 7;

  } while (number != 0);

  return num_bytes;

}

void SymbolTable::Encoding::appendEncoding(uint64_t number, MemBlockBuilder<uint8_t>& mem_block) {

  do {

    if (number < (1 << 7)) {

      mem_block.appendOne(number); // number <= 127 gets encoded in one byte.

    } else {

      mem_block.appendOne((number & Low7Bits) | SpilloverMask); // >= 128 need spillover bytes.

    }

    number >>= 7;

  } while (number != 0);

}

void SymbolTable::Encoding::addSymbols(const std::vector<Symbol>& symbols) {

  ASSERT(data_bytes_required_ == 0);

  for (Symbol symbol : symbols) {

    data_bytes_required_ += encodingSizeBytes(symbol);

  }

  mem_block_.setCapacity(data_bytes_required_);

  for (Symbol symbol : symbols) {

    appendEncoding(symbol, mem_block_);

  }

}

std::pair<uint64_t, size_t> SymbolTable::Encoding::decodeNumber(const uint8_t* encoding) {

  uint64_t number = 0;

  uint64_t uc = SpilloverMask;

  const uint8_t* start = encoding;

  for (uint32_t shift = 0; (uc & SpilloverMask) != 0; ++encoding, shift += 7) {

    uc = static_cast<uint32_t>(*encoding);

    number |= (uc & Low7Bits) << shift;

  }

  return std::make_pair(number, encoding - start);

}

SymbolVec SymbolTable::Encoding::decodeSymbols(StatName stat_name) {

  SymbolVec symbol_vec;

  symbol_vec.reserve(stat_name.dataSize());

  decodeTokens(

      stat_name, [&symbol_vec](Symbol symbol) { symbol_vec.push_back(symbol); },

      [](absl::string_view) {});

  return symbol_vec;

}

  TokenIter(StatName stat_name) {

    const uint8_t* raw_data = stat_name.dataIncludingSize();

    if (raw_data == nullptr) {

      size_ = 0;

      array_ = nullptr;

    } else {

      std::pair<uint64_t, size_t> size_consumed = decodeNumber(raw_data);

      size_ = size_consumed.first;

      array_ = raw_data + size_consumed.second;

    }

  }

  TokenType next() {

    if (size_ == 0) {

      return TokenType::End;

    }

    if (*array_ == LiteralStringIndicator) {

      ASSERT(size_ > 1);

      ++array_;

      --size_;

      std::pair<uint64_t, size_t> length_consumed = decodeNumber(array_);

      uint64_t length = length_consumed.first;

      array_ += length_consumed.second;

      size_ -= length_consumed.second;

      ASSERT(size_ >= length);

      string_view_ = absl::string_view(reinterpret_cast<const char*>(array_), length);

      size_ -= length;

      array_ += length;

      return TokenType::StringView;

    }

    std::pair<uint64_t, size_t> symbol_consumed = decodeNumber(array_);

    symbol_ = symbol_consumed.first;

    size_ -= symbol_consumed.second;

    array_ += symbol_consumed.second;

    return TokenType::Symbol;

  }

  absl::string_view stringView() const {

    return string_view_;

  }

  Symbol symbol() const {

    return symbol_;

  }

    const std::function<void(absl::string_view)>& string_view_token_fn) {

  TokenIter iter(stat_name);

  TokenIter::TokenType type;

  while ((type = iter.next()) != TokenIter::TokenType::End) {

    if (type == TokenIter::TokenType::StringView) {

      string_view_token_fn(iter.stringView());

    } else {

      ASSERT(type == TokenIter::TokenType::Symbol);

      symbol_token_fn(iter.symbol());

    }

  }

}

bool StatName::startsWith(StatName prefix) const {

  using TokenIter = SymbolTable::Encoding::TokenIter;

  TokenIter prefix_iter(prefix);

  TokenIter this_iter(*this);

  while (true) {

    TokenIter::TokenType prefix_type = prefix_iter.next();

    TokenIter::TokenType this_type = this_iter.next();

    if (prefix_type == TokenIter::TokenType::End) {

      return true; // "a.b.c" starts with "a.b" or "a.b.c"

    }

    if (this_type == TokenIter::TokenType::End) {

      return false; // "a.b" does not start with "a.b.c"

    }

    if (prefix_type != TokenIter::TokenType::Symbol) {

      return false;

    }

    if (this_type != TokenIter::TokenType::Symbol || this_iter.symbol() != prefix_iter.symbol()) {

      return false;

    }

  }

}

std::vector<absl::string_view> SymbolTable::decodeStrings(StatName stat_name) const {

  std::vector<absl::string_view> strings;

  Thread::LockGuard lock(lock_);

  Encoding::decodeTokens(

      stat_name,

      [this, &strings](Symbol symbol)

          ABSL_NO_THREAD_SAFETY_ANALYSIS { strings.push_back(fromSymbol(symbol)); },

      [&strings](absl::string_view str) { strings.push_back(str); });

  return strings;

}

void SymbolTable::Encoding::moveToMemBlock(MemBlockBuilder<uint8_t>& mem_block) {

  appendEncoding(data_bytes_required_, mem_block);

  mem_block.appendBlock(mem_block_);

  mem_block_.reset(); // Logically transfer ownership, enabling empty assert on destruct.

}

                                             MemBlockBuilder<uint8_t>& mem_block) {

  const uint8_t* data = stat_name.dataIncludingSize();

  if (data == nullptr) {

    mem_block.appendOne(0);

  } else {

    mem_block.appendData(absl::MakeSpan(data, stat_name.size()));

  }

}

    : next_symbol_(FirstValidSymbol), monotonic_counter_(FirstValidSymbol) {}

SymbolTable::~SymbolTable() {

  ASSERT(numSymbols() == 0);

}

void SymbolTable::addTokensToEncoding(const absl::string_view name, Encoding& encoding) {

  if (name.empty()) {

    return;

  }

  const std::vector<absl::string_view> tokens = absl::StrSplit(name, '.');

  std::vector<Symbol> symbols;

  symbols.reserve(tokens.size());

  {

    Thread::LockGuard lock(lock_);

    recent_lookups_.lookup(name);

    for (auto& token : tokens) {

      symbols.push_back(toSymbol(token));

    }

  }

  encoding.addSymbols(symbols);

}

uint64_t SymbolTable::numSymbols() const {

  Thread::LockGuard lock(lock_);

  ASSERT(encode_map_.size() == decode_map_.size());

  return encode_map_.size();

}

std::string SymbolTable::toString(const StatName& stat_name) const {

  return absl::StrJoin(decodeStrings(stat_name), ".");

}

void SymbolTable::incRefCount(const StatName& stat_name) {

  const SymbolVec symbols = Encoding::decodeSymbols(stat_name);

  Thread::LockGuard lock(lock_);

  for (Symbol symbol : symbols) {

    auto decode_search = decode_map_.find(symbol);

    ASSERT(decode_search != decode_map_.end(),

           "Please see "

           "https://github.com/envoyproxy/envoy/blob/main/source/docs/stats.md#"

           "debugging-symbol-table-assertions");

    auto encode_search = encode_map_.find(decode_search->second->toStringView());

    ASSERT(encode_search != encode_map_.end(),

           "Please see "

           "https://github.com/envoyproxy/envoy/blob/main/source/docs/stats.md#"

           "debugging-symbol-table-assertions");

    ++encode_search->second.ref_count_;

  }

}

void SymbolTable::free(const StatName& stat_name) {

  const SymbolVec symbols = Encoding::decodeSymbols(stat_name);

  Thread::LockGuard lock(lock_);

  for (Symbol symbol : symbols) {

    auto decode_search = decode_map_.find(symbol);

    ASSERT(decode_search != decode_map_.end());

    auto encode_search = encode_map_.find(decode_search->second->toStringView());

    ASSERT(encode_search != encode_map_.end());

    if (--encode_search->second.ref_count_ == 0) {

      decode_map_.erase(decode_search);

      encode_map_.erase(encode_search);

      pool_.push(symbol);

    }

  }

}

uint64_t SymbolTable::getRecentLookups(const RecentLookupsFn& iter) const {

  uint64_t total = 0;

  absl::flat_hash_map<std::string, uint64_t> name_count_map;

  {

    Thread::LockGuard lock(lock_);

    recent_lookups_.forEach(

        [&name_count_map](absl::string_view str, uint64_t count)

            ABSL_NO_THREAD_SAFETY_ANALYSIS { name_count_map[std::string(str)] += count; });

    total += recent_lookups_.total();

  }

  using LookupCount = std::pair<uint64_t, absl::string_view>;

  std::vector<LookupCount> lookup_data;

  lookup_data.reserve(name_count_map.size());

  for (const auto& iter : name_count_map) {

    lookup_data.emplace_back(LookupCount(iter.second, iter.first));

  }

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

  for (const LookupCount& lookup_count : lookup_data) {

    iter(lookup_count.second, lookup_count.first);

  }

  return total;

}

DynamicSpans SymbolTable::getDynamicSpans(StatName stat_name) const {

  DynamicSpans dynamic_spans;

  uint32_t index = 0;

  auto record_dynamic = [&dynamic_spans, &index](absl::string_view str) {

    DynamicSpan span;

    span.first = index;

    index += std::count(str.begin(), str.end(), '.');

    span.second = index;

    ++index;

    dynamic_spans.push_back(span);

  };

  Encoding::decodeTokens(stat_name, [&index](Symbol) { ++index; }, record_dynamic);

  return dynamic_spans;

}

void SymbolTable::setRecentLookupCapacity(uint64_t capacity) {

  Thread::LockGuard lock(lock_);

  recent_lookups_.setCapacity(capacity);

}

void SymbolTable::clearRecentLookups() {

  Thread::LockGuard lock(lock_);

  recent_lookups_.clear();

}

uint64_t SymbolTable::recentLookupCapacity() const {

  Thread::LockGuard lock(lock_);

  return recent_lookups_.capacity();

}

StatNameSetPtr SymbolTable::makeSet(absl::string_view name) {

  StatNameSetPtr stat_name_set(new StatNameSet(*this, name));

  return stat_name_set;

}

Symbol SymbolTable::toSymbol(absl::string_view sv) {

  Symbol result;

  auto encode_find = encode_map_.find(sv);

  if (encode_find == encode_map_.end()) {

    InlineStringPtr str = InlineString::create(sv);

    auto encode_insert = encode_map_.insert({str->toStringView(), SharedSymbol(next_symbol_)});

    ASSERT(encode_insert.second);

    auto decode_insert = decode_map_.insert({next_symbol_, std::move(str)});

    ASSERT(decode_insert.second);

    result = next_symbol_;

    newSymbol();

  } else {

    result = encode_find->second.symbol_;

    ++(encode_find->second.ref_count_);

  }

  return result;

}

    ABSL_EXCLUSIVE_LOCKS_REQUIRED(lock_) {

  auto search = decode_map_.find(symbol);

  RELEASE_ASSERT(search != decode_map_.end(), "no such symbol");

  return search->second->toStringView();

}

void SymbolTable::newSymbol() ABSL_EXCLUSIVE_LOCKS_REQUIRED(lock_) {

  if (pool_.empty()) {

    next_symbol_ = ++monotonic_counter_;

  } else {

    next_symbol_ = pool_.top();

    pool_.pop();

  }

  ASSERT(monotonic_counter_ != 0);

}

bool SymbolTable::lessThan(const StatName& a, const StatName& b) const {

  Thread::LockGuard lock(lock_);

  return lessThanLockHeld(a, b);

}

    ABSL_EXCLUSIVE_LOCKS_REQUIRED(lock_) {

  Encoding::TokenIter a_iter(a), b_iter(b);

  while (true) {

    Encoding::TokenIter::TokenType a_type = a_iter.next();

    Encoding::TokenIter::TokenType b_type = b_iter.next();

    if (b_type == Encoding::TokenIter::TokenType::End) {

      return false; // "x.y.z" > "x.y", "x.y" == "x.y"

    }

    if (a_type == Encoding::TokenIter::TokenType::End) {

      return true; // "x.y" < "x.y.z"

    }

    if (a_type == b_type && a_type == Encoding::TokenIter::TokenType::Symbol &&

        a_iter.symbol() == b_iter.symbol()) {

      continue; // matching symbols don't need to be decoded to strings

    }

    absl::string_view a_token = a_type == Encoding::TokenIter::TokenType::Symbol

                                    ? fromSymbol(a_iter.symbol())

                                    : a_iter.stringView();

    absl::string_view b_token = b_type == Encoding::TokenIter::TokenType::Symbol

                                    ? fromSymbol(b_iter.symbol())

                                    : b_iter.stringView();

    if (a_token != b_token) {

      return a_token < b_token;

    }

  }

}

SymbolTable::StoragePtr SymbolTable::encode(absl::string_view name) {

  name = StringUtil::removeTrailingCharacters(name, '.');

  Encoding encoding;

  addTokensToEncoding(name, encoding);

  MemBlockBuilder<uint8_t> mem_block(Encoding::totalSizeBytes(encoding.bytesRequired()));

  encoding.moveToMemBlock(mem_block);

  return mem_block.release();

}

    : StatNameStorageBase(table.encode(name)) {}

StatNameStorage::StatNameStorage(StatName src, SymbolTable& table) {

  const size_t size = src.size();

  MemBlockBuilder<uint8_t> storage(size); // Note: MemBlockBuilder takes uint64_t.

  src.copyToMemBlock(storage);

  setBytes(storage.release());

  table.incRefCount(statName());

}

SymbolTable::StoragePtr SymbolTable::makeDynamicStorage(absl::string_view name) {

  name = StringUtil::removeTrailingCharacters(name, '.');

  const size_t payload_bytes = Encoding::totalSizeBytes(name.size()) + 1;

  const size_t total_bytes = Encoding::totalSizeBytes(payload_bytes);

  MemBlockBuilder<uint8_t> mem_block(total_bytes);

  Encoding::appendEncoding(payload_bytes, mem_block);

  mem_block.appendOne(LiteralStringIndicator);

  Encoding::appendEncoding(name.size(), mem_block);

  mem_block.appendData(absl::MakeSpan(reinterpret_cast<const uint8_t*>(name.data()), name.size()));

  ASSERT(mem_block.capacityRemaining() == 0);

  return mem_block.release();

}

StatNameStorage::~StatNameStorage() {

  ASSERT(bytes() == nullptr);

}

void StatNameStorage::free(SymbolTable& table) {

  table.free(statName());

  clear();

}

void StatNamePool::clear() {

  for (StatNameStorage& storage : storage_vector_) {

    storage.free(symbol_table_);

  }

  storage_vector_.clear();

}

const uint8_t* StatNamePool::addReturningStorage(absl::string_view str) {

  storage_vector_.emplace_back(str, symbol_table_);

  return storage_vector_.back().bytes();

}

StatName StatNamePool::add(StatName name) {

  storage_vector_.emplace_back(name, symbol_table_);

  return storage_vector_.back().statName();

}

StatName StatNamePool::add(absl::string_view str) { return StatName(addReturningStorage(str)); }

StatName StatNameDynamicPool::add(absl::string_view str) {

  storage_vector_.push_back(Stats::StatNameDynamicStorage(str, symbol_table_));

  return StatName(storage_vector_.back().bytes());

}

StatNameStorageSet::~StatNameStorageSet() {

  ASSERT(hash_set_.empty());

}

void StatNameStorageSet::free(SymbolTable& symbol_table) {

  while (!hash_set_.empty()) {

    auto storage = hash_set_.extract(hash_set_.begin());

    storage.value().free(symbol_table);

  }

}

SymbolTable::StoragePtr SymbolTable::join(const StatNameVec& stat_names) const {

  size_t num_bytes = 0;

  for (StatName stat_name : stat_names) {

    if (!stat_name.empty()) {

      num_bytes += stat_name.dataSize();

    }

  }

  MemBlockBuilder<uint8_t> mem_block(Encoding::totalSizeBytes(num_bytes));

  Encoding::appendEncoding(num_bytes, mem_block);

  for (StatName stat_name : stat_names) {

    stat_name.appendDataToMemBlock(mem_block);

  }

  ASSERT(mem_block.capacityRemaining() == 0);

  return mem_block.release();

}

void SymbolTable::populateList(const StatName* names, uint32_t num_names, StatNameList& list) {

  RELEASE_ASSERT(num_names < 256, "Maximum number elements in a StatNameList exceeded");

  size_t total_size_bytes = 1; /* one byte for holding the number of names */

  for (uint32_t i = 0; i < num_names; ++i) {

    total_size_bytes += names[i].size();

  }

  MemBlockBuilder<uint8_t> mem_block(total_size_bytes);

  mem_block.appendOne(num_names);

  for (uint32_t i = 0; i < num_names; ++i) {

    const StatName stat_name = names[i];

    Encoding::appendToMemBlock(stat_name, mem_block);

    incRefCount(stat_name);

  }

  ASSERT(mem_block.capacityRemaining() == 0);

  list.moveStorageIntoList(mem_block.release());

}

StatNameList::~StatNameList() { ASSERT(!populated()); }

void StatNameList::iterate(const std::function<bool(StatName)>& f) const {

  const uint8_t* p = &storage_[0];

  const uint32_t num_elements = *p++;

  for (uint32_t i = 0; i < num_elements; ++i) {

    const StatName stat_name(p);

    p += stat_name.size();

    if (!f(stat_name)) {

      break;

    }

  }

}

void StatNameList::clear(SymbolTable& symbol_table) {

  iterate([&symbol_table](StatName stat_name) -> bool {

    symbol_table.free(stat_name);

    return true;

  });

  storage_.reset();

}

    : name_(std::string(name)), pool_(symbol_table) {

  builtin_stat_names_[""] = StatName();

}

void StatNameSet::rememberBuiltin(absl::string_view str) {

  StatName stat_name;

  {

    absl::MutexLock lock(mutex_);

    stat_name = pool_.add(str);

  }

  builtin_stat_names_[str] = stat_name;

}

StatName StatNameSet::getBuiltin(absl::string_view token, StatName fallback) const {

  const auto iter = builtin_stat_names_.find(token);

  if (iter != builtin_stat_names_.end()) {

    return iter->second;

  }

  return fallback;

}