Add QpackHeaderTable::draining_index().

gfe-relnote: n/a, change to QUIC v99-only code.  Protected by existing disabled
gfe2_reloadable_flag_quic_enable_version_99.
PiperOrigin-RevId: 259954990
Change-Id: I896a5b039f2d61e7b4e9f97299b9ebb2234e2820

quic/core/qpack/qpack_header_table.cc

diff --git a/quic/core/qpack/qpack_header_table.cc b/quic/core/qpack/qpack_header_table.cc
index 6fa6412..92eb072 100644
--- a/quic/core/qpack/qpack_header_table.cc
+++ b/quic/core/qpack/qpack_header_table.cc
@@ -173,6 +173,31 @@
   observers_.push({observer, required_insert_count});
 }
 
+uint64_t QpackHeaderTable::draining_index(float draining_fraction) const {
+  DCHECK_LE(0.0, draining_fraction);
+  DCHECK_LE(draining_fraction, 1.0);
+
+  const uint64_t required_space = draining_fraction * dynamic_table_capacity_;
+  uint64_t space_above_draining_index =
+      dynamic_table_capacity_ - dynamic_table_size_;
+
+  if (dynamic_entries_.empty() ||
+      space_above_draining_index >= required_space) {
+    return dropped_entry_count_;
+  }
+
+  auto it = dynamic_entries_.begin();
+  while (space_above_draining_index < required_space) {
+    space_above_draining_index += it->Size();
+    ++it;
+    if (it == dynamic_entries_.end()) {
+      return inserted_entry_count();
+    }
+  }
+
+  return it->InsertionIndex();
+}
+
 bool QpackHeaderTable::ObserverWithThreshold::operator>(
     const ObserverWithThreshold& other) const {
   return required_insert_count > other.required_insert_count;

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 39d7326..54b0829 100644
--- a/quic/core/qpack/qpack_header_table.h
+++ b/quic/core/qpack/qpack_header_table.h
@@ -99,6 +99,14 @@
   // The number of entries dropped from the dynamic table.
   uint64_t dropped_entry_count() const { return dropped_entry_count_; }
 
+  // Returns the draining index described at
+  // https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#avoiding-blocked-insertions.
+  // Entries with an index larger than or equal to the draining index take up
+  // approximately |1.0 - draining_fraction| of dynamic table capacity.  The
+  // remaining capacity is taken up by draining entries and unused space.
+  // The returned index might not be the index of a valid entry.
+  uint64_t draining_index(float draining_fraction) const;
+
  private:
   // Evict entries from the dynamic table until table size is less than or equal
   // to current value of |dynamic_table_capacity_|.

quic/core/qpack/qpack_header_table_test.cc

diff --git a/quic/core/qpack/qpack_header_table_test.cc b/quic/core/qpack/qpack_header_table_test.cc
index ff7ef48..7d1044b 100644
--- a/quic/core/qpack/qpack_header_table_test.cc
+++ b/quic/core/qpack/qpack_header_table_test.cc
@@ -404,6 +404,42 @@
   Mock::VerifyAndClearExpectations(&observer5);
 }
 
+TEST_F(QpackHeaderTableTest, DrainingIndex) {
+  QpackHeaderTable table;
+  table.SetMaximumDynamicTableCapacity(4 * QpackEntry::Size("foo", "bar"));
+
+  // Empty table: no draining entry.
+  EXPECT_EQ(0u, table.draining_index(0.0));
+  EXPECT_EQ(0u, table.draining_index(1.0));
+
+  // Table with one entry.
+  EXPECT_TRUE(table.InsertEntry("foo", "bar"));
+  // Any entry can be referenced if none of the table is draining.
+  EXPECT_EQ(0u, table.draining_index(0.0));
+  // No entry can be referenced if all of the table is draining.
+  EXPECT_EQ(1u, table.draining_index(1.0));
+
+  // Table with two entries is at half capacity.
+  EXPECT_TRUE(table.InsertEntry("foo", "bar"));
+  // Any entry can be referenced if at most half of the table is draining,
+  // because current entries only take up half of total capacity.
+  EXPECT_EQ(0u, table.draining_index(0.0));
+  EXPECT_EQ(0u, table.draining_index(0.5));
+  // No entry can be referenced if all of the table is draining.
+  EXPECT_EQ(2u, table.draining_index(1.0));
+
+  // Table with four entries is full.
+  EXPECT_TRUE(table.InsertEntry("foo", "bar"));
+  EXPECT_TRUE(table.InsertEntry("foo", "bar"));
+  // Any entry can be referenced if none of the table is draining.
+  EXPECT_EQ(0u, table.draining_index(0.0));
+  // In a full table with identically sized entries, |draining_fraction| of all
+  // entries are draining.
+  EXPECT_EQ(2u, table.draining_index(0.5));
+  // No entry can be referenced if all of the table is draining.
+  EXPECT_EQ(4u, table.draining_index(1.0));
+}
+
 }  // namespace
 }  // namespace test
 }  // namespace quic