test/test-invalset.cc

// Copyright 2014, ARM Limited
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
//   * Redistributions of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//   * Redistributions in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//   * Neither the name of ARM Limited nor the names of its contributors may be
//     used to endorse or promote products derived from this software without
//     specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "test-runner.h"

#include "vixl/invalset.h"

namespace vixl {

// This file contains tests for the `InvalSet` and `InvalSetIterator` classes.

#define TEST(name)  TEST_(INVALSET_##name)

typedef ptrdiff_t KeyType;
typedef ptrdiff_t ValType;

// We test with an object for which the key and the value are distinct.
class Obj {
 public:
  Obj() {}
  Obj(KeyType key, ValType val) : key_(key), val_(val) {}
  KeyType key_;
  ValType val_;

  bool operator==(const Obj& other) const {
    return (key_ == other.key_) && (val_ == other.val_);
  }
  bool operator<(const Obj& other) const {
    return (key_ < other.key_) ||
        ((key_ == other.key_) && (val_ < other.val_));
  }
  bool operator<=(const Obj& other) const {
    return (key_ <= other.key_) ||
        ((key_ == other.key_) && (val_ <= other.val_));
  }
  bool operator>(const Obj& other) const {
    return (key_ > other.key_) ||
        ((key_ == other.key_) && (val_ > other.val_));
  }
};

static const unsigned kNPreallocatedElements = 8;
static const KeyType kInvalidKey = PTRDIFF_MAX;
static const size_t kReclaimFrom = 1000;
static const unsigned kReclaimFactor = 10;

typedef InvalSet<Obj,
                 kNPreallocatedElements,
                 KeyType,
                 kInvalidKey,
                 kReclaimFrom,
                 kReclaimFactor> TestSet;

template<>
inline KeyType InvalSet<Obj,
                        kNPreallocatedElements,
                        KeyType,
                        kInvalidKey,
                        kReclaimFrom,
                        kReclaimFactor>::GetKey(const Obj& obj) {
  return obj.key_;
}
template<>
inline void InvalSet<Obj,
                     kNPreallocatedElements,
                     KeyType,
                     kInvalidKey,
                     kReclaimFrom,
                     kReclaimFactor>::SetKey(Obj* obj, KeyType key) {
  obj->key_ = key;
}


TEST(basic_test) {
  TestSet set;
  VIXL_CHECK(set.empty() && (set.size() == 0));

  for (unsigned i = 0; i < kNPreallocatedElements; i++) {
    set.insert(Obj(i, i));
  }
  VIXL_CHECK(set.size() == kNPreallocatedElements);

  set.insert(Obj(-123, 456));
  set.insert(Obj(2718, 2871828));
  VIXL_CHECK(set.size() == kNPreallocatedElements + 2);
  VIXL_CHECK(set.GetMinElement() == Obj(-123, 456));

  set.erase(Obj(-123, 456));
  VIXL_CHECK(set.GetMinElementKey() == 0);

  set.clear();
  VIXL_CHECK(set.empty() && (set.size() == 0));
}


TEST(valid_element) {
  VIXL_CHECK(TestSet::IsValid(Obj(0, 0)));
  VIXL_CHECK(TestSet::IsValid(Obj(-1, 0)));
  VIXL_CHECK(TestSet::IsValid(Obj(kInvalidKey - 1, 0)));
  VIXL_CHECK(!TestSet::IsValid(Obj(kInvalidKey, 0)));
}


TEST(insert) {
  TestSet set;
  VIXL_CHECK(set.empty() && (set.size() == 0));

  for (unsigned i = 0; i < kNPreallocatedElements; i++) {
    set.insert(Obj(i, i));
  }
  VIXL_CHECK(set.size() == kNPreallocatedElements);
  set.insert(Obj(-123, 1));
  VIXL_CHECK(set.size() == kNPreallocatedElements + 1);
  set.insert(Obj(-123, 2));
  set.insert(Obj(-123, 3));
  VIXL_CHECK(set.size() == kNPreallocatedElements + 3);

  set.clear();
  VIXL_CHECK(set.empty() && (set.size() == 0));
}


TEST(erase) {
  TestSet set;
  VIXL_CHECK(set.empty() && (set.size() == 0));

  // Test with only preallocated elements in the set.
  VIXL_STATIC_ASSERT(kNPreallocatedElements >= 2);
  set.insert(Obj(2718, 0));
  set.erase(Obj(2718, 0));
  VIXL_CHECK(set.empty() && (set.size() == 0));
  set.insert(Obj(2718, 0));
  VIXL_CHECK(set.size() == 1);
  set.insert(Obj(2718, 1));
  VIXL_CHECK(set.size() == 2);
  set.erase(Obj(2718, 0));
  VIXL_CHECK(set.size() == 1);

  // Test with more elements.
  for (unsigned i = 0; i < 100 * kNPreallocatedElements; i++) {
    set.insert(Obj(i * i, i % 30));
    set.insert(Obj(i, -1));
  }
  size_t max_size = set.size();
  set.erase(Obj(100, -1));
  VIXL_CHECK(set.size() == max_size - 1);
  for (size_t i = 2; i <= max_size; i++) {
    set.erase(set.GetMinElement());
    VIXL_CHECK(set.size() == max_size - i);
  }

  VIXL_CHECK(set.empty() && (set.size() == 0));
}


TEST(min) {
  TestSet set;
  VIXL_CHECK(set.empty() && (set.size() == 0));

  // Test with only preallocated elements in the set.
  VIXL_STATIC_ASSERT(kNPreallocatedElements >= 4);
  set.insert(Obj(-1, -1));
  set.insert(Obj(-1, 0));
  set.insert(Obj(0, 0));
  set.insert(Obj(1, 0));
  VIXL_CHECK(set.GetMinElement() == Obj(-1, -1));
  VIXL_CHECK(set.GetMinElementKey() == -1);
  VIXL_CHECK(set.GetMinElement().key_ == set.GetMinElementKey());

  // Test with more elements.
  set.clear();
  int max_index = 100 * kNPreallocatedElements;
  for (int i = 0; i <= max_index; i++) {
    // Insert elements out of order.
    int sign = ((i % 2) == 0) ? -1 : 1;
    set.insert(Obj(sign * i, i));
  }
  VIXL_CHECK(set.GetMinElement() == Obj(-max_index, max_index));
  VIXL_CHECK(set.GetMinElement().key_ == set.GetMinElementKey());

  set.erase(Obj(0, 0));
  VIXL_CHECK(set.GetMinElement() == Obj(-max_index, max_index));
  set.erase(set.GetMinElement());
  VIXL_CHECK(set.GetMinElement() == Obj(-(max_index - 2), max_index - 2));

  set.clear();
  VIXL_CHECK(set.empty() && (set.size() == 0));
}


TEST(iterator) {
  TestSet set;
  VIXL_CHECK(set.empty() && (set.size() == 0));

  // Ensure that set.begin() == set.end() for the empty set.
  VIXL_CHECK(set.begin() == set.end());

  // Test with only preallocated elements in the set.
  size_t expected_total = 0;
  for (unsigned i = 0; i < kNPreallocatedElements; i++) {
    set.insert(Obj(i, i));
    expected_total += i;
  }

  size_t size = 0;
  size_t total = 0;
  for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) {
    total += it->val_;
    size++;
  }
  VIXL_CHECK(size == set.size());
  VIXL_CHECK(total == expected_total);

