1 /////////////////////////////////////////////////////////////////////////////
2 // Copyright (c) Electronic Arts Inc. All rights reserved.
3 /////////////////////////////////////////////////////////////////////////////
4
5
6 #include "EASTLTest.h"
7 #include <EASTL/internal/intrusive_hashtable.h>
8 #include <EASTL/intrusive_hash_set.h>
9 #include <EASTL/intrusive_hash_map.h>
10 #include <EABase/eabase.h>
11
12
13
14 using namespace eastl;
15
16
17 namespace
18 {
19 struct SetWidget : public intrusive_hash_node
20 {
SetWidget__anon2bceaeec0111::SetWidget21 SetWidget(int x = 0)
22 : mX(x) { }
23 int mX;
24 };
25
operator ==(const SetWidget & a,const SetWidget & b)26 inline bool operator==(const SetWidget& a, const SetWidget& b)
27 { return a.mX == b.mX; }
28
29 struct SWHash
30 {
operator ()__anon2bceaeec0111::SWHash31 size_t operator()(const SetWidget& sw) const
32 {
33 return (size_t)sw.mX;
34 }
35 };
36
37 struct SetWidgetComparable // Exists for the sole purpose of testing the find_as function.
38 {
SetWidgetComparable__anon2bceaeec0111::SetWidgetComparable39 SetWidgetComparable(int x = 0)
40 : mX(x) { }
41 int mX;
42 };
43
44 struct SWCHash
45 {
operator ()__anon2bceaeec0111::SWCHash46 size_t operator()(const SetWidgetComparable& swc) const
47 {
48 return (size_t)swc.mX;
49 }
50 };
51
operator ==(const SetWidget & a,const SetWidgetComparable & b)52 bool operator==(const SetWidget& a, const SetWidgetComparable& b)
53 { return a.mX == b.mX; }
54
55
56
57 struct MapWidget : public intrusive_hash_node_key<int>
58 {
MapWidget__anon2bceaeec0111::MapWidget59 MapWidget(int x = 0)
60 : mX(x) { }
61 int mX;
62 };
63
operator ==(const MapWidget & a,const MapWidget & b)64 inline bool operator==(const MapWidget& a, const MapWidget& b)
65 { return a.mX == b.mX; }
66
67 //struct MapWidgetComparable // Exists for the sole purpose of testing the find_as function.
68 //{
69 // MapWidgetComparable(int x = 0)
70 // : mX(x) { }
71 // int mX;
72 //};
73 //
74 //bool operator==(const SetWidget& a, const MapWidgetComparable& b)
75 // { return a.mX == b.mX; }
76
77
78
79
80 // IHWidget
81 //
82 // Implements the intrusive node data directly instead of inheriting from intrusive_hash_node.
83 //
84 struct IHWidget
85 {
IHWidget__anon2bceaeec0111::IHWidget86 IHWidget(int x = 0)
87 : mX(x) { }
88
89 int mX;
90 IHWidget* mpNext;
91 typedef int key_type;
92 int mKey;
93
94 };
95
operator ==(const IHWidget & a,const IHWidget & b)96 inline bool operator==(const IHWidget& a, const IHWidget& b)
97 { return a.mX == b.mX; }
98
99 struct IHWHash
100 {
operator ()__anon2bceaeec0111::IHWHash101 size_t operator()(const IHWidget& ihw) const
102 {
103 return (size_t)ihw.mX;
104 }
105 };
106
107 } // namespace
108
109
110
111
112 // Template instantations.
113 // These tell the compiler to compile all the functions for the given class.
114 //template class intrusive_hash_set<SetWidget>;
115 //template class intrusive_hash_map<MapWidget>;
116
117
118 template class eastl::intrusive_hashtable<SetWidget, SetWidget, SWHash, eastl::equal_to<SetWidget>, 37, true, true>;
119 template class eastl::intrusive_hashtable<int, MapWidget, eastl::hash<int>, eastl::equal_to<int>, 37, false, true>;
120
121 template class eastl::intrusive_hash_set<SetWidget, 37, SWHash>;
122 template class eastl::intrusive_hash_multiset<SetWidget, 37, SWHash>;
123
124 template class eastl::intrusive_hash_map<int, MapWidget, 37>;
125 template class eastl::intrusive_hash_multimap<int, MapWidget, 37>;
126
127 template class eastl::intrusive_hash_set<IHWidget, 37, IHWHash>;
128 template class eastl::intrusive_hash_multiset<IHWidget, 37, IHWHash>;
129
130 template class eastl::intrusive_hash_map<int, IHWidget, 37, IHWHash>;
131 template class eastl::intrusive_hash_multimap<int, IHWidget, 37, IHWHash>;
132
133
134
135
136
TestIntrusiveHash()137 int TestIntrusiveHash()
138 {
139 int nErrorCount = 0;
140
141 {
142 SetWidget sw1, sw2;
143 VERIFY(sw1 == sw2);
144
145 MapWidget mw1, mw2;
146 VERIFY(mw1 == mw2);
147
148 IHWidget iw1, iw2;
149 VERIFY(iw1 == iw2);
150
151 IHWHash ih1;
152 VERIFY(ih1.operator()(iw1) == ih1.operator()(iw2));
153 }
154
155 {
156 // Test intrusive_hash_set
157
158 const size_t kBucketCount = 37;
159 typedef intrusive_hash_set<SetWidget, kBucketCount, SWHash> IHM_SW;
160
161 const size_t kArraySize = 100;
162 SetWidget swArray[kArraySize];
163
164 int nExpectedKeySum = 0; // We use this as a checksum in order to do validity checks below.
165
166 for(size_t i = 0; i < kArraySize; i++)
167 {
168 swArray[i].mX = (int)i;
169 nExpectedKeySum += (int)i;
170 }
171
172
173 // const key_equal& key_eq() const;
174 // key_equal& key_eq();
175 IHM_SW ih;
176 const IHM_SW ihc;
177
178 const IHM_SW::key_equal& ke = ihc.key_eq();
179 ih.key_eq() = ke;
180
181
182 // intrusive_hashtable(const Hash&, const Equal&);
183 // void swap(this_type& x);
184 // size_type size() const;
185 // bool empty() const;
186 // size_type bucket_count() const;
187 // size_type bucket_size(size_type n) const;
188 // float load_factor() const;
189 // void clear();
190 // bool validate() const;
191
192 IHM_SW ihmSW1;
193 IHM_SW ihmSW2;
194
195 VERIFY(ihmSW1.size() == 0);
196 VERIFY(ihmSW1.empty());
197 VERIFY(ihmSW1.validate());
198 VERIFY(ihmSW2.validate());
199
200 ihmSW1.swap(ihmSW2);
201
202 VERIFY(ihmSW1.validate());
203 VERIFY(ihmSW2.validate());
204 VERIFY(ihmSW2.bucket_count() == kBucketCount);
205 VERIFY(ihmSW2.bucket_size(0) == 0);
206 VERIFY(ihmSW2.bucket_size(kBucketCount - 1) == 0);
207 VERIFY(ihmSW1.load_factor() == 0.f);
208 VERIFY(ihmSW2.load_factor() == 0.f);
209
210 ihmSW1.clear();
211 VERIFY(ihmSW1.validate());
212 VERIFY(ihmSW1.begin() == ihmSW1.end());
213
214
215 // void insert(InputIterator first, InputIterator last);
216 // insert_return_type insert(value_type& value);
217 // void swap(this_type& x);
218 // void clear();
219
220 ihmSW1.clear();
221 ihmSW1.insert(swArray, swArray + (kArraySize - 10));
222 for(int i = 0; i < 10; i++) // insert the remaining elements via the other insert function.
223 {
224 pair<IHM_SW::iterator, bool> result = ihmSW1.insert(swArray[(kArraySize - 10) + i]);
225 VERIFY(result.second == true);
226 }
227
228 VERIFY(ihmSW1.size() == kArraySize);
229 VERIFY(ihmSW1.validate());
230
231 for(size_t i = 0; i < kArraySize; i++)
232 {
233 // Try to re-insert the elements. All insertions should fail.
234 pair<IHM_SW::iterator, bool> result = ihmSW1.insert(swArray[i]);
235 VERIFY(result.second == false);
236 }
237
238 VERIFY(ihmSW1.size() == kArraySize);
239 VERIFY(!ihmSW1.empty());
240 VERIFY(ihmSW1.validate());
241
242 ihmSW2.clear();
243 ihmSW1.swap(ihmSW2);
244
245
246 // size_type size() const;
247 // bool empty() const;
248 // size_type count(const key_type& k) const;
249 // size_type bucket_size(size_type n) const;
250 // float load_factor() const;
251 // size_type bucket(const key_type& k) const
252
253 VERIFY(ihmSW1.validate());
254 VERIFY(ihmSW2.validate());
255 VERIFY(ihmSW1.size() == 0);
256 VERIFY(ihmSW1.empty());
257 VERIFY(ihmSW2.size() == kArraySize);
258 VERIFY(!ihmSW2.empty());
259 VERIFY(ihmSW1.load_factor() == 0.f);
260 VERIFY(ihmSW2.load_factor() > 2.f);
261 VERIFY(ihmSW1.count(0) == 0);
262 VERIFY(ihmSW1.count(999999) == 0);
263 VERIFY(ihmSW2.count(0) == 1);
264 VERIFY(ihmSW2.count(999999) == 0);
265 VERIFY(ihmSW2.bucket_size(0) == 3); // We just happen to know this should be so based on the distribution.
266 VERIFY(ihmSW2.bucket(13) == (13 % kBucketCount)); // We know this is so because our hash function simply returns n.
267 VERIFY(ihmSW2.bucket(10000) == (10000 % kBucketCount)); // We know this is so because our hash function simply returns n.
268
269
270 // iterator begin();
271 // const_iterator begin() const;
272
273 ihmSW1.swap(ihmSW2);
274 int nSum = 0;
275
276 for(IHM_SW::iterator it = ihmSW1.begin(); it != ihmSW1.end(); ++it)
277 {
278 const SetWidget& sw = *it; // Recall that set iterators are const_iterators.
279
280 nSum += sw.mX;
281
282 const int iresult = ihmSW1.validate_iterator(it);
283 VERIFY(iresult == (isf_valid | isf_current | isf_can_dereference));
284
285 IHM_SW::iterator itf = ihmSW1.find(sw.mX);
286 VERIFY(itf == it);
287 }
288
289 VERIFY(nSum == nExpectedKeySum);
290
291
292 // iterator end();
293 // const_iterator end() const;
294
295 const IHM_SW& ihmSW1Const = ihmSW1;
296
297 for(IHM_SW::const_iterator itc = ihmSW1Const.begin(); itc != ihmSW1Const.end(); ++itc)
298 {
299 const SetWidget& sw = *itc;
300
301 IHM_SW::const_iterator itf = ihmSW1.find(sw.mX);
302 VERIFY(itf == itc);
303 }
304
305
306 // local_iterator begin(size_type n)
307 // local_iterator end(size_type)
308
309 for(IHM_SW::local_iterator itl = ihmSW1.begin(5); itl != ihmSW1.end(5); ++itl)
310 {
311 const SetWidget& sw = *itl; // Recall that set iterators are const_iterators.
312
313 VERIFY((sw.mX % kBucketCount) == 5);
314 }
315
316
317 // const_local_iterator begin(size_type n) const
318 // const_local_iterator end(size_type) const
319
320 for(IHM_SW::const_local_iterator itlc = ihmSW1Const.begin(5); itlc != ihmSW1Const.end(5); ++itlc)
321 {
322 const SetWidget& sw = *itlc;
323
324 VERIFY((sw.mX % kBucketCount) == 5);
325 }
326
327
328 // iterator find(const key_type& k);
329 // const_iterator find(const key_type& k) const;
330
331 IHM_SW::iterator itf = ihmSW1.find(SetWidget(99999));
332 VERIFY(itf == ihmSW1.end());
333
334 IHM_SW::const_iterator itfc = ihmSW1Const.find(SetWidget(99999));
335 VERIFY(itfc == ihmSW1Const.end());
336
337
338 // iterator find_as(const U& u);
339 // const_iterator find_as(const U& u) const;
340
341 //itf = ihmSW1.find_as(SetWidget(7)); // Can't work unless there was a default eastl::hash function for SetWidget.
342 //VERIFY(itf->mX == 7);
343
344 //itfc = ihmSW1Const.find_as(SetWidget(7));
345 //VERIFY(itfc->mX == 7);
346
347
348 // iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate);
349 // const_iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate) const;
350
351 itf = ihmSW1.find_as(SetWidgetComparable(7), SWCHash(), eastl::equal_to_2<SetWidget, SetWidgetComparable>());
352 VERIFY(itf->mX == 7);
353
354 itfc = ihmSW1Const.find_as(SetWidgetComparable(7), SWCHash(), eastl::equal_to_2<SetWidget, SetWidgetComparable>());
355 VERIFY(itfc->mX == 7);
356
357
358 // iterator erase(iterator);
359 // iterator erase(iterator, iterator);
360 // size_type erase(const key_type&);
361
362 eastl_size_t n = ihmSW1.erase(SetWidget(99999));
363 VERIFY(n == 0);
364
365 n = ihmSW1.erase(SetWidget(17));
366 VERIFY(n == 1);
367
368 itf = ihmSW1.find(SetWidget(18));
369 VERIFY(itf != ihmSW1.end());
370 VERIFY(ihmSW1.validate_iterator(itf) == (isf_valid | isf_current | isf_can_dereference));
371
372 itf = ihmSW1.erase(itf);
373 VERIFY(itf != ihmSW1.end());
374 VERIFY(ihmSW1.validate_iterator(itf) == (isf_valid | isf_current | isf_can_dereference));
375
376 itf = ihmSW1.find(SetWidget(18));
377 VERIFY(itf == ihmSW1.end());
378
379 itf = ihmSW1.find(SetWidget(19));
380 VERIFY(itf != ihmSW1.end());
381
382 IHM_SW::iterator itf2(itf);
383 eastl::advance(itf2, 7);
384 VERIFY(itf2 != ihmSW1.end());
385 VERIFY(ihmSW1.validate_iterator(itf2) == (isf_valid | isf_current | isf_can_dereference));
386
387 itf = ihmSW1.erase(itf, itf2);
388 VERIFY(itf != ihmSW1.end());
389 VERIFY(ihmSW1.validate_iterator(itf) == (isf_valid | isf_current | isf_can_dereference));
390
391 itf = ihmSW1.find(SetWidget(19));
392 VERIFY(itf == ihmSW1.end());
393
394
395 // eastl::pair<iterator, iterator> equal_range(const key_type& k);
396 // eastl::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
397
398 eastl::pair<IHM_SW::iterator, IHM_SW::iterator> p = ihmSW1.equal_range(SetWidget(1));
399 VERIFY(p.first != ihmSW1.end());
400 VERIFY(p.second != ihmSW1.end());
401
402 eastl::pair<IHM_SW::const_iterator, IHM_SW::const_iterator> pc = ihmSW1Const.equal_range(SetWidget(1));
403 VERIFY(pc.first != ihmSW1Const.end());
404 VERIFY(pc.second != ihmSW1Const.end());
405
406
407 // void clear();
408 // bool validate() const;
409 // int validate_iterator(const_iterator i) const;
410
411 IHM_SW::iterator itTest;
412 int iresult = ihmSW1.validate_iterator(itTest);
413 VERIFY(iresult == isf_none);
414
415 itTest = ihmSW1.begin();
416 iresult = ihmSW1.validate_iterator(itTest);
417 VERIFY(iresult == (isf_valid | isf_current | isf_can_dereference));
418
419 itTest = ihmSW1.end();
420 iresult = ihmSW1.validate_iterator(itTest);
421 VERIFY(iresult == (isf_valid | isf_current));
422
423 ihmSW1.clear();
424 ihmSW2.clear();
425 VERIFY(ihmSW1.validate());
426 VERIFY(ihmSW2.validate());
427
428 itTest = ihmSW1.begin();
429 iresult = ihmSW1.validate_iterator(itTest);
430 VERIFY(iresult == (isf_valid | isf_current));
431 }
432
433
434 {
435 // Test intrusive_hash_map
436
437 const size_t kBucketCount = 37;
438 typedef intrusive_hash_map<int, MapWidget, kBucketCount> IHM_MW;
439
440 const size_t kArraySize = 100;
441 MapWidget mwArray[kArraySize];
442
443 int nExpectedKeySum = 0; // We use this as a checksum in order to do validity checks below.
444
445 for(size_t i = 0; i < kArraySize; i++)
446 {
447 mwArray[i].mKey = (int)i;
448 mwArray[i].mX = (int)i;
449 nExpectedKeySum += (int)i;
450 }
451
452
453 // intrusive_hashtable(const Hash&, const Equal&);
454 // void swap(this_type& x);
455 // size_type size() const;
456 // bool empty() const;
457 // size_type bucket_count() const;
458 // size_type bucket_size(size_type n) const;
459 // float load_factor() const;
460 // void clear();
461 // bool validate() const;
462
463 IHM_MW ihmMW1;
464 IHM_MW ihmMW2;
465
466 VERIFY(ihmMW1.size() == 0);
467 VERIFY(ihmMW1.empty());
468 VERIFY(ihmMW1.validate());
469 VERIFY(ihmMW2.validate());
470
471 ihmMW1.swap(ihmMW2);
472
473 VERIFY(ihmMW1.validate());
474 VERIFY(ihmMW2.validate());
475 VERIFY(ihmMW2.bucket_count() == kBucketCount);
476 VERIFY(ihmMW2.bucket_size(0) == 0);
477 VERIFY(ihmMW2.bucket_size(kBucketCount - 1) == 0);
478 VERIFY(ihmMW1.load_factor() == 0.f);
479 VERIFY(ihmMW2.load_factor() == 0.f);
480
481 ihmMW1.clear();
482 VERIFY(ihmMW1.validate());
483 VERIFY(ihmMW1.begin() == ihmMW1.end());
484
485
486 // void insert(InputIterator first, InputIterator last);
487 // insert_return_type insert(value_type& value);
488 // void swap(this_type& x);
489 // void clear();
490
491 ihmMW1.clear();
492 ihmMW1.insert(mwArray, mwArray + (kArraySize - 10));
493 for(int i = 0; i < 10; i++) // insert the remaining elements via the other insert function.
494 {
495 pair<IHM_MW::iterator, bool> result = ihmMW1.insert(mwArray[(kArraySize - 10) + i]);
496 VERIFY(result.second == true);
497 }
498
499 VERIFY(ihmMW1.size() == kArraySize);
500 VERIFY(ihmMW1.validate());
501
502 for(size_t i = 0; i < kArraySize; i++)
503 {
504 // Try to re-insert the elements. All insertions should fail.
505 pair<IHM_MW::iterator, bool> result = ihmMW1.insert(mwArray[i]);
506 VERIFY(result.second == false);
507 }
508
509 VERIFY(ihmMW1.size() == kArraySize);
510 VERIFY(!ihmMW1.empty());
511 VERIFY(ihmMW1.validate());
512
513 ihmMW2.clear();
514 ihmMW1.swap(ihmMW2);
515
516
517 // size_type size() const;
518 // bool empty() const;
519 // size_type count(const key_type& k) const;
520 // size_type bucket_size(size_type n) const;
521 // float load_factor() const;
522 // size_type bucket(const key_type& k) const
523
524 VERIFY(ihmMW1.validate());
525 VERIFY(ihmMW2.validate());
526 VERIFY(ihmMW1.size() == 0);
527 VERIFY(ihmMW1.empty());
528 VERIFY(ihmMW2.size() == kArraySize);
529 VERIFY(!ihmMW2.empty());
530 VERIFY(ihmMW1.load_factor() == 0.f);
531 VERIFY(ihmMW2.load_factor() > 2.f);
532 VERIFY(ihmMW1.count(0) == 0);
533 VERIFY(ihmMW1.count(999999) == 0);
534 VERIFY(ihmMW2.count(0) == 1);
535 VERIFY(ihmMW2.count(999999) == 0);
536 VERIFY(ihmMW2.bucket_size(0) == 3); // We just happen to know this should be so based on the distribution.
537 VERIFY(ihmMW2.bucket(13) == (13 % kBucketCount)); // We know this is so because our hash function simply returns n.
538 VERIFY(ihmMW2.bucket(10000) == (10000 % kBucketCount)); // We know this is so because our hash function simply returns n.
539
540
541 // iterator begin();
542 // const_iterator begin() const;
543
544 ihmMW1.swap(ihmMW2);
545 int nSum = 0;
546
547 for(IHM_MW::iterator it = ihmMW1.begin(); it != ihmMW1.end(); ++it)
548 {
549 IHM_MW::value_type& v = *it;
550
551 VERIFY(v.mKey == v.mX); // We intentionally made this so above.
552 nSum += v.mKey;
553
554 const int iresult = ihmMW1.validate_iterator(it);
555 VERIFY(iresult == (isf_valid | isf_current | isf_can_dereference));
556
557 IHM_MW::iterator itf = ihmMW1.find(v.mKey);
558 VERIFY(itf == it);
559 }
560
561 VERIFY(nSum == nExpectedKeySum);
562
563
564 // iterator end();
565 // const_iterator end() const;
566
567 const IHM_MW& ihmMW1Const = ihmMW1;
568
569 for(IHM_MW::const_iterator itc = ihmMW1Const.begin(); itc != ihmMW1Const.end(); ++itc)
570 {
571 const IHM_MW::value_type& v = *itc;
572
573 VERIFY(v.mKey == v.mX); // We intentionally made this so above.
574
575 IHM_MW::const_iterator itf = ihmMW1Const.find(v.mKey);
576 VERIFY(itf == itc);
577 }
578
579
580 // local_iterator begin(size_type n)
581 // local_iterator end(size_type)
582
583 for(IHM_MW::local_iterator itl = ihmMW1.begin(5); itl != ihmMW1.end(5); ++itl)
584 {
585 IHM_MW::value_type& v = *itl;
586
587 VERIFY(v.mKey == v.mX); // We intentionally made this so above.
588 }
589
590
591 // const_local_iterator begin(size_type n) const
592 // const_local_iterator end(size_type) const
593
594 for(IHM_MW::const_local_iterator itlc = ihmMW1Const.begin(5); itlc != ihmMW1Const.end(5); ++itlc)
595 {
596 const IHM_MW::value_type& v = *itlc;
597
598 VERIFY(v.mKey == v.mX); // We intentionally made this so above.
599 }
600
601
602 // iterator find(const key_type& k);
603 // const_iterator find(const key_type& k) const;
604
605 IHM_MW::iterator itf = ihmMW1.find(99999);
606 VERIFY(itf == ihmMW1.end());
607
608 IHM_MW::const_iterator itfc = ihmMW1Const.find(99999);
609 VERIFY(itfc == ihmMW1Const.end());
610
611
612 // iterator find_as(const U& u);
613 // const_iterator find_as(const U& u) const;
614
615 itf = ihmMW1.find_as(7.f);
616 VERIFY(itf->mKey == 7);
617
618 itfc = ihmMW1Const.find_as(7.f);
619 VERIFY(itfc->mKey == 7);
620
621
622 // iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate);
623 // const_iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate) const;
624
625 itf = ihmMW1.find_as(7.f, eastl::hash<float>(), eastl::equal_to_2<int, float>());
626 VERIFY(itf->mKey == 7);
627
628 itfc = ihmMW1Const.find_as(7.f, eastl::hash<float>(), eastl::equal_to_2<int, float>());
629 VERIFY(itfc->mKey == 7);
630
631
632 // iterator erase(iterator);
633 // iterator erase(iterator, iterator);
634 // size_type erase(const key_type&);
635
636 eastl_size_t n = ihmMW1.erase(99999);
637 VERIFY(n == 0);
638
639 n = ihmMW1.erase(17);
640 VERIFY(n == 1);
641
642 itf = ihmMW1.find(18);
643 VERIFY(itf != ihmMW1.end());
644 VERIFY(ihmMW1.validate_iterator(itf) == (isf_valid | isf_current | isf_can_dereference));
645
646 itf = ihmMW1.erase(itf);
647 VERIFY(itf != ihmMW1.end());
648 VERIFY(ihmMW1.validate_iterator(itf) == (isf_valid | isf_current | isf_can_dereference));
649
650 itf = ihmMW1.find(18);
651 VERIFY(itf == ihmMW1.end());
652
653 itf = ihmMW1.find(19);
654 VERIFY(itf != ihmMW1.end());
655
656 IHM_MW::iterator itf2(itf);
657 eastl::advance(itf2, 7);
658 VERIFY(itf2 != ihmMW1.end());
659 VERIFY(ihmMW1.validate_iterator(itf2) == (isf_valid | isf_current | isf_can_dereference));
660
661 itf = ihmMW1.erase(itf, itf2);
662 VERIFY(itf != ihmMW1.end());
663 VERIFY(ihmMW1.validate_iterator(itf) == (isf_valid | isf_current | isf_can_dereference));
664
665 itf = ihmMW1.find(19);
666 VERIFY(itf == ihmMW1.end());
667
668
669 // eastl::pair<iterator, iterator> equal_range(const key_type& k);
670 // eastl::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
671
672 eastl::pair<IHM_MW::iterator, IHM_MW::iterator> p = ihmMW1.equal_range(1);
673 VERIFY(p.first != ihmMW1.end());
674 VERIFY(p.second != ihmMW1.end());
675
676 eastl::pair<IHM_MW::const_iterator, IHM_MW::const_iterator> pc = ihmMW1Const.equal_range(1);
677 VERIFY(pc.first != ihmMW1Const.end());
678 VERIFY(pc.second != ihmMW1Const.end());
679
680
681 // void clear();
682 // bool validate() const;
683 // int validate_iterator(const_iterator i) const;
684
685 IHM_MW::iterator itTest;
686 int iresult = ihmMW1.validate_iterator(itTest);
687 VERIFY(iresult == isf_none);
688
689 itTest = ihmMW1.begin();
690 iresult = ihmMW1.validate_iterator(itTest);
691 VERIFY(iresult == (isf_valid | isf_current | isf_can_dereference));
692
693 itTest = ihmMW1.end();
694 iresult = ihmMW1.validate_iterator(itTest);
695 VERIFY(iresult == (isf_valid | isf_current));
696
697 ihmMW1.clear();
698 ihmMW2.clear();
699 VERIFY(ihmMW1.validate());
700 VERIFY(ihmMW2.validate());
701
702 itTest = ihmMW1.begin();
703 iresult = ihmMW1.validate_iterator(itTest);
704 VERIFY(iresult == (isf_valid | isf_current));
705 }
706
707
708 {
709 // Test case of single bucket.
710 eastl::intrusive_hash_set<SetWidget, 1, SWHash> hs;
711 SetWidget node1, node2, node3;
712
713 node1.mX = 1;
714 node2.mX = 2;
715 node3.mX = 3;
716
717 hs.insert(node1);
718 hs.insert(node2);
719 hs.insert(node3);
720
721 const eastl_size_t removeCount = hs.erase(node3);
722 VERIFY(removeCount == 1);
723 }
724
725
726 {
727 // Test intrusive_hashtable_iterator(value_type* pNode, value_type** pBucket = NULL)
728 eastl::intrusive_hash_set<SetWidget, 37, SWHash> hs;
729 SetWidget node1, node2, node3;
730
731 node1.mX = 1;
732 node2.mX = 2;
733 node3.mX = 3;
734
735 hs.insert(node1);
736 hs.insert(node2);
737 hs.insert(node3);
738
739 VERIFY(hs.validate());
740
741 hs.remove(node1);
742 hs.remove(node2);
743 hs.remove(node3);
744
745 VERIFY(hs.validate());
746
747 hs.insert(node1);
748 hs.insert(node2);
749 hs.insert(node3);
750
751 VERIFY(hs.validate());
752 }
753
754 return nErrorCount;
755 }
756
757
758
759
760
761
762
763
764
765
766
767
768