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);