commit b9d64756fe21b8fa6c5956ee161c59202c0091af
author bnc <bnc@google.com> Fri May 07 08:32:36 2021 -0700
committer Copybara-Service <copybara-worker@google.com> Fri May 07 08:33:11 2021 -0700
tree a70edd6bbe7ec797e929622fce42a4d623cd250c
parent a685322effce973893f0420c8df261417fa430c5

Use circular deque in QpackDecoderHeaderTable.

This will require much fewer allocations than std::deque, with a bounded memory
usage (because the dynamic table size is bounded).  Note that HPACK decoder
already uses a circular deque (see http2::HpackDecoderDynamicTable::table_).

Keep using std::deque in QpackEncoderHeaderTable.
The same container is used in the HPACK encoder spdy::HpackHeaderTable.

PiperOrigin-RevId: 372561109
Change-Id: I73761ff632ceda9f5c9ea6727f5bed73f19ea9e8

quic/core/qpack/qpack_header_table.h

diff --git a/quic/core/qpack/qpack_header_table.h b/quic/core/qpack/qpack_header_table.h
index ce4375d..5ca3b11 100644
--- a/quic/core/qpack/qpack_header_table.h
+++ b/quic/core/qpack/qpack_header_table.h
@@ -6,12 +6,11 @@
 #define QUICHE_QUIC_CORE_QPACK_QPACK_HEADER_TABLE_H_
 
 #include <cstdint>
-#include <functional>
-#include <queue>
-#include <vector>
+#include <deque>
 
 #include "absl/strings/string_view.h"
 #include "quic/platform/api/quic_export.h"
+#include "common/quiche_circular_deque.h"
 #include "spdy/core/hpack/hpack_entry.h"
 #include "spdy/core/hpack/hpack_header_table.h"
 
@@ -23,11 +22,12 @@
 
 // Encoder needs pointer stability for |dynamic_index_| and
 // |dynamic_name_index_|.  However, it does not need random access.
-using QpackEncoderDynamicTable = spdy::HpackHeaderTable::DynamicEntryTable;
+// TODO(b/182349990): Change to a more memory efficient container.
+using QpackEncoderDynamicTable = std::deque<QpackEntry>;
 
 // Decoder needs random access for LookupEntry().
 // However, it does not need pointer stability.
-using QpackDecoderDynamicTable = spdy::HpackHeaderTable::DynamicEntryTable;
+using QpackDecoderDynamicTable = quiche::QuicheCircularDeque<QpackEntry>;
 
 // This is a base class for encoder and decoder classes that manage the QPACK
 // static and dynamic tables.  For dynamic entries, it only has a concept of

spdy/core/hpack/hpack_header_table.h

diff --git a/spdy/core/hpack/hpack_header_table.h b/spdy/core/hpack/hpack_header_table.h
index 893aaa7..49478cd 100644
--- a/spdy/core/hpack/hpack_header_table.h
+++ b/spdy/core/hpack/hpack_header_table.h
@@ -43,11 +43,6 @@
   // HpackHeaderTable takes advantage of the deque property that references
   // remain valid, so long as insertions & deletions are at the head & tail.
   // This precludes the use of base::circular_deque.
-  //
-  // If this changes (we want to change to circular_deque or we start to drop
-  // entries from the middle of the table), this should to be a std::list, in
-  // which case |*_index_| can be trivially extended to map to list iterators.
-  //
   // TODO(b/182349990): Change to a more memory efficient container.
   using DynamicEntryTable = std::deque<HpackEntry>;