Introduce a FlatMap and FlatSet into WTF

third_party/WebKit/Source/wtf/FlatMap.h

Index: third_party/WebKit/Source/wtf/FlatMap.h
diff --git a/third_party/WebKit/Source/wtf/FlatMap.h b/third_party/WebKit/Source/wtf/FlatMap.h
new file mode 100644
index 0000000000000000000000000000000000000000..e0bf88da7cd419c28d555a2ff3208989194ad60b
--- /dev/null
+++ b/third_party/WebKit/Source/wtf/FlatMap.h
@@ -0,0 +1,119 @@
+// Copyright 2016 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.
+
+#ifndef WTF_FlatMap_h
+#define WTF_FlatMap_h
+
+#include "base/macros.h"
+#include "wtf/FlatTable.h"
+
+namespace WTF {
+
+template <typename Key, typename Value>
+struct FlatMapDelegate {
+  using key_type = Key;
+  using value_type = std::pair<Key, Value>;
+
+  static inline const Key& ToKey(const value_type& v) { return v.first; }
+};
+
+// A FlatMap is an STL-like associative container backed by a ring buffer.
+// Generally you should use WTF::HashMap unless you need an associative
+// container. FlatMap is usually faster than std::map for small maps (<=128)
+// (sometimes considerably so) and is always faster for immutable maps.
+template <typename Key, typename Value>
+class FlatMap : public FlatTable<FlatMapDelegate<Key, Value>> {
+ public:
+  FlatMap() {}
+
+  using BaseClass = FlatTable<FlatMapDelegate<Key, Value>>;
+  using key_type = typename BaseClass::key_type;
+  using value_type = typename BaseClass::value_type;
+  using iterator = typename BaseClass::iterator;
+  using const_iterator = typename BaseClass::const_iterator;
+  using reverse_iterator = typename BaseClass::reverse_iterator;
+  using const_reverse_iterator = typename BaseClass::const_reverse_iterator;
+
+  using BaseClass::empty;
+  using BaseClass::clear;
+  using BaseClass::insert;
+  using BaseClass::insertUnique;
+  using BaseClass::size;
+
+  iterator begin() { return BaseClass::begin(); }
+  iterator end() { return BaseClass::end(); }
+  const_iterator begin() const { return BaseClass::begin(); }
+  const_iterator end() const { return BaseClass::end(); }
+  reverse_iterator rbegin() { return BaseClass::rbegin(); }
+  const_reverse_iterator rbegin() const { return BaseClass::rbegin(); }
+
+  // Erases an entry corresponding to |key|, if any, from the map.
+  // Invalidates any iterators. O(log n + n / 2)
+  size_t erase(const Key& key) { return BaseClass::erase(key); }
+
+  // Erases |it| from the map, invalidating any iterators. O(n / 2)
+  void erase(const iterator& it) { return BaseClass::erase(it); }
+  void erase(const reverse_iterator& it) { return BaseClass::erase(it); }
+
+  // O(log n)
+  iterator find(const Key& key) { return BaseClass::find(key); }
+
+  // O(log n)
+  const_iterator find(const Key& key) const { return BaseClass::find(key); }
+
+  // O(log n + n / 2)
+  void ChangeKey(const iterator& it, const Key& new_key) {
+    size_t index;
+    if (BinarySearch(new_key, &index)) {
+      // We are overwriting an existing entry.
+      ring_buffer_[index].second = std::move(it->second);
+      erase(it);
+      return;
+    }
+
+    ChangeKeyUnique(it, new_key);
+  }
+
+  // O(n / 2)
+  void ChangeKeyUnique(const iterator& it, const Key& new_key) {
+    size_t i = IteratorPosition(it);
+    DCHECK(ValidIndex(i)) << "i = " << i;
+    if (ring_buffer_[i].first < new_key) {
+      Value tempValue = std::move(ring_buffer_[i].second);
+      for (; i != RingPrev(back_) && ring_buffer_[RingNext(i)].first < new_key;
+           i = RingNext(i)) {
+        ring_buffer_[i] = std::move(ring_buffer_[RingNext(i)]);
+      }
+      DCHECK(ValidIndex(i)) << "i = " << i;
+      ring_buffer_[i].first = new_key;
+      ring_buffer_[i].second = std::move(tempValue);
+    } else if (new_key < ring_buffer_[i].first) {
+      Value tempValue = std::move(ring_buffer_[i].second);
+      for (; i != front_ && new_key < ring_buffer_[RingPrev(i)].first;
+           i = RingPrev(i)) {
+        ring_buffer_[i] = std::move(ring_buffer_[RingPrev(i)]);
+      }
+      DCHECK(ValidIndex(i)) << "i = " << i;
+      ring_buffer_[i].first = new_key;
+      ring_buffer_[i].second = std::move(tempValue);
+    }
+#ifndef NDEBUG
+    BaseClass::InvalidateIterators();
+#endif
+  }
+
+ private:
+  using BaseClass::BinarySearch;
+  using BaseClass::IteratorPosition;
+  using BaseClass::RingNext;
+  using BaseClass::RingPrev;
+  using BaseClass::ValidIndex;
+  using BaseClass::back_;
+  using BaseClass::front_;
+  using BaseClass::ring_buffer_;
+};
+
+}  // namespace WTF
+
+#endif  // WTF_FlatMap_h