Add push_front and emplace_front to absl::chunked_queue.

This implements push_front and emplace_front operations, prepending elements into available space in the head block or allocating a new head block when needed. Corresponding unit tests, exception safety tests, fuzzing actions, and benchmarks are also added.

PiperOrigin-RevId: 998673257
Change-Id: Ibe23e6276d1b016128c2505c756acb59ae9688ac

absl/container/BUILD.bazel

diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index d325e39..850eaec 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -1488,6 +1488,7 @@
         "//absl/base:core_headers",
         "//absl/base:hardening",
         "//absl/base:iterator_traits_internal",
+        "//absl/cleanup",
     ],
 )
 

absl/container/CMakeLists.txt

diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index 79bcee0..7a2641c 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -1239,6 +1239,7 @@
   LINKOPTS
     ${ABSL_DEFAULT_LINKOPTS}
   DEPS
+     absl::cleanup
      absl::config
      absl::core_headers
      absl::hardening

absl/container/chunked_queue.h

diff --git a/absl/container/chunked_queue.h b/absl/container/chunked_queue.h
index bcaa508..54cb6d8 100644
--- a/absl/container/chunked_queue.h
+++ b/absl/container/chunked_queue.h
@@ -35,6 +35,8 @@
 //   shrink_to_fit()
 //   resize()
 //   assign()
+//   push_front()
+//   emplace_front()
 //   push_back()
 //   emplace_back()
 //   pop_front()
@@ -110,6 +112,7 @@
 #include "absl/base/internal/hardening.h"
 #include "absl/base/internal/iterator_traits.h"
 #include "absl/base/macros.h"
+#include "absl/cleanup/cleanup.h"
 #include "absl/container/internal/chunked_queue.h"
 #include "absl/container/internal/layout.h"
 
@@ -402,6 +405,20 @@
   // Replaces the contents with the elements from the initializer list `il`.
   void assign(std::initializer_list<T> il) { assign(il.begin(), il.end()); }
 
+  // Prepends the given element value to the beginning of the container.
+  // Invalidates `end()` iterator if the container was empty. References to
+  // other elements remain valid.
+  void push_front(const T& val) { emplace_front(val); }
+  void push_front(T&& val) { emplace_front(std::move(val)); }
+
+  // Prepends a new element to the beginning of the container.
+  // The element is constructed in-place with `args`.
+  // Returns a reference to the new element.
+  // Invalidates `end()` iterator if the container was empty. References to
+  // other elements remain valid.
+  template <typename... A>
+  T& emplace_front(A&&... args);
+
   // Appends the given element value to the end of the container.
   // Invalidates `end()` iterator. References to other elements remain valid.
   void push_back(const T& val) { emplace_back(val); }
@@ -537,10 +554,13 @@
   }
 
   void AddTailBlock();
-  size_t NewBlockSize() {
-    // Double the last block size and bound to [kBlockSizeMin, kBlockSizeMax].
-    if (!tail_.block) return kBlockSizeMin;
-    return (std::min)(kBlockSizeMax, 2 * tail_.block->size());
+  // Returns the capacity (in elements) to allocate for a new block adjacent to
+  // `b` (`head_.block` when prepending or `tail_.block` when appending). Starts
+  // at `kBlockSizeMin` when `b` is null, otherwise doubles `b->size()` and
+  // clamps to `[kBlockSizeMin, kBlockSizeMax]`.
+  size_t NewBlockSize(Block* b) {
+    if (!b) return kBlockSizeMin;
+    return (std::min)(kBlockSizeMax, 2 * b->size());
   }
 
   T* AllocateBack();
@@ -651,9 +671,70 @@
 }
 
 template <typename T, size_t BLo, size_t BHi, typename Allocator>
