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
