Graph.h Source File (original) (raw)

13#ifndef LLVM_XRAY_GRAPH_H

14#define LLVM_XRAY_GRAPH_H

16#include <initializer_list>

17#include <stdint.h>

18#include <type_traits>

19#include

71template <typename VertexAttribute, typename EdgeAttribute,

72 typename VI = int32_t>

74public:

90private:

100

101

103

104

105

107

108private:

109

110

111 EdgeMapT Edges;

112

113

114 VertexMapT Vertices;

115

116

117 NeighborLookupT InNeighbors;

118

119

120 NeighborLookupT OutNeighbors;

121

122

123

124

125

126 template <bool IsConst, bool IsOut,

128 typename T =

129 std::conditional_t<IsConst, const EdgeValueType, EdgeValueType>>

130 class NeighborEdgeIteratorT

132 NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,

133 typename std::iterator_traits::iterator_category, T> {

134 using InternalEdgeMapT =

135 std::conditional_t<IsConst, const EdgeMapT, EdgeMapT>;

136

137 friend class NeighborEdgeIteratorT<false, IsOut, BaseIt, EdgeValueType>;

138 friend class NeighborEdgeIteratorT<true, IsOut, BaseIt,

140

141 InternalEdgeMapT *MP;

143

144 public:

145 template <bool IsConstDest,

146 typename = std::enable_if_t<IsConstDest && !IsConst>>

147 operator NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,

149 return NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,

151 }

152

153 NeighborEdgeIteratorT() = default;

154 NeighborEdgeIteratorT(BaseIt _I, InternalEdgeMapT *_MP,

157 NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,

158 typename std::iterator_traits::iterator_category, T>(_I),

159 MP(_MP), SI(_SI) {}

160

162 if (!IsOut)

163 return *(MP->find({*(this->I), SI}));

164 else

165 return *(MP->find({SI, *(this->I)}));

166 }

167 };

168

169public:

170

171

172

173

175

176

177

178

180

181

182

183

184

186

187

188

189

191

192

193

194

195

196

198 public:

199 using iterator = NeighborEdgeIteratorT<isConst, isOut>;

201 using GraphT = std::conditional_t<isConst, const Graph, Graph>;

203 std::conditional_t<isConst, const EdgeMapT, EdgeMapT>;

204

205 private:

208 const NeighborLookupT &NL;

209

210 public:

212 auto It = NL.find(A);

213 if (It == NL.end())

215 return iterator(It->second.begin(), &M, A);

216 }

217

219 auto It = NL.find(A);

220 if (It == NL.end())

223 }

224

226

228 auto It = NL.find(A);

229 if (It == NL.end())

231 return iterator(It->second.end(), &M, A);

232 }

234 auto It = NL.find(A);

235 if (It == NL.end())

238 }

239

241

243 auto I = NL.find(A);

244 if (I == NL.end())

245 return 0;

246 else

247 return I->second.size();

248 }

249

250 bool empty() const { return NL.count(A) == 0; };

251

253 : M(G.Edges), A(A), NL(isOut ? G.OutNeighbors : G.InNeighbors) {}

254 };

255

256

257

258

259

261

262

263

264

266

267

268

269

270

271

273 public:

275 std::conditional_t<isConst, ConstVertexIterator, VertexIterator>;

277 using GraphT = std::conditional_t<isConst, const Graph, Graph>;

278

279 private:

281

282 public:

290 bool empty() const { return G.Vertices.empty(); }

292 };

293

294

295

296

298

299

300

301

303

304

305

306

307

308

310 public:

312 std::conditional_t<isConst, ConstEdgeIterator, EdgeIterator>;

314 using GraphT = std::conditional_t<isConst, const Graph, Graph>;

315

316 private:

318

319 public:

327 bool empty() const { return G.Edges.empty(); }

329 };

330

331public:

332

333

334

335

336

337

338

340 Edges.clear();

341 Vertices.clear();

342 InNeighbors.clear();

343 OutNeighbors.clear();

344 }

345

346

347

349

351

352

353

355

357

358

359

363

367

368

369

373

377

378

379

381

382

383

384

386 Vertices.try_emplace(I.first);

387 Vertices.try_emplace(I.second);

388 InNeighbors[I.second].insert(I.first);

389 OutNeighbors[I.first].insert(I.second);

390 return Edges[I];

391 }

392

393

395 auto It = Vertices.find(I);

396 if (It == Vertices.end())

398 "Vertex Identifier Does Not Exist",

399 std::make_error_code(std::errc::invalid_argument));

400 return It->second;

401 }

402

404 auto It = Vertices.find(I);

405 if (It == Vertices.end())

407 "Vertex Identifier Does Not Exist",

408 std::make_error_code(std::errc::invalid_argument));

