Bring SpdyIntrusiveList back to life as QuicheIntrusiveList. I need it for the QuicBufferedPacketStore change in cl/650350765. PiperOrigin-RevId: 651457521
diff --git a/build/source_list.bzl b/build/source_list.bzl index d65346b..c93905d 100644 --- a/build/source_list.bzl +++ b/build/source_list.bzl
@@ -47,6 +47,7 @@ "common/quiche_data_writer.h", "common/quiche_endian.h", "common/quiche_feature_flags_list.h", + "common/quiche_intrusive_list.h", "common/quiche_ip_address.h", "common/quiche_ip_address_family.h", "common/quiche_linked_hash_map.h", @@ -1094,6 +1095,7 @@ "common/quiche_data_reader_test.cc", "common/quiche_data_writer_test.cc", "common/quiche_endian_test.cc", + "common/quiche_intrusive_list_test.cc", "common/quiche_ip_address_test.cc", "common/quiche_linked_hash_map_test.cc", "common/quiche_mem_slice_storage_test.cc",
diff --git a/build/source_list.gni b/build/source_list.gni index 1692b9a..634b199 100644 --- a/build/source_list.gni +++ b/build/source_list.gni
@@ -47,6 +47,7 @@ "src/quiche/common/quiche_data_writer.h", "src/quiche/common/quiche_endian.h", "src/quiche/common/quiche_feature_flags_list.h", + "src/quiche/common/quiche_intrusive_list.h", "src/quiche/common/quiche_ip_address.h", "src/quiche/common/quiche_ip_address_family.h", "src/quiche/common/quiche_linked_hash_map.h", @@ -1095,6 +1096,7 @@ "src/quiche/common/quiche_data_reader_test.cc", "src/quiche/common/quiche_data_writer_test.cc", "src/quiche/common/quiche_endian_test.cc", + "src/quiche/common/quiche_intrusive_list_test.cc", "src/quiche/common/quiche_ip_address_test.cc", "src/quiche/common/quiche_linked_hash_map_test.cc", "src/quiche/common/quiche_mem_slice_storage_test.cc",
diff --git a/build/source_list.json b/build/source_list.json index 9bb5d09..dc343b0 100644 --- a/build/source_list.json +++ b/build/source_list.json
@@ -46,6 +46,7 @@ "quiche/common/quiche_data_writer.h", "quiche/common/quiche_endian.h", "quiche/common/quiche_feature_flags_list.h", + "quiche/common/quiche_intrusive_list.h", "quiche/common/quiche_ip_address.h", "quiche/common/quiche_ip_address_family.h", "quiche/common/quiche_linked_hash_map.h", @@ -1094,6 +1095,7 @@ "quiche/common/quiche_data_reader_test.cc", "quiche/common/quiche_data_writer_test.cc", "quiche/common/quiche_endian_test.cc", + "quiche/common/quiche_intrusive_list_test.cc", "quiche/common/quiche_ip_address_test.cc", "quiche/common/quiche_linked_hash_map_test.cc", "quiche/common/quiche_mem_slice_storage_test.cc",
diff --git a/quiche/common/quiche_intrusive_list.h b/quiche/common/quiche_intrusive_list.h new file mode 100644 index 0000000..a00bc76 --- /dev/null +++ b/quiche/common/quiche_intrusive_list.h
@@ -0,0 +1,343 @@ +// Copyright (c) 2024 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_QUICHE_INTRUSIVE_LIST_H_ +#define QUICHE_COMMON_QUICHE_INTRUSIVE_LIST_H_ + +// A QuicheIntrusiveList<> is a doubly-linked list where the link pointers are +// embedded in the elements. They are circularly linked making insertion and +// removal into a known position constant time and branch-free operations. +// +// Usage is similar to an STL list<> where feasible, but there are important +// differences. First and foremost, the elements must derive from the +// QuicheIntrusiveLink<> base class: +// +// struct Foo : public QuicheIntrusiveLink<Foo> { +// // ... +// } +// +// QuicheIntrusiveList<Foo> l; +// l.push_back(new Foo); +// l.push_front(new Foo); +// l.erase(&l.front()); +// l.erase(&l.back()); +// +// Intrusive lists are primarily useful when you would have considered embedding +// link pointers in your class directly for space or performance reasons. An +// QuicheIntrusiveLink<> is the size of 2 pointers, usually 16 bytes on 64-bit +// systems. Intrusive lists do not perform memory allocation (unlike the STL +// list<> class) and thus may use less memory than list<>. In particular, if the +// list elements are pointers to objects, using a list<> would perform an extra +// memory allocation for each list node structure, while an +// QuicheIntrusiveList<> would not. +// +// Note that QuicheIntrusiveLink is exempt from the C++ style guide's +// limitations on multiple inheritance, so it's fine to inherit from both +// QuicheIntrusiveLink and a base class, even if the base class is not a pure +// interface. +// +// Because the list pointers are embedded in the objects stored in an +// QuicheIntrusiveList<>, erasing an item from a list is constant time. Consider +// the following: +// +// map<string,Foo> foo_map; +// list<Foo*> foo_list; +// +// foo_list.push_back(&foo_map["bar"]); +// foo_list.erase(&foo_map["bar"]); // Compile error! +// +// The problem here is that a Foo* doesn't know where on foo_list it resides, +// so removal requires iteration over the list. Various tricks can be performed +// to overcome this. For example, a foo_list::iterator can be stored inside of +// the Foo object. But at that point you'd be better off using an +// QuicheIntrusiveList<>: +// +// map<string,Foo> foo_map; +// QuicheIntrusiveList<Foo> foo_list; +// +// foo_list.push_back(&foo_map["bar"]); +// foo_list.erase(&foo_map["bar"]); // Yeah! +// +// Note that QuicheIntrusiveLists come with a few limitations. The primary +// limitation is that the QuicheIntrusiveLink<> base class is not copyable or +// assignable. The result is that STL algorithms which mutate the order of +// iterators, such as reverse() and unique(), will not work by default with +// QuicheIntrusiveLists. In order to allow these algorithms to work you'll need +// to define swap() and/or operator= for your class. +// +// Another limitation is that the QuicheIntrusiveList<> structure itself is not +// copyable or assignable since an item/link combination can only exist on one +// QuicheIntrusiveList<> at a time. This limitation is a result of the link +// pointers for an item being intrusive in the item itself. For example, the +// following will not compile: +// +// FooList a; +// FooList b(a); // no copy constructor +// b = a; // no assignment operator +// +// The similar STL code does work since the link pointers are external to the +// item: +// +// list<int*> a; +// a.push_back(new int); +// list<int*> b(a); +// QUICHE_CHECK(a.front() == b.front()); +// +// Note that QuicheIntrusiveList::size() runs in O(N) time. + +#include <stddef.h> + +#include <cstddef> +#include <iterator> + +#include "quiche/common/platform/api/quiche_export.h" + +namespace quiche { + +template <typename T, typename ListID> +class QuicheIntrusiveList; + +template <typename T, typename ListID = void> +class QUICHE_EXPORT QuicheIntrusiveLink { + protected: + // We declare the constructor protected so that only derived types and the + // befriended list can construct this. + QuicheIntrusiveLink() : next_(nullptr), prev_(nullptr) {} + +#ifndef SWIG + QuicheIntrusiveLink(const QuicheIntrusiveLink&) = delete; + QuicheIntrusiveLink& operator=(const QuicheIntrusiveLink&) = delete; +#endif // SWIG + + private: + // We befriend the matching list type so that it can manipulate the links + // while they are kept private from others. + friend class QuicheIntrusiveList<T, ListID>; + + // Encapsulates the logic to convert from a link to its derived type. + T* cast_to_derived() { return static_cast<T*>(this); } + const T* cast_to_derived() const { return static_cast<const T*>(this); } + + QuicheIntrusiveLink* next_; + QuicheIntrusiveLink* prev_; +}; + +template <typename T, typename ListID = void> +class QUICHE_EXPORT QuicheIntrusiveList { + template <typename QualifiedT, typename QualifiedLinkT> + class iterator_impl; + + public: + typedef T value_type; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + + typedef QuicheIntrusiveLink<T, ListID> link_type; + typedef iterator_impl<T, link_type> iterator; + typedef iterator_impl<const T, const link_type> const_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + + QuicheIntrusiveList() { clear(); } + // After the move constructor the moved-from list will be empty. + // + // NOTE: There is no move assign operator (for now). + // The reason is that at the moment 'clear()' does not unlink the nodes. + // It makes is_linked() return true when it should return false. + // If such node is removed from the list (e.g. from its destructor), or is + // added to another list - a memory corruption will occur. + // Admitedly the destructor does not unlink the nodes either, but move-assign + // will likely make the problem more prominent. +#ifndef SWIG + QuicheIntrusiveList(QuicheIntrusiveList&& src) noexcept { + clear(); + if (src.empty()) return; + sentinel_link_.next_ = src.sentinel_link_.next_; + sentinel_link_.prev_ = src.sentinel_link_.prev_; + // Fix head and tail nodes of the list. + sentinel_link_.prev_->next_ = &sentinel_link_; + sentinel_link_.next_->prev_ = &sentinel_link_; + src.clear(); + } +#endif // SWIG + + iterator begin() { return iterator(sentinel_link_.next_); } + const_iterator begin() const { return const_iterator(sentinel_link_.next_); } + iterator end() { return iterator(&sentinel_link_); } + const_iterator end() const { return const_iterator(&sentinel_link_); } + reverse_iterator rbegin() { return reverse_iterator(end()); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + + bool empty() const { return (sentinel_link_.next_ == &sentinel_link_); } + // This runs in O(N) time. + size_type size() const { return std::distance(begin(), end()); } + size_type max_size() const { return size_type(-1); } + + reference front() { return *begin(); } + const_reference front() const { return *begin(); } + reference back() { return *(--end()); } + const_reference back() const { return *(--end()); } + + static iterator insert(iterator position, T* obj) { + return insert_link(position.link(), obj); + } + void push_front(T* obj) { insert(begin(), obj); } + void push_back(T* obj) { insert(end(), obj); } + + static iterator erase(T* obj) { + link_type* obj_link = obj; + // Fix up the next and previous links for the previous and next objects. + obj_link->next_->prev_ = obj_link->prev_; + obj_link->prev_->next_ = obj_link->next_; + // Zero out the next and previous links for the removed item. This will + // cause any future attempt to remove the item from the list to cause a + // crash instead of possibly corrupting the list structure. + link_type* next_link = obj_link->next_; + obj_link->next_ = nullptr; + obj_link->prev_ = nullptr; + return iterator(next_link); + } + + static iterator erase(iterator position) { + return erase(position.operator->()); + } + void pop_front() { erase(begin()); } + void pop_back() { erase(--end()); } + + // Check whether the given element is linked into some list. Note that this + // does *not* check whether it is linked into a particular list. + // Also, if clear() is used to clear the containing list, is_linked() will + // still return true even though obj is no longer in any list. + static bool is_linked(const T* obj) { + return obj->link_type::next_ != nullptr; + } + + void clear() { + sentinel_link_.next_ = sentinel_link_.prev_ = &sentinel_link_; + } + void swap(QuicheIntrusiveList& x) { + QuicheIntrusiveList tmp; + tmp.splice(tmp.begin(), *this); + this->splice(this->begin(), x); + x.splice(x.begin(), tmp); + } + + void splice(iterator pos, QuicheIntrusiveList& src) { + splice(pos, src.begin(), src.end()); + } + + void splice(iterator pos, iterator i) { splice(pos, i, std::next(i)); } + + void splice(iterator pos, iterator first, iterator last) { + if (first == last) return; + + link_type* const last_prev = last.link()->prev_; + + // Remove from the source. + first.link()->prev_->next_ = last.operator->(); + last.link()->prev_ = first.link()->prev_; + + // Attach to the destination. + first.link()->prev_ = pos.link()->prev_; + pos.link()->prev_->next_ = first.operator->(); + last_prev->next_ = pos.operator->(); + pos.link()->prev_ = last_prev; + } + + private: + static iterator insert_link(link_type* next_link, T* obj) { + link_type* obj_link = obj; + obj_link->next_ = next_link; + link_type* const initial_next_prev = next_link->prev_; + obj_link->prev_ = initial_next_prev; + initial_next_prev->next_ = obj_link; + next_link->prev_ = obj_link; + return iterator(obj_link); + } + + // The iterator implementation is parameterized on a potentially qualified + // variant of T and the matching qualified link type. Essentially, QualifiedT + // will either be 'T' or 'const T', the latter for a const_iterator. + template <typename QualifiedT, typename QualifiedLinkT> + class QUICHE_EXPORT iterator_impl { + public: + using iterator_category = std::bidirectional_iterator_tag; + using value_type = QualifiedT; + using difference_type = std::ptrdiff_t; + using pointer = QualifiedT*; + using reference = QualifiedT&; + + iterator_impl() = default; + iterator_impl(QualifiedLinkT* link) : link_(link) {} + iterator_impl(const iterator_impl& x) = default; + iterator_impl& operator=(const iterator_impl& x) = default; + + // Allow converting and comparing across iterators where the pointer + // assignment and comparisons (respectively) are allowed. + template <typename U, typename V> + iterator_impl(const iterator_impl<U, V>& x) : link_(x.link_) {} + template <typename U, typename V> + bool operator==(const iterator_impl<U, V>& x) const { + return link_ == x.link_; + } + template <typename U, typename V> + bool operator!=(const iterator_impl<U, V>& x) const { + return link_ != x.link_; + } + + reference operator*() const { return *operator->(); } + pointer operator->() const { return link_->cast_to_derived(); } + + QualifiedLinkT* link() const { return link_; } + +#ifndef SWIG // SWIG can't wrap these operator overloads. + iterator_impl& operator++() { + link_ = link_->next_; + return *this; + } + iterator_impl operator++(int /*unused*/) { + iterator_impl tmp = *this; + ++*this; + return tmp; + } + iterator_impl& operator--() { + link_ = link_->prev_; + return *this; + } + iterator_impl operator--(int /*unused*/) { + iterator_impl tmp = *this; + --*this; + return tmp; + } +#endif // SWIG + + private: + // Ensure iterators can access other iterators node directly. + template <typename U, typename V> + friend class iterator_impl; + + QualifiedLinkT* link_ = nullptr; + }; + + // This bare link acts as the sentinel node. + link_type sentinel_link_; + + // These are private and undefined to prevent copying and assigning. + QuicheIntrusiveList(const QuicheIntrusiveList&); + void operator=(const QuicheIntrusiveList&); +}; + +} // namespace quiche + +#endif // QUICHE_COMMON_QUICHE_INTRUSIVE_LIST_H_
diff --git a/quiche/common/quiche_intrusive_list_test.cc b/quiche/common/quiche_intrusive_list_test.cc new file mode 100644 index 0000000..26b4731 --- /dev/null +++ b/quiche/common/quiche_intrusive_list_test.cc
@@ -0,0 +1,420 @@ +// Copyright (c) 2024 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/quiche_intrusive_list.h" + +#include <algorithm> +#include <iterator> +#include <list> +#include <string> +#include <utility> + +#include "quiche/common/platform/api/quiche_test.h" + +namespace quiche { +namespace test { + +struct ListId2 {}; + +struct TestItem : public QuicheIntrusiveLink<TestItem>, + public QuicheIntrusiveLink<TestItem, ListId2> { + int n; +}; +typedef QuicheIntrusiveList<TestItem> TestList; +typedef std::list<TestItem *> CanonicalList; + +void swap(TestItem &a, TestItem &b) { + using std::swap; + swap(a.n, b.n); +} + +class IntrusiveListTest : public quiche::test::QuicheTest { + protected: + void CheckLists() { + CheckLists(l1, ll1); + if (quiche::test::QuicheTest::HasFailure()) return; + CheckLists(l2, ll2); + } + + void CheckLists(const TestList &list_a, const CanonicalList &list_b) { + ASSERT_EQ(list_a.size(), list_b.size()); + TestList::const_iterator it_a = list_a.begin(); + CanonicalList::const_iterator it_b = list_b.begin(); + while (it_a != list_a.end()) { + EXPECT_EQ(&*it_a++, *it_b++); + } + EXPECT_EQ(list_a.end(), it_a); + EXPECT_EQ(list_b.end(), it_b); + } + + void PrepareLists(int num_elems_1, int num_elems_2 = 0) { + FillLists(&l1, &ll1, e, num_elems_1); + FillLists(&l2, &ll2, e + num_elems_1, num_elems_2); + } + + void FillLists(TestList *list_a, CanonicalList *list_b, TestItem *elems, + int num_elems) { + list_a->clear(); + list_b->clear(); + for (int i = 0; i < num_elems; ++i) { + list_a->push_back(elems + i); + list_b->push_back(elems + i); + } + CheckLists(*list_a, *list_b); + } + + TestItem e[10]; + TestList l1, l2; + CanonicalList ll1, ll2; +}; + +TEST(NewIntrusiveListTest, Basic) { + TestList list1; + + EXPECT_EQ(sizeof(QuicheIntrusiveLink<TestItem>), sizeof(void *) * 2); + + for (int i = 0; i < 10; ++i) { + TestItem *e = new TestItem; + e->n = i; + list1.push_front(e); + } + EXPECT_EQ(list1.size(), 10u); + + // Verify we can reverse a list because we defined swap for TestItem. + std::reverse(list1.begin(), list1.end()); + EXPECT_EQ(list1.size(), 10u); + + // Check both const and non-const forward iteration. + const TestList &clist1 = list1; + int i = 0; + TestList::iterator iter = list1.begin(); + for (; iter != list1.end(); ++iter, ++i) { + EXPECT_EQ(iter->n, i); + } + EXPECT_EQ(iter, clist1.end()); + EXPECT_NE(iter, clist1.begin()); + i = 0; + iter = list1.begin(); + for (; iter != list1.end(); ++iter, ++i) { + EXPECT_EQ(iter->n, i); + } + EXPECT_EQ(iter, clist1.end()); + EXPECT_NE(iter, clist1.begin()); + + EXPECT_EQ(list1.front().n, 0); + EXPECT_EQ(list1.back().n, 9); + + // Verify we can swap 2 lists. + TestList list2; + list2.swap(list1); + EXPECT_EQ(list1.size(), 0u); + EXPECT_EQ(list2.size(), 10u); + + // Check both const and non-const reverse iteration. + const TestList &clist2 = list2; + TestList::reverse_iterator riter = list2.rbegin(); + i = 9; + for (; riter != list2.rend(); ++riter, --i) { + EXPECT_EQ(riter->n, i); + } + EXPECT_EQ(riter, clist2.rend()); + EXPECT_NE(riter, clist2.rbegin()); + + riter = list2.rbegin(); + i = 9; + for (; riter != list2.rend(); ++riter, --i) { + EXPECT_EQ(riter->n, i); + } + EXPECT_EQ(riter, clist2.rend()); + EXPECT_NE(riter, clist2.rbegin()); + + while (!list2.empty()) { + TestItem *e = &list2.front(); + list2.pop_front(); + delete e; + } +} + +TEST(NewIntrusiveListTest, Erase) { + TestList l; + TestItem *e[10]; + + // Create a list with 10 items. + for (int i = 0; i < 10; ++i) { + e[i] = new TestItem; + l.push_front(e[i]); + } + + // Test that erase works. + for (int i = 0; i < 10; ++i) { + EXPECT_EQ(l.size(), (10u - i)); + + TestList::iterator iter = l.erase(e[i]); + EXPECT_NE(iter, TestList::iterator(e[i])); + + EXPECT_EQ(l.size(), (10u - i - 1)); + delete e[i]; + } +} + +TEST(NewIntrusiveListTest, Insert) { + TestList l; + TestList::iterator iter = l.end(); + TestItem *e[10]; + + // Create a list with 10 items. + for (int i = 9; i >= 0; --i) { + e[i] = new TestItem; + iter = l.insert(iter, e[i]); + EXPECT_EQ(&(*iter), e[i]); + } + + EXPECT_EQ(l.size(), 10u); + + // Verify insertion order. + iter = l.begin(); + for (TestItem *item : e) { + EXPECT_EQ(&(*iter), item); + iter = l.erase(item); + delete item; + } +} + +TEST(NewIntrusiveListTest, Move) { + // Move contructible. + + { // Move-construct from an empty list. + TestList src; + TestList dest(std::move(src)); + EXPECT_TRUE(dest.empty()); + } + + { // Move-construct from a single item list. + TestItem e; + TestList src; + src.push_front(&e); + + TestList dest(std::move(src)); + EXPECT_TRUE(src.empty()); // NOLINT bugprone-use-after-move + ASSERT_THAT(dest.size(), 1); + EXPECT_THAT(&dest.front(), &e); + EXPECT_THAT(&dest.back(), &e); + } + + { // Move-construct from a list with multiple items. + TestItem items[10]; + TestList src; + for (TestItem &e : items) src.push_back(&e); + + TestList dest(std::move(src)); + EXPECT_TRUE(src.empty()); // NOLINT bugprone-use-after-move + // Verify the items on the destination list. + ASSERT_THAT(dest.size(), 10); + int i = 0; + for (TestItem &e : dest) { + EXPECT_THAT(&e, &items[i++]) << " for index " << i; + } + } +} + +TEST(NewIntrusiveListTest, StaticInsertErase) { + TestList l; + TestItem e[2]; + TestList::iterator i = l.begin(); + TestList::insert(i, &e[0]); + TestList::insert(&e[0], &e[1]); + TestList::erase(&e[0]); + TestList::erase(TestList::iterator(&e[1])); + EXPECT_TRUE(l.empty()); +} + +TEST_F(IntrusiveListTest, Splice) { + // We verify that the contents of this secondary list aren't affected by any + // of the splices. + QuicheIntrusiveList<TestItem, ListId2> secondary_list; + for (int i = 0; i < 3; ++i) { + secondary_list.push_back(&e[i]); + } + + // Test the basic cases: + // - The lists range from 0 to 2 elements. + // - The insertion point ranges from begin() to end() + // - The transfered range has multiple sizes and locations in the source. + for (int l1_count = 0; l1_count < 3; ++l1_count) { + for (int l2_count = 0; l2_count < 3; ++l2_count) { + for (int pos = 0; pos <= l1_count; ++pos) { + for (int first = 0; first <= l2_count; ++first) { + for (int last = first; last <= l2_count; ++last) { + PrepareLists(l1_count, l2_count); + + l1.splice(std::next(l1.begin(), pos), std::next(l2.begin(), first), + std::next(l2.begin(), last)); + ll1.splice(std::next(ll1.begin(), pos), ll2, + std::next(ll2.begin(), first), + std::next(ll2.begin(), last)); + + CheckLists(); + + ASSERT_EQ(3u, secondary_list.size()); + for (int i = 0; i < 3; ++i) { + EXPECT_EQ(&e[i], &*std::next(secondary_list.begin(), i)); + } + } + } + } + } + } +} + +// Build up a set of classes which form "challenging" type hierarchies to use +// with an QuicheIntrusiveList. +struct BaseLinkId {}; +struct DerivedLinkId {}; + +struct AbstractBase : public QuicheIntrusiveLink<AbstractBase, BaseLinkId> { + virtual ~AbstractBase() = 0; + virtual std::string name() { return "AbstractBase"; } +}; +AbstractBase::~AbstractBase() {} +struct DerivedClass : public QuicheIntrusiveLink<DerivedClass, DerivedLinkId>, + public AbstractBase { + ~DerivedClass() override {} + std::string name() override { return "DerivedClass"; } +}; +struct VirtuallyDerivedBaseClass : public virtual AbstractBase { + ~VirtuallyDerivedBaseClass() override = 0; + std::string name() override { return "VirtuallyDerivedBaseClass"; } +}; +VirtuallyDerivedBaseClass::~VirtuallyDerivedBaseClass() {} +struct VirtuallyDerivedClassA + : public QuicheIntrusiveLink<VirtuallyDerivedClassA, DerivedLinkId>, + public virtual VirtuallyDerivedBaseClass { + ~VirtuallyDerivedClassA() override {} + std::string name() override { return "VirtuallyDerivedClassA"; } +}; +struct NonceClass { + virtual ~NonceClass() {} + int data_; +}; +struct VirtuallyDerivedClassB + : public QuicheIntrusiveLink<VirtuallyDerivedClassB, DerivedLinkId>, + public virtual NonceClass, + public virtual VirtuallyDerivedBaseClass { + ~VirtuallyDerivedClassB() override {} + std::string name() override { return "VirtuallyDerivedClassB"; } +}; +struct VirtuallyDerivedClassC + : public QuicheIntrusiveLink<VirtuallyDerivedClassC, DerivedLinkId>, + public virtual AbstractBase, + public virtual NonceClass, + public virtual VirtuallyDerivedBaseClass { + ~VirtuallyDerivedClassC() override {} + std::string name() override { return "VirtuallyDerivedClassC"; } +}; + +// Test for multiple layers between the element type and the link. +namespace templated_base_link { +template <typename T> +struct AbstractBase : public QuicheIntrusiveLink<T> { + virtual ~AbstractBase() = 0; +}; +template <typename T> +AbstractBase<T>::~AbstractBase() {} +struct DerivedClass : public AbstractBase<DerivedClass> { + int n; +}; +} // namespace templated_base_link + +TEST(NewIntrusiveListTest, HandleInheritanceHierarchies) { + { + QuicheIntrusiveList<DerivedClass, DerivedLinkId> list; + DerivedClass elements[2]; + EXPECT_TRUE(list.empty()); + list.push_back(&elements[0]); + EXPECT_EQ(1u, list.size()); + list.push_back(&elements[1]); + EXPECT_EQ(2u, list.size()); + list.pop_back(); + EXPECT_EQ(1u, list.size()); + list.pop_back(); + EXPECT_TRUE(list.empty()); + } + { + QuicheIntrusiveList<VirtuallyDerivedClassA, DerivedLinkId> list; + VirtuallyDerivedClassA elements[2]; + EXPECT_TRUE(list.empty()); + list.push_back(&elements[0]); + EXPECT_EQ(1u, list.size()); + list.push_back(&elements[1]); + EXPECT_EQ(2u, list.size()); + list.pop_back(); + EXPECT_EQ(1u, list.size()); + list.pop_back(); + EXPECT_TRUE(list.empty()); + } + { + QuicheIntrusiveList<VirtuallyDerivedClassC, DerivedLinkId> list; + VirtuallyDerivedClassC elements[2]; + EXPECT_TRUE(list.empty()); + list.push_back(&elements[0]); + EXPECT_EQ(1u, list.size()); + list.push_back(&elements[1]); + EXPECT_EQ(2u, list.size()); + list.pop_back(); + EXPECT_EQ(1u, list.size()); + list.pop_back(); + EXPECT_TRUE(list.empty()); + } + { + QuicheIntrusiveList<AbstractBase, BaseLinkId> list; + DerivedClass d1; + VirtuallyDerivedClassA d2; + VirtuallyDerivedClassB d3; + VirtuallyDerivedClassC d4; + EXPECT_TRUE(list.empty()); + list.push_back(&d1); + EXPECT_EQ(1u, list.size()); + list.push_back(&d2); + EXPECT_EQ(2u, list.size()); + list.push_back(&d3); + EXPECT_EQ(3u, list.size()); + list.push_back(&d4); + EXPECT_EQ(4u, list.size()); + QuicheIntrusiveList<AbstractBase, BaseLinkId>::iterator it = list.begin(); + EXPECT_EQ("DerivedClass", (it++)->name()); + EXPECT_EQ("VirtuallyDerivedClassA", (it++)->name()); + EXPECT_EQ("VirtuallyDerivedClassB", (it++)->name()); + EXPECT_EQ("VirtuallyDerivedClassC", (it++)->name()); + } + { + QuicheIntrusiveList<templated_base_link::DerivedClass> list; + templated_base_link::DerivedClass elements[2]; + EXPECT_TRUE(list.empty()); + list.push_back(&elements[0]); + EXPECT_EQ(1u, list.size()); + list.push_back(&elements[1]); + EXPECT_EQ(2u, list.size()); + list.pop_back(); + EXPECT_EQ(1u, list.size()); + list.pop_back(); + EXPECT_TRUE(list.empty()); + } +} + +class IntrusiveListTagTypeTest : public quiche::test::QuicheTest { + protected: + struct Tag {}; + class Element : public QuicheIntrusiveLink<Element, Tag> {}; +}; + +TEST_F(IntrusiveListTagTypeTest, TagTypeListID) { + QuicheIntrusiveList<Element, Tag> list; + { + Element e; + list.push_back(&e); + } +} + +} // namespace test +} // namespace quiche