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