ReactOS  0.4.15-dev-3182-g7b62228
hash_test.cpp
Go to the documentation of this file.
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 {
36 #if !defined (STLPORT) || defined (_STLP_NO_EXTENSIONS)
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);
48 
49 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
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 
72 
73 //
74 // tests implementation
75 //
77 {
78 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
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 );
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 
114 {
115 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
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 {
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 
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 
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 }
299 {
300 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
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 
312 {
313 #if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
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 
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  {
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;
425  hash_multiset<IncompleteClass> hsminstances;
427 
432 };
433 # endif
434 #endif
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLboolean GLenum GLenum GLvoid * values
Definition: glext.h:5666
bool ok() const
_Ht::iterator iterator
Definition: _hash_map.h:266
#define CPPUNIT_TEST_SUITE(X)
Definition: cppunit_mini.h:142
#define assert(x)
Definition: debug.h:53
pair< _T1, _T2 > _STLP_CALL make_pair(_T1 __x, _T2 __y)
Definition: _pair.h:124
iterator insert(const value_type &__obj)
Definition: _hash_map.h:371
#define CPPUNIT_TEST(X)
Definition: cppunit_mini.h:182
Definition: features.h:417
const GLfloat * m
Definition: glext.h:10848
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
#define cout
Definition: iostream.cpp:38
void allocator_with_state()
Definition: hash_test.cpp:377
basic_ostream< _CharT, _Traits > &_STLP_CALL endl(basic_ostream< _CharT, _Traits > &__os)
Definition: _ostream.h:357
_Ht::iterator iterator
Definition: _hash_set.h:255
#define CPPUNIT_TEST_SUITE_END()
Definition: cppunit_mini.h:191
GLuint counter
Definition: glext.h:11116
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
#define CPPUNIT_CHECK(X)
Definition: cppunit_mini.h:195
_STLP_DECLSPEC _Stl_aligned_buffer< ostream > cerr
Definition: iostream.cpp:102
_Ht::iterator iterator
Definition: _hash_map.h:75
rope< char, allocator< char > > crope
Definition: _rope.h:2297
void insert_erase()
Definition: hash_test.cpp:311
void hmap1()
Definition: hash_test.cpp:76
void hmmap1()
Definition: hash_test.cpp:113
Definition: _map.h:237
GLdouble s
Definition: gl.h:2039
WDF_CHILD_LIST_ITERATOR iterator
void hset2()
Definition: hash_test.cpp:298
GLenum GLint * range
Definition: glext.h:7539
#define CPPUNIT_ASSERT(X)
Definition: cppunit_mini.h:200
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
static ICollection collection
Definition: typelib.c:184
Definition: _pair.h:47
void hmmap2()
Definition: hash_test.cpp:248
GLenum GLuint id
Definition: glext.h:5579
int strcmp(const char *String1, const char *String2)
Definition: utclib.c:469
GLfloat GLfloat p
Definition: glext.h:8902
Definition: _set.h:46
CPPUNIT_TEST_SUITE_REGISTRATION(HashTest)
Definition: path.c:41
void hmset1()
Definition: hash_test.cpp:280
_Ht::iterator iterator
Definition: _hash_set.h:69