File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/include/llvm/ADT

usr / src / contrib / llvm-project / llvm / include / llvm / ADT /

📁 ..
📄 APFloat.h(48.83 KB)
📄 APInt.h(74.48 KB)
📄 APSInt.h(11.75 KB)
📄 AllocatorList.h(7.53 KB)
📄 Any.h(5.05 KB)
📄 ArrayRef.h(17.92 KB)
📄 BitVector.h(29.74 KB)
📄 Bitfields.h(11.65 KB)
📄 BitmaskEnum.h(5.53 KB)
📄 BreadthFirstIterator.h(4.82 KB)
📄 CachedHashString.h(5.9 KB)
📄 CoalescingBitVector.h(14.91 KB)
📄 DAGDeltaAlgorithm.h(3.13 KB)
📄 DeltaAlgorithm.h(3.54 KB)
📄 DenseMap.h(43.14 KB)
📄 DenseMapInfo.h(11.4 KB)
📄 DenseSet.h(9.33 KB)
📄 DepthFirstIterator.h(10.37 KB)
📄 DirectedGraph.h(9.56 KB)
📄 EnumeratedArray.h(1.6 KB)
📄 EpochTracker.h(3.2 KB)
📄 EquivalenceClasses.h(10.52 KB)
📄 FloatingPointMode.h(5.62 KB)
📄 FoldingSet.h(30.16 KB)
📄 FunctionExtras.h(14.55 KB)
📄 GraphTraits.h(5.71 KB)
📄 Hashing.h(25.12 KB)
📄 ImmutableList.h(7.57 KB)
📄 ImmutableMap.h(10.84 KB)
📄 ImmutableSet.h(37.52 KB)
📄 IndexedMap.h(2.5 KB)
📄 IntEqClasses.h(2.87 KB)
📄 IntervalMap.h(72.88 KB)
📄 IntrusiveRefCntPtr.h(8.1 KB)
📄 MapVector.h(7.79 KB)
📄 None.h(983 B)
📄 Optional.h(10.82 KB)
📄 PackedVector.h(4.17 KB)
📄 PointerEmbeddedInt.h(4.05 KB)
📄 PointerIntPair.h(8.72 KB)
📄 PointerSumType.h(11.61 KB)
📄 PointerUnion.h(10.17 KB)
📄 PostOrderIterator.h(11.05 KB)
📄 PriorityQueue.h(2.69 KB)
📄 PriorityWorklist.h(8.11 KB)
📄 SCCIterator.h(8.02 KB)
📄 STLExtras.h(70.56 KB)
📄 ScopeExit.h(1.83 KB)
📄 ScopedHashTable.h(8.27 KB)
📄 Sequence.h(2.59 KB)
📄 SetOperations.h(2.58 KB)
📄 SetVector.h(9.39 KB)
📄 SmallBitVector.h(20.36 KB)
📄 SmallPtrSet.h(16.93 KB)
📄 SmallSet.h(8.37 KB)
📄 SmallString.h(8.55 KB)
📄 SmallVector.h(32.33 KB)
📄 SparseBitVector.h(26.2 KB)
📄 SparseMultiSet.h(17.83 KB)
📄 SparseSet.h(11.41 KB)
📄 Statistic.h(7.01 KB)
📄 StringExtras.h(13.25 KB)
📄 StringMap.h(15.7 KB)
📄 StringMapEntry.h(4.83 KB)
📄 StringRef.h(31.68 KB)
📄 StringSet.h(1.51 KB)
📄 StringSwitch.h(6.25 KB)
📄 TinyPtrVector.h(10.19 KB)
📄 Triple.h(27.4 KB)
📄 Twine.h(17.48 KB)
📄 TypeSwitch.h(5.82 KB)
📄 UniqueVector.h(3.09 KB)
📄 Waymarking.h(11.96 KB)
📄 bit.h(2.26 KB)
📄 edit_distance.h(3.57 KB)
📄 fallible_iterator.h(8.31 KB)
📄 ilist.h(13.68 KB)
📄 ilist_base.h(2.72 KB)
📄 ilist_iterator.h(7.21 KB)
📄 ilist_node.h(9.84 KB)
📄 ilist_node_base.h(1.7 KB)
📄 ilist_node_options.h(5.07 KB)
📄 iterator.h(13.46 KB)
📄 iterator_range.h(2.22 KB)
📄 simple_ilist.h(10.78 KB)

Editing: DirectedGraph.h

//===- llvm/ADT/DirectedGraph.h - Directed Graph ----------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the interface and a base class implementation for a
// directed graph.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_DIRECTEDGRAPH_H
#define LLVM_ADT_DIRECTEDGRAPH_H