+template <typename... A>
+T& chunked_queue<T, BLo, BHi, Allocator>::emplace_front(A&&... args) {
+  // Per "The set of elements in the queue" / "Rep invariants" (documented above
+  // `head_` and `tail_`), in a multi-block queue the head block holds
+  // `[head_.ptr .. head_.block->limit()-1]`, interior blocks hold all elements
+  // `[b->start() .. b->limit()-1]`, and the tail block holds
+  // `[tail_.block->start() .. tail_.ptr-1]` (as also assumed by `block_begin()`
+  // and `iterator_common::Incr()`). Therefore, a head block is populated from
+  // `b->limit() - 1` down to `b->start()` before a new head block can be
+  // prepended.
+
+  // Determine the target block `b` and element slot `storage`, allocating a new
+  // head block if needed.
+  Block* b = head_.block;
+  T* storage;
+  if (empty()) {
+    // Empty queue: allocate the first block if none exists, or reuse the empty
+    // block retained by `clear()` / `pop_front()`.
+    if (!b) {
+      b = Block::New(NewBlockSize(b), &alloc_and_size_.allocator());
+    }
+    storage = b->limit() - 1;
+  } else if (head_.ptr == head_.block->start()) {
+    // Full head block (no spare capacity before `head_.ptr`): allocate a new
+    // head block to prepend.
+    b = Block::New(NewBlockSize(b), &alloc_and_size_.allocator());
+    storage = b->limit() - 1;
+  } else {
+    // Partially filled head block: use the slot immediately before `head_.ptr`.
+    storage = head_.ptr - 1;
+  }
+
+  // Construct the new element in `storage`.
+  {
+    // Exception safety: Unlike `emplace_back()` (where `AddTailBlock()` links
+    // the new block into `tail_` before construction with `tail_.ptr ==
+    // b->start()`, so the container owns it if construction throws), `b` is not
+    // linked into `head_` until after construction succeeds so that `head_`
+    // remains valid on throw. Delete `b` if construction throws.
+    absl::Cleanup cleanup = [&] {
+      if (b != head_.block) Block::Delete(b, &alloc_and_size_.allocator());
+    };
+    AllocatorTraits::construct(alloc_and_size_.allocator(), storage,
+                               std::forward<A>(args)...);
+    std::move(cleanup).Cancel();
+  }
+
+  // Link the new block (if allocated) and update queue iterators and size.
+  if (empty()) {
+    tail_.block = b;
+    tail_.ptr = b->limit();
+  } else if (b != head_.block) {
+    b->set_next(head_.block);
+  }
+  head_.block = b;
+  head_.ptr = storage;
+  ++alloc_and_size_.size;
+  return *storage;
+}
+
+template <typename T, size_t BLo, size_t BHi, typename Allocator>
 inline void chunked_queue<T, BLo, BHi, Allocator>::AddTailBlock() {
   ABSL_ASSERT(!tail_.block || tail_.ptr == tail_.block->limit());
-  auto* b = Block::New(NewBlockSize(), &alloc_and_size_.allocator());
+  auto* b = Block::New(NewBlockSize(tail_.block), &alloc_and_size_.allocator());
   if (!head_.block) {
     ABSL_ASSERT(!tail_.block);
     head_ = iterator(b);

absl/container/chunked_queue_benchmark.cc

diff --git a/absl/container/chunked_queue_benchmark.cc b/absl/container/chunked_queue_benchmark.cc
index ee4d3c1..3c031ed 100644
--- a/absl/container/chunked_queue_benchmark.cc
+++ b/absl/container/chunked_queue_benchmark.cc
@@ -38,6 +38,16 @@
   ~forward_list_queue() = default;
 
   template <typename... Args>
+  void emplace_front(Args&&... args) {
+    if (list_.empty()) {
+      list_.emplace_front(std::forward<Args>(args)...);
+      tail_ = list_.begin();
+    } else {
+      list_.emplace_front(std::forward<Args>(args)...);
+    }
+  }
+
+  template <typename... Args>
   void emplace_back(Args&&... args) {
     if (list_.empty()) {
       list_.emplace_front(std::forward<Args>(args)...);
@@ -48,6 +58,7 @@
     }
   }
 
+  void push_front(const T& value) { emplace_front(value); }
   void push_back(const T& value) { emplace_back(value); }
   iterator begin() { return list_.begin(); }
   iterator end() { return list_.end(); }
@@ -146,6 +157,31 @@
 BENCHMARK_TEMPLATE(BM_destroy, ExpChunked<Element>)->Apply(CustomArgs);
 
 template <class Q>
+void BM_push_front(benchmark::State& state) {
+  const int64_t num_elements = state.range(0);
+
+  state.SetItemsProcessed(state.max_iterations * num_elements);
+  for (auto s : state) {
+    state.PauseTiming();
+    Q q;
+    state.ResumeTiming();
+    for (int j = 0; j < num_elements; j++) q.push_front(j);
+    benchmark::DoNotOptimize(q);
+  }
+}
+
+BENCHMARK_TEMPLATE(BM_push_front, Deque<int64_t>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, List<int64_t>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, FwdList<int64_t>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, Chunked<int64_t>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, ExpChunked<int64_t>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, Deque<Element>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, List<Element>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, FwdList<Element>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, Chunked<Element>)->Apply(CustomArgs);
+BENCHMARK_TEMPLATE(BM_push_front, ExpChunked<Element>)->Apply(CustomArgs);
+
+template <class Q>
 void BM_push_back(benchmark::State& state) {
   const int64_t num_elements = state.range(0);
 

absl/container/chunked_queue_test.cc

diff --git a/absl/container/chunked_queue_test.cc b/absl/container/chunked_queue_test.cc
index f3f9b3e..b4604b6 100644
--- a/absl/container/chunked_queue_test.cc
+++ b/absl/container/chunked_queue_test.cc
@@ -346,6 +346,59 @@
   EXPECT_EQ(0, q.size());
 }
 
+TEST(ChunkedQueue, PushFrontAndPop) {
+  absl::chunked_queue<int64_t> q;
+  EXPECT_TRUE(q.empty());
+  EXPECT_EQ(0, q.size());
+  // Push enough elements to exercise exponential block growth from
+  // `kBlockSizeMin` (1) up to `kBlockSizeMax` (128) across multiple max-sized
+  // head blocks (`1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255`).
+  constexpr int kNumElements = 500;
+  for (int i = 0; i < kNumElements; i++) {
+    q.push_front(i);
+    EXPECT_EQ(q.front(), i) << ": iteration " << i;
+    EXPECT_EQ(q.back(), 0) << ": iteration " << i;
+    EXPECT_FALSE(q.empty());
+    EXPECT_EQ(i + 1, q.size());
+  }
+  for (int i = 0; i < kNumElements; i++) {
+    EXPECT_FALSE(q.empty());
+    EXPECT_EQ(kNumElements - i, q.size());
+    EXPECT_EQ(q.front(), kNumElements - 1 - i);
+    EXPECT_EQ(q.back(), 0);
+    q.pop_front();
+  }
+  EXPECT_TRUE(q.empty());
+  EXPECT_EQ(0, q.size());
+}
+
+TEST(ChunkedQueue, PushFrontAndPushBack) {
+  absl::chunked_queue<int64_t, 4> q;
+  q.push_front(2);
+  q.push_back(3);
+  q.push_front(1);
+  q.push_back(4);
+  q.push_front(0);
+  q.push_back(5);
+  EXPECT_THAT(q, ElementsAre(0, 1, 2, 3, 4, 5));
+  EXPECT_EQ(q.front(), 0);
+  EXPECT_EQ(q.back(), 5);
+
+  q.pop_front();
+  q.push_front(-1);
+  EXPECT_THAT(q, ElementsAre(-1, 1, 2, 3, 4, 5));
+
+  q.clear();
+  EXPECT_TRUE(q.empty());
+  q.push_front(10);
+  EXPECT_THAT(q, ElementsAre(10));
+  EXPECT_EQ(q.front(), 10);
+  EXPECT_EQ(q.back(), 10);
+  q.push_front(9);
+  q.push_back(11);
+  EXPECT_THAT(q, ElementsAre(9, 10, 11));
+}
+
 TEST(ChunkedQueue, Swap) {
   absl::chunked_queue<int64_t> q1;
   absl::chunked_queue<int64_t> q2;
@@ -662,6 +715,28 @@
   EXPECT_EQ(*++i, 2);
 }
 
+// Verifies that `push_front` on a non-empty queue does not invalidate
+// iterators to existing elements, both when prepending into remaining space in
+// the current head block (`1`) and when allocating a new head block (`0`), and
+// that advancing `begin()` across the block boundary reaches the existing
+// iterator `i`.
+TEST(ChunkedQueue, Iterator_PushFrontInvalidate) {
+  absl::chunked_queue<int64_t, 2> q;
+  q.push_front(2);
+  auto i = q.begin();
+  EXPECT_EQ(*i, 2);
+  q.push_front(1);
+  EXPECT_EQ(*i, 2);
+  q.push_front(0);
+  EXPECT_EQ(*i, 2);
+  auto j = q.begin();
+  EXPECT_EQ(*j, 0);
+  EXPECT_EQ(*++j, 1);
+  EXPECT_EQ(*++j, 2);
+  EXPECT_TRUE(j == i);
+  EXPECT_TRUE(++j == q.end());
+}
+
 struct MyType {
   static int constructor_calls;
   static int destructor_calls;
@@ -707,13 +782,56 @@
   absl::chunked_queue<std::unique_ptr<int>> q;
   q.push_back(std::make_unique<int>(10));
   q.push_back(std::make_unique<int>(11));
+  q.push_front(std::make_unique<int>(9));
 
+  EXPECT_EQ(9, *q.front());
+  q.pop_front();
   EXPECT_EQ(10, *q.front());
   q.pop_front();
   EXPECT_EQ(11, *q.front());
   q.pop_front();
 }
 
+// Verifies that `emplace_front` constructs elements in-place at the front of
+// the queue, returns a reference to the newly inserted element, and preserves
+// existing elements at the back.
+TEST(ChunkedQueue, EmplaceFrontUpdatesFrontAndReturnsReference) {
+  absl::chunked_queue<std::pair<int, int>> q;
+  auto& v1 = q.emplace_front(1, 2);
+  EXPECT_THAT(v1, Pair(1, 2));
+  EXPECT_THAT(q.front(), Pair(1, 2));
+  EXPECT_EQ(&v1, &q.front());
+  EXPECT_EQ(&v1, &q.back());
+
+  auto& v2 = q.emplace_front(3, 4);
+  EXPECT_THAT(v2, Pair(3, 4));
+  EXPECT_THAT(q.front(), Pair(3, 4));
+  EXPECT_THAT(q.back(), Pair(1, 2));
+  EXPECT_EQ(&v2, &q.front());
+  EXPECT_EQ(&v1, &q.back());
+}
+
+// Verifies that `emplace_front` forwards move-only arguments to construct the
+// element in-place.
+TEST(ChunkedQueue, EmplaceFrontMoveOnlyType) {
+  absl::chunked_queue<std::pair<std::unique_ptr<int>, std::string>> q;
+  auto& v = q.emplace_front(std::make_unique<int>(11), "val12");
+  EXPECT_THAT(v, Pair(Pointee(11), "val12"));
+  EXPECT_THAT(q.front(), Pair(Pointee(11), "val12"));
+}
+
+TEST(ChunkedQueue, OveralignmentEmplaceFront) {
+  struct alignas(64) Overaligned {
+    int x;
+    int y;
+  };
+  absl::chunked_queue<Overaligned, 1, 8> q;
+  for (int i = 0; i < 10; ++i) {
+    auto& v = q.emplace_front(Overaligned{i, i});
+    EXPECT_EQ(reinterpret_cast<uintptr_t>(&v) % 64, 0);
+  }
+}
+
 TEST(ChunkedQueue, EmplaceBack1) {
   absl::chunked_queue<std::pair<int, int>> q;
   auto& v = q.emplace_back(1, 2);
@@ -865,4 +983,111 @@
 }
 #endif
 
+TEST(ChunkedQueue, StrongExceptionSafetyEmplaceFrontEmptyQueue) {
+#ifndef ABSL_HAVE_EXCEPTIONS
+  GTEST_SKIP() << "Exceptions are not enabled.";
+#else
+  int ctor_count = 0;
+  int dtor_count = 0;
+  absl::chunked_queue<ThrowingCtor> q;
+
+  try {
+    q.emplace_front(5, true, &ctor_count, &dtor_count);
+  } catch (...) {
+  }
+
+  EXPECT_TRUE(q.empty());
+  EXPECT_EQ(ctor_count, 0);
+  EXPECT_EQ(dtor_count, 0);
+#endif
+}
+
+TEST(ChunkedQueue, StrongExceptionSafetyEmplaceFrontNewHeadBlock) {
+#ifndef ABSL_HAVE_EXCEPTIONS
+  GTEST_SKIP() << "Exceptions are not enabled.";
+#else
+  int ctor_count = 0;
+  int dtor_count = 0;
+  absl::chunked_queue<ThrowingCtor> q;
+  q.emplace_front(10, false, &ctor_count, &dtor_count);
+  ASSERT_EQ(q.size(), 1);
+  ASSERT_EQ(ctor_count, 1);
+  ASSERT_EQ(dtor_count, 0);
+
+  // The first block has size 1, so the next emplace_front allocates a new head
+  // block and must delete it if element construction throws.
+  try {
+    q.emplace_front(15, true, &ctor_count, &dtor_count);
+  } catch (...) {
+  }
+
+  EXPECT_EQ(q.size(), 1);
+  EXPECT_EQ(ctor_count, 1);
+  EXPECT_EQ(dtor_count, 0);
+  EXPECT_EQ(q.front().value, 10);
+  EXPECT_EQ(q.back().value, 10);
+
+  q.clear();
+  EXPECT_EQ(q.size(), 0);
+  EXPECT_EQ(dtor_count, 1);
+#endif
+}
+
+TEST(ChunkedQueue, StrongExceptionSafetyEmplaceFrontExistingHeadBlock) {
+#ifndef ABSL_HAVE_EXCEPTIONS
+  GTEST_SKIP() << "Exceptions are not enabled.";
+#else
+  int ctor_count = 0;
+  int dtor_count = 0;
+  absl::chunked_queue<ThrowingCtor, 2> q;
+  q.emplace_front(10, false, &ctor_count, &dtor_count);
+  ASSERT_EQ(q.size(), 1);
+  ASSERT_EQ(ctor_count, 1);
+  ASSERT_EQ(dtor_count, 0);
+
+  // The head block has capacity 2 with 1 element, so the next emplace_front
+  // constructs into the remaining slot in the existing head block.
+  try {
+    q.emplace_front(20, true, &ctor_count, &dtor_count);
+  } catch (...) {
+  }
+
+  EXPECT_EQ(q.size(), 1);
+  EXPECT_EQ(ctor_count, 1);
+  EXPECT_EQ(dtor_count, 0);
+  EXPECT_EQ(q.front().value, 10);
+  EXPECT_EQ(q.back().value, 10);
+
+  q.clear();
+  EXPECT_EQ(q.size(), 0);
+  EXPECT_EQ(dtor_count, 1);
+#endif
+}
+
+TEST(ChunkedQueue, StrongExceptionSafetyEmplaceFrontClearedQueue) {
+#ifndef ABSL_HAVE_EXCEPTIONS
+  GTEST_SKIP() << "Exceptions are not enabled.";
+#else
+  int ctor_count = 0;
+  int dtor_count = 0;
+  absl::chunked_queue<ThrowingCtor> q;
+  q.emplace_front(10, false, &ctor_count, &dtor_count);
+  q.clear();
+  ASSERT_TRUE(q.empty());
+  ASSERT_EQ(ctor_count, 1);
+  ASSERT_EQ(dtor_count, 1);
+
+  // `clear()` leaves one empty block allocated; throwing while constructing
+  // into that retained block must leave the queue empty and valid.
+  try {
+    q.emplace_front(20, true, &ctor_count, &dtor_count);
+  } catch (...) {
+  }
+
+  EXPECT_TRUE(q.empty());
+  EXPECT_EQ(ctor_count, 1);
+  EXPECT_EQ(dtor_count, 1);
+#endif
+}
+
 }  // namespace