[ tor-browser ].git.dasho

TestVector.cpp (22954B)
      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
      2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
      3 /* This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
      5 * You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 #include <utility>
      8 
      9 #include "mozilla/IntegerRange.h"
     10 #include "mozilla/UniquePtr.h"
     11 #include "mozilla/Vector.h"
     12 
     13 using mozilla::IntegerRange;
     14 using mozilla::MakeUnique;
     15 using mozilla::UniquePtr;
     16 using mozilla::Vector;
     17 using mozilla::detail::VectorTesting;
     18 
     19 struct mozilla::detail::VectorTesting {
     20  static void testReserved();
     21  static void testConstRange();
     22  static void testEmplaceBack();
     23  static void testReverse();
     24  static void testExtractRawBuffer();
     25  static void testExtractOrCopyRawBuffer();
     26  static void testReplaceRawBuffer();
     27  static void testInsert();
     28  static void testErase();
     29  static void testShrinkStorageToFit();
     30  static void testAppend();
     31 };
     32 
     33 void mozilla::detail::VectorTesting::testReserved() {
     34 #ifdef DEBUG
     35  Vector<bool> bv;
     36  MOZ_RELEASE_ASSERT(bv.reserved() == 0);
     37 
     38  MOZ_RELEASE_ASSERT(bv.append(true));
     39  MOZ_RELEASE_ASSERT(bv.reserved() == 1);
     40 
     41  Vector<bool> otherbv;
     42  MOZ_RELEASE_ASSERT(otherbv.append(false));
     43  MOZ_RELEASE_ASSERT(otherbv.append(true));
     44  MOZ_RELEASE_ASSERT(bv.appendAll(otherbv));
     45  MOZ_RELEASE_ASSERT(bv.reserved() == 3);
     46 
     47  MOZ_RELEASE_ASSERT(bv.reserve(5));
     48  MOZ_RELEASE_ASSERT(bv.reserved() == 5);
     49 
     50  MOZ_RELEASE_ASSERT(bv.reserve(1));
     51  MOZ_RELEASE_ASSERT(bv.reserved() == 5);
     52 
     53  Vector<bool> bv2(std::move(bv));
     54  MOZ_RELEASE_ASSERT(bv.reserved() == 0);
     55  MOZ_RELEASE_ASSERT(bv2.reserved() == 5);
     56 
     57  bv2.clearAndFree();
     58  MOZ_RELEASE_ASSERT(bv2.reserved() == 0);
     59 
     60  Vector<int, 42> iv;
     61  MOZ_RELEASE_ASSERT(iv.reserved() == 0);
     62 
     63  MOZ_RELEASE_ASSERT(iv.append(17));
     64  MOZ_RELEASE_ASSERT(iv.reserved() == 1);
     65 
     66  Vector<int, 42> otheriv;
     67  MOZ_RELEASE_ASSERT(otheriv.append(42));
     68  MOZ_RELEASE_ASSERT(otheriv.append(37));
     69  MOZ_RELEASE_ASSERT(iv.appendAll(otheriv));
     70  MOZ_RELEASE_ASSERT(iv.reserved() == 3);
     71 
     72  MOZ_RELEASE_ASSERT(iv.reserve(5));
     73  MOZ_RELEASE_ASSERT(iv.reserved() == 5);
     74 
     75  MOZ_RELEASE_ASSERT(iv.reserve(1));
     76  MOZ_RELEASE_ASSERT(iv.reserved() == 5);
     77 
     78  MOZ_RELEASE_ASSERT(iv.reserve(55));
     79  MOZ_RELEASE_ASSERT(iv.reserved() == 55);
     80 
     81  Vector<int, 42> iv2(std::move(iv));
     82  MOZ_RELEASE_ASSERT(iv.reserved() == 0);
     83  MOZ_RELEASE_ASSERT(iv2.reserved() == 55);
     84 
     85  iv2.clearAndFree();
     86  MOZ_RELEASE_ASSERT(iv2.reserved() == 0);
     87 #endif
     88 }
     89 
     90 void mozilla::detail::VectorTesting::testConstRange() {
     91 #ifdef DEBUG
     92  Vector<int> vec;
     93 
     94  for (int i = 0; i < 10; i++) {
     95    MOZ_RELEASE_ASSERT(vec.append(i));
     96  }
     97 
     98  const auto& vecRef = vec;
     99 
    100  Vector<int>::ConstRange range = vecRef.all();
    101  for (int i = 0; i < 10; i++) {
    102    MOZ_RELEASE_ASSERT(!range.empty());
    103    MOZ_RELEASE_ASSERT(range.front() == i);
    104    range.popFront();
    105  }
    106 #endif
    107 }
    108 
    109 namespace {
    110 
    111 struct S {
    112  size_t j;
    113  UniquePtr<size_t> k;
    114 
    115  static size_t constructCount;
    116  static size_t moveCount;
    117  static size_t destructCount;
    118 
    119  static void resetCounts() {
    120    constructCount = 0;
    121    moveCount = 0;
    122    destructCount = 0;
    123  }
    124 
    125  S(size_t j, size_t k) : j(j), k(MakeUnique<size_t>(k)) { constructCount++; }
    126 
    127  S(S&& rhs) : j(rhs.j), k(std::move(rhs.k)) {
    128    rhs.j = 0;
    129    rhs.k.reset(0);
    130    moveCount++;
    131  }
    132 
    133  ~S() { destructCount++; }
    134 
    135  S& operator=(S&& rhs) {
    136    j = rhs.j;
    137    rhs.j = 0;
    138    k = std::move(rhs.k);
    139    rhs.k.reset();
    140    moveCount++;
    141    return *this;
    142  }
    143 
    144  bool operator==(const S& rhs) const { return j == rhs.j && *k == *rhs.k; }
    145 
    146  S(const S&) = delete;
    147  S& operator=(const S&) = delete;
    148 };
    149 
    150 size_t S::constructCount = 0;
    151 size_t S::moveCount = 0;
    152 size_t S::destructCount = 0;
    153 
    154 }  // namespace
    155 
    156 void mozilla::detail::VectorTesting::testEmplaceBack() {
    157  S::resetCounts();
    158 
    159  Vector<S> vec;
    160  MOZ_RELEASE_ASSERT(vec.reserve(20));
    161 
    162  for (size_t i = 0; i < 10; i++) {
    163    S s(i, i * i);
    164    MOZ_RELEASE_ASSERT(vec.append(std::move(s)));
    165  }
    166 
    167  MOZ_RELEASE_ASSERT(vec.length() == 10);
    168  MOZ_RELEASE_ASSERT(S::constructCount == 10);
    169  MOZ_RELEASE_ASSERT(S::moveCount == 10);
    170 
    171  for (size_t i = 10; i < 20; i++) {
    172    MOZ_RELEASE_ASSERT(vec.emplaceBack(i, i * i));
    173  }
    174 
    175  MOZ_RELEASE_ASSERT(vec.length() == 20);
    176  MOZ_RELEASE_ASSERT(S::constructCount == 20);
    177  MOZ_RELEASE_ASSERT(S::moveCount == 10);
    178 
    179  for (size_t i = 0; i < 20; i++) {
    180    MOZ_RELEASE_ASSERT(vec[i].j == i);
    181    MOZ_RELEASE_ASSERT(*vec[i].k == i * i);
    182  }
    183 }
    184 
    185 void mozilla::detail::VectorTesting::testReverse() {
    186  // Use UniquePtr to make sure that reverse() can handler move-only types.
    187  Vector<UniquePtr<uint8_t>, 0> vec;
    188 
    189  // Reverse an odd number of elements.
    190 
    191  for (uint8_t i = 0; i < 5; i++) {
    192    auto p = MakeUnique<uint8_t>(i);
    193    MOZ_RELEASE_ASSERT(p);
    194    MOZ_RELEASE_ASSERT(vec.append(std::move(p)));
    195  }
    196 
    197  vec.reverse();
    198 
    199  MOZ_RELEASE_ASSERT(*vec[0] == 4);
    200  MOZ_RELEASE_ASSERT(*vec[1] == 3);
    201  MOZ_RELEASE_ASSERT(*vec[2] == 2);
    202  MOZ_RELEASE_ASSERT(*vec[3] == 1);
    203  MOZ_RELEASE_ASSERT(*vec[4] == 0);
    204 
    205  // Reverse an even number of elements.
    206 
    207  vec.popBack();
    208  vec.reverse();
    209 
    210  MOZ_RELEASE_ASSERT(*vec[0] == 1);
    211  MOZ_RELEASE_ASSERT(*vec[1] == 2);
    212  MOZ_RELEASE_ASSERT(*vec[2] == 3);
    213  MOZ_RELEASE_ASSERT(*vec[3] == 4);
    214 
    215  // Reverse an empty vector.
    216 
    217  vec.clear();
    218  MOZ_RELEASE_ASSERT(vec.length() == 0);
    219  vec.reverse();
    220  MOZ_RELEASE_ASSERT(vec.length() == 0);
    221 
    222  // Reverse a vector using only inline storage.
    223 
    224  Vector<UniquePtr<uint8_t>, 5> vec2;
    225  for (uint8_t i = 0; i < 5; i++) {
    226    auto p = MakeUnique<uint8_t>(i);
    227    MOZ_RELEASE_ASSERT(p);
    228    MOZ_RELEASE_ASSERT(vec2.append(std::move(p)));
    229  }
    230 
    231  vec2.reverse();
    232 
    233  MOZ_RELEASE_ASSERT(*vec2[0] == 4);
    234  MOZ_RELEASE_ASSERT(*vec2[1] == 3);
    235  MOZ_RELEASE_ASSERT(*vec2[2] == 2);
    236  MOZ_RELEASE_ASSERT(*vec2[3] == 1);
    237  MOZ_RELEASE_ASSERT(*vec2[4] == 0);
    238 }
    239 
    240 void mozilla::detail::VectorTesting::testExtractRawBuffer() {
    241  S::resetCounts();
    242 
    243  Vector<S, 5> vec;
    244  MOZ_RELEASE_ASSERT(vec.reserve(5));
    245  for (size_t i = 0; i < 5; i++) {
    246    vec.infallibleEmplaceBack(i, i * i);
    247  }
    248  MOZ_RELEASE_ASSERT(vec.length() == 5);
    249  MOZ_ASSERT(vec.reserved() == 5);
    250  MOZ_RELEASE_ASSERT(S::constructCount == 5);
    251  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    252  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    253 
    254  S* buf = vec.extractRawBuffer();
    255  MOZ_RELEASE_ASSERT(!buf);
    256  MOZ_RELEASE_ASSERT(vec.length() == 5);
    257  MOZ_ASSERT(vec.reserved() == 5);
    258  MOZ_RELEASE_ASSERT(S::constructCount == 5);
    259  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    260  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    261 
    262  MOZ_RELEASE_ASSERT(vec.reserve(10));
    263  for (size_t i = 5; i < 10; i++) {
    264    vec.infallibleEmplaceBack(i, i * i);
    265  }
    266  MOZ_RELEASE_ASSERT(vec.length() == 10);
    267  MOZ_ASSERT(vec.reserved() == 10);
    268  MOZ_RELEASE_ASSERT(S::constructCount == 10);
    269  MOZ_RELEASE_ASSERT(S::moveCount == 5);
    270  MOZ_RELEASE_ASSERT(S::destructCount == 5);
    271 
    272  buf = vec.extractRawBuffer();
    273  MOZ_RELEASE_ASSERT(buf);
    274  MOZ_RELEASE_ASSERT(vec.length() == 0);
    275  MOZ_ASSERT(vec.reserved() == 0);
    276  MOZ_RELEASE_ASSERT(S::constructCount == 10);
    277  MOZ_RELEASE_ASSERT(S::moveCount == 5);
    278  MOZ_RELEASE_ASSERT(S::destructCount == 5);
    279 
    280  for (size_t i = 0; i < 10; i++) {
    281    MOZ_RELEASE_ASSERT(buf[i].j == i);
    282    MOZ_RELEASE_ASSERT(*buf[i].k == i * i);
    283  }
    284 
    285  free(buf);
    286 }
    287 
    288 void mozilla::detail::VectorTesting::testExtractOrCopyRawBuffer() {
    289  S::resetCounts();
    290 
    291  Vector<S, 5> vec;
    292  MOZ_RELEASE_ASSERT(vec.reserve(5));
    293  for (size_t i = 0; i < 5; i++) {
    294    vec.infallibleEmplaceBack(i, i * i);
    295  }
    296  MOZ_RELEASE_ASSERT(vec.length() == 5);
    297  MOZ_ASSERT(vec.reserved() == 5);
    298  MOZ_RELEASE_ASSERT(S::constructCount == 5);
    299  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    300  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    301 
    302  S* buf = vec.extractOrCopyRawBuffer();
    303  MOZ_RELEASE_ASSERT(buf);
    304  MOZ_RELEASE_ASSERT(vec.length() == 0);
    305  MOZ_ASSERT(vec.reserved() == 0);
    306  MOZ_RELEASE_ASSERT(S::constructCount == 5);
    307  MOZ_RELEASE_ASSERT(S::moveCount == 5);
    308  MOZ_RELEASE_ASSERT(S::destructCount == 5);
    309 
    310  for (size_t i = 0; i < 5; i++) {
    311    MOZ_RELEASE_ASSERT(buf[i].j == i);
    312    MOZ_RELEASE_ASSERT(*buf[i].k == i * i);
    313  }
    314 
    315  S::resetCounts();
    316 
    317  MOZ_RELEASE_ASSERT(vec.reserve(10));
    318  for (size_t i = 0; i < 10; i++) {
    319    vec.infallibleEmplaceBack(i, i * i);
    320  }
    321  MOZ_RELEASE_ASSERT(vec.length() == 10);
    322  MOZ_ASSERT(vec.reserved() == 10);
    323  MOZ_RELEASE_ASSERT(S::constructCount == 10);
    324  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    325  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    326 
    327  buf = vec.extractOrCopyRawBuffer();
    328  MOZ_RELEASE_ASSERT(buf);
    329  MOZ_RELEASE_ASSERT(vec.length() == 0);
    330  MOZ_ASSERT(vec.reserved() == 0);
    331  MOZ_RELEASE_ASSERT(S::constructCount == 10);
    332  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    333  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    334 
    335  for (size_t i = 0; i < 10; i++) {
    336    MOZ_RELEASE_ASSERT(buf[i].j == i);
    337    MOZ_RELEASE_ASSERT(*buf[i].k == i * i);
    338  }
    339 
    340  free(buf);
    341 }
    342 
    343 void mozilla::detail::VectorTesting::testReplaceRawBuffer() {
    344  S::resetCounts();
    345 
    346  S* s = nullptr;
    347 
    348  {
    349    Vector<S> v;
    350    MOZ_RELEASE_ASSERT(v.reserve(4));
    351    v.infallibleEmplaceBack(1, 2);
    352    v.infallibleEmplaceBack(3, 4);
    353    MOZ_RELEASE_ASSERT(S::constructCount == 2);
    354    s = v.extractRawBuffer();
    355  }
    356 
    357  MOZ_RELEASE_ASSERT(S::constructCount == 2);
    358  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    359  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    360 
    361  {
    362    Vector<S, 10> v;
    363    v.replaceRawBuffer(s, 2);
    364    MOZ_ASSERT(v.reserved() == 2);
    365    MOZ_RELEASE_ASSERT(v.length() == 2);
    366    MOZ_RELEASE_ASSERT(v.capacity() == 10);
    367    MOZ_RELEASE_ASSERT(v[0].j == 1);
    368    MOZ_RELEASE_ASSERT(v[1].j == 3);
    369    MOZ_RELEASE_ASSERT(S::destructCount == 2);
    370  }
    371 
    372  MOZ_RELEASE_ASSERT(S::constructCount == 2);
    373  MOZ_RELEASE_ASSERT(S::moveCount == 2);
    374  MOZ_RELEASE_ASSERT(S::destructCount == 4);
    375 
    376  S::resetCounts();
    377 
    378  {
    379    Vector<S, 2> v;
    380    MOZ_RELEASE_ASSERT(v.reserve(4));
    381    v.infallibleEmplaceBack(9, 10);
    382    MOZ_RELEASE_ASSERT(S::constructCount == 1);
    383    s = v.extractRawBuffer();
    384    MOZ_RELEASE_ASSERT(S::constructCount == 1);
    385    MOZ_RELEASE_ASSERT(S::moveCount == 0);
    386  }
    387 
    388  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    389 
    390  {
    391    Vector<S> v;
    392    v.replaceRawBuffer(s, 1, 4);
    393    MOZ_ASSERT(v.reserved() == 4);
    394    MOZ_RELEASE_ASSERT(v.length() == 1);
    395    MOZ_RELEASE_ASSERT(v.capacity() == 4);
    396    MOZ_RELEASE_ASSERT(v[0].j == 9);
    397    for (size_t i = 0; i < 5; i++) MOZ_RELEASE_ASSERT(v.emplaceBack(i, i));
    398    MOZ_ASSERT(v.reserved() == 6);
    399    MOZ_RELEASE_ASSERT(v.length() == 6);
    400    MOZ_RELEASE_ASSERT(S::constructCount == 6);
    401    MOZ_RELEASE_ASSERT(S::moveCount == 4);
    402    MOZ_RELEASE_ASSERT(S::destructCount == 4);
    403  }
    404 
    405  MOZ_RELEASE_ASSERT(S::destructCount == 10);
    406 }
    407 
    408 void mozilla::detail::VectorTesting::testInsert() {
    409  S::resetCounts();
    410 
    411  Vector<S, 8> vec;
    412  MOZ_RELEASE_ASSERT(vec.reserve(8));
    413  for (size_t i = 0; i < 7; i++) {
    414    vec.infallibleEmplaceBack(i, i * i);
    415  }
    416 
    417  MOZ_RELEASE_ASSERT(vec.length() == 7);
    418  MOZ_ASSERT(vec.reserved() == 8);
    419  MOZ_RELEASE_ASSERT(S::constructCount == 7);
    420  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    421  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    422 
    423  S s(42, 43);
    424  MOZ_RELEASE_ASSERT(vec.insert(vec.begin() + 4, std::move(s)));
    425 
    426  for (size_t i = 0; i < vec.length(); i++) {
    427    const S& s = vec[i];
    428    MOZ_RELEASE_ASSERT(s.k);
    429    if (i < 4) {
    430      MOZ_RELEASE_ASSERT(s.j == i && *s.k == i * i);
    431    } else if (i == 4) {
    432      MOZ_RELEASE_ASSERT(s.j == 42 && *s.k == 43);
    433    } else {
    434      MOZ_RELEASE_ASSERT(s.j == i - 1 && *s.k == (i - 1) * (i - 1));
    435    }
    436  }
    437 
    438  MOZ_RELEASE_ASSERT(vec.length() == 8);
    439  MOZ_ASSERT(vec.reserved() == 8);
    440  MOZ_RELEASE_ASSERT(S::constructCount == 8);
    441  MOZ_RELEASE_ASSERT(S::moveCount == 1 /* move in insert() call */ +
    442                                         1 /* move the back() element */ +
    443                                         3 /* elements to shift */);
    444  MOZ_RELEASE_ASSERT(S::destructCount == 1);
    445 }
    446 
    447 void mozilla::detail::VectorTesting::testErase() {
    448  S::resetCounts();
    449 
    450  Vector<S, 8> vec;
    451  MOZ_RELEASE_ASSERT(vec.reserve(8));
    452  for (size_t i = 0; i < 7; i++) {
    453    vec.infallibleEmplaceBack(i, i * i);
    454  }
    455 
    456  // vec: [0, 1, 2, 3, 4, 5, 6]
    457  MOZ_RELEASE_ASSERT(vec.length() == 7);
    458  MOZ_ASSERT(vec.reserved() == 8);
    459  MOZ_RELEASE_ASSERT(S::constructCount == 7);
    460  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    461  MOZ_RELEASE_ASSERT(S::destructCount == 0);
    462  S::resetCounts();
    463 
    464  vec.erase(&vec[4]);
    465  // vec: [0, 1, 2, 3, 5, 6]
    466  MOZ_RELEASE_ASSERT(vec.length() == 6);
    467  MOZ_ASSERT(vec.reserved() == 8);
    468  MOZ_RELEASE_ASSERT(S::constructCount == 0);
    469  // 5 and 6 should have been moved into 4 and 5.
    470  MOZ_RELEASE_ASSERT(S::moveCount == 2);
    471  MOZ_RELEASE_ASSERT(S::destructCount == 1);
    472  MOZ_RELEASE_ASSERT(vec[4] == S(5, 5 * 5));
    473  MOZ_RELEASE_ASSERT(vec[5] == S(6, 6 * 6));
    474  S::resetCounts();
    475 
    476  vec.erase(&vec[3], &vec[5]);
    477  // vec: [0, 1, 2, 6]
    478  MOZ_RELEASE_ASSERT(vec.length() == 4);
    479  MOZ_ASSERT(vec.reserved() == 8);
    480  MOZ_RELEASE_ASSERT(S::constructCount == 0);
    481  // 6 should have been moved into 3.
    482  MOZ_RELEASE_ASSERT(S::moveCount == 1);
    483  MOZ_RELEASE_ASSERT(S::destructCount == 2);
    484  MOZ_RELEASE_ASSERT(vec[3] == S(6, 6 * 6));
    485 
    486  S s2(2, 2 * 2);
    487  S::resetCounts();
    488 
    489  vec.eraseIfEqual(s2);
    490  // vec: [0, 1, 6]
    491  MOZ_RELEASE_ASSERT(vec.length() == 3);
    492  MOZ_ASSERT(vec.reserved() == 8);
    493  MOZ_RELEASE_ASSERT(S::constructCount == 0);
    494  // 6 should have been moved into 2.
    495  MOZ_RELEASE_ASSERT(S::moveCount == 1);
    496  MOZ_RELEASE_ASSERT(S::destructCount == 1);
    497  MOZ_RELEASE_ASSERT(vec[2] == S(6, 6 * 6));
    498  S::resetCounts();
    499 
    500  // Predicate to find one element.
    501  vec.eraseIf([](const S& s) { return s.j == 1; });
    502  // vec: [0, 6]
    503  MOZ_RELEASE_ASSERT(vec.length() == 2);
    504  MOZ_ASSERT(vec.reserved() == 8);
    505  MOZ_RELEASE_ASSERT(S::constructCount == 0);
    506  // 6 should have been moved into 1.
    507  MOZ_RELEASE_ASSERT(S::moveCount == 1);
    508  MOZ_RELEASE_ASSERT(S::destructCount == 1);
    509  MOZ_RELEASE_ASSERT(vec[1] == S(6, 6 * 6));
    510  S::resetCounts();
    511 
    512  // Generic predicate that flags everything.
    513  vec.eraseIf([](auto&&) { return true; });
    514  // vec: []
    515  MOZ_RELEASE_ASSERT(vec.length() == 0);
    516  MOZ_ASSERT(vec.reserved() == 8);
    517  MOZ_RELEASE_ASSERT(S::constructCount == 0);
    518  MOZ_RELEASE_ASSERT(S::moveCount == 0);
    519  MOZ_RELEASE_ASSERT(S::destructCount == 2);
    520 
    521  for (size_t i = 0; i < 7; i++) {
    522    vec.infallibleEmplaceBack(i, i * i);
    523  }
    524  // vec: [0, 1, 2, 3, 4, 5, 6]
    525  MOZ_RELEASE_ASSERT(vec.length() == 7);
    526  S::resetCounts();
    527 
    528  // Predicate that flags all even numbers.
    529  vec.eraseIf([](const S& s) { return s.j % 2 == 0; });
    530  // vec: [1 (was 0), 3 (was 1), 5 (was 2)]
    531  MOZ_RELEASE_ASSERT(vec.length() == 3);
    532  MOZ_ASSERT(vec.reserved() == 8);
    533  MOZ_RELEASE_ASSERT(S::constructCount == 0);
    534  MOZ_RELEASE_ASSERT(S::moveCount == 3);
    535  MOZ_RELEASE_ASSERT(S::destructCount == 4);
    536 }
    537 
    538 void mozilla::detail::VectorTesting::testShrinkStorageToFit() {
    539  // Vectors not using inline storage realloc capacity to exact length.
    540  {
    541    Vector<int, 0> v1;
    542    MOZ_RELEASE_ASSERT(v1.reserve(10));
    543    v1.infallibleAppend(1);
    544    MOZ_ASSERT(v1.reserved() == 10);
    545    MOZ_RELEASE_ASSERT(v1.length() == 1);
    546    MOZ_RELEASE_ASSERT(v1.capacity() >= 10);
    547    v1.shrinkStorageToFit();
    548    MOZ_ASSERT(v1.reserved() == 1);
    549    MOZ_RELEASE_ASSERT(v1.length() == 1);
    550    MOZ_RELEASE_ASSERT(v1.capacity() == 1);
    551  }
    552 
    553  // Vectors using inline storage do nothing.
    554  {
    555    Vector<int, 2> v2;
    556    MOZ_RELEASE_ASSERT(v2.reserve(2));
    557    v2.infallibleAppend(1);
    558    MOZ_ASSERT(v2.reserved() == 2);
    559    MOZ_RELEASE_ASSERT(v2.length() == 1);
    560    MOZ_RELEASE_ASSERT(v2.capacity() == 2);
    561    v2.shrinkStorageToFit();
    562    MOZ_ASSERT(v2.reserved() == 2);
    563    MOZ_RELEASE_ASSERT(v2.length() == 1);
    564    MOZ_RELEASE_ASSERT(v2.capacity() == 2);
    565  }
    566 
    567  // shrinkStorageToFit uses inline storage if possible.
    568  {
    569    Vector<int, 2> v;
    570    MOZ_RELEASE_ASSERT(v.reserve(4));
    571    v.infallibleAppend(1);
    572    MOZ_ASSERT(v.reserved() == 4);
    573    MOZ_RELEASE_ASSERT(v.length() == 1);
    574    MOZ_RELEASE_ASSERT(v.capacity() >= 4);
    575    v.shrinkStorageToFit();
    576    MOZ_ASSERT(v.reserved() == 1);
    577    MOZ_RELEASE_ASSERT(v.length() == 1);
    578    MOZ_RELEASE_ASSERT(v.capacity() == 2);
    579  }
    580 
    581  // Non-pod shrinking to non-inline storage.
    582  {
    583    static size_t sConstructCounter = 0;
    584    static size_t sCopyCounter = 0;
    585    static size_t sMoveCounter = 0;
    586    static size_t sDestroyCounter = 0;
    587    struct NonPod {
    588      int mSomething = 10;
    589 
    590      NonPod() { sConstructCounter++; }
    591 
    592      NonPod(const NonPod& aOther) : mSomething(aOther.mSomething) {
    593        sCopyCounter++;
    594      }
    595      NonPod(NonPod&& aOther) : mSomething(aOther.mSomething) {
    596        sMoveCounter++;
    597      }
    598      ~NonPod() { sDestroyCounter++; }
    599    };
    600 
    601    Vector<NonPod, 5> v;
    602    MOZ_RELEASE_ASSERT(v.reserve(10));
    603    for (size_t i = 0; i < 8; ++i) {
    604      v.infallibleEmplaceBack();
    605    }
    606    MOZ_RELEASE_ASSERT(sConstructCounter == 8);
    607    MOZ_RELEASE_ASSERT(sCopyCounter == 0);
    608    MOZ_RELEASE_ASSERT(sMoveCounter == 0);
    609    MOZ_RELEASE_ASSERT(sDestroyCounter == 0);
    610    MOZ_RELEASE_ASSERT(v.length() == 8);
    611    MOZ_ASSERT(v.reserved() == 10);
    612    MOZ_RELEASE_ASSERT(v.capacity() >= 10);
    613    MOZ_RELEASE_ASSERT(v.shrinkStorageToFit());
    614 
    615    MOZ_RELEASE_ASSERT(sConstructCounter == 8);
    616    MOZ_RELEASE_ASSERT(sCopyCounter == 0);
    617    MOZ_RELEASE_ASSERT(sMoveCounter == 8);
    618    MOZ_RELEASE_ASSERT(sDestroyCounter == 8);
    619    MOZ_RELEASE_ASSERT(v.length() == 8);
    620    MOZ_ASSERT(v.reserved() == 8);
    621    MOZ_RELEASE_ASSERT(v.capacity() == 8);
    622  }
    623 
    624  // Non-POD shrinking to inline storage.
    625  {
    626    static size_t sConstructCounter = 0;
    627    static size_t sCopyCounter = 0;
    628    static size_t sMoveCounter = 0;
    629    static size_t sDestroyCounter = 0;
    630    struct NonPod {
    631      int mSomething = 10;
    632 
    633      NonPod() { sConstructCounter++; }
    634 
    635      NonPod(const NonPod& aOther) : mSomething(aOther.mSomething) {
    636        sCopyCounter++;
    637      }
    638      NonPod(NonPod&& aOther) : mSomething(aOther.mSomething) {
    639        sMoveCounter++;
    640      }
    641      ~NonPod() { sDestroyCounter++; }
    642    };
    643 
    644    Vector<NonPod, 5> v;
    645    MOZ_RELEASE_ASSERT(v.reserve(10));
    646    for (size_t i = 0; i < 3; ++i) {
    647      v.infallibleEmplaceBack();
    648    }
    649    MOZ_RELEASE_ASSERT(sConstructCounter == 3);
    650    MOZ_RELEASE_ASSERT(sCopyCounter == 0);
    651    MOZ_RELEASE_ASSERT(sMoveCounter == 0);
    652    MOZ_RELEASE_ASSERT(sDestroyCounter == 0);
    653    MOZ_RELEASE_ASSERT(v.length() == 3);
    654    MOZ_ASSERT(v.reserved() == 10);
    655    MOZ_RELEASE_ASSERT(v.capacity() >= 10);
    656    MOZ_RELEASE_ASSERT(v.shrinkStorageToFit());
    657 
    658    MOZ_RELEASE_ASSERT(sConstructCounter == 3);
    659    MOZ_RELEASE_ASSERT(sCopyCounter == 0);
    660    MOZ_RELEASE_ASSERT(sMoveCounter == 3);
    661    MOZ_RELEASE_ASSERT(sDestroyCounter == 3);
    662    MOZ_RELEASE_ASSERT(v.length() == 3);
    663    MOZ_ASSERT(v.reserved() == 3);
    664    MOZ_RELEASE_ASSERT(v.capacity() == 5);
    665  }
    666 }
    667 
    668 void mozilla::detail::VectorTesting::testAppend() {
    669  // Test moving append/appendAll with a move-only type
    670  Vector<UniquePtr<int>> bv;
    671  for (const int val : IntegerRange<int>(0, 3)) {
    672    MOZ_RELEASE_ASSERT(bv.append(MakeUnique<int>(val)));
    673  }
    674 
    675  Vector<UniquePtr<int>> otherbv;
    676  for (const int val : IntegerRange<int>(3, 8)) {
    677    MOZ_RELEASE_ASSERT(otherbv.append(MakeUnique<int>(val)));
    678  }
    679  MOZ_RELEASE_ASSERT(bv.appendAll(std::move(otherbv)));
    680 
    681  MOZ_RELEASE_ASSERT(otherbv.length() == 0);
    682  MOZ_RELEASE_ASSERT(bv.length() == 8);
    683  for (const int val : IntegerRange<int>(0, 8)) {
    684    MOZ_RELEASE_ASSERT(*bv[val] == val);
    685  }
    686 }
    687 
    688 // Vector with no inline storage should occupy the absolute minimum space in
    689 // non-debug builds.  (Debug adds a laundry list of other constraints, none
    690 // directly relevant to shipping builds, that aren't worth precisely modeling.)
    691 #ifndef DEBUG
    692 
    693 template <typename T>
    694 struct NoInlineStorageLayout {
    695  T* mBegin;
    696  size_t mLength;
    697  struct CRAndStorage {
    698    size_t mCapacity;
    699  } mTail;
    700 };
    701 
    702 // Only one of these should be necessary, but test a few of them for good
    703 // measure.
    704 static_assert(sizeof(Vector<int, 0>) == sizeof(NoInlineStorageLayout<int>),
    705              "Vector of int without inline storage shouldn't occupy dead "
    706              "space for that absence of storage");
    707 
    708 static_assert(sizeof(Vector<bool, 0>) == sizeof(NoInlineStorageLayout<bool>),
    709              "Vector of bool without inline storage shouldn't occupy dead "
    710              "space for that absence of storage");
    711 
    712 static_assert(sizeof(Vector<S, 0>) == sizeof(NoInlineStorageLayout<S>),
    713              "Vector of S without inline storage shouldn't occupy dead "
    714              "space for that absence of storage");
    715 
    716 #endif  // DEBUG
    717 
    718 static void TestVectorBeginNonNull() {
    719  // Vector::begin() should never return nullptr, to accommodate callers that
    720  // (either for hygiene, or for semantic reasons) need a non-null pointer even
    721  // for zero elements.
    722 
    723  Vector<bool, 0> bvec0;
    724  MOZ_RELEASE_ASSERT(bvec0.length() == 0);
    725  MOZ_RELEASE_ASSERT(bvec0.begin() != nullptr);
    726 
    727  Vector<bool, 1> bvec1;
    728  MOZ_RELEASE_ASSERT(bvec1.length() == 0);
    729  MOZ_RELEASE_ASSERT(bvec1.begin() != nullptr);
    730 
    731  Vector<bool, 64> bvec64;
    732  MOZ_RELEASE_ASSERT(bvec64.length() == 0);
    733  MOZ_RELEASE_ASSERT(bvec64.begin() != nullptr);
    734 
    735  Vector<int, 0> ivec0;
    736  MOZ_RELEASE_ASSERT(ivec0.length() == 0);
    737  MOZ_RELEASE_ASSERT(ivec0.begin() != nullptr);
    738 
    739  Vector<int, 1> ivec1;
    740  MOZ_RELEASE_ASSERT(ivec1.length() == 0);
    741  MOZ_RELEASE_ASSERT(ivec1.begin() != nullptr);
    742 
    743  Vector<int, 64> ivec64;
    744  MOZ_RELEASE_ASSERT(ivec64.length() == 0);
    745  MOZ_RELEASE_ASSERT(ivec64.begin() != nullptr);
    746 
    747  Vector<long, 0> lvec0;
    748  MOZ_RELEASE_ASSERT(lvec0.length() == 0);
    749  MOZ_RELEASE_ASSERT(lvec0.begin() != nullptr);
    750 
    751  Vector<long, 1> lvec1;
    752  MOZ_RELEASE_ASSERT(lvec1.length() == 0);
    753  MOZ_RELEASE_ASSERT(lvec1.begin() != nullptr);
    754 
    755  Vector<long, 64> lvec64;
    756  MOZ_RELEASE_ASSERT(lvec64.length() == 0);
    757  MOZ_RELEASE_ASSERT(lvec64.begin() != nullptr);
    758 
    759  // Vector<T, N> doesn't guarantee N inline elements -- the actual count is
    760  // capped so that any Vector fits in a not-crazy amount of space -- so the
    761  // code below won't overflow stacks or anything crazy.
    762  struct VeryBig {
    763    int array[16 * 1024 * 1024];
    764  };
    765 
    766  Vector<VeryBig, 0> vbvec0;
    767  MOZ_RELEASE_ASSERT(vbvec0.length() == 0);
    768  MOZ_RELEASE_ASSERT(vbvec0.begin() != nullptr);
    769 
    770  Vector<VeryBig, 1> vbvec1;
    771  MOZ_RELEASE_ASSERT(vbvec1.length() == 0);
    772  MOZ_RELEASE_ASSERT(vbvec1.begin() != nullptr);
    773 
    774  Vector<VeryBig, 64> vbvec64;
    775  MOZ_RELEASE_ASSERT(vbvec64.length() == 0);
    776  MOZ_RELEASE_ASSERT(vbvec64.begin() != nullptr);
    777 }
    778 
    779 int main() {
    780  VectorTesting::testReserved();
    781  VectorTesting::testConstRange();
    782  VectorTesting::testEmplaceBack();
    783  VectorTesting::testReverse();
    784  VectorTesting::testExtractRawBuffer();
    785  VectorTesting::testExtractOrCopyRawBuffer();
    786  VectorTesting::testReplaceRawBuffer();
    787  VectorTesting::testInsert();
    788  VectorTesting::testErase();
    789  VectorTesting::testShrinkStorageToFit();
    790  VectorTesting::testAppend();
    791  TestVectorBeginNonNull();
    792 }
	tor-browser The Tor Browser
	git clone https://git.dasho.dev/tor-browser.git
	Log \| Files \| Refs \| README \| LICENSE