1 #include <cppunit/TestAssert.h>
2 #include <cppunit/TestCaller.h>
3 #include <cppunit/TestSuite.h>
4 #include <TestShell.h>
5
6 #include <os/support/ObjectList.h>
7 #include <shared/AutoDeleter.h>
8 #include <util/OpenHashTable.h>
9
10 #include "BOpenHashTableTest.h"
11
12
13 namespace {
14
15 class Entry {
16 public:
Entry(uint32_t value)17 Entry(uint32_t value)
18 :
19 fValue(value),
20 fNext(NULL)
21 {
22 }
23
Value() const24 const uint32_t Value() const
25 {
26 return fValue;
27 }
28
Next() const29 Entry* Next() const
30 {
31 return fNext;
32 }
33
34 private:
35 uint32_t fValue;
36 Entry *fNext;
37
38 friend class EntryDefinition;
39 };
40
41
42 class EntryDefinition {
43 public:
44 typedef uint32_t KeyType;
45 typedef Entry ValueType;
46
HashKey(const KeyType & key) const47 size_t HashKey(const KeyType& key) const
48 {
49 return key;
50 }
51
Hash(Entry * entry) const52 size_t Hash(Entry* entry) const
53 {
54 return entry->fValue;
55 }
56
Compare(const KeyType & key,Entry * entry) const57 bool Compare(const KeyType& key, Entry* entry) const
58 {
59 return key == entry->fValue;
60 }
61
GetLink(Entry * entry) const62 Entry*& GetLink(Entry* entry) const
63 {
64 return entry->fNext;
65 }
66 };
67
68 }
69
70
Suite()71 CppUnit::Test* BOpenHashTableTest::Suite()
72 {
73 CppUnit::TestSuite* suite = new CppUnit::TestSuite("BOpenHashTable");
74
75 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
76 "BOpenHashTable::Insert test",
77 &BOpenHashTableTest::InsertTest));
78 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
79 "BOpenHashTable::Insert unchecked test",
80 &BOpenHashTableTest::InsertUncheckedTest));
81 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
82 "BOpenHashTable::Insert unchecked uninitialized test",
83 &BOpenHashTableTest::InsertUncheckedUninitializedTest));
84 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
85 "BOpenHashTable::Iterate and count test",
86 &BOpenHashTableTest::IterateAndCountTest));
87 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
88 "BOpenHashTable::Lookup test",
89 &BOpenHashTableTest::LookupTest));
90 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
91 "BOpenHashTable::Resize test",
92 &BOpenHashTableTest::ResizeTest));
93 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
94 "BOpenHashTable::Remove test",
95 &BOpenHashTableTest::RemoveTest));
96 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
97 "BOpenHashTable::Remove unchecked test",
98 &BOpenHashTableTest::RemoveUncheckedTest));
99 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
100 "BOpenHashTable::Remove when not present test",
101 &BOpenHashTableTest::RemoveWhenNotPresentTest));
102 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
103 "BOpenHashTable::Duplicate insert test",
104 &BOpenHashTableTest::DuplicateInsertTest));
105 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
106 "BOpenHashTable::Disable auto expand",
107 &BOpenHashTableTest::DisableAutoExpandTest));
108 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
109 "BOpenHashTable::Init with zero size",
110 &BOpenHashTableTest::InitWithZeroSizeTest));
111 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
112 "BOpenHashTable::Clear test",
113 &BOpenHashTableTest::ClearTest));
114 suite->addTest(new CppUnit::TestCaller<BOpenHashTableTest>(
115 "BOpenHashTable::Clear and return test",
116 &BOpenHashTableTest::ClearAndReturnTest));
117
118 return suite;
119 }
120
121
BOpenHashTableTest(std::string name)122 BOpenHashTableTest::BOpenHashTableTest(std::string name)
123 : BTestCase(name)
124 {
125 }
126
127
InsertTest()128 void BOpenHashTableTest::InsertTest()
129 {
130 Entry entry(123);
131
132 BOpenHashTable<EntryDefinition> table;
133 CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
134
135 CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
136 }
137
138
InsertUncheckedTest()139 void BOpenHashTableTest::InsertUncheckedTest()
140 {
141 Entry entry(123);
142
143 BOpenHashTable<EntryDefinition> table;
144 CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
145
146 table.InsertUnchecked(&entry);
147 }
148
149
InsertUncheckedUninitializedTest()150 void BOpenHashTableTest::InsertUncheckedUninitializedTest()
151 {
152 Entry entry(123);
153
154 BOpenHashTable<EntryDefinition> table;
155 CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
156
157 table.InsertUnchecked(&entry);
158 }
159
160
IterateAndCountTest()161 void BOpenHashTableTest::IterateAndCountTest() {
162 const size_t kEntryCount = 20;
163
164 BObjectList<Entry> entries(20, true);
165
166 BOpenHashTable<EntryDefinition> table;
167 CPPUNIT_ASSERT_EQUAL(table.Init(kEntryCount * 2), B_OK);
168
169 for (uint32_t i = 0; i < kEntryCount; ++i) {
170 Entry* entry = new Entry(i);
171 entries.AddItem(entry);
172 CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
173 }
174
175 // Verify that the table contains the expected values.
176 uint64_t map = 0;
177 BOpenHashTable<EntryDefinition>::Iterator iterator = table.GetIterator();
178 while (iterator.HasNext()) {
179 Entry* entry = iterator.Next();
180 CPPUNIT_ASSERT_EQUAL(0, map & (1 << entry->Value()));
181 map |= (1 << entry->Value());
182 }
183
184 CPPUNIT_ASSERT_EQUAL(map, (1 << kEntryCount) - 1);
185 CPPUNIT_ASSERT_EQUAL(kEntryCount, table.CountElements());
186 }
187
188
ResizeTest()189 void BOpenHashTableTest::ResizeTest()
190 {
191 // This is the same as IterateAndCountTest, except that the table will
192 // be resized mid insertion.
193 const size_t kEntryCount = 20;
194 BObjectList<Entry> entries(20, true);
195 BOpenHashTable<EntryDefinition> table;
196
197 // Start off with capacity for 8 elements. This will mean that the table
198 // will be resized in the loop below since we are inserting 20 elements.
199 CPPUNIT_ASSERT_EQUAL(table.Init(8), B_OK);
200
201 for (uint32_t i = 0; i < kEntryCount; ++i) {
202 Entry* entry = new Entry(i);
203 entries.AddItem(entry);
204 CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
205 }
206
207 // Verify that after resize the expected elements are present within
208 // the table.
209 uint64_t map = 0;
210 BOpenHashTable<EntryDefinition>::Iterator iterator = table.GetIterator();
211 while (iterator.HasNext()) {
212 Entry* entry = iterator.Next();
213 CPPUNIT_ASSERT_EQUAL(0, map & (1 << entry->Value()));
214 map |= (1 << entry->Value());
215 }
216
217 CPPUNIT_ASSERT_EQUAL(map, (1 << kEntryCount) - 1);
218 CPPUNIT_ASSERT_EQUAL(kEntryCount, table.CountElements());
219 }
220
221
LookupTest()222 void BOpenHashTableTest::LookupTest() {
223 Entry entry(123);
224
225 BOpenHashTable<EntryDefinition> table;
226 CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
227
228 CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
229 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
230 }
231
232
RemoveTest()233 void BOpenHashTableTest::RemoveTest() {
234 Entry entry(123);
235
236 BOpenHashTable<EntryDefinition> table;
237 CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
238
239 CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
240 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
241
242 table.Remove(&entry);
243 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), NULL);
244 }
245
246
RemoveUncheckedTest()247 void BOpenHashTableTest::RemoveUncheckedTest()
248 {
249 Entry entry(123);
250
251 BOpenHashTable<EntryDefinition> table;
252 CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
253
254 CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
255 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
256
257 table.RemoveUnchecked(&entry);
258 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), NULL);
259 }
260
261
RemoveWhenNotPresentTest()262 void BOpenHashTableTest::RemoveWhenNotPresentTest()
263 {
264 Entry entry1(123);
265 Entry entry2(456);
266 Entry entry3(789);
267
268 BOpenHashTable<EntryDefinition> table;
269 CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
270
271 // Only add the first two entries.
272 table.Insert(&entry1);
273 table.Insert(&entry2);
274
275 // entry3 is not in the table, but we'll remove it anyway.
276 table.Remove(&entry3);
277 table.RemoveUnchecked(&entry3);
278
279 // The original two entries should still be there.
280 CPPUNIT_ASSERT_EQUAL(table.CountElements(), 2);
281 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry1);
282 CPPUNIT_ASSERT_EQUAL(table.Lookup(456), &entry2);
283 CPPUNIT_ASSERT_EQUAL(table.Lookup(789), NULL);
284 }
285
286
DuplicateInsertTest()287 void BOpenHashTableTest::DuplicateInsertTest()
288 {
289 Entry entry(123);
290
291 BOpenHashTable<EntryDefinition, true, true> table;
292 CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
293
294 CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
295 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
296
297 CPPUNIT_ASSERT_DEBUGGER(table.Insert(&entry));
298
299 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
300
301 // The item can basically never be removed now since there is a cycle,
302 // but we'll break into the debugger on remove when that happens as well.
303 CPPUNIT_ASSERT_DEBUGGER(table.Remove(&entry));
304 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
305
306 CPPUNIT_ASSERT_DEBUGGER(table.Remove(&entry));
307 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
308 }
309
310
DisableAutoExpandTest()311 void BOpenHashTableTest::DisableAutoExpandTest()
312 {
313 // Insert multiple items into a table with a fixed size of 1. This
314 // essentially turns this BOpenHashTable into a linked list, since resize
315 // will never occur.
316 Entry entry1(123);
317 Entry entry2(456);
318
319 BOpenHashTable<EntryDefinition, false> table;
320 CPPUNIT_ASSERT_EQUAL(table.Init(1), B_OK);
321
322 CPPUNIT_ASSERT_EQUAL(table.Insert(&entry1), B_OK);
323 CPPUNIT_ASSERT_EQUAL(table.Insert(&entry2), B_OK);
324 CPPUNIT_ASSERT_EQUAL(table.CountElements(), 2);
325 }
326
327
InitWithZeroSizeTest()328 void BOpenHashTableTest::InitWithZeroSizeTest()
329 {
330 Entry entry(123);
331
332 BOpenHashTable<EntryDefinition> table;
333 CPPUNIT_ASSERT_EQUAL(table.Init(0), B_OK);
334
335 CPPUNIT_ASSERT_EQUAL(table.Insert(&entry), B_OK);
336 CPPUNIT_ASSERT_EQUAL(table.Lookup(123), &entry);
337 }
338
339
ClearTest()340 void BOpenHashTableTest::ClearTest()
341 {
342 const size_t kEntryCount = 3;
343
344 BObjectList<Entry> entries(20, true);
345
346 BOpenHashTable<EntryDefinition> table;
347 CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
348
349 for (uint32_t i = 0; i < kEntryCount; ++i) {
350 Entry* entry = new Entry(i);
351 entries.AddItem(entry);
352 CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
353 }
354
355 CPPUNIT_ASSERT_EQUAL(table.CountElements(), kEntryCount);
356 CPPUNIT_ASSERT(table.Lookup(2) != NULL);
357
358 CPPUNIT_ASSERT_EQUAL(table.Clear(false), NULL);
359 CPPUNIT_ASSERT_EQUAL(table.CountElements(), 0);
360 CPPUNIT_ASSERT_EQUAL(table.Lookup(2), NULL);
361 CPPUNIT_ASSERT_EQUAL(table.GetIterator().HasNext(), false);
362 }
363
364
ClearAndReturnTest()365 void BOpenHashTableTest::ClearAndReturnTest()
366 {
367 // Same as ClearTest(), except that Clear(true) is called, which tells
368 // the BOpenHashTable<T> to return a linked list of entries before clearing
369 // the table.
370 const size_t kEntryCount = 3;
371 BOpenHashTable<EntryDefinition> table;
372 CPPUNIT_ASSERT_EQUAL(table.Init(), B_OK);
373
374 for (uint32_t i = 0; i < kEntryCount; ++i) {
375 Entry* entry = new Entry(i);
376 CPPUNIT_ASSERT_EQUAL(table.Insert(entry), B_OK);
377 }
378
379 CPPUNIT_ASSERT_EQUAL(table.CountElements(), kEntryCount);
380 CPPUNIT_ASSERT(table.Lookup(2) != NULL);
381
382 Entry* head = table.Clear(true);
383 CPPUNIT_ASSERT(head != NULL);
384
385 CPPUNIT_ASSERT_EQUAL(table.CountElements(), 0);
386 CPPUNIT_ASSERT_EQUAL(table.Lookup(2), NULL);
387 CPPUNIT_ASSERT_EQUAL(table.GetIterator().HasNext(), false);
388
389 size_t items_returned = 0;
390 while (head != NULL) {
391 Entry* next = head->Next();
392 delete head;
393 head = next;
394
395 ++items_returned;
396 }
397
398 CPPUNIT_ASSERT_EQUAL(items_returned, kEntryCount);
399 }
400