Author: kuemmel
Date: Wed Jan 19 10:03:41 2011
New Revision: 37257
URL: http://www.lyx.org/trac/changeset/37257
Log:
#7240
Make Graph more thread save by removing unneeded sharing of data between
function calls:
1. Q_
When Q_ is used then it always has been cleared before usage in bfs_init
(if bfs_init returns false Q_ is not used).
Therefore we could make Q_ local to the functions.
2. vertices_[].path
.path is only used in getPath, and the pathes are always cleared before usage,
so the pathes could also be local.
The locks are not needed here any more. When there will be errors due to
race conditions, we could not solve them here. We have to lock at higher
places.
Modified:
lyx-devel/trunk/src/Graph.cpp
lyx-devel/trunk/src/Graph.h
Modified: lyx-devel/trunk/src/Graph.cpp
==============================================================================
--- lyx-devel/trunk/src/Graph.cpp Wed Jan 19 00:11:27 2011 (r37256)
+++ lyx-devel/trunk/src/Graph.cpp Wed Jan 19 10:03:41 2011 (r37257)
@@ -24,12 +24,12 @@
namespace lyx {
-bool Graph::bfs_init(int s, bool clear_visited)
+bool Graph::bfs_init(int s, bool clear_visited, queue<int>* Q)
{
- if (s < 0)
+ if (s < 0 || !Q)
return false;
- Q_ = queue<int>();
+ *Q = queue<int>();
if (clear_visited) {
vector<Vertex>::iterator it = vertices_.begin();
@@ -38,40 +38,30 @@
it->visited = false;
}
if (!vertices_[s].visited) {
- Q_.push(s);
+ Q->push(s);
vertices_[s].visited = true;
}
return true;
}
-void Graph::clearPaths()
-{
- vector<Vertex>::iterator it = vertices_.begin();
- vector<Vertex>::iterator en = vertices_.end();
- for (; it != en; ++it)
- it->path.clear();
-}
-
-
vector<int> const
Graph::getReachableTo(int target, bool clear_visited)
{
- Mutex::Locker lock(&mutex_);
-
vector<int> result;
- if (!bfs_init(target, clear_visited))
+ queue<int> Q;
+ if (!bfs_init(target, clear_visited, &Q))
return result;
// Here's the logic, which is shared by the other routines.
- // Q_ holds a list of nodes we have been able to reach (in this
+ // Q holds a list of nodes we have been able to reach (in this
// case, reach backwards). It is initialized to the current node
// by bfs_init, and then we recurse, adding the nodes we can reach
// from the current node as we go. That makes it a breadth-first
// search.
- while (!Q_.empty()) {
- int const current = Q_.front();
- Q_.pop();
+ while (!Q.empty()) {
+ int const current = Q.front();
+ Q.pop();
if (current != target || formats.get(target).name() != "lyx")
result.push_back(current);
@@ -81,7 +71,7 @@
const int cv = (*it)->from;
if (!vertices_[cv].visited) {
vertices_[cv].visited = true;
- Q_.push(cv);
+ Q.push(cv);
}
}
}
@@ -94,15 +84,14 @@
Graph::getReachable(int from, bool only_viewable,
bool clear_visited)
{
- Mutex::Locker lock(&mutex_);
-
vector<int> result;
- if (!bfs_init(from, clear_visited))
+ queue<int> Q;
+ if (!bfs_init(from, clear_visited, &Q))
return result;
- while (!Q_.empty()) {
- int const current = Q_.front();
- Q_.pop();
+ while (!Q.empty()) {
+ int const current = Q.front();
+ Q.pop();
Format const & format = formats.get(current);
if (!only_viewable || !format.viewer().empty())
result.push_back(current);
@@ -121,7 +110,7 @@
int const cv = (*cit)->to;
if (!vertices_[cv].visited) {
vertices_[cv].visited = true;
- Q_.push(cv);
+ Q.push(cv);
}
}
}
@@ -132,17 +121,16 @@
bool Graph::isReachable(int from, int to)
{
- Mutex::Locker lock(&mutex_);
-
if (from == to)
return true;
- if (to < 0 || !bfs_init(from))
+ queue<int> Q;
+ if (to < 0 || !bfs_init(from, true, &Q))
return false;
- while (!Q_.empty()) {
- int const current = Q_.front();
- Q_.pop();
+ while (!Q.empty()) {
+ int const current = Q.front();
+ Q.pop();
if (current == to)
return true;
@@ -154,7 +142,7 @@
int const cv = (*cit)->to;
if (!vertices_[cv].visited) {
vertices_[cv].visited = true;
- Q_.push(cv);
+ Q.push(cv);
}
}
}
@@ -165,18 +153,18 @@
Graph::EdgePath const Graph::getPath(int from, int to)
{
- Mutex::Locker lock(&mutex_);
-
if (from == to)
return EdgePath();
- if (to < 0 || !bfs_init(from))
+ queue<int> Q;
+ if (to < 0 || !bfs_init(from, true, &Q))
return EdgePath();
- clearPaths();
- while (!Q_.empty()) {
- int const current = Q_.front();
- Q_.pop();
+ vector<EdgePath> pathes;
+ pathes.resize(vertices_.size());
+ while (!Q.empty()) {
+ int const current = Q.front();
+ Q.pop();
vector<Arrow *>::const_iterator cit =
vertices_[current].out_arrows.begin();
@@ -186,16 +174,16 @@
int const cv = (*cit)->to;
if (!vertices_[cv].visited) {
vertices_[cv].visited = true;
- Q_.push(cv);
+ Q.push(cv);
// NOTE If we wanted to collect all the paths,
then
// we just need to collect them here and not
worry
// about "visited".
- EdgePath lastpath =
vertices_[(*cit)->from].path;
+ EdgePath lastpath = pathes[(*cit)->from];
lastpath.push_back((*cit)->id);
- vertices_[cv].path = lastpath;
+ pathes[cv] = lastpath;
}
if (cv == to) {
- return vertices_[cv].path;
+ return pathes[cv];
}
}
}
@@ -206,8 +194,6 @@
void Graph::init(int size)
{
- Mutex::Locker lock(&mutex_);
-
vertices_ = vector<Vertex>(size);
arrows_.clear();
numedges_ = 0;
@@ -216,8 +202,6 @@
void Graph::addEdge(int from, int to)
{
- Mutex::Locker lock(&mutex_);
-
arrows_.push_back(Arrow(from, to, numedges_));
numedges_++;
Arrow * ar = &(arrows_.back());
Modified: lyx-devel/trunk/src/Graph.h
==============================================================================
--- lyx-devel/trunk/src/Graph.h Wed Jan 19 00:11:27 2011 (r37256)
+++ lyx-devel/trunk/src/Graph.h Wed Jan 19 10:03:41 2011 (r37257)
@@ -13,7 +13,6 @@
#ifndef GRAPH_H
#define GRAPH_H
-#include "support/mutex.h"
#include <list>
#include <queue>
@@ -47,10 +46,7 @@
private:
///
- bool bfs_init(int, bool clear_visited = true);
- /// clears the paths from a previous search. should be
- /// called before each new one.
- void clearPaths();
+ bool bfs_init(int, bool clear_visited, std::queue<int>* Q);
/// used to recover a marked path
void getMarkedPath(int from, int to, EdgePath & path);
/// these represent the arrows connecting the nodes of the graph.
@@ -83,8 +79,6 @@
std::vector<Arrow *> out_arrows;
/// used in the search routines
bool visited;
- ///
- EdgePath path;
};
/// a container for the vertices
/// the index into the vector functions as the identifier by which
@@ -94,17 +88,13 @@
/// of Format, this is easy, since the Format objects already have ints
/// as identifiers.)
std::vector<Vertex> vertices_;
- ///
- std::queue<int> Q_;
+
/// a counter that we use to assign id's to the arrows
/// FIXME This technique assumes a correspondence between the
/// ids of the arrows and ids associated with Converters that
/// seems kind of fragile. Perhaps a better solution would be
/// to pass the ids as we create the arrows.
int numedges_;
-
- /// make public functions thread save
- Mutex mutex_;
};
