1 #include <vector> 2 #include <algorithm> 3 #include <string> 4 #if defined (STLPORT) 5 # include <unordered_map> 6 # include <unordered_set> 7 #endif 8 9 //#include <iostream> 10 11 #include "cppunit/cppunit_proxy.h" 12 13 #if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES) 14 using namespace std; 15 # if defined (STLPORT) 16 using namespace std::tr1; 17 # endif 18 #endif 19 20 // 21 // TestCase class 22 // 23 class UnorderedTest : public CPPUNIT_NS::TestCase 24 { 25 CPPUNIT_TEST_SUITE(UnorderedTest); 26 #if !defined (STLPORT) 27 CPPUNIT_IGNORE; 28 #endif 29 CPPUNIT_TEST(uset); 30 CPPUNIT_TEST(umultiset); 31 CPPUNIT_TEST(umap); 32 CPPUNIT_TEST(umultimap); 33 CPPUNIT_TEST(user_case); 34 CPPUNIT_TEST(hash_policy); 35 CPPUNIT_TEST(buckets); 36 CPPUNIT_TEST(equal_range); 37 CPPUNIT_EXPLICIT_TEST(benchmark1); 38 CPPUNIT_EXPLICIT_TEST(benchmark2); 39 #if !defined (_STLP_USE_CONTAINERS_EXTENSION) 40 CPPUNIT_IGNORE; 41 #endif 42 CPPUNIT_TEST(template_methods); 43 CPPUNIT_TEST_SUITE_END(); 44 45 protected: 46 void uset(); 47 void umultiset(); 48 void umap(); 49 void umultimap(); 50 void user_case(); 51 void hash_policy(); 52 void buckets(); 53 void equal_range(); 54 void benchmark1(); 55 void benchmark2(); 56 void template_methods(); 57 }; 58 59 CPPUNIT_TEST_SUITE_REGISTRATION(UnorderedTest); 60 61 const int NB_ELEMS = 2000; 62 63 // 64 // tests implementation 65 // 66 void UnorderedTest::uset() 67 { 68 #if defined (STLPORT) 69 typedef unordered_set<int, hash<int>, equal_to<int> > usettype; 70 usettype us; 71 72 //Small compilation check of the copy constructor: 73 usettype us2(us); 74 //And assignment operator 75 us = us2; 76 77 int i; 78 pair<usettype::iterator, bool> ret; 79 for (i = 0; i < NB_ELEMS; ++i) { 80 ret = us.insert(i); 81 CPPUNIT_ASSERT( ret.second ); 82 CPPUNIT_ASSERT( *ret.first == i ); 83 84 ret = us.insert(i); 85 CPPUNIT_ASSERT( !ret.second ); 86 CPPUNIT_ASSERT( *ret.first == i ); 87 } 88 89 vector<int> us_val; 90 91 usettype::local_iterator lit, litEnd; 92 for (i = 0; i < NB_ELEMS; ++i) { 93 lit = us.begin(us.bucket(i)); 94 litEnd = us.end(us.bucket(i)); 95 96 usettype::size_type bucket_pos = us.bucket(*lit); 97 for (; lit != litEnd; ++lit) { 98 CPPUNIT_ASSERT( us.bucket(*lit) == bucket_pos ); 99 us_val.push_back(*lit); 100 } 101 } 102 103 //A compilation time check to uncomment from time to time 104 { 105 //usettype::iterator it; 106 //CPPUNIT_ASSERT( it != lit ); 107 } 108 109 sort(us_val.begin(), us_val.end()); 110 for (i = 0; i < NB_ELEMS; ++i) { 111 CPPUNIT_ASSERT( us_val[i] == i ); 112 } 113 #endif 114 } 115 116 void UnorderedTest::umultiset() 117 { 118 #if defined (STLPORT) 119 typedef unordered_multiset<int, hash<int>, equal_to<int> > usettype; 120 usettype us; 121 122 int i; 123 usettype::iterator ret; 124 for (i = 0; i < NB_ELEMS; ++i) { 125 ret = us.insert(i); 126 CPPUNIT_ASSERT( *ret == i ); 127 128 ret = us.insert(i); 129 CPPUNIT_ASSERT( *ret == i ); 130 } 131 132 CPPUNIT_ASSERT( us.size() == 2 * NB_ELEMS ); 133 vector<int> us_val; 134 135 usettype::local_iterator lit, litEnd; 136 for (i = 0; i < NB_ELEMS; ++i) { 137 lit = us.begin(us.bucket(i)); 138 litEnd = us.end(us.bucket(i)); 139 140 usettype::size_type bucket_pos = us.bucket(*lit); 141 for (; lit != litEnd; ++lit) { 142 CPPUNIT_ASSERT( us.bucket(*lit) == bucket_pos ); 143 us_val.push_back(*lit); 144 } 145 } 146 147 sort(us_val.begin(), us_val.end()); 148 for (i = 0; i < NB_ELEMS; ++i) { 149 CPPUNIT_ASSERT( us_val[2 * i] == i ); 150 CPPUNIT_ASSERT( us_val[2 * i + 1] == i ); 151 } 152 #endif 153 } 154 155 void UnorderedTest::umap() 156 { 157 #if defined (STLPORT) 158 typedef unordered_map<int, int, hash<int>, equal_to<int> > umaptype; 159 umaptype us; 160 161 //Compilation check of the [] operator: 162 umaptype us2; 163 us[0] = us2[0]; 164 us.clear(); 165 166 { 167 //An other compilation check 168 typedef unordered_map<int, umaptype> uumaptype; 169 uumaptype uus; 170 umaptype const& uref = uus[0]; 171 umaptype ucopy = uus[0]; 172 ucopy = uref; 173 //Avoids warning: 174 //(void*)&uref; 175 } 176 177 int i; 178 pair<umaptype::iterator, bool> ret; 179 for (i = 0; i < NB_ELEMS; ++i) { 180 umaptype::value_type p1(i, i); 181 ret = us.insert(p1); 182 CPPUNIT_ASSERT( ret.second ); 183 CPPUNIT_ASSERT( *ret.first == p1 ); 184 185 umaptype::value_type p2(i, i + 1); 186 ret = us.insert(p2); 187 CPPUNIT_ASSERT( !ret.second ); 188 CPPUNIT_ASSERT( *ret.first == p1 ); 189 } 190 191 { 192 //Lets look for some values to see if everything is normal: 193 umaptype::iterator umit; 194 for (int j = 0; j < NB_ELEMS; j += NB_ELEMS / 100) { 195 umit = us.find(j); 196 197 CPPUNIT_ASSERT( umit != us.end() ); 198 CPPUNIT_ASSERT( (*umit).second == j ); 199 } 200 } 201 202 CPPUNIT_ASSERT( us.size() == (size_t)NB_ELEMS ); 203 vector<pair<int, int> > us_val; 204 205 umaptype::local_iterator lit, litEnd; 206 for (i = 0; i < NB_ELEMS; ++i) { 207 lit = us.begin(us.bucket(i)); 208 litEnd = us.end(us.bucket(i)); 209 210 umaptype::size_type bucket_pos = us.bucket((*lit).first); 211 for (; lit != litEnd; ++lit) { 212 CPPUNIT_ASSERT( us.bucket((*lit).first) == bucket_pos ); 213 us_val.push_back(make_pair((*lit).first, (*lit).second)); 214 } 215 } 216 217 sort(us_val.begin(), us_val.end()); 218 for (i = 0; i < NB_ELEMS; ++i) { 219 CPPUNIT_ASSERT( us_val[i] == make_pair(i, i) ); 220 } 221 #endif 222 } 223 224 void UnorderedTest::umultimap() 225 { 226 #if defined (STLPORT) 227 typedef unordered_multimap<int, int, hash<int>, equal_to<int> > umaptype; 228 umaptype us; 229 230 int i; 231 umaptype::iterator ret; 232 for (i = 0; i < NB_ELEMS; ++i) { 233 umaptype::value_type p(i, i); 234 ret = us.insert(p); 235 CPPUNIT_ASSERT( *ret == p ); 236 237 ret = us.insert(p); 238 CPPUNIT_ASSERT( *ret == p ); 239 } 240 241 CPPUNIT_ASSERT( us.size() == 2 * NB_ELEMS ); 242 typedef pair<int, int> ptype; 243 vector<ptype> us_val; 244 245 umaptype::local_iterator lit, litEnd; 246 for (i = 0; i < NB_ELEMS; ++i) { 247 lit = us.begin(us.bucket(i)); 248 litEnd = us.end(us.bucket(i)); 249 250 umaptype::size_type bucket_pos = us.bucket((*lit).first); 251 for (; lit != litEnd; ++lit) { 252 CPPUNIT_ASSERT( us.bucket((*lit).first) == bucket_pos ); 253 us_val.push_back(ptype((*lit).first, (*lit).second)); 254 } 255 } 256 257 sort(us_val.begin(), us_val.end()); 258 for (i = 0; i < NB_ELEMS; ++i) { 259 ptype p(i, i); 260 CPPUNIT_ASSERT( us_val[i * 2] == p ); 261 CPPUNIT_ASSERT( us_val[i * 2 + 1] == p ); 262 } 263 #endif 264 } 265 266 void UnorderedTest::user_case() 267 { 268 #if defined (STLPORT) 269 typedef unordered_map<int, string> UnorderedMap1; 270 typedef unordered_map<int, UnorderedMap1> UnorderedMap2; 271 272 UnorderedMap1 foo; 273 UnorderedMap2 bar; 274 275 foo.insert(UnorderedMap1::value_type(1, string("test1"))); 276 foo.insert(UnorderedMap1::value_type(2, string("test2"))); 277 foo.insert(UnorderedMap1::value_type(3, string("test3"))); 278 foo.insert(UnorderedMap1::value_type(4, string("test4"))); 279 foo.insert(UnorderedMap1::value_type(5, string("test5"))); 280 281 bar.insert(UnorderedMap2::value_type(0, foo)); 282 UnorderedMap2::iterator it = bar.find(0); 283 CPPUNIT_ASSERT( it != bar.end() ); 284 285 UnorderedMap1 &body = it->second; 286 UnorderedMap1::iterator cur = body.find(3); 287 CPPUNIT_ASSERT( cur != body.end() ); 288 289 body.erase(body.begin(), body.end()); 290 CPPUNIT_ASSERT( body.empty() ); 291 #endif 292 } 293 294 void UnorderedTest::hash_policy() 295 { 296 #if defined (STLPORT) 297 unordered_set<int> int_uset; 298 299 CPPUNIT_ASSERT( int_uset.max_load_factor() == 1.0f ); 300 CPPUNIT_ASSERT( int_uset.load_factor() == 0.0f ); 301 302 size_t nbInserts = int_uset.bucket_count() - 1; 303 for (int i = 0; (size_t)i < nbInserts; ++i) { 304 int_uset.insert(i); 305 } 306 CPPUNIT_ASSERT( int_uset.size() == nbInserts ); 307 308 int_uset.max_load_factor(0.5f); 309 int_uset.rehash(0); 310 CPPUNIT_ASSERT( int_uset.load_factor() < int_uset.max_load_factor() ); 311 312 size_t bucketsHint = int_uset.bucket_count() + 1; 313 int_uset.rehash(bucketsHint); 314 CPPUNIT_ASSERT( int_uset.bucket_count() >= bucketsHint ); 315 316 CPPUNIT_ASSERT( int_uset.key_eq()(10, 10) ); 317 CPPUNIT_ASSERT( int_uset.hash_function()(10) == 10 ); 318 #endif 319 } 320 321 void UnorderedTest::buckets() 322 { 323 #if defined (STLPORT) 324 unordered_set<int> int_uset; 325 326 CPPUNIT_ASSERT( int_uset.bucket_count() < int_uset.max_bucket_count() ); 327 328 int i; 329 size_t nbBuckets = int_uset.bucket_count(); 330 size_t nbInserts = int_uset.bucket_count() - 1; 331 for (i = 0; (size_t)i < nbInserts; ++i) { 332 int_uset.insert(i); 333 } 334 CPPUNIT_ASSERT( nbBuckets == int_uset.bucket_count() ); 335 336 size_t bucketSizes = 0; 337 for (i = 0; (size_t)i < nbBuckets; ++i) { 338 bucketSizes += int_uset.bucket_size(i); 339 } 340 CPPUNIT_ASSERT( bucketSizes == int_uset.size() ); 341 #endif 342 } 343 344 void UnorderedTest::equal_range() 345 { 346 #if defined (STLPORT) 347 typedef unordered_multiset<size_t> umset; 348 { 349 //General test 350 umset iumset; 351 iumset.max_load_factor(10.0f); 352 353 size_t nbBuckets = iumset.bucket_count(); 354 355 for (size_t i = 0; i < nbBuckets; ++i) { 356 iumset.insert(i); 357 iumset.insert(i + nbBuckets); 358 iumset.insert(i + 2 * nbBuckets); 359 iumset.insert(i + 3 * nbBuckets); 360 iumset.insert(i + 4 * nbBuckets); 361 } 362 363 CPPUNIT_ASSERT( nbBuckets == iumset.bucket_count() ); 364 CPPUNIT_ASSERT( iumset.size() == 5 * nbBuckets ); 365 366 pair<umset::iterator, umset::iterator> p = iumset.equal_range(1); 367 CPPUNIT_ASSERT( p.first != p.second ); 368 369 size_t nbElems = iumset.size(); 370 nbElems -= distance(p.first, p.second); 371 for (umset::iterator j = p.first; j != p.second;) { 372 iumset.erase(j++); 373 } 374 375 CPPUNIT_ASSERT( nbElems == iumset.size() ); 376 377 p = iumset.equal_range(2); 378 CPPUNIT_ASSERT( p.first != p.second ); 379 nbElems -= distance(p.first, p.second); 380 iumset.erase(p.first, p.second); 381 CPPUNIT_ASSERT( nbElems == iumset.size() ); 382 } 383 384 { 385 //More specific test that tries to put many values in the same bucket 386 umset iumset; 387 388 size_t i; 389 //We are going to add at least 20 values, to get a stable hash container while doing that 390 //we force a large number of buckets: 391 iumset.rehash(193); 392 393 size_t nbBuckets = iumset.bucket_count(); 394 const size_t targetedBucket = nbBuckets / 2; 395 396 //Lets put 10 values in the targeted bucket: 397 for (i = 0; i < 10; ++i) { 398 iumset.insert(targetedBucket + (i * nbBuckets)); 399 } 400 401 //We put again 10 values in the targeted bucket and in reverse order: 402 for (i = 9; i <= 10; --i) { 403 iumset.insert(targetedBucket + (i * nbBuckets)); 404 } 405 406 //Now we put some more elements until hash container is resized: 407 i = 0; 408 while (iumset.bucket_count() == nbBuckets) { 409 iumset.insert(i++); 410 } 411 412 //CPPUNIT_ASSERT( iumset.bucket_size(targetedBucket) == 21 ); 413 414 pair<umset::iterator, umset::iterator> p = iumset.equal_range(targetedBucket); 415 CPPUNIT_ASSERT( p.first != p.second ); 416 CPPUNIT_ASSERT( distance(p.first, p.second) == 3 ); 417 418 // Now we remove some elements until hash container is resized: 419 nbBuckets = iumset.bucket_count(); 420 while (iumset.bucket_count() == nbBuckets && 421 !iumset.empty()) { 422 iumset.erase(iumset.begin()); 423 } 424 CPPUNIT_ASSERT( iumset.load_factor() <= iumset.max_load_factor() ); 425 426 // Adding an element back shouldn't change number of buckets: 427 nbBuckets = iumset.bucket_count(); 428 iumset.insert(0); 429 CPPUNIT_ASSERT( iumset.bucket_count() == nbBuckets ); 430 } 431 432 { 433 srand(0); 434 for (int runs = 0; runs < 2; ++runs) { 435 size_t magic = rand(); 436 umset hum; 437 size_t c = 0; 438 for (int i = 0; i < 10000; ++i) { 439 if ((rand() % 500) == 0) { 440 hum.insert(magic); 441 ++c; 442 } 443 else { 444 size_t r; 445 while ((r = rand()) == magic) 446 ; 447 hum.insert(r); 448 } 449 450 /* 451 if ((float)(hum.size() + 1) / (float)hum.bucket_count() > hum.max_load_factor()) { 452 cout << "Hash container dump: Nb elems: " << hum.size() << ", Nb buckets: " << hum.bucket_count() << "\n"; 453 for (size_t b = 0; b < hum.bucket_count(); ++b) { 454 if (hum.bucket_size(b) != 0) { 455 umset::local_iterator litBegin(hum.begin(b)), litEnd(hum.end(b)); 456 cout << "B" << b << ": "; 457 for (umset::local_iterator lit = litBegin; lit != litEnd; ++lit) { 458 if (lit != litBegin) { 459 cout << " - "; 460 } 461 cout << *lit; 462 } 463 cout << "\n"; 464 } 465 } 466 cout << endl; 467 } 468 */ 469 } 470 CPPUNIT_ASSERT( hum.count(magic) == c ); 471 } 472 } 473 #endif 474 } 475 476 void UnorderedTest::benchmark1() 477 { 478 #if defined (STLPORT) 479 typedef unordered_multiset<size_t> umset; 480 481 const size_t target = 500000; 482 umset iumset; 483 iumset.max_load_factor(10); 484 size_t i; 485 for (i = 0; i < target; ++i) { 486 iumset.insert(i); 487 } 488 489 for (i = 0; i < target; ++i) { 490 iumset.erase(i); 491 } 492 #endif 493 } 494 495 void UnorderedTest::benchmark2() 496 { 497 #if defined (STLPORT) 498 typedef unordered_multiset<size_t> umset; 499 500 const size_t target = 500000; 501 umset iumset; 502 iumset.max_load_factor(10); 503 size_t i; 504 for (i = 0; i < target; ++i) { 505 iumset.insert(target - i); 506 } 507 508 for (i = 0; i < target; ++i) { 509 iumset.erase(target - i); 510 } 511 #endif 512 } 513 514 struct Key 515 { 516 Key() : m_data(0) {} 517 explicit Key(int data) : m_data(data) {} 518 519 int m_data; 520 521 #if defined (__DMC__) // slist<_Tp,_Alloc>::remove error 522 bool operator==(const Key&) const; 523 #endif 524 }; 525 526 struct KeyHash 527 { 528 size_t operator () (Key key) const 529 { return (size_t)key.m_data; } 530 531 size_t operator () (int data) const 532 { return (size_t)data; } 533 }; 534 535 struct KeyEqual 536 { 537 bool operator () (Key lhs, Key rhs) const 538 { return lhs.m_data == rhs.m_data; } 539 540 bool operator () (Key lhs, int rhs) const 541 { return lhs.m_data == rhs; } 542 543 bool operator () (int lhs, Key rhs) const 544 { return lhs == rhs.m_data; } 545 }; 546 547 struct KeyHashPtr 548 { 549 size_t operator () (Key const volatile *key) const 550 { return (size_t)key->m_data; } 551 552 size_t operator () (int data) const 553 { return (size_t)data; } 554 }; 555 556 struct KeyEqualPtr 557 { 558 bool operator () (Key const volatile *lhs, Key const volatile *rhs) const 559 { return lhs->m_data == rhs->m_data; } 560 561 bool operator () (Key const volatile *lhs, int rhs) const 562 { return lhs->m_data == rhs; } 563 564 bool operator () (int lhs, Key const volatile *rhs) const 565 { return lhs == rhs->m_data; } 566 }; 567 568 void UnorderedTest::template_methods() 569 { 570 #if defined (STLPORT) && defined (_STLP_USE_CONTAINERS_EXTENSION) 571 { 572 typedef unordered_set<Key, KeyHash, KeyEqual> Container; 573 Container cont; 574 cont.insert(Key(1)); 575 cont.insert(Key(2)); 576 cont.insert(Key(3)); 577 cont.insert(Key(4)); 578 579 CPPUNIT_ASSERT( cont.count(Key(1)) == 1 ); 580 CPPUNIT_ASSERT( cont.count(1) == 1 ); 581 CPPUNIT_ASSERT( cont.count(5) == 0 ); 582 583 CPPUNIT_ASSERT( cont.find(2) != cont.end() ); 584 CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) ); 585 586 Container const& ccont = cont; 587 CPPUNIT_ASSERT( ccont.find(2) != ccont.end() ); 588 CPPUNIT_ASSERT( ccont.bucket(2) == ccont.bucket(2) ); 589 CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.begin(), ccont.end()) ); 590 } 591 592 { 593 typedef unordered_set<Key*, KeyHashPtr, KeyEqualPtr> Container; 594 Container cont; 595 Key key1(1), key2(2), key3(3), key4(4); 596 cont.insert(&key1); 597 cont.insert(&key2); 598 cont.insert(&key3); 599 cont.insert(&key4); 600 601 CPPUNIT_ASSERT( cont.count(1) == 1 ); 602 CPPUNIT_ASSERT( cont.count(5) == 0 ); 603 604 CPPUNIT_ASSERT( cont.find(2) != cont.end() ); 605 CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) ); 606 607 Container const& ccont = cont; 608 CPPUNIT_ASSERT( ccont.find(2) != ccont.end() ); 609 CPPUNIT_ASSERT( ccont.bucket(2) == ccont.bucket(2) ); 610 CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.begin(), ccont.end()) ); 611 } 612 { 613 typedef unordered_multiset<Key, KeyHash, KeyEqual> Container; 614 Container cont; 615 cont.insert(Key(1)); 616 cont.insert(Key(2)); 617 cont.insert(Key(1)); 618 cont.insert(Key(2)); 619 620 CPPUNIT_ASSERT( cont.count(Key(1)) == 2 ); 621 CPPUNIT_ASSERT( cont.count(1) == 2 ); 622 CPPUNIT_ASSERT( cont.count(5) == 0 ); 623 624 CPPUNIT_ASSERT( cont.find(2) != cont.end() ); 625 CPPUNIT_ASSERT( cont.equal_range(1) != make_pair(cont.end(), cont.end()) ); 626 627 Container const& ccont = cont; 628 CPPUNIT_ASSERT( ccont.find(2) != ccont.end() ); 629 CPPUNIT_ASSERT( ccont.bucket(2) == ccont.bucket(2) ); 630 CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.end(), ccont.end()) ); 631 } 632 633 { 634 typedef unordered_multiset<Key const volatile*, KeyHashPtr, KeyEqualPtr> Container; 635 Container cont; 636 Key key1(1), key2(2), key3(3), key4(4); 637 cont.insert(&key1); 638 cont.insert(&key2); 639 cont.insert(&key3); 640 cont.insert(&key4); 641 642 CPPUNIT_ASSERT( cont.count(1) == 1 ); 643 CPPUNIT_ASSERT( cont.count(5) == 0 ); 644 645 CPPUNIT_ASSERT( cont.find(2) != cont.end() ); 646 CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) ); 647 648 Container const& ccont = cont; 649 CPPUNIT_ASSERT( ccont.find(2) != ccont.end() ); 650 CPPUNIT_ASSERT( ccont.bucket(2) == ccont.bucket(2) ); 651 CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.begin(), ccont.end()) ); 652 } 653 #endif 654 } 655 656 #if defined (STLPORT) && \ 657 (!defined (_STLP_USE_PTR_SPECIALIZATIONS) || defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)) 658 # if !defined (__DMC__) 659 /* Simple compilation test: Check that nested types like iterator 660 * can be access even if type used to instanciate container is not 661 * yet completely defined. 662 */ 663 class IncompleteClass 664 { 665 unordered_set<IncompleteClass> usinstances; 666 typedef unordered_set<IncompleteClass>::iterator usit; 667 unordered_multiset<IncompleteClass> usminstances; 668 typedef unordered_multiset<IncompleteClass>::iterator usmit; 669 670 unordered_map<IncompleteClass, IncompleteClass> uminstances; 671 typedef unordered_map<IncompleteClass, IncompleteClass>::iterator umit; 672 unordered_multimap<IncompleteClass, IncompleteClass> umminstances; 673 typedef unordered_multimap<IncompleteClass, IncompleteClass>::iterator ummit; 674 }; 675 # endif 676 #endif 677
