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

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

 /*
  * Copyright (C) 2011 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
  * 2.  Redistributions in binary form must reproduce the above copyright
  *     notice, this list of conditions and the following disclaimer in the
  *     documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "modules/indexeddb/IDBKey.h"
 
+#include <algorithm>
+
 namespace blink {
 
 IDBKey::~IDBKey() {}
 
 DEFINE_TRACE(IDBKey) {
   visitor->trace(m_array);
 }
 
 bool IDBKey::isValid() const {
   if (m_type == InvalidType)
@@ skipping 57 matching lines @@
   return compare(other) == -1;
 }
 
 bool IDBKey::isEqual(const IDBKey* other) const {
   if (!other)
     return false;
 
   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