409 return It->second;

410 }

411

412

414 auto It = Edges.find(I);

415 if (It == Edges.end())

417 "Edge Identifier Does Not Exist",

418 std::make_error_code(std::errc::invalid_argument));

419 return It->second;

420 }

421

423 auto It = Edges.find(I);

424 if (It == Edges.end())

426 "Edge Identifier Does Not Exist",

427 std::make_error_code(std::errc::invalid_argument));

428 return It->second;

429 }

430

431

432

434 return Vertices.count(I);

435 }

436

437

438

440

441

442

443 std::pair<VertexIterator, bool>

444 insert(const std::pair<VertexIdentifier, VertexAttribute> &Val) {

445 return Vertices.insert(Val);

446 }

447

448 std::pair<VertexIterator, bool>

449 insert(std::pair<VertexIdentifier, VertexAttribute> &&Val) {

450 return Vertices.insert(std::move(Val));

451 }

452

453

454

455

456 std::pair<EdgeIterator, bool>

457 insert(const std::pair<EdgeIdentifier, EdgeAttribute> &Val) {

458 const auto &p = Edges.insert(Val);

459 if (p.second) {

460 const auto &EI = Val.first;

461 Vertices.FindAndConstruct(EI.first);

462 Vertices.FindAndConstruct(EI.second);

463 InNeighbors[EI.second].insert(EI.first);

464 OutNeighbors[EI.first].insert(EI.second);

465 };

466

467 return p;

468 }

469

470

471

472

473 std::pair<EdgeIterator, bool>

474 insert(std::pair<EdgeIdentifier, EdgeAttribute> &&Val) {

475 auto EI = Val.first;

476 const auto &p = Edges.insert(std::move(Val));

477 if (p.second) {

478 Vertices.try_emplace(EI.first);

479 Vertices.try_emplace(EI.second);

480 InNeighbors[EI.second].insert(EI.first);

481 OutNeighbors[EI.first].insert(EI.second);

482 };

483

484 return p;

485 }

486};

487}

488

489#endif

This file defines the DenseMap class.

This file defines the DenseSet and SmallDenseSet classes.

StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator

Implements a dense probed hash-table based set.

Tagged union holding either a T or a Error.

DenseSetIterator< true > const_iterator

CRTP base class for adapting an iterator to a different type.

ReferenceT operator*() const

A class for ranging over all the edges in the graph.

Definition Graph.h:309

EdgeView(GraphT &_G)

Definition Graph.h:328

const_iterator cend() const

Definition Graph.h:323

const_iterator end() const

Definition Graph.h:325

bool empty() const

Definition Graph.h:327

size_type size() const

Definition Graph.h:326

ConstEdgeIterator const_iterator

Definition Graph.h:313

iterator end()

Definition Graph.h:321

std::conditional_t< isConst, const Graph, Graph > GraphT

Definition Graph.h:314

const_iterator cbegin() const

Definition Graph.h:322

iterator begin()

Definition Graph.h:320

std::conditional_t< isConst, ConstEdgeIterator, EdgeIterator > iterator

Definition Graph.h:311

const_iterator begin() const

Definition Graph.h:324

A class for ranging over the incoming edges incident to a vertex.

Definition Graph.h:197

iterator end()

Definition Graph.h:227

NeighborEdgeIteratorT< isConst, isOut > iterator

Definition Graph.h:199

const_iterator end() const

Definition Graph.h:240

bool empty() const

Definition Graph.h:250

const_iterator cbegin() const

Definition Graph.h:218

std::conditional_t< isConst, const EdgeMapT, EdgeMapT > InternalEdgeMapT

Definition Graph.h:202

std::conditional_t< isConst, const Graph, Graph > GraphT

Definition Graph.h:201

const_iterator begin() const

Definition Graph.h:225

iterator begin()

Definition Graph.h:211

NeighborEdgeIteratorT< true, isOut > const_iterator

Definition Graph.h:200

size_type size() const

Definition Graph.h:242

const_iterator cend() const

Definition Graph.h:233

InOutEdgeView(GraphT &G, VertexIdentifier A)

Definition Graph.h:252

A class for ranging over the vertices in the graph.

Definition Graph.h:272

std::conditional_t< isConst, ConstVertexIterator, VertexIterator > iterator

Definition Graph.h:274

ConstVertexIterator const_iterator

Definition Graph.h:276

const_iterator end() const

Definition Graph.h:288

bool empty() const

Definition Graph.h:290

const_iterator begin() const

Definition Graph.h:287

iterator end()

Definition Graph.h:284

const_iterator cend() const

Definition Graph.h:286

VertexView(GraphT &_G)

Definition Graph.h:291

std::conditional_t< isConst, const Graph, Graph > GraphT

Definition Graph.h:277

