Merge pull request #1015 from moroten/docs-relpath
Describe why to use relative paths
diff --git a/README b/README
index 66a6516..20630c4 100644
--- a/README
+++ b/README
@@ -13,7 +13,7 @@
just run `./configure.py --bootstrap`; for more details see HACKING.md.
(Also read that before making changes to Ninja, as it has advice.)
-Installation is not necessary because the only required file is is the
+Installation is not necessary because the only required file is the
resulting ninja binary. However, to enable features like Bash
completion and Emacs and Vim editing modes, some files in misc/ must be
copied to appropriate locations.
diff --git a/src/build_log.h b/src/build_log.h
index fe81a85..785961e 100644
--- a/src/build_log.h
+++ b/src/build_log.h
@@ -27,7 +27,7 @@
/// Can answer questions about the manifest for the BuildLog.
struct BuildLogUser {
- /// Return if a given output no longer part of the build manifest.
+ /// Return if a given output is no longer part of the build manifest.
/// This is only called during recompaction and doesn't have to be fast.
virtual bool IsPathDead(StringPiece s) const = 0;
};
diff --git a/src/edit_distance.cc b/src/edit_distance.cc
index a6719d3..3bb62b8 100644
--- a/src/edit_distance.cc
+++ b/src/edit_distance.cc
@@ -28,40 +28,42 @@
// http://en.wikipedia.org/wiki/Levenshtein_distance
//
// Although the algorithm is typically described using an m x n
- // array, only two rows are used at a time, so this implementation
- // just keeps two separate vectors for those two rows.
+ // array, only one row plus one element are used at a time, so this
+ // implementation just keeps one vector for the row. To update one entry,
+ // only the entries to the left, top, and top-left are needed. The left
+ // entry is in row[x-1], the top entry is what's in row[x] from the last
+ // iteration, and the top-left entry is stored in previous.
int m = s1.len_;
int n = s2.len_;
- vector<int> previous(n + 1);
- vector<int> current(n + 1);
-
- for (int i = 0; i <= n; ++i)
- previous[i] = i;
+ vector<int> row(n + 1);
+ for (int i = 1; i <= n; ++i)
+ row[i] = i;
for (int y = 1; y <= m; ++y) {
- current[0] = y;
- int best_this_row = current[0];
+ row[0] = y;
+ int best_this_row = row[0];
+ int previous = y - 1;
for (int x = 1; x <= n; ++x) {
+ int old_row = row[x];
if (allow_replacements) {
- current[x] = min(previous[x-1] + (s1.str_[y-1] == s2.str_[x-1] ? 0 : 1),
- min(current[x-1], previous[x])+1);
+ row[x] = min(previous + (s1.str_[y - 1] == s2.str_[x - 1] ? 0 : 1),
+ min(row[x - 1], row[x]) + 1);
}
else {
- if (s1.str_[y-1] == s2.str_[x-1])
- current[x] = previous[x-1];
+ if (s1.str_[y - 1] == s2.str_[x - 1])
+ row[x] = previous;
else
- current[x] = min(current[x-1], previous[x]) + 1;
+ row[x] = min(row[x - 1], row[x]) + 1;
}
- best_this_row = min(best_this_row, current[x]);
+ previous = old_row;
+ best_this_row = min(best_this_row, row[x]);
}
if (max_edit_distance && best_this_row > max_edit_distance)
return max_edit_distance + 1;
-
- current.swap(previous);
}
- return previous[n];
+ return row[n];
}
diff --git a/src/hash_map.h b/src/hash_map.h
index abdba92..a91aeb9 100644
--- a/src/hash_map.h
+++ b/src/hash_map.h
@@ -76,7 +76,7 @@
return MurmurHash2(key.str_, key.len_);
}
bool operator()(const StringPiece& a, const StringPiece& b) const {
- int cmp = strncmp(a.str_, b.str_, min(a.len_, b.len_));
+ int cmp = memcmp(a.str_, b.str_, min(a.len_, b.len_));
if (cmp < 0) {
return true;
} else if (cmp > 0) {
