unordered_test.cpp revision e46c9386c4f79aa40185f79a19fc5b2a7ef528b3 
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)
14using namespace std;
15#  if defined (STLPORT)
16using namespace std::tr1;
17#  endif
18#endif
19
20//
21// TestCase class
22//
23class 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
45protected:
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
59CPPUNIT_TEST_SUITE_REGISTRATION(UnorderedTest);
60
61const int NB_ELEMS = 2000;
62
63//
64// tests implementation
65//
66void 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
116void 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
155void 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
224void 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
266void 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
294void 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
321void 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
344void 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
476void 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
495void 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
514struct 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
526struct 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
535struct 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
547struct 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
556struct 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
568void 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 */
663class 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