Home | History | Annotate | Download | only in test 
      1 // Copyright 2014, ARM Limited
      2 // All rights reserved.
      3 //
      4 // Redistribution and use in source and binary forms, with or without
      5 // modification, are permitted provided that the following conditions are met:
      6 //
      7 //   * Redistributions of source code must retain the above copyright notice,
      8 //     this list of conditions and the following disclaimer.
      9 //   * Redistributions in binary form must reproduce the above copyright notice,
     10 //     this list of conditions and the following disclaimer in the documentation
     11 //     and/or other materials provided with the distribution.
     12 //   * Neither the name of ARM Limited nor the names of its contributors may be
     13 //     used to endorse or promote products derived from this software without
     14 //     specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND
     17 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
     18 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
     19 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
     20 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
     22 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     23 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     24 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     26 
     27 #include "test-runner.h"
     28 
     29 #include "vixl/invalset.h"
     30 
     31 namespace vixl {
     32 
     33 // This file contains tests for the `InvalSet` and `InvalSetIterator` classes.
     34 
     35 #define TEST(name)  TEST_(INVALSET_##name)
     36 
     37 typedef ptrdiff_t KeyType;
     38 typedef ptrdiff_t ValType;
     39 
     40 // We test with an object for which the key and the value are distinct.
     41 class Obj {
     42  public:
     43   Obj() {}
     44   Obj(KeyType key, ValType val) : key_(key), val_(val) {}
     45   KeyType key_;
     46   ValType val_;
     47 
     48   bool operator==(const Obj& other) const {
     49     return (key_ == other.key_) && (val_ == other.val_);
     50   }
     51   bool operator<(const Obj& other) const {
     52     return (key_ < other.key_) ||
     53         ((key_ == other.key_) && (val_ < other.val_));
     54   }
     55   bool operator<=(const Obj& other) const {
     56     return (key_ <= other.key_) ||
     57         ((key_ == other.key_) && (val_ <= other.val_));
     58   }
     59   bool operator>(const Obj& other) const {
     60     return (key_ > other.key_) ||
     61         ((key_ == other.key_) && (val_ > other.val_));
     62   }
     63 };
     64 
     65 static const unsigned kNPreallocatedElements = 8;
     66 static const KeyType kInvalidKey = PTRDIFF_MAX;
     67 static const size_t kReclaimFrom = 1000;
     68 static const unsigned kReclaimFactor = 10;
     69 
     70 typedef InvalSet<Obj,
     71                  kNPreallocatedElements,
     72                  KeyType,
     73                  kInvalidKey,
     74                  kReclaimFrom,
     75                  kReclaimFactor> TestSet;
     76 
     77 template<>
     78 inline KeyType InvalSet<Obj,
     79                         kNPreallocatedElements,
     80                         KeyType,
     81                         kInvalidKey,
     82                         kReclaimFrom,
     83                         kReclaimFactor>::Key(const Obj& obj) {
     84   return obj.key_;
     85 }
     86 template<>
     87 inline void InvalSet<Obj,
     88                      kNPreallocatedElements,
     89                      KeyType,
     90                      kInvalidKey,
     91                      kReclaimFrom,
     92                      kReclaimFactor>::SetKey(Obj* obj, KeyType key) {
     93   obj->key_ = key;
     94 }
     95 
     96 
     97 TEST(basic_test) {
     98   TestSet set;
     99   VIXL_CHECK(set.empty() && (set.size() == 0));
    100 
    101   for (unsigned i = 0; i < kNPreallocatedElements; i++) {
    102     set.insert(Obj(i, i));
    103   }
    104   VIXL_CHECK(set.size() == kNPreallocatedElements);
    105 
    106   set.insert(Obj(-123, 456));
    107   set.insert(Obj(2718, 2871828));
    108   VIXL_CHECK(set.size() == kNPreallocatedElements + 2);
    109   VIXL_CHECK(set.min_element() == Obj(-123, 456));
    110 
    111   set.erase(Obj(-123, 456));
    112   VIXL_CHECK(set.min_element_key() == 0);
    113 
    114   set.clear();
    115   VIXL_CHECK(set.empty() && (set.size() == 0));
    116 }
    117 
    118 
    119 TEST(valid_element) {
    120   VIXL_CHECK(TestSet::IsValid(Obj(0, 0)));
    121   VIXL_CHECK(TestSet::IsValid(Obj(-1, 0)));
    122   VIXL_CHECK(TestSet::IsValid(Obj(kInvalidKey - 1, 0)));
    123   VIXL_CHECK(!TestSet::IsValid(Obj(kInvalidKey, 0)));
    124 }
    125 
    126 
    127 TEST(insert) {
    128   TestSet set;
    129   VIXL_CHECK(set.empty() && (set.size() == 0));
    130 
    131   for (unsigned i = 0; i < kNPreallocatedElements; i++) {
    132     set.insert(Obj(i, i));
    133   }
    134   VIXL_CHECK(set.size() == kNPreallocatedElements);
    135   set.insert(Obj(-123, 1));
    136   VIXL_CHECK(set.size() == kNPreallocatedElements + 1);
    137   set.insert(Obj(-123, 2));
    138   set.insert(Obj(-123, 3));
    139   VIXL_CHECK(set.size() == kNPreallocatedElements + 3);
    140 
    141   set.clear();
    142   VIXL_CHECK(set.empty() && (set.size() == 0));
    143 }
    144 
    145 
    146 TEST(erase) {
    147   TestSet set;
    148   VIXL_CHECK(set.empty() && (set.size() == 0));
    149 
    150   // Test with only preallocated elements in the set.
    151   VIXL_STATIC_ASSERT(kNPreallocatedElements >= 2);
    152   set.insert(Obj(2718, 0));
    153   set.erase(Obj(2718, 0));
    154   VIXL_CHECK(set.empty() && (set.size() == 0));
    155   set.insert(Obj(2718, 0));
    156   VIXL_CHECK(set.size() == 1);
    157   set.insert(Obj(2718, 1));
    158   VIXL_CHECK(set.size() == 2);
    159   set.erase(Obj(2718, 0));
    160   VIXL_CHECK(set.size() == 1);
    161 
    162   // Test with more elements.
    163   for (unsigned i = 0; i < 100 * kNPreallocatedElements; i++) {
    164     set.insert(Obj(i * i, i % 30));
    165     set.insert(Obj(i, -1));
    166   }
    167   size_t max_size = set.size();
    168   set.erase(Obj(100, -1));
    169   VIXL_CHECK(set.size() == max_size - 1);
    170   for (size_t i = 2; i <= max_size; i++) {
    171     set.erase(set.min_element());
    172     VIXL_CHECK(set.size() == max_size - i);
    173   }
    174 
    175   VIXL_CHECK(set.empty() && (set.size() == 0));
    176 }
    177 
    178 
    179 TEST(min) {
    180   TestSet set;
    181   VIXL_CHECK(set.empty() && (set.size() == 0));
    182 
    183   // Test with only preallocated elements in the set.
    184   VIXL_STATIC_ASSERT(kNPreallocatedElements >= 4);
    185   set.insert(Obj(-1, -1));
    186   set.insert(Obj(-1, 0));
    187   set.insert(Obj(0, 0));
    188   set.insert(Obj(1, 0));
    189   VIXL_CHECK(set.min_element() == Obj(-1, -1));
    190   VIXL_CHECK(set.min_element_key() == -1);
    191   VIXL_CHECK(set.min_element().key_ == set.min_element_key());
    192 
    193   // Test with more elements.
    194   set.clear();
    195   int max_index = 100 * kNPreallocatedElements;
    196   for (int i = 0; i <= max_index; i++) {
    197     // Insert elements out of order.
    198     int sign = ((i % 2) == 0) ? -1 : 1;
    199     set.insert(Obj(sign * i, i));
    200   }
    201   VIXL_CHECK(set.min_element() == Obj(-max_index, max_index));
    202   VIXL_CHECK(set.min_element().key_ == set.min_element_key());
    203 
    204   set.erase(Obj(0, 0));
    205   VIXL_CHECK(set.min_element() == Obj(-max_index, max_index));
    206   set.erase(set.min_element());
    207   VIXL_CHECK(set.min_element() == Obj(-(max_index - 2), max_index - 2));
    208 
    209   set.clear();
    210   VIXL_CHECK(set.empty() && (set.size() == 0));
    211 }
    212 
    213 
    214 TEST(iterator) {
    215   TestSet set;
    216   VIXL_CHECK(set.empty() && (set.size() == 0));
    217 
    218   // Test with only preallocated elements in the set.
    219   for (unsigned i = 0; i < kNPreallocatedElements; i++) {
    220     set.insert(Obj(i, i));
    221   }
    222 
    223   size_t size = 0;
    224   for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
    225     size++;
    226   }
    227   VIXL_CHECK(size == set.size());
    228 
    229   // Test with more elements.
    230   for (unsigned i = kNPreallocatedElements;
    231        i < 4 * kNPreallocatedElements;
    232        i++) {
    233     set.insert(Obj(i, i));
    234   }
    235 
    236   size = 0;
    237   for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
    238     size++;
    239   }
    240   VIXL_CHECK(size == set.size());
    241 
    242   // Test after an element has been deleted.
    243   size = 0;
    244   set.erase(Obj(0, 0));
    245   for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
    246     size++;
    247   }
    248   VIXL_CHECK(size == set.size());
    249 }
    250 
    251 }  // namespace vixl
    252