1 //==========-- ImmutableGraph.h - A fast DAG implementation ---------=========//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 /// The advantages to this implementation are two-fold:
16 ///    implemented as a bit vector, wherein each bit corresponds to one edge in
17 ///    the edge array. This implies a lower bound of 64x spatial improvement
23 //===----------------------------------------------------------------------===//
47   class Edge {
62     const Edge *Edges;
68     const Edge *edges_begin() const { return Edges; }  in edges_begin()
73     const Edge *edges_end() const { return (this + 1)->Edges; }  in edges_end()
74     ArrayRef<Edge> edges() const {  in edges()
80   ImmutableGraph(std::unique_ptr<Node[]> Nodes, std::unique_ptr<Edge[]> Edges,  in ImmutableGraph()
94   ArrayRef<Edge> edges() const { return ArrayRef(Edges.get(), EdgesSize); }  in edges()
95   const Edge *edges_begin() const { return edges().begin(); }  in edges_begin()
96   const Edge *edges_end() const { return edges().end(); }  in edges_end()
105   // Edge E must belong to this ImmutableGraph.
106   size_type getEdgeIndex(const Edge &E) const {  in getEdgeIndex()
140       assert(&this->G == &RHS.G);
146       assert(&this->G == &RHS.G);
152       assert(&this->G == &RHS.G);
168         assert(Current != -1);  in advance()
185         assert(Current != -1);
189         assert(&this->Set == &other.Set);
190         return this->Current == other.Current;
196     iterator end() const { return iterator{*this, -1}; }  in end()
206     bool insert(const Edge &E) {  in insert()
212     void erase(const Edge &E) {  in erase()
216     bool contains(const Edge &E) const {  in contains()
228       assert(&this->G == &RHS.G);
234       assert(&this->G == &RHS.G);
240       assert(&this->G == &RHS.G);
256         assert(Current != -1);  in advance()
272       Edge *operator*() const {
273         assert(Current != -1);
277         assert(&this->Set == &other.Set);
278         return this->Current == other.Current;
284     iterator end() const { return iterator{*this, -1}; }  in end()
289   std::unique_ptr<Edge[]> Edges;
306   using Edge = typename GraphT::Edge;  variable
334     auto EdgeArray = std::make_unique<Edge[]>(EdgeSize);  in get()
357     size_type NewVertexSize = G.nodes_size() - TrimNodes.count();  in trim()
358     size_type NewEdgeSize = G.edges_size() - TrimEdges.count();  in trim()
361     auto NewEdgeArray = std::make_unique<Edge[]>(NewEdgeSize);  in trim()
380       for (const Edge &E : N.edges()) {  in trim()
408   using EdgeRef = typename GraphT::Edge const &;
412       mapped_iterator<typename GraphT::Edge const *, decltype(&edge_dest)>;
414   static NodeRef getEntryNode(GraphT *G) { return G->nodes_begin(); }
416     return {N->edges_begin(), &edge_dest};
419     return {N->edges_end(), &edge_dest};
426     return {G->nodes_begin(), &getNode};
429     return {G->nodes_end(), &getNode};
432   using ChildEdgeIteratorType = typename GraphT::Edge const *;
435     return N->edges_begin();
438     return N->edges_end();
440   static typename GraphT::size_type size(GraphT *G) { return G->nodes_size(); }