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