1 //Has to be first for StackAllocator swap overload to be taken 2 //into account (at least using GCC 4.0.1) 3 #include "stack_allocator.h" 4 5 #include <vector> 6 #include <algorithm> 7 #include <map> 8 #include <set> 9 10 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 11 # include <hash_map> 12 # include <hash_set> 13 # include <rope> 14 #endif 15 16 #include <string> 17 18 #include "cppunit/cppunit_proxy.h" 19 20 #if defined (__MVS__) 21 const char star = 92; 22 #else 23 const char star = 42; 24 #endif 25 26 #if !defined (STLPORT) || defined (_STLP_USE_NAMESPACES) 27 using namespace std; 28 #endif 29 30 // 31 // TestCase class 32 // 33 class HashTest : public CPPUNIT_NS::TestCase 34 { 35 CPPUNIT_TEST_SUITE(HashTest); 36 #if !defined (STLPORT) || defined (_STLP_NO_EXTENSIONS) 37 CPPUNIT_IGNORE; 38 #endif 39 CPPUNIT_TEST(hmap1); 40 CPPUNIT_TEST(hmmap1); 41 CPPUNIT_TEST(hmmap2); 42 CPPUNIT_TEST(hmset1); 43 CPPUNIT_TEST(hset2); 44 CPPUNIT_TEST(insert_erase); 45 CPPUNIT_TEST(allocator_with_state); 46 //CPPUNIT_TEST(equality); 47 CPPUNIT_TEST_SUITE_END(); 48 49 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 50 typedef hash_multiset<char, hash<char>, equal_to<char> > hmset; 51 #endif 52 53 protected: 54 void hmap1(); 55 void hmmap1(); 56 void hmmap2(); 57 void hmset1(); 58 void hset2(); 59 void insert_erase(); 60 //void equality(); 61 void allocator_with_state(); 62 63 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 64 typedef hash_multimap<int, int> hashType; 65 typedef multimap<int, int> mapType; 66 67 void check_keys( hashType& h, mapType& m ); 68 #endif 69 }; 70 71 CPPUNIT_TEST_SUITE_REGISTRATION(HashTest); 72 73 // 74 // tests implementation 75 // 76 void HashTest::hmap1() 77 { 78 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 79 typedef hash_map<char, crope, hash<char>, equal_to<char> > maptype; 80 maptype m; 81 // Store mappings between roman numerals and decimals. 82 m['l'] = "50"; 83 m['x'] = "20"; // Deliberate mistake. 84 m['v'] = "5"; 85 m['i'] = "1"; 86 CPPUNIT_ASSERT( !strcmp(m['x'].c_str(),"20") ); 87 m['x'] = "10"; // Correct mistake. 88 CPPUNIT_ASSERT( !strcmp(m['x'].c_str(),"10") ); 89 90 CPPUNIT_ASSERT( !strcmp(m['z'].c_str(),"") ); 91 92 CPPUNIT_ASSERT( m.count('z')==1 ); 93 pair<maptype::iterator, bool> p = m.insert(pair<const char, crope>('c', crope("100"))); 94 95 CPPUNIT_ASSERT(p.second); 96 97 p = m.insert(pair<const char, crope>('c', crope("100"))); 98 CPPUNIT_ASSERT(!p.second); 99 100 //Some iterators compare check, really compile time checks 101 maptype::iterator ite(m.begin()); 102 maptype::const_iterator cite(m.begin()); 103 cite = m.begin(); 104 maptype const& cm = m; 105 cite = cm.begin(); 106 CPPUNIT_ASSERT( ite == cite ); 107 CPPUNIT_ASSERT( !(ite != cite) ); 108 CPPUNIT_ASSERT( cite == ite ); 109 CPPUNIT_ASSERT( !(cite != ite) ); 110 #endif 111 } 112 113 void HashTest::hmmap1() 114 { 115 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 116 typedef hash_multimap<char, int, hash<char>,equal_to<char> > mmap; 117 mmap m; 118 CPPUNIT_ASSERT(m.count('X')==0); 119 m.insert(pair<const char,int>('X', 10)); // Standard way. 120 CPPUNIT_ASSERT(m.count('X')==1); 121 // m.insert('X', 20); // Non-standard, but very convenient! 122 m.insert(pair<const char,int>('X', 20)); // jbuck: standard way 123 CPPUNIT_ASSERT(m.count('X')==2); 124 // m.insert('Y', 32); 125 m.insert(pair<const char,int>('Y', 32)); // jbuck: standard way 126 mmap::iterator i = m.find('X'); // Find first match. 127 128 CPPUNIT_ASSERT((*i).first=='X'); 129 CPPUNIT_ASSERT((*i).second==10); 130 i++; 131 CPPUNIT_ASSERT((*i).first=='X'); 132 CPPUNIT_ASSERT((*i).second==20); 133 i++; 134 CPPUNIT_ASSERT((*i).first=='Y'); 135 CPPUNIT_ASSERT((*i).second==32); 136 i++; 137 CPPUNIT_ASSERT(i==m.end()); 138 139 size_t count = m.erase('X'); 140 CPPUNIT_ASSERT(count==2); 141 142 //Some iterators compare check, really compile time checks 143 mmap::iterator ite(m.begin()); 144 mmap::const_iterator cite(m.begin()); 145 CPPUNIT_ASSERT( ite == cite ); 146 CPPUNIT_ASSERT( !(ite != cite) ); 147 CPPUNIT_ASSERT( cite == ite ); 148 CPPUNIT_ASSERT( !(cite != ite) ); 149 150 typedef hash_multimap<size_t, size_t> HMapType; 151 HMapType hmap; 152 153 //We fill the map to implicitely start a rehash. 154 for (size_t counter = 0; counter < 3077; ++counter) 155 hmap.insert(HMapType::value_type(1, counter)); 156 157 hmap.insert(HMapType::value_type(12325, 1)); 158 hmap.insert(HMapType::value_type(12325, 2)); 159 160 CPPUNIT_ASSERT( hmap.count(12325) == 2 ); 161 162 //At this point 23 goes to the same bucket as 12325, it used to reveal a bug. 163 hmap.insert(HMapType::value_type(23, 0)); 164 165 CPPUNIT_ASSERT( hmap.count(12325) == 2 ); 166 #endif 167 } 168 169 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 170 // Short demonstrator that helps reproducing a bug in the hash-table implementation 171 // of STLPort 5.0.1/5.0.2. 172 // 173 // Problem: Fill a hash_multimap with entries of which many have the same key 174 // Internally, entries with the same key are kept as one block within the same bucket. 175 // Thus, when calling equal_range(key) the begin/end of that block is returned. 176 // However, this code shows that for key =3, that block is destroyed after inserting the 194th element. 177 // According to _hashtable.c we will have a rehash from size 193 to size 389 in that situation. 178 // After that rehash, equal_range only returns 2 elements with key = 3 whereas there are 65 in it. 179 // Reproduction: 180 // In the main()-method we fill a hash_multimap as well as a multi_map with the same <key, data> pairs 181 // After each insertion we call check_keys(...) to assure validity of these two containers. 182 // This works fine up to the 193th insertion. Insertion 194 generates the bug. 183 // 184 // check_keys() works as follows: 185 // (a) we check whether both containers contain the same number of elements. 186 // (b) Assuming that the multi_map works correctly, we iterate over all its elements and check 187 // whether we can find that key also in the hash_multimap. We collect all data for that specific 188 // key in in a set ("collection"). Notice that data is unique by construction in main(), thus the 189 // number of elements in the set must equal the number of entries in the hash_multimap and in the multimap 190 // (c) We check if we have seen as many data elements in collection as we have seen in the multimap. 191 // if so, we print "OK", otherwise we print a detailed key/data overview and assert. 192 // Caution: 193 // There are several configurations of the program that will NOT fail. (see comment in code below) 194 // E.g. it seems that whenever the keys are more or less sorted, the problem does not occur. 195 // Also, using numbers from 200 downto 1 or from 300 downto 1 cannot generate the problem, 196 // whereas using 400 downto 1 will fail. 197 // Finally, if we use key 1 (rather than key 3) we cannot generate a problem. 198 199 void HashTest::check_keys( HashTest::hashType& h, HashTest::mapType& m ) 200 { 201 set<int> collection; 202 203 // (a) check sizes 204 CPPUNIT_CHECK( h.size() == m.size() ); 205 206 // (b) iterate over multi_map 207 for ( mapType::iterator i = m.begin(); i != m.end(); ++i ) { 208 // look up that key in hash-table and keep all data in the set 209 pair<hashType::iterator,hashType::iterator> range = h.equal_range( i->first ); 210 for ( hashType::iterator j = range.first; j != range.second; ++j ) { 211 collection.insert( j->second ); 212 } 213 } 214 // (c) we should have seen as many elements as there are in the hash-table 215 #if 0 216 if (collection.size() == h.size()) cout << " OK" << endl; 217 else { 218 // if not, please report 219 cout << " FAILED: " << endl; 220 int lastKey = -1; 221 // iterate over all elements in multi_map 222 for (mapType::iterator mIter = m.begin(); mIter != m.end(); mIter++) { 223 // new key? print a new status line 224 if (mIter->first != lastKey) { 225 cout << endl << "Key : " << mIter->first << endl; 226 lastKey = mIter->first; 227 228 // print all hashed values for that key 229 cout << " data in hash: "; 230 pair<hashType::iterator,hashType::iterator> range = h.equal_range(mIter->first); 231 232 for (hashType::iterator h = range.first; h != range.second; h++) { 233 assert (h->first == lastKey); 234 cerr << h->second << ", "; // print all data for that key in Hash-Table 235 } 236 cout << endl << " data in map: "; 237 } 238 // and print all member in multi-map until the next key occurs 239 cout << mIter->second << ", " ; // print all data for that key in Map 240 } 241 } 242 #endif 243 CPPUNIT_CHECK( collection.size() == h.size() ); 244 } 245 246 #endif 247 248 void HashTest::hmmap2() 249 { 250 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 251 hashType h; 252 mapType m; 253 254 // CAUTION the following configurations WORKS in our setting 255 // for (int id = 1; id != 400; id ++) and int key = (id %3 == 0 ? 3 : id) 256 // for (int id = 200; id != 1; id --) and int key = (id %3 == 0 ? 3 : id) 257 // for (int id = 300; id != 1; id --) and int key = (id %3 == 0 ? 3 : id) 258 // for (int id = 400; id != 1; id --) and int key = (id %3 == 0 ? 1 : id) 259 // for (int id = 4000; id != 1; id --) and int key = (id %3 == 0 ? 1 : id) 260 // 261 // whereas these will FAIL 262 // for (int id = 400; id != 1; id --) and int key = (id %3 == 0 ? 3 : id) 263 // for (int id = 4000; id != 1; id --) and int key = (id %3 == 0 ? 3 : id) 264 // 265 266 for ( int id = 400; id != 1; id-- ) { 267 // generate many entries with key 3, fill up with unique keys. Data is unique (needed in check_keys()) 268 int key = (id % 3 == 0 ? 3 : id); 269 270 // keep hash_multi_map and multimap in sync 271 h.insert(make_pair(key, id)); 272 m.insert(make_pair(key, id)); 273 274 // check whether both contain the same elements 275 check_keys( h, m ); 276 } 277 #endif 278 } 279 280 void HashTest::hmset1() 281 { 282 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 283 hmset s; 284 CPPUNIT_ASSERT( s.count(star) == 0 ); 285 s.insert(star); 286 CPPUNIT_ASSERT( s.count(star) == 1 ); 287 s.insert(star); 288 CPPUNIT_ASSERT( s.count(star) == 2 ); 289 hmset::iterator i = s.find(char(40)); 290 CPPUNIT_ASSERT( i == s.end() ); 291 292 i = s.find(star); 293 CPPUNIT_ASSERT( i != s.end() ) 294 CPPUNIT_ASSERT( *i == '*' ); 295 CPPUNIT_ASSERT( s.erase(star) == 2 ); 296 #endif 297 } 298 void HashTest::hset2() 299 { 300 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 301 hash_set<int, hash<int>, equal_to<int> > s; 302 pair<hash_set<int, hash<int>, equal_to<int> >::iterator, bool> p = s.insert(42); 303 CPPUNIT_ASSERT( p.second ); 304 CPPUNIT_ASSERT( *(p.first) == 42 ); 305 306 p = s.insert(42); 307 CPPUNIT_ASSERT( !p.second ); 308 #endif 309 } 310 311 void HashTest::insert_erase() 312 { 313 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 314 typedef hash_map<string, size_t, hash<string>, equal_to<string> > hmap; 315 typedef hmap::value_type val_type; 316 { 317 hmap values; 318 # if !defined (__BORLANDC__) || (__BORLANDC__ >= 0x564) 319 CPPUNIT_ASSERT( values.insert(val_type("foo", 0)).second ); 320 CPPUNIT_ASSERT( values.insert(val_type("bar", 0)).second ); 321 CPPUNIT_ASSERT( values.insert(val_type("abc", 0)).second ); 322 # else 323 CPPUNIT_ASSERT( values.insert(hmap::value_type("foo", 0)).second ); 324 CPPUNIT_ASSERT( values.insert(hmap::value_type("bar", 0)).second ); 325 CPPUNIT_ASSERT( values.insert(hmap::value_type("abc", 0)).second ); 326 # endif 327 328 CPPUNIT_ASSERT( values.erase("foo") == 1 ); 329 CPPUNIT_ASSERT( values.erase("bar") == 1 ); 330 CPPUNIT_ASSERT( values.erase("abc") == 1 ); 331 } 332 333 { 334 hmap values; 335 # if !defined (__BORLANDC__) || (__BORLANDC__ >= 0x564) 336 CPPUNIT_ASSERT( values.insert(val_type("foo", 0)).second ); 337 CPPUNIT_ASSERT( values.insert(val_type("bar", 0)).second ); 338 CPPUNIT_ASSERT( values.insert(val_type("abc", 0)).second ); 339 # else 340 CPPUNIT_ASSERT( values.insert(hmap::value_type("foo", 0)).second ); 341 CPPUNIT_ASSERT( values.insert(hmap::value_type("bar", 0)).second ); 342 CPPUNIT_ASSERT( values.insert(hmap::value_type("abc", 0)).second ); 343 # endif 344 345 CPPUNIT_ASSERT( values.erase("abc") == 1 ); 346 CPPUNIT_ASSERT( values.erase("bar") == 1 ); 347 CPPUNIT_ASSERT( values.erase("foo") == 1 ); 348 } 349 #endif 350 } 351 352 /* 353 * Here is the test showing why equality operator on hash containers 354 * has no meaning: 355 356 struct equality_hash_func { 357 size_t operator () (size_t val) const { 358 return val % 10; 359 } 360 }; 361 362 void HashTest::equality() 363 { 364 hash_set<size_t, equality_hash_func, equal_to<size_t> > s1, s2; 365 366 s1.insert(10); 367 s1.insert(20); 368 369 s2.insert(20); 370 s2.insert(10); 371 372 //s1 and s2 contains both 10 and 20: 373 CPPUNIT_ASSERT( s1 == s2 ); 374 } 375 */ 376 377 void HashTest::allocator_with_state() 378 { 379 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) 380 char buf1[2048]; 381 StackAllocator<int> stack1(buf1, buf1 + sizeof(buf1)); 382 383 char buf2[2048]; 384 StackAllocator<int> stack2(buf2, buf2 + sizeof(buf2)); 385 386 { 387 typedef hash_set<int, hash<int>, equal_to<int>, StackAllocator<int> > HashSetInt; 388 HashSetInt hint1(10, hash<int>(), equal_to<int>(), stack1); 389 390 int i; 391 for (i = 0; i < 5; ++i) 392 hint1.insert(i); 393 HashSetInt hint1Cpy(hint1); 394 395 HashSetInt hint2(10, hash<int>(), equal_to<int>(), stack2); 396 for (; i < 10; ++i) 397 hint2.insert(i); 398 HashSetInt hint2Cpy(hint2); 399 400 hint1.swap(hint2); 401 402 CPPUNIT_ASSERT( hint1.get_allocator().swaped() ); 403 CPPUNIT_ASSERT( hint2.get_allocator().swaped() ); 404 405 CPPUNIT_ASSERT( hint1.get_allocator() == stack2 ); 406 CPPUNIT_ASSERT( hint2.get_allocator() == stack1 ); 407 } 408 CPPUNIT_ASSERT( stack1.ok() ); 409 CPPUNIT_ASSERT( stack2.ok() ); 410 #endif 411 } 412 413 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS) && \ 414 (!defined (_STLP_USE_PTR_SPECIALIZATIONS) || defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)) 415 # if !defined (__DMC__) 416 417 /* Simple compilation test: Check that nested types like iterator 418 * can be access even if type used to instanciate container is not 419 * yet completely defined. 420 */ 421 class IncompleteClass 422 { 423 hash_set<IncompleteClass> hsinstances; 424 typedef hash_set<IncompleteClass>::iterator hsit; 425 hash_multiset<IncompleteClass> hsminstances; 426 typedef hash_multiset<IncompleteClass>::iterator hsmit; 427 428 hash_map<IncompleteClass, IncompleteClass> hminstances; 429 typedef hash_map<IncompleteClass, IncompleteClass>::iterator hmit; 430 hash_multimap<IncompleteClass, IncompleteClass> hmminstances; 431 typedef hash_multimap<IncompleteClass, IncompleteClass>::iterator hmmit; 432 }; 433 # endif 434 #endif 435
