gfe-relnote: (n/a) Add pop_front_n and pop_back_n methods to QuicCircularDeque. Code not used yet.

PiperOrigin-RevId: 279127905
Change-Id: I3a5ee539cb53d1cb7fac68ba30f230135f1023fd

quic/core/quic_circular_deque.h

diff --git a/quic/core/quic_circular_deque.h b/quic/core/quic_circular_deque.h
index 54043fd..3a34626 100644
--- a/quic/core/quic_circular_deque.h
+++ b/quic/core/quic_circular_deque.h
@@ -151,17 +151,25 @@
     basic_iterator(const QuicCircularDeque* deque, size_type index)
         : deque_(deque), index_(index) {}
 
-    void Increment() { index_ = deque_->index_next(index_); }
+    void Increment() {
+      DCHECK_LE(ExternalPosition() + 1, deque_->size());
+      index_ = deque_->index_next(index_);
+    }
 
-    void Decrement() { index_ = deque_->index_prev(index_); }
+    void Decrement() {
+      DCHECK_GE(ExternalPosition(), 1);
+      index_ = deque_->index_prev(index_);
+    }
 
     void IncrementBy(difference_type delta) {
-      if (delta == 0) {
-        return;
+      if (delta >= 0) {
+        // After increment we are before or at end().
+        DCHECK_LE(ExternalPosition() + delta, deque_->size());
+      } else {
+        // After decrement we are after or at begin().
+        DCHECK_GE(ExternalPosition(), -delta);
       }
-
-      index_ = (deque_->begin_ + ExternalPosition() + delta) %
-               deque_->data_capacity();
+      index_ = deque_->index_increment_by(index_, delta);
     }
 
     size_type ExternalPosition() const {
@@ -415,6 +423,15 @@
     MaybeShrinkCapacity();
   }
 
+  size_type pop_front_n(size_type count) {
+    size_type num_elements_to_pop = std::min(count, size());
+    size_type new_begin = index_increment_by(begin_, num_elements_to_pop);
+    DestroyRange(begin_, new_begin);
+    begin_ = new_begin;
+    MaybeShrinkCapacity();
+    return num_elements_to_pop;
+  }
+
   void pop_back() {
     DCHECK(!empty());
     end_ = index_prev(end_);
@@ -422,6 +439,15 @@
     MaybeShrinkCapacity();
   }
 
+  size_type pop_back_n(size_type count) {
+    size_type num_elements_to_pop = std::min(count, size());
+    size_type new_end = index_increment_by(end_, -num_elements_to_pop);
+    DestroyRange(new_end, end_);
+    end_ = new_end;
+    MaybeShrinkCapacity();
+    return num_elements_to_pop;
+  }
+
   void swap(QuicCircularDeque& other) {
     using std::swap;
     swap(begin_, other.begin_);
@@ -683,6 +709,15 @@
     return index == data_capacity() - 1 ? 0 : index + 1;
   }
 
+  size_type index_increment_by(size_type index, difference_type delta) const {
+    if (delta == 0) {
+      return index;
+    }
+
+    DCHECK_LT(std::abs(delta), data_capacity());
+    return (index + data_capacity() + delta) % data_capacity();
+  }
+
   // Empty base-class optimization: bundle storage for our allocator together
   // with the fields we had to store anyway, via inheriting from the allocator,
   // so this allocator instance doesn't consume any storage when its type has no

quic/core/quic_circular_deque_test.cc

diff --git a/quic/core/quic_circular_deque_test.cc b/quic/core/quic_circular_deque_test.cc
index f9774ee..8844d92 100644
--- a/quic/core/quic_circular_deque_test.cc
+++ b/quic/core/quic_circular_deque_test.cc
@@ -660,6 +660,41 @@
     ASSERT_GT(&dq1.front(), &dq1.back());
     // dq1 destructs with wrapped data.
   }
+
+  {  // Pop n elements from front.
+    QuicCircularDeque<Foo, 4, CountingAllocator<Foo>> dq2(5);
+    for (size_t i = 0; i < dq2.size(); ++i) {
+      dq2[i].Set(i + 1);
+    }
+    EXPECT_THAT(dq2, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)));
+
+    EXPECT_EQ(2u, dq2.pop_front_n(2));
+    EXPECT_THAT(dq2, ElementsAre(Foo(3), Foo(4), Foo(5)));
+
+    EXPECT_EQ(3u, dq2.pop_front_n(100));
+    EXPECT_TRUE(dq2.empty());
+  }
+
+  {  // Pop n elements from back.
+    QuicCircularDeque<Foo, 4, CountingAllocator<Foo>> dq3(6);
+    for (size_t i = 0; i < dq3.size(); ++i) {
+      dq3[i].Set(i + 1);
+    }
+    EXPECT_THAT(dq3,
+                ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4), Foo(5), Foo(6)));
+
+    ShiftRight(&dq3, true);
+    ShiftRight(&dq3, true);
+    ShiftRight(&dq3, true);
+    EXPECT_THAT(dq3,
+                ElementsAre(Foo(4), Foo(5), Foo(6), Foo(1), Foo(2), Foo(3)));
+
+    EXPECT_EQ(2u, dq3.pop_back_n(2));
+    EXPECT_THAT(dq3, ElementsAre(Foo(4), Foo(5), Foo(6), Foo(1)));
+
+    EXPECT_EQ(2u, dq3.pop_back_n(2));
+    EXPECT_THAT(dq3, ElementsAre(Foo(4), Foo(5)));
+  }
 }
 
 TEST(QuicCircularDeque, Allocation) {