[Courgette Experimental] Replace QSufSort with libdivsufsort

courgette/third_party/bsdiff/bsdiff_search_unittest.cc

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "courgette/third_party/bsdiff/bsdiff_search.h"
 
 #include <cstring>
 #include <vector>
 
 #include "base/macros.h"
-#include "courgette/third_party/bsdiff/qsufsort.h"
+#include "courgette/third_party/bsdiff/paged_array.h"
+#include "courgette/third_party/divsufsort/divsufsort.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 TEST(BSDiffSearchTest, Search) {
   // Initialize main string and the suffix array.
   // Positions:      000000000011111111111222222222333333333344444
   //                 012345678901234567890123456789012345678901234
   const char* str = "the quick brown fox jumps over the lazy dog.";
   int size = static_cast<int>(::strlen(str));
   const unsigned char* buf = reinterpret_cast<const unsigned char*>(str);
-  std::vector<int> I(size + 1);
-  std::vector<int> V(size + 1);
-  courgette::qsuf::qsufsort<int*>(&I[0], &V[0], buf, size);
+  courgette::PagedArray<divsuf::saidx_t> I;
+  ASSERT_TRUE(I.Allocate(size + 1));
+  I[0] = size;
+  divsuf::divsufsort(buf, I.begin() + 1, size);
 
   // Specific queries.
   const struct {
     int exp_pos;  // -1 means "don't care".
     int exp_match_size;
     const char* query_str;
   } test_cases[] = {
       // Entire string: exact and unique.
       {0, 44, "the quick brown fox jumps over the lazy dog."},
       // Empty string: exact and non-unique.
@@ skipping 25 matching lines @@
 
   for (size_t idx = 0; idx < arraysize(test_cases); ++idx) {
     const auto& test_case = test_cases[idx];
     int query_size = static_cast<int>(::strlen(test_case.query_str));
     const unsigned char* query_buf =
         reinterpret_cast<const unsigned char*>(test_case.query_str);
 
     // Perform the search.
     int pos = 0;
     int match_size =
-        courgette::search(&I[0], buf, size, query_buf, query_size, &pos);
+        bsdiff::search(&I[0], buf, size, query_buf, query_size, &pos);
 
     // Check basic properties and match with expected values.
     EXPECT_GE(match_size, 0);
     EXPECT_LE(match_size, query_size);
     if (match_size > 0) {
       EXPECT_GE(pos, 0);
       EXPECT_LE(pos, size - match_size);
       EXPECT_EQ(0, ::memcmp(buf + pos, query_buf, match_size));
     }
     if (test_case.exp_pos >= 0) {
@@ skipping 14 matching lines @@
       "banana",
       "tobeornottobe",
       "the quick brown fox jumps over the lazy dog.",
       "elephantelephantelephantelephantelephant",
       "011010011001011010010110011010010",
   };
   for (size_t idx = 0; idx < arraysize(test_cases); ++idx) {
     int size = static_cast<int>(::strlen(test_cases[idx]));
     const unsigned char* buf =
         reinterpret_cast<const unsigned char*>(test_cases[idx]);
-    std::vector<int> I(size + 1);
-    std::vector<int> V(size + 1);
-    courgette::qsuf::qsufsort<int*>(&I[0], &V[0], buf, size);
+    courgette::PagedArray<divsuf::saidx_t> I;
+    ASSERT_TRUE(I.Allocate(size + 1));
+    I[0] = size;
+    divsuf::divsufsort(buf, I.begin() + 1, size);
 
     // Test exact matches for every non-empty substring.
     for (int lo = 0; lo < size; ++lo) {
       for (int hi = lo + 1; hi <= size; ++hi) {
         std::string query(buf + lo, buf + hi);
         int query_size = static_cast<int>(query.length());
         ASSERT_EQ(query_size, hi - lo);
         const unsigned char* query_buf =
             reinterpret_cast<const unsigned char*>(query.c_str());
         int pos = 0;
         int match_size =
-            courgette::search(&I[0], buf, size, query_buf, query_size, &pos);
+            bsdiff::search(&I[0], buf, size, query_buf, query_size, &pos);
 
         EXPECT_EQ(query_size, match_size);
         EXPECT_GE(pos, 0);
         EXPECT_LE(pos, size - match_size);
         std::string suffix(buf + pos, buf + size);
         EXPECT_EQ(suffix.substr(0, query_size), query);
       }
     }
   }
 }