1//
2// LinearHashTableTest.cpp
3//
4// Copyright (c) 2006, Applied Informatics Software Engineering GmbH.
5// and Contributors.
6//
7// SPDX-License-Identifier: BSL-1.0
8//
9
10
11#include "LinearHashTableTest.h"
12#include "Poco/CppUnit/TestCaller.h"
13#include "Poco/CppUnit/TestSuite.h"
14#include "Poco/LinearHashTable.h"
15#include "Poco/HashTable.h"
16#include "Poco/Stopwatch.h"
17#include "Poco/NumberFormatter.h"
18#include <set>
19#include <iostream>
20
21
22using Poco::LinearHashTable;
23using Poco::Hash;
24using Poco::HashTable;
25using Poco::Stopwatch;
26using Poco::NumberFormatter;
27
28
29LinearHashTableTest::LinearHashTableTest(const std::string& rName): CppUnit::TestCase(rName)
30{
31}
32
33
34LinearHashTableTest::~LinearHashTableTest()
35{
36}
37
38
39void LinearHashTableTest::testInsert()
40{
41 const int N = 1000;
42
43 LinearHashTable<int, Hash<int> > ht;
44
45 assertTrue (ht.empty());
46
47 for (int i = 0; i < N; ++i)
48 {
49 std::pair<LinearHashTable<int, Hash<int> >::Iterator, bool> res = ht.insert(i);
50 assertTrue (*res.first == i);
51 assertTrue (res.second);
52 LinearHashTable<int, Hash<int> >::Iterator it = ht.find(i);
53 assertTrue (it != ht.end());
54 assertTrue (*it == i);
55 assertTrue (ht.size() == i + 1);
56 }
57 assertTrue (ht.buckets() == N + 1);
58
59 assertTrue (!ht.empty());
60
61 for (int i = 0; i < N; ++i)
62 {
63 LinearHashTable<int, Hash<int> >::Iterator it = ht.find(i);
64 assertTrue (it != ht.end());
65 assertTrue (*it == i);
66 }
67
68 for (int i = 0; i < N; ++i)
69 {
70 std::pair<LinearHashTable<int, Hash<int> >::Iterator, bool> res = ht.insert(i);
71 assertTrue (*res.first == i);
72 assertTrue (!res.second);
73 assertTrue (ht.size() == N);
74 assertTrue (ht.buckets() == N + 1);
75 }
76}
77
78
79void LinearHashTableTest::testErase()
80{
81 const int N = 1000;
82
83 LinearHashTable<int, Hash<int> > ht;
84
85 for (int i = 0; i < N; ++i)
86 {
87 ht.insert(i);
88 }
89 assertTrue (ht.size() == N);
90
91 for (int i = 0; i < N; i += 2)
92 {
93 ht.erase(i);
94 LinearHashTable<int, Hash<int> >::Iterator it = ht.find(i);
95 assertTrue (it == ht.end());
96 }
97 assertTrue (ht.size() == N/2);
98
99 for (int i = 0; i < N; i += 2)
100 {
101 LinearHashTable<int, Hash<int> >::Iterator it = ht.find(i);
102 assertTrue (it == ht.end());
103 }
104
105 for (int i = 1; i < N; i += 2)
106 {
107 LinearHashTable<int, Hash<int> >::Iterator it = ht.find(i);
108 assertTrue (it != ht.end());
109 assertTrue (*it == i);
110 }
111
112 for (int i = 0; i < N; i += 2)
113 {
114 ht.insert(i);
115 }
116
117 for (int i = 0; i < N; ++i)
118 {
119 LinearHashTable<int, Hash<int> >::Iterator it = ht.find(i);
120 assertTrue (it != ht.end());
121 assertTrue (*it == i);
122 }
123}
124
125
126void LinearHashTableTest::testIterator()
127{
128 const int N = 1000;
129
130 LinearHashTable<int, Hash<int> > ht;
131
132 for (int i = 0; i < N; ++i)
133 {
134 ht.insert(i);
135 }
136
137 std::set<int> values;
138 LinearHashTable<int, Hash<int> >::Iterator it = ht.begin();
139 while (it != ht.end())
140 {
141 assertTrue (values.find(*it) == values.end());
142 values.insert(*it);
143 ++it;
144 }
145
146 assertTrue (values.size() == N);
147}
148
149
150void LinearHashTableTest::testConstIterator()
151{
152 const int N = 1000;
153
154 LinearHashTable<int, Hash<int> > ht;
155
156 for (int i = 0; i < N; ++i)
157 {
158 ht.insert(i);
159 }
160
161 std::set<int> values;
162 LinearHashTable<int, Hash<int> >::ConstIterator it = ht.begin();
163 while (it != ht.end())
164 {
165 assertTrue (values.find(*it) == values.end());
166 values.insert(*it);
167 ++it;
168 }
169
170 assertTrue (values.size() == N);
171
172 values.clear();
173 const LinearHashTable<int, Hash<int> > cht(ht);
174
175 LinearHashTable<int, Hash<int> >::ConstIterator cit = cht.begin();
176 while (cit != cht.end())
177 {
178 assertTrue (values.find(*cit) == values.end());
179 values.insert(*cit);
180 ++cit;
181 }
182
183 assertTrue (values.size() == N);
184}
185
186
187void LinearHashTableTest::testPerformanceInt()
188{
189 const int N = 5000000;
190 Stopwatch sw;
191
192 {
193 LinearHashTable<int, Hash<int> > lht(N);
194 sw.start();
195 for (int i = 0; i < N; ++i)
196 {
197 lht.insert(i);
198 }
199 sw.stop();
200 std::cout << "Insert LHT: " << sw.elapsedSeconds() << std::endl;
201 sw.reset();
202
203 sw.start();
204 for (int i = 0; i < N; ++i)
205 {
206 lht.find(i);
207 }
208 sw.stop();
209 std::cout << "Find LHT: " << sw.elapsedSeconds() << std::endl;
210 sw.reset();
211 }
212
213 {
214 HashTable<int, int> ht;
215
216 sw.start();
217 for (int i = 0; i < N; ++i)
218 {
219 ht.insert(i, i);
220 }
221 sw.stop();
222 std::cout << "Insert HT: " << sw.elapsedSeconds() << std::endl;
223 sw.reset();
224
225 sw.start();
226 for (int i = 0; i < N; ++i)
227 {
228 ht.exists(i);
229 }
230 sw.stop();
231 std::cout << "Find HT: " << sw.elapsedSeconds() << std::endl;
232 }
233
234 {
235 std::set<int> s;
236 sw.start();
237 for (int i = 0; i < N; ++i)
238 {
239 s.insert(i);
240 }
241 sw.stop();
242 std::cout << "Insert set: " << sw.elapsedSeconds() << std::endl;
243 sw.reset();
244
245 sw.start();
246 for (int i = 0; i < N; ++i)
247 {
248 s.find(i);
249 }
250 sw.stop();
251 std::cout << "Find set: " << sw.elapsedSeconds() << std::endl;
252 sw.reset();
253 }
254
255}
256
257
258void LinearHashTableTest::testPerformanceStr()
259{
260 const int N = 5000000;
261 Stopwatch sw;
262
263 std::vector<std::string> values;
264 for (int i = 0; i < N; ++i)
265 {
266 values.push_back(NumberFormatter::format0(i, 8));
267 }
268
269 {
270 LinearHashTable<std::string, Hash<std::string> > lht(N);
271 sw.start();
272 for (int i = 0; i < N; ++i)
273 {
274 lht.insert(values[i]);
275 }
276 sw.stop();
277 std::cout << "Insert LHT: " << sw.elapsedSeconds() << std::endl;
278 sw.reset();
279
280 sw.start();
281 for (int i = 0; i < N; ++i)
282 {
283 lht.find(values[i]);
284 }
285 sw.stop();
286 std::cout << "Find LHT: " << sw.elapsedSeconds() << std::endl;
287 sw.reset();
288 }
289
290 {
291 HashTable<std::string, int> ht;
292
293 sw.start();
294 for (int i = 0; i < N; ++i)
295 {
296 ht.insert(values[i], i);
297 }
298 sw.stop();
299 std::cout << "Insert HT: " << sw.elapsedSeconds() << std::endl;
300 sw.reset();
301
302 sw.start();
303 for (int i = 0; i < N; ++i)
304 {
305 ht.exists(values[i]);
306 }
307 sw.stop();
308 std::cout << "Find HT: " << sw.elapsedSeconds() << std::endl;
309 }
310
311 {
312 std::set<std::string> s;
313 sw.start();
314 for (int i = 0; i < N; ++i)
315 {
316 s.insert(values[i]);
317 }
318 sw.stop();
319 std::cout << "Insert set: " << sw.elapsedSeconds() << std::endl;
320 sw.reset();
321
322 sw.start();
323 for (int i = 0; i < N; ++i)
324 {
325 s.find(values[i]);
326 }
327 sw.stop();
328 std::cout << "Find set: " << sw.elapsedSeconds() << std::endl;
329 sw.reset();
330 }
331}
332
333
334void LinearHashTableTest::setUp()
335{
336}
337
338
339void LinearHashTableTest::tearDown()
340{
341}
342
343
344CppUnit::Test* LinearHashTableTest::suite()
345{
346 CppUnit::TestSuite* pSuite = new CppUnit::TestSuite("LinearHashTableTest");
347
348 CppUnit_addTest(pSuite, LinearHashTableTest, testInsert);
349 CppUnit_addTest(pSuite, LinearHashTableTest, testErase);
350 CppUnit_addTest(pSuite, LinearHashTableTest, testIterator);
351 CppUnit_addTest(pSuite, LinearHashTableTest, testConstIterator);
352 //CppUnit_addTest(pSuite, LinearHashTableTest, testPerformanceInt);
353 //CppUnit_addTest(pSuite, LinearHashTableTest, testPerformanceStr);
354
355 return pSuite;
356}
357