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;
VerificationBaseVerificationBase31 VerificationBase() : m_Canary(NoliMeTangere) {}
32 }; // struct VerificationBase
33
34 struct DataItemWithInheritedNodeBase : intrusive_list_node {
35 int m_Data;
36
DataItemWithInheritedNodeBaseDataItemWithInheritedNodeBase37 DataItemWithInheritedNodeBase( int value ) : m_Data(value) {}
38
DataDataItemWithInheritedNodeBase39 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
DataItemWithInheritedNodeDataItemWithInheritedNode45 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
DataItemWithMemberNodeBaseDataItemWithMemberNodeBase54 DataItemWithMemberNodeBase( int value ) : m_Data(value) {}
55
DataDataItemWithMemberNodeBase56 int Data() const { return m_Data; }
57 }; // struct DataItemWithMemberNodeBase
58
59 struct DataItemWithMemberNodes : VerificationBase, DataItemWithMemberNodeBase {
60 intrusive_list_node m_Node;
61
DataItemWithMemberNodesDataItemWithMemberNodes62 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>
check_list_nodes(List & il,int value_step)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>
test_list_operations()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