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 <set>
+
 #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.
 bool CopiesExist(const std::vector<std::vector<uint8_t> >& bufs) {
+  std::set<std::vector<uint8_t> > values;
   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;
+    if (!values.insert(bufs[i]).second) {
+      return true;
     }

[Ryan Sleevi, 2014/08/27 17:15:58]

This seems to be memory intensive.

Why not just sort and then do a linear scan?

[eroman, 2014/08/27 18:47:06]

Done. I also modified it to sort a vector of indices to avoid moving lots of
data.

   }
   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