]> git.ipfire.org Git - thirdparty/gcc.git/blame - libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Update Copyright years for files modified in 2011 and/or 2012.
[thirdparty/gcc.git] / libstdc++-v3 / testsuite / util / regression / rand / assoc / container_rand_regression_test.tcc
CommitLineData
2661beb5 1// -*- C++ -*-
2
71e45bc2 3// Copyright (C) 2005, 2006, 2008, 2009, 2010, 2011
4// Free Software Foundation, Inc.
2661beb5 5//
6// This file is part of the GNU ISO C++ Library. This library is free
7// software; you can redistribute it and/or modify it under the terms
8// of the GNU General Public License as published by the Free Software
6bc9506f 9// Foundation; either version 3, or (at your option) any later
2661beb5 10// version.
11
12// This library is distributed in the hope that it will be useful, but
13// WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15// General Public License for more details.
16
17// You should have received a copy of the GNU General Public License
6bc9506f 18// along with this library; see the file COPYING3. If not see
19// <http://www.gnu.org/licenses/>.
2661beb5 20
2661beb5 21
22// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
23
24// Permission to use, copy, modify, sell, and distribute this software
25// is hereby granted without fee, provided that the above copyright
26// notice appears in all copies, and that both that copyright notice
27// and this permission notice appear in supporting documentation. None
28// of the above authors, nor IBM Haifa Research Laboratories, make any
29// representation about the suitability of this software for any
30// purpose. It is provided "as is" without express or implied
31// warranty.
32
33/**
34 * @file container_rand_regression_test.tcc
35 * Contains a random regression test for a specific container type.
36 */
37
38#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
39#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
40
41// Constructors/Destructors.
42PB_DS_CLASS_T_DEC
43PB_DS_CLASS_C_DEC::
44container_rand_regression_test(unsigned long seed, size_t n, size_t m,
45 double tp, double ip, double ep, double cp,
46 double mp, bool disp)
47: m_seed((seed == 0) ? twister_rand_gen::get_time_determined_seed() : seed),
48 m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_ep(ep), m_cp(cp), m_mp(mp),
e4bb1925 49 m_disp(disp), m_p_c(0)
2661beb5 50{ }
51
52PB_DS_CLASS_T_DEC
53PB_DS_CLASS_C_DEC::
54~container_rand_regression_test()
55{ }
56
57PB_DS_CLASS_T_DEC
58bool
59PB_DS_CLASS_C_DEC::
60default_constructor()
61{
62 PB_DS_TRACE("default_constructor");
63 bool done = true;
d6816d50 64 m_alloc.set_probability(m_tp);
2661beb5 65
66 try
67 {
68 m_p_c = new Cntnr;
69 }
0bab73e9 70 catch(__gnu_cxx::forced_error&)
2661beb5 71 {
72 done = false;
73 }
74
e4bb1925 75 if (m_p_c)
2661beb5 76 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
77 return done;
78}
79
80PB_DS_CLASS_T_DEC
81void
82PB_DS_CLASS_C_DEC::
83swap()
84{
85 PB_DS_TRACE("swap");
d6816d50 86 m_alloc.set_probability(0);
2661beb5 87 Cntnr* p_c = new Cntnr;
d6816d50 88 m_alloc.set_probability(1);
2661beb5 89 p_c->swap(*m_p_c);
90 std::swap(p_c, m_p_c);
91 delete p_c;
92 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
93}
94
95PB_DS_CLASS_T_DEC
96bool
97PB_DS_CLASS_C_DEC::
98copy_constructor()
99{
100 PB_DS_TRACE("copy_constructor");
101 bool done = true;
e4bb1925 102 Cntnr* p_c = 0;
d6816d50 103 m_alloc.set_probability(m_tp);
104 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 105
106 try
107 {
108 p_c = new Cntnr(*m_p_c);
109 std::swap(p_c, m_p_c);
110 }
0bab73e9 111 catch(__gnu_cxx::forced_error&)
2661beb5 112 {
113 done = false;
114 }
115
116 delete p_c;
117 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
118 return done;
119}
120
121PB_DS_CLASS_T_DEC
122bool
123PB_DS_CLASS_C_DEC::
124assignment_operator()
125{
126 PB_DS_TRACE("assignment operator");
127 bool done = true;
e4bb1925 128 Cntnr* p_c = 0;
d6816d50 129 m_alloc.set_probability(m_tp);
130 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 131
132 try
133 {
134 p_c = new Cntnr();
4f4a327e 135 *p_c = *m_p_c;
2661beb5 136 std::swap(p_c, m_p_c);
137 }
0bab73e9 138 catch(__gnu_cxx::forced_error&)
2661beb5 139 {
140 done = false;
141 }
142
143 delete p_c;
144 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
145 return done;
146}
147
148PB_DS_CLASS_T_DEC
149bool
150PB_DS_CLASS_C_DEC::
151it_constructor()
152{
153 PB_DS_TRACE("it_constructor");
154 return it_constructor_imp(typename Cntnr::container_category());
155}
156
157PB_DS_CLASS_T_DEC
158bool
159PB_DS_CLASS_C_DEC::
160it_constructor_imp(__gnu_pbds::cc_hash_tag)
161{
162 bool done = true;
e4bb1925 163 Cntnr* p_c = 0;
d6816d50 164 m_alloc.set_probability(m_tp);
165 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 166
167 try
168 {
169 switch(get_next_sub_op(8))
170 {
171 case 0:
172 p_c = new Cntnr(m_p_c->get_hash_fn());
173 m_native_c.clear();
174 break;
175 case 1:
176 p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn());
177 m_native_c.clear();
178 break;
179 case 2:
180 p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
181 m_p_c->get_comb_hash_fn());
182 m_native_c.clear();
183 break;
184 case 3:
185 p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
186 m_p_c->get_comb_hash_fn(),
187 m_p_c->get_resize_policy());
188 m_native_c.clear();
189 break;
190 case 4:
191 p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
192 break;
193 case 5:
194 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn());
195 break;
196 case 6:
197 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
198 m_p_c->get_eq_fn());
199 break;
200 case 7:
201 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
202 m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn());
203 break;
204 case 8:
205 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
206 m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn(),
207 m_p_c->get_resize_policy());
208 break;
209 default:
210 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
211 };
212 std::swap(p_c, m_p_c);
213 }
0bab73e9 214 catch (__gnu_cxx::forced_error&)
2661beb5 215 {
216 done = false;
217 }
218
219 delete p_c;
220 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
221 return done;
222}
223
224PB_DS_CLASS_T_DEC
225bool
226PB_DS_CLASS_C_DEC::
227it_constructor_imp(__gnu_pbds::gp_hash_tag)
228{
229 bool done = true;
e4bb1925 230 Cntnr* p_c = 0;
d6816d50 231 m_alloc.set_probability(m_tp);
232 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 233
234 try
235 {
236 switch(get_next_sub_op(11))
237 {
238 case 0:
239 p_c = new Cntnr(m_p_c->get_hash_fn());
240 m_native_c.clear();
241 break;
242 case 1:
243 p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn());
244 m_native_c.clear();
245 break;
246 case 2:
247 p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
248 m_p_c->get_comb_probe_fn());
249 m_native_c.clear();
250 break;
251 case 3:
252 p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
253 m_p_c->get_comb_probe_fn());
254 m_native_c.clear();
255 break;
256 case 4:
257 p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
258 m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn());
259 m_native_c.clear();
260 break;
261 case 5:
262 p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
263 m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn(),
264 m_p_c->get_resize_policy());
265 m_native_c.clear();
266 break;
267 case 6:
268 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn());
269 break;
270 case 7:
271 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
272 m_p_c->get_eq_fn());
273 break;
274 case 8:
275 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
276 m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn());
277 break;
278 case 9:
279 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
280 m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn());
281 break;
282 case 10:
283 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
284 m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(),
285 m_p_c->get_probe_fn());
286 break;
287 case 11:
288 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
289 m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(),
290 m_p_c->get_probe_fn(), m_p_c->get_resize_policy());
291 break;
292 default:
293 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
294 };
295 std::swap(p_c, m_p_c);
296 }
0bab73e9 297 catch (__gnu_cxx::forced_error&)
2661beb5 298 {
299 done = false;
300 }
301
302 delete p_c;
303 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
304 return done;
305}
306
307PB_DS_CLASS_T_DEC
308bool
309PB_DS_CLASS_C_DEC::
310it_constructor_imp(__gnu_pbds::tree_tag)
311{
312 bool done = true;
e4bb1925 313 Cntnr* p_c = 0;
d6816d50 314 m_alloc.set_probability(m_tp);
315 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 316
317 try
318 {
319 switch(get_next_sub_op(2))
320 {
321 case 0:
322 p_c = new Cntnr(m_p_c->get_cmp_fn());
323 m_native_c.clear();
324 break;
325 case 1:
326 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_cmp_fn());
327 break;
328 default:
329 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
330 };
331 std::swap(p_c, m_p_c);
332 }
0bab73e9 333 catch (__gnu_cxx::forced_error&)
2661beb5 334 {
335 done = false;
336 }
337
338 delete p_c;
339 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
340 return done;
341}
342
343PB_DS_CLASS_T_DEC
344bool
345PB_DS_CLASS_C_DEC::
346it_constructor_imp(__gnu_pbds::list_update_tag)
347{
348 bool done = true;
e4bb1925 349 Cntnr* p_c = 0;
d6816d50 350 m_alloc.set_probability(m_tp);
351 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 352
353 try
354 {
355 p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
356 std::swap(p_c, m_p_c);
357 }
0bab73e9 358 catch (__gnu_cxx::forced_error&)
2661beb5 359 {
360 done = false;
361 }
362
363 delete p_c;
364 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
365 return done;
366}
367
368PB_DS_CLASS_T_DEC
369bool
370PB_DS_CLASS_C_DEC::
371it_constructor_imp(__gnu_pbds::pat_trie_tag)
372{
373 bool done = true;
e4bb1925 374 Cntnr* p_c = 0;
d6816d50 375 m_alloc.set_probability(m_tp);
376 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 377
378 try
379 {
380 switch(get_next_sub_op(2))
381 {
382 case 0:
4f4a327e 383 p_c = new Cntnr(m_p_c->get_access_traits());
2661beb5 384 m_native_c.clear();
385 break;
386 case 1:
387 p_c = new Cntnr(m_p_c->begin(), m_p_c->end(),
4f4a327e 388 m_p_c->get_access_traits());
2661beb5 389 break;
390 default:
391 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
392 };
393
394 std::swap(p_c, m_p_c);
395 }
0bab73e9 396 catch (__gnu_cxx::forced_error&)
2661beb5 397 {
398 done = false;
399 }
400
401 delete p_c;
402 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
403 return done;
404}
405
406// Cmp.
407PB_DS_CLASS_T_DEC
408void
409PB_DS_CLASS_C_DEC::
410cmp(const Cntnr& r_c, const native_type& r_native_c,
411 const std::string& r_call_fn)
412{
d6816d50 413 m_alloc.set_probability(1);
2661beb5 414 const size_t size = r_c.size();
415 const size_t native_size = r_native_c.size();
416 PB_DS_THROW_IF_FAILED(size == native_size,
417 size << " " << native_size, &r_c, &r_native_c);
418
419 const bool empty = r_c.empty();
420 const bool native_empty = r_native_c.empty();
421 PB_DS_THROW_IF_FAILED(empty == native_empty,
422 empty << " " << native_empty, &r_c, &r_native_c);
423
424 try
425 {
426 basic_cmp_(r_c, r_native_c);
427 cmp_(r_c, r_native_c);
428 }
429 catch(...)
430 {
431 PB_DS_THROW_IF_FAILED(false, "call-fn: " + r_call_fn, &r_c, &r_native_c);
432 }
433}
434
435PB_DS_CLASS_T_DEC
436void
437PB_DS_CLASS_C_DEC::
438basic_cmp_(const Cntnr& r_c, const native_type& r_native_c)
439{
440 PB_DS_SET_DESTRUCT_PRINT
441
442 if (static_cast<size_t>(std::distance(r_c.begin(), r_c.end())) != r_c.size())
443 PB_DS_THROW_IF_FAILED(false,
444 static_cast<unsigned long>(std::distance(r_c.begin(), r_c.end())) << " " << static_cast<unsigned long>(r_c.size()), &r_c, &r_native_c);
445
446 typename native_type::const_iterator it = r_native_c.begin();
447 while (it != r_native_c.end())
448 {
449 typename native_type::key_type native_key = test_traits::extract_native_key(*it);
450
d6816d50 451 m_alloc.set_probability(0);
2661beb5 452 const key_type k = native_key;
d6816d50 453 m_alloc.set_probability(1);
4f4a327e 454 typename cntnr::point_const_iterator found_it = r_c.find(k);
2661beb5 455 PB_DS_THROW_IF_FAILED(found_it != r_c.end(),
456 test_traits::native_val_to_string(*it),
457 &r_c, &r_native_c);
458
459 if (!test_traits::cmp(*found_it, * it))
460 PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c);
461
462 ++it;
463 }
464 PB_DS_CANCEL_DESTRUCT_PRINT
465}
466
467PB_DS_CLASS_T_DEC
468void
469PB_DS_CLASS_C_DEC::
470cmp_(const Cntnr& r_c, const native_type& r_native_c)
471{
472 enum
473 {
474 order_preserving = container_traits::order_preserving,
475 back_order_preserving = container_traits::order_preserving
476 &&
477 !__gnu_pbds::detail::is_same<
478 typename std::iterator_traits<
479 typename cntnr::const_iterator>::iterator_category,
480 std::forward_iterator_tag>::value,
481 reverse_iteration = container_traits::reverse_iteration,
482 order_statistics = test_traits::order_statistics,
483 prefix_search = test_traits::prefix_search,
484 has_mapped = !__gnu_pbds::detail::is_same<
485 typename Cntnr::mapped_type,
4f4a327e 486 __gnu_pbds::null_type>::value
2661beb5 487 };
488
489 order_preserving_cmp_imp(r_c, r_native_c,
490 __gnu_pbds::detail::integral_constant<int,order_preserving>());
491
492 back_order_preserving_cmp_imp(r_c, r_native_c,
493 __gnu_pbds::detail::integral_constant<int,back_order_preserving>());
494
495 order_statistics_cmp_imp(r_c, r_native_c,
496 __gnu_pbds::detail::integral_constant<int,order_statistics>());
497
498 prefix_search_cmp_imp(r_c, r_native_c,
499 __gnu_pbds::detail::integral_constant<int,prefix_search>());
500
501 reverse_iteration_cmp_imp(r_c, r_native_c,
502 __gnu_pbds::detail::integral_constant<int,reverse_iteration>());
503
504 lower_bound_cmp_imp(r_c, r_native_c,
505 __gnu_pbds::detail::integral_constant<int,order_preserving>());
506
507 upper_bound_cmp_imp(r_c, r_native_c,
508 __gnu_pbds::detail::integral_constant<int,order_preserving>());
509}
510
511PB_DS_CLASS_T_DEC
512void
513PB_DS_CLASS_C_DEC::
514order_preserving_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
515{ }
516
517PB_DS_CLASS_T_DEC
518void
519PB_DS_CLASS_C_DEC::
520order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
521{
522 PB_DS_SET_DESTRUCT_PRINT
523
524 typename cntnr::const_iterator b = r_c.begin();
525 typename cntnr::const_iterator e = r_c.end();
526
527 typename native_type::const_iterator native_b = r_native_c.begin();
528 typename native_type::const_iterator native_e = r_native_c.end();
529
530 try
531 {
532 it_cmp_imp(b, e, native_b, native_e);
533 }
534 catch(...)
535 {
536 PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
537 }
538
539 try
540 {
541 back_it_cmp_imp(b, e, native_b, native_e);
542 }
543 catch(...)
544 {
545 PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
546 }
547
548 PB_DS_CANCEL_DESTRUCT_PRINT
549}
550
551PB_DS_CLASS_T_DEC
552void
553PB_DS_CLASS_C_DEC::
554back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
555 __gnu_pbds::detail::false_type)
556{ }
557
558PB_DS_CLASS_T_DEC
559void
560PB_DS_CLASS_C_DEC::
561back_order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c,
562 __gnu_pbds::detail::true_type)
563{
564 PB_DS_SET_DESTRUCT_PRINT
565 typename cntnr::const_iterator b = r_c.begin();
566 typename cntnr::const_iterator e = r_c.end();
567 typename native_type::const_iterator native_b = r_native_c.begin();
568 typename native_type::const_iterator native_e = r_native_c.end();
569 it_cmp_imp(b, e, native_b, native_e);
570 PB_DS_CANCEL_DESTRUCT_PRINT
571}
572
573PB_DS_CLASS_T_DEC
574void
575PB_DS_CLASS_C_DEC::
576reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
577 __gnu_pbds::detail::false_type)
578{ }
579
580PB_DS_CLASS_T_DEC
581void
582PB_DS_CLASS_C_DEC::
583reverse_iteration_cmp_imp(const Cntnr& r_c, const native_type&r_native_c, __gnu_pbds::detail::true_type)
584{
585 PB_DS_SET_DESTRUCT_PRINT
586
587 typename cntnr::const_reverse_iterator b = r_c.rbegin();
588 typename cntnr::const_reverse_iterator e = r_c.rend();
589
590 typename native_type::const_reverse_iterator native_b = r_native_c.rbegin();
591 typename native_type::const_reverse_iterator native_e = r_native_c.rend();
592
593 try
594 {
595 it_cmp_imp(b, e, native_b, native_e);
596 }
597 catch(...)
598 {
599 PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
600 }
601
602 try
603 {
604 back_it_cmp_imp(b, e, native_b, native_e);
605 }
606 catch(...)
607 {
608 PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
609 }
610
611 PB_DS_CANCEL_DESTRUCT_PRINT
612}
613
614PB_DS_CLASS_T_DEC
615void
616PB_DS_CLASS_C_DEC::
617order_statistics_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
618{ }
619
620PB_DS_CLASS_T_DEC
621void
622PB_DS_CLASS_C_DEC::
623order_statistics_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
624{
625 {
d6816d50 626 m_alloc.set_probability(0);
2661beb5 627 const key_type k = test_traits::generate_key(m_g, m_m);
d6816d50 628 m_alloc.set_probability(1);
2661beb5 629 const size_type order = r_c.order_of_key(k);
630 const size_type native_order = std::distance(r_native_c.begin(),
631 r_native_c.lower_bound(test_traits::native_key(k)));
632
633 PB_DS_THROW_IF_FAILED(order == native_order,
634 test_traits::key_to_string(k) << " " <<
635 static_cast<unsigned long>(order) << " " <<
636 static_cast<unsigned long>(native_order),
637 &r_c,
638 &r_native_c);
639 }
640
641 const size_type rand_ord =
642 static_cast<size_t>(m_g.get_unsigned_long(0,
643 2 * static_cast<unsigned long>(m_m)));
644
645 typename cntnr::const_iterator it = r_c.find_by_order(rand_ord);
646 typename native_type::const_iterator native_it = r_native_c.begin();
647 std::advance(native_it, std::min(rand_ord, r_native_c.size()));
648 if (it == r_c.end()&& native_it != r_native_c.end())
649 PB_DS_THROW_IF_FAILED(false,
650 static_cast<unsigned long>(rand_ord),
651 m_p_c,
652 &m_native_c);
653
654 if (it != r_c.end()&& native_it == r_native_c.end())
655 PB_DS_THROW_IF_FAILED(false,
656 static_cast<unsigned long>(rand_ord),
657 m_p_c,
658 &m_native_c);
659
660 if (it != r_c.end()&& native_it != r_native_c.end())
661 PB_DS_THROW_IF_FAILED(test_traits::cmp(*it, * native_it),
662 static_cast<unsigned long>(rand_ord),
663 m_p_c,
664 &m_native_c);
665}
666
667PB_DS_CLASS_T_DEC
668void
669PB_DS_CLASS_C_DEC::
670prefix_search_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
671{ }
672
673PB_DS_CLASS_T_DEC
674void
675PB_DS_CLASS_C_DEC::
676prefix_search_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
677{
678 PB_DS_SET_DESTRUCT_PRINT
d6816d50 679 m_alloc.set_probability(0);
2661beb5 680 const key_type k = test_traits::generate_key(m_g, m_m);
d6816d50 681 m_alloc.set_probability(1);
2661beb5 682 try
683 {
684 typedef
685 std::pair<typename Cntnr::const_iterator, typename Cntnr::const_iterator>
686 pref_ret_t;
687
688 const pref_ret_t pref_ret = r_c.prefix_range(k);
689
690 typename native_type::const_iterator native_start_it = r_native_c.begin();
691
692 while (native_start_it != r_native_c.end() &&
693 !test_traits::prefix_match(k,
694 test_traits::extract_native_key(*native_start_it)))
695 ++native_start_it;
696
697 typename native_type::const_iterator native_end_it =
698 native_start_it;
699
700 do
701 {
702 if (native_end_it != r_native_c.end())
703 ++native_end_it;
704 }
705 while (native_end_it != r_native_c.end() &&
706 test_traits::prefix_match(k,
707 test_traits::extract_native_key(*native_end_it)));
708
709 it_cmp_imp(pref_ret.first, pref_ret.second, native_start_it, native_end_it);
710 }
711 catch(...)
712 {
713 PB_DS_THROW_IF_FAILED(false, "prefix key " << k, &r_c, &r_native_c);
714 }
715
716 PB_DS_CANCEL_DESTRUCT_PRINT
717}
718
719PB_DS_CLASS_T_DEC
720template<typename Const_It, class Const_Native_It>
721void
722PB_DS_CLASS_C_DEC::
723it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b,
724 Const_Native_It native_e)
725{
726 PB_DS_SET_DESTRUCT_PRINT
727
728 if (std::distance(b, e) != std::distance(native_b, native_e))
729 {
730 const size_t dist = std::distance(b, e);
731 const size_t native_dist = std::distance(native_b, native_e);
732 PB_DS_THROW_IF_FAILED(false,
733 static_cast<unsigned long>(dist) << " "
734 << static_cast<unsigned long>(native_dist),
735 m_p_c, &m_native_c);
736 }
737
738 while (b != e)
739 {
740 PB_DS_THROW_IF_FAILED(native_b != native_e, "", m_p_c, &m_native_c);
741
742 if (!test_traits::cmp(*b, * native_b))
743 PB_DS_THROW_IF_FAILED(false,
744 test_traits::val_to_string(*b) << " " <<
745 test_traits::val_to_string(*native_b),
746 m_p_c, &m_native_c);
747
748 ++b;
749 ++native_b;
750 }
751
752 PB_DS_THROW_IF_FAILED(native_b == native_e, "", m_p_c, &m_native_c);
753 PB_DS_CANCEL_DESTRUCT_PRINT
754}
755
756PB_DS_CLASS_T_DEC
757template<typename Const_It, class Const_Native_It>
758void
759PB_DS_CLASS_C_DEC::
760back_it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b,
761 Const_Native_It native_e)
762{
763 PB_DS_SET_DESTRUCT_PRINT
764 while (b != e)
765 {
766 PB_DS_THROW_IF_FAILED(native_b != native_e,
767 test_traits::val_to_string(*native_e),
768 m_p_c, &m_native_c);
769
770 --e;
771 --native_e;
772
773 PB_DS_THROW_IF_FAILED(test_traits::cmp(*e, * native_e),
774 test_traits::val_to_string(*e) <<
775 test_traits::val_to_string(*native_e),
776 m_p_c, &m_native_c);
777 }
778
779 PB_DS_THROW_IF_FAILED(native_b == native_e,
780 test_traits::val_to_string(*native_e),
781 m_p_c, &m_native_c);
782
783 PB_DS_CANCEL_DESTRUCT_PRINT
784}
785
786PB_DS_CLASS_T_DEC
787void
788PB_DS_CLASS_C_DEC::
789lower_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
790{ }
791
792PB_DS_CLASS_T_DEC
793void
794PB_DS_CLASS_C_DEC::
795lower_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
796{
797 PB_DS_SET_DESTRUCT_PRINT
d6816d50 798 m_alloc.set_probability(0);
2661beb5 799 const key_type k = test_traits::generate_key(m_g, m_m);
d6816d50 800 m_alloc.set_probability(1);
2661beb5 801 typename cntnr::const_iterator it = r_c.lower_bound(k);
802 typename native_type::key_type native_k = test_traits::native_key(k);
803 typename native_type::const_iterator native_it = r_native_c.lower_bound(native_k);
804
805 if (it != r_c.end() && native_it == r_native_c.end())
806 PB_DS_THROW_IF_FAILED("",
807 "it: " + test_traits::val_to_string(*it) + "\n\n",
808 &r_c, &r_native_c);
809
810 if (it == r_c.end() && native_it != r_native_c.end())
811 PB_DS_THROW_IF_FAILED("",
812 "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
813 &r_c, &r_native_c);
814
815 if (it != r_c.end() && !test_traits::cmp(*it, * native_it))
816 PB_DS_THROW_IF_FAILED(false,
817 "key: " + test_traits::key_to_string(k) + "\n\n" +
818 "it: " + test_traits::val_to_string(*it) + "\n\n" +
819 "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
820 &r_c, &r_native_c);
821
822 PB_DS_CANCEL_DESTRUCT_PRINT
823}
824
825PB_DS_CLASS_T_DEC
826void
827PB_DS_CLASS_C_DEC::
828upper_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
829{ }
830
831PB_DS_CLASS_T_DEC
832void
833PB_DS_CLASS_C_DEC::
834upper_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
835{
836 PB_DS_SET_DESTRUCT_PRINT
d6816d50 837 m_alloc.set_probability(0);
2661beb5 838 const key_type k = test_traits::generate_key(m_g, m_m);
d6816d50 839 m_alloc.set_probability(1);
2661beb5 840 typename cntnr::const_iterator it = r_c.upper_bound(k);
841 typename native_type::key_type native_k = test_traits::native_key(k);
842 typename native_type::const_iterator native_it = r_native_c.upper_bound(native_k);
843
844 if (it == r_c.end() && native_it != r_native_c.end())
845 PB_DS_THROW_IF_FAILED(false,
846 "key: " + test_traits::key_to_string(k) + "\n\n" +
847 "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
848 &r_c, &r_native_c);
849
850 if (it != r_c.end() && native_it == r_native_c.end())
851 PB_DS_THROW_IF_FAILED(false,
852 "key: " + test_traits::key_to_string(k) + "\n\n" +
853 "it: " + test_traits::val_to_string(*it) + "\n\n",
854 &r_c, &r_native_c);
855
856 if (it != r_c.end() && !test_traits::cmp(*it, * native_it))
857 PB_DS_THROW_IF_FAILED(false,
858 "key: " + test_traits::key_to_string(k) + "\n\n" +
859 "it: " + test_traits::val_to_string(*it) + "\n\n" +
860 "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
861 &r_c, &r_native_c);
862
863 PB_DS_CANCEL_DESTRUCT_PRINT
864}
865
866// Operators.
867PB_DS_CLASS_T_DEC
868void
869PB_DS_CLASS_C_DEC::
870operator()()
871{
872 typedef xml_result_set_regression_formatter formatter_type;
e4bb1925 873 formatter_type* p_fmt = 0;
2661beb5 874
875 if (m_disp)
876 p_fmt = new formatter_type(string_form<Cntnr>::name(),
877 string_form<Cntnr>::desc());
878
879 m_g.init(m_seed);
880
881 // Track allocation from this point only.
882 const size_t memory_label = 775;
d6816d50 883 m_alloc.seed(m_seed);
2661beb5 884 m_alloc.set_label(memory_label);
885
886 prog_bar pb(m_n, std::cout, m_disp);
887 m_i = 0;
888
889 try
890 {
891 for (m_i = 0; m_i < m_n; ++m_i)
892 {
893 PB_DS_TRACE("Op #" << static_cast<unsigned long>(m_i));
894 allocator_type::set_label(m_i);
895 switch (m_i)
896 {
897 case 0:
898 PB_DS_RUN_MTHD(default_constructor);
899 break;
900 case 1:
901 defs();
902 break;
903 case 2:
904 policy_access();
905 break;
906 case 3:
907 it_copy();
908 break;
909 case 4:
910 it_assign();
911 break;
912 case 5:
913 rev_it_copy();
914 break;
915 case 6:
916 rev_it_assign();
917 break;
918 default:
919 switch(get_next_op())
920 {
921 case insert_op:
922 switch(get_next_sub_op(2))
923 {
924 case 0:
925 PB_DS_RUN_MTHD(insert)
926 break;
927 case 1:
928 PB_DS_RUN_MTHD(subscript)
929 break;
930 default:
931 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
932 }
933 break;
934 case erase_op:
935 switch(get_next_sub_op(4))
936 {
937 case 0:
938 PB_DS_RUN_MTHD(erase)
939 break;
940 case 1:
941 PB_DS_RUN_MTHD(erase_if)
942 break;
943 case 2:
944 PB_DS_RUN_MTHD(erase_it)
945 break;
946 case 3:
947 PB_DS_RUN_MTHD(erase_rev_it)
948 break;
949 default:
950 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
951 }
952 break;
953 case clear_op:
954 PB_DS_RUN_MTHD(clear)
955 break;
956 case other_op:
957 switch(get_next_sub_op(8))
958 {
959 case 0:
960 swap();
961 break;
962 case 1:
963 PB_DS_RUN_MTHD(copy_constructor)
4f4a327e 964 break;
2661beb5 965 case 2:
966 PB_DS_RUN_MTHD(it_constructor)
4f4a327e 967 break;
2661beb5 968 case 3:
969 PB_DS_RUN_MTHD(assignment_operator)
4f4a327e 970 break;
2661beb5 971 case 4:
972 PB_DS_RUN_MTHD(split_join)
4f4a327e 973 break;
2661beb5 974 case 5:
975 resize();
976 break;
977 case 6:
978 get_set_load();
979 break;
980 case 7:
981 get_set_loads();
982 break;
983 default:
984 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
985 }
986 break;
987 default:
988 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
989 };
990 }
991
992 pb.inc();
993 }
994 }
995 catch (...)
996 {
997 std::cerr << "Failed at index " << static_cast<unsigned long>(m_i)
998 << std::endl;
999 delete m_p_c;
1000 throw;
1001 }
1002
1003 // Clean up, then check for allocation by special label, set above.
1004 delete m_p_c;
1005
1006 try
1007 { m_alloc.check_allocated(memory_label); }
1008 catch (...)
1009 {
1010 std::cerr << "detected leaks!" << std::endl;
1011 std::cerr << m_alloc << std::endl;
1012 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
1013 }
1014
1015 // Reset throw probability.
d6816d50 1016 m_alloc.set_probability(0);
2661beb5 1017
1018 if (m_disp)
1019 {
1020 std::cout << std::endl;
1021 delete p_fmt;
1022 }
1023}
1024
1025PB_DS_CLASS_T_DEC
1026typename PB_DS_CLASS_C_DEC::op
1027PB_DS_CLASS_C_DEC::
1028get_next_op()
1029{
1030 const double prob = m_g.get_prob();
1031 if (prob < m_ip)
1032 return insert_op;
1033
1034 if (prob < m_ip + m_ep)
1035 return erase_op;
1036
1037 if (prob < m_ip + m_ep + m_cp)
1038 return clear_op;
1039
1040 PB_DS_THROW_IF_FAILED(prob <= 1, prob, m_p_c, &m_native_c);
1041 return other_op;
1042}
1043
1044PB_DS_CLASS_T_DEC
1045size_t
1046PB_DS_CLASS_C_DEC::
1047get_next_sub_op(size_t max)
1048{
1049 const double p = m_g.get_prob();
1050 const double delta = 1 / static_cast<double>(max);
1051 size_t i = 0;
1052 while (true)
1053 if (p <= (i + 1) * delta)
1054 {
1055 PB_DS_THROW_IF_FAILED(i < max, i << " " << max, m_p_c, &m_native_c);
1056 return i;
1057 }
1058 else
1059 ++i;
1060}
1061
1062// Insert.
1063PB_DS_CLASS_T_DEC
1064bool
1065PB_DS_CLASS_C_DEC::
1066insert()
1067{
1068 PB_DS_TRACE("insert");
1069 bool done = true;
1070 PB_DS_SET_DESTRUCT_PRINT
1071 try
1072 {
d6816d50 1073 m_alloc.set_probability(0);
2661beb5 1074 value_type v = test_traits::generate_value(m_g, m_m);
d6816d50 1075 m_alloc.set_probability(m_tp);
4f4a327e 1076 key_const_reference r_k = test_traits::extract_key(v);
1077 typename cntnr::point_const_iterator found_it = m_p_c->find(r_k);
2661beb5 1078 const bool existed = (found_it != m_p_c->end());
1079 const std::pair<typename cntnr::point_iterator, bool> ins_ret = m_p_c->insert(v);
1080
1081 if (ins_ret.second)
1082 {
1083 PB_DS_THROW_IF_FAILED(!existed, "", m_p_c, &m_native_c);
1084 }
1085 else
1086 {
1087 PB_DS_THROW_IF_FAILED(existed, "", m_p_c, &m_native_c);
1088 PB_DS_THROW_IF_FAILED(found_it == ins_ret.first, "", m_p_c, &m_native_c);
1089 }
1090 m_native_c.insert(test_traits::native_value(v));
1091 }
0bab73e9 1092 catch(__gnu_cxx::forced_error&)
2661beb5 1093 {
1094 done = false;
1095 }
1096 catch(__gnu_pbds::insert_error&)
1097 {
1098 PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
1099 }
1100
1101 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1102 PB_DS_CANCEL_DESTRUCT_PRINT
1103 return done;
1104}
1105
1106// Subscript.
1107PB_DS_CLASS_T_DEC
1108bool
1109PB_DS_CLASS_C_DEC::
1110subscript()
1111{
1112 PB_DS_TRACE("subscript");
1113
1114 enum
1115 {
1116 no_data = __gnu_pbds::detail::is_same<
4f4a327e 1117 typename Cntnr::key_const_reference,
2661beb5 1118 typename Cntnr::const_reference>::value
1119 };
1120
1121 return (subscript_imp(__gnu_pbds::detail::integral_constant<int,no_data>()));
1122}
1123
1124PB_DS_CLASS_T_DEC
1125bool
1126PB_DS_CLASS_C_DEC::
1127subscript_imp(__gnu_pbds::detail::false_type)
1128{
1129 bool done = true;
1130 PB_DS_SET_DESTRUCT_PRINT
1131
1132 try
1133 {
d6816d50 1134 m_alloc.set_probability(0);
2661beb5 1135 value_type v = test_traits::generate_value(m_g, m_m);
1136
d6816d50 1137 m_alloc.set_probability(m_tp);
2661beb5 1138 (*m_p_c)[v.first] = v.second;
1139
1140 m_native_c[test_traits::native_value(v).first] =
1141 test_traits::native_value(v).second;
1142 }
0bab73e9 1143 catch(__gnu_cxx::forced_error&)
2661beb5 1144 {
1145 done = false;
1146 }
1147
1148 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1149 PB_DS_CANCEL_DESTRUCT_PRINT
1150 return done;
1151}
1152
1153PB_DS_CLASS_T_DEC
1154bool
1155PB_DS_CLASS_C_DEC::
1156subscript_imp(__gnu_pbds::detail::true_type)
1157{
1158 bool done = true;
1159 PB_DS_SET_DESTRUCT_PRINT
1160 try
1161 {
d6816d50 1162 m_alloc.set_probability(0);
2661beb5 1163 value_type v = test_traits::generate_value(m_g, m_m);
d6816d50 1164 m_alloc.set_probability(m_tp);
4f4a327e 1165 (*m_p_c)[v] = __gnu_pbds::null_type();
2661beb5 1166 m_native_c.insert(test_traits::native_value(v));
1167 }
0bab73e9 1168 catch(__gnu_cxx::forced_error&)
2661beb5 1169 {
1170 done = false;
1171 }
1172
1173 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1174 PB_DS_CANCEL_DESTRUCT_PRINT
1175 return done;
1176}
1177
1178// Clear.
1179PB_DS_CLASS_T_DEC
1180bool
1181PB_DS_CLASS_C_DEC::
1182clear()
1183{
1184 m_p_c->clear();
1185 m_native_c.clear();
1186 return true;
1187}
1188
1189
1190// Erase.
1191PB_DS_CLASS_T_DEC
1192bool
1193PB_DS_CLASS_C_DEC::
1194erase()
1195{
1196 PB_DS_TRACE("erase");
1197 bool done = true;
1198 PB_DS_SET_DESTRUCT_PRINT
d6816d50 1199 m_alloc.set_probability(0);
2661beb5 1200 const key_type k = test_traits::generate_key(m_g, m_m);
d6816d50 1201 m_alloc.set_probability(m_tp);
2661beb5 1202
1203 try
1204 {
1205 const bool cntnd = m_p_c->find(k) != m_p_c->end();
1206 PB_DS_THROW_IF_FAILED(cntnd ==(m_native_c.find(test_traits::native_key(k)) != m_native_c.end()), test_traits::key_to_string(k), m_p_c, &m_native_c);
1207
1208 const bool ersd = m_p_c->erase(k);
1209 const bool native_ersd = m_native_c.erase(test_traits::native_key(k)) != 0;
1210
1211 PB_DS_THROW_IF_FAILED(ersd == native_ersd, ersd << " " << native_ersd,
1212 m_p_c, &m_native_c);
1213
1214 PB_DS_THROW_IF_FAILED(m_p_c->find(k) == m_p_c->end(), "",
1215 m_p_c, &m_native_c);
1216 }
0bab73e9 1217 catch(__gnu_cxx::forced_error&)
2661beb5 1218 {
1219 done = false;
1220
1221 PB_DS_THROW_IF_FAILED( container_traits::erase_can_throw, container_traits::erase_can_throw, m_p_c, &m_native_c);
1222 }
1223
1224 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1225 PB_DS_CANCEL_DESTRUCT_PRINT
1226 return done;
1227}
1228
1229PB_DS_CLASS_T_DEC
1230bool
1231PB_DS_CLASS_C_DEC::
1232erase_if()
1233{
1234 PB_DS_TRACE("erase_if");
1235 bool done = true;
1236 PB_DS_SET_DESTRUCT_PRINT
1237
1238 try
1239 {
1240 typedef
1241 typename std::iterator_traits<typename cntnr::iterator>::reference
1242 it_const_reference;
1243
1244 typedef
1245 typename test_traits::template erase_if_fn<value_type>
1246 erase_if_fn_t;
1247
d6816d50 1248 m_alloc.set_probability(m_tp);
2661beb5 1249
1250 const size_t ersd = m_p_c->erase_if(erase_if_fn_t());
1251 const size_t native_ersd = test_traits::erase_if(m_native_c);
1252 PB_DS_THROW_IF_FAILED(ersd == native_ersd,
1253 ersd << " " << native_ersd, m_p_c, &m_native_c);
1254 }
0bab73e9 1255 catch(__gnu_cxx::forced_error&)
2661beb5 1256 {
1257 done = false;
1258 PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw,
1259 container_traits::erase_can_throw,
1260 m_p_c, &m_native_c);
1261 }
1262
1263 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1264 PB_DS_CANCEL_DESTRUCT_PRINT
1265 return done;
1266}
1267
1268PB_DS_CLASS_T_DEC
1269bool
1270PB_DS_CLASS_C_DEC::
1271erase_it()
1272{
1273 enum
1274 {
1275 erase_iterators = container_traits::order_preserving
1276 };
1277
1278 return (erase_it_imp(__gnu_pbds::detail::integral_constant<int,erase_iterators>()));
1279}
1280
1281PB_DS_CLASS_T_DEC
1282bool
1283PB_DS_CLASS_C_DEC::
1284erase_it_imp(__gnu_pbds::detail::false_type)
1285{
1286 return true;
1287}
1288
1289PB_DS_CLASS_T_DEC
1290bool
1291PB_DS_CLASS_C_DEC::
1292erase_it_imp(__gnu_pbds::detail::true_type)
1293{
1294 PB_DS_TRACE("erase_it");
1295 bool done = true;
1296 PB_DS_SET_DESTRUCT_PRINT
1297
1298 try
1299 {
d6816d50 1300 m_alloc.set_probability(0);
2661beb5 1301 const key_type k = test_traits::generate_key(m_g, m_m);
d6816d50 1302 m_alloc.set_probability(m_tp);
2661beb5 1303
1304 typename cntnr::iterator found_it = m_p_c->find(k);
1305
1306 typename native_type::iterator native_it = m_native_c.find(test_traits::native_key(k));
1307
1308 const bool found = found_it != m_p_c->end();
1309 const bool native_found = native_it != m_native_c.end();
1310
1311 PB_DS_THROW_IF_FAILED(
1312 found == native_found,
1313 found << " " << native_found,
1314 m_p_c,
1315 &m_native_c);
1316
1317 typename cntnr::const_iterator next_it = found_it;
1318 if (next_it != m_p_c->end())
1319 ++next_it;
1320
1321 typename cntnr::iterator next_ers_it = m_p_c->erase(found_it);
1322
1323 if (native_it != m_native_c.end())
1324 m_native_c.erase(native_it);
1325
1326 bool range_guarantee = __gnu_pbds::detail::is_same<
1327 typename container_traits::invalidation_guarantee,
1328 __gnu_pbds::range_invalidation_guarantee>::value ;
1329
1330 if (range_guarantee)
1331 PB_DS_THROW_IF_FAILED(next_ers_it == next_it, "", m_p_c, &m_native_c);
1332 }
0bab73e9 1333 catch(__gnu_cxx::forced_error&)
2661beb5 1334 {
1335 done = false;
1336 PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw, container_traits::erase_can_throw, m_p_c, &m_native_c);
1337 }
1338
1339 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1340 PB_DS_CANCEL_DESTRUCT_PRINT
1341 return done;
1342}
1343
1344PB_DS_CLASS_T_DEC
1345bool
1346PB_DS_CLASS_C_DEC::
1347erase_rev_it()
1348{
1349 enum
1350 {
1351 erase_iterators = container_traits::order_preserving
1352 && container_traits::reverse_iteration
1353 };
1354
1355 return (erase_rev_it_imp(__gnu_pbds::detail::integral_constant<int,erase_iterators>()));
1356}
1357
1358PB_DS_CLASS_T_DEC
1359bool
1360PB_DS_CLASS_C_DEC::
1361erase_rev_it_imp(__gnu_pbds::detail::false_type)
1362{
1363 return true;
1364}
1365
1366PB_DS_CLASS_T_DEC
1367bool
1368PB_DS_CLASS_C_DEC::
1369erase_rev_it_imp(__gnu_pbds::detail::true_type)
1370{
1371 PB_DS_TRACE("erase_rev_it");
1372 bool done = true;
1373 PB_DS_SET_DESTRUCT_PRINT
1374
1375 try
1376 {
d6816d50 1377 m_alloc.set_probability(0);
2661beb5 1378 const key_type k = test_traits::generate_key(m_g, m_m);
d6816d50 1379 m_alloc.set_probability(m_tp);
2661beb5 1380
1381 typename cntnr::iterator found_it = m_p_c->find(k);
1382 typename native_type::iterator native_it = m_native_c.find(test_traits::native_key(k));
1383
1384 typename cntnr::const_reverse_iterator next_it = found_it;
1385 if (next_it != m_p_c->end())
1386 ++next_it;
1387
1388 typename cntnr::reverse_iterator next_ers_it =
1389 m_p_c->erase((typename cntnr::reverse_iterator)found_it);
1390
1391 PB_DS_THROW_IF_FAILED(next_ers_it == next_it, "", m_p_c, &m_native_c);
1392
1393 if (native_it != m_native_c.end())
1394 m_native_c.erase(native_it);
1395 }
0bab73e9 1396 catch(__gnu_cxx::forced_error&)
2661beb5 1397 {
1398 done = false;
1399 PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw,
1400 container_traits::erase_can_throw,
1401 m_p_c, &m_native_c);
1402 }
1403
1404 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1405 PB_DS_CANCEL_DESTRUCT_PRINT
1406 return done;
1407}
1408
1409// Defs.
1410PB_DS_CLASS_T_DEC
1411void
1412PB_DS_CLASS_C_DEC::
1413defs()
1414{
1415 // General container types.
1416 typedef typename Cntnr::size_type test_size_type;
1417 typedef typename Cntnr::difference_type difference_type;
1418
1419 key_defs();
1420 mapped_defs();
1421 value_defs();
1422 iterator_defs();
1423 node_iterator_defs(__gnu_pbds::detail::integral_constant<int,
1424 container_traits::order_preserving>());
1425 policy_defs();
1426}
1427
1428PB_DS_CLASS_T_DEC
1429void
1430PB_DS_CLASS_C_DEC::
1431key_defs()
1432{
1433 typedef typename Cntnr::key_type test_key_type;
1434 typedef typename Cntnr::key_reference test_key_reference;
4f4a327e 1435 typedef typename Cntnr::key_const_reference test_key_const_reference;
2661beb5 1436 typedef typename Cntnr::key_pointer test_key_pointer;
4f4a327e 1437 typedef typename Cntnr::key_const_pointer test_key_const_pointer;
2661beb5 1438}
1439
1440PB_DS_CLASS_T_DEC
1441void
1442PB_DS_CLASS_C_DEC::
1443mapped_defs()
1444{
1445 typedef typename Cntnr::mapped_type test_mapped_type;
1446 typedef typename Cntnr::mapped_reference test_mapped_reference;
4f4a327e 1447 typedef typename Cntnr::mapped_const_reference test_mapped_const_reference;
2661beb5 1448 typedef typename Cntnr::mapped_pointer test_mapped_pointer;
4f4a327e 1449 typedef typename Cntnr::mapped_const_pointer test_mapped_const_pointer;
2661beb5 1450}
1451
1452PB_DS_CLASS_T_DEC
1453void
1454PB_DS_CLASS_C_DEC::
1455value_defs()
1456{
1457 typedef typename Cntnr::value_type test_value_type;
1458 typedef typename Cntnr::reference test_reference;
1459 typedef typename Cntnr::const_reference test_const_reference;
1460 typedef typename Cntnr::pointer test_pointer;
1461 typedef typename Cntnr::const_pointer test_const_pointer;
1462}
1463
1464PB_DS_CLASS_T_DEC
1465void
1466PB_DS_CLASS_C_DEC::
1467ds_defs()
1468{
1469 typedef __gnu_pbds::container_traits< Cntnr> test_container_traits;
1470
1471 typedef typename test_container_traits::container_category test_container_category;
1472
1473 typedef
1474 typename test_container_traits::invalidation_guarantee
1475 test_invalidation_guarantee;
1476
1477 enum
1478 {
1479 test_order_preserving = test_container_traits::order_preserving
1480 };
1481
1482 enum
1483 {
1484 test_erase_can_throw = test_container_traits::erase_can_throw
1485 };
1486}
1487
1488PB_DS_CLASS_T_DEC
1489void
1490PB_DS_CLASS_C_DEC::
1491iterator_defs()
1492{
1493 typedef typename Cntnr::point_iterator test_point_iterator;
4f4a327e 1494 typedef typename Cntnr::point_const_iterator const_test_point_iterator;
2661beb5 1495 typedef typename Cntnr::iterator test_iterator;
1496 typedef typename Cntnr::const_iterator const_test_iterator;
1497}
1498
1499PB_DS_CLASS_T_DEC
1500void
1501PB_DS_CLASS_C_DEC::
1502node_iterator_defs(__gnu_pbds::detail::false_type)
1503{ }
1504
1505PB_DS_CLASS_T_DEC
1506void
1507PB_DS_CLASS_C_DEC::
1508node_iterator_defs(__gnu_pbds::detail::true_type)
1509{
1510 typedef typename Cntnr::node_iterator test_node_iterator;
4f4a327e 1511 typedef typename Cntnr::node_const_iterator test_node_const_iterator;
2661beb5 1512}
1513
1514PB_DS_CLASS_T_DEC
1515void
1516PB_DS_CLASS_C_DEC::
1517policy_defs()
1518{
1519 typedef typename Cntnr::allocator_type test_allocator;
1520 policy_defs(typename Cntnr::container_category());
1521}
1522
1523PB_DS_CLASS_T_DEC
1524void
1525PB_DS_CLASS_C_DEC::
1526policy_defs(__gnu_pbds::basic_hash_tag)
1527{
1528 typedef typename Cntnr::hash_fn test_hash_fn;
1529 typedef typename Cntnr::eq_fn test_eq_fn;
1530 typedef typename Cntnr::resize_policy test_resize_policy;
1531}
1532
1533PB_DS_CLASS_T_DEC
1534void
1535PB_DS_CLASS_C_DEC::
1536policy_defs(__gnu_pbds::cc_hash_tag)
1537{
1538 policy_defs(__gnu_pbds::basic_hash_tag());
1539 typedef typename Cntnr::comb_hash_fn test_comb_hash_fn;
1540}
1541
1542PB_DS_CLASS_T_DEC
1543void
1544PB_DS_CLASS_C_DEC::
1545policy_defs(__gnu_pbds::gp_hash_tag)
1546{
1547 policy_defs(__gnu_pbds::basic_hash_tag());
1548 typedef typename Cntnr::comb_probe_fn test_comb_probe_fn;
1549 typedef typename Cntnr::probe_fn test_probe_fn;
1550}
1551
1552PB_DS_CLASS_T_DEC
1553void
1554PB_DS_CLASS_C_DEC::
1555policy_defs(__gnu_pbds::tree_tag)
1556{
1557 typedef typename Cntnr::cmp_fn test_cmp_fn;
1558 typedef typename Cntnr::node_update test_node_update;
1559}
1560
1561PB_DS_CLASS_T_DEC
1562void
1563PB_DS_CLASS_C_DEC::
1564policy_defs(__gnu_pbds::list_update_tag)
1565{
1566 typedef typename Cntnr::eq_fn test_eq_fn;
1567 typedef typename Cntnr::update_policy test_update_policy;
1568}
1569
1570PB_DS_CLASS_T_DEC
1571void
1572PB_DS_CLASS_C_DEC::
1573policy_defs(__gnu_pbds::pat_trie_tag)
1574{
4f4a327e 1575 typedef typename Cntnr::access_traits access_traits;
2661beb5 1576}
1577
1578
1579// Policy Access.
1580PB_DS_CLASS_T_DEC
1581void
1582PB_DS_CLASS_C_DEC::
1583policy_access()
1584{
1585 policy_access(typename Cntnr::container_category());
1586}
1587
1588PB_DS_CLASS_T_DEC
1589void
1590PB_DS_CLASS_C_DEC::
1591policy_access(__gnu_pbds::basic_hash_tag)
1592{
1593 {
1594 typename Cntnr::hash_fn& r_t = m_p_c->get_hash_fn();
e4bb1925 1595 assert(&r_t);
2661beb5 1596 }
1597 {
1598 const typename Cntnr::hash_fn& r_t =((const Cntnr& )*m_p_c).get_hash_fn();
e4bb1925 1599 assert(&r_t);
2661beb5 1600 }
1601
1602 {
1603 typename Cntnr::eq_fn& r_t = m_p_c->get_eq_fn();
e4bb1925 1604 assert(&r_t);
2661beb5 1605 }
1606 {
1607 const typename Cntnr::eq_fn& r_t =((const Cntnr& )*m_p_c).get_eq_fn();
e4bb1925 1608 assert(&r_t);
2661beb5 1609 }
1610
1611 {
1612 typename Cntnr::resize_policy& r_t = m_p_c->get_resize_policy();
e4bb1925 1613 assert(&r_t);
2661beb5 1614 }
1615 {
1616 const typename Cntnr::resize_policy& r_t =((const Cntnr& )*m_p_c).get_resize_policy();
1617
e4bb1925 1618 assert(&r_t);
2661beb5 1619 }
1620}
1621
1622PB_DS_CLASS_T_DEC
1623void
1624PB_DS_CLASS_C_DEC::
1625policy_access(__gnu_pbds::cc_hash_tag)
1626{
1627 policy_access(__gnu_pbds::basic_hash_tag());
1628
1629 {
1630 typename Cntnr::comb_hash_fn& r_t = m_p_c->get_comb_hash_fn();
e4bb1925 1631 assert(&r_t);
2661beb5 1632 }
1633 {
1634 const typename Cntnr::comb_hash_fn& r_t =((const Cntnr& )*m_p_c).get_comb_hash_fn();
1635
e4bb1925 1636 assert(&r_t);
2661beb5 1637 }
1638}
1639
1640PB_DS_CLASS_T_DEC
1641void
1642PB_DS_CLASS_C_DEC::
1643policy_access(__gnu_pbds::gp_hash_tag)
1644{
1645 policy_access(__gnu_pbds::basic_hash_tag());
1646
1647 {
1648 typename Cntnr::comb_probe_fn& r_t = m_p_c->get_comb_probe_fn();
e4bb1925 1649 assert(&r_t);
2661beb5 1650 }
1651 {
1652 const typename Cntnr::comb_probe_fn& r_t =((const Cntnr& )*m_p_c).get_comb_probe_fn();
1653
e4bb1925 1654 assert(&r_t);
2661beb5 1655 }
1656
1657 {
1658 typename Cntnr::probe_fn& r_t = m_p_c->get_probe_fn();
e4bb1925 1659 assert(&r_t);
2661beb5 1660 }
1661 {
1662 const typename Cntnr::probe_fn& r_t =((const Cntnr& )*m_p_c).get_probe_fn();
e4bb1925 1663 assert(&r_t);
2661beb5 1664 }
1665}
1666
1667PB_DS_CLASS_T_DEC
1668void
1669PB_DS_CLASS_C_DEC::
1670policy_access(__gnu_pbds::tree_tag)
1671{
1672 {
1673 typename Cntnr::cmp_fn& r_t = m_p_c->get_cmp_fn();
e4bb1925 1674 assert(&r_t);
2661beb5 1675 }
1676
1677 {
1678 const typename Cntnr::cmp_fn& r_t =((const Cntnr& )*m_p_c).get_cmp_fn();
e4bb1925 1679 assert(&r_t);
2661beb5 1680 }
1681}
1682
1683PB_DS_CLASS_T_DEC
1684void
1685PB_DS_CLASS_C_DEC::
1686policy_access(__gnu_pbds::list_update_tag)
1687{ }
1688
1689PB_DS_CLASS_T_DEC
1690void
1691PB_DS_CLASS_C_DEC::
1692policy_access(__gnu_pbds::pat_trie_tag)
1693{
4f4a327e 1694 typename Cntnr::access_traits& r_t = m_p_c->get_access_traits();
e4bb1925 1695 assert(&r_t);
2661beb5 1696}
1697
1698
1699// Split/Join.
1700PB_DS_CLASS_T_DEC
1701bool
1702PB_DS_CLASS_C_DEC::
1703split_join()
1704{
1705 enum
1706 {
1707 split_join = container_traits::order_preserving
1708 };
1709
4f4a327e 1710 typedef __gnu_pbds::detail::integral_constant<int, split_join> __true_type;
1711 return split_join_imp(__true_type());
2661beb5 1712}
1713
1714PB_DS_CLASS_T_DEC
1715bool
1716PB_DS_CLASS_C_DEC::
1717split_join_imp(__gnu_pbds::detail::false_type)
1718{
1719 return true;
1720}
1721
1722PB_DS_CLASS_T_DEC
1723bool
1724PB_DS_CLASS_C_DEC::
1725split_join_imp(__gnu_pbds::detail::true_type)
1726{
1727 PB_DS_TRACE("split_join");
1728 bool done = true;
1729 PB_DS_SET_DESTRUCT_PRINT
1730
1731 try
1732 {
d6816d50 1733 m_alloc.set_probability(0);
2661beb5 1734 Cntnr lhs(*m_p_c);
1735 Cntnr rhs;
1736 native_type native_lhs(m_native_c);
1737 native_type native_rhs;
1738 const key_type k = test_traits::generate_key(m_g, m_m);
1739
d6816d50 1740 m_alloc.set_probability(m_tp);
2661beb5 1741 lhs.split(k, rhs);
1742
1743 typename native_type::const_iterator it =
1744 native_lhs.upper_bound(test_traits::native_key(k));
1745
1746 while (!native_lhs.empty()&& it != native_lhs.end())
1747 {
1748 native_rhs.insert(*it);
1749 typename native_type::const_iterator next_it = it;
1750 ++next_it;
1751 native_lhs.erase(test_traits::extract_native_key(*it));
1752 it = next_it;
1753 }
1754
1755 PB_DS_COND_COMPARE(lhs, native_lhs);
1756 PB_DS_COND_COMPARE(rhs, native_rhs);
1757
d6816d50 1758 m_alloc.set_probability(m_tp);
2661beb5 1759
1760 if (m_g.get_prob() < 0.5)
1761 lhs.swap(rhs);
1762
1763 lhs.join(rhs);
1764 PB_DS_THROW_IF_FAILED(rhs.size() == 0, rhs.size(), m_p_c, &m_native_c);
1765 PB_DS_THROW_IF_FAILED(rhs.empty(), rhs.size(), m_p_c, &m_native_c);
1766 m_p_c->swap(lhs);
1767 }
0bab73e9 1768 catch(__gnu_cxx::forced_error&)
2661beb5 1769 {
1770 done = false;
1771 PB_DS_THROW_IF_FAILED(container_traits::split_join_can_throw,
1772 container_traits::split_join_can_throw,
1773 m_p_c, &m_native_c);
1774 }
1775
1776 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1777 PB_DS_CANCEL_DESTRUCT_PRINT
1778 return done;
1779}
1780
1781// Iterator conversions.
1782PB_DS_CLASS_T_DEC
1783void
1784PB_DS_CLASS_C_DEC::
1785it_copy()
1786{
1787 {
1788 typename cntnr::iterator it = m_p_c->end();
1789 typename cntnr::const_iterator const_it(it);
1790 PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1791 PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1792
4f4a327e 1793 typename cntnr::point_const_iterator const_find_it(it);
2661beb5 1794 PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1795 PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1796
1797 typename cntnr::point_iterator find_it(it);
1798 PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1799 PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1800 }
1801
1802 {
1803 typename cntnr::const_iterator const_it = m_p_c->end();
4f4a327e 1804 typename cntnr::point_const_iterator const_find_it(const_it);
2661beb5 1805 PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c);
1806 PB_DS_THROW_IF_FAILED(!(const_find_it != const_it), "", m_p_c, &m_native_c);
1807 }
1808
1809 {
1810 typename cntnr::point_iterator find_it = m_p_c->end();
4f4a327e 1811 typename cntnr::point_const_iterator const_find_it(find_it);
2661beb5 1812 PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c);
1813 PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c);
1814 }
1815}
1816
1817PB_DS_CLASS_T_DEC
1818void
1819PB_DS_CLASS_C_DEC::
1820it_assign()
1821{
1822 {
1823 typename cntnr::iterator it = m_p_c->end();
1824 typename cntnr::const_iterator const_it;
1825 const_it = it;
1826 PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1827 PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1828
4f4a327e 1829 typename cntnr::point_const_iterator const_find_it;
2661beb5 1830 const_find_it = it;
1831 PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1832 PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1833
1834 typename cntnr::point_iterator find_it;
1835 find_it = it;
1836 PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1837 PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1838 }
1839
1840 {
1841 typename cntnr::const_iterator const_it = m_p_c->end();
4f4a327e 1842 typename cntnr::point_const_iterator const_find_it;
2661beb5 1843 const_find_it = const_it;
1844 PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c);
1845 PB_DS_THROW_IF_FAILED(!(const_find_it != const_it), "", m_p_c, &m_native_c);
1846 }
1847
1848 {
1849 typename cntnr::point_iterator find_it = m_p_c->end();
4f4a327e 1850 typename cntnr::point_const_iterator const_find_it;
2661beb5 1851 const_find_it = find_it;
1852 PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c);
1853 PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c);
1854 }
1855}
1856
1857PB_DS_CLASS_T_DEC
1858void
1859PB_DS_CLASS_C_DEC::
1860rev_it_copy()
1861{
1862 enum
1863 {
1864 reverse_iteration = container_traits::reverse_iteration
1865 };
1866
1867 rev_it_copy_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>());
1868}
1869
1870PB_DS_CLASS_T_DEC
1871void
1872PB_DS_CLASS_C_DEC::
1873rev_it_assign()
1874{
1875 enum
1876 {
1877 reverse_iteration = container_traits::reverse_iteration
1878 };
1879
1880 rev_it_assign_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>());
1881}
1882
1883PB_DS_CLASS_T_DEC
1884void
1885PB_DS_CLASS_C_DEC::
1886rev_it_copy_imp(__gnu_pbds::detail::false_type)
1887{ }
1888
1889PB_DS_CLASS_T_DEC
1890void
1891PB_DS_CLASS_C_DEC::
1892rev_it_copy_imp(__gnu_pbds::detail::true_type)
1893{
1894 {
1895 typename cntnr::iterator it = m_p_c->end();
1896 typename cntnr::const_reverse_iterator const_it(it);
1897 PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1898 PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1899
4f4a327e 1900 typename cntnr::point_const_iterator const_find_it(it);
2661beb5 1901 PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1902 PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1903
1904 typename cntnr::point_iterator find_it(it);
1905 PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1906 PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1907 }
1908}
1909
1910PB_DS_CLASS_T_DEC
1911void
1912PB_DS_CLASS_C_DEC::
1913rev_it_assign_imp(__gnu_pbds::detail::false_type)
1914{ }
1915
1916PB_DS_CLASS_T_DEC
1917void
1918PB_DS_CLASS_C_DEC::
1919rev_it_assign_imp(__gnu_pbds::detail::true_type)
1920{
1921 {
1922 typename cntnr::iterator it = m_p_c->end();
1923 typename cntnr::const_reverse_iterator const_it;
1924 const_it = it;
1925 PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1926 PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1927
4f4a327e 1928 typename cntnr::point_const_iterator const_find_it;
2661beb5 1929 const_find_it = it;
1930 PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1931 PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1932
1933 typename cntnr::point_iterator find_it;
1934 find_it = it;
1935 PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1936 PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1937 }
1938}
1939
1940// Resize.
1941PB_DS_CLASS_T_DEC
1942bool
1943PB_DS_CLASS_C_DEC::
1944resize()
1945{
1946 typedef __gnu_pbds::detail::integral_constant<int, test_traits::resize> resize_ind;
1947
1948 return resize_imp(resize_ind());
1949}
1950
1951PB_DS_CLASS_T_DEC
1952bool
1953PB_DS_CLASS_C_DEC::
1954resize_imp(__gnu_pbds::detail::false_type)
1955{
1956 return true;
1957}
1958
1959PB_DS_CLASS_T_DEC
1960bool
1961PB_DS_CLASS_C_DEC::
1962resize_imp(__gnu_pbds::detail::true_type)
1963{
1964 PB_DS_TRACE("resize");
1965 bool done = true;
1966 PB_DS_SET_DESTRUCT_PRINT
1967 const size_t old_size = m_p_c->get_actual_size();
1968
1969 try
1970 {
1971 enum
1972 {
1973 min_new_size = 200,
1974 max_new_size = 2000
1975 };
1976
d6816d50 1977 m_alloc.set_probability(m_tp);
1978 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 1979 const size_t new_size = m_g.get_unsigned_long(min_new_size, max_new_size);
1980 m_p_c->resize(new_size);
1981 const size_t actual_new_size = m_p_c->get_actual_size();
1982 PB_DS_THROW_IF_FAILED(actual_new_size >= new_size,
1983 actual_new_size << " " << new_size,
1984 m_p_c, &m_native_c);
1985 }
1986 catch(...)
1987 {
1988 PB_DS_THROW_IF_FAILED(m_p_c->get_actual_size() == old_size,
1989 m_p_c->get_actual_size() << " " << old_size,
1990 m_p_c, &m_native_c);
1991
1992 done = false;
1993 }
1994
1995 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1996 PB_DS_CANCEL_DESTRUCT_PRINT
1997 return done;
1998}
1999
2000
2001// Get/Set load.
2002PB_DS_CLASS_T_DEC
2003void
2004PB_DS_CLASS_C_DEC::
2005get_set_load()
2006{
2007 typedef
2008 __gnu_pbds::detail::integral_constant<int, test_traits::get_set_load>
2009 get_set_load_ind;
2010
2011 get_set_load_imp(get_set_load_ind());
2012}
2013
2014PB_DS_CLASS_T_DEC
2015void
2016PB_DS_CLASS_C_DEC::
2017get_set_load_imp(__gnu_pbds::detail::false_type)
2018{ }
2019
2020PB_DS_CLASS_T_DEC
2021void
2022PB_DS_CLASS_C_DEC::
2023get_set_load_imp(__gnu_pbds::detail::true_type)
2024{
2025 PB_DS_TRACE("get_set_load");
2026 PB_DS_SET_DESTRUCT_PRINT
2027 m_p_c->get_load();
d6816d50 2028 m_alloc.set_probability(1);
2029 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 2030 const float min_load = static_cast<float>(0.05);
2031 const float max_load = static_cast<float>(0.9);
2032
2033 const float new_load = static_cast<float>(m_g.get_prob() * (max_load - min_load) + min_load);
2034
2035 m_p_c->set_load(new_load);
2036 PB_DS_THROW_IF_FAILED(m_p_c->get_load() == new_load, "", m_p_c, &m_native_c);
2037 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
2038 PB_DS_CANCEL_DESTRUCT_PRINT
2039}
2040
2041
2042// Get/Set loads.
2043PB_DS_CLASS_T_DEC
2044bool
2045PB_DS_CLASS_C_DEC::
2046get_set_loads()
2047{
2048 typedef
2049 __gnu_pbds::detail::integral_constant<int, test_traits::get_set_loads>
2050 get_set_loads_ind;
2051
2052 return get_set_loads_imp(get_set_loads_ind());
2053}
2054
2055PB_DS_CLASS_T_DEC
2056bool
2057PB_DS_CLASS_C_DEC::
2058get_set_loads_imp(__gnu_pbds::detail::false_type)
2059{
2060 return true;
2061}
2062
2063PB_DS_CLASS_T_DEC
2064bool
2065PB_DS_CLASS_C_DEC::
2066get_set_loads_imp(__gnu_pbds::detail::true_type)
2067{
2068 PB_DS_TRACE("get_set_loads");
2069 bool done = true;
2070 PB_DS_SET_DESTRUCT_PRINT
2071 const std::pair<float, float> old_loads = m_p_c->get_loads();
2072
2073 try
2074 {
d6816d50 2075 m_alloc.set_probability(m_tp);
2661beb5 2076
d6816d50 2077 typename alloc_t::group_adjustor adjust(m_p_c->size());
2661beb5 2078
2079 const float min_min_load = static_cast<float>(0.05);
2080 const float max_min_load = static_cast<float>(0.2);
2081
2082 const float new_min_load =
2083 static_cast<float>(m_g.get_prob()* (max_min_load - min_min_load) +
2084 min_min_load);
2085
2086 const float new_max_load = static_cast<float>(new_min_load* 2.5);
2087 PB_DS_THROW_IF_FAILED(new_max_load < 1, new_max_load, m_p_c, &m_native_c);
2088 m_p_c->set_loads(std::make_pair(new_min_load, new_max_load));
2089 }
2090 catch(...)
2091 {
2092 PB_DS_THROW_IF_FAILED(old_loads == m_p_c->get_loads(),
2093 old_loads.first << " " << old_loads.second << " " <<
2094 m_p_c->get_loads().first << " " <<
2095 m_p_c->get_loads().second,
2096 m_p_c, &m_native_c);
2097
2098 done = false;
2099 }
2100
2101 PB_DS_COND_COMPARE(*m_p_c, m_native_c);
2102 PB_DS_CANCEL_DESTRUCT_PRINT
2103 return done;
2104}
2105
2106// Diagnostics.
2107PB_DS_CLASS_T_DEC
2108void
2109PB_DS_CLASS_C_DEC::
2110print_container(const native_type& r_cnt, std::ostream& r_os) const
2111{
d6816d50 2112 m_alloc.set_probability(0);
2661beb5 2113 typename native_type::const_iterator it = r_cnt.begin();
2114 while (it != r_cnt.end())
2115 {
2116 r_os << test_traits::val_to_string(*it) + "\n";
2117 ++it;
2118 }
2119}
2120
2121PB_DS_CLASS_T_DEC
2122void
2123PB_DS_CLASS_C_DEC::
2124print_container(const cntnr& r_cnt, std::ostream& r_os) const
2125{
d6816d50 2126 m_alloc.set_probability(0);
2661beb5 2127 typename cntnr::const_iterator it = r_cnt.begin();
2128 while (it != r_cnt.end())
2129 {
2130 r_os << test_traits::val_to_string(*it) + "\n";
2131 ++it;
2132 }
2133}
2134
2135#endif
Mirror of https://gcc.gnu.org/git/gcc.git