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>

56template

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

109 inline df_iterator(NodeRef 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

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

156 static df_iterator begin(const GraphT &G) {

157 return df_iterator(GT::getEntryNode(G));

158 }

159 static df_iterator end(const GraphT &G) { return df_iterator(); }

160

161

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

163 return df_iterator(GT::getEntryNode(G), S);

164 }

165 static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }

166

168 return VisitStack == x.VisitStack;

169 }

170 bool operator!=(const df_iterator &x) const { return !(*this == x); }

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

197 df_iterator tmp = *this;

198 ++*this;

199 return tmp;

200 }

201

202

203

204

205

209

210

211

213

214

215

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

217};

218

219

220

221template

225

226template

230

231

232template

236

237

238template <class T,

239 class SetTy =

240 df_iterator_default_set<typename GraphTraits::NodeRef>>

243 : df_iterator<T, SetTy, true>(V) {}

244};

245

246template <class T, class SetTy>

250

251template <class T, class SetTy>

255

256template <class T, class SetTy>

261

262

263template <class T,

264 class SetTy =

265 df_iterator_default_set<typename GraphTraits::NodeRef>,

266 bool External = false>

267struct idf_iterator : df_iterator<Inverse, SetTy, External> {

269 : df_iterator<Inverse<T>, SetTy, External>(V) {}

270};

271

272template

276

277template

281

282

283template

287

288

289template <class T,

290 class SetTy =

291 df_iterator_default_set<typename GraphTraits::NodeRef>>

298

299template <class T, class SetTy>

303

304template <class T, class SetTy>

308

309template <class T, class SetTy>

314

315}

316

317#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(NodeRef Ptr)

SmallPtrSetIterator< NodeRef > iterator

df_iterator_storage(const df_iterator_storage &S)

Definition DepthFirstIterator.h:60

df_iterator_storage(SetType &VSet)

Definition DepthFirstIterator.h:59

SetType & Visited

Definition DepthFirstIterator.h:62

SetType Visited

Definition DepthFirstIterator.h:53

df_iterator & operator++()

Definition DepthFirstIterator.h:180

static df_iterator begin(const GraphT &G)

Definition DepthFirstIterator.h:156

NodeRef operator->() const

Definition DepthFirstIterator.h:178

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

Definition DepthFirstIterator.h:89

static df_iterator end(const GraphT &G)

Definition DepthFirstIterator.h:159

value_type * pointer

Definition DepthFirstIterator.h:94

const value_type & reference

Definition DepthFirstIterator.h:95

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

Definition DepthFirstIterator.h:165

df_iterator & skipChildren()

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

Definition DepthFirstIterator.h:189

unsigned getPathLength() const

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

Definition DepthFirstIterator.h:212

bool operator==(const df_iterator &x) const

Definition DepthFirstIterator.h:167

df_iterator operator++(int)

Definition DepthFirstIterator.h:196

bool operator!=(const df_iterator &x) const

Definition DepthFirstIterator.h:170

bool nodeVisited(NodeRef Node) const

Definition DepthFirstIterator.h:206

NodeRef getPath(unsigned n) const

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

Definition DepthFirstIterator.h:216

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

Definition DepthFirstIterator.h:162

reference operator*() const

Definition DepthFirstIterator.h:172

std::ptrdiff_t difference_type

Definition DepthFirstIterator.h:93

typename GT::NodeRef value_type

Definition DepthFirstIterator.h:92

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.

NodeAddr< NodeBase * > Node

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)

Definition DepthFirstIterator.h:257

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

Definition DepthFirstIterator.h:305

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

Convenience function for iterating over sub-ranges.

df_iterator< T > df_begin(const T &G)

Definition DepthFirstIterator.h:222

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

Definition DepthFirstIterator.h:300

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

Definition DepthFirstIterator.h:284

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

Definition DepthFirstIterator.h:247

idf_iterator< T > idf_end(const T &G)

Definition DepthFirstIterator.h:278

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

Definition DepthFirstIterator.h:310

FunctionAddr VTableAddr Next

idf_iterator< T > idf_begin(const T &G)

Definition DepthFirstIterator.h:273

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

Definition DepthFirstIterator.h:252

df_iterator< T > df_end(const T &G)

Definition DepthFirstIterator.h:227

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

Definition DepthFirstIterator.h:233

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

Definition DepthFirstIterator.h:242

void completed(NodeRef)

Definition DepthFirstIterator.h:78

void insert(IterT Begin, IterT End)

Definition DepthFirstIterator.h:76

typename BaseSet::iterator iterator

Definition DepthFirstIterator.h:72

SmallPtrSet< NodeRef, SmallSize > BaseSet

Definition DepthFirstIterator.h:71

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

Definition DepthFirstIterator.h:74

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

Definition DepthFirstIterator.h:293

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

Definition DepthFirstIterator.h:295

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

Definition DepthFirstIterator.h:268