Index: courgette/third_party/bsdiff/qsufsort.h |
diff --git a/courgette/third_party/bsdiff/qsufsort.h b/courgette/third_party/bsdiff/qsufsort.h |
index ce4d7e577897c7058afccd428f7c75d99bec9f0c..37320652083c4d5a6f06d5e4a07f9a1748b96ad0 100644 |
--- a/courgette/third_party/bsdiff/qsufsort.h |
+++ b/courgette/third_party/bsdiff/qsufsort.h |
@@ -15,7 +15,7 @@ |
--Stephen Adams <sra@chromium.org> |
2015-08-03 - Extract QSufSort to a separate file as template. |
--Samuel Huang <huangs@chromium.org> |
- 2015-08-19 - Optimize split() and search(), add comments. |
+ 2015-08-19 - Optimize split(), add comments. |
--Samuel Huang <huangs@chromium.org> |
2016-04-27 - Change split() to use Bentley & McIlroy's pivot selection |
algorithm, which QSufSort originally used. Reference: |
@@ -26,10 +26,6 @@ |
#ifndef COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ |
#define COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ |
-#include <algorithm> |
-#include <cstring> |
- |
-namespace courgette { |
namespace qsuf { |
// ------------------------------------------------------------------------ |
@@ -40,7 +36,8 @@ namespace qsuf { |
// (2) indentation and spacing, |
// (3) using 'const', |
// (4) changing the V and I parameters from int* to template <typename T>. |
-// (5) optimizing split() and search(); fix styles. |
+// (5) optimizing split(); fix styles. |
+// (6) moving matchlen() and search() to a separate file. |
// |
// The code appears to be a rewritten version of the suffix array algorithm |
// presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko |
@@ -198,50 +195,9 @@ static void qsufsort(T I, T V, const unsigned char* old, int oldsize) { |
I[V[i]] = i; |
} |
-static int matchlen(const unsigned char* old, |
- int oldsize, |
- const unsigned char* newbuf, |
- int newsize) { |
- int i; |
- |
- for (i = 0; (i < oldsize) && (i < newsize); i++) |
- if (old[i] != newbuf[i]) |
- break; |
- |
- return i; |
-} |
- |
-template <class T> |
-static int search(T I, |
- const unsigned char* old, |
- int oldsize, |
- const unsigned char* newbuf, |
- int newsize, |
- int* pos) { |
- int lo = 0; |
- int hi = oldsize; |
- while (hi - lo >= 2) { |
- int mid = (lo + hi) / 2; |
- if (memcmp(old + I[mid], newbuf, std::min(oldsize - I[mid], newsize)) < 0) { |
- lo = mid; |
- } else { |
- hi = mid; |
- } |
- } |
- |
- int x = matchlen(old + I[lo], oldsize - I[lo], newbuf, newsize); |
- int y = matchlen(old + I[hi], oldsize - I[hi], newbuf, newsize); |
- if (x > y) { |
- *pos = I[lo]; |
- return x; |
- } |
- *pos = I[hi]; |
- return y; |
-} |
- |
// End of 'verbatim' code. |
// ------------------------------------------------------------------------ |
} // namespace qsuf |
-} // namespace courgette |
+ |
#endif // COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_ |