Add pop_back() and bidirectional iterator support to absl::chunked_queue. Turn the internal chunked queue blocks into a doubly linked list by tracking previous block pointers. This enables: - Implementing pop_back() to destroy and remove elements from the back of the queue. - Upgrading container iterators from forward iterators to bidirectional iterators with operator-- support. - Adding reverse iterator accessors: rbegin(), rend(), crbegin(), and crend(). PiperOrigin-RevId: 1001017381
diff --git a/absl/container/chunked_queue.h b/absl/container/chunked_queue.h index 54cb6d8..7dba5dc 100644 --- a/absl/container/chunked_queue.h +++ b/absl/container/chunked_queue.h
@@ -40,12 +40,15 @@ // push_back() // emplace_back() // pop_front() +// pop_back() // front() // back() // swap() // clear() // begin(), end() // cbegin(), cend() +// rbegin(), rend() +// crbegin(), crend() // // === ADVANCED USAGE // @@ -156,6 +159,19 @@ *this = iterator_common(block->next()); } + void Decr() { + // If we are at the start of this block, make ptr point to the last + // element of the previous block. Unlike Incr(), which can advance one + // past the last block to form end(), Decr() cannot move before the first + // block (begin()), so a previous block must exist. + if (ptr == block->start()) { + ABSL_ASSERT(block->prev() != nullptr); + block = block->prev(); + ptr = block->limit(); + } + --ptr; + } + void IncrBy(size_t n) { while (n > static_cast<size_t>(block->limit() - ptr)) { n -= static_cast<size_t>(block->limit() - ptr); @@ -172,7 +188,7 @@ template <typename CT> class basic_iterator : public iterator_common { public: - using iterator_category = std::forward_iterator_tag; + using iterator_category = std::bidirectional_iterator_tag; using value_type = typename AllocatorTraits::value_type; using difference_type = typename AllocatorTraits::difference_type; using pointer = std::conditional_t<std::is_const_v<CT>, @@ -200,6 +216,15 @@ ++*this; return t; } + basic_iterator& operator--() { + this->Decr(); + return *this; + } + basic_iterator operator--(int) { + basic_iterator t = *this; + --*this; + return t; + } private: explicit basic_iterator(Block* b) : iterator_common(b) {} @@ -216,6 +241,8 @@ using const_reference = const value_type&; using iterator = basic_iterator<T>; using const_iterator = basic_iterator<const T>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; // Constructs an empty queue. chunked_queue() : chunked_queue(allocator_type()) {} @@ -443,6 +470,11 @@ // REQUIRES: !empty() void pop_front(); + // Removes the last element of the container. + // Invalidates iterators to the removed element and `end()`. + // REQUIRES: !empty() + void pop_back(); + // Returns a reference to the first element in the container. // REQUIRES: !empty() T& front() { @@ -498,6 +530,23 @@ const_iterator cbegin() const { return head_; } const_iterator cend() const { return tail_; } + reverse_iterator rbegin() { return reverse_iterator(end()); } + reverse_iterator rend() { return reverse_iterator(begin()); } + + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + + const_reverse_iterator crbegin() const { + return const_reverse_iterator(cend()); + } + const_reverse_iterator crend() const { + return const_reverse_iterator(cbegin()); + } + // Returns the allocator associated with the container. allocator_type get_allocator() const { return alloc_and_size_.allocator(); } @@ -724,6 +773,7 @@ tail_.ptr = b->limit(); } else if (b != head_.block) { b->set_next(head_.block); + head_.block->set_prev(b); } head_.block = b; head_.ptr = storage; @@ -741,6 +791,7 @@ } else { ABSL_ASSERT(tail_.block); tail_.block->set_next(b); + b->set_prev(tail_.block); } tail_ = iterator(b); } @@ -802,11 +853,43 @@ if (head_.ptr == head_.block->limit()) { Block* n = head_.block->next(); Block::Delete(head_.block, &alloc_and_size_.allocator()); + n->set_prev(nullptr); head_ = iterator(n); } } template <typename T, size_t BLo, size_t BHi, typename Allocator> +inline void chunked_queue<T, BLo, BHi, Allocator>::pop_back() { + absl::base_internal::HardeningAssertNonEmpty(*this); + ABSL_ASSERT(tail_.block); + ABSL_ASSERT(tail_.ptr > tail_.block->start()); + + // Since tail_.ptr points just past the last element, repoint it to the last + // element (past the second-to-last one), and delete it. + --tail_.ptr; + AllocatorTraits::destroy(alloc_and_size_.allocator(), tail_.ptr); + --alloc_and_size_.size; + + if (empty()) { + // Reset head and tail to the start of the (only) block. + ABSL_ASSERT(head_.block == tail_.block); + head_.ptr = tail_.ptr = head_.block->start(); + return; + } + + // If we deleted the only element from the last block, repoint the tail_ to + // the second-to-last block. + if (tail_.ptr == tail_.block->start()) { + Block* prev = tail_.block->prev(); + ABSL_ASSERT(prev != nullptr); + Block::Delete(tail_.block, &alloc_and_size_.allocator()); + prev->set_next(nullptr); + tail_.block = prev; + tail_.ptr = prev->limit(); + } +} + +template <typename T, size_t BLo, size_t BHi, typename Allocator> void chunked_queue<T, BLo, BHi, Allocator>::clear() { // NOTE: As an optimization we leave one block allocated. Block* b = head_.block;
diff --git a/absl/container/chunked_queue_benchmark.cc b/absl/container/chunked_queue_benchmark.cc index 3c031ed..b426895 100644 --- a/absl/container/chunked_queue_benchmark.cc +++ b/absl/container/chunked_queue_benchmark.cc
@@ -232,6 +232,30 @@ BENCHMARK_TEMPLATE(BM_pop_front, ExpChunked<Element>)->Apply(CustomArgs); template <class Q> +void BM_pop_back(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 = MakeQueue<Q>(num_elements); + state.ResumeTiming(); + for (int j = 0; j < num_elements; j++) q.pop_back(); + benchmark::DoNotOptimize(q); + } +} + +// FwdList does not support pop_back. +BENCHMARK_TEMPLATE(BM_pop_back, Deque<int64_t>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_pop_back, List<int64_t>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_pop_back, Chunked<int64_t>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_pop_back, ExpChunked<int64_t>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_pop_back, Deque<Element>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_pop_back, List<Element>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_pop_back, Chunked<Element>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_pop_back, ExpChunked<Element>)->Apply(CustomArgs); + +template <class Q> void BM_clear(benchmark::State& state) { const int64_t num_elements = state.range(0); @@ -283,6 +307,31 @@ BENCHMARK_TEMPLATE(BM_iter, ExpChunked<Element>)->Apply(CustomArgs); template <class Q> +void BM_riter(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 = MakeQueue<Q>(state.max_iterations); + int sum = 0; + state.ResumeTiming(); + for (auto it = q.rbegin(); it != q.rend(); ++it) sum += *it; + benchmark::DoNotOptimize(sum); + } +} + +// FwdList does not support rbegin/rend. +BENCHMARK_TEMPLATE(BM_riter, Deque<int64_t>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_riter, List<int64_t>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_riter, Chunked<int64_t>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_riter, ExpChunked<int64_t>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_riter, Deque<Element>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_riter, List<Element>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_riter, Chunked<Element>)->Apply(CustomArgs); +BENCHMARK_TEMPLATE(BM_riter, ExpChunked<Element>)->Apply(CustomArgs); + +template <class Q> void BM_resize_shrink(benchmark::State& state) { const int64_t num_elements = state.range(0);
diff --git a/absl/container/chunked_queue_test.cc b/absl/container/chunked_queue_test.cc index b4604b6..d98cdfb 100644 --- a/absl/container/chunked_queue_test.cc +++ b/absl/container/chunked_queue_test.cc
@@ -399,6 +399,164 @@ EXPECT_THAT(q, ElementsAre(9, 10, 11)); } +TEST(ChunkedQueue, PushBackAndPopBack) { + absl::chunked_queue<int64_t, 2> q; + EXPECT_TRUE(q.empty()); + EXPECT_EQ(0, q.size()); + + // Pop from a single-element queue then push to it, and vice versa. + q.push_back(1); + EXPECT_THAT(q, ElementsAre(1)); + EXPECT_EQ(q.front(), 1); + EXPECT_EQ(q.back(), 1); + q.pop_back(); + EXPECT_TRUE(q.empty()); + EXPECT_EQ(0, q.size()); + + q.push_back(2); + EXPECT_THAT(q, ElementsAre(2)); + EXPECT_EQ(q.front(), 2); + EXPECT_EQ(q.back(), 2); + + // Fill the first block (size 2), pop one element, then push again. + q.push_back(3); + EXPECT_THAT(q, ElementsAre(2, 3)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2)); + q.push_back(4); + EXPECT_THAT(q, ElementsAre(2, 4)); + + // Push a 3rd element to allocate a new tail block with a single element, + // pop that only element in the tail block, then push to the queue again. + q.push_back(5); + EXPECT_THAT(q, ElementsAre(2, 4, 5)); + EXPECT_EQ(q.front(), 2); + EXPECT_EQ(q.back(), 5); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2, 4)); + EXPECT_EQ(q.front(), 2); + EXPECT_EQ(q.back(), 4); + + q.push_back(6); + EXPECT_THAT(q, ElementsAre(2, 4, 6)); + EXPECT_EQ(q.back(), 6); + + // Fill the second block, pop one element (leaving one in the tail block), + // then push to it again. + q.push_back(7); + EXPECT_THAT(q, ElementsAre(2, 4, 6, 7)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2, 4, 6)); + q.push_back(8); + EXPECT_THAT(q, ElementsAre(2, 4, 6, 8)); + + // Pop all elements across block boundaries back to empty, then push again. + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2, 4, 6)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2, 4)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2)); + q.pop_back(); + EXPECT_TRUE(q.empty()); + EXPECT_EQ(0, q.size()); + + q.push_back(9); + EXPECT_THAT(q, ElementsAre(9)); +} + +TEST(ChunkedQueue, PushFrontAndPopBack) { + absl::chunked_queue<int64_t, 2> q; + EXPECT_TRUE(q.empty()); + EXPECT_EQ(0, q.size()); + + // Push front to an empty queue (places element at the end of the block), + // pop back to empty, then push front / push back again. + q.push_front(1); + EXPECT_THAT(q, ElementsAre(1)); + EXPECT_EQ(q.front(), 1); + EXPECT_EQ(q.back(), 1); + q.pop_back(); + EXPECT_TRUE(q.empty()); + + q.push_front(2); + EXPECT_THAT(q, ElementsAre(2)); + q.pop_back(); + EXPECT_TRUE(q.empty()); + + q.push_back(3); + EXPECT_THAT(q, ElementsAre(3)); + q.pop_back(); + EXPECT_TRUE(q.empty()); + + // Populate multiple blocks via push_front: head block has [_, 2], tail block + // has [3, 4]. + q.push_front(4); + q.push_front(3); + q.push_front(2); + EXPECT_THAT(q, ElementsAre(2, 3, 4)); + + // Pop from the tail block leaving one element [3], then push_back into the + // freed tail slot and pop_back again. + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2, 3)); + EXPECT_EQ(q.back(), 3); + q.push_back(5); + EXPECT_THAT(q, ElementsAre(2, 3, 5)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2, 3)); + + // Pop the only remaining element in the tail block, repointing tail_ to the + // partially filled head block [_, 2]. + q.pop_back(); + EXPECT_THAT(q, ElementsAre(2)); + EXPECT_EQ(q.front(), 2); + EXPECT_EQ(q.back(), 2); + + // Prepend into the remaining front slot of that block ([1, 2]), then pop all. + q.push_front(1); + EXPECT_THAT(q, ElementsAre(1, 2)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(1)); + q.pop_back(); + EXPECT_TRUE(q.empty()); +} + +TEST(ChunkedQueue, MixedPushAndPopBothEnds) { + absl::chunked_queue<int64_t, 3> 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)); + + q.pop_back(); + EXPECT_THAT(q, ElementsAre(0, 1, 2, 3, 4)); + q.pop_front(); + EXPECT_THAT(q, ElementsAre(1, 2, 3, 4)); + + // Alternate push_back and pop_back across block boundary. + q.push_back(40); + q.push_back(50); + q.push_back(60); + EXPECT_THAT(q, ElementsAre(1, 2, 3, 4, 40, 50, 60)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(1, 2, 3, 4, 40, 50)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(1, 2, 3, 4, 40)); + q.pop_back(); + EXPECT_THAT(q, ElementsAre(1, 2, 3, 4)); + q.push_back(400); + EXPECT_THAT(q, ElementsAre(1, 2, 3, 4, 400)); + + while (!q.empty()) { + q.pop_back(); + } + EXPECT_TRUE(q.empty()); +} + TEST(ChunkedQueue, Swap) { absl::chunked_queue<int64_t> q1; absl::chunked_queue<int64_t> q2; @@ -614,20 +772,63 @@ ASSERT_TRUE(copy_iter == q.end()); } +TEST(ChunkedQueue, ReverseIterator) { + absl::chunked_queue<int64_t> q; + EXPECT_TRUE(q.rbegin() == q.rend()); + + q.push_back(1); + absl::chunked_queue<int64_t>::const_reverse_iterator iter = q.rbegin(); + ASSERT_FALSE(iter == q.rend()); + ASSERT_EQ(*iter, 1); + ++iter; + ASSERT_TRUE(iter == q.rend()); + + q.push_back(2); + iter = q.rbegin(); + ASSERT_EQ(*iter, 2); + ++iter; + absl::chunked_queue<int64_t>::const_reverse_iterator copy_iter = iter; + ASSERT_FALSE(copy_iter == q.rend()); + ASSERT_EQ(*copy_iter, 1); + ++copy_iter; + ASSERT_TRUE(copy_iter == q.rend()); + + copy_iter = iter; + ASSERT_FALSE(iter == q.rend()); + ASSERT_EQ(*iter, 1); + ++iter; + ASSERT_TRUE(iter == q.rend()); + + ASSERT_FALSE(copy_iter == q.rend()); + ASSERT_EQ(*copy_iter, 1); + ++copy_iter; + ASSERT_TRUE(copy_iter == q.rend()); +} + TEST(ChunkedQueue, IteratorDefaultConstructor) { using ConstIter = absl::chunked_queue<int64_t>::const_iterator; using Iter = absl::chunked_queue<int64_t>::iterator; + using ConstRevIter = absl::chunked_queue<int64_t>::const_reverse_iterator; + using RevIter = absl::chunked_queue<int64_t>::reverse_iterator; ConstIter const_iter; EXPECT_TRUE(const_iter == ConstIter()); Iter iter; EXPECT_TRUE(iter == Iter()); + ConstRevIter const_rev_iter; + EXPECT_TRUE(const_rev_iter == ConstRevIter()); + RevIter rev_iter; + EXPECT_TRUE(rev_iter == RevIter()); } TEST(ChunkedQueue, IteratorConversion) { using ConstIter = absl::chunked_queue<int64_t>::const_iterator; using Iter = absl::chunked_queue<int64_t>::iterator; + using ConstRevIter = absl::chunked_queue<int64_t>::const_reverse_iterator; + using RevIter = absl::chunked_queue<int64_t>::reverse_iterator; EXPECT_FALSE((std::is_convertible_v<ConstIter, Iter>)); EXPECT_TRUE((std::is_convertible_v<Iter, ConstIter>)); + EXPECT_FALSE((std::is_convertible_v<ConstRevIter, RevIter>)); + EXPECT_TRUE((std::is_convertible_v<RevIter, ConstRevIter>)); absl::chunked_queue<int64_t> q; ConstIter it1 = q.begin(); ConstIter it2 = q.cbegin(); @@ -636,6 +837,14 @@ it2 = q.cend(); it3 = q.end(); EXPECT_FALSE((std::is_assignable_v<Iter, ConstIter>)); + + ConstRevIter rit1 = q.rbegin(); + ConstRevIter rit2 = q.crbegin(); + RevIter rit3 = q.rbegin(); + rit1 = q.rend(); + rit2 = q.crend(); + rit3 = q.rend(); + EXPECT_FALSE((std::is_assignable_v<RevIter, ConstRevIter>)); } struct TestEntry { @@ -662,6 +871,26 @@ EXPECT_TRUE(iter == q.end()); } +TEST(ChunkedQueue, ReverseIterator2) { + absl::chunked_queue<TestEntry> q; + TestEntry e; + e.x = 1; + e.y = 2; + q.push_back(e); + e.x = 3; + e.y = 4; + q.push_back(e); + + absl::chunked_queue<TestEntry>::const_reverse_iterator iter = q.rbegin(); + EXPECT_EQ(iter->x, 3); + EXPECT_EQ(iter->y, 4); + ++iter; + EXPECT_EQ(iter->x, 1); + EXPECT_EQ(iter->y, 2); + ++iter; + EXPECT_TRUE(iter == q.rend()); +} + TEST(ChunkedQueue, Iterator_MultipleBlocks) { absl::chunked_queue<int64_t> q; for (int i = 0; i < 130; ++i) { @@ -688,6 +917,33 @@ EXPECT_TRUE(q.begin() == q.end()); } +TEST(ChunkedQueue, ReverseIterator_MultipleBlocks) { + absl::chunked_queue<int64_t> q; + for (int i = 0; i < 130; ++i) { + absl::chunked_queue<int64_t>::const_reverse_iterator iter = q.rbegin(); + for (int j = i - 1; j >= 0; --j) { + ASSERT_FALSE(iter == q.rend()); + EXPECT_EQ(*iter, j); + ++iter; + } + ASSERT_TRUE(iter == q.rend()); + q.push_back(i); + } + + for (int i = 129; i >= 0; --i) { + absl::chunked_queue<int64_t>::const_reverse_iterator iter = q.rbegin(); + for (int j = i; j >= 0; --j) { + ASSERT_FALSE(iter == q.rend()); + EXPECT_EQ(*iter, j); + ++iter; + } + ASSERT_TRUE(iter == q.rend()); + q.pop_back(); + } + EXPECT_TRUE(q.empty()); + EXPECT_TRUE(q.rbegin() == q.rend()); +} + TEST(ChunkedQueue, Iterator_PopFrontInvalidate) { absl::chunked_queue<int64_t> q; for (int i = 0; i < 130; ++i) { @@ -737,6 +993,83 @@ EXPECT_TRUE(++j == q.end()); } +// Verifies that `pop_back` only invalidates iterators to the removed element +// and `end()`, leaving an iterator that was decremented to the preceding +// element valid across multiple blocks. +TEST(ChunkedQueue, Iterator_PopBackInvalidate) { + absl::chunked_queue<int64_t> q; + for (int i = 0; i < 130; ++i) { + q.push_back(i); + } + + auto iter = --q.end(); + for (int i = 129; i > 0; --i) { + auto curr = iter--; + ASSERT_NE(curr, q.end()); + EXPECT_EQ(*curr, i); + q.pop_back(); + } + ASSERT_EQ(iter, q.begin()); + EXPECT_EQ(*iter, 0); + q.pop_back(); + ASSERT_TRUE(q.empty()); +} + +TEST(ChunkedQueue, BidirectionalAndReverseIterator) { + absl::chunked_queue<int64_t, 3> q; + EXPECT_EQ(q.rbegin(), q.rend()); + EXPECT_EQ(q.crbegin(), q.crend()); + + // Test decrementing from `end()` to `begin()` in a single-block queue (where + // `block->prev() == nullptr` and `begin()` is at `block->start()`). + { + absl::chunked_queue<int64_t, 4> single_block_q = {10, 20, 30}; + auto it = single_block_q.end(); + --it; + EXPECT_EQ(*it, 30); + EXPECT_EQ(*it--, 30); + EXPECT_EQ(*it, 20); + --it; + EXPECT_EQ(*it, 10); + EXPECT_EQ(it, single_block_q.begin()); + } + + // Populate from both front and back across multiple blocks. + for (int i = 4; i >= 0; --i) { + q.push_front(i); + } + for (int i = 5; i < 10; ++i) { + q.push_back(i); + } + + // Test decrementing from `end()` to `begin()` via `--it`. + auto it = q.end(); + for (int expected = 9; expected >= 0; --expected) { + ASSERT_NE(it, q.begin()); + --it; + EXPECT_EQ(*it, expected); + } + EXPECT_EQ(it, q.begin()); + + // Test decrementing from `end()` to `begin()` via `it--`. + it = q.end(); + for (int expected = 9; expected >= 0; --expected) { + ASSERT_NE(it, q.begin()); + auto prev_it = it--; + EXPECT_EQ(prev_it, std::next(it)); + EXPECT_EQ(*it, expected); + } + EXPECT_EQ(it, q.begin()); + + // Test `rbegin()` / `rend()` and `crbegin()` / `crend()`. + std::vector<int64_t> rev(q.rbegin(), q.rend()); + EXPECT_THAT(rev, ElementsAre(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)); + + const auto& cq = q; + std::vector<int64_t> crev(cq.crbegin(), cq.crend()); + EXPECT_THAT(crev, ElementsAre(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)); +} + struct MyType { static int constructor_calls; static int destructor_calls; @@ -766,7 +1099,7 @@ } if (i % 10 == 0) { q.clear(); - } else { + } else if (i % 2 == 0) { for (int j = 0; j < i; j++) { EXPECT_EQ(q.front().val, j); q.pop_front(); @@ -778,6 +1111,29 @@ } } +TEST(ChunkedQueue, ConstructorDestructorCallsPopBack) { + for (int i = 0; i < 100; i++) { + std::vector<MyType> vals; + for (int j = 0; j < i; j++) { + vals.push_back(MyType(j)); + } + MyType::constructor_calls = 0; + MyType::destructor_calls = 0; + { + absl::chunked_queue<MyType> q; + for (int j = 0; j < i; j++) { + q.push_back(vals[j]); + } + for (int j = i - 1; j >= 0; j--) { + EXPECT_EQ(q.back().val, j); + q.pop_back(); + } + } + EXPECT_EQ(MyType::constructor_calls, i); + EXPECT_EQ(MyType::destructor_calls, i); + } +} + TEST(ChunkedQueue, MoveObjects) { absl::chunked_queue<std::unique_ptr<int>> q; q.push_back(std::make_unique<int>(10)); @@ -790,6 +1146,17 @@ q.pop_front(); EXPECT_EQ(11, *q.front()); q.pop_front(); + + 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(11, *q.back()); + q.pop_back(); + EXPECT_EQ(10, *q.back()); + q.pop_back(); + EXPECT_EQ(9, *q.back()); + q.pop_back(); } // Verifies that `emplace_front` constructs elements in-place at the front of @@ -881,6 +1248,7 @@ }; struct MockBlock { void* next; + void* prev; void* limit; }; using TestQueueType = absl::chunked_queue<int64_t, 1, 16>; @@ -924,6 +1292,7 @@ EXPECT_DEATH_IF_SUPPORTED(q.front(), ""); EXPECT_DEATH_IF_SUPPORTED(q.back(), ""); EXPECT_DEATH_IF_SUPPORTED(q.pop_front(), ""); + EXPECT_DEATH_IF_SUPPORTED(q.pop_back(), ""); const absl::chunked_queue<int> cq; EXPECT_DEATH_IF_SUPPORTED(cq.front(), "");
diff --git a/absl/container/internal/chunked_queue.h b/absl/container/internal/chunked_queue.h index c3718ac..0c236c1 100644 --- a/absl/container/internal/chunked_queue.h +++ b/absl/container/internal/chunked_queue.h
@@ -35,9 +35,9 @@ ABSL_NAMESPACE_BEGIN namespace container_internal { -// ChunkedQueueBlock defines a node in a forward list of uninitialized storage -// of size T's. The user is responsible for constructing and destroying T's in -// said storage. +// ChunkedQueueBlock defines a node in a doubly-linked list of uninitialized +// storage of size T's. The user is responsible for constructing and destroying +// T's in said storage. // // ChunkedQueueBlock::New(size) returns said node, with at least size_hint T's // of uninitialized storage. @@ -54,7 +54,7 @@ // the New() and Delete() methods. (This notionally-private constructor is // public only to allow access from allocator types used by New().) explicit ChunkedQueueBlock(size_t size) - : next_(nullptr), limit_(start() + size) {} + : next_(nullptr), prev_(nullptr), limit_(start() + size) {} // Must be deleted by ChunkedQueueBlock::Delete. static ChunkedQueueBlock* New(size_t size_hint, Allocator* alloc) { // NOLINT @@ -100,6 +100,8 @@ ChunkedQueueBlock* next() const { return next_; } void set_next(ChunkedQueueBlock* next) { next_ = next; } + ChunkedQueueBlock* prev() const { return prev_; } + void set_prev(ChunkedQueueBlock* prev) { prev_ = prev; } T* start() { return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(this) + start_offset()); @@ -163,6 +165,7 @@ } ChunkedQueueBlock* next_; + ChunkedQueueBlock* prev_; T* limit_; };