Implements `StableBlockList` for `QuicheLinkedHashMap`. `StableBlockList` is a simplified, block-based append-only sequence container designed to provide iterator stability for linked hash map backing stores. This implementation uses a heap-allocated `ControlBlock` containing a list sentinel, and a circular doubly-linked list of active blocks. Empty blocks are unlinked and recycled in a LIFO pool to reduce allocator pressure. Iterators store direct pointers to blocks and element indices, resulting in a compact iterator size of 16 bytes. A `shrink_to_fit()` method is provided to release recycled blocks in the free list. Key optimizations: - Compact iterator can be returned in registers. - Large block size allows amortization of data structure overhead. - Fast traversal: Uses C++20 bitwise intrinsics (`std::countr_zero`, `std::countl_zero`) for constant-time within-block traversal. - Synchronous block recycling: Empty blocks are unlinked in O(1) and cached for reuse. ## Benchmark Results (N = 8192, Optimized Build) ### 1. Raw Container Comparison: `std::list` vs `StableBlockList` #### Small Element Type: `std::pair<int, int>` (8 bytes) | Workload | `std::list` (CPU) | `StableBlockList<16>` (CPU) | Speedup (16) | `StableBlockList<32>` (CPU) | Speedup (32) | | :--- | :--- | :--- | :--- | :--- | :--- | | **Insert Only** | 228.8 us | 180.7 us | **1.27x** | 171.1 us | **1.34x** | | **FIFO (Insert + Erase)** | 299.1 us | 274.5 us | **1.09x** | 263.0 us | **1.14x** | | **Random Erase** | 411.8 us | 284.5 us | **1.45x** | 273.3 us | **1.51x** | | **Traversal** | 14.8 us | 12.4 us | **1.19x** | 12.9 us | **1.14x** | #### Large Element Type: `std::pair<absl::string_view, absl::string_view>` (32 bytes) | Workload | `std::list` (CPU) | `StableBlockList<16>` (CPU) | Speedup (16) | `StableBlockList<32>` (CPU) | Speedup (32) | | :--- | :--- | :--- | :--- | :--- | :--- | | **Insert Only** | 394.6 us | 349.2 us | **1.13x** | 336.6 us | **1.17x** | | **FIFO (Insert + Erase)** | 525.1 us | 498.3 us | **1.05x** | 483.5 us | **1.09x** | | **Random Erase** | 684.3 us | 549.2 us | **1.25x** | 523.2 us | **1.31x** | | **Traversal** | 17.4 us | 17.7 us | 1.02x Slower | 14.4 us | **1.21x** | ### 2. `HttpHeaderBlock` E2E A/B Comparison (Base: `std::list` vs. Exp: `StableBlockList<32>`) | Workload | Base (`std::list`) | Exp (`StableBlockList<32>`) | Speedup / Overhead | | :--- | :--- | :--- | :--- | | **Insert Only** | 1,015.1 us | 998.2 us | **1.02x (Neutral)** | | **FIFO Workload** | 1,633.0 us | 1,646.0 us | **0.99x (Neutral)** | | **Random Erase** | 1,996.0 us | 1,876.0 us | **1.06x (Neutral)** | | **Lookup** | 296.8 us | 322.5 us | 1.09x Slower (8.6% overhead) | | **Clone** | 844.8 us | 827.3 us | **1.02x Faster (2.1% saving)** | | **Traversal** | 34.9 us | 31.5 us | **1.11x (Neutral)** | PiperOrigin-RevId: 963585805
diff --git a/build/source_list.bzl b/build/source_list.bzl index 3aa9288..64dfb01 100644 --- a/build/source_list.bzl +++ b/build/source_list.bzl
@@ -66,6 +66,7 @@ "common/quiche_text_utils.h", "common/quiche_weak_ptr.h", "common/simple_buffer_allocator.h", + "common/stable_block_list.h", "common/structured_headers.h", "common/vectorized_io_utils.h", "common/wire_serialization.h", @@ -1168,6 +1169,7 @@ "common/quiche_text_utils_test.cc", "common/quiche_weak_ptr_test.cc", "common/simple_buffer_allocator_test.cc", + "common/stable_block_list_test.cc", "common/structured_headers_generated_test.cc", "common/structured_headers_test.cc", "common/test_tools/quiche_test_utils_test.cc",
diff --git a/build/source_list.gni b/build/source_list.gni index 553b0a4..bd07125 100644 --- a/build/source_list.gni +++ b/build/source_list.gni
@@ -66,6 +66,7 @@ "src/quiche/common/quiche_text_utils.h", "src/quiche/common/quiche_weak_ptr.h", "src/quiche/common/simple_buffer_allocator.h", + "src/quiche/common/stable_block_list.h", "src/quiche/common/structured_headers.h", "src/quiche/common/vectorized_io_utils.h", "src/quiche/common/wire_serialization.h", @@ -1170,6 +1171,7 @@ "src/quiche/common/quiche_text_utils_test.cc", "src/quiche/common/quiche_weak_ptr_test.cc", "src/quiche/common/simple_buffer_allocator_test.cc", + "src/quiche/common/stable_block_list_test.cc", "src/quiche/common/structured_headers_generated_test.cc", "src/quiche/common/structured_headers_test.cc", "src/quiche/common/test_tools/quiche_test_utils_test.cc",
diff --git a/build/source_list.json b/build/source_list.json index 8e9046a..1212ca4 100644 --- a/build/source_list.json +++ b/build/source_list.json
@@ -65,6 +65,7 @@ "quiche/common/quiche_text_utils.h", "quiche/common/quiche_weak_ptr.h", "quiche/common/simple_buffer_allocator.h", + "quiche/common/stable_block_list.h", "quiche/common/structured_headers.h", "quiche/common/vectorized_io_utils.h", "quiche/common/wire_serialization.h", @@ -1169,6 +1170,7 @@ "quiche/common/quiche_text_utils_test.cc", "quiche/common/quiche_weak_ptr_test.cc", "quiche/common/simple_buffer_allocator_test.cc", + "quiche/common/stable_block_list_test.cc", "quiche/common/structured_headers_generated_test.cc", "quiche/common/structured_headers_test.cc", "quiche/common/test_tools/quiche_test_utils_test.cc",
diff --git a/quiche/common/stable_block_list.h b/quiche/common/stable_block_list.h new file mode 100644 index 0000000..f46646d --- /dev/null +++ b/quiche/common/stable_block_list.h
@@ -0,0 +1,576 @@ +// Copyright (c) 2026 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef QUICHE_COMMON_STABLE_BLOCK_LIST_H_ +#define QUICHE_COMMON_STABLE_BLOCK_LIST_H_ + +#include <algorithm> +#include <array> +#include <bit> +#include <cstddef> +#include <cstdint> +#include <iterator> +#include <memory> +#include <type_traits> +#include <utility> +#include <vector> + +#include "absl/base/macros.h" +#include "absl/base/nullability.h" +#include "quiche/common/platform/api/quiche_export.h" +#include "quiche/common/platform/api/quiche_logging.h" + +namespace quiche { + +// StableBlockList: A block-based append-only sequence container with iterator +// stability. +// +// StableBlockList is designed for use cases where elements are only appended to +// the end or erased from arbitrary positions, such as the backing store of a +// LinkedHashMap. +// +// It provides 100% iterator stability on push_back/emplace_back and erase. +// Iterators to erased elements are invalidated, but all other iterators remain +// valid. +// +// Internally, it manages a doubly-linked list of fixed-capacity blocks. +template <typename T, size_t BlockCapacity = 16, // QUICHE_NO_EXPORT + typename Allocator = std::allocator<T>> // QUICHE_NO_EXPORT +class StableBlockList { // QUICHE_NO_EXPORT + static_assert(BlockCapacity > 0, "BlockCapacity must be greater than 0"); + static_assert(BlockCapacity <= 64, "BlockCapacity cannot exceed 64"); + + private: + // Selects the smallest unsigned integer type that can hold BlockCapacity + // bits. This minimizes block metadata overhead (2B for capacity<=16, 4B for + // capacity<=32, 8B for capacity<=64). + using OccupancyType = std::conditional_t< + BlockCapacity <= 16, uint16_t, + std::conditional_t<BlockCapacity <= 32, uint32_t, uint64_t>>; + + static constexpr int kBitWidth = sizeof(OccupancyType) * 8; + + // --- Bitwise Math & Manipulation Helpers --- + // These map to single-cycle CPU instructions (e.g. tzcnt, lzcnt, bsf, bsr) + // for O(1) operations. + + // Finds the index of the lowest set bit. Returns default_idx if none. + static constexpr int LowestBitIndex(OccupancyType bits, int default_idx) { + return bits != 0 ? std::countr_zero(bits) : default_idx; + } + + // Finds the index of the highest set bit. Returns default_idx if none. + static constexpr int HighestBitIndex(OccupancyType bits, int default_idx) { + return bits != 0 ? (kBitWidth - 1 - std::countl_zero(bits)) : default_idx; + } + + // Clears (zeros out) all bits at indices <= start_idx. + [[nodiscard]] static constexpr OccupancyType ClearLowBits(OccupancyType bits, + int start_idx) { + QUICHE_DCHECK_GE(start_idx, 0); + QUICHE_DCHECK_LE(start_idx, kBitWidth); + if constexpr (kBitWidth < 64) { + // Safe to shift without guard because start_idx <= kBitWidth <= 32. + uint64_t mask = ~((uint64_t{1} << start_idx) - 1); + return static_cast<OccupancyType>(static_cast<uint64_t>(bits) & mask); + } else { + if (start_idx >= 64) return 0; + uint64_t mask = ~((uint64_t{1} << start_idx) - 1); + return static_cast<OccupancyType>(bits & mask); + } + } + + // Clears (zeros out) all bits at indices >= end_idx. + [[nodiscard]] static constexpr OccupancyType ClearHighBits(OccupancyType bits, + int end_idx) { + QUICHE_DCHECK_GE(end_idx, 0); + QUICHE_DCHECK_LE(end_idx, kBitWidth); + if (end_idx <= 0) return 0; + if constexpr (kBitWidth < 64) { + // Safe to shift without guard because end_idx <= kBitWidth <= 32. + uint64_t mask = (uint64_t{1} << end_idx) - 1; + return static_cast<OccupancyType>(static_cast<uint64_t>(bits) & mask); + } else { + if (end_idx >= 64) return bits; + uint64_t mask = (uint64_t{1} << end_idx) - 1; + return static_cast<OccupancyType>(bits & mask); + } + } + + static constexpr bool IsBitSet(OccupancyType bits, int index) { + return (bits & (OccupancyType{1} << index)) != 0; + } + + [[nodiscard]] static constexpr OccupancyType SetBit(OccupancyType bits, + int index) { + return bits | (OccupancyType{1} << index); + } + + [[nodiscard]] static constexpr OccupancyType ClearBit(OccupancyType bits, + int index) { + return bits & ~(OccupancyType{1} << index); + } + + struct Block; + + // Lightweight header for blocks to allow sentinel node in ControlBlock + // without wasting memory for elements. + struct BlockHeader { + BlockHeader* prev = this; // Not used when a block is in the freelist. + BlockHeader* next = this; + OccupancyType occupancy = 0; + }; + + // Fixed-capacity node (block) holding contiguous elements. + struct Block : public BlockHeader { + alignas(T) char data[BlockCapacity * + sizeof(T)]; // Uninitialized storage for elements + + T* ElementAt(size_t index) { return reinterpret_cast<T*>(data) + index; } + const T* ElementAt(size_t index) const { + return reinterpret_cast<const T*>(data) + index; + } + }; + + using BlockAllocator = + typename std::allocator_traits<Allocator>::template rebind_alloc<Block>; + + // ControlBlock holds metadata and sentinel. It is heap-allocated and + // owned via unique_ptr to keep block pointers and iterators stable when the + // list is moved. + struct ControlBlock { + BlockHeader sentinel; // next/prev point to the head/tail + size_t size = 0; // Total number of elements in the list + Block* free_blocks = nullptr; // Singly-linked LIFO pool of recycled blocks + }; + + public: + template <bool is_const> + class IteratorImpl { + public: + using iterator_category = std::bidirectional_iterator_tag; + using value_type = T; + using difference_type = std::ptrdiff_t; + using pointer = typename std::conditional<is_const, const T*, T*>::type; + using reference = typename std::conditional<is_const, const T&, T&>::type; + + IteratorImpl() = default; + + // Iterators reference elements by their block pointer and offset. + IteratorImpl(BlockHeader* block, uint32_t block_index) + : block_(block), block_index_(block_index) {} + + // Allows implicit conversion from iterator to const_iterator. + template <bool was_const = is_const, + typename = typename std::enable_if<was_const>::type> + IteratorImpl(const IteratorImpl<false>& other) + : block_(other.block_), block_index_(other.block_index_) {} + + reference operator*() const { + ABSL_HARDENING_ASSERT(block_ != nullptr); + ABSL_HARDENING_ASSERT(block_->occupancy != 0 && + "Attempted to dereference end()"); + return *static_cast<pointer_to_block>(block_)->ElementAt(block_index_); + } + pointer operator->() const { + ABSL_HARDENING_ASSERT(block_ != nullptr); + ABSL_HARDENING_ASSERT(block_->occupancy != 0 && + "Attempted to dereference end()"); + return static_cast<pointer_to_block>(block_)->ElementAt(block_index_); + } + + IteratorImpl& operator++() { + *this = Next(*this); + return *this; + } + + IteratorImpl operator++(int) { + IteratorImpl tmp = *this; + ++*this; + return tmp; + } + + IteratorImpl& operator--() { + *this = Prev(*this); + return *this; + } + + IteratorImpl operator--(int) { + IteratorImpl tmp = *this; + --*this; + return tmp; + } + + bool operator==(const IteratorImpl& other) const = default; + + private: + using pointer_to_block = + typename std::conditional<is_const, const Block*, Block*>::type; + + BlockHeader* block_ = nullptr; + uint32_t block_index_ = 0; + + friend class StableBlockList; + template <bool> + friend class IteratorImpl; + }; + + using value_type = T; + using size_type = size_t; + using difference_type = std::ptrdiff_t; + using reference = T&; + using const_reference = const T&; + using pointer = T*; + using const_pointer = const T*; + using iterator = IteratorImpl<false>; + using const_iterator = IteratorImpl<true>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + + // Copies are not allowed. + StableBlockList(const StableBlockList&) = delete; + StableBlockList& operator=(const StableBlockList&) = delete; + + // Moves are allowed. + StableBlockList(StableBlockList&& other) noexcept + : allocator_(std::move(other.allocator_)), + control_block_(std::move(other.control_block_)) {} + + StableBlockList& operator=(StableBlockList&& other) noexcept { + if (this != &other) { + this->~StableBlockList(); + new (this) StableBlockList(std::move(other)); + } + return *this; + } + + explicit StableBlockList(const Allocator& alloc = Allocator()) + : allocator_(alloc), control_block_(std::make_unique<ControlBlock>()) {} + + ~StableBlockList() { + if (!control_block_) return; + clear(); + shrink_to_fit(); + } + + bool empty() const { + return control_block_ ? (control_block_->size == 0) : true; + } + size_t size() const { return control_block_ ? control_block_->size : 0; } + + // Standard element accessors. + T& front() { + return const_cast<T&>(const_cast<const StableBlockList*>(this)->front()); + } + const T& front() const { + QUICHE_DCHECK(!empty()); + return *begin(); + } + + T& back() { + return const_cast<T&>(const_cast<const StableBlockList*>(this)->back()); + } + const T& back() const { + QUICHE_DCHECK(!empty()); + return *rbegin(); + } + + // Standard iterator accessors. + iterator begin() { + if (empty()) { + return end(); + } + BlockHeader* head = control_block_->sentinel.next; + return iterator(head, LowestBitIndex(head->occupancy, BlockCapacity)); + } + const_iterator begin() const { + return const_cast<StableBlockList*>(this)->begin(); + } + const_iterator cbegin() const { return begin(); } + + iterator end() { + return iterator(control_block_ ? &control_block_->sentinel : nullptr, 0); + } + const_iterator end() const { + return const_iterator( + control_block_ ? const_cast<BlockHeader*>(&control_block_->sentinel) + : nullptr, + 0); + } + const_iterator cend() const { return end(); } + + reverse_iterator rbegin() { return reverse_iterator(end()); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + const_reverse_iterator crbegin() const { + return const_reverse_iterator(end()); + } + + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + const_reverse_iterator crend() const { + return const_reverse_iterator(begin()); + } + + // Elements may be appended. + void push_back(const T& value) { InsertToEnd(value); } + void push_back(T&& value) { InsertToEnd(std::move(value)); } + + // TODO(birenroy): Remove these restricted insert/emplace methods once + // QuicheLinkedHashMap is updated to use push_back/emplace_back. + iterator insert(const_iterator pos, const T& value) { + QUICHE_DCHECK(pos == end()) + << "StableBlockList only supports insertion at the end"; + return InsertToEnd(value); + } + iterator insert(const_iterator pos, T&& value) { + QUICHE_DCHECK(pos == end()) + << "StableBlockList only supports insertion at the end"; + return InsertToEnd(std::move(value)); + } + + template <typename... Args> + iterator emplace(const_iterator pos, Args&&... args) { + QUICHE_DCHECK(pos == end()) + << "StableBlockList only supports emplace at the end"; + return InsertToEnd(std::forward<Args>(args)...); + } + + // Swaps are efficient, and do not require any copies. + void swap(StableBlockList& other) noexcept { + using std::swap; + swap(control_block_, other.control_block_); + if constexpr (std::allocator_traits< + Allocator>::propagate_on_container_swap::value) { + swap(allocator_, other.allocator_); + } + } + + // Elements may be erased at any position. + iterator erase(const_iterator pos) { + BlockHeader* header = pos.block_; + QUICHE_DCHECK(header != &control_block_->sentinel); + Block* block = static_cast<Block*>(header); + + // Capture the next element before destroying the current one + iterator next_it = Next(iterator(header, pos.block_index_)); + + // Destroy the element and clear its occupancy bit + std::allocator_traits<Allocator>::destroy( + allocator_, block->ElementAt(pos.block_index_)); + block->occupancy = ClearBit(block->occupancy, pos.block_index_); + --control_block_->size; + + // If the block becomes completely empty, unlink and recycle it + if (block->occupancy == 0) { + BlockHeader* prev = block->prev; + BlockHeader* next = block->next; + + prev->next = next; + next->prev = prev; + + DeallocateBlock(block); + } + + // If we erased the last element, next_it will be end() which points to + // sentinel. + return next_it; + } + + iterator erase(const_iterator first, const_iterator last) { + while (first != last && first != end()) { + first = erase(first); + } + return iterator(first.block_, first.block_index_); + } + + // The clear operation removes all elements from the list, but does not free + // the memory of any allocated blocks. These are appended to the freelist. + void clear() { + if (!control_block_) return; + BlockHeader* curr = control_block_->sentinel.next; + while (curr != &control_block_->sentinel) { + Block* block = static_cast<Block*>(curr); + BlockHeader* next = curr->next; + for (size_t i = 0; i < BlockCapacity; ++i) { + if (IsBitSet(block->occupancy, i)) { + std::allocator_traits<Allocator>::destroy(allocator_, + block->ElementAt(i)); + } + } + DeallocateBlock(block); + curr = next; + } + control_block_->sentinel.next = &control_block_->sentinel; + control_block_->sentinel.prev = &control_block_->sentinel; + control_block_->size = 0; + // Note: we keep control_block_->free_blocks for reuse. + } + + // Releases all recycled blocks in the free list to free memory. + // + // Note: This method does not compact elements in active blocks or relocate + // them, as doing so would invalidate iterators and references, violating + // the iterator stability guarantee of StableBlockList. It only releases + // completely empty blocks that have been cached for reuse. + void shrink_to_fit() { + if (!control_block_) return; + BlockAllocator block_alloc(allocator_); + Block* curr = control_block_->free_blocks; + while (curr != nullptr) { + Block* next = static_cast<Block*>(curr->next); + std::allocator_traits<BlockAllocator>::deallocate(block_alloc, curr, 1); + curr = next; + } + control_block_->free_blocks = nullptr; + } + + private: + Block* AllocateBlock() { + BlockAllocator block_alloc(allocator_); + Block* block = nullptr; + if (control_block_->free_blocks != nullptr) { + block = control_block_->free_blocks; + control_block_->free_blocks = static_cast<Block*>(block->next); + } else { + block = std::allocator_traits<BlockAllocator>::allocate(block_alloc, 1); + } + std::allocator_traits<BlockAllocator>::construct(block_alloc, block); + return block; + } + + void DeallocateBlock(Block* block) { + BlockAllocator block_alloc(allocator_); + std::allocator_traits<BlockAllocator>::destroy(block_alloc, block); + + // Link to free blocks LIFO list using 'next' pointer + block->next = control_block_->free_blocks; + control_block_->free_blocks = block; + } + + template <typename It> + static It Next(It it) { + BlockHeader* curr = it.block_; + // Handles default-constructed iterators and end() of moved-from lists. + if (curr == nullptr) { + return it; + } + uint32_t i = it.block_index_; + + // Incrementing end() is undefined behavior. + QUICHE_DCHECK(curr->occupancy != 0) + << "Attempted to increment end() iterator"; + + // Find the next set bit in the current block's occupancy mask after index + // 'i' + OccupancyType bits = ClearLowBits(curr->occupancy, i + 1); + int next_idx = LowestBitIndex(bits, BlockCapacity); + if (next_idx < static_cast<int>(BlockCapacity)) { + return It(curr, next_idx); + } + + // If no more elements in this block, jump to the next block. + // Invariant: empty blocks are immediately unlinked in erase(), so any + // linked next block (if it's not the sentinel) is guaranteed to have + // occupancy > 0. + BlockHeader* next_b = curr->next; + if (next_b->occupancy != 0) { + int first_idx = LowestBitIndex(next_b->occupancy, BlockCapacity); + QUICHE_DCHECK_LT(first_idx, static_cast<int>(BlockCapacity)); + return It(next_b, first_idx); + } + + // Reached sentinel (end()) + return It(next_b, 0); + } + + template <typename It> + static It Prev(It it) { + BlockHeader* curr = it.block_; + if (curr == nullptr) { + return it; + } + uint32_t i = it.block_index_; + + // Find the previous set bit in the current block's occupancy mask before + // index 'i' + OccupancyType bits = ClearHighBits(curr->occupancy, i); + int prev_idx = HighestBitIndex(bits, -1); + if (prev_idx >= 0) { + return It(curr, prev_idx); + } + + // If no previous elements in this block, jump to the previous block. + BlockHeader* prev_b = curr->prev; + if (prev_b->occupancy != 0) { // If not sentinel + int last_idx = HighestBitIndex(prev_b->occupancy, -1); + QUICHE_DCHECK_GE(last_idx, 0); + return It(prev_b, last_idx); + } + + // Reached sentinel (begin() decrement goes to end()) + return It(prev_b, 0); + } + + template <typename... Args> + iterator InsertToEnd(Args&&... args) { + EnsureControlBlock(); + + BlockHeader* sentinel = &control_block_->sentinel; + BlockHeader* tail_header = sentinel->prev; + Block* tail = static_cast<Block*>(tail_header); + + int insert_idx = 0; + bool need_new_block = false; + + if (tail_header == sentinel) { + need_new_block = true; + } else { + int k = HighestBitIndex(tail->occupancy, -1); + if (k < static_cast<int>(BlockCapacity) - 1) { + insert_idx = k + 1; + } else { + need_new_block = true; + } + } + + if (need_new_block) { + Block* new_block = AllocateBlock(); + new_block->prev = tail_header; + new_block->next = sentinel; + tail_header->next = new_block; + sentinel->prev = new_block; + tail = new_block; + insert_idx = 0; + } + + std::allocator_traits<Allocator>::construct( + allocator_, tail->ElementAt(insert_idx), std::forward<Args>(args)...); + tail->occupancy = SetBit(tail->occupancy, insert_idx); + control_block_->size++; + return iterator(tail, insert_idx); + } + + void EnsureControlBlock() { + if (!control_block_) { + control_block_ = std::make_unique<ControlBlock>(); + } + } + + [[no_unique_address]] Allocator allocator_; + absl_nullable std::unique_ptr<ControlBlock> control_block_; +}; + +template <typename T, size_t BlockCapacity, typename Allocator> +void swap(StableBlockList<T, BlockCapacity, Allocator>& lhs, + StableBlockList<T, BlockCapacity, Allocator>& rhs) noexcept { + lhs.swap(rhs); +} + +} // namespace quiche + +#endif // QUICHE_COMMON_STABLE_BLOCK_LIST_H_
diff --git a/quiche/common/stable_block_list_test.cc b/quiche/common/stable_block_list_test.cc new file mode 100644 index 0000000..e1bc942 --- /dev/null +++ b/quiche/common/stable_block_list_test.cc
@@ -0,0 +1,386 @@ +// Copyright (c) 2026 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "quiche/common/stable_block_list.h" + +#include <memory> +#include <vector> + +#include "quiche/common/platform/api/quiche_test.h" + +namespace quiche { +namespace { + +struct AllocStats { + size_t allocs = 0; + size_t deallocs = 0; +}; + +template <typename T> +struct TrackingAllocator { + using value_type = T; + + std::shared_ptr<AllocStats> stats; + + TrackingAllocator() = default; + explicit TrackingAllocator(std::shared_ptr<AllocStats> s) + : stats(std::move(s)) {} + + template <typename U> + TrackingAllocator(const TrackingAllocator<U>& other) : stats(other.stats) {} + + T* allocate(std::size_t n) { + if (stats) stats->allocs++; + return std::allocator<T>().allocate(n); + } + + void deallocate(T* p, std::size_t n) { + if (stats) stats->deallocs++; + std::allocator<T>().deallocate(p, n); + } + + template <typename U> + bool operator==(const TrackingAllocator<U>& other) const { + return stats == other.stats; + } + template <typename U> + bool operator!=(const TrackingAllocator<U>& other) const { + return stats != other.stats; + } +}; + +TEST(StableBlockListTest, BasicOps) { + StableBlockList<int> list; + EXPECT_TRUE(list.empty()); + EXPECT_EQ(list.size(), 0); + + list.push_back(1); + list.push_back(2); + list.push_back(3); + + EXPECT_FALSE(list.empty()); + EXPECT_EQ(list.size(), 3); + EXPECT_EQ(list.front(), 1); + EXPECT_EQ(list.back(), 3); + + StableBlockList<int> list2 = std::move(list); + EXPECT_FALSE(list2.empty()); + EXPECT_EQ(list2.size(), 3); + EXPECT_EQ(list2.front(), 1); + EXPECT_EQ(list2.back(), 3); + + list2.clear(); + EXPECT_TRUE(list2.empty()); + EXPECT_EQ(list2.size(), 0); +} + +TEST(StableBlockListTest, Traversal) { + StableBlockList<int> list; + list.push_back(1); + list.push_back(2); + list.push_back(3); + + auto it = list.begin(); + EXPECT_EQ(*it, 1); + ++it; + EXPECT_EQ(*it, 2); + ++it; + EXPECT_EQ(*it, 3); + ++it; + EXPECT_TRUE(it == list.end()); + + --it; + EXPECT_EQ(*it, 3); + --it; + EXPECT_EQ(*it, 2); + --it; + EXPECT_EQ(*it, 1); + EXPECT_TRUE(it == list.begin()); +} + +TEST(StableBlockListTest, IteratorStabilityOnPushBack) { + StableBlockList<int, 4> + list; // Small capacity to force multi-block allocations + // Fill one chunk (4 elements) + for (int i = 0; i < 4; ++i) { + list.push_back(i * 10); // 0, 10, 20, 30 + } + + // Store iterators + std::vector<StableBlockList<int, 4>::iterator> iters; + for (auto it = list.begin(); it != list.end(); ++it) { + iters.push_back(it); + } + + // Push back more elements to force allocation of a new block + list.push_back(40); + list.push_back(50); + + EXPECT_EQ(list.size(), 6); + + // Verify stored iterators are still valid and point to the same values + EXPECT_EQ(*iters[0], 0); + EXPECT_EQ(*iters[1], 10); + EXPECT_EQ(*iters[2], 20); + EXPECT_EQ(*iters[3], 30); + + // Verify traversal order + std::vector<int> elements; + for (int x : list) { + elements.push_back(x); + } + EXPECT_THAT(elements, ::testing::ElementsAre(0, 10, 20, 30, 40, 50)); +} + +TEST(StableBlockListTest, IteratorStabilityOnErase) { + StableBlockList<int, 4> list; + for (int i = 0; i < 8; ++i) { + list.push_back(i * 10); // 0, 10, 20, 30, 40, 50, 60, 70 + } + + std::vector<StableBlockList<int, 4>::iterator> iters; + for (auto it = list.begin(); it != list.end(); ++it) { + iters.push_back(it); + } + + // Erase 30 (index 3, which is the last element of first block) + auto erase_pos = iters[3]; + auto next_it = list.erase(erase_pos); + EXPECT_EQ(*next_it, 40); + EXPECT_EQ(list.size(), 7); + + // Verify other iterators are still valid + EXPECT_EQ(*iters[0], 0); + EXPECT_EQ(*iters[1], 10); + EXPECT_EQ(*iters[2], 20); + // iters[3] is invalid (erased), we shouldn't dereference it. + EXPECT_EQ(*iters[4], 40); + EXPECT_EQ(*iters[5], 50); + EXPECT_EQ(*iters[6], 60); + EXPECT_EQ(*iters[7], 70); + + std::vector<int> elements; + for (int x : list) { + elements.push_back(x); + } + EXPECT_THAT(elements, ::testing::ElementsAre(0, 10, 20, 40, 50, 60, 70)); +} + +TEST(StableBlockListTest, MoveOnlyType) { + StableBlockList<std::unique_ptr<int>> list; + list.push_back(std::make_unique<int>(1)); + list.push_back(std::make_unique<int>(2)); + + EXPECT_EQ(list.size(), 2); + EXPECT_EQ(*list.front(), 1); + EXPECT_EQ(*list.back(), 2); + + list.push_back(std::make_unique<int>(3)); // [1, 2, 3] + + EXPECT_EQ(list.size(), 3); + auto it = list.begin(); + EXPECT_EQ(**it, 1); + ++it; + EXPECT_EQ(**it, 2); + ++it; + EXPECT_EQ(**it, 3); + + it = list.begin(); + ++it; // points to 2 + list.erase(it); // [1, 3] + EXPECT_EQ(list.size(), 2); + EXPECT_EQ(*list.front(), 1); + EXPECT_EQ(*list.back(), 3); +} + +TEST(StableBlockListTest, MultiBlockPushBackAndBackwardTraversal) { + StableBlockList<int, 8> list; + const int num_elements = 100; + for (int i = 0; i < num_elements; ++i) { + list.push_back(i); + } + EXPECT_EQ(list.size(), num_elements); + EXPECT_EQ(list.front(), 0); + EXPECT_EQ(list.back(), num_elements - 1); + + // Forward traversal across multiple blocks + int expected = 0; + for (int val : list) { + EXPECT_EQ(val, expected++); + } + EXPECT_EQ(expected, num_elements); + + // Backward traversal across multiple blocks + auto it = list.end(); + for (int i = num_elements - 1; i >= 0; --i) { + --it; + EXPECT_EQ(*it, i); + } + EXPECT_TRUE(it == list.begin()); +} + +TEST(StableBlockListTest, SingleBlockReverseIteration) { + StableBlockList<int, 4> list; + list.push_back(1); + list.push_back(2); + + auto it = list.rbegin(); + EXPECT_EQ(*it, 2); + ++it; + EXPECT_EQ(*it, 1); + ++it; + EXPECT_TRUE(it == list.rend()); +} + +TEST(StableBlockListTest, SingleElementReverseIteration) { + StableBlockList<int, 4> list; + list.push_back(1); + + auto it = list.rbegin(); + EXPECT_EQ(*it, 1); + ++it; + EXPECT_TRUE(it == list.rend()); +} + +TEST(StableBlockListTest, EmptyReverseIteration) { + StableBlockList<int, 4> list; + + auto it = list.rbegin(); + EXPECT_TRUE(it == list.rend()); +} + +TEST(StableBlockListTest, EraseLastElementOfMultiBlockList) { + StableBlockList<int, 4> list; + // Push 5 elements. Block capacity is 4. + // Block 0 will have 4 elements (0..3). + // Block 1 will have 1 element (4). + for (int i = 0; i < 5; ++i) { + list.push_back(i); + } + // Now erase the last element (4). + auto it = std::prev(list.end()); + EXPECT_EQ(*it, 4); + list.erase(it); + + // Check size + EXPECT_EQ(list.size(), 4); + // Check back + EXPECT_EQ(list.back(), 3); + + // Verify we can still traverse + int expected = 0; + for (int val : list) { + EXPECT_EQ(val, expected++); + } + EXPECT_EQ(expected, 4); +} + +TEST(StableBlockListTest, BlockDeallocationAndReallocation) { + StableBlockList<int, 2> list; + list.push_back(1); + list.push_back(2); + list.push_back(3); // Allocates 2nd block + + EXPECT_EQ(list.size(), 3); + + auto it = list.begin(); // points to 1 + list.erase(it); // 1 is erased + it = list.begin(); // points to 2 + list.erase(it); // 2 is erased, 1st block becomes empty and is deallocated! + + EXPECT_EQ(list.size(), 1); + EXPECT_EQ(list.front(), 3); + + // Now push back another element, it should go to the 2nd block if it has + // space, or allocate a new block. Since 2nd block has '3' at index 0, it has + // space at index 1. + list.push_back(4); + EXPECT_EQ(list.size(), 2); + EXPECT_EQ(list.back(), 4); + + // Now 2nd block is full (3, 4). Push another to allocate a new block. + list.push_back(5); + EXPECT_EQ(list.size(), 3); + EXPECT_EQ(list.back(), 5); + + std::vector<int> elements; + for (int x : list) { + elements.push_back(x); + } + EXPECT_THAT(elements, ::testing::ElementsAre(3, 4, 5)); +} + +TEST(StableBlockListTest, IteratorBoundaryCases) { + StableBlockList<int> empty_list; + + // 1. Decrementing end() on empty list should return end() (covers line 505) + auto empty_it = empty_list.end(); + --empty_it; + EXPECT_TRUE(empty_it == empty_list.end()); + + // 2. Decrementing a default-constructed iterator should return itself (covers + // line 505) + StableBlockList<int>::iterator default_it; + --default_it; + EXPECT_TRUE(default_it == StableBlockList<int>::iterator()); + + // 3. Decrementing begin() on non-empty list should return end() (covers line + // 530) + StableBlockList<int> list; + list.push_back(10); + auto it = list.begin(); + --it; + EXPECT_TRUE(it == list.end()); +} + +TEST(StableBlockListTest, ShrinkToFitReleasesMemory) { + auto stats = std::make_shared<AllocStats>(); + { + StableBlockList<int, 2, TrackingAllocator<int>> list( + (TrackingAllocator<int>(stats))); + + // Push 2 elements. Capacity is 2, so this allocates 1 block. + list.push_back(1); + list.push_back(2); + EXPECT_EQ(stats->allocs, 1); + EXPECT_EQ(stats->deallocs, 0); + + // Push 3rd element. Allocates 2nd block. + list.push_back(3); + EXPECT_EQ(stats->allocs, 2); + EXPECT_EQ(stats->deallocs, 0); + + // Erase 1st and 2nd elements. 1st block becomes empty and is unlinked. + // It should be moved to the free list, NOT deallocated. + auto it = list.begin(); + list.erase(it); + it = list.begin(); + list.erase(it); + + EXPECT_EQ(stats->allocs, 2); + EXPECT_EQ(stats->deallocs, 0); + + // Call shrink_to_fit(). This should deallocate the block in the free list. + list.shrink_to_fit(); + EXPECT_EQ(stats->allocs, 2); + EXPECT_EQ(stats->deallocs, 1); + + // Push 4th element. Goes to 2nd block (which contains 3 and has space). + // No new allocation. + list.push_back(4); + EXPECT_EQ(stats->allocs, 2); + EXPECT_EQ(stats->deallocs, 1); + + // Push 5th element. 2nd block is full [3, 4], allocates 3rd block. + list.push_back(5); + EXPECT_EQ(stats->allocs, 3); + EXPECT_EQ(stats->deallocs, 1); + } + // Destructor deallocates the remaining active blocks (Block 2 and Block 3). + EXPECT_EQ(stats->allocs, 3); + EXPECT_EQ(stats->deallocs, 3); +} + +} // namespace +} // namespace quiche