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 //
hmap1()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
hmmap1()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
check_keys(HashTest::hashType & h,HashTest::mapType & m)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
hmmap2()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
hmset1()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 }
hset2()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
insert_erase()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
allocator_with_state()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