Deprecates `--gfe2_reloadable_flag_quiche_linked_hash_map_use_stable_block_list`. PiperOrigin-RevId: 994669365
diff --git a/quiche/common/quiche_feature_flags_list.h b/quiche/common/quiche_feature_flags_list.h index fe4de6c..7f950d8 100755 --- a/quiche/common/quiche_feature_flags_list.h +++ b/quiche/common/quiche_feature_flags_list.h
@@ -66,7 +66,6 @@ QUICHE_FLAG(bool, quiche_reloadable_flag_quic_testonly_default_false, false, false, "A testonly reloadable flag that will always default to false.") QUICHE_FLAG(bool, quiche_reloadable_flag_quic_testonly_default_true, true, true, "A testonly reloadable flag that will always default to true.") QUICHE_FLAG(bool, quiche_reloadable_flag_quic_use_received_client_addresses_cache, true, true, "If true, use a LRU cache to record client addresses of packets received on server's original address.") -QUICHE_FLAG(bool, quiche_reloadable_flag_quiche_linked_hash_map_use_stable_block_list, true, true, "If true, use StableBlockList in QuicheLinkedHashMap.") QUICHE_FLAG(bool, quiche_restart_flag_quic_client_cert_support, false, true, "If true, enables dynamic client certs in QUIC.") QUICHE_FLAG(bool, quiche_restart_flag_quic_dispatcher_close_connection_on_invalid_ack, false, false, "An invalid ack is an ack that the peer sent for a packet that was not sent by the dispatcher. If true, the dispatcher will close the connection if it receives an invalid ack.") QUICHE_FLAG(bool, quiche_restart_flag_quic_support_release_time_for_gso, false, false, "If true, QuicGsoBatchWriter will support release time if it is available and the process has the permission to do so.")
diff --git a/quiche/common/quiche_linked_hash_map.h b/quiche/common/quiche_linked_hash_map.h index ddd328f..30b92b2 100644 --- a/quiche/common/quiche_linked_hash_map.h +++ b/quiche/common/quiche_linked_hash_map.h
@@ -17,17 +17,13 @@ #define QUICHE_COMMON_QUICHE_LINKED_HASH_MAP_H_ #include <functional> -#include <list> #include <tuple> #include <type_traits> #include <utility> -#include <variant> #include "absl/container/flat_hash_map.h" #include "absl/hash/hash.h" #include "quiche/common/platform/api/quiche_export.h" -#include "quiche/common/platform/api/quiche_flag_utils.h" -#include "quiche/common/platform/api/quiche_flags.h" #include "quiche/common/platform/api/quiche_logging.h" #include "quiche/common/stable_block_list.h" @@ -48,132 +44,21 @@ size_t BlockSize = 16> // QUICHE_NO_EXPORT class QuicheLinkedHashMap { // QUICHE_NO_EXPORT private: - using StdList = std::list<std::pair<Key, Value>>; - using BlockList = quiche::StableBlockList<std::pair<Key, Value>, BlockSize>; - using ListType = std::variant<StdList, BlockList>; + using ListType = quiche::StableBlockList<std::pair<Key, Value>, BlockSize>; + using MapType = + absl::flat_hash_map<Key, typename ListType::iterator, Hash, Eq>; public: - class const_iterator; + using iterator = typename ListType::iterator; + using reverse_iterator = typename ListType::reverse_iterator; + using const_iterator = typename ListType::const_iterator; + using const_reverse_iterator = typename ListType::const_reverse_iterator; + using key_type = typename MapType::key_type; + using value_type = typename ListType::value_type; + using size_type = typename ListType::size_type; - class iterator { - public: - using iterator_category = std::bidirectional_iterator_tag; - using value_type = std::pair<Key, Value>; - using difference_type = std::ptrdiff_t; - using pointer = value_type*; - using reference = value_type&; - - iterator() = default; - iterator(typename StdList::iterator it) : it_(it) {} - iterator(typename BlockList::iterator it) : it_(it) {} - - reference operator*() const { - return std::visit([](auto&& it) -> reference { return *it; }, it_); - } - pointer operator->() const { - return std::visit([](auto&& it) -> pointer { return &*it; }, it_); - } - iterator& operator++() { - std::visit([](auto&& it) { ++it; }, it_); - return *this; - } - iterator operator++(int) { - iterator tmp = *this; - ++(*this); - return tmp; - } - iterator& operator--() { - std::visit([](auto&& it) { --it; }, it_); - return *this; - } - iterator operator--(int) { - iterator tmp = *this; - --(*this); - return tmp; - } - bool operator==(const iterator& other) const { return it_ == other.it_; } - bool operator!=(const iterator& other) const { return !(*this == other); } - - private: - std::variant<typename StdList::iterator, typename BlockList::iterator> it_; - friend class QuicheLinkedHashMap; - friend class const_iterator; - }; - - class const_iterator { - public: - using iterator_category = std::bidirectional_iterator_tag; - using value_type = std::pair<Key, Value>; - using difference_type = std::ptrdiff_t; - using pointer = const value_type*; - using reference = const value_type&; - - const_iterator() = default; - const_iterator(typename StdList::const_iterator it) : it_(it) {} - const_iterator(typename BlockList::const_iterator it) : it_(it) {} - const_iterator(const iterator& other) { - std::visit([this](auto&& it) { it_ = it; }, other.it_); - } - - reference operator*() const { - return std::visit([](auto&& it) -> reference { return *it; }, it_); - } - pointer operator->() const { - return std::visit([](auto&& it) -> pointer { return &*it; }, it_); - } - const_iterator& operator++() { - std::visit([](auto&& it) { ++it; }, it_); - return *this; - } - const_iterator operator++(int) { - const_iterator tmp = *this; - ++(*this); - return tmp; - } - const_iterator& operator--() { - std::visit([](auto&& it) { --it; }, it_); - return *this; - } - const_iterator operator--(int) { - const_iterator tmp = *this; - --(*this); - return tmp; - } - bool operator==(const const_iterator& other) const { - return it_ == other.it_; - } - bool operator!=(const const_iterator& other) const { - return !(*this == other); - } - - private: - std::variant<typename StdList::const_iterator, - typename BlockList::const_iterator> - it_; - friend class QuicheLinkedHashMap; - }; - - using reverse_iterator = std::reverse_iterator<iterator>; - using const_reverse_iterator = std::reverse_iterator<const_iterator>; - using key_type = Key; - using value_type = std::pair<Key, Value>; - using size_type = size_t; - - QuicheLinkedHashMap() { - if (GetQuicheReloadableFlag(quiche_linked_hash_map_use_stable_block_list)) { - list_.template emplace<BlockList>(); - QUICHE_RELOADABLE_FLAG_COUNT( - quiche_linked_hash_map_use_stable_block_list); - } - } - - explicit QuicheLinkedHashMap(size_type bucket_count) : map_(bucket_count) { - if (GetQuicheReloadableFlag(quiche_linked_hash_map_use_stable_block_list)) { - list_.template emplace<BlockList>(); - QUICHE_RELOADABLE_FLAG_COUNT( - quiche_linked_hash_map_use_stable_block_list); - } - } + QuicheLinkedHashMap() = default; + explicit QuicheLinkedHashMap(size_type bucket_count) : map_(bucket_count) {} QuicheLinkedHashMap(const QuicheLinkedHashMap& other) = delete; QuicheLinkedHashMap& operator=(const QuicheLinkedHashMap& other) = delete; @@ -182,71 +67,44 @@ // Returns an iterator to the first (insertion-ordered) element. Like a map, // this can be dereferenced to a pair<Key, Value>. - iterator begin() { - return std::visit([](auto& list) -> iterator { return list.begin(); }, - list_); - } - const_iterator begin() const { - return std::visit([](auto& list) -> const_iterator { return list.begin(); }, - list_); - } + iterator begin() { return list_.begin(); } + const_iterator begin() const { return list_.begin(); } // Returns an iterator beyond the last element. - iterator end() { - return std::visit([](auto& list) -> iterator { return list.end(); }, list_); - } - const_iterator end() const { - return std::visit([](auto& list) -> const_iterator { return list.end(); }, - list_); - } + iterator end() { return list_.end(); } + const_iterator end() const { return list_.end(); } // Returns an iterator to the last (insertion-ordered) element. Like a map, // this can be dereferenced to a pair<Key, Value>. - reverse_iterator rbegin() { return reverse_iterator(end()); } - const_reverse_iterator rbegin() const { - return const_reverse_iterator(end()); - } + reverse_iterator rbegin() { return list_.rbegin(); } + const_reverse_iterator rbegin() const { return list_.rbegin(); } // Returns an iterator beyond the first element. - reverse_iterator rend() { return reverse_iterator(begin()); } - const_reverse_iterator rend() const { - return const_reverse_iterator(begin()); - } + reverse_iterator rend() { return list_.rend(); } + const_reverse_iterator rend() const { return list_.rend(); } // Front and back accessors common to many stl containers. // Returns the earliest-inserted element - const value_type& front() const { - return std::visit( - [](auto& list) -> const value_type& { return list.front(); }, list_); - } + const value_type& front() const { return list_.front(); } + // Returns the earliest-inserted element. - value_type& front() { - return std::visit([](auto& list) -> value_type& { return list.front(); }, - list_); - } + value_type& front() { return list_.front(); } // Returns the most-recently-inserted element. - const value_type& back() const { - return std::visit( - [](auto& list) -> const value_type& { return list.back(); }, list_); - } + const value_type& back() const { return list_.back(); } + // Returns the most-recently-inserted element. - value_type& back() { - return std::visit([](auto& list) -> value_type& { return list.back(); }, - list_); - } + value_type& back() { return list_.back(); } // Clears the map of all values. void clear() { map_.clear(); - std::visit([](auto& list) { list.clear(); }, list_); + list_.clear(); } // Returns true iff the map is empty. - bool empty() const { - return std::visit([](auto& list) { return list.empty(); }, list_); - } + bool empty() const { return list_.empty(); } // Removes the first element from the list. void pop_front() { erase(begin()); } @@ -259,12 +117,7 @@ return 0; } - if (auto* list = std::get_if<BlockList>(&list_)) { - list->erase(std::get<typename BlockList::iterator>(found->second.it_)); - } else { - std::get<StdList>(list_).erase( - std::get<typename StdList::iterator>(found->second.it_)); - } + list_.erase(found->second); map_.erase(found); return 1; @@ -282,12 +135,7 @@ "invalid."; map_.erase(found); - if (auto* list = std::get_if<BlockList>(&list_)) { - return list->erase(std::get<typename BlockList::iterator>(position.it_)); - } else { - return std::get<StdList>(list_).erase( - std::get<typename StdList::iterator>(position.it_)); - } + return list_.erase(position); } // Erases all the items in the range [first, last). Returns an iterator that @@ -316,7 +164,7 @@ if (found == map_.end()) { return end(); } - return const_iterator(found->second); + return found->second; } bool contains(const Key& key) const { return find(key) != end(); } @@ -370,11 +218,7 @@ } // Otherwise, insert into the list, and set value in map. - iterator list_iter = std::visit( - [&pair](auto& list) -> iterator { - return iterator(list.insert(list.end(), std::forward<U>(pair))); - }, - list_); + auto list_iter = list_.insert(list_.end(), std::forward<U>(pair)); map_iter->second = list_iter; return {list_iter, true}; @@ -388,24 +232,20 @@ return {insert_result.first->second, false}; } - iterator list_iter = std::visit( - [&insert_result, &args...](auto& list) -> iterator { - return iterator( - list.emplace(list.end(), std::piecewise_construct, - std::forward_as_tuple(insert_result.first->first), - std::forward_as_tuple(std::forward<Args>(args)...))); - }, - list_); + auto list_iter = + list_.emplace(list_.end(), std::piecewise_construct, + std::forward_as_tuple(insert_result.first->first), + std::forward_as_tuple(std::forward<Args>(args)...)); insert_result.first->second = list_iter; return {list_iter, true}; } - // The list component, used for maintaining insertion order - ListType list_; - using MapType = absl::flat_hash_map<Key, iterator, Hash, Eq>; // The map component, used for speedy lookups MapType map_; + + // The list component, used for maintaining insertion order + ListType list_; }; } // namespace quiche
diff --git a/quiche/common/quiche_linked_hash_map_test.cc b/quiche/common/quiche_linked_hash_map_test.cc index a84c3d7..21d23ba 100644 --- a/quiche/common/quiche_linked_hash_map_test.cc +++ b/quiche/common/quiche_linked_hash_map_test.cc
@@ -11,7 +11,6 @@ #include <tuple> #include <utility> -#include "quiche/common/platform/api/quiche_flags.h" #include "quiche/common/platform/api/quiche_test.h" using testing::ElementsAre; @@ -22,19 +21,8 @@ namespace quiche { namespace test { -class QuicheLinkedHashMapTest : public QuicheTestWithParam<bool> { - protected: - void SetUp() override { - SetQuicheReloadableFlag(quiche_linked_hash_map_use_stable_block_list, - GetParam()); - } -}; - -INSTANTIATE_TEST_SUITE_P(QuicheLinkedHashMapTests, QuicheLinkedHashMapTest, - ::testing::Bool()); - // Tests that move constructor works. -TEST_P(QuicheLinkedHashMapTest, Move) { +TEST(LinkedHashMapTest, Move) { // Use unique_ptr as an example of a non-copyable type. QuicheLinkedHashMap<int, std::unique_ptr<int>> m; m[2] = std::make_unique<int>(12); @@ -44,7 +32,7 @@ UnorderedElementsAre(Pair(2, Pointee(12)), Pair(3, Pointee(13)))); } -TEST_P(QuicheLinkedHashMapTest, ConstructorWithBucketCount) { +TEST(LinkedHashMapTest, ConstructorWithBucketCount) { QuicheLinkedHashMap<int, int> m(100); EXPECT_EQ(0u, m.size()); EXPECT_TRUE(m.empty()); @@ -56,7 +44,7 @@ EXPECT_EQ(2u, m.size()); } -TEST_P(QuicheLinkedHashMapTest, CanTryEmplaceMoveOnly) { +TEST(LinkedHashMapTest, CanTryEmplaceMoveOnly) { QuicheLinkedHashMap<int, std::unique_ptr<int>> m; struct Data { int k, v; @@ -80,7 +68,7 @@ int x; }; -TEST_P(QuicheLinkedHashMapTest, CanTryEmplaceNoMoveNoCopy) { +TEST(LinkedHashMapTest, CanTryEmplaceNoMoveNoCopy) { QuicheLinkedHashMap<int, NoCopy> m; struct Data { int k, v; @@ -95,7 +83,7 @@ EXPECT_EQ(234, found->second.x); } -TEST_P(QuicheLinkedHashMapTest, TryEmplaceRvalueKey) { +TEST(LinkedHashMapTest, TryEmplaceRvalueKey) { QuicheLinkedHashMap<std::string, int> m; std::string key = "hello"; auto result = m.try_emplace(std::move(key), 42); @@ -105,7 +93,7 @@ EXPECT_EQ(m.begin()->first, "hello"); } -TEST_P(QuicheLinkedHashMapTest, ConstKeys) { +TEST(LinkedHashMapTest, ConstKeys) { QuicheLinkedHashMap<int, int> m; m.insert(std::make_pair(1, 2)); // Test that keys are const in iteration. @@ -114,7 +102,7 @@ } // Tests that iteration from begin() to end() works -TEST_P(QuicheLinkedHashMapTest, Iteration) { +TEST(LinkedHashMapTest, Iteration) { QuicheLinkedHashMap<int, int> m; EXPECT_TRUE(m.begin() == m.end()); @@ -143,7 +131,7 @@ } // Tests that reverse iteration from rbegin() to rend() works -TEST_P(QuicheLinkedHashMapTest, ReverseIteration) { +TEST(LinkedHashMapTest, ReverseIteration) { QuicheLinkedHashMap<int, int> m; EXPECT_TRUE(m.rbegin() == m.rend()); @@ -172,7 +160,7 @@ } // Tests that clear() works -TEST_P(QuicheLinkedHashMapTest, Clear) { +TEST(LinkedHashMapTest, Clear) { QuicheLinkedHashMap<int, int> m; m.insert(std::make_pair(2, 12)); m.insert(std::make_pair(1, 11)); @@ -190,7 +178,7 @@ } // Tests that size() works. -TEST_P(QuicheLinkedHashMapTest, Size) { +TEST(LinkedHashMapTest, Size) { QuicheLinkedHashMap<int, int> m; EXPECT_EQ(0u, m.size()); m.insert(std::make_pair(2, 12)); @@ -204,7 +192,7 @@ } // Tests empty() -TEST_P(QuicheLinkedHashMapTest, Empty) { +TEST(LinkedHashMapTest, Empty) { QuicheLinkedHashMap<int, int> m; ASSERT_TRUE(m.empty()); m.insert(std::make_pair(2, 12)); @@ -213,7 +201,7 @@ ASSERT_TRUE(m.empty()); } -TEST_P(QuicheLinkedHashMapTest, Erase) { +TEST(LinkedHashMapTest, Erase) { QuicheLinkedHashMap<int, int> m; ASSERT_EQ(0u, m.size()); EXPECT_EQ(0u, m.erase(2)); // Nothing to erase yet @@ -227,7 +215,7 @@ EXPECT_EQ(0u, m.size()); } -TEST_P(QuicheLinkedHashMapTest, Erase2) { +TEST(LinkedHashMapTest, Erase2) { QuicheLinkedHashMap<int, int> m; ASSERT_EQ(0u, m.size()); EXPECT_EQ(0u, m.erase(2)); // Nothing to erase yet @@ -266,7 +254,7 @@ } // Test that erase(iter,iter) and erase(iter) compile and work. -TEST_P(QuicheLinkedHashMapTest, Erase3) { +TEST(LinkedHashMapTest, Erase3) { QuicheLinkedHashMap<int, int> m; m.insert(std::make_pair(1, 11)); @@ -301,7 +289,7 @@ ASSERT_TRUE(it == m.end()); } -TEST_P(QuicheLinkedHashMapTest, Insertion) { +TEST(LinkedHashMapTest, Insertion) { QuicheLinkedHashMap<int, int> m; ASSERT_EQ(0u, m.size()); std::pair<QuicheLinkedHashMap<int, int>::iterator, bool> result; @@ -335,7 +323,7 @@ static std::pair<int, int> Pair(int i, int j) { return {i, j}; } // Test front accessors. -TEST_P(QuicheLinkedHashMapTest, Front) { +TEST(LinkedHashMapTest, Front) { QuicheLinkedHashMap<int, int> m; m.insert(std::make_pair(2, 12)); @@ -354,7 +342,7 @@ EXPECT_TRUE(m.empty()); } -TEST_P(QuicheLinkedHashMapTest, Find) { +TEST(LinkedHashMapTest, Find) { QuicheLinkedHashMap<int, int> m; EXPECT_TRUE(m.end() == m.find(1)) @@ -383,7 +371,7 @@ << "We shouldn't find anything in a map that we've cleared."; } -TEST_P(QuicheLinkedHashMapTest, Contains) { +TEST(LinkedHashMapTest, Contains) { QuicheLinkedHashMap<int, int> m; EXPECT_FALSE(m.contains(1)) << "An empty map shouldn't contain anything."; @@ -401,7 +389,7 @@ << "A map that we've cleared shouldn't contain anything."; } -TEST_P(QuicheLinkedHashMapTest, Swap) { +TEST(LinkedHashMapTest, Swap) { QuicheLinkedHashMap<int, int> m1; QuicheLinkedHashMap<int, int> m2; m1.insert(std::make_pair(1, 1)); @@ -414,7 +402,7 @@ ASSERT_EQ(2u, m2.size()); } -TEST_P(QuicheLinkedHashMapTest, CustomHashAndEquality) { +TEST(LinkedHashMapTest, CustomHashAndEquality) { struct CustomIntHash { size_t operator()(int x) const { return x; } }; @@ -424,7 +412,7 @@ EXPECT_EQ(1, m[1]); } -TEST_P(QuicheLinkedHashMapTest, CustomBlockSize) { +TEST(LinkedHashMapTest, CustomBlockSize) { // Use a small block size (2) to force multiple blocks. QuicheLinkedHashMap<int, int, absl::Hash<int>, std::equal_to<int>, 2> m; m.insert(std::make_pair(1, 10));