1 //=== llvm/unittest/ADT/DepthFirstIteratorTest.cpp - DFS iterator tests ---===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "TestGraph.h"
11 #include "llvm/ADT/DepthFirstIterator.h"
12 #include "gtest/gtest.h"
13 
14 using namespace llvm;
15 
16 namespace llvm {
17 
18 template <typename T> struct CountedSet {
19   typedef typename SmallPtrSet<T, 4>::iterator iterator;
20 
21   SmallPtrSet<T, 4> S;
22   int InsertVisited = 0;
23 
24   std::pair<iterator, bool> insert(const T &Item) {
25     InsertVisited++;
26     return S.insert(Item);
27   }
28 
29   size_t count(const T &Item) const { return S.count(Item); }
30 };
31 
32 template <typename T> class df_iterator_storage<CountedSet<T>, true> {
33 public:
34   df_iterator_storage(CountedSet<T> &VSet) : Visited(VSet) {}
35 
36   CountedSet<T> &Visited;
37 };
38 
39 TEST(DepthFirstIteratorTest, ActuallyUpdateIterator) {
40   typedef CountedSet<Graph<3>::NodeType *> StorageT;
41   typedef df_iterator<Graph<3>, StorageT, true> DFIter;
42 
43   Graph<3> G;
44   G.AddEdge(0, 1);
45   G.AddEdge(0, 2);
46   StorageT S;
47   for (auto N : make_range(DFIter::begin(G, S), DFIter::end(G, S)))
48     (void)N;
49 
50   EXPECT_EQ(3, S.InsertVisited);
51 }
52 }
53