1 /* 2 Copyright (c) 2005-2021 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 //! \file test_intrusive_list.cpp 18 //! \brief Test for [internal] functionality 19 20 #include "common/test.h" 21 #include "common/utils.h" 22 #include "../../src/tbb/intrusive_list.h" 23 24 using tbb::detail::r1::intrusive_list_node; 25 26 // Machine word filled with repeated pattern of FC bits 27 const uintptr_t NoliMeTangere = ~uintptr_t(0)/0xFF*0xFC; 28 29 struct VerificationBase : utils::NoAfterlife { 30 uintptr_t m_Canary; 31 VerificationBase() : m_Canary(NoliMeTangere) {} 32 }; // struct VerificationBase 33 34 struct DataItemWithInheritedNodeBase : intrusive_list_node { 35 int m_Data; 36 37 DataItemWithInheritedNodeBase( int value ) : m_Data(value) {} 38 39 int Data() const { return m_Data; } 40 }; // struct DataItemWithInheritedNodeBase 41 42 struct DataItemWithInheritedNode : VerificationBase, DataItemWithInheritedNodeBase { 43 friend class tbb::detail::r1::intrusive_list<DataItemWithInheritedNode>; 44 45 DataItemWithInheritedNode( int value ) : DataItemWithInheritedNodeBase(value) {} 46 }; // struct DataItemWithInheritedNode 47 48 struct DataItemWithMemberNodeBase { 49 int m_Data; 50 51 // Cannot be used be member_intrusive_list to form lists of objects derived from DataItemBase 52 intrusive_list_node m_BaseNode; 53 54 DataItemWithMemberNodeBase( int value ) : m_Data(value) {} 55 56 int Data() const { return m_Data; } 57 }; // struct DataItemWithMemberNodeBase 58 59 struct DataItemWithMemberNodes : VerificationBase, DataItemWithMemberNodeBase { 60 intrusive_list_node m_Node; 61 62 DataItemWithMemberNodes( int value ) : DataItemWithMemberNodeBase(value) {} 63 }; // struct DataItemWithMemberNodes 64 65 using intrusive_list1 = tbb::detail::r1::intrusive_list<DataItemWithInheritedNode>; 66 using intrusive_list2 = tbb::detail::r1::memptr_intrusive_list<DataItemWithMemberNodes, 67 DataItemWithMemberNodeBase, 68 &DataItemWithMemberNodeBase::m_BaseNode>; 69 70 using intrusive_list3 = tbb::detail::r1::memptr_intrusive_list<DataItemWithMemberNodes, 71 DataItemWithMemberNodes, 72 &DataItemWithMemberNodes::m_Node>; 73 74 const int NumElements = 256 * 1024; 75 76 // Iterates through the list forward and backward checking the validity of values stored by the list nodes 77 template <typename List, typename Iterator> 78 void check_list_nodes( List& il, int value_step ) { 79 REQUIRE_MESSAGE(il.size() == unsigned(NumElements / value_step), "Wrong size of the list"); 80 REQUIRE_MESSAGE(!il.empty(), "Incorrect result of empty() or the list is corrupted"); 81 82 int i; 83 Iterator it = il.begin(); 84 85 Iterator it_default; 86 REQUIRE_MESSAGE(it_default != it, "Incorrect default constructed intrusive_list::iterator"); 87 88 for ( i = value_step - 1; it != il.end(); ++it, i += value_step ) { 89 REQUIRE_MESSAGE(it->Data() == i, "Unexpected node value while iterating forward"); 90 REQUIRE_MESSAGE(it->m_Canary == NoliMeTangere, "Memory corruption"); 91 } 92 93 REQUIRE_MESSAGE(i == NumElements + value_step - 1, "Wrong number of list elements while iterating forward"); 94 it = il.end(); 95 96 for ( i = NumElements - 1, it--; it != il.end(); --it, i -= value_step ) { 97 REQUIRE_MESSAGE(it->Data() == i, "Unexpected node value while iterating backward"); 98 REQUIRE_MESSAGE(it->m_Canary == NoliMeTangere, "Memory corruption"); 99 } 100 REQUIRE_MESSAGE(i == -1, "Wrong number of list elements while iterating backward"); 101 } 102 103 template <typename List, typename Item> 104 void test_list_operations() { 105 using iterator = typename List::iterator; 106 107 List il; 108 109 for (int i = NumElements - 1; i >= 0; --i) { 110 il.push_front(*new Item(i)); 111 } 112 check_list_nodes<const List, typename List::const_iterator>(il, 1); 113 iterator it = il.begin(); 114 115 for (;it != il.end(); ++it) { 116 Item& item = *it; 117 it = il.erase(it); // also advances the iterator 118 delete &item; 119 } 120 121 check_list_nodes<List, iterator>(il, 2); 122 for (it = il.begin(); it != il.end(); ++it) { 123 Item& item = *it; 124 il.remove(*it++); // extra advance here as well 125 delete &item; 126 } 127 128 check_list_nodes<List, iterator>(il, 4); 129 for (it = il.begin(); it != il.end();) { 130 Item& item = *it++; // the iterator advances only here 131 il.remove(item); 132 delete &item; 133 } 134 REQUIRE_MESSAGE(il.size() == 0, "The list has wrong size or not all items were removed"); 135 REQUIRE_MESSAGE(il.empty(), "Incorrect result of empty() or not all items were removed"); 136 } 137 138 // TODO: tests for intrusive_list assertions were not ported 139 140 //! \brief \ref error_guessing 141 TEST_CASE("Test tbb::detail::r1::intrusive_list operations") { 142 test_list_operations<intrusive_list1, DataItemWithInheritedNode>(); 143 } 144 145 //! \brief \ref error_guessing 146 TEST_CASE("Test tbb::detail::r1::memptr_intrusive_list operations") { 147 test_list_operations<intrusive_list2, DataItemWithMemberNodes>(); 148 test_list_operations<intrusive_list3, DataItemWithMemberNodes>(); 149 } 150