Improve a poor implementation of "find duplicates".

content/child/webcrypto/test/test_helpers.cc

 // Copyright 2014 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 "content/child/webcrypto/test/test_helpers.h"
 
+#include <algorithm>
+
 #include "base/file_util.h"
 #include "base/json/json_reader.h"
 #include "base/json/json_writer.h"
 #include "base/logging.h"
 #include "base/path_service.h"
 #include "base/stl_util.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/string_util.h"
 #include "base/values.h"
 #include "content/child/webcrypto/algorithm_dispatch.h"
@@ skipping 215 matching lines @@
     };
 
   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(kDigestNameToId); ++i) {
     if (kDigestNameToId[i].name == algorithm_name)
       return CreateAlgorithm(kDigestNameToId[i].id);
   }
 
   return blink::WebCryptoAlgorithm::createNull();
 }
 
-// Returns true if any of the vectors in the input list have identical content.
-// Dumb O(n^2) implementation but should be fast enough for the input sizes that
-// are used.
+// Creates a comparator for |bufs| which operates on indices rather than values.
+class CompareUsingIndex {
+ public:
+  explicit CompareUsingIndex(const std::vector<std::vector<uint8_t> >* bufs)
+      : bufs_(bufs) {}
+
+  bool operator()(size_t i1, size_t i2) { return (*bufs_)[i1] < (*bufs_)[i2]; }
+
+ private:
+  const std::vector<std::vector<uint8_t> >* bufs_;
+};
+
 bool CopiesExist(const std::vector<std::vector<uint8_t> >& bufs) {
-  for (size_t i = 0; i < bufs.size(); ++i) {
-    for (size_t j = i + 1; j < bufs.size(); ++j) {
-      if (CryptoData(bufs[i]) == CryptoData(bufs[j]))
-        return true;
-    }
+  // Sort the indices of |bufs| into a separate vector. This reduces the amount
+  // of data copied versus sorting |bufs| directly.
+  std::vector<size_t> sorted_indices(bufs.size());
+  for (size_t i = 0; i < sorted_indices.size(); ++i)
+    sorted_indices[i] = i;
+  std::sort(
+      sorted_indices.begin(), sorted_indices.end(), CompareUsingIndex(&bufs));
+
+  // Scan for adjacent duplicates.
+  for (size_t i = 1; i < sorted_indices.size(); ++i) {
+    if (bufs[sorted_indices[i]] == bufs[sorted_indices[i - 1]])
+      return true;
   }
   return false;
 }
 
 blink::WebCryptoAlgorithm CreateAesKeyGenAlgorithm(
     blink::WebCryptoAlgorithmId aes_alg_id,
     unsigned short length) {
   return blink::WebCryptoAlgorithm::adoptParamsAndCreate(
       aes_alg_id, new blink::WebCryptoAesKeyGenParams(length));
 }
@@ skipping 296 matching lines @@
   // Export the key in raw format and compare to the original.
   std::vector<uint8_t> key_raw_out;
   ASSERT_EQ(Status::Success(),
             ExportKey(blink::WebCryptoKeyFormatRaw, key, &key_raw_out));
   EXPECT_BYTES_EQ_HEX(key_hex, key_raw_out);
 }
 
 }  // namespace webcrypto
 
 }  // namesapce content