libcxx/test/std/containers/sequences/deque/deque.modifiers/insert_iter_iter.pass.cpp

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 // REQUIRES: long_tests
  10 // UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME
  11
  12 // This test is super slow, in particular with msan or tsan. In order to avoid timeouts and to
  13 // spend less time waiting for this particular test to complete we compile with optimizations.
  14 // ADDITIONAL_COMPILE_FLAGS(msan): -O1
  15 // ADDITIONAL_COMPILE_FLAGS(tsan): -O1
  16
  17 // <deque>
  18
  19 // template <class InputIterator>
  20 //   iterator insert (const_iterator p, InputIterator f, InputIterator l);
  21
  22 #include "asan_testing.h"
  23 #include <deque>
  24 #include <cassert>
  25 #include <cstddef>
  26
  27 #include "test_macros.h"
  28 #include "test_iterators.h"
  29 #include "MoveOnly.h"
  30 #include "test_allocator.h"
  31 #include "min_allocator.h"
  32
  33 template <class C>
  34 C
  35 make(int size, int start = 0 )
  36 {
  37     const int b = 4096 / sizeof(int);
  38     int init = 0;
  39     if (start > 0)
  40     {
  41         init = (start+1) / b + ((start+1) % b != 0);
  42         init *= b;
  43         --init;
  44     }
  45     C c(init, 0);
  46     for (int i = 0; i < init-start; ++i)
  47         c.pop_back();
  48     for (int i = 0; i < size; ++i)
  49         c.push_back(i);
  50     for (int i = 0; i < start; ++i)
  51         c.pop_front();
  52     return c;
  53 }
  54
  55 template <class C>
  56 void
  57 test(int P, const C& c0, const C& c2)
  58 {
  59     {
  60     typedef typename C::const_iterator CI;
  61     typedef cpp17_input_iterator<CI> BCI;
  62     C c1 = c0;
  63     std::size_t c1_osize = c1.size();
  64     CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
  65     assert(i == c1.begin() + P);
  66     assert(c1.size() == c1_osize + c2.size());
  67     assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
  68     LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c1));
  69     LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c2));
  70     i = c1.begin();
  71     for (int j = 0; j < P; ++j, ++i)
  72         assert(*i == j);
  73     for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
  74         assert(*i == j);
  75     for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
  76         assert(*i == j);
  77     }
  78     {
  79     typedef typename C::const_iterator CI;
  80     typedef forward_iterator<CI> BCI;
  81     C c1 = c0;
  82     std::size_t c1_osize = c1.size();
  83     CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
  84     assert(i == c1.begin() + P);
  85     assert(c1.size() == c1_osize + c2.size());
  86     assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
  87     i = c1.begin();
  88     for (int j = 0; j < P; ++j, ++i)
  89         assert(*i == j);
  90     for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
  91         assert(*i == j);
  92     for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
  93         assert(*i == j);
  94     }
  95     {
  96     typedef typename C::const_iterator CI;
  97     typedef bidirectional_iterator<CI> BCI;
  98     C c1 = c0;
  99     std::size_t c1_osize = c1.size();
 100     CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
 101     assert(i == c1.begin() + P);
 102     assert(c1.size() == c1_osize + c2.size());
 103     assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
 104     i = c1.begin();
 105     for (int j = 0; j < P; ++j, ++i)
 106         assert(*i == j);
 107     for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
 108         assert(*i == j);
 109     for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
 110         assert(*i == j);
 111     }
 112 }
 113
 114 template <class C>
 115 void
 116 testN(int start, int N, int M)
 117 {
 118     for (int i = 0; i <= 3; ++i)
 119     {
 120         if (0 <= i && i <= N)
 121         {
 122             C c1 = make<C>(N, start);
 123             C c2 = make<C>(M);
 124             test(i, c1, c2);
 125         }
 126     }
 127     for (int i = M-1; i <= M+1; ++i)
 128     {
 129         if (0 <= i && i <= N)
 130         {
 131             C c1 = make<C>(N, start);
 132             C c2 = make<C>(M);
 133             test(i, c1, c2);
 134         }
 135     }
 136     for (int i = N/2-1; i <= N/2+1; ++i)
 137     {
 138         if (0 <= i && i <= N)
 139         {
 140             C c1 = make<C>(N, start);
 141             C c2 = make<C>(M);
 142             test(i, c1, c2);
 143         }
 144     }
 145     for (int i = N - M - 1; i <= N - M + 1; ++i)
 146     {
 147         if (0 <= i && i <= N)
 148         {
 149             C c1 = make<C>(N, start);
 150             C c2 = make<C>(M);
 151             test(i, c1, c2);
 152         }
 153     }
 154     for (int i = N - M - 1; i <= N - M + 1; ++i)
 155     {
 156         if (0 <= i && i <= N)
 157         {
 158             C c1 = make<C>(N, start);
 159             C c2 = make<C>(M);
 160             test(i, c1, c2);
 161         }
 162     }
 163     for (int i = N - 3; i <= N; ++i)
 164     {
 165         if (0 <= i && i <= N)
 166         {
 167             C c1 = make<C>(N, start);
 168             C c2 = make<C>(M);
 169             test(i, c1, c2);
 170         }
 171     }
 172 }
 173
 174 template <class C>
 175 void
 176 testI(int P, C& c1, const C& c2)
 177 {
 178     typedef typename C::const_iterator CI;
 179     typedef cpp17_input_iterator<CI> ICI;
 180     std::size_t c1_osize = c1.size();
 181     CI i = c1.insert(c1.begin() + P, ICI(c2.begin()), ICI(c2.end()));
 182     assert(i == c1.begin() + P);
 183     assert(c1.size() == c1_osize + c2.size());
 184     assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
 185     LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c1));
 186     LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c2));
 187     i = c1.begin();
 188     for (int j = 0; j < P; ++j, ++i)
 189         assert(*i == j);
 190     for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
 191         assert(*i == j);
 192     for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
 193         assert(*i == j);
 194 }
 195
 196 template <class C>
 197 void
 198 testNI(int start, int N, int M)
 199 {
 200     for (int i = 0; i <= 3; ++i)
 201     {
 202         if (0 <= i && i <= N)
 203         {
 204             C c1 = make<C>(N, start);
 205             C c2 = make<C>(M);
 206             testI(i, c1, c2);
 207         }
 208     }
 209     for (int i = M-1; i <= M+1; ++i)
 210     {
 211         if (0 <= i && i <= N)
 212         {
 213             C c1 = make<C>(N, start);
 214             C c2 = make<C>(M);
 215             testI(i, c1, c2);
 216         }
 217     }
 218     for (int i = N/2-1; i <= N/2+1; ++i)
 219     {
 220         if (0 <= i && i <= N)
 221         {
 222             C c1 = make<C>(N, start);
 223             C c2 = make<C>(M);
 224             testI(i, c1, c2);
 225         }
 226     }
 227     for (int i = N - M - 1; i <= N - M + 1; ++i)
 228     {
 229         if (0 <= i && i <= N)
 230         {
 231             C c1 = make<C>(N, start);
 232             C c2 = make<C>(M);
 233             testI(i, c1, c2);
 234         }
 235     }
 236     for (int i = N - 3; i <= N; ++i)
 237     {
 238         if (0 <= i && i <= N)
 239         {
 240             C c1 = make<C>(N, start);
 241             C c2 = make<C>(M);
 242             testI(i, c1, c2);
 243         }
 244     }
 245 }
 246
 247 template <class C>
 248 void
 249 test_move()
 250 {
 251 #if TEST_STD_VER >= 11
 252     C c;
 253     typedef typename C::const_iterator CI;
 254     {
 255         MoveOnly mo(0);
 256         typedef MoveOnly* I;
 257         c.insert(c.end(), std::move_iterator<I>(&mo), std::move_iterator<I>(&mo+1));
 258     }
 259     int j = 0;
 260     for (CI i = c.begin(); i != c.end(); ++i, (void) ++j)
 261         assert(*i == MoveOnly(j));
 262     {
 263         MoveOnly mo(1);
 264         typedef cpp17_input_iterator<MoveOnly*> I;
 265         c.insert(c.end(), std::move_iterator<I>(I(&mo)), std::move_iterator<I>(I(&mo+1)));
 266     }
 267     j = 0;
 268     for (CI i = c.begin(); i != c.end(); ++i, (void) ++j)
 269         assert(*i == MoveOnly(j));
 270 #endif
 271 }
 272
 273 int main(int, char**)
 274 {
 275     {
 276     int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
 277     const int N = sizeof(rng)/sizeof(rng[0]);
 278     for (int i = 0; i < N; ++i)
 279         for (int j = 0; j < N; ++j)
 280             for (int k = 0; k < N; ++k)
 281                 testN<std::deque<int> >(rng[i], rng[j], rng[k]);
 282     testNI<std::deque<int> >(1500, 2000, 1000);
 283 #if TEST_STD_VER >= 11
 284     test_move<std::deque<MoveOnly, limited_allocator<MoveOnly, 2000> > >();
 285 #endif
 286     }
 287 #if TEST_STD_VER >= 11
 288     {
 289     int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
 290     const int N = sizeof(rng)/sizeof(rng[0]);
 291     for (int i = 0; i < N; ++i)
 292         for (int j = 0; j < N; ++j)
 293             for (int k = 0; k < N; ++k)
 294                 testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j], rng[k]);
 295     testNI<std::deque<int> >(1500, 2000, 1000);
 296     test_move<std::deque<MoveOnly, min_allocator<MoveOnly> > >();
 297     }
 298     {
 299     int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
 300     const int N = sizeof(rng)/sizeof(rng[0]);
 301     for (int i = 0; i < N; ++i)
 302         for (int j = 0; j < N; ++j)
 303             for (int k = 0; k < N; ++k)
 304                 testN<std::deque<int, safe_allocator<int>> >(rng[i], rng[j], rng[k]);
 305     testNI<std::deque<int> >(1500, 2000, 1000);
 306     test_move<std::deque<MoveOnly, safe_allocator<MoveOnly> > >();
 307     }
 308 #endif
 309
 310   return 0;
 311 }