#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

namespace llvm {

/// Represent an edge in the directed graph.
/// The edge contains the target node it connects to.
template <class NodeType, class EdgeType> class DGEdge {
public:
  DGEdge() = delete;
  /// Create an edge pointing to the given node \p N.
  explicit DGEdge(NodeType &N) : TargetNode(N) {}
  explicit DGEdge(const DGEdge<NodeType, EdgeType> &E)
      : TargetNode(E.TargetNode) {}
  DGEdge<NodeType, EdgeType> &operator=(const DGEdge<NodeType, EdgeType> &E) {
    TargetNode = E.TargetNode;
    return *this;
  }

/// Static polymorphism: delegate implementation (via isEqualTo) to the
  /// derived class.
  bool operator==(const EdgeType &E) const { return getDerived().isEqualTo(E); }
  bool operator!=(const EdgeType &E) const { return !operator==(E); }

/// Retrieve the target node this edge connects to.
  const NodeType &getTargetNode() const { return TargetNode; }
  NodeType &getTargetNode() {
    return const_cast<NodeType &>(
        static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getTargetNode());
  }

/// Set the target node this edge connects to.
  void setTargetNode(const NodeType &N) { TargetNode = N; }

protected:
  // As the default implementation use address comparison for equality.
  bool isEqualTo(const EdgeType &E) const { return this == &E; }

// Cast the 'this' pointer to the derived type and return a reference.
  EdgeType &getDerived() { return *static_cast<EdgeType *>(this); }
  const EdgeType &getDerived() const {
    return *static_cast<const EdgeType *>(this);
  }

// The target node this edge connects to.
  NodeType &TargetNode;
};

/// Represent a node in the directed graph.
/// The node has a (possibly empty) list of outgoing edges.
template <class NodeType, class EdgeType> class DGNode {
public:
  using EdgeListTy = SetVector<EdgeType *>;
  using iterator = typename EdgeListTy::iterator;
  using const_iterator = typename EdgeListTy::const_iterator;

/// Create a node with a single outgoing edge \p E.
  explicit DGNode(EdgeType &E) : Edges() { Edges.insert(&E); }
  DGNode() = default;

explicit DGNode(const DGNode<NodeType, EdgeType> &N) : Edges(N.Edges) {}
  DGNode(DGNode<NodeType, EdgeType> &&N) : Edges(std::move(N.Edges)) {}

DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &N) {
    Edges = N.Edges;
    return *this;
  }
  DGNode<NodeType, EdgeType> &operator=(const DGNode<NodeType, EdgeType> &&N) {
    Edges = std::move(N.Edges);
    return *this;
  }

/// Static polymorphism: delegate implementation (via isEqualTo) to the
  /// derived class.
  bool operator==(const NodeType &N) const { return getDerived().isEqualTo(N); }
  bool operator!=(const NodeType &N) const { return !operator==(N); }

const_iterator begin() const { return Edges.begin(); }
  const_iterator end() const { return Edges.end(); }
  iterator begin() { return Edges.begin(); }
  iterator end() { return Edges.end(); }
  const EdgeType &front() const { return *Edges.front(); }
  EdgeType &front() { return *Edges.front(); }
  const EdgeType &back() const { return *Edges.back(); }
  EdgeType &back() { return *Edges.back(); }

/// Collect in \p EL, all the edges from this node to \p N.
  /// Return true if at least one edge was found, and false otherwise.
  /// Note that this implementation allows more than one edge to connect
  /// a given pair of nodes.
  bool findEdgesTo(const NodeType &N, SmallVectorImpl<EdgeType *> &EL) const {
    assert(EL.empty() && "Expected the list of edges to be empty.");
    for (auto *E : Edges)
      if (E->getTargetNode() == N)
        EL.push_back(E);
    return !EL.empty();
  }

/// Add the given edge \p E to this node, if it doesn't exist already. Returns
  /// true if the edge is added and false otherwise.
  bool addEdge(EdgeType &E) { return Edges.insert(&E); }

/// Remove the given edge \p E from this node, if it exists.
  void removeEdge(EdgeType &E) { Edges.remove(&E); }

/// Test whether there is an edge that goes from this node to \p N.
  bool hasEdgeTo(const NodeType &N) const {
    return (findEdgeTo(N) != Edges.end());
  }

/// Retrieve the outgoing edges for the node.
  const EdgeListTy &getEdges() const { return Edges; }
  EdgeListTy &getEdges() {
    return const_cast<EdgeListTy &>(
        static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges);
  }

/// Clear the outgoing edges.
  void clear() { Edges.clear(); }

protected:
  // As the default implementation use address comparison for equality.
  bool isEqualTo(const NodeType &N) const { return this == &N; }

// Cast the 'this' pointer to the derived type and return a reference.
  NodeType &getDerived() { return *static_cast<NodeType *>(this); }
  const NodeType &getDerived() const {
    return *static_cast<const NodeType *>(this);
  }

/// Find an edge to \p N. If more than one edge exists, this will return
  /// the first one in the list of edges.
  const_iterator findEdgeTo(const NodeType &N) const {
    return llvm::find_if(
        Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; });
  }