size_type size() const

Definition Graph.h:289

const_iterator cbegin() const

Definition Graph.h:285

iterator begin()

Definition Graph.h:283

A Graph object represents a Directed Graph and is used in XRay to compute and store function call gra...

Definition Graph.h:73

std::pair< EdgeIterator, bool > insert(std::pair< EdgeIdentifier, EdgeAttribute > &&Val)

Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.

Definition Graph.h:474

std::pair< EdgeIterator, bool > insert(const std::pair< EdgeIdentifier, EdgeAttribute > &Val)

Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.

Definition Graph.h:457

EdgeAttribute & operator[](const EdgeIdentifier &I)

Looks up the edge with identifier I, if it does not exist it default constructs it,...

Definition Graph.h:385

std::pair< VertexIterator, bool > insert(std::pair< VertexIdentifier, VertexAttribute > &&Val)

Definition Graph.h:449

VertexView< false > vertices()

Returns a view object allowing iteration over the vertices of the graph.

Definition Graph.h:348

NeighborEdgeIteratorT< false, true > OutEdgeIterator

An iterator type for iterating through the set of edges leaving a vertex.

Definition Graph.h:190

InOutEdgeView< true, true > outEdges(const VertexIdentifier I) const

Definition Graph.h:364

size_type count(const EdgeIdentifier &I) const

Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.

Definition Graph.h:439

void clear()

Empty the Graph.

Definition Graph.h:339

EdgeView< true > edges() const

Definition Graph.h:356

size_type count(const VertexIdentifier &I) const

Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.

Definition Graph.h:433

NeighborEdgeIteratorT< true, false > ConstInEdgeIterator

A const iterator type for iterating through the set of edges entering a vertex.

Definition Graph.h:174

std::size_t size_type

Definition Graph.h:88

EdgeView< false > edges()

Returns a view object allowing iteration over the edges of the graph.

Definition Graph.h:354

NeighborEdgeIteratorT< true, true > ConstOutEdgeIterator

A const iterator type for iterating through the set of edges entering a vertex.

Definition Graph.h:185

NeighborEdgeIteratorT< false, false > InEdgeIterator

An iterator type for iterating through the set of edges leaving a vertex.

Definition Graph.h:179

typename VertexMapT::iterator VertexIterator

An iterator type for iterating through the whole vertex set of the graph.

Definition Graph.h:265

InOutEdgeView< false, false > inEdges(const VertexIdentifier I)

Returns a view object allowing iteration over the edges which point to a vertex I.

Definition Graph.h:370

typename EdgeMapT::const_iterator ConstEdgeIterator

A const iterator for iterating through the entire edge set of the graph.

Definition Graph.h:297

std::pair< VertexIterator, bool > insert(const std::pair< VertexIdentifier, VertexAttribute > &Val)

Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.

Definition Graph.h:444

detail::DenseMapPair< VertexIdentifier, VertexAttribute > VertexValueType

This type is the value_type of all iterators which range over vertices, Determined by the Vertices De...

Definition Graph.h:81

Expected< const VertexAttribute & > at(const VertexIdentifier &I) const

Definition Graph.h:403

VI VertexIdentifier

These objects are used to name edges and vertices in the graph.

Definition Graph.h:76

Expected< VertexAttribute & > at(const VertexIdentifier &I)

Looks up a vertex with Identifier I, or an error if it does not exist.

Definition Graph.h:394

VertexAttribute & operator[](const VertexIdentifier &I)

Looks up the vertex with identifier I, if it does not exist it default constructs it.

Definition Graph.h:380

VertexView< true > vertices() const

Definition Graph.h:350

InOutEdgeView< true, false > inEdges(const VertexIdentifier I) const

Definition Graph.h:374

typename VertexMapT::const_iterator ConstVertexIterator

A const iterator type for iterating through the whole vertex set of the graph.

Definition Graph.h:260

typename EdgeMapT::iterator EdgeIterator

An iterator for iterating through the entire edge set of the graph.

Definition Graph.h:302

std::pair< VI, VI > EdgeIdentifier

Definition Graph.h:77

detail::DenseMapPair< EdgeIdentifier, EdgeAttribute > EdgeValueType

This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap...

Definition Graph.h:86

Expected< const EdgeAttribute & > at(const EdgeIdentifier &I) const

Definition Graph.h:422

Expected< EdgeAttribute & > at(const EdgeIdentifier &I)

Looks up an edge with Identifier I, or an error if it does not exist.

Definition Graph.h:413

InOutEdgeView< false, true > outEdges(const VertexIdentifier I)

Returns a view object allowing iteration over the edges which start at a vertex I.

Definition Graph.h:360

Error make_error(ArgTs &&... Args)

Make a Error instance representing failure using the given error info type.