IndexedDB: Replace O(n^2) algorithm computing multientry index keys

third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp

Index: third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp
diff --git a/third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp b/third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp
index f682a31d65a1a8b77da7e38e56599434f9c0e002..356ad3bbf3b210df2566c89d03bcc990e57753aa 100644
--- a/third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp
+++ b/third_party/WebKit/Source/modules/indexeddb/IDBKey.cpp
@@ -25,6 +25,8 @@
 
 #include "modules/indexeddb/IDBKey.h"
 
+#include <algorithm>
+
 namespace blink {
 
 IDBKey::~IDBKey() {}
@@ -102,4 +104,23 @@ bool IDBKey::isEqual(const IDBKey* other) const {
   return !compare(other);
 }
 
+IDBKey::KeyArray IDBKey::toMultiEntryArray() const {
+  DCHECK_EQ(m_type, ArrayType);
+  KeyArray result;
+  result.reserveCapacity(m_array.size());
+  std::copy_if(m_array.begin(), m_array.end(), std::back_inserter(result),
+               [](const Member<IDBKey> key) { return key->isValid(); });
+
+  // Remove duplicates using std::sort/std::unique rather than a hashtable to
+  // avoid the complexity of implementing DefaultHash<IDBKey>.
+  std::sort(result.begin(), result.end(),
+            [](const Member<IDBKey> a, const Member<IDBKey> b) {
+              return a->isLessThan(b);
+            });
+  const auto end = std::unique(result.begin(), result.end());
+  DCHECK_LE(static_cast<size_t>(end - result.begin()), result.size());
+  result.resize(end - result.begin());
+  return result;
+}
+
 }  // namespace blink