  // Test with more elements.
  for (unsigned i = kNPreallocatedElements;
       i < 4 * kNPreallocatedElements;
       i++) {
    set.insert(Obj(i, i));
    expected_total += i;
  }

  size = 0;
  total = 0;
  for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) {
    total += it->val_;
    size++;
  }
  VIXL_CHECK(size == set.size());
  VIXL_CHECK(total == expected_total);

  // Test after elements have been deleted.
  // - Select an interesting list of elements to erase.
  std::vector<Obj> to_erase;
  unsigned step = 0;
  for (unsigned i = 0; i < set.size(); i += step, step++) {
    to_erase.push_back(Obj(i, i));
  }
  to_erase.push_back(Obj(set.size() - 1, set.size() - 1));  // The last element.
  to_erase.push_back(Obj(set.size(), set.size()));          // Not in the set.

  // - Erase one at a time, retesting after each one.
  while (!to_erase.empty()) {
    size_t erased = set.erase(to_erase.back());
    if (erased > 0) {
      VIXL_CHECK(erased == 1);
      expected_total -= to_erase.back().val_;
    } else {
    }
    to_erase.pop_back();

    size = 0;
    total = 0;
    for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) {
      total += it->val_;
      size++;
    }
    VIXL_CHECK(size == set.size());
    VIXL_CHECK(total == expected_total);
  }
}


