absl::string_view delimiterByHeader(const LowerCaseString& key) {

  if (key == Http::Headers::get().Cookie) {

    return DelimiterForInlineCookies;

  }

  return DelimiterForInlineHeaders;

}

    : UnionStringBase(absl::string_view(ref_value.get().c_str(), ref_value.get().size())) {

  ASSERT(valid());

}

HeaderString::HeaderString(UnionString&& move_value) noexcept {

  buffer_ = std::move(move_value.storage());

  move_value.clear();

  ASSERT(valid());

}

template <> bool HeaderMapImpl::HeaderList::isPseudoHeader(const LowerCaseString& key) {

  return key.get().c_str()[0] == ':';

}

bool HeaderMapImpl::HeaderList::maybeMakeMap() {

  if (lazy_map_.empty()) {

    if (headers_.size() < kMinHeadersForLazyMap) {

      return false;

    }

    for (auto node = headers_.begin(); node != headers_.end(); ++node) {

      HeaderNodeVector& v = lazy_map_[node->key().getStringView()];

      v.push_back(node);

    }

  }

  return true;

}

size_t HeaderMapImpl::HeaderList::remove(absl::string_view key) {

  size_t removed_bytes = 0;

  if (maybeMakeMap()) {

    auto iter = lazy_map_.find(key);

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

      HeaderNodeVector header_nodes = std::move(iter->second);

      lazy_map_.erase(iter);

      for (const HeaderNode& node : header_nodes) {

        ASSERT(node->key() == key);

        removed_bytes += node->key().size() + node->value().size();

        erase(node, false /* remove_from_map */);

      }

    }

  } else {

    for (auto i = headers_.begin(); i != headers_.end();) {

      if (i->key() == key) {

        removed_bytes += i->key().size() + i->value().size();

        i = erase(i, false /* remove_from_map */);

      } else {

        ++i;

      }

    }

  }

  return removed_bytes;

}

HeaderMapImpl::HeaderEntryImpl::HeaderEntryImpl(const LowerCaseString& key) : key_(key) {}

    : key_(key), value_(std::move(value)) {}

    : key_(std::move(key)), value_(std::move(value)) {}

template <> HeaderMapImpl::StaticLookupTable<RequestHeaderMap>::StaticLookupTable() {

#define REGISTER_DEFAULT_REQUEST_HEADER(name)                                                      \

  CustomInlineHeaderRegistry::registerInlineHeader<RequestHeaderMap::header_map_type>(             \

      Headers::get().name);

  INLINE_REQ_HEADERS(REGISTER_DEFAULT_REQUEST_HEADER)

  INLINE_REQ_RESP_HEADERS(REGISTER_DEFAULT_REQUEST_HEADER)

  auto input = finalizedTable();

  const auto handle =

      CustomInlineHeaderRegistry::getInlineHeader<RequestHeaderMap::header_map_type>(

          Headers::get().Host);

  input.emplace_back(

      Headers::get().HostLegacy.get(), [handle](HeaderMapImpl& h) -> StaticLookupResponse {

        return {&h.inlineHeaders()[handle.value().it_->second], &handle.value().it_->first};

      });

  compile(std::move(input));

}

template <> HeaderMapImpl::StaticLookupTable<RequestTrailerMap>::StaticLookupTable() {

  compile(finalizedTable());

}

template <> HeaderMapImpl::StaticLookupTable<ResponseHeaderMap>::StaticLookupTable() {

#define REGISTER_RESPONSE_HEADER(name)                                                             \

  CustomInlineHeaderRegistry::registerInlineHeader<ResponseHeaderMap::header_map_type>(            \

      Headers::get().name);

  INLINE_RESP_HEADERS(REGISTER_RESPONSE_HEADER)

  INLINE_REQ_RESP_HEADERS(REGISTER_RESPONSE_HEADER)

  INLINE_RESP_HEADERS_TRAILERS(REGISTER_RESPONSE_HEADER)

  compile(finalizedTable());

}

