GraphLab: Distributed Graph-Parallel API  2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
rw_lock_manager.hpp
1 /**
2  * Copyright (c) 2009 Carnegie Mellon University.
3  * All rights reserved.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing,
12  * software distributed under the License is distributed on an "AS
13  * IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
14  * express or implied. See the License for the specific language
15  * governing permissions and limitations under the License.
16  *
17  * For more about this software visit:
18  *
19  * http://www.graphlab.ml.cmu.edu
20  *
21  */
22 
23 /**
24  * Also contains code that is Copyright 2011 Yahoo! Inc. All rights
25  * reserved.
26  *
27  * Contributed under the iCLA for:
28  * Joseph Gonzalez ([email protected])
29  *
30  */
31 
32 
33 
34 #ifndef GRAPHLAB_RW_LOCK_MANAGER_HPP
35 #define GRAPHLAB_RW_LOCK_MANAGER_HPP
36 
37 #include <vector>
38 
39 #include <graphlab/parallel/pthread_tools.hpp>
40 
41 
42 #include <graphlab/macros_def.hpp>
43 namespace graphlab {
44 
45 
46  template<typename Graph>
47  class rw_lock_manager {
48 
49  public:
50  typedef Graph graph_type;
51  typedef typename graph_type::vertex_id_type vertex_id_type;
52  typedef typename graph_type::edge_list_type edge_list_type;
53  typedef typename edge_list_type::const_iterator iterator;
54  typedef typename graph_type::edge_type edge_type;
55 
56  private:
57  const graph_type& graph;
58  std::vector<rwlock> locks;
59 
60  public:
61  rw_lock_manager(const graph_type& graph) :
62  graph(graph), locks(graph.num_vertices()) { }
63 
64  inline void writelock_vertex(const vertex_id_type& vid) {
65  // ASSERT_LT(vid, locks.size());
66  locks[vid].writelock();
67  }
68 
69  inline void readlock_vertex(const vertex_id_type& vid) {
70  // ASSERT_LT(vid, locks.size());
71  locks[vid].readlock();
72  }
73 
74  inline bool try_readlock_vertex(const vertex_id_type& vid) {
75  // ASSERT_LT(vid, locks.size());
76  return locks[vid].try_readlock();
77  }
78 
79  inline void release_vertex(const vertex_id_type& vid) {
80  // ASSERT_LT(vid, locks.size());
81  locks[vid].unlock();
82  }
83 
84  inline void lock_edge_context(const vertex_id_type& vid) {
85  const edge_list_type in_edges = graph.in_edges(vid);
86  const edge_list_type out_edges = graph.out_edges(vid);
87  // Loop over edges
88  bool processed_center = false;
89  iterator in = in_edges.begin(), out = out_edges.begin();
90  while(in != in_edges.end() && out != out_edges.end()) {
91  const vertex_id_type in_vid = in->source();
92  const vertex_id_type out_vid = out->target();
93  if(__builtin_expect(!processed_center &&
94  vid < in_vid && vid < out_vid, false)) {
95  processed_center = true; writelock_vertex(vid);
96  } else if (in_vid == out_vid) {
97  readlock_vertex(in_vid); ++in; ++out;
98  } else if(in_vid < out_vid) {
99  readlock_vertex(in_vid); ++in;
100  } else {
101  readlock_vertex(out_vid); ++out;
102  }
103  } // loop over both in and out
104  // Finish locking any remaining in edges
105  while(in != in_edges.end()) {
106  const vertex_id_type in_vid = in->source();
107  if(__builtin_expect(!processed_center && vid < in_vid, false)) {
108  processed_center = true; writelock_vertex(vid);
109  } else { readlock_vertex(in_vid); ++in; }
110  } // loop over in edges
111  // Finish locking any remaining out edges
112  while(out != out_edges.end()) {
113  const vertex_id_type out_vid = out->target();
114  if(__builtin_expect(!processed_center && vid < out_vid, false)) {
115  processed_center = true; writelock_vertex(vid);
116  } else { readlock_vertex(out_vid); ++out; }
117  } // loop over out edges
118  // If we still have not locked the center do so now
119  if(__builtin_expect(!processed_center, false)) { writelock_vertex(vid); }
120  } // end of lock edge context
121 
122  inline void lock_full_context(const vertex_id_type& vid) {
123  const edge_list_type in_edges = graph.in_edges(vid);
124  const edge_list_type out_edges = graph.out_edges(vid);
125  // Loop over edges
126  bool processed_center = false;
127  iterator in = in_edges.begin(), out = out_edges.begin();
128  while(in != in_edges.end() && out != out_edges.end()) {
129  const vertex_id_type in_vid = in->source();
130  const vertex_id_type out_vid = out->target();
131  if(__builtin_expect(!processed_center &&
132  vid < in_vid && vid < out_vid, false)) {
133  processed_center = true; writelock_vertex(vid);
134  } else if (in_vid == out_vid) {
135  writelock_vertex(in_vid); ++in; ++out;
136  } else if(in_vid < out_vid) {
137  writelock_vertex(in_vid); ++in;
138  } else {
139  writelock_vertex(out_vid); ++out;
140  }
141  } // loop over both in and out
142  // Finish locking any remaining in edges
143  while(in != in_edges.end()) {
144  const vertex_id_type in_vid = in->source();
145  if(__builtin_expect(!processed_center && vid < in_vid, false)) {
146  processed_center = true; writelock_vertex(vid);
147  } else { writelock_vertex(in_vid); ++in; }
148  } // loop over in edges
149  // Finish locking any remaining out edges
150  while(out != out_edges.end()) {
151  const vertex_id_type out_vid = out->target();
152  if(__builtin_expect(!processed_center && vid < out_vid, false)) {
153  processed_center = true; writelock_vertex(vid);
154  } else { writelock_vertex(out_vid); ++out; }
155  } // loop over out edges
156  // If we still have not locked the center do so now
157  if(__builtin_expect(!processed_center, false)) { writelock_vertex(vid); }
158  } // end of lock full context
159 
160 
161  inline void release_context(const vertex_id_type& vid) {
162  const edge_list_type in_edges = graph.in_edges(vid);
163  const edge_list_type out_edges = graph.out_edges(vid);
164  // Loop over edges
165  bool processed_center = false;
166  iterator in = in_edges.begin(), out = out_edges.begin();
167  while(in != in_edges.end() && out != out_edges.end()) {
168  const vertex_id_type in_vid = in->source();
169  const vertex_id_type out_vid = out->target();
170  if(__builtin_expect(!processed_center &&
171  vid < in_vid && vid < out_vid, false)) {
172  processed_center = true; release_vertex(vid);
173  } else if (in_vid == out_vid) {
174  release_vertex(in_vid); ++in; ++out;
175  } else if(in_vid < out_vid) {
176  release_vertex(in_vid); ++in;
177  } else {
178  release_vertex(out_vid); ++out;
179  }
180  } // loop over both in and out
181  // Finish releasing any remaining in edges
182  while(in != in_edges.end()) {
183  const vertex_id_type in_vid = in->source();
184  if(__builtin_expect(!processed_center && vid < in_vid, false)) {
185  processed_center = true; release_vertex(vid);
186  } else { release_vertex(in_vid); ++in; }
187  } // loop over in edges
188  // Finish releasing any remaining out edges
189  while(out != out_edges.end()) {
190  const vertex_id_type out_vid = out->target();
191  if(__builtin_expect(!processed_center && vid < out_vid, false)) {
192  processed_center = true; release_vertex(vid);
193  } else { release_vertex(out_vid); ++out; }
194  } // loop over out edges
195  // If we still have not released the center do so now
196  if(__builtin_expect(!processed_center, false)) { release_vertex(vid); }
197  } // end of release context
198 
199 
200 
201  inline void lock_single_edge(vertex_id_type center,
202  vertex_id_type neighbor) {
203  if(center < neighbor) { writelock_vertex(center); readlock_vertex(neighbor); }
204  else { readlock_vertex(neighbor); writelock_vertex(center); }
205  }
206 
207  inline void release_single_edge(vertex_id_type center,
208  vertex_id_type neighbor) {
209  release_vertex(center); release_vertex(neighbor);
210  }
211 
212  inline void swap_single_edge(vertex_id_type center,
213  vertex_id_type old_neighbor,
214  vertex_id_type new_neighbor) {
215  release_vertex(old_neighbor);
216  if(!try_readlock_vertex(new_neighbor)) {
217  release_vertex(center);
218  lock_single_edge(center, new_neighbor);
219  }
220  } // end of swap_single_edge
221 
222 
223  }; // end of rw_lock_manager
224 
225 
226 }; // end of graphlab namespace
227 #include <graphlab/macros_undef.hpp>
228 
229 
230 
231 #endif
232