#if __cplusplus >= 201103L
TEST(iterator_cxx11) {
  TestSet set;
  VIXL_CHECK(set.empty() && (set.size() == 0));

  // Test with only preallocated elements in the set.
  size_t expected_total = 0;
  for (unsigned i = 0; i < kNPreallocatedElements; i++) {
    set.insert(Obj(i, i));
    expected_total += i;
  }

  size_t size = 0;
  size_t total = 0;
  for (auto object : set) {
    total += object.val_;
    size++;
  }
  VIXL_CHECK(size == set.size());
  VIXL_CHECK(total == expected_total);

  // Test with more elements.
  for (unsigned i = kNPreallocatedElements;
       i < 4 * kNPreallocatedElements;
       i++) {
    set.insert(Obj(i, i));
    expected_total += i;
  }

  size = 0;
  total = 0;
  for (auto object : set) {
    total += object.val_;
    size++;
  }
  VIXL_CHECK(size == set.size());
  VIXL_CHECK(total == expected_total);

  // Test after elements have been deleted.
  // - Select an interesting list of elements to erase.
  std::vector<Obj> to_erase;
  unsigned step = 0;
  for (unsigned i = 0; i < set.size(); i += step, step++) {
    to_erase.push_back(Obj(i, i));
  }
  to_erase.push_back(Obj(set.size() - 1, set.size() - 1));  // The last element.
  to_erase.push_back(Obj(set.size(), set.size()));          // Not in the set.

  // - Erase one at a time, retesting after each one.
  while (!to_erase.empty()) {
    size_t erased = set.erase(to_erase.back());
    if (erased > 0) {
      VIXL_CHECK(erased == 1);
      expected_total -= to_erase.back().val_;
    } else {
    }
    to_erase.pop_back();

    size = 0;
    total = 0;
    for (auto object : set) {
      total += object.val_;
      size++;
    }
    VIXL_CHECK(size == set.size());
    VIXL_CHECK(total == expected_total);
  }
}
#endif


TEST(stl_forward_iterator) {
  {
    TestSet::iterator default_it;               // Default-constructible.
    TestSet::iterator copy_it(default_it);      // Copy-constructible.
    copy_it = default_it;                       // Copy-assignable.
  }                                             // Destructible.

  TestSet set1;
  VIXL_CHECK(set1.empty() && (set1.size() == 0));

  TestSet set2;
  VIXL_CHECK(set2.empty() && (set2.size() == 0));

  // Test with only preallocated elements in the set.
  for (unsigned i = 0; i < kNPreallocatedElements; i++) {
    set1.insert(Obj(i, 1));
    set2.insert(Obj(i, 2));
  }

  TestSet::iterator it1_a = set1.begin();
  TestSet::iterator it1_b = set1.begin();

  // Incrementable (whilst valid).
  it1_a++;
  ++it1_b;

  // Testable for equivalence.
  VIXL_CHECK(it1_a == it1_b);
  VIXL_CHECK(set1.begin() != set1.end());
  VIXL_CHECK(set2.begin() != set2.end());
  VIXL_CHECK(set1.begin() != set2.begin());
  VIXL_CHECK(set1.end() != set2.end());

  // Dereferencable.
  VIXL_CHECK((*it1_a++).key_ == 1);
  VIXL_CHECK(((*it1_a).key_ == 2) && ((*it1_a).val_ == 1));
  *it1_b = Obj(42, 1);
  VIXL_CHECK((it1_b->key_ == 42) && (it1_b->val_ == 1));

#if __cplusplus >= 201103L
  // Swappable.
  std::swap(it1_a, it1_b);
  VIXL_CHECK(it1_a->key_ == 42);
  VIXL_CHECK(it1_b->key_ == 2);
#endif
}


}  // namespace vixl