unittests/Support/ReverseIterationTest.cpp

   1 //===- llvm/unittest/Support/ReverseIterationTest.cpp ---------------------===//
   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 // Reverse Iteration unit tests.
  10 //
  11 //===---------------------------------------------------------------------===//
  12
  13 #include "llvm/Support/ReverseIteration.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/ADT/DenseMapInfo.h"
  16 #include "gtest/gtest.h"
  17
  18 using namespace llvm;
  19
  20 TEST(ReverseIterationTest, DenseMapTest1) {
  21   static_assert(detail::IsPointerLike<int *>::value,
  22                 "int * is pointer-like");
  23   static_assert(detail::IsPointerLike<uintptr_t>::value,
  24                 "uintptr_t is pointer-like");
  25   static_assert(!detail::IsPointerLike<int>::value,
  26                 "int is not pointer-like");
  27   static_assert(detail::IsPointerLike<void *>::value,
  28                 "void * is pointer-like");
  29   struct IncompleteType;
  30   static_assert(detail::IsPointerLike<IncompleteType *>::value,
  31                 "incomplete * is pointer-like");
  32
  33   // For a DenseMap with non-pointer-like keys, forward iteration equals
  34   // reverse iteration.
  35   DenseMap<int, int> Map;
  36   int Keys[] = { 1, 2, 3, 4 };
  37
  38   // Insert keys into the DenseMap.
  39   for (auto Key: Keys)
  40     Map[Key] = 0;
  41
  42   // Note: This is the observed order of keys in the DenseMap.
  43   // If there is any change in the behavior of the DenseMap, this order
  44   // would need to be adjusted accordingly.
  45   int IterKeys[] = { 2, 4, 1, 3 };
  46
  47   // Check that the DenseMap is iterated in the expected order.
  48   for (const auto &Tuple : zip(Map, IterKeys))
  49     ASSERT_EQ(std::get<0>(Tuple).first, std::get<1>(Tuple));
  50
  51   // Check operator++ (post-increment).
  52   int i = 0;
  53   for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i)
  54     ASSERT_EQ(iter->first, IterKeys[i]);
  55 }
  56
  57 // Define a pointer-like int.
  58 struct PtrLikeInt { int value; };
  59
  60 namespace llvm {
  61
  62 template<> struct DenseMapInfo<PtrLikeInt *> {
  63   static PtrLikeInt *getEmptyKey() {
  64     static PtrLikeInt EmptyKey;
  65     return &EmptyKey;
  66   }
  67
  68   static PtrLikeInt *getTombstoneKey() {
  69     static PtrLikeInt TombstoneKey;
  70     return &TombstoneKey;
  71   }
  72
  73   static int getHashValue(const PtrLikeInt *P) {
  74     return P->value;
  75   }
  76
  77   static bool isEqual(const PtrLikeInt *LHS, const PtrLikeInt *RHS) {
  78     return LHS == RHS;
  79   }
  80 };
  81
  82 } // end namespace llvm
  83
  84 TEST(ReverseIterationTest, DenseMapTest2) {
  85   static_assert(detail::IsPointerLike<PtrLikeInt *>::value,
  86                 "PtrLikeInt * is pointer-like");
  87
  88   PtrLikeInt a = {4}, b = {8}, c = {12}, d = {16};
  89   PtrLikeInt *Keys[] = { &a, &b, &c, &d };
  90
  91   // Insert keys into the DenseMap.
  92   DenseMap<PtrLikeInt *, int> Map;
  93   for (auto *Key : Keys)
  94     Map[Key] = Key->value;
  95
  96   // Note: If there is any change in the behavior of the DenseMap,
  97   // the observed order of keys would need to be adjusted accordingly.
  98   if (shouldReverseIterate<PtrLikeInt *>())
  99     std::reverse(&Keys[0], &Keys[4]);
 100
 101   // Check that the DenseMap is iterated in the expected order.
 102   for (const auto &Tuple : zip(Map, Keys))
 103     ASSERT_EQ(std::get<0>(Tuple).second, std::get<1>(Tuple)->value);
 104
 105   // Check operator++ (post-increment).
 106   int i = 0;
 107   for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i)
 108     ASSERT_EQ(iter->second, Keys[i]->value);
 109 }