Add QuicheCircularDeque::shrink_to_fit.

Notes:
1. This is useful if the data structure (e.g., in a connection that has been idle for a long time) has excessive unused capacity.
2. quiche::QuicheCircularDeque cannot be replaced with absl::chunked_queue completely as the later is not a deque and does not offer random access.
PiperOrigin-RevId: 873030800

quiche/common/quiche_circular_deque.h

diff --git a/quiche/common/quiche_circular_deque.h b/quiche/common/quiche_circular_deque.h
index 5c8fc1f..28c32c7 100644
--- a/quiche/common/quiche_circular_deque.h
+++ b/quiche/common/quiche_circular_deque.h
@@ -457,6 +457,15 @@
     return num_elements_to_pop;
   }
 
+  // Requests the reduction of unused capacity. A bit headroom is still kept.
+  void shrink_to_fit() {
+    size_type new_capacity =
+        size() + std::max(MinCapacityIncrement, size() / 4);
+    if (capacity() > new_capacity) {
+      Relocate(new_capacity);
+    }
+  }
+
   void swap(QuicheCircularDeque& other) {
     using std::swap;
     swap(begin_, other.begin_);

quiche/common/quiche_circular_deque_test.cc

diff --git a/quiche/common/quiche_circular_deque_test.cc b/quiche/common/quiche_circular_deque_test.cc
index 9278420..48fe474 100644
--- a/quiche/common/quiche_circular_deque_test.cc
+++ b/quiche/common/quiche_circular_deque_test.cc
@@ -540,6 +540,84 @@
   EXPECT_EQ(5, *(dq2.rbegin() + 1));
 }
 
+TEST_F(QuicheCircularDequeTest, ShrinkToFitOnEmptyDeque) {
+  QuicheCircularDeque<int> dq;
+  EXPECT_EQ(0u, dq.size());
+  EXPECT_EQ(0u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(0u, dq.size());
+  EXPECT_EQ(0u, dq.capacity());
+}
+
+TEST_F(QuicheCircularDequeTest, ShrinkToFitOnSmallDeque) {
+  QuicheCircularDeque<int> dq;
+  dq.push_back(1);
+  EXPECT_EQ(1u, dq.size());
+  EXPECT_EQ(3u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(1u, dq.size());
+  EXPECT_EQ(3u, dq.capacity());
+  dq.clear();
+  EXPECT_EQ(0u, dq.size());
+  EXPECT_EQ(3u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(0u, dq.size());
+  EXPECT_EQ(3u, dq.capacity());
+}
+
+TEST_F(QuicheCircularDequeTest, ShrinkToFitOnLargeDeque) {
+  QuicheCircularDeque<int> dq;
+  dq.assign(64, 1);
+  dq.push_back(2);
+  EXPECT_EQ(65u, dq.size());
+  EXPECT_EQ(80u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(65u, dq.size());
+  EXPECT_EQ(80u, dq.capacity());
+  dq.pop_front_n(33);
+  EXPECT_EQ(32u, dq.size());
+  EXPECT_EQ(80u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(32u, dq.size());
+  EXPECT_EQ(40u, dq.capacity());
+  dq.pop_front_n(16);
+  EXPECT_EQ(16u, dq.size());
+  EXPECT_EQ(40u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(16u, dq.size());
+  EXPECT_EQ(20u, dq.capacity());
+  dq.pop_front_n(8);
+  EXPECT_EQ(8u, dq.size());
+  EXPECT_EQ(20u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(8u, dq.size());
+  EXPECT_EQ(11u, dq.capacity());
+  dq.pop_front_n(4);
+  EXPECT_EQ(4u, dq.size());
+  EXPECT_EQ(11u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(4u, dq.size());
+  EXPECT_EQ(7u, dq.capacity());
+  dq.pop_front_n(2);
+  EXPECT_EQ(2u, dq.size());
+  EXPECT_EQ(7u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(2u, dq.size());
+  EXPECT_EQ(5u, dq.capacity());
+  dq.pop_front();
+  EXPECT_EQ(1u, dq.size());
+  EXPECT_EQ(5u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(1u, dq.size());
+  EXPECT_EQ(4u, dq.capacity());
+  dq.pop_front();
+  EXPECT_EQ(0u, dq.size());
+  EXPECT_EQ(4u, dq.capacity());
+  dq.shrink_to_fit();
+  EXPECT_EQ(0u, dq.size());
+  EXPECT_EQ(3u, dq.capacity());
+}
+
 namespace {
 class Foo {
  public: