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: 17 Entry(uint32_t value) 18 : 19 fValue(value), 20 fNext(NULL) 21 { 22 } 23 24 const uint32_t Value() const 25 { 26 return fValue; 27 } 28 29 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 47 size_t HashKey(const KeyType& key) const 48 { 49 return key; 50 } 51 52 size_t Hash(Entry* entry) const 53 { 54 return entry->fValue; 55 } 56 57 bool Compare(const KeyType& key, Entry* entry) const 58 { 59 return key == entry->fValue; 60 } 61 62 Entry*& GetLink(Entry* entry) const 63 { 64 return entry->fNext; 65 } 66 }; 67 68 } 69 70 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 122 BOpenHashTableTest::BOpenHashTableTest(std::string name) 123 : BTestCase(name) 124 { 125 } 126 127 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 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 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 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 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 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 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 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 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 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 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 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 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 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