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..a16cdf4a81996dde102ac06065a4cc111f1b6aac 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);
 }
 
+// static
+IDBKey* IDBKey::createMultiEntryArray(const KeyArray& array) {
+  KeyArray result;

[pwnall, 2017/01/18 02:35:19]

Would it make sense to add a comment stating that we're not using HeapHashSet
because getting rid of the log factor isn't worth the code size/complexity of
having to implement DefaultHash<IDBKey>?

[jsbell, 2017/01/18 18:18:56]

I'm not sure why that is worth calling out. A hash lookup is O(log n) but we do
n inserts so that's O(n log n) to build the set, same as the sort.

What am I missing?

[pwnall, 2017/01/18 19:04:15]

If I'm reading HashTable.h correctly, we're using an open-addressing hash table
implementation in WTF, which should give us lookups and insertions in O(1)
amortized.

[jsbell, 2017/01/18 19:39:56]

Ah, right. Sleepy josh is sleepy. I'll add a note.

+  result.reserveCapacity(array.size());
+  std::copy_if(array.begin(), array.end(), std::back_inserter(result),
+               [](const Member<IDBKey> key) { return key->isValid(); });
+  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());
+
+  IDBKey* idbKey = new IDBKey(std::move(result));
+  DCHECK(idbKey->isValid());
+  return idbKey;
+}
+
 }  // namespace blink