DepthFirstIterator.h Source File (original) (raw)

34#ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H

35#define LLVM_ADT_DEPTHFIRSTITERATOR_H

40#include

41#include

42#include <type_traits>

43#include

44#include

46namespace llvm {

50template<class SetType, bool External>

52public:

54};

56template

58public:

63};

69template <typename NodeRef, unsigned SmallSize=8>

75 template

79};

82template <class GraphT,

83 class SetType =

84 df_iterator_default_set<typename GraphTraits::NodeRef>,

85 bool ExtStorage = false, class GT = GraphTraits>

87public:

90 std::conditional_t<ExtStorage, std::input_iterator_tag,

91 std::forward_iterator_tag>;

97private:

98 using NodeRef = typename GT::NodeRef;

99 using ChildItTy = typename GT::ChildIteratorType;

100

101

102

103

104 using StackElement = std::pair<NodeRef, std::optional>;

105

106

107 std::vector VisitStack;

108

110 this->Visited.insert(Node);

111 VisitStack.push_back(StackElement(Node, std::nullopt));

112 }

113

114 inline df_iterator() = default;

115

118 if (this->Visited.insert(Node).second)

119 VisitStack.push_back(StackElement(Node, std::nullopt));

120 }

121

122 inline df_iterator(SetType &S)

123 : df_iterator_storage<SetType, ExtStorage>(S) {

124

125 }

126

127 inline void toNext() {

128 do {

129 NodeRef Node = VisitStack.back().first;

130 std::optional &Opt = VisitStack.back().second;

131

132 if (!Opt)

133 Opt.emplace(GT::child_begin(Node));

134

135

136

137

138 while (*Opt != GT::child_end(Node)) {

139 NodeRef Next = *(*Opt)++;

140

141 if (this->Visited.insert(Next).second) {

142

143 VisitStack.push_back(StackElement(Next, std::nullopt));

144 return;

145 }

146 }

147 this->Visited.completed(Node);

148

149

150 VisitStack.pop_back();

151 } while (!VisitStack.empty());

152 }

153

154public:

155

158 }

160

161

164 }

166

168 return VisitStack == x.VisitStack;

169 }

171

173

174

175

176

177

179

181 toNext();

182 return *this;

183 }

184

185

186

187

188

190 VisitStack.pop_back();

191 if (!VisitStack.empty())

192 toNext();

193 return *this;

194 }

195

198 ++*this;

199 return tmp;

200 }

201

202

203

204

205

207 return this->Visited.contains(Node);

208 }

209

210

211

213

214

215

216 NodeRef getPath(unsigned n) const { return VisitStack[n].first; }

217};

218

219

220

221template

224}

225

226template

229}

230

231

232template

235}

236

237

238template <class T, class SetTy = df_iterator_default_set<typename GraphTraits::NodeRef>>

242};

243

244template <class T, class SetTy>

247}

248

249template <class T, class SetTy>

252}

253

254template <class T, class SetTy>

256 SetTy &S) {

258}

259

260

261template <class T,

262 class SetTy =

263 df_iterator_default_set<typename GraphTraits::NodeRef>,

264 bool External = false>

268};

269

270template

273}

274

275template

278}

279

280

281template

284}

285

286

287template <class T, class SetTy = df_iterator_default_set<typename GraphTraits::NodeRef>>

293};

294

295template <class T, class SetTy>

298}

299

300template <class T, class SetTy>

303}

304

305template <class T, class SetTy>

307 SetTy &S) {

309}

310

311}

312

313#endif

This file defines the little GraphTraits template class that should be specialized by classes that...

This file defines the SmallPtrSet class.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSetIterator< PtrType > iterator

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

df_iterator_storage(const df_iterator_storage &S)

df_iterator_storage(SetType &VSet)

df_iterator & operator++()

static df_iterator begin(const GraphT &G)

NodeRef operator->() const

std::conditional_t< ExtStorage, std::input_iterator_tag, std::forward_iterator_tag > iterator_category

static df_iterator end(const GraphT &G)

const value_type & reference

static df_iterator end(const GraphT &G, SetType &S)

df_iterator & skipChildren()

Skips all children of the current node and traverses to next node.

unsigned getPathLength() const

getPathLength - Return the length of the path from the entry node to the current node,...

bool operator==(const df_iterator &x) const

df_iterator operator++(int)

bool operator!=(const df_iterator &x) const

bool nodeVisited(NodeRef Node) const

NodeRef getPath(unsigned n) const

getPath - Return the n'th node in the path from the entry node to the current node.

static df_iterator begin(const GraphT &G, SetType &S)

reference operator*() const

std::ptrdiff_t difference_type

typename GT::NodeRef value_type

A range adaptor for a pair of iterators.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)

idf_ext_iterator< T, SetTy > idf_ext_end(const T &G, SetTy &S)

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

df_iterator< T > df_begin(const T &G)

idf_ext_iterator< T, SetTy > idf_ext_begin(const T &G, SetTy &S)

iterator_range< idf_iterator< T > > inverse_depth_first(const T &G)

df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)

idf_iterator< T > idf_end(const T &G)

iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)

idf_iterator< T > idf_begin(const T &G)

df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)

df_iterator< T > df_end(const T &G)

iterator_range< df_iterator< T > > depth_first(const T &G)

df_ext_iterator(const df_iterator< T, SetTy, true > &V)

void insert(IterT Begin, IterT End)

typename BaseSet::iterator iterator

std::pair< iterator, bool > insert(NodeRef N)

idf_ext_iterator(const idf_iterator< T, SetTy, true > &V)

idf_ext_iterator(const df_iterator< Inverse< T >, SetTy, true > &V)

idf_iterator(const df_iterator< Inverse< T >, SetTy, External > &V)