1/*
2 Copyright (c) 2005-2019 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#define HARNESS_NO_PARSE_COMMAND_LINE 1
18#include "harness.h"
19
20#include "../tbb/intrusive_list.h"
21
22using tbb::internal::intrusive_list_node;
23
24// Machine word filled with repeated pattern of FC bits
25const uintptr_t NoliMeTangere = ~uintptr_t(0)/0xFF*0xFC;
26
27struct VerificationBase : Harness::NoAfterlife {
28 uintptr_t m_Canary;
29 VerificationBase () : m_Canary(NoliMeTangere) {}
30};
31
32struct DataItemWithInheritedNodeBase : intrusive_list_node {
33 int m_Data;
34public:
35 DataItemWithInheritedNodeBase ( int value ) : m_Data(value) {}
36
37 int Data() const { return m_Data; }
38};
39
40class DataItemWithInheritedNode : public VerificationBase, public DataItemWithInheritedNodeBase {
41 friend class tbb::internal::intrusive_list<DataItemWithInheritedNode>;
42public:
43 DataItemWithInheritedNode ( int value ) : DataItemWithInheritedNodeBase(value) {}
44};
45
46struct DataItemWithMemberNodeBase {
47 int m_Data;
48public:
49 // Cannot be used by member_intrusive_list to form lists of objects derived from DataItemBase
50 intrusive_list_node m_BaseNode;
51
52 DataItemWithMemberNodeBase ( int value ) : m_Data(value) {}
53
54 int Data() const { return m_Data; }
55};
56
57class DataItemWithMemberNodes : public VerificationBase, public DataItemWithMemberNodeBase {
58public:
59 intrusive_list_node m_Node;
60
61 DataItemWithMemberNodes ( int value ) : DataItemWithMemberNodeBase(value) {}
62};
63
64typedef tbb::internal::intrusive_list<DataItemWithInheritedNode> IntrusiveList1;
65typedef tbb::internal::memptr_intrusive_list<DataItemWithMemberNodes,
66 DataItemWithMemberNodeBase, &DataItemWithMemberNodeBase::m_BaseNode> IntrusiveList2;
67typedef tbb::internal::memptr_intrusive_list<DataItemWithMemberNodes,
68 DataItemWithMemberNodes, &DataItemWithMemberNodes::m_Node> IntrusiveList3;
69
70const int NumElements = 256 * 1024;
71
72//! Iterates through the list forward and backward checking the validity of values stored by the list nodes
73template<class List, class Iterator>
74void CheckListNodes ( List& il, int valueStep ) {
75 ASSERT( il.size()==unsigned(NumElements/valueStep), "Wrong size of the list" );
76 ASSERT( !il.empty(), "Incorrect result of empty() or the list is corrupted" );
77 int i;
78 Iterator it = il.begin();
79 for ( i = valueStep - 1; it != il.end(); ++it, i += valueStep ) {
80 ASSERT( it->Data() == i, "Unexpected node value while iterating forward" );
81 ASSERT( (*it).m_Canary == NoliMeTangere, "Memory corruption" );
82 }
83 ASSERT( i == NumElements + valueStep - 1, "Wrong number of list elements while iterating forward" );
84 it = il.end();
85 for ( i = NumElements - 1, it--; it != il.end(); --it, i -= valueStep ) {
86 ASSERT( (*it).Data() == i, "Unexpected node value while iterating backward" );
87 ASSERT( it->m_Canary == NoliMeTangere, "Memory corruption" );
88 }
89 ASSERT( i == -1, "Wrong number of list elements while iterating backward" );
90}
91
92template<class List, class Item>
93void TestListOperations () {
94 typedef typename List::iterator iterator;
95 List il;
96 for ( int i = NumElements - 1; i >= 0; --i )
97 il.push_front( *new Item(i) );
98 CheckListNodes<const List, typename List::const_iterator>( il, 1 );
99 iterator it = il.begin();
100 for ( ; it != il.end(); ++it ) {
101 Item &item = *it;
102 it = il.erase( it ); // also advances the iterator
103 delete &item;
104 }
105 CheckListNodes<List, iterator>( il, 2 );
106 for ( it = il.begin(); it != il.end(); ++it ) {
107 Item &item = *it;
108 il.remove( *it++ ); // extra advance here as well
109 delete &item;
110 }
111 CheckListNodes<List, iterator>( il, 4 );
112 for ( it = il.begin(); it != il.end(); ) {
113 Item &item = *it++; // the iterator advances only here
114 il.remove( item );
115 delete &item;
116 }
117 ASSERT( il.size()==0, "The list has wrong size or not all items were removed" );
118 ASSERT( il.empty(), "Incorrect result of empty() or not all items were removed" );
119}
120
121#include "harness_bad_expr.h"
122
123template<class List, class Item>
124void TestListAssertions () {
125#if TRY_BAD_EXPR_ENABLED
126 tbb::set_assertion_handler( AssertionFailureHandler );
127 List il1, il2;
128 Item n1(1), n2(2), n3(3);
129 il1.push_front(n1);
130 TRY_BAD_EXPR( il2.push_front(n1), "only one intrusive list" );
131 TRY_BAD_EXPR( il1.push_front(n1), "only one intrusive list" );
132 il2.push_front(n2);
133 TRY_BAD_EXPR( il1.remove(n3), "not in the list" );
134 tbb::set_assertion_handler( ReportError );
135#endif /* TRY_BAD_EXPR_ENABLED */
136}
137
138int TestMain () {
139 TestListOperations<IntrusiveList1, DataItemWithInheritedNode>();
140 TestListOperations<IntrusiveList2, DataItemWithMemberNodes>();
141 TestListOperations<IntrusiveList3, DataItemWithMemberNodes>();
142 TestListAssertions<IntrusiveList1, DataItemWithInheritedNode>();
143 TestListAssertions<IntrusiveList2, DataItemWithMemberNodes>();
144 TestListAssertions<IntrusiveList3, DataItemWithMemberNodes>();
145 return Harness::Done;
146}
147