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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
/***************************************************************************
* tests/containers/test_stack.cpp
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2003 Roman Dementiev <dementiev@mpi-sb.mpg.de>
* Copyright (C) 2010 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
//! \example containers/test_stack.cpp
//! This is an example of how to use \c stxxl::STACK_GENERATOR class
//! to generate an \b external stack type
//! with \c stxxl::grow_shrink_stack implementation, \b four blocks per page,
//! block size \b 4096 bytes
#include <stxxl/stack>
// forced instantiation
template class stxxl::STACK_GENERATOR<size_t, stxxl::external, stxxl::normal, 4, 4096>;
template class stxxl::STACK_GENERATOR<size_t, stxxl::migrating, stxxl::normal, 4, 4096>;
template class stxxl::STACK_GENERATOR<size_t, stxxl::external, stxxl::grow_shrink, 4, 4096>;
template class stxxl::STACK_GENERATOR<size_t, stxxl::external, stxxl::grow_shrink2, 1, 4096>;
template <typename stack_type>
void test_lvalue_correctness(stack_type& stack, int a, int b)
{
int i;
STXXL_CHECK(stack.empty());
for (i = 0; i < a; ++i)
stack.push(i);
for (i = 0; i < b; ++i)
stack.push(i);
for (i = 0; i < b; ++i)
stack.pop();
stack.top() = 0xbeeff00d;
for (i = 0; i < b; ++i)
stack.push(i);
for (i = 0; i < b; ++i)
stack.pop();
if ((stack.top() != (size_t)(0xbeeff00d))) {
STXXL_ERRMSG("STACK MISMATCH AFTER top() LVALUE MODIFICATION (0x" << std::hex << stack.top() << " != 0xbeeff00d)");
STXXL_CHECK(stack.top() == (size_t)(0xbeeff00d));
}
for (i = 0; i < a; ++i)
stack.pop();
}
template <typename stack_type>
void simple_test(stack_type& my_stack, size_t test_size)
{
for (size_t i = 0; i < test_size; i++)
{
my_stack.push(i);
STXXL_CHECK(my_stack.top() == i);
STXXL_CHECK(my_stack.size() == i + 1);
}
for (size_t i = test_size; i > 0; )
{
--i;
STXXL_CHECK(my_stack.top() == i);
my_stack.pop();
STXXL_CHECK(my_stack.size() == i);
}
for (size_t i = 0; i < test_size; i++)
{
my_stack.push(i);
STXXL_CHECK(my_stack.top() == i);
STXXL_CHECK(my_stack.size() == i + 1);
}
// test swap
stack_type s2;
std::swap(s2, my_stack);
std::swap(s2, my_stack);
for (size_t i = test_size; i > 0; )
{
--i;
STXXL_CHECK(my_stack.top() == i);
my_stack.pop();
STXXL_CHECK(my_stack.size() == i);
}
std::stack<size_t> int_stack;
for (size_t i = 0; i < test_size; i++)
{
int_stack.push(i);
STXXL_CHECK(int_stack.top() == i);
STXXL_CHECK(int_stack.size() == i + 1);
}
stack_type my_stack1(int_stack);
for (size_t i = test_size; i > 0; )
{
--i;
STXXL_CHECK(my_stack1.top() == i);
my_stack1.pop();
STXXL_CHECK(my_stack1.size() == i);
}
STXXL_MSG("Test 1 passed.");
test_lvalue_correctness(my_stack, 4 * 4096 / 4 * 2, 4 * 4096 / 4 * 2 * 20);
}
int main(int argc, char* argv[])
{
typedef stxxl::STACK_GENERATOR<size_t, stxxl::external, stxxl::normal, 4, 4096>::result ext_normal_stack_type;
typedef stxxl::STACK_GENERATOR<size_t, stxxl::migrating, stxxl::normal, 4, 4096>::result ext_migrating_stack_type;
typedef stxxl::STACK_GENERATOR<size_t, stxxl::external, stxxl::grow_shrink, 4, 4096>::result ext_stack_type;
typedef stxxl::STACK_GENERATOR<size_t, stxxl::external, stxxl::grow_shrink2, 1, 4096>::result ext_stack_type2;
if (argc < 2)
{
STXXL_MSG("Usage: " << argv[0] << " test_size_in_pages");
return -1;
}
{
ext_normal_stack_type my_stack;
simple_test(my_stack, atoi(argv[1]) * 4 * 4096 / sizeof(int));
}
{
ext_migrating_stack_type my_stack;
//simple_test(my_stack, atoi(argv[1]) * 4 * 4096 / sizeof(int));
}
{
ext_stack_type my_stack;
simple_test(my_stack, atoi(argv[1]) * 4 * 4096 / sizeof(int));
}
{
// prefetch/write pool with 10 blocks prefetching and 10 block write cache (> D is recommended)
stxxl::read_write_pool<ext_stack_type2::block_type> pool(10, 10);
// create a stack that does not prefetch (level of prefetch aggressiveness 0)
ext_stack_type2 my_stack(pool, 0);
size_t test_size = atoi(argv[1]) * 4 * 4096 / sizeof(int);
for (size_t i = 0; i < test_size; i++)
{
my_stack.push(i);
STXXL_CHECK(my_stack.top() == i);
STXXL_CHECK(my_stack.size() == i + 1);
}
my_stack.set_prefetch_aggr(10);
for (size_t i = test_size; i > 0; )
{
--i;
STXXL_CHECK(my_stack.top() == i);
my_stack.pop();
STXXL_CHECK(my_stack.size() == i);
}
for (size_t i = 0; i < test_size; i++)
{
my_stack.push(i);
STXXL_CHECK(my_stack.top() == i);
STXXL_CHECK(my_stack.size() == i + 1);
}
// test swap
ext_stack_type2 s2(pool, 0);
std::swap(s2, my_stack);
std::swap(s2, my_stack);
for (size_t i = test_size; i > 0; )
{
--i;
STXXL_CHECK(my_stack.top() == i);
my_stack.pop();
STXXL_CHECK(my_stack.size() == i);
}
STXXL_MSG("Test 2 passed.");
test_lvalue_correctness(my_stack, 4 * 4096 / 4 * 2, 4 * 4096 / 4 * 2 * 20);
}
return 0;
}
// vim: et:ts=4:sw=4
|
