Move IntrusiveForwardList<> to libartbase.
It's generally useful, not just for the compiler.
Test: m test-art-host-gtest
Change-Id: I3ca742d93a0bca961d1b8b8209356747d2de08a0
diff --git a/compiler/Android.bp b/compiler/Android.bp
index aee181a..c7fe77d 100644
--- a/compiler/Android.bp
+++ b/compiler/Android.bp
@@ -382,7 +382,6 @@
"optimizing/suspend_check_test.cc",
"utils/atomic_dex_ref_map_test.cc",
"utils/dedupe_set_test.cc",
- "utils/intrusive_forward_list_test.cc",
"utils/swap_space_test.cc",
"jni/jni_cfi_test.cc",
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 2a7bbcb..9419c8d 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -22,6 +22,7 @@
#include <sstream>
#include "art_method.h"
+#include "base/intrusive_forward_list.h"
#include "bounds_check_elimination.h"
#include "builder.h"
#include "code_generator.h"
@@ -38,7 +39,6 @@
#include "scoped_thread_state_change-inl.h"
#include "ssa_liveness_analysis.h"
#include "utils/assembler.h"
-#include "utils/intrusive_forward_list.h"
namespace art {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 57ed71d..023e3a6 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -25,6 +25,7 @@
#include "base/arena_containers.h"
#include "base/arena_object.h"
#include "base/array_ref.h"
+#include "base/intrusive_forward_list.h"
#include "base/iteration_range.h"
#include "base/mutex.h"
#include "base/quasi_atomic.h"
@@ -45,7 +46,6 @@
#include "mirror/class.h"
#include "mirror/method_type.h"
#include "offsets.h"
-#include "utils/intrusive_forward_list.h"
namespace art {
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index c883907..3ea2815 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -19,11 +19,11 @@
#include <iostream>
+#include "base/intrusive_forward_list.h"
#include "base/iteration_range.h"
#include "base/scoped_arena_allocator.h"
#include "base/scoped_arena_containers.h"
#include "nodes.h"
-#include "utils/intrusive_forward_list.h"
namespace art {
diff --git a/compiler/utils/intrusive_forward_list.h b/compiler/utils/intrusive_forward_list.h
deleted file mode 100644
index ccdd32a..0000000
--- a/compiler/utils/intrusive_forward_list.h
+++ /dev/null
@@ -1,477 +0,0 @@
-/*
- * Copyright (C) 2016 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#ifndef ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
-#define ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
-
-#include <stdint.h>
-#include <functional>
-#include <iterator>
-#include <memory>
-#include <type_traits>
-
-#include <android-base/logging.h>
-
-#include "base/casts.h"
-#include "base/macros.h"
-
-namespace art {
-
-struct IntrusiveForwardListHook {
- IntrusiveForwardListHook() : next_hook(nullptr) { }
- explicit IntrusiveForwardListHook(const IntrusiveForwardListHook* hook) : next_hook(hook) { }
-
- // Allow copyable values but do not copy the hook, it is not part of the value.
- IntrusiveForwardListHook(const IntrusiveForwardListHook& other ATTRIBUTE_UNUSED)
- : next_hook(nullptr) { }
- IntrusiveForwardListHook& operator=(const IntrusiveForwardListHook& src ATTRIBUTE_UNUSED) {
- return *this;
- }
-
- mutable const IntrusiveForwardListHook* next_hook;
-};
-
-template <typename Derived, typename Tag = void>
-struct IntrusiveForwardListNode : public IntrusiveForwardListHook {
-};
-
-template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook>
-class IntrusiveForwardListMemberHookTraits;
-
-template <typename T, typename Tag = void>
-class IntrusiveForwardListBaseHookTraits;
-
-template <typename T,
- typename HookTraits =
- IntrusiveForwardListBaseHookTraits<typename std::remove_const<T>::type>>
-class IntrusiveForwardList;
-
-template <typename T, typename HookTraits>
-class IntrusiveForwardListIterator : public std::iterator<std::forward_iterator_tag, T> {
- public:
- // Construct/copy/destroy (except the private constructor used by IntrusiveForwardList<>).
- IntrusiveForwardListIterator() : hook_(nullptr) { }
- IntrusiveForwardListIterator(const IntrusiveForwardListIterator& src) = default;
- IntrusiveForwardListIterator& operator=(const IntrusiveForwardListIterator& src) = default;
-
- // Conversion from iterator to const_iterator.
- template <typename OtherT,
- typename = typename std::enable_if<std::is_same<T, const OtherT>::value>::type>
- IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT, HookTraits>& src) // NOLINT, implicit
- : hook_(src.hook_) { }
-
- // Iteration.
- IntrusiveForwardListIterator& operator++() {
- DCHECK(hook_ != nullptr);
- hook_ = hook_->next_hook;
- return *this;
- }
- IntrusiveForwardListIterator operator++(int) {
- IntrusiveForwardListIterator tmp(*this);
- ++*this;
- return tmp;
- }
-
- // Dereference
- T& operator*() const {
- DCHECK(hook_ != nullptr);
- return *HookTraits::GetValue(hook_);
- }
- T* operator->() const {
- return &**this;
- }
-
- private:
- explicit IntrusiveForwardListIterator(const IntrusiveForwardListHook* hook) : hook_(hook) { }
-
- const IntrusiveForwardListHook* hook_;
-
- template <typename OtherT, typename OtherTraits>
- friend class IntrusiveForwardListIterator;
-
- template <typename OtherT, typename OtherTraits>
- friend class IntrusiveForwardList;
-
- template <typename OtherT1, typename OtherT2, typename OtherTraits>
- friend typename std::enable_if<std::is_same<const OtherT1, const OtherT2>::value, bool>::type
- operator==(const IntrusiveForwardListIterator<OtherT1, OtherTraits>& lhs,
- const IntrusiveForwardListIterator<OtherT2, OtherTraits>& rhs);
-};
-
-template <typename T, typename OtherT, typename HookTraits>
-typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator==(
- const IntrusiveForwardListIterator<T, HookTraits>& lhs,
- const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
- return lhs.hook_ == rhs.hook_;
-}
-
-template <typename T, typename OtherT, typename HookTraits>
-typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator!=(
- const IntrusiveForwardListIterator<T, HookTraits>& lhs,
- const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
- return !(lhs == rhs);
-}
-
-// Intrusive version of std::forward_list<>. See also slist<> in Boost.Intrusive.
-//
-// This class template provides the same interface as std::forward_list<> as long
-// as the functions are meaningful for an intrusive container; this excludes emplace
-// functions and functions taking an std::initializer_list<> as the container does
-// not construct elements.
-template <typename T, typename HookTraits>
-class IntrusiveForwardList {
- public:
- typedef HookTraits hook_traits;
- typedef T value_type;
- typedef T& reference;
- typedef const T& const_reference;
- typedef T* pointer;
- typedef const T* const_pointer;
- typedef IntrusiveForwardListIterator< T, hook_traits> iterator;
- typedef IntrusiveForwardListIterator<const T, hook_traits> const_iterator;
-
- // Construct/copy/destroy.
- IntrusiveForwardList() = default;
- template <typename InputIterator>
- IntrusiveForwardList(InputIterator first, InputIterator last) : IntrusiveForwardList() {
- insert_after(before_begin(), first, last);
- }
- IntrusiveForwardList(IntrusiveForwardList&& src) : first_(src.first_.next_hook) {
- src.first_.next_hook = nullptr;
- }
- IntrusiveForwardList& operator=(const IntrusiveForwardList& src) = delete;
- IntrusiveForwardList& operator=(IntrusiveForwardList&& src) {
- IntrusiveForwardList tmp(std::move(src));
- tmp.swap(*this);
- return *this;
- }
- ~IntrusiveForwardList() = default;
-
- // Iterators.
- iterator before_begin() { return iterator(&first_); }
- const_iterator before_begin() const { return const_iterator(&first_); }
- iterator begin() { return iterator(first_.next_hook); }
- const_iterator begin() const { return const_iterator(first_.next_hook); }
- iterator end() { return iterator(nullptr); }
- const_iterator end() const { return const_iterator(nullptr); }
- const_iterator cbefore_begin() const { return const_iterator(&first_); }
- const_iterator cbegin() const { return const_iterator(first_.next_hook); }
- const_iterator cend() const { return const_iterator(nullptr); }
-
- // Capacity.
- bool empty() const { return begin() == end(); }
- size_t max_size() { return static_cast<size_t>(-1); }
-
- // Element access.
- reference front() { return *begin(); }
- const_reference front() const { return *begin(); }
-
- // Modifiers.
- template <typename InputIterator>
- void assign(InputIterator first, InputIterator last) {
- IntrusiveForwardList tmp(first, last);
- tmp.swap(*this);
- }
- void push_front(value_type& value) {
- insert_after(before_begin(), value);
- }
- void pop_front() {
- DCHECK(!empty());
- erase_after(before_begin());
- }
- iterator insert_after(const_iterator position, value_type& value) {
- const IntrusiveForwardListHook* new_hook = hook_traits::GetHook(&value);
- new_hook->next_hook = position.hook_->next_hook;
- position.hook_->next_hook = new_hook;
- return iterator(new_hook);
- }
- template <typename InputIterator>
- iterator insert_after(const_iterator position, InputIterator first, InputIterator last) {
- while (first != last) {
- position = insert_after(position, *first++);
- }
- return iterator(position.hook_);
- }
- iterator erase_after(const_iterator position) {
- const_iterator last = position;
- std::advance(last, 2);
- return erase_after(position, last);
- }
- iterator erase_after(const_iterator position, const_iterator last) {
- DCHECK(position != last);
- position.hook_->next_hook = last.hook_;
- return iterator(last.hook_);
- }
- void swap(IntrusiveForwardList& other) {
- std::swap(first_.next_hook, other.first_.next_hook);
- }
- void clear() {
- first_.next_hook = nullptr;
- }
-
- // Operations.
- void splice_after(const_iterator position, IntrusiveForwardList& src) {
- DCHECK(position != end());
- splice_after(position, src, src.before_begin(), src.end());
- }
- void splice_after(const_iterator position, IntrusiveForwardList&& src) {
- splice_after(position, src); // Use l-value overload.
- }
- // Splice the element after `i`.
- void splice_after(const_iterator position, IntrusiveForwardList& src, const_iterator i) {
- // The standard specifies that this version does nothing if `position == i`
- // or `position == ++i`. We must handle the latter here because the overload
- // `splice_after(position, src, first, last)` does not allow `position` inside
- // the range `(first, last)`.
- if (++const_iterator(i) == position) {
- return;
- }
- const_iterator last = i;
- std::advance(last, 2);
- splice_after(position, src, i, last);
- }
- // Splice the element after `i`.
- void splice_after(const_iterator position, IntrusiveForwardList&& src, const_iterator i) {
- splice_after(position, src, i); // Use l-value overload.
- }
- // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
- void splice_after(const_iterator position,
- IntrusiveForwardList& src,
- const_iterator first,
- const_iterator last) {
- DCHECK(position != end());
- DCHECK(first != last);
- if (++const_iterator(first) == last) {
- // Nothing to do.
- return;
- }
- // If position is just before end() and last is src.end(), we can finish this quickly.
- if (++const_iterator(position) == end() && last == src.end()) {
- position.hook_->next_hook = first.hook_->next_hook;
- first.hook_->next_hook = nullptr;
- return;
- }
- // Otherwise we need to find the position before last to fix up the hook.
- const_iterator before_last = first;
- while (++const_iterator(before_last) != last) {
- ++before_last;
- }
- // Detach (first, last).
- const IntrusiveForwardListHook* first_taken = first.hook_->next_hook;
- first.hook_->next_hook = last.hook_;
- // Attach the sequence to the new position.
- before_last.hook_->next_hook = position.hook_->next_hook;
- position.hook_->next_hook = first_taken;
- }
- // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
- void splice_after(const_iterator position,
- IntrusiveForwardList&& src,
- const_iterator first,
- const_iterator last) {
- splice_after(position, src, first, last); // Use l-value overload.
- }
- void remove(const value_type& value) {
- remove_if([value](const value_type& v) { return value == v; });
- }
- template <typename Predicate>
- void remove_if(Predicate pred) {
- iterator prev = before_begin();
- for (iterator current = begin(); current != end(); ++current) {
- if (pred(*current)) {
- erase_after(prev);
- current = prev;
- } else {
- prev = current;
- }
- }
- }
- void unique() {
- unique(std::equal_to<value_type>());
- }
- template <typename BinaryPredicate>
- void unique(BinaryPredicate pred) {
- if (!empty()) {
- iterator prev = begin();
- iterator current = prev;
- ++current;
- for (; current != end(); ++current) {
- if (pred(*prev, *current)) {
- erase_after(prev);
- current = prev;
- } else {
- prev = current;
- }
- }
- }
- }
- void merge(IntrusiveForwardList& other) {
- merge(other, std::less<value_type>());
- }
- void merge(IntrusiveForwardList&& other) {
- merge(other); // Use l-value overload.
- }
- template <typename Compare>
- void merge(IntrusiveForwardList& other, Compare cmp) {
- iterator prev = before_begin();
- iterator current = begin();
- iterator other_prev = other.before_begin();
- iterator other_current = other.begin();
- while (current != end() && other_current != other.end()) {
- if (cmp(*other_current, *current)) {
- ++other_current;
- splice_after(prev, other, other_prev);
- ++prev;
- } else {
- prev = current;
- ++current;
- }
- DCHECK(++const_iterator(prev) == current);
- DCHECK(++const_iterator(other_prev) == other_current);
- }
- splice_after(prev, other);
- }
- template <typename Compare>
- void merge(IntrusiveForwardList&& other, Compare cmp) {
- merge(other, cmp); // Use l-value overload.
- }
- void sort() {
- sort(std::less<value_type>());
- }
- template <typename Compare>
- void sort(Compare cmp) {
- size_t n = std::distance(begin(), end());
- if (n >= 2u) {
- const_iterator middle = before_begin();
- std::advance(middle, n / 2u);
- IntrusiveForwardList second_half;
- second_half.splice_after(second_half.before_begin(), *this, middle, end());
- sort(cmp);
- second_half.sort(cmp);
- merge(second_half, cmp);
- }
- }
- void reverse() {
- IntrusiveForwardList reversed;
- while (!empty()) {
- value_type& value = front();
- erase_after(before_begin());
- reversed.insert_after(reversed.before_begin(), value);
- }
- reversed.swap(*this);
- }
-
- // Extensions.
- bool HasExactlyOneElement() const {
- return !empty() && ++begin() == end();
- }
- size_t SizeSlow() const {
- return std::distance(begin(), end());
- }
- bool ContainsNode(const_reference node) const {
- for (auto&& n : *this) {
- if (std::addressof(n) == std::addressof(node)) {
- return true;
- }
- }
- return false;
- }
-
- private:
- static IntrusiveForwardListHook* ModifiableHook(const IntrusiveForwardListHook* hook) {
- return const_cast<IntrusiveForwardListHook*>(hook);
- }
-
- IntrusiveForwardListHook first_;
-};
-
-template <typename T, typename HookTraits>
-void swap(IntrusiveForwardList<T, HookTraits>& lhs, IntrusiveForwardList<T, HookTraits>& rhs) {
- lhs.swap(rhs);
-}
-
-template <typename T, typename HookTraits>
-bool operator==(const IntrusiveForwardList<T, HookTraits>& lhs,
- const IntrusiveForwardList<T, HookTraits>& rhs) {
- auto lit = lhs.begin();
- auto rit = rhs.begin();
- for (; lit != lhs.end() && rit != rhs.end(); ++lit, ++rit) {
- if (*lit != *rit) {
- return false;
- }
- }
- return lit == lhs.end() && rit == rhs.end();
-}
-
-template <typename T, typename HookTraits>
-bool operator!=(const IntrusiveForwardList<T, HookTraits>& lhs,
- const IntrusiveForwardList<T, HookTraits>& rhs) {
- return !(lhs == rhs);
-}
-
-template <typename T, typename HookTraits>
-bool operator<(const IntrusiveForwardList<T, HookTraits>& lhs,
- const IntrusiveForwardList<T, HookTraits>& rhs) {
- return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
-}
-
-template <typename T, typename HookTraits>
-bool operator>(const IntrusiveForwardList<T, HookTraits>& lhs,
- const IntrusiveForwardList<T, HookTraits>& rhs) {
- return rhs < lhs;
-}
-
-template <typename T, typename HookTraits>
-bool operator<=(const IntrusiveForwardList<T, HookTraits>& lhs,
- const IntrusiveForwardList<T, HookTraits>& rhs) {
- return !(rhs < lhs);
-}
-
-template <typename T, typename HookTraits>
-bool operator>=(const IntrusiveForwardList<T, HookTraits>& lhs,
- const IntrusiveForwardList<T, HookTraits>& rhs) {
- return !(lhs < rhs);
-}
-
-template <typename T, IntrusiveForwardListHook T::* NextPtr>
-class IntrusiveForwardListMemberHookTraits {
- public:
- static const IntrusiveForwardListHook* GetHook(const T* value) {
- return &(value->*NextPtr);
- }
-
- static T* GetValue(const IntrusiveForwardListHook* hook) {
- return reinterpret_cast<T*>(
- reinterpret_cast<uintptr_t>(hook) - OFFSETOF_MEMBERPTR(T, NextPtr));
- }
-};
-
-template <typename T, typename Tag>
-class IntrusiveForwardListBaseHookTraits {
- public:
- static const IntrusiveForwardListHook* GetHook(const T* value) {
- // Explicit conversion to the "node" followed by implicit conversion to the "hook".
- return static_cast<const IntrusiveForwardListNode<T, Tag>*>(value);
- }
-
- static T* GetValue(const IntrusiveForwardListHook* hook) {
- return down_cast<T*>(down_cast<IntrusiveForwardListNode<T, Tag>*>(
- const_cast<IntrusiveForwardListHook*>(hook)));
- }
-};
-
-} // namespace art
-
-#endif // ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
diff --git a/compiler/utils/intrusive_forward_list_test.cc b/compiler/utils/intrusive_forward_list_test.cc
deleted file mode 100644
index e97c304..0000000
--- a/compiler/utils/intrusive_forward_list_test.cc
+++ /dev/null
@@ -1,779 +0,0 @@
-/*
- * Copyright (C) 2016 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <algorithm>
-#include <forward_list>
-#include <vector>
-
-#include "gtest/gtest.h"
-#include "intrusive_forward_list.h"
-
-namespace art {
-
-struct IFLTestValue : public IntrusiveForwardListNode<IFLTestValue> {
- // Deliberately not explicit.
- IFLTestValue(int v) : value(v) { } // NOLINT(runtime/explicit)
-
- int value;
-};
-using IFLTestValueList = IntrusiveForwardList<IFLTestValue>;
-using ConstIFLTestValueList = IntrusiveForwardList<const IFLTestValue>;
-
-bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) {
- return lhs.value == rhs.value;
-}
-
-bool operator<(const IFLTestValue& lhs, const IFLTestValue& rhs) {
- return lhs.value < rhs.value;
-}
-
-struct IFLTestValue2 {
- // Deliberately not explicit.
- IFLTestValue2(int v) : hook(), value(v) { } // NOLINT(runtime/explicit)
-
- IntrusiveForwardListHook hook;
- int value;
-};
-using IFLTestValue2List =
- IntrusiveForwardList<IFLTestValue2, IntrusiveForwardListMemberHookTraits<IFLTestValue2>>;
-
-bool operator==(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
- return lhs.value == rhs.value;
-}
-
-bool operator<(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
- return lhs.value < rhs.value;
-}
-
-#define ASSERT_LISTS_EQUAL(expected, value) \
- do { \
- ASSERT_EQ((expected).empty(), (value).empty()); \
- ASSERT_EQ(std::distance((expected).begin(), (expected).end()), \
- std::distance((value).begin(), (value).end())); \
- ASSERT_TRUE(std::equal((expected).begin(), (expected).end(), (value).begin())); \
- } while (false)
-
-class IntrusiveForwardListTest : public testing::Test {
- public:
- template <typename ListType>
- void IteratorToConstIterator();
-
- template <typename ListType>
- void IteratorOperators();
-
- template <typename ListType>
- void ConstructRange();
-
- template <typename ListType>
- void Assign();
-
- template <typename ListType>
- void PushPop();
-
- template <typename ListType>
- void InsertAfter1();
-
- template <typename ListType>
- void InsertAfter2();
-
- template <typename ListType>
- void EraseAfter1();
-
- template <typename ListType>
- void EraseAfter2();
-
- template <typename ListType>
- void SwapClear();
-
- template <typename ListType>
- void SpliceAfter();
-
- template <typename ListType>
- void Remove();
-
- template <typename ListType>
- void Unique();
-
- template <typename ListType>
- void Merge();
-
- template <typename ListType>
- void Sort1();
-
- template <typename ListType>
- void Sort2();
-
- template <typename ListType>
- void Reverse();
-
- template <typename ListType>
- void ModifyValue();
-};
-
-template <typename ListType>
-void IntrusiveForwardListTest::IteratorToConstIterator() {
- ListType ifl;
- typename ListType::iterator begin = ifl.begin();
- typename ListType::const_iterator cbegin = ifl.cbegin();
- typename ListType::const_iterator converted_begin = begin;
- ASSERT_TRUE(converted_begin == cbegin);
-}
-
-TEST_F(IntrusiveForwardListTest, IteratorToConstIterator) {
- IteratorToConstIterator<IFLTestValueList>();
- IteratorToConstIterator<ConstIFLTestValueList>();
- IteratorToConstIterator<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::IteratorOperators() {
- using ValueType = typename ListType::value_type;
- ListType ifl;
- ASSERT_TRUE(ifl.begin() == ifl.cbegin());
- ASSERT_FALSE(ifl.begin() != ifl.cbegin());
- ASSERT_TRUE(ifl.end() == ifl.cend());
- ASSERT_FALSE(ifl.end() != ifl.cend());
-
- ASSERT_TRUE(ifl.begin() == ifl.end()); // Empty.
- ASSERT_FALSE(ifl.begin() != ifl.end()); // Empty.
-
- ValueType value(1);
- ifl.insert_after(ifl.cbefore_begin(), value);
-
- ASSERT_FALSE(ifl.begin() == ifl.end()); // Not empty.
- ASSERT_TRUE(ifl.begin() != ifl.end()); // Not empty.
-}
-
-TEST_F(IntrusiveForwardListTest, IteratorOperators) {
- IteratorOperators<IFLTestValueList>();
- IteratorOperators<ConstIFLTestValueList>();
- IteratorOperators<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::ConstructRange() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 1, 2, 7 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, ConstructRange) {
- ConstructRange<IFLTestValueList>();
- ConstructRange<ConstIFLTestValueList>();
- ConstructRange<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::Assign() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref1({ 2, 8, 5 });
- std::vector<ValueType> storage1(ref1.begin(), ref1.end());
- ListType ifl;
- ifl.assign(storage1.begin(), storage1.end());
- ASSERT_LISTS_EQUAL(ref1, ifl);
- std::forward_list<int> ref2({ 7, 1, 3 });
- std::vector<ValueType> storage2(ref2.begin(), ref2.end());
- ifl.assign(storage2.begin(), storage2.end());
- ASSERT_LISTS_EQUAL(ref2, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, Assign) {
- Assign<IFLTestValueList>();
- Assign<ConstIFLTestValueList>();
- Assign<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::PushPop() {
- using ValueType = typename ListType::value_type;
- ValueType value3(3);
- ValueType value7(7);
- std::forward_list<int> ref;
- ListType ifl;
- ASSERT_LISTS_EQUAL(ref, ifl);
- ref.push_front(3);
- ifl.push_front(value3);
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(3, ifl.front());
- ref.push_front(7);
- ifl.push_front(value7);
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(7, ifl.front());
- ref.pop_front();
- ifl.pop_front();
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(3, ifl.front());
- ref.pop_front();
- ifl.pop_front();
- ASSERT_LISTS_EQUAL(ref, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, PushPop) {
- PushPop<IFLTestValueList>();
- PushPop<ConstIFLTestValueList>();
- PushPop<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::InsertAfter1() {
- using ValueType = typename ListType::value_type;
- ValueType value4(4);
- ValueType value8(8);
- ValueType value5(5);
- ValueType value3(3);
- std::forward_list<int> ref;
- ListType ifl;
-
- auto ref_it = ref.insert_after(ref.before_begin(), 4);
- auto ifl_it = ifl.insert_after(ifl.before_begin(), value4);
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(*ref_it, *ifl_it);
- CHECK(ref_it == ref.begin());
- ASSERT_TRUE(ifl_it == ifl.begin());
-
- ref_it = ref.insert_after(ref.begin(), 8);
- ifl_it = ifl.insert_after(ifl.begin(), value8);
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(*ref_it, *ifl_it);
- CHECK(ref_it != ref.end());
- ASSERT_TRUE(ifl_it != ifl.end());
- CHECK(++ref_it == ref.end());
- ASSERT_TRUE(++ifl_it == ifl.end());
-
- ref_it = ref.insert_after(ref.begin(), 5);
- ifl_it = ifl.insert_after(ifl.begin(), value5);
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(*ref_it, *ifl_it);
-
- ref_it = ref.insert_after(ref_it, 3);
- ifl_it = ifl.insert_after(ifl_it, value3);
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(*ref_it, *ifl_it);
-}
-
-TEST_F(IntrusiveForwardListTest, InsertAfter1) {
- InsertAfter1<IFLTestValueList>();
- InsertAfter1<ConstIFLTestValueList>();
- InsertAfter1<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::InsertAfter2() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref;
- ListType ifl;
-
- auto ref_it = ref.insert_after(ref.before_begin(), { 2, 8, 5 });
- std::vector<ValueType> storage1({ { 2 }, { 8 }, { 5 } });
- auto ifl_it = ifl.insert_after(ifl.before_begin(), storage1.begin(), storage1.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(*ref_it, *ifl_it);
-
- std::vector<ValueType> storage2({ { 7 }, { 2 } });
- ref_it = ref.insert_after(ref.begin(), { 7, 2 });
- ifl_it = ifl.insert_after(ifl.begin(), storage2.begin(), storage2.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(*ref_it, *ifl_it);
-
- std::vector<ValueType> storage3({ { 1 }, { 3 }, { 4 }, { 9 } });
- ref_it = ref.begin();
- ifl_it = ifl.begin();
- std::advance(ref_it, std::distance(ref.begin(), ref.end()) - 1);
- std::advance(ifl_it, std::distance(ifl.begin(), ifl.end()) - 1);
- ref_it = ref.insert_after(ref_it, { 1, 3, 4, 9 });
- ifl_it = ifl.insert_after(ifl_it, storage3.begin(), storage3.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, InsertAfter2) {
- InsertAfter2<IFLTestValueList>();
- InsertAfter2<ConstIFLTestValueList>();
- InsertAfter2<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::EraseAfter1() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 1, 2, 7, 4, 5 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 5);
-
- auto ref_it = ref.begin();
- auto ifl_it = ifl.begin();
- std::advance(ref_it, 2);
- std::advance(ifl_it, 2);
- ref_it = ref.erase_after(ref_it);
- ifl_it = ifl.erase_after(ifl_it);
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 4);
- CHECK(ref_it != ref.end());
- ASSERT_TRUE(ifl_it != ifl.end());
- CHECK(++ref_it == ref.end());
- ASSERT_TRUE(++ifl_it == ifl.end());
-
- ref_it = ref.begin();
- ifl_it = ifl.begin();
- std::advance(ref_it, 2);
- std::advance(ifl_it, 2);
- ref_it = ref.erase_after(ref_it);
- ifl_it = ifl.erase_after(ifl_it);
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 3);
- CHECK(ref_it == ref.end());
- ASSERT_TRUE(ifl_it == ifl.end());
-
- ref_it = ref.erase_after(ref.begin());
- ifl_it = ifl.erase_after(ifl.begin());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
- CHECK(ref_it != ref.end());
- ASSERT_TRUE(ifl_it != ifl.end());
- CHECK(++ref_it == ref.end());
- ASSERT_TRUE(++ifl_it == ifl.end());
-
- ref_it = ref.erase_after(ref.before_begin());
- ifl_it = ifl.erase_after(ifl.before_begin());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 1);
- CHECK(ref_it == ref.begin());
- ASSERT_TRUE(ifl_it == ifl.begin());
-
- ref_it = ref.erase_after(ref.before_begin());
- ifl_it = ifl.erase_after(ifl.before_begin());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
- CHECK(ref_it == ref.begin());
- ASSERT_TRUE(ifl_it == ifl.begin());
-}
-
-TEST_F(IntrusiveForwardListTest, EraseAfter1) {
- EraseAfter1<IFLTestValueList>();
- EraseAfter1<ConstIFLTestValueList>();
- EraseAfter1<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::EraseAfter2() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 1, 2, 7, 4, 5, 3, 2, 8, 9 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 9);
-
- auto ref_it = ref.begin();
- auto ifl_it = ifl.begin();
- std::advance(ref_it, 3);
- std::advance(ifl_it, 3);
- ref_it = ref.erase_after(ref.begin(), ref_it);
- ifl_it = ifl.erase_after(ifl.begin(), ifl_it);
- ASSERT_LISTS_EQUAL(ref, ifl);
- ASSERT_EQ(std::distance(ref.begin(), ref_it), std::distance(ifl.begin(), ifl_it));
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 7);
-
- ref_it = ref.erase_after(ref_it, ref.end());
- ifl_it = ifl.erase_after(ifl_it, ifl.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK(ref_it == ref.end());
- ASSERT_TRUE(ifl_it == ifl.end());
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 2);
-
- ref_it = ref.erase_after(ref.before_begin(), ref.end());
- ifl_it = ifl.erase_after(ifl.before_begin(), ifl.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK(ref_it == ref.end());
- ASSERT_TRUE(ifl_it == ifl.end());
- CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
-}
-
-TEST_F(IntrusiveForwardListTest, EraseAfter2) {
- EraseAfter2<IFLTestValueList>();
- EraseAfter2<ConstIFLTestValueList>();
- EraseAfter2<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::SwapClear() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref1({ 1, 2, 7 });
- std::vector<ValueType> storage1(ref1.begin(), ref1.end());
- ListType ifl1(storage1.begin(), storage1.end());
- std::forward_list<int> ref2({ 3, 8, 6 });
- std::vector<ValueType> storage2(ref2.begin(), ref2.end());
- ListType ifl2(storage2.begin(), storage2.end());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
- ref1.swap(ref2);
- ifl1.swap(ifl2);
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
- ref1.clear();
- ifl1.clear();
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
- swap(ref1, ref2);
- swap(ifl1, ifl2);
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
- ref1.clear();
- ifl1.clear();
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-}
-
-TEST_F(IntrusiveForwardListTest, SwapClear) {
- SwapClear<IFLTestValueList>();
- SwapClear<ConstIFLTestValueList>();
- SwapClear<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::SpliceAfter() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref1({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
- std::forward_list<int> ref2;
- std::vector<ValueType> storage(ref1.begin(), ref1.end());
- ListType ifl1(storage.begin(), storage.end());
- ListType ifl2;
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-
- // Move everything to ref2/ifl2.
- ref2.splice_after(ref2.before_begin(), ref1);
- ifl2.splice_after(ifl2.before_begin(), ifl1);
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-
- // Move first element (3) to ref1/ifl1.
- ref1.splice_after(ref1.before_begin(), ref2, ref2.before_begin());
- ifl1.splice_after(ifl1.before_begin(), ifl2, ifl2.before_begin());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-
- // Move second element (2) to ref1/ifl1 after the first element (3).
- ref1.splice_after(ref1.begin(), ref2, ref2.begin());
- ifl1.splice_after(ifl1.begin(), ifl2, ifl2.begin());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-
- // Move everything from ref2/ifl2 between the 2 elements now in ref1/ifl1.
- ref1.splice_after(ref1.begin(), ref2);
- ifl1.splice_after(ifl1.begin(), ifl2);
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-
- std::forward_list<int> check({ 3, 1, 7, 4, 5, 4, 8, 7, 2 });
- ASSERT_LISTS_EQUAL(check, ifl1);
- ASSERT_TRUE(ifl2.empty());
-
- // Empty splice_after().
- ref2.splice_after(
- ref2.before_begin(), ref1, ref1.before_begin(), ref1.begin());
- ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.before_begin(), ifl1.begin());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-
- // Move { 1, 7 } to ref2/ifl2.
- auto ref_it = ref1.begin();
- auto ifl_it = ifl1.begin();
- std::advance(ref_it, 3);
- std::advance(ifl_it, 3);
- ref2.splice_after(ref2.before_begin(), ref1, ref1.begin(), ref_it);
- ifl2.splice_after(ifl2.before_begin(), ifl1, ifl1.begin(), ifl_it);
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-
- // Move { 8, 7, 2 } to the beginning of ref1/ifl1.
- ref_it = ref1.begin();
- ifl_it = ifl1.begin();
- std::advance(ref_it, 3);
- std::advance(ifl_it, 3);
- ref1.splice_after(ref1.before_begin(), ref1, ref_it, ref1.end());
- ifl1.splice_after(ifl1.before_begin(), ifl1, ifl_it, ifl1.end());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
-
- check.assign({ 8, 7, 2, 3, 4, 5, 4 });
- ASSERT_LISTS_EQUAL(check, ifl1);
- check.assign({ 1, 7 });
- ASSERT_LISTS_EQUAL(check, ifl2);
-
- // Move all but the first element to ref2/ifl2.
- ref_it = ref2.begin();
- ifl_it = ifl2.begin();
- std::advance(ref_it, 1);
- std::advance(ifl_it, 1);
- ref2.splice_after(ref_it, ref1, ref1.begin(), ref1.end());
- ifl2.splice_after(ifl_it, ifl1, ifl1.begin(), ifl1.end());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
-
- check.assign({8});
- ASSERT_LISTS_EQUAL(check, ifl1);
-
- // Move the first element of ref1/ifl1 to the beginning of ref1/ifl1 (do nothing).
- ref1.splice_after(ref1.before_begin(), ref1, ref1.before_begin());
- ifl1.splice_after(ifl1.before_begin(), ifl1, ifl1.before_begin());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(check, ifl1);
-
- // Move the first element of ref2/ifl2 after itself (do nothing).
- ref1.splice_after(ref1.begin(), ref1, ref1.before_begin());
- ifl1.splice_after(ifl1.begin(), ifl1, ifl1.before_begin());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(check, ifl1);
-
- check.assign({ 1, 7, 7, 2, 3, 4, 5, 4 });
- ASSERT_LISTS_EQUAL(check, ifl2);
-
- // Move the first element of ref2/ifl2 to the beginning of ref2/ifl2 (do nothing).
- ref2.splice_after(ref2.before_begin(), ref2, ref2.before_begin());
- ifl2.splice_after(ifl2.before_begin(), ifl2, ifl2.before_begin());
- ASSERT_LISTS_EQUAL(ref2, ifl2);
- ASSERT_LISTS_EQUAL(check, ifl2);
-
- // Move the first element of ref2/ifl2 after itself (do nothing).
- ref2.splice_after(ref2.begin(), ref2, ref2.before_begin());
- ifl2.splice_after(ifl2.begin(), ifl2, ifl2.before_begin());
- ASSERT_LISTS_EQUAL(ref2, ifl2);
- ASSERT_LISTS_EQUAL(check, ifl2);
-}
-
-TEST_F(IntrusiveForwardListTest, SpliceAfter) {
- SpliceAfter<IFLTestValueList>();
- SpliceAfter<ConstIFLTestValueList>();
- SpliceAfter<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::Remove() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- ref.remove(1);
- ifl.remove(1);
- ASSERT_LISTS_EQUAL(ref, ifl);
- ref.remove(4);
- ifl.remove(4);
- ASSERT_LISTS_EQUAL(ref, ifl);
- auto odd = [](ValueType value) { return (value.value & 1) != 0; };
- ref.remove_if(odd);
- ifl.remove_if(odd);
- ASSERT_LISTS_EQUAL(ref, ifl);
- auto all = [](ValueType value ATTRIBUTE_UNUSED) { return true; };
- ref.remove_if(all);
- ifl.remove_if(all);
- ASSERT_LISTS_EQUAL(ref, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, Remove) {
- Remove<IFLTestValueList>();
- Remove<ConstIFLTestValueList>();
- Remove<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::Unique() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 3, 1, 1, 2, 3, 3, 7, 7, 4, 4, 5, 7 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- ref.unique();
- ifl.unique();
- ASSERT_LISTS_EQUAL(ref, ifl);
- std::forward_list<int> check({ 3, 1, 2, 3, 7, 4, 5, 7 });
- ASSERT_LISTS_EQUAL(check, ifl);
-
- auto bin_pred = [](const ValueType& lhs, const ValueType& rhs) {
- return (lhs.value & ~1) == (rhs.value & ~1);
- };
- ref.unique(bin_pred);
- ifl.unique(bin_pred);
- ASSERT_LISTS_EQUAL(ref, ifl);
- check.assign({ 3, 1, 2, 7, 4, 7 });
- ASSERT_LISTS_EQUAL(check, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, Unique) {
- Unique<IFLTestValueList>();
- Unique<ConstIFLTestValueList>();
- Unique<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::Merge() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref1({ 1, 4, 8, 8, 12 });
- std::vector<ValueType> storage1(ref1.begin(), ref1.end());
- ListType ifl1(storage1.begin(), storage1.end());
- std::forward_list<int> ref2({ 3, 5, 6, 7, 9 });
- std::vector<ValueType> storage2(ref2.begin(), ref2.end());
- ListType ifl2(storage2.begin(), storage2.end());
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
- CHECK(std::is_sorted(ref1.begin(), ref1.end()));
- CHECK(std::is_sorted(ref2.begin(), ref2.end()));
- ref1.merge(ref2);
- ifl1.merge(ifl2);
- ASSERT_LISTS_EQUAL(ref1, ifl1);
- ASSERT_LISTS_EQUAL(ref2, ifl2);
- CHECK(ref2.empty());
- std::forward_list<int> check({ 1, 3, 4, 5, 6, 7, 8, 8, 9, 12 });
- ASSERT_LISTS_EQUAL(check, ifl1);
-}
-
-TEST_F(IntrusiveForwardListTest, Merge) {
- Merge<IFLTestValueList>();
- Merge<ConstIFLTestValueList>();
- Merge<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::Sort1() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK(!std::is_sorted(ref.begin(), ref.end()));
- ref.sort();
- ifl.sort();
- ASSERT_LISTS_EQUAL(ref, ifl);
- std::forward_list<int> check({ 0, 1, 2, 3, 3, 4, 5, 7, 8, 9 });
- ASSERT_LISTS_EQUAL(check, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, Sort1) {
- Sort1<IFLTestValueList>();
- Sort1<ConstIFLTestValueList>();
- Sort1<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::Sort2() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- auto cmp = [](const ValueType& lhs, const ValueType& rhs) {
- return (lhs.value & ~1) < (rhs.value & ~1);
- };
- CHECK(!std::is_sorted(ref.begin(), ref.end(), cmp));
- ref.sort(cmp);
- ifl.sort(cmp);
- ASSERT_LISTS_EQUAL(ref, ifl);
- std::forward_list<int> check({ 1, 0, 2, 3, 3, 4, 5, 7, 9, 8 });
- ASSERT_LISTS_EQUAL(check, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, Sort2) {
- Sort2<IFLTestValueList>();
- Sort2<ConstIFLTestValueList>();
- Sort2<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::Reverse() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 8, 3, 5, 4, 1, 3 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
- CHECK(!std::is_sorted(ref.begin(), ref.end()));
- ref.reverse();
- ifl.reverse();
- ASSERT_LISTS_EQUAL(ref, ifl);
- std::forward_list<int> check({ 3, 1, 4, 5, 3, 8 });
- ASSERT_LISTS_EQUAL(check, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, Reverse) {
- Reverse<IFLTestValueList>();
- Reverse<ConstIFLTestValueList>();
- Reverse<IFLTestValue2List>();
-}
-
-template <typename ListType>
-void IntrusiveForwardListTest::ModifyValue() {
- using ValueType = typename ListType::value_type;
- std::forward_list<int> ref({ 3, 7, 42 });
- std::vector<ValueType> storage(ref.begin(), ref.end());
- ListType ifl(storage.begin(), storage.end());
- ASSERT_LISTS_EQUAL(ref, ifl);
-
- auto add1 = [](const ValueType& value) { return value.value + 1; };
- std::transform(ref.begin(), ref.end(), ref.begin(), add1);
- std::transform(ifl.begin(), ifl.end(), ifl.begin(), add1);
- ASSERT_LISTS_EQUAL(ref, ifl);
-}
-
-TEST_F(IntrusiveForwardListTest, ModifyValue) {
- ModifyValue<IFLTestValueList>();
- // Does not compile with ConstIFLTestValueList because LHS of the assignment is const.
- // ModifyValue<ConstIFLTestValueList>();
- static_assert(std::is_const<ConstIFLTestValueList::iterator::value_type>::value, "Const check.");
- ModifyValue<IFLTestValue2List>();
-}
-
-struct Tag1;
-struct Tag2;
-struct TwoListsValue : public IntrusiveForwardListNode<TwoListsValue, Tag1>,
- public IntrusiveForwardListNode<TwoListsValue, Tag2> {
- // Deliberately not explicit.
- TwoListsValue(int v) : value(v) { } // NOLINT(runtime/explicit)
-
- int value;
-};
-using FirstList =
- IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag1>>;
-using SecondList =
- IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag2>>;
-
-bool operator==(const TwoListsValue& lhs, const TwoListsValue& rhs) {
- return lhs.value == rhs.value;
-}
-
-TEST_F(IntrusiveForwardListTest, TwoLists) {
- // Test that a value can be in two lists at the same time and the hooks do not interfere.
- std::vector<TwoListsValue> storage({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }); // storage[i] = i
-
- std::vector<int> order1({ 3, 1, 7, 2, 8, 9, 4, 0, 6, 5 });
- FirstList list1;
- auto pos1 = list1.before_begin();
- for (size_t idx : order1) {
- pos1 = list1.insert_after(pos1, storage[idx]);
- }
-
- std::vector<int> order2({ 8, 5, 1, 6, 7, 2, 9, 3, 0, 4 });
- SecondList list2;
- auto pos2 = list2.before_begin();
- for (size_t idx : order2) {
- pos2 = list2.insert_after(pos2, storage[idx]);
- }
-
- // Using `storage[i] = i`, we can easily compare that nodes of each list are in the right order.
- ASSERT_LISTS_EQUAL(order1, list1);
- ASSERT_LISTS_EQUAL(order2, list2);
-}
-
-} // namespace art