Return index instead of HpackEntry* from HpackHeaderTable::GetByName*().
This allows HpackHeaderTable::IndexOf() to be removed. It will also allow for
internal storage to be changed in a later CL.
PiperOrigin-RevId: 363217057
Change-Id: I87430171b6b2946bda8e7ee630100caaf0dc59b9
diff --git a/spdy/core/hpack/hpack_encoder.cc b/spdy/core/hpack/hpack_encoder.cc
index 4aecc73..42777a4 100644
--- a/spdy/core/hpack/hpack_encoder.cc
+++ b/spdy/core/hpack/hpack_encoder.cc
@@ -137,10 +137,10 @@
const auto header = iter->Next();
listener_(header.first, header.second);
if (enable_compression_) {
- const HpackEntry* entry =
+ size_t index =
header_table_.GetByNameAndValue(header.first, header.second);
- if (entry != nullptr) {
- EmitIndex(entry);
+ if (index != kHpackEntryNotFound) {
+ EmitIndex(index);
} else if (should_index_(header.first, header.second)) {
EmitIndexedLiteral(header);
} else {
@@ -154,10 +154,10 @@
output_stream_.TakeString(output);
}
-void HpackEncoder::EmitIndex(const HpackEntry* entry) {
- SPDY_DVLOG(2) << "Emitting index " << header_table_.IndexOf(entry);
+void HpackEncoder::EmitIndex(size_t index) {
+ SPDY_DVLOG(2) << "Emitting index " << index;
output_stream_.AppendPrefix(kIndexedOpcode);
- output_stream_.AppendUint32(header_table_.IndexOf(entry));
+ output_stream_.AppendUint32(index);
}
void HpackEncoder::EmitIndexedLiteral(const Representation& representation) {
@@ -173,9 +173,9 @@
SPDY_DVLOG(2) << "Emitting nonindexed literal: (" << representation.first
<< ", " << representation.second << ")";
output_stream_.AppendPrefix(kLiteralNoIndexOpcode);
- const HpackEntry* name_entry = header_table_.GetByName(representation.first);
- if (enable_compression && name_entry != nullptr) {
- output_stream_.AppendUint32(header_table_.IndexOf(name_entry));
+ size_t name_index = header_table_.GetByName(representation.first);
+ if (enable_compression && name_index != kHpackEntryNotFound) {
+ output_stream_.AppendUint32(name_index);
} else {
output_stream_.AppendUint32(0);
EmitString(representation.first);
@@ -184,9 +184,9 @@
}
void HpackEncoder::EmitLiteral(const Representation& representation) {
- const HpackEntry* name_entry = header_table_.GetByName(representation.first);
- if (name_entry != nullptr) {
- output_stream_.AppendUint32(header_table_.IndexOf(name_entry));
+ size_t name_index = header_table_.GetByName(representation.first);
+ if (name_index != kHpackEntryNotFound) {
+ output_stream_.AppendUint32(name_index);
} else {
output_stream_.AppendUint32(0);
EmitString(representation.first);
@@ -357,10 +357,10 @@
const Representation header = header_it_->Next();
encoder_->listener_(header.first, header.second);
if (enable_compression) {
- const HpackEntry* entry = encoder_->header_table_.GetByNameAndValue(
- header.first, header.second);
- if (entry != nullptr) {
- encoder_->EmitIndex(entry);
+ size_t index = encoder_->header_table_.GetByNameAndValue(header.first,
+ header.second);
+ if (index != kHpackEntryNotFound) {
+ encoder_->EmitIndex(index);
} else if (encoder_->should_index_(header.first, header.second)) {
encoder_->EmitIndexedLiteral(header);
} else {
diff --git a/spdy/core/hpack/hpack_encoder.h b/spdy/core/hpack/hpack_encoder.h
index 70fade8..d85b98e 100644
--- a/spdy/core/hpack/hpack_encoder.h
+++ b/spdy/core/hpack/hpack_encoder.h
@@ -108,7 +108,7 @@
void EncodeRepresentations(RepresentationIterator* iter, std::string* output);
// Emits a static/dynamic indexed representation (Section 7.1).
- void EmitIndex(const HpackEntry* entry);
+ void EmitIndex(size_t index);
// Emits a literal representation (Section 7.2).
void EmitIndexedLiteral(const Representation& representation);
diff --git a/spdy/core/hpack/hpack_encoder_test.cc b/spdy/core/hpack/hpack_encoder_test.cc
index 1498312..3f0fbaa 100644
--- a/spdy/core/hpack/hpack_encoder_test.cc
+++ b/spdy/core/hpack/hpack_encoder_test.cc
@@ -166,12 +166,6 @@
expected_.AppendPrefix(kIndexedOpcode);
expected_.AppendUint32(index);
}
- void ExpectIndexedLiteral(const HpackEntry* key_entry,
- absl::string_view value) {
- expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
- expected_.AppendUint32(peer_.table()->IndexOf(key_entry));
- ExpectString(&expected_, value);
- }
void ExpectIndexedLiteral(size_t key_index, absl::string_view value) {
expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
expected_.AppendUint32(key_index);
@@ -190,10 +184,10 @@
ExpectString(&expected_, name);
ExpectString(&expected_, value);
}
- void ExpectNonIndexedLiteralWithNameIndex(const HpackEntry* key_entry,
+ void ExpectNonIndexedLiteralWithNameIndex(size_t key_index,
absl::string_view value) {
expected_.AppendPrefix(kLiteralNoIndexOpcode);
- expected_.AppendUint32(peer_.table()->IndexOf(key_entry));
+ expected_.AppendUint32(key_index);
ExpectString(&expected_, value);
}
void ExpectString(HpackOutputStream* stream, absl::string_view str) {
diff --git a/spdy/core/hpack/hpack_entry_test.cc b/spdy/core/hpack/hpack_entry_test.cc
index dfb4888..ecd5565 100644
--- a/spdy/core/hpack/hpack_entry_test.cc
+++ b/spdy/core/hpack/hpack_entry_test.cc
@@ -30,14 +30,6 @@
}
void DropEntry() { --table_size_; }
- size_t IndexOf(const HpackEntry& entry) const {
- if (entry.IsStatic()) {
- return 1 + entry.InsertionIndex() + table_size_;
- } else {
- return total_insertions_ - entry.InsertionIndex();
- }
- }
-
size_t Size() {
return name_.size() + value_.size() + kHpackEntrySizeOverhead;
}
@@ -56,7 +48,6 @@
EXPECT_EQ(name_, entry.name());
EXPECT_EQ(value_, entry.value());
EXPECT_TRUE(entry.IsStatic());
- EXPECT_EQ(1u, IndexOf(entry));
EXPECT_EQ(Size(), entry.Size());
}
@@ -66,7 +57,6 @@
EXPECT_EQ(name_, entry.name());
EXPECT_EQ(value_, entry.value());
EXPECT_FALSE(entry.IsStatic());
- EXPECT_EQ(1u, IndexOf(entry));
EXPECT_EQ(Size(), entry.Size());
}
@@ -76,7 +66,6 @@
EXPECT_EQ(name_, entry.name());
EXPECT_EQ(value_, entry.value());
EXPECT_FALSE(entry.IsStatic());
- EXPECT_EQ(0u, IndexOf(entry));
EXPECT_EQ(Size(), entry.Size());
}
@@ -88,35 +77,6 @@
EXPECT_EQ(kHpackEntrySizeOverhead, entry.Size());
}
-TEST_F(HpackEntryTest, IndexUpdate) {
- HpackEntry static1(StaticEntry());
- HpackEntry static2(StaticEntry());
-
- EXPECT_EQ(1u, IndexOf(static1));
- EXPECT_EQ(2u, IndexOf(static2));
-
- HpackEntry dynamic1(DynamicEntry());
- HpackEntry dynamic2(DynamicEntry());
-
- EXPECT_EQ(1u, IndexOf(dynamic2));
- EXPECT_EQ(2u, IndexOf(dynamic1));
- EXPECT_EQ(3u, IndexOf(static1));
- EXPECT_EQ(4u, IndexOf(static2));
-
- DropEntry(); // Drops |dynamic1|.
-
- EXPECT_EQ(1u, IndexOf(dynamic2));
- EXPECT_EQ(2u, IndexOf(static1));
- EXPECT_EQ(3u, IndexOf(static2));
-
- HpackEntry dynamic3(DynamicEntry());
-
- EXPECT_EQ(1u, IndexOf(dynamic3));
- EXPECT_EQ(2u, IndexOf(dynamic2));
- EXPECT_EQ(3u, IndexOf(static1));
- EXPECT_EQ(4u, IndexOf(static2));
-}
-
} // namespace
} // namespace spdy
diff --git a/spdy/core/hpack/hpack_header_table.cc b/spdy/core/hpack/hpack_header_table.cc
index e720bab..e8e469b 100644
--- a/spdy/core/hpack/hpack_header_table.cc
+++ b/spdy/core/hpack/hpack_header_table.cc
@@ -57,48 +57,39 @@
return nullptr;
}
-const HpackEntry* HpackHeaderTable::GetByName(absl::string_view name) {
+size_t HpackHeaderTable::GetByName(absl::string_view name) {
{
auto it = static_name_index_.find(name);
if (it != static_name_index_.end()) {
- return it->second;
+ return 1 + it->second->InsertionIndex();
}
}
{
NameToEntryMap::const_iterator it = dynamic_name_index_.find(name);
if (it != dynamic_name_index_.end()) {
- return it->second;
+ return total_insertions_ - it->second->InsertionIndex() +
+ kStaticTableSize;
}
}
- return nullptr;
+ return kHpackEntryNotFound;
}
-const HpackEntry* HpackHeaderTable::GetByNameAndValue(absl::string_view name,
- absl::string_view value) {
+size_t HpackHeaderTable::GetByNameAndValue(absl::string_view name,
+ absl::string_view value) {
HpackEntry query(name, value);
{
auto it = static_index_.find(&query);
if (it != static_index_.end()) {
- return *it;
+ return 1 + (*it)->InsertionIndex();
}
}
{
auto it = dynamic_index_.find(&query);
if (it != dynamic_index_.end()) {
- return *it;
+ return total_insertions_ - (*it)->InsertionIndex() + kStaticTableSize;
}
}
- return nullptr;
-}
-
-size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
- if (entry->IsLookup()) {
- return 0;
- } else if (entry->IsStatic()) {
- return 1 + entry->InsertionIndex();
- } else {
- return total_insertions_ - entry->InsertionIndex() + kStaticTableSize;
- }
+ return kHpackEntryNotFound;
}
void HpackHeaderTable::SetMaxSize(size_t max_size) {
diff --git a/spdy/core/hpack/hpack_header_table.h b/spdy/core/hpack/hpack_header_table.h
index d522aaa..88a656f 100644
--- a/spdy/core/hpack/hpack_header_table.h
+++ b/spdy/core/hpack/hpack_header_table.h
@@ -25,6 +25,11 @@
class HpackHeaderTablePeer;
} // namespace test
+// Return value of GetByName() and GetByNameAndValue() if matching entry is not
+// found. This value is never used in HPACK for indexing entries, see
+// https://httpwg.org/specs/rfc7541.html#index.address.space.
+constexpr size_t kHpackEntryNotFound = 0;
+
// A data structure for the static table (2.3.1) and the dynamic table (2.3.2).
class QUICHE_EXPORT_PRIVATE HpackHeaderTable {
public:
@@ -64,18 +69,20 @@
size_t size() const { return size_; }
size_t max_size() const { return max_size_; }
+ // The HPACK indexing scheme used by GetByIndex(), GetByName(), and
+ // GetByNameAndValue() is defined at
+ // https://httpwg.org/specs/rfc7541.html#index.address.space.
+
// Returns the entry matching the index, or NULL.
const HpackEntry* GetByIndex(size_t index);
- // Returns the lowest-value entry having |name|, or NULL.
- const HpackEntry* GetByName(absl::string_view name);
+ // Returns the index of the lowest-index entry matching |name|,
+ // or kHpackEntryNotFound if no matching entry is found.
+ size_t GetByName(absl::string_view name);
- // Returns the lowest-index matching entry, or NULL.
- const HpackEntry* GetByNameAndValue(absl::string_view name,
- absl::string_view value);
-
- // Returns the index of an entry within this header table.
- size_t IndexOf(const HpackEntry* entry) const;
+ // Returns the index of the lowest-index entry matching |name| and |value|,
+ // or kHpackEntryNotFound if no matching entry is found.
+ size_t GetByNameAndValue(absl::string_view name, absl::string_view value);
// Sets the maximum size of the header table, evicting entries if
// necessary as described in 5.2.
@@ -144,8 +151,8 @@
size_t size_;
size_t max_size_;
- // Total number of table insertions which have occurred. Referenced by
- // IndexOf() for determination of an HpackEntry's table index.
+ // Total number of table insertions which have occurred,
+ // including initial static table insertions.
size_t total_insertions_;
};
diff --git a/spdy/core/hpack/hpack_header_table_test.cc b/spdy/core/hpack/hpack_header_table_test.cc
index 1cef8df..31d64b7 100644
--- a/spdy/core/hpack/hpack_header_table_test.cc
+++ b/spdy/core/hpack/hpack_header_table_test.cc
@@ -13,6 +13,7 @@
#include "common/platform/api/quiche_test.h"
#include "spdy/core/hpack/hpack_constants.h"
#include "spdy/core/hpack/hpack_entry.h"
+#include "spdy/core/hpack/hpack_static_table.h"
namespace spdy {
@@ -114,11 +115,10 @@
for (size_t i = 0; i != entries.size(); ++i) {
// Static table has 61 entries, dynamic entries follow those.
- size_t index = 61 + entries.size() - i;
+ size_t index = kStaticTableSize + entries.size() - i;
const HpackEntry* entry = table_.GetByIndex(index);
EXPECT_EQ(entries[i].name(), entry->name());
EXPECT_EQ(entries[i].value(), entry->value());
- EXPECT_EQ(index, table_.IndexOf(entry));
}
}
@@ -146,16 +146,18 @@
const HpackEntry* entry = &peer_.static_entries()[i];
EXPECT_TRUE(entry->IsStatic());
- EXPECT_EQ(entry, table_.GetByIndex(i + 1));
- EXPECT_EQ(entry, table_.GetByNameAndValue(entry->name(), entry->value()));
+
+ size_t index = i + 1;
+ EXPECT_EQ(entry, table_.GetByIndex(index));
+ EXPECT_EQ(index, table_.GetByNameAndValue(entry->name(), entry->value()));
}
}
TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) {
size_t static_count = peer_.total_insertions();
- const HpackEntry* first_static_entry = table_.GetByIndex(1);
- EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
+ const HpackEntry* first_static_entry = table_.GetByIndex(1);
+ EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
const HpackEntry* entry = table_.TryAddEntry("header-key", "Header Value");
EXPECT_EQ("header-key", entry->name());
@@ -169,13 +171,11 @@
EXPECT_EQ(static_count + 1, peer_.total_insertions());
EXPECT_EQ(static_count + 1, peer_.index_size());
- // Index() of entries reflects the insertion.
- EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
- // Static table has 61 entries.
- EXPECT_EQ(62u, table_.IndexOf(entry));
- EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
EXPECT_EQ(entry, table_.GetByIndex(62));
+ // Index of |first_static_entry| does not change.
+ EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
+
// Evict |entry|. Table counts are again updated appropriately.
peer_.Evict(1);
EXPECT_EQ(0u, table_.size());
@@ -184,8 +184,7 @@
EXPECT_EQ(static_count + 1, peer_.total_insertions());
EXPECT_EQ(static_count, peer_.index_size());
- // Index() of |first_static_entry| reflects the eviction.
- EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
+ // Index of |first_static_entry| does not change.
EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
}
@@ -193,10 +192,9 @@
const HpackEntry* first_static_entry = table_.GetByIndex(1);
// Static entries are queryable by name & value.
- EXPECT_EQ(first_static_entry, table_.GetByName(first_static_entry->name()));
- EXPECT_EQ(first_static_entry,
- table_.GetByNameAndValue(first_static_entry->name(),
- first_static_entry->value()));
+ EXPECT_EQ(1u, table_.GetByName(first_static_entry->name()));
+ EXPECT_EQ(1u, table_.GetByNameAndValue(first_static_entry->name(),
+ first_static_entry->value()));
// Create a mix of entries which duplicate names, and names & values of both
// dynamic and static entries.
@@ -221,38 +219,37 @@
EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
// Querying by name returns the most recently added matching entry.
- EXPECT_EQ(entry5, table_.GetByName("key-1"));
- EXPECT_EQ(entry7, table_.GetByName("key-2"));
- EXPECT_EQ(entry2->name(),
- table_.GetByName(first_static_entry->name())->name());
- EXPECT_EQ(nullptr, table_.GetByName("not-present"));
+ EXPECT_EQ(64u, table_.GetByName("key-1"));
+ EXPECT_EQ(62u, table_.GetByName("key-2"));
+ EXPECT_EQ(1u, table_.GetByName(first_static_entry->name()));
+ EXPECT_EQ(kHpackEntryNotFound, table_.GetByName("not-present"));
// Querying by name & value returns the lowest-index matching entry among
// static entries, and the highest-index one among dynamic entries.
- EXPECT_EQ(entry3, table_.GetByNameAndValue("key-1", "Value One"));
- EXPECT_EQ(entry5, table_.GetByNameAndValue("key-1", "Value Two"));
- EXPECT_EQ(entry6, table_.GetByNameAndValue("key-2", "Value Three"));
- EXPECT_EQ(entry7, table_.GetByNameAndValue("key-2", "Value Four"));
- EXPECT_EQ(first_static_entry,
- table_.GetByNameAndValue(first_static_entry->name(),
- first_static_entry->value()));
- EXPECT_EQ(entry2,
+ EXPECT_EQ(66u, table_.GetByNameAndValue("key-1", "Value One"));
+ EXPECT_EQ(64u, table_.GetByNameAndValue("key-1", "Value Two"));
+ EXPECT_EQ(63u, table_.GetByNameAndValue("key-2", "Value Three"));
+ EXPECT_EQ(62u, table_.GetByNameAndValue("key-2", "Value Four"));
+ EXPECT_EQ(1u, table_.GetByNameAndValue(first_static_entry->name(),
+ first_static_entry->value()));
+ EXPECT_EQ(67u,
table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
- EXPECT_EQ(nullptr, table_.GetByNameAndValue("key-1", "Not Present"));
- EXPECT_EQ(nullptr, table_.GetByNameAndValue("not-present", "Value One"));
+ EXPECT_EQ(kHpackEntryNotFound,
+ table_.GetByNameAndValue("key-1", "Not Present"));
+ EXPECT_EQ(kHpackEntryNotFound,
+ table_.GetByNameAndValue("not-present", "Value One"));
// Evict |entry1|. Queries for its name & value now return the static entry.
// |entry2| remains queryable.
peer_.Evict(1);
- EXPECT_EQ(first_static_entry,
- table_.GetByNameAndValue(first_static_entry->name(),
- first_static_entry->value()));
- EXPECT_EQ(entry2,
+ EXPECT_EQ(1u, table_.GetByNameAndValue(first_static_entry->name(),
+ first_static_entry->value()));
+ EXPECT_EQ(67u,
table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
// Evict |entry2|. Queries by its name & value are not found.
peer_.Evict(1);
- EXPECT_EQ(nullptr,
+ EXPECT_EQ(kHpackEntryNotFound,
table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
}
@@ -373,7 +370,6 @@
const HpackEntry* new_entry =
table_.TryAddEntry(long_entry.name(), long_entry.value());
- EXPECT_EQ(62u, table_.IndexOf(new_entry));
EXPECT_EQ(2u, peer_.dynamic_entries().size());
EXPECT_EQ(table_.GetByIndex(63), survivor_entry);
EXPECT_EQ(table_.GetByIndex(62), new_entry);
