ReactOS 0.4.15-dev-8109-gd7be748
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
19
20#if defined (__MVS__)
21const char star = 92;
22#else
23const char star = 42;
24#endif
25
26#if !defined (STLPORT) || defined (_STLP_USE_NAMESPACES)
27using namespace std;
28#endif
29
30//
31// TestCase class
32//
33class HashTest : public CPPUNIT_NS::TestCase
34{
36#if !defined (STLPORT) || defined (_STLP_NO_EXTENSIONS)
38#endif
46 //CPPUNIT_TEST(equality);
48
49#if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
51#endif
52
53protected:
54 void hmap1();
55 void hmmap1();
56 void hmmap2();
57 void hmset1();
58 void hset2();
59 void insert_erase();
60 //void equality();
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');
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
199void 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
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
356struct equality_hash_func {
357 size_t operator () (size_t val) const {
358 return val % 10;
359 }
360};
361
362void 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 */
421class IncompleteClass
422{
423 hash_set<IncompleteClass> hsinstances;
427
432};
433# endif
434#endif
basic_ostream< _CharT, _Traits > &_STLP_CALL endl(basic_ostream< _CharT, _Traits > &__os)
Definition: _ostream.h:357
pair< _T1, _T2 > _STLP_CALL make_pair(_T1 __x, _T2 __y)
Definition: _pair.h:124
rope< char, allocator< char > > crope
Definition: _rope.h:2297
int strcmp(const char *String1, const char *String2)
Definition: utclib.c:469
CPPUNIT_TEST(allocator_with_state)
void hmap1()
Definition: hash_test.cpp:76
void hmmap1()
Definition: hash_test.cpp:113
CPPUNIT_TEST_SUITE(HashTest)
void insert_erase()
Definition: hash_test.cpp:311
void hmmap2()
Definition: hash_test.cpp:248
void hset2()
Definition: hash_test.cpp:298
CPPUNIT_TEST(hmap1)
CPPUNIT_TEST(hmmap2)
CPPUNIT_TEST(hmset1)
CPPUNIT_TEST_SUITE_END()
CPPUNIT_TEST(insert_erase)
void hmset1()
Definition: hash_test.cpp:280
void allocator_with_state()
Definition: hash_test.cpp:377
CPPUNIT_TEST(hset2)
CPPUNIT_TEST(hmmap1)
_Ht::iterator iterator
Definition: _hash_map.h:75
iterator insert(const value_type &__obj)
Definition: _hash_map.h:371
_Ht::iterator iterator
Definition: _hash_map.h:266
_Ht::iterator iterator
Definition: _hash_set.h:255
_Ht::iterator iterator
Definition: _hash_set.h:69
Definition: _map.h:241
Definition: _set.h:50
#define CPPUNIT_CHECK(X)
Definition: cppunit_mini.h:195
#define CPPUNIT_TEST_SUITE_REGISTRATION(X)
Definition: cppunit_mini.h:193
#define CPPUNIT_ASSERT(X)
Definition: cppunit_mini.h:200
#define assert(x)
Definition: debug.h:53
GLdouble s
Definition: gl.h:2039
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLenum GLint * range
Definition: glext.h:7539
GLboolean GLenum GLenum GLvoid * values
Definition: glext.h:5666
GLfloat GLfloat p
Definition: glext.h:8902
GLuint id
Definition: glext.h:5910
const GLfloat * m
Definition: glext.h:10848
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
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
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 cout
Definition: iostream.cpp:38
#define cerr
Definition: iostream.cpp:39
static ICollection collection
Definition: typelib.c:184
Definition: features.h:417
bool ok() const
Definition: _hash_fun.h:40
Definition: copy.c:22
Definition: _pair.h:47