template <> HeaderMapImpl::StaticLookupTable<ResponseTrailerMap>::StaticLookupTable() {

#define REGISTER_RESPONSE_TRAILER(name)                                                            \

  CustomInlineHeaderRegistry::registerInlineHeader<ResponseTrailerMap::header_map_type>(           \

      Headers::get().name);

  INLINE_RESP_HEADERS_TRAILERS(REGISTER_RESPONSE_TRAILER)

  compile(finalizedTable());

}

                                       absl::string_view delimiter) {

  if (data.empty()) {

    return 0;

  }

  uint64_t byte_size = 0;

  if (!header.empty()) {

    header.append(delimiter.data(), delimiter.size());

    byte_size += delimiter.size();

  }

  header.append(data.data(), data.size());

  return data.size() + byte_size;

}

void HeaderMapImpl::updateSize(uint64_t from_size, uint64_t to_size) {

  ASSERT(cached_byte_size_ >= from_size);

  cached_byte_size_ -= from_size;

  cached_byte_size_ += to_size;

}

void HeaderMapImpl::addSize(uint64_t size) { cached_byte_size_ += size; }

void HeaderMapImpl::subtractSize(uint64_t size) {

  ASSERT(cached_byte_size_ >= size);

  cached_byte_size_ -= size;

}

void HeaderMapImpl::copyFrom(HeaderMap& lhs, const HeaderMap& header_map) {

  header_map.iterate([&lhs](const HeaderEntry& header) -> HeaderMap::Iterate {

    HeaderString key_string;

    key_string.setCopy(header.key().getStringView());

    HeaderString value_string;

    value_string.setCopy(header.value().getStringView());

    lhs.addViaMove(std::move(key_string), std::move(value_string));

    return HeaderMap::Iterate::Continue;

  });

}

collectAllHeaders(std::vector<std::pair<absl::string_view, absl::string_view>>* dest) {

  return [dest](const HeaderEntry& header) -> HeaderMap::Iterate {

    dest->push_back(std::make_pair(header.key().getStringView(), header.value().getStringView()));

    return HeaderMap::Iterate::Continue;

  };

};

bool HeaderMapImpl::operator==(const HeaderMap& rhs) const {

  if (size() != rhs.size()) {

    return false;

  }

  std::vector<std::pair<absl::string_view, absl::string_view>> rhs_headers;

  rhs_headers.reserve(rhs.size());

  rhs.iterate(collectAllHeaders(&rhs_headers));

  auto i = headers_.begin();

  auto j = rhs_headers.begin();

  for (; i != headers_.end(); ++i, ++j) {

    if (i->key() != j->first || i->value() != j->second) {

      return false;

    }

  }

  return true;

}

bool HeaderMapImpl::operator!=(const HeaderMap& rhs) const { return !operator==(rhs); }

void HeaderMapImpl::insertByKey(HeaderString&& key, HeaderString&& value) {

  auto lookup = staticLookup(key.getStringView());

  if (lookup.has_value()) {

    key.clear();

    if (*lookup.value().entry_ == nullptr) {

      maybeCreateInline(lookup.value().entry_, *lookup.value().key_, std::move(value));

    } else {

      const auto delimiter = delimiterByHeader(*lookup.value().key_);

      const uint64_t added_size =

          appendToHeader((*lookup.value().entry_)->value(), value.getStringView(), delimiter);

      addSize(added_size);

      value.clear();

    }

  } else {

    addSize(key.size() + value.size());

    HeaderNode i = headers_.insert(std::move(key), std::move(value));

    i->entry_ = i;

  }

}

void HeaderMapImpl::addViaMove(HeaderString&& key, HeaderString&& value) {

  insertByKey(std::move(key), std::move(value));

}

void HeaderMapImpl::addReference(const LowerCaseString& key, absl::string_view value) {

  HeaderString ref_key(key);

  HeaderString ref_value(value);

  insertByKey(std::move(ref_key), std::move(ref_value));

}

void HeaderMapImpl::addReferenceKey(const LowerCaseString& key, uint64_t value) {

  HeaderString ref_key(key);

  HeaderString new_value;

  new_value.setInteger(value);

  insertByKey(std::move(ref_key), std::move(new_value));

  ASSERT(new_value.empty()); // NOLINT(bugprone-use-after-move)

}

void HeaderMapImpl::addReferenceKey(const LowerCaseString& key, absl::string_view value) {

  HeaderString ref_key(key);

  HeaderString new_value;

  new_value.setCopy(value);

  insertByKey(std::move(ref_key), std::move(new_value));

  ASSERT(new_value.empty()); // NOLINT(bugprone-use-after-move)

}

