00001
00025 #ifndef GALOIS_GRAPH_LC_MORPH_GRAPH_H
00026 #define GALOIS_GRAPH_LC_MORPH_GRAPH_H
00027
00028 #include "Galois/config.h"
00029 #include "Galois/Bag.h"
00030 #include "Galois/LargeArray.h"
00031 #include "Galois/Graph/FileGraph.h"
00032 #include "Galois/Graph/Details.h"
00033 #include "Galois/Runtime/MethodFlags.h"
00034
00035 #include <boost/mpl/if.hpp>
00036 #include GALOIS_CXX11_STD_HEADER(type_traits)
00037
00038 namespace Galois {
00039 namespace Graph {
00040
00042 template<typename NodeTy, typename EdgeTy,
00043 bool HasNoLockable=false,
00044 bool UseNumaAlloc=false,
00045 bool HasOutOfLineLockable=false,
00046 bool HasId=false>
00047 class LC_Morph_Graph:
00048 private boost::noncopyable,
00049 private detail::OutOfLineLockableFeature<HasOutOfLineLockable && !HasNoLockable> {
00050 template<typename Graph> friend class LC_InOut_Graph;
00051
00052 public:
00053 template<bool _has_id>
00054 struct with_id { typedef LC_Morph_Graph<NodeTy,EdgeTy,HasNoLockable,UseNumaAlloc,HasOutOfLineLockable,_has_id> type; };
00055
00056 template<typename _node_data>
00057 struct with_node_data { typedef LC_Morph_Graph<_node_data,EdgeTy,HasNoLockable,UseNumaAlloc,HasOutOfLineLockable,HasId> type; };
00058
00059 template<bool _has_no_lockable>
00060 struct with_no_lockable { typedef LC_Morph_Graph<NodeTy,EdgeTy,_has_no_lockable,UseNumaAlloc,HasOutOfLineLockable,HasId> type; };
00061
00062 template<bool _use_numa_alloc>
00063 struct with_numa_alloc { typedef LC_Morph_Graph<NodeTy,EdgeTy,HasNoLockable,_use_numa_alloc,HasOutOfLineLockable,HasId> type; };
00064
00065 template<bool _has_out_of_line_lockable>
00066 struct with_out_of_line_lockable { typedef LC_Morph_Graph<NodeTy,EdgeTy,HasNoLockable,UseNumaAlloc,_has_out_of_line_lockable,_has_out_of_line_lockable||HasId> type; };
00067
00068 typedef read_with_aux_graph_tag read_tag;
00069
00070 protected:
00071 class NodeInfo;
00072 typedef detail::EdgeInfoBase<NodeInfo*, EdgeTy> EdgeInfo;
00073 typedef Galois::InsertBag<NodeInfo> Nodes;
00074 typedef detail::NodeInfoBaseTypes<NodeTy,!HasNoLockable && !HasOutOfLineLockable> NodeInfoTypes;
00075
00076 struct EdgeHolder {
00077 EdgeInfo* begin;
00078 EdgeInfo* end;
00079 EdgeHolder* next;
00080 };
00081
00082 class NodeInfo: public detail::NodeInfoBase<NodeTy,!HasNoLockable && !HasOutOfLineLockable> {
00083 typedef detail::NodeInfoBase<NodeTy,!HasNoLockable && !HasOutOfLineLockable> Super;
00084 friend class LC_Morph_Graph;
00085
00086 EdgeInfo* edgeBegin;
00087 EdgeInfo* edgeEnd;
00088
00089 public:
00090 template<typename... Args>
00091 NodeInfo(Args&&... args): Super(std::forward<Args>(args)...) { }
00092 };
00093
00094 struct makeGraphNode: public std::unary_function<NodeInfo&, NodeInfo*> {
00095 NodeInfo* operator()(NodeInfo& data) const { return &data; }
00096 };
00097
00098 struct dst_equals {
00099 NodeInfo* dst;
00100 dst_equals(NodeInfo* d): dst(d) { }
00101 bool operator()(const EdgeInfo& edge) { return edge.dst == dst; }
00102 };
00103
00104 public:
00105 typedef NodeInfo* GraphNode;
00106 typedef EdgeTy edge_data_type;
00107 typedef NodeTy node_data_type;
00108 typedef typename NodeInfoTypes::reference node_data_reference;
00109 typedef typename EdgeInfo::reference edge_data_reference;
00110 typedef EdgeInfo* edge_iterator;
00111 typedef boost::transform_iterator<makeGraphNode,typename Nodes::iterator> iterator;
00112 typedef boost::transform_iterator<makeGraphNode,typename Nodes::const_iterator> const_iterator;
00113 typedef iterator local_iterator;
00114 typedef const_iterator const_local_iterator;
00115 typedef LargeArray<GraphNode> ReadGraphAuxData;
00116
00117 protected:
00118 Nodes nodes;
00119 Galois::Runtime::PerThreadStorage<EdgeHolder*> edges;
00120
00121 template<bool _A1 = HasNoLockable, bool _A2 = HasOutOfLineLockable>
00122 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<!_A1 && !_A2>::type* = 0) {
00123 Galois::Runtime::acquire(N, mflag);
00124 }
00125
00126 template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
00127 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<_A1 && !_A2>::type* = 0) {
00128 this->outOfLineAcquire(getId(N), mflag);
00129 }
00130
00131 template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
00132 void acquireNode(GraphNode N, MethodFlag mflag, typename std::enable_if<_A2>::type* = 0) { }
00133
00134 template<bool _Enable = HasId>
00135 size_t getId(GraphNode N, typename std::enable_if<_Enable>::type* = 0) {
00136 return N->getId();
00137 }
00138
00139 public:
00140 ~LC_Morph_Graph() {
00141 for (typename Nodes::iterator ii = nodes.begin(), ei = nodes.end(); ii != ei; ++ii) {
00142 NodeInfo& n = *ii;
00143 EdgeInfo* edgeBegin = n.edgeBegin;
00144 EdgeInfo* edgeEnd = n.edgeEnd;
00145
00146 if (EdgeInfo::has_value) {
00147 while (edgeBegin != edgeEnd) {
00148 edgeBegin->destroy();
00149 ++edgeBegin;
00150 }
00151 }
00152 }
00153 }
00154
00155 node_data_reference getData(const GraphNode& N, MethodFlag mflag = MethodFlag::ALL) {
00156 Galois::Runtime::checkWrite(mflag, false);
00157 acquireNode(N, mflag);
00158 return N->getData();
00159 }
00160
00161 edge_data_reference getEdgeData(edge_iterator ni, MethodFlag mflag = MethodFlag::NONE) {
00162 Galois::Runtime::checkWrite(mflag, false);
00163 acquireNode(ni->dst, mflag);
00164 return ni->get();
00165 }
00166
00167 GraphNode getEdgeDst(edge_iterator ni) {
00168
00169
00170 return GraphNode(ni->dst);
00171 }
00172
00176 iterator begin() {
00177 return boost::make_transform_iterator(nodes.begin(), makeGraphNode());
00178 }
00179
00181 iterator end() {
00182 return boost::make_transform_iterator(nodes.end(), makeGraphNode());
00183 }
00184
00185 local_iterator local_begin() {
00186 return boost::make_transform_iterator(nodes.local_begin(), makeGraphNode());
00187 }
00188
00189 local_iterator local_end() {
00190 return boost::make_transform_iterator(nodes.local_end(), makeGraphNode());
00191 }
00192
00193 edge_iterator edge_begin(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00194 acquireNode(N, mflag);
00195 if (Galois::Runtime::shouldLock(mflag)) {
00196 for (edge_iterator ii = N->edgeBegin, ee = N->edgeEnd; ii != ee; ++ii) {
00197 acquireNode(ii->dst, mflag);
00198 }
00199 }
00200 return N->edgeBegin;
00201 }
00202
00203 edge_iterator edge_end(GraphNode N, MethodFlag mflag = MethodFlag::ALL) {
00204 return N->edgeEnd;
00205 }
00206
00207 template<typename... Args>
00208 GraphNode createNode(int nedges, Args&&... args) {
00209 Galois::Runtime::checkWrite(MethodFlag::ALL, true);
00210 NodeInfo* N = &nodes.emplace(std::forward<Args>(args)...);
00211 acquireNode(N, MethodFlag::ALL);
00212 EdgeHolder*& local_edges = *edges.getLocal();
00213 if (!local_edges || std::distance(local_edges->begin, local_edges->end) < nedges) {
00214 EdgeHolder* old = local_edges;
00215 char* newblock = (char*)Runtime::MM::pageAlloc();
00216 local_edges = (EdgeHolder*)newblock;
00217 local_edges->next = old;
00218 char* estart = newblock + sizeof(EdgeHolder);
00219 if ((uintptr_t)estart % sizeof(EdgeInfo))
00220 #ifdef HAVE_CXX11_ALIGNOF
00221 estart += sizeof(EdgeInfo) - ((uintptr_t)estart % alignof(EdgeInfo));
00222 #else
00223 estart += sizeof(EdgeInfo) - ((uintptr_t)estart % 8);
00224 #endif
00225
00226 local_edges->begin = (EdgeInfo*)estart;
00227 char* eend = newblock + Runtime::MM::pageSize;
00228 eend -= (uintptr_t)eend % sizeof(EdgeInfo);
00229 local_edges->end = (EdgeInfo*)eend;
00230 }
00231 N->edgeBegin = N->edgeEnd = local_edges->begin;
00232 local_edges->begin += nedges;
00233 return GraphNode(N);
00234 }
00235
00236 template<typename... Args>
00237 edge_iterator addEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag, Args&&... args) {
00238 Galois::Runtime::checkWrite(mflag, true);
00239 acquireNode(src, mflag);
00240 auto it = std::find_if(src->edgeBegin, src->edgeEnd, dst_equals(dst));
00241 if (it == src->edgeEnd) {
00242 it->dst = dst;
00243 it->construct(std::forward<Args>(args)...);
00244 src->edgeEnd++;
00245 }
00246 return it;
00247 }
00248
00249 template<typename... Args>
00250 edge_iterator addEdgeWithoutCheck(GraphNode src, GraphNode dst, Galois::MethodFlag mflag, Args&&... args) {
00251 Galois::Runtime::checkWrite(mflag, true);
00252 acquireNode(src, mflag);
00253 auto it = src->edgeEnd;
00254 it->dst = dst;
00255 it->construct(std::forward<Args>(args)...);
00256 src->edgeEnd++;
00257 return it;
00258 }
00259
00260 edge_iterator findEdge(GraphNode src, GraphNode dst, Galois::MethodFlag mflag = MethodFlag::ALL) {
00261 Galois::Runtime::checkWrite(mflag, true);
00262 acquireNode(src, mflag);
00263 return std::find_if(src->edgeBegin, src->edgeEnd, dst_equals(dst));
00264 }
00265
00266 void allocateFrom(FileGraph& graph, ReadGraphAuxData& aux) {
00267 size_t numNodes = graph.size();
00268
00269 if (UseNumaAlloc) {
00270 aux.allocateLocal(numNodes, false);
00271 this->outOfLineAllocateLocal(numNodes, false);
00272 } else {
00273 aux.allocateInterleaved(numNodes);
00274 this->outOfLineAllocateInterleaved(numNodes);
00275 }
00276 }
00277
00278 void constructNodesFrom(FileGraph& graph, unsigned tid, unsigned total, ReadGraphAuxData& aux) {
00279 auto r = graph.divideBy(
00280 sizeof(NodeInfo) + LC_Morph_Graph::size_of_out_of_line::value,
00281 sizeof(EdgeInfo),
00282 tid, total);
00283
00284 size_t id = *r.first;
00285 for (FileGraph::iterator ii = r.first, ei = r.second; ii != ei; ++ii, ++id) {
00286 aux[id] = createNode(std::distance(graph.edge_begin(*ii), graph.edge_end(*ii)));
00287 }
00288 }
00289
00290 void constructEdgesFrom(FileGraph& graph, unsigned tid, unsigned total, const ReadGraphAuxData& aux) {
00291 auto r = graph.divideBy(
00292 sizeof(NodeInfo) + LC_Morph_Graph::size_of_out_of_line::value,
00293 sizeof(EdgeInfo),
00294 tid, total);
00295
00296 for (FileGraph::iterator ii = r.first, ei = r.second; ii != ei; ++ii) {
00297 for (FileGraph::edge_iterator nn = graph.edge_begin(*ii), en = graph.edge_end(*ii); nn != en; ++nn) {
00298 if (EdgeInfo::has_value) {
00299 addEdgeWithoutCheck(aux[*ii], aux[graph.getEdgeDst(nn)], Galois::MethodFlag::NONE, graph.getEdgeData<uint32_t>(nn));
00300 } else {
00301 addEdgeWithoutCheck(aux[*ii], aux[graph.getEdgeDst(nn)], Galois::MethodFlag::NONE);
00302 }
00303 }
00304 }
00305 }
00306 };
00307
00308 }
00309 }
00310
00311 #endif