// The list of outgoing edges.
  EdgeListTy Edges;
};

/// Directed graph
///
/// The graph is represented by a table of nodes.
/// Each node contains a (possibly empty) list of outgoing edges.
/// Each edge contains the target node it connects to.
template <class NodeType, class EdgeType> class DirectedGraph {
protected:
  using NodeListTy = SmallVector<NodeType *, 10>;
  using EdgeListTy = SmallVector<EdgeType *, 10>;
public:
  using iterator = typename NodeListTy::iterator;
  using const_iterator = typename NodeListTy::const_iterator;
  using DGraphType = DirectedGraph<NodeType, EdgeType>;

DirectedGraph() = default;
  explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); }
  DirectedGraph(const DGraphType &G) : Nodes(G.Nodes) {}
  DirectedGraph(DGraphType &&RHS) : Nodes(std::move(RHS.Nodes)) {}
  DGraphType &operator=(const DGraphType &G) {
    Nodes = G.Nodes;
    return *this;
  }
  DGraphType &operator=(const DGraphType &&G) {
    Nodes = std::move(G.Nodes);
    return *this;
  }

const_iterator begin() const { return Nodes.begin(); }
  const_iterator end() const { return Nodes.end(); }
  iterator begin() { return Nodes.begin(); }
  iterator end() { return Nodes.end(); }
  const NodeType &front() const { return *Nodes.front(); }
  NodeType &front() { return *Nodes.front(); }
  const NodeType &back() const { return *Nodes.back(); }
  NodeType &back() { return *Nodes.back(); }

size_t size() const { return Nodes.size(); }

/// Find the given node \p N in the table.
  const_iterator findNode(const NodeType &N) const {
    return llvm::find_if(Nodes,
                         [&N](const NodeType *Node) { return *Node == N; });
  }
  iterator findNode(const NodeType &N) {
    return const_cast<iterator>(
        static_cast<const DGraphType &>(*this).findNode(N));
  }

/// Add the given node \p N to the graph if it is not already present.
  bool addNode(NodeType &N) {
    if (findNode(N) != Nodes.end())
      return false;
    Nodes.push_back(&N);
    return true;
  }

/// Collect in \p EL all edges that are coming into node \p N. Return true
  /// if at least one edge was found, and false otherwise.
  bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl<EdgeType*> &EL) const {
    assert(EL.empty() && "Expected the list of edges to be empty.");
    EdgeListTy TempList;
    for (auto *Node : Nodes) {
      if (*Node == N)
        continue;
      Node->findEdgesTo(N, TempList);
      EL.insert(EL.end(), TempList.begin(), TempList.end());
      TempList.clear();
    }
    return !EL.empty();
  }

/// Remove the given node \p N from the graph. If the node has incoming or
  /// outgoing edges, they are also removed. Return true if the node was found
  /// and then removed, and false if the node was not found in the graph to
  /// begin with.
  bool removeNode(NodeType &N) {
    iterator IT = findNode(N);
    if (IT == Nodes.end())
      return false;
    // Remove incoming edges.
    EdgeListTy EL;
    for (auto *Node : Nodes) {
      if (*Node == N)
        continue;
      Node->findEdgesTo(N, EL);
      for (auto *E : EL)
        Node->removeEdge(*E);
      EL.clear();
    }
    N.clear();
    Nodes.erase(IT);
    return true;
  }

/// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p
  /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is
  /// not already connected to \p Dst via \p E, and false otherwise.
  bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {
    assert(findNode(Src) != Nodes.end() && "Src node should be present.");
    assert(findNode(Dst) != Nodes.end() && "Dst node should be present.");
    assert((E.getTargetNode() == Dst) &&
           "Target of the given edge does not match Dst.");
    return Src.addEdge(E);
  }

protected:
  // The list of nodes in the graph.
  NodeListTy Nodes;
};

} // namespace llvm

#endif // LLVM_ADT_DIRECTEDGRAPH_H

003 File Manager

Editing: DirectedGraph.h

Upload File

Create Folder