void HeaderMapImpl::addCopy(const LowerCaseString& key, uint64_t value) {

  HeaderString new_key;

  new_key.setCopy(key.get());

  HeaderString new_value;

  new_value.setInteger(value);

  insertByKey(std::move(new_key), std::move(new_value));

  ASSERT(new_key.empty());   // NOLINT(bugprone-use-after-move)

  ASSERT(new_value.empty()); // NOLINT(bugprone-use-after-move)

}

void HeaderMapImpl::addCopy(const LowerCaseString& key, absl::string_view value) {

  HeaderString new_key;

  new_key.setCopy(key.get());

  HeaderString new_value;

  new_value.setCopy(value);

  insertByKey(std::move(new_key), std::move(new_value));

  ASSERT(new_key.empty());   // NOLINT(bugprone-use-after-move)

  ASSERT(new_value.empty()); // NOLINT(bugprone-use-after-move)

}

void HeaderMapImpl::appendCopy(const LowerCaseString& key, absl::string_view value) {

  auto entry = getExisting(key);

  if (!entry.empty()) {

    const auto delimiter = delimiterByHeader(key);

    const uint64_t added_size = appendToHeader(entry[0]->value(), value, delimiter);

    addSize(added_size);

  } else {

    addCopy(key, value);

  }

}

void HeaderMapImpl::setReference(const LowerCaseString& key, absl::string_view value) {

  remove(key);

  addReference(key, value);

}

void HeaderMapImpl::setReferenceKey(const LowerCaseString& key, absl::string_view value) {

  remove(key);

  addReferenceKey(key, value);

}

void HeaderMapImpl::setCopy(const LowerCaseString& key, absl::string_view value) {

  remove(key);

  addCopy(key, value);

}

uint64_t HeaderMapImpl::byteSize() const { return cached_byte_size_; }

void HeaderMapImpl::verifyByteSizeInternalForTest() const {

  uint64_t byte_size = 0;

  for (const HeaderEntryImpl& header : headers_) {

    byte_size += header.key().size();

    byte_size += header.value().size();

  }

  ASSERT(cached_byte_size_ == byte_size);

}

HeaderMap::GetResult HeaderMapImpl::get(const LowerCaseString& key) const {

  return HeaderMap::GetResult(const_cast<HeaderMapImpl*>(this)->getExisting(key));

}

HeaderMap::NonConstGetResult HeaderMapImpl::getExisting(absl::string_view key) {

  HeaderMap::NonConstGetResult ret;

  auto lookup = staticLookup(key);

  if (lookup.has_value()) {

    if (*lookup.value().entry_ != nullptr) {

      ret.push_back(*lookup.value().entry_);

    }

    return ret;

  }

  if (headers_.maybeMakeMap()) {

    HeaderList::HeaderLazyMap::iterator iter = headers_.mapFind(key);

    if (iter != headers_.mapEnd()) {

      const HeaderList::HeaderNodeVector& v = iter->second;

      ASSERT(!v.empty()); // It's impossible to have a map entry with an empty vector as its value.

      for (const auto& values_it : v) {

        ret.push_back(&(*values_it));

      }

    }

    return ret;

  }

  for (HeaderEntryImpl& header : headers_) {

    if (header.key() == key) {

      ret.push_back(&header);

    }

  }

  return ret;

}

void HeaderMapImpl::iterate(HeaderMap::ConstIterateCb cb) const {

  for (const HeaderEntryImpl& header : headers_) {

    if (cb(header) == HeaderMap::Iterate::Break) {

      break;

    }

  }

}

void HeaderMapImpl::iterateReverse(HeaderMap::ConstIterateCb cb) const {

  for (auto it = headers_.rbegin(); it != headers_.rend(); it++) {

    if (cb(*it) == HeaderMap::Iterate::Break) {

      break;

    }

  }

}

void HeaderMapImpl::clear() {

  clearInline();

  headers_.clear();

  cached_byte_size_ = 0;

}

