Remove HpackEntry::InsertionIndex().
Map to index instead of HpackEntry* in static_index_, static_name_index_,
dynamic_index_, dynamic_name_index_. Elsewhere infer index by simple
calculations.
PiperOrigin-RevId: 364610531
Change-Id: Id6357fff6b7ac52026523c07afbbb352e60cf373
diff --git a/quic/core/qpack/qpack_header_table.cc b/quic/core/qpack/qpack_header_table.cc
index 9c12524..bd6c6d0 100644
--- a/quic/core/qpack/qpack_header_table.cc
+++ b/quic/core/qpack/qpack_header_table.cc
@@ -60,7 +60,7 @@
// Look for exact match in static table.
auto index_it = static_index_.find(query);
if (index_it != static_index_.end()) {
- *index = index_it->second->InsertionIndex();
+ *index = index_it->second;
*is_static = true;
return MatchType::kNameAndValue;
}
@@ -68,7 +68,7 @@
// Look for exact match in dynamic table.
index_it = dynamic_index_.find(query);
if (index_it != dynamic_index_.end()) {
- *index = index_it->second->InsertionIndex();
+ *index = index_it->second;
*is_static = false;
return MatchType::kNameAndValue;
}
@@ -76,7 +76,7 @@
// Look for name match in static table.
auto name_index_it = static_name_index_.find(name);
if (name_index_it != static_name_index_.end()) {
- *index = name_index_it->second->InsertionIndex();
+ *index = name_index_it->second;
*is_static = true;
return MatchType::kName;
}
@@ -84,7 +84,7 @@
// Look for name match in dynamic table.
name_index_it = dynamic_name_index_.find(name);
if (name_index_it != dynamic_name_index_.end()) {
- *index = name_index_it->second->InsertionIndex();
+ *index = name_index_it->second;
*is_static = false;
return MatchType::kName;
}
@@ -103,7 +103,7 @@
QUICHE_DCHECK(EntryFitsDynamicTableCapacity(name, value));
const uint64_t index = dropped_entry_count_ + dynamic_entries_.size();
- dynamic_entries_.push_back({name, value, index});
+ dynamic_entries_.push_back({name, value});
QpackEntry* const new_entry = &dynamic_entries_.back();
// Evict entries after inserting the new entry instead of before
@@ -112,28 +112,26 @@
EvictDownToCurrentCapacity();
auto index_result = dynamic_index_.insert(std::make_pair(
- QpackLookupEntry{new_entry->name(), new_entry->value()}, new_entry));
+ QpackLookupEntry{new_entry->name(), new_entry->value()}, index));
if (!index_result.second) {
// An entry with the same name and value already exists. It needs to be
// replaced, because |dynamic_index_| tracks the most recent entry for a
// given name and value.
- QUICHE_DCHECK_GT(new_entry->InsertionIndex(),
- index_result.first->second->InsertionIndex());
+ QUICHE_DCHECK_GT(index, index_result.first->second);
dynamic_index_.erase(index_result.first);
auto result = dynamic_index_.insert(std::make_pair(
- QpackLookupEntry{new_entry->name(), new_entry->value()}, new_entry));
+ QpackLookupEntry{new_entry->name(), new_entry->value()}, index));
QUICHE_CHECK(result.second);
}
- auto name_result = dynamic_name_index_.insert({new_entry->name(), new_entry});
+ auto name_result = dynamic_name_index_.insert({new_entry->name(), index});
if (!name_result.second) {
// An entry with the same name already exists. It needs to be replaced,
// because |dynamic_name_index_| tracks the most recent entry for a given
// name.
- QUICHE_DCHECK_GT(new_entry->InsertionIndex(),
- name_result.first->second->InsertionIndex());
+ QUICHE_DCHECK_GT(index, name_result.first->second);
dynamic_name_index_.erase(name_result.first);
- auto result = dynamic_name_index_.insert({new_entry->name(), new_entry});
+ auto result = dynamic_name_index_.insert({new_entry->name(), index});
QUICHE_CHECK(result.second);
}
@@ -165,9 +163,7 @@
uint64_t entry_index = dropped_entry_count_;
for (const auto& entry : dynamic_entries_) {
- // TODO(b/182789212): Remove InsertionIndex(), use entry_index instead.
- QUICHE_CHECK_EQ(entry_index, entry.InsertionIndex());
- if (entry.InsertionIndex() >= index) {
+ if (entry_index >= index) {
break;
}
++entry_index;
@@ -239,7 +235,6 @@
uint64_t entry_index = dropped_entry_count_;
while (space_above_draining_index < required_space) {
space_above_draining_index += it->Size();
- QUICHE_CHECK_EQ(entry_index, it->InsertionIndex());
++it;
++entry_index;
if (it == dynamic_entries_.end()) {
@@ -247,8 +242,7 @@
}
}
- // TODO(b/182789212): Remove InsertionIndex(), use entry_index instead.
- return it->InsertionIndex();
+ return entry_index;
}
void QpackHeaderTable::EvictDownToCurrentCapacity() {
@@ -261,21 +255,19 @@
QUICHE_DCHECK_GE(dynamic_table_size_, entry_size);
dynamic_table_size_ -= entry_size;
- // TODO(b/182789212): Remove InsertionIndex(), use dropped_entry_count_
- // instead.
- QUICHE_CHECK_EQ(dropped_entry_count_, entry->InsertionIndex());
+ const uint64_t index = dropped_entry_count_;
auto index_it = dynamic_index_.find({entry->name(), entry->value()});
// Remove |dynamic_index_| entry only if it points to the same
// QpackEntry in |dynamic_entries_|.
- if (index_it != dynamic_index_.end() && index_it->second == entry) {
+ if (index_it != dynamic_index_.end() && index_it->second == index) {
dynamic_index_.erase(index_it);
}
auto name_it = dynamic_name_index_.find(entry->name());
// Remove |dynamic_name_index_| entry only if it points to the same
// QpackEntry in |dynamic_entries_|.
- if (name_it != dynamic_name_index_.end() && name_it->second == entry) {
+ if (name_it != dynamic_name_index_.end() && name_it->second == index) {
dynamic_name_index_.erase(name_it);
}
diff --git a/spdy/core/hpack/hpack_entry.cc b/spdy/core/hpack/hpack_entry.cc
index bc17bf2..2e440f4 100644
--- a/spdy/core/hpack/hpack_entry.cc
+++ b/spdy/core/hpack/hpack_entry.cc
@@ -10,14 +10,8 @@
namespace spdy {
-HpackEntry::HpackEntry(absl::string_view name,
- absl::string_view value,
- size_t insertion_index)
- : name_(std::string(name)),
- value_(std::string(value)),
- insertion_index_(insertion_index) {}
-
-HpackEntry::HpackEntry() : insertion_index_(0) {}
+HpackEntry::HpackEntry(absl::string_view name, absl::string_view value)
+ : name_(std::string(name)), value_(std::string(value)) {}
// static
size_t HpackEntry::Size(absl::string_view name, absl::string_view value) {
@@ -28,8 +22,7 @@
}
std::string HpackEntry::GetDebugString() const {
- return absl::StrCat("{ name: \"", name_, "\", value: \"", value_,
- "\", index: ", insertion_index_, " }");
+ return absl::StrCat("{ name: \"", name_, "\", value: \"", value_, "\" }");
}
size_t HpackEntry::EstimateMemoryUsage() const {
diff --git a/spdy/core/hpack/hpack_entry.h b/spdy/core/hpack/hpack_entry.h
index 1db5297..281d225 100644
--- a/spdy/core/hpack/hpack_entry.h
+++ b/spdy/core/hpack/hpack_entry.h
@@ -43,25 +43,17 @@
class QUICHE_EXPORT_PRIVATE HpackEntry {
public:
// Copies |name| and |value| in the constructor.
- // TODO(b/182789212): Remove |insertion_index|.
- // |insertion_index| starts from 0, separately for static entries and dynamic
- // entries.
- HpackEntry(absl::string_view name,
- absl::string_view value,
- size_t insertion_index);
+ HpackEntry(absl::string_view name, absl::string_view value);
// Creates an entry with empty name and value. Only defined so that
// entries can be stored in STL containers.
- HpackEntry();
+ HpackEntry() = default;
~HpackEntry() = default;
absl::string_view name() const { return name_; }
absl::string_view value() const { return value_; }
- // Used to compute the entry's index in the header table.
- size_t InsertionIndex() const { return insertion_index_; }
-
// Returns the size of an entry as defined in 5.1.
static size_t Size(absl::string_view name, absl::string_view value);
size_t Size() const;
@@ -74,11 +66,6 @@
private:
std::string name_;
std::string value_;
-
- // TODO(b/182789212): Remove |insertion_index_|.
- // |insertion_index_| starts from 0, separately for static entries and dynamic
- // entries.
- size_t insertion_index_;
};
} // namespace spdy
diff --git a/spdy/core/hpack/hpack_entry_test.cc b/spdy/core/hpack/hpack_entry_test.cc
index cfb3c01..1a43c98 100644
--- a/spdy/core/hpack/hpack_entry_test.cc
+++ b/spdy/core/hpack/hpack_entry_test.cc
@@ -39,7 +39,7 @@
}
TEST(HpackEntryTest, BasicEntry) {
- HpackEntry entry("header-name", "header value", 0);
+ HpackEntry entry("header-name", "header value");
EXPECT_EQ("header-name", entry.name());
EXPECT_EQ("header value", entry.value());
diff --git a/spdy/core/hpack/hpack_header_table.cc b/spdy/core/hpack/hpack_header_table.cc
index 0f0fafc..d59257e 100644
--- a/spdy/core/hpack/hpack_header_table.cc
+++ b/spdy/core/hpack/hpack_header_table.cc
@@ -44,14 +44,13 @@
{
auto it = static_name_index_.find(name);
if (it != static_name_index_.end()) {
- return 1 + it->second->InsertionIndex();
+ return 1 + it->second;
}
}
{
NameToEntryMap::const_iterator it = dynamic_name_index_.find(name);
if (it != dynamic_name_index_.end()) {
- return dynamic_table_insertions_ - it->second->InsertionIndex() +
- kStaticTableSize;
+ return dynamic_table_insertions_ - it->second + kStaticTableSize;
}
}
return kHpackEntryNotFound;
@@ -63,14 +62,13 @@
{
auto it = static_index_.find(query);
if (it != static_index_.end()) {
- return 1 + it->second->InsertionIndex();
+ return 1 + it->second;
}
}
{
auto it = dynamic_index_.find(query);
if (it != dynamic_index_.end()) {
- return dynamic_table_insertions_ - it->second->InsertionIndex() +
- kStaticTableSize;
+ return dynamic_table_insertions_ - it->second + kStaticTableSize;
}
}
return kHpackEntryNotFound;
@@ -124,10 +122,9 @@
void HpackHeaderTable::Evict(size_t count) {
for (size_t i = 0; i != count; ++i) {
QUICHE_CHECK(!dynamic_entries_.empty());
+
HpackEntry* entry = &dynamic_entries_.back();
- // TODO(b/182789212): Remove InsertionIndex().
- QUICHE_CHECK_EQ(dynamic_table_insertions_ - dynamic_entries_.size(),
- entry->InsertionIndex());
+ const size_t index = dynamic_table_insertions_ - dynamic_entries_.size();
size_ -= entry->Size();
auto it = dynamic_index_.find({entry->name(), entry->value()});
@@ -135,7 +132,7 @@
// Only remove an entry from the index if its insertion index matches;
// otherwise, the index refers to another entry with the same name and
// value.
- if (it->second->InsertionIndex() == entry->InsertionIndex()) {
+ if (it->second == index) {
dynamic_index_.erase(it);
}
auto name_it = dynamic_name_index_.find(entry->name());
@@ -143,7 +140,7 @@
// Only remove an entry from the literal index if its insertion index
/// matches; otherwise, the index refers to another entry with the same
// name.
- if (name_it->second->InsertionIndex() == entry->InsertionIndex()) {
+ if (name_it->second == index) {
dynamic_name_index_.erase(name_it);
}
dynamic_entries_.pop_back();
@@ -164,37 +161,37 @@
QUICHE_DCHECK_EQ(0u, size_);
return nullptr;
}
- dynamic_entries_.emplace_front(name, value, dynamic_table_insertions_);
+
+ const size_t index = dynamic_table_insertions_;
+ dynamic_entries_.emplace_front(name, value);
HpackEntry* new_entry = &dynamic_entries_.front();
auto index_result = dynamic_index_.insert(std::make_pair(
- HpackLookupEntry{new_entry->name(), new_entry->value()}, new_entry));
+ HpackLookupEntry{new_entry->name(), new_entry->value()}, index));
if (!index_result.second) {
// An entry with the same name and value already exists in the dynamic
// index. We should replace it with the newly added entry.
- SPDY_DVLOG(1) << "Found existing entry: "
- << index_result.first->second->GetDebugString()
- << " replacing with: " << new_entry->GetDebugString();
- QUICHE_DCHECK_GT(new_entry->InsertionIndex(),
- index_result.first->second->InsertionIndex());
+ SPDY_DVLOG(1) << "Found existing entry at: " << index_result.first->second
+ << " replacing with: " << new_entry->GetDebugString()
+ << " at: " << index;
+ QUICHE_DCHECK_GT(index, index_result.first->second);
dynamic_index_.erase(index_result.first);
auto insert_result = dynamic_index_.insert(std::make_pair(
- HpackLookupEntry{new_entry->name(), new_entry->value()}, new_entry));
+ HpackLookupEntry{new_entry->name(), new_entry->value()}, index));
QUICHE_CHECK(insert_result.second);
}
auto name_result =
- dynamic_name_index_.insert(std::make_pair(new_entry->name(), new_entry));
+ dynamic_name_index_.insert(std::make_pair(new_entry->name(), index));
if (!name_result.second) {
// An entry with the same name already exists in the dynamic index. We
// should replace it with the newly added entry.
- SPDY_DVLOG(1) << "Found existing entry: "
- << name_result.first->second->GetDebugString()
- << " replacing with: " << new_entry->GetDebugString();
- QUICHE_DCHECK_GT(new_entry->InsertionIndex(),
- name_result.first->second->InsertionIndex());
+ SPDY_DVLOG(1) << "Found existing entry at: " << name_result.first->second
+ << " replacing with: " << new_entry->GetDebugString()
+ << " at: " << index;
+ QUICHE_DCHECK_GT(index, name_result.first->second);
dynamic_name_index_.erase(name_result.first);
- auto insert_result = dynamic_name_index_.insert(
- std::make_pair(new_entry->name(), new_entry));
+ auto insert_result =
+ dynamic_name_index_.insert(std::make_pair(new_entry->name(), index));
QUICHE_CHECK(insert_result.second);
}
diff --git a/spdy/core/hpack/hpack_header_table.h b/spdy/core/hpack/hpack_header_table.h
index 1022d11..6a32eb8 100644
--- a/spdy/core/hpack/hpack_header_table.h
+++ b/spdy/core/hpack/hpack_header_table.h
@@ -46,10 +46,8 @@
// which case |*_index_| can be trivially extended to map to list iterators.
using EntryTable = std::deque<HpackEntry>;
- using NameValueToEntryMap =
- absl::flat_hash_map<HpackLookupEntry, const HpackEntry*>;
- using NameToEntryMap =
- absl::flat_hash_map<absl::string_view, const HpackEntry*>;
+ using NameValueToEntryMap = absl::flat_hash_map<HpackLookupEntry, size_t>;
+ using NameToEntryMap = absl::flat_hash_map<absl::string_view, size_t>;
HpackHeaderTable();
HpackHeaderTable(const HpackHeaderTable&) = delete;
@@ -121,28 +119,28 @@
// |static_entries_|, |static_index_|, and |static_name_index_| are owned by
// HpackStaticTable singleton.
- // Tracks HpackEntries by index.
+ // Stores HpackEntries.
const EntryTable& static_entries_;
EntryTable dynamic_entries_;
- // Tracks the unique HpackEntry for a given header name and value.
- // Entries consist of string_views that point to strings stored in
+ // Tracks the index of the unique HpackEntry for a given header name and
+ // value. Keys consist of string_views that point to strings stored in
// |static_entries_|.
const NameValueToEntryMap& static_index_;
- // Tracks the first static entry for each name in the static table.
- // Each entry has a string_view that points to the name strings stored in
+ // Tracks the index of the first static entry for each name in the static
+ // table. Each key is a string_view that points to a name string stored in
// |static_entries_|.
const NameToEntryMap& static_name_index_;
- // Tracks the most recently inserted HpackEntry for a given header name and
- // value. Entries consist of string_views that point to strings stored in
- // |dynamic_entries_|.
+ // Tracks the index of the most recently inserted HpackEntry for a given
+ // header name and value. Keys consist of string_views that point to strings
+ // stored in |dynamic_entries_|.
NameValueToEntryMap dynamic_index_;
- // Tracks the most recently inserted HpackEntry for a given header name.
- // Each entry has a string_view that points to the name strings stored in
- // |dynamic_entries_|.
+ // Tracks the index of the most recently inserted HpackEntry for a given
+ // header name. Each key is a string_view that points to a name string stored
+ // in |dynamic_entries_|.
NameToEntryMap dynamic_name_index_;
// Last acknowledged value for SETTINGS_HEADER_TABLE_SIZE.
diff --git a/spdy/core/hpack/hpack_header_table_test.cc b/spdy/core/hpack/hpack_header_table_test.cc
index 82e8dc1..b3f761e 100644
--- a/spdy/core/hpack/hpack_header_table_test.cc
+++ b/spdy/core/hpack/hpack_header_table_test.cc
@@ -72,7 +72,7 @@
EXPECT_GE(size, kHpackEntrySizeOverhead);
std::string name((size - kHpackEntrySizeOverhead) / 2, 'n');
std::string value(size - kHpackEntrySizeOverhead - name.size(), 'v');
- HpackEntry entry(name, value, 0);
+ HpackEntry entry(name, value);
EXPECT_EQ(size, entry.Size());
return entry;
}
diff --git a/spdy/core/hpack/hpack_static_table.cc b/spdy/core/hpack/hpack_static_table.cc
index 7e42b89..260008b 100644
--- a/spdy/core/hpack/hpack_static_table.cc
+++ b/spdy/core/hpack/hpack_static_table.cc
@@ -20,20 +20,20 @@
size_t static_entry_count) {
QUICHE_CHECK(!IsInitialized());
- int total_insertions = 0;
+ int insertion_count = 0;
for (const HpackStaticEntry* it = static_entry_table;
it != static_entry_table + static_entry_count; ++it) {
absl::string_view name(it->name, it->name_len);
absl::string_view value(it->value, it->value_len);
- static_entries_.emplace_back(name, value, total_insertions);
+ static_entries_.emplace_back(name, value);
HpackEntry* entry = &static_entries_.back();
- auto result = static_index_.insert(
- std::make_pair(HpackLookupEntry{name, value}, entry));
+ auto result = static_index_.insert(std::make_pair(
+ HpackLookupEntry{entry->name(), entry->value()}, insertion_count));
QUICHE_CHECK(result.second);
// Multiple static entries may have the same name, so inserts may fail.
- static_name_index_.insert(std::make_pair(name, entry));
+ static_name_index_.insert(std::make_pair(entry->name(), insertion_count));
- ++total_insertions;
+ ++insertion_count;
}
}