diff options
| -rw-r--r-- | README | 2 | ||||
| -rw-r--r-- | src/build_log.h | 2 | ||||
| -rw-r--r-- | src/edit_distance.cc | 38 | ||||
| -rw-r--r-- | src/hash_map.h | 2 |
4 files changed, 23 insertions, 21 deletions
@@ -13,7 +13,7 @@ To build your own binary, on many platforms it should be sufficient to 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 @@ struct Edge; /// 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 @@ int EditDistance(const StringPiece& s1, // 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 @@ struct StringPieceCmp : public hash_compare<StringPiece> { 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) { |