size_t HeaderMapImpl::removeIf(const HeaderMap::HeaderMatchPredicate& predicate) {

  const size_t old_size = headers_.size();

  headers_.removeIf([&predicate, this](const HeaderEntryImpl& entry) {

    const bool to_remove = predicate(entry);

    if (to_remove) {

      auto lookup = staticLookup(entry.key().getStringView());

      if (lookup.has_value()) {

        if (lookup.value().entry_) {

          const uint32_t key_value_size =

              (*lookup.value().entry_)->key().size() + (*lookup.value().entry_)->value().size();

          subtractSize(key_value_size);

          *lookup.value().entry_ = nullptr;

        }

      } else {

        subtractSize(entry.key().size() + entry.value().size());

      }

    }

    return to_remove;

  });

  return old_size - headers_.size();

}

size_t HeaderMapImpl::remove(const LowerCaseString& key) { return removeExisting(key); }

size_t HeaderMapImpl::removePrefix(const LowerCaseString& prefix) {

  return HeaderMapImpl::removeIf([&prefix](const HeaderEntry& entry) -> bool {

    return absl::StartsWith(entry.key().getStringView(), prefix.get());

  });

}

void HeaderMapImpl::dumpState(std::ostream& os, int indent_level) const {

  iterate([&os,

           spaces = spacesForLevel(indent_level)](const HeaderEntry& header) -> HeaderMap::Iterate {

    os << spaces << "'" << header.key().getStringView() << "', '" << header.value().getStringView()

       << "'\n";

    return HeaderMap::Iterate::Continue;

  });

}

                                                                 const LowerCaseString& key) {

  if (*entry) {

    return **entry;

  }

  addSize(key.get().size());

  HeaderNode i = headers_.insert(key);

  i->entry_ = i;

  *entry = &(*i);

  return **entry;

}

                                                                 HeaderString&& value) {

  if (*entry) {

  addSize(key.get().size() + value.size());

  HeaderNode i = headers_.insert(key, std::move(value));

  i->entry_ = i;

  *entry = &(*i);

  return **entry;

}

size_t HeaderMapImpl::removeExisting(absl::string_view key) {

  const size_t old_size = headers_.size();

  auto lookup = staticLookup(key);

  if (lookup.has_value()) {

    removeInline(lookup.value().entry_);

  } else {

    subtractSize(headers_.remove(key));

  }

  return old_size - headers_.size();

}

size_t HeaderMapImpl::removeInline(HeaderEntryImpl** ptr_to_entry) {

  if (!*ptr_to_entry) {

    return 0;

  }

  HeaderEntryImpl* entry = *ptr_to_entry;

  const uint64_t size_to_subtract = entry->entry_->key().size() + entry->entry_->value().size();

  subtractSize(size_to_subtract);

  *ptr_to_entry = nullptr;

  headers_.erase(entry->entry_, true);

  return 1;

}

ProtobufTypes::MessagePtr TunnelResponseHeadersOrTrailersImpl::serializeAsProto() const {

  auto proto_out = std::make_unique<envoy::config::core::v3::HeaderMap>();

  value().iterate([&proto_out](const HeaderEntry& e) -> HeaderMap::Iterate {

    auto* new_header = proto_out->add_headers();

    new_header->set_key(std::string(e.key().getStringView()));

    new_header->set_value(std::string(e.value().getStringView()));

    return HeaderMap::Iterate::Continue;

  });

  return proto_out;

}

HeaderMapImplUtility::HeaderMapImplInfo makeHeaderMapImplInfo(absl::string_view name) {

  auto header_map = T::create();

  HeaderMapImplUtility::HeaderMapImplInfo info;

  info.name_ = std::string(name);

  info.size_ = T::inlineHeadersSize() + sizeof(T);

  for (const auto& header : CustomInlineHeaderRegistry::headers<T::header_map_type>()) {

    info.registered_headers_.push_back(header.first.get());

  }

  return info;

}

HeaderMapImplUtility::getAllHeaderMapImplInfo() {

  std::vector<HeaderMapImplUtility::HeaderMapImplInfo> ret;

  ret.push_back(makeHeaderMapImplInfo<RequestHeaderMapImpl>("request header map"));

  ret.push_back(makeHeaderMapImplInfo<RequestTrailerMapImpl>("request trailer map"));

  ret.push_back(makeHeaderMapImplInfo<ResponseHeaderMapImpl>("response header map"));

  ret.push_back(makeHeaderMapImplInfo<ResponseTrailerMapImpl>("response trailer map"));

  return ret;

}