LC_Morph_Graph.h

Go to the documentation of this file.

/*
 * This file belongs to the Galois project, a C++ library for exploiting
 * parallelism. The code is being released under the terms of the 3-Clause BSD
 * License (a copy is located in LICENSE.txt at the top-level directory).
 *
 * Copyright (C) 2018, The University of Texas at Austin. All rights reserved.
 * UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS
 * SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF
 * PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF
 * DEALING OR USAGE OF TRADE.  NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH
 * RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances
 * shall University be liable for incidental, special, indirect, direct or
 * consequential damages or loss of profits, interruption of business, or
 * related expenses which may arise from use of Software or Documentation,
 * including but not limited to those resulting from defects in Software and/or
 * Documentation, or loss or inaccuracy of data of any kind.
 */

#ifndef GALOIS_GRAPHS_LC_MORPH_GRAPH_H
#define GALOIS_GRAPHS_LC_MORPH_GRAPH_H

#include <type_traits>

#include <boost/mpl/if.hpp>

#include "galois/Bag.h"
#include "galois/config.h"
#include "galois/LargeArray.h"
#include "galois/graphs/FileGraph.h"
#include "galois/graphs/Details.h"

namespace galois {
namespace graphs {

template <typename NodeTy, typename EdgeTy, bool HasNoLockable = false,
          bool UseNumaAlloc = false, bool HasOutOfLineLockable = false,
          bool HasId = false, typename FileEdgeTy = EdgeTy>
class LC_Morph_Graph
    : private boost::noncopyable,
      private internal::OutOfLineLockableFeature<HasOutOfLineLockable &&
                                                 !HasNoLockable> {
  template <typename Graph>
  friend class LC_InOut_Graph;

public:
  template <bool _has_id>
  struct with_id {
    using type = LC_Morph_Graph<NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc,
                                HasOutOfLineLockable, _has_id, FileEdgeTy>;
  };

  template <typename _node_data>
  struct with_node_data {
    using type = LC_Morph_Graph<_node_data, EdgeTy, HasNoLockable, UseNumaAlloc,
                                HasOutOfLineLockable, HasId, FileEdgeTy>;
  };

  template <typename _edge_data>
  struct with_edge_data {
    using type = LC_Morph_Graph<NodeTy, _edge_data, HasNoLockable, UseNumaAlloc,
                                HasOutOfLineLockable, HasId, FileEdgeTy>;
  };

  template <typename _file_edge_data>
  struct with_file_edge_data {
    using type = LC_Morph_Graph<NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc,
                                HasOutOfLineLockable, HasId, _file_edge_data>;
  };

  template <bool _has_no_lockable>
  struct with_no_lockable {
    using type = LC_Morph_Graph<NodeTy, EdgeTy, _has_no_lockable, UseNumaAlloc,
                                HasOutOfLineLockable, HasId, FileEdgeTy>;
  };

  template <bool _use_numa_alloc>
  struct with_numa_alloc {
    using type = LC_Morph_Graph<NodeTy, EdgeTy, HasNoLockable, _use_numa_alloc,
                                HasOutOfLineLockable, HasId, FileEdgeTy>;
  };

  template <bool _has_out_of_line_lockable>
  struct with_out_of_line_lockable {
    using type = LC_Morph_Graph<NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc,
                                _has_out_of_line_lockable,
                                _has_out_of_line_lockable || HasId, FileEdgeTy>;
  };

  using read_tag = read_with_aux_graph_tag;

protected:
  // Forward declaration of class (defined below)
  class NodeInfo;

  using EdgeInfo = internal::EdgeInfoBase<NodeInfo*, EdgeTy>;
  using Nodes = galois::InsertBag<NodeInfo>;
  using NodeInfoTypes =
      internal::NodeInfoBaseTypes<NodeTy,
                                  !HasNoLockable && !HasOutOfLineLockable>;

  struct EdgeHolder {
    EdgeInfo* begin;
    EdgeInfo* end;
    EdgeHolder* next;
  };

  class NodeInfo
      : public internal::NodeInfoBase<NodeTy,
                                      !HasNoLockable && !HasOutOfLineLockable> {
    using Super =
        internal::NodeInfoBase<NodeTy, !HasNoLockable && !HasOutOfLineLockable>;
    friend class LC_Morph_Graph;

    EdgeInfo* edgeBegin;
    EdgeInfo* edgeEnd;
#ifndef NDEBUG
    EdgeInfo* trueEdgeEnd;
#endif

  public:
    template <typename... Args>
    NodeInfo(Args&&... args) : Super(std::forward<Args>(args)...) {}
  }; // end NodeInfo

  struct makeGraphNode : public std::unary_function<NodeInfo&, NodeInfo*> {
    NodeInfo* operator()(NodeInfo& data) const { return &data; }
  };

  struct dst_equals {
    NodeInfo* dst;
    dst_equals(NodeInfo* d) : dst(d) {}
    bool operator()(const EdgeInfo& edge) { return edge.dst == dst; }
  };

public:
  using GraphNode = NodeInfo*;
  using file_edge_data_type = FileEdgeTy;
  using edge_data_type = EdgeTy;
  using node_data_type = NodeTy;
  using node_data_reference = typename NodeInfoTypes::reference;
  using edge_data_reference = typename EdgeInfo::reference;
  using edge_iterator = EdgeInfo*;
  using iterator =
      boost::transform_iterator<makeGraphNode, typename Nodes::iterator>;
  using const_iterator =
      boost::transform_iterator<makeGraphNode, typename Nodes::const_iterator>;
  using local_iterator = iterator;
  using const_local_iterator = const_iterator;
  using ReadGraphAuxData = LargeArray<GraphNode>;

protected:
  Nodes nodes;
  galois::substrate::PerThreadStorage<EdgeHolder*> edgesL;

  template <bool _A1 = HasNoLockable, bool _A2 = HasOutOfLineLockable>
  void acquireNode(GraphNode N, MethodFlag mflag,
                   typename std::enable_if<!_A1 && !_A2>::type* = 0) {
    galois::runtime::acquire(N, mflag);
  }

  template <bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
  void acquireNode(GraphNode N, MethodFlag mflag,
                   typename std::enable_if<_A1 && !_A2>::type* = 0) {
    this->outOfLineAcquire(getId(N), mflag);
  }

  template <bool _A1 = EdgeInfo::has_value,
            bool _A2 = LargeArray<FileEdgeTy>::has_value>
  void constructEdgeValue(FileGraph& graph,
                          typename FileGraph::edge_iterator nn, GraphNode src,
                          GraphNode dst,
                          typename std::enable_if<!_A1 || _A2>::type* = 0) {
    if (EdgeInfo::has_value) {
      // type of edge data in file graph
      using FEDV = typename LargeArray<FileEdgeTy>::value_type;
      // add an edge with edge data
      addMultiEdge(src, dst, galois::MethodFlag::UNPROTECTED,
                   graph.getEdgeData<FEDV>(nn));
    } else {
      // add an edge without edge data
      addMultiEdge(src, dst, galois::MethodFlag::UNPROTECTED);
    }
  }

  template <bool _A1 = EdgeInfo::has_value,
            bool _A2 = LargeArray<FileEdgeTy>::has_value>
  void constructEdgeValue(FileGraph&, typename FileGraph::edge_iterator,
                          GraphNode src, GraphNode dst,
                          typename std::enable_if<_A1 && !_A2>::type* = 0) {
    addMultiEdge(src, dst, galois::MethodFlag::UNPROTECTED);
  }

  template <bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
  void acquireNode(GraphNode, MethodFlag,
                   typename std::enable_if<_A2>::type* = 0) {}

  template <bool _Enable = HasId>
  size_t getId(GraphNode N, typename std::enable_if<_Enable>::type* = 0) {
    return N->getId();
  }

public:
  ~LC_Morph_Graph() {
    for (typename Nodes::iterator ii = nodes.begin(), ei = nodes.end();
         ii != ei; ++ii) {
      NodeInfo& n         = *ii;
      EdgeInfo* edgeBegin = n.edgeBegin;
      EdgeInfo* edgeEnd   = n.edgeEnd;

      if (EdgeInfo::has_value) {
        while (edgeBegin != edgeEnd) {
          edgeBegin->destroy();
          ++edgeBegin;
        }
      }
    }
  }

  node_data_reference getData(const GraphNode& N,
                              MethodFlag mflag = MethodFlag::WRITE) {
    // galois::runtime::checkWrite(mflag, false);
    acquireNode(N, mflag);
    return N->getData();
  }

  edge_data_reference getEdgeData(edge_iterator ni,
                                  MethodFlag mflag = MethodFlag::UNPROTECTED) {
    // galois::runtime::checkWrite(mflag, false);
    acquireNode(ni->dst, mflag);
    return ni->get();
  }

  GraphNode getEdgeDst(edge_iterator ni) {
    // galois::runtime::checkWrite(mflag, false);
    // acquireNode(ni->dst, mflag);
    return GraphNode(ni->dst);
  }

  iterator begin() {
    return boost::make_transform_iterator(nodes.begin(), makeGraphNode());
  }

  iterator end() {
    return boost::make_transform_iterator(nodes.end(), makeGraphNode());
  }

  local_iterator local_begin() {
    return boost::make_transform_iterator(nodes.local_begin(), makeGraphNode());
  }

  local_iterator local_end() {
    return boost::make_transform_iterator(nodes.local_end(), makeGraphNode());
  }

  edge_iterator edge_begin(GraphNode N, MethodFlag mflag = MethodFlag::WRITE) {
    acquireNode(N, mflag);
    // Locks all destinations before returning edge iterator.
    if (galois::runtime::shouldLock(mflag)) {
      for (edge_iterator ii = N->edgeBegin, ee = N->edgeEnd; ii != ee; ++ii) {
        acquireNode(ii->dst, mflag);
      }
    }
    return N->edgeBegin;
  }

  edge_iterator edge_end(GraphNode N,
                         MethodFlag GALOIS_UNUSED(mflag) = MethodFlag::WRITE) {
    return N->edgeEnd;
  }

  runtime::iterable<NoDerefIterator<edge_iterator>>
  edges(GraphNode N, MethodFlag mflag = MethodFlag::WRITE) {
    return internal::make_no_deref_range(edge_begin(N, mflag),
                                         edge_end(N, mflag));
  }

  internal::EdgesIterator<LC_Morph_Graph>
  out_edges(GraphNode N, MethodFlag mflag = MethodFlag::WRITE) {
    return internal::EdgesIterator<LC_Morph_Graph>(*this, N, mflag);
  }

  template <typename... Args>
  GraphNode createNode(int nedges, Args&&... args) {
    NodeInfo* N = &nodes.emplace(std::forward<Args>(args)...);
    acquireNode(N, MethodFlag::WRITE);
    EdgeHolder*& local_edges = *edgesL.getLocal();

    // Allocate space for a new EdgeHolder object if necessary
    if (!local_edges ||
        std::distance(local_edges->begin, local_edges->end) < nedges) {
      EdgeHolder* old = local_edges;
      // FIXME: this seems to leak
      size_t size       = runtime::pagePoolSize();
      void* block       = runtime::pagePoolAlloc();
      local_edges       = reinterpret_cast<EdgeHolder*>(block);
      local_edges->next = old;

      size -= sizeof(EdgeHolder);
      block = reinterpret_cast<char*>(block) + sizeof(EdgeHolder);

      if (!std::align(std::alignment_of_v<EdgeInfo>, sizeof(EdgeInfo), block,
                      size)) {
        GALOIS_DIE("not enough space for EdgeInfo");
      }

      local_edges->begin = reinterpret_cast<EdgeInfo*>(block);
      local_edges->end   = local_edges->begin;
      local_edges->end += size / sizeof(EdgeInfo);
      if (std::distance(local_edges->begin, local_edges->end) < nedges) {
        GALOIS_DIE("not enough space for EdgeInfo");
      }
    }

    // Set the memory aside for the new node in the edge holder object
    N->edgeBegin = N->edgeEnd = local_edges->begin;
    local_edges->begin += nedges;
#ifndef NDEBUG
    N->trueEdgeEnd = local_edges->begin;
#endif
    return GraphNode(N);
  }

  template <typename... Args>
  edge_iterator addEdge(GraphNode src, GraphNode dst, galois::MethodFlag mflag,
                        Args&&... args) {
    // galois::runtime::checkWrite(mflag, true);
    acquireNode(src, mflag);
    auto it = std::find_if(src->edgeBegin, src->edgeEnd, dst_equals(dst));
    if (it == src->edgeEnd) {
      it->dst = dst;
      it->construct(std::forward<Args>(args)...);
      src->edgeEnd++;
      assert(src->edgeEnd <= src->trueEdgeEnd);
    }
    return it;
  }

  template <typename... Args>
  edge_iterator addMultiEdge(GraphNode src, GraphNode dst,
                             galois::MethodFlag mflag, Args&&... args) {
    acquireNode(src, mflag);
    auto it = src->edgeEnd;
    it->dst = dst;
    it->construct(std::forward<Args>(args)...);
    src->edgeEnd++;
    assert(src->edgeEnd <= src->trueEdgeEnd);
    return it;
  }

  void removeEdge(GraphNode src, edge_iterator dst,
                  galois::MethodFlag mflag = MethodFlag::WRITE) {
    // galois::runtime::checkWrite(mflag, true);
    acquireNode(src, mflag);
    src->edgeEnd--;
    assert(src->edgeBegin <= src->edgeEnd);
    std::swap(*dst, *src->edgeEnd);
    src->edgeEnd->destroy();
  }

  edge_iterator findEdge(GraphNode src, GraphNode dst,
                         galois::MethodFlag mflag = MethodFlag::WRITE) {
    // galois::runtime::checkWrite(mflag, true); // TODO: double check 'true'
    // here
    acquireNode(src, mflag);
    return std::find_if(src->edgeBegin, src->edgeEnd, dst_equals(dst));
  }

  void allocateFrom(FileGraph& graph, ReadGraphAuxData& aux) {
    size_t numNodes = graph.size();

    if (UseNumaAlloc) {
      aux.allocateLocal(numNodes);
      this->outOfLineAllocateLocal(numNodes);
    } else {
      aux.allocateInterleaved(numNodes);
      this->outOfLineAllocateInterleaved(numNodes);
    }
  }

  void constructNodesFrom(FileGraph& graph, unsigned tid, unsigned total,
                          ReadGraphAuxData& aux) {
    // get the portion of the graph that this thread is responsible for
    // creating
    auto r = graph
                 .divideByNode(sizeof(NodeInfo) +
                                   LC_Morph_Graph::size_of_out_of_line::value,
                               sizeof(EdgeInfo), tid, total)
                 .first;

    // create nodes of portion we are responsible for only
    for (FileGraph::iterator ii = r.first, ei = r.second; ii != ei; ++ii) {
      aux[*ii] =
          createNode(std::distance(graph.edge_begin(*ii), graph.edge_end(*ii)));
    }
  }

  void constructEdgesFrom(FileGraph& graph, unsigned tid, unsigned total,
                          const ReadGraphAuxData& aux) {
    auto r = graph
                 .divideByNode(sizeof(NodeInfo) +
                                   LC_Morph_Graph::size_of_out_of_line::value,
                               sizeof(EdgeInfo), tid, total)
                 .first;

    for (FileGraph::iterator ii = r.first, ei = r.second; ii != ei; ++ii) {
      for (FileGraph::edge_iterator nn = graph.edge_begin(*ii),
                                    en = graph.edge_end(*ii);
           nn != en; ++nn) {
        constructEdgeValue(graph, nn, aux[*ii], aux[graph.getEdgeDst(nn)]);
      }
    }
  }
};

} // namespace graphs
} // namespace galois

#endif /* LC_MORPH_GRAPH_H_ */