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