Introduce a FlatMap and FlatSet into WTF

third_party/WebKit/Source/wtf/FlatTable.h

+// 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_FlatTable_h
+#define WTF_FlatTable_h
+
+#include "base/logging.h"
+#include <vector>
+
+namespace WTF {
+
+// Iterator customization.
+template <typename Delegate>
+struct ForwardIteratorDelegate : public Delegate {
+  using FlatTableDelegate = Delegate;
+  static constexpr bool is_const = false;
+  static inline size_t next(size_t index) { return index + 1; }
+  static inline size_t prev(size_t index) { return index - 1; }
+};
+
+template <typename Delegate>
+struct ConstForwardIteratorDelegate : public Delegate {
+  using FlatTableDelegate = Delegate;
+  static constexpr bool is_const = true;
+  static inline size_t next(size_t index) { return index + 1; }
+  static inline size_t prev(size_t index) { return index - 1; }
+};
+
+template <typename Delegate>
+struct ReverseIteratorDelegate : public Delegate {
+  using FlatTableDelegate = Delegate;
+  static constexpr bool is_const = false;
+  static inline size_t next(size_t index) { return index - 1; }
+  static inline size_t prev(size_t index) { return index + 1; }
+};
+
+template <typename Delegate>
+struct ConstReverseIteratorDelegate : public Delegate {
+  using FlatTableDelegate = Delegate;
+  static constexpr bool is_const = true;
+  static inline size_t next(size_t index) { return index - 1; }
+  static inline size_t prev(size_t index) { return index + 1; }
+};
+
+// A FlatTable containing common code for FlatMap and FlatSet. Typically it
+// shouldn't be used directly.
+//
+// FlatTable is an associative container where the elements are held in a ring
+// buffer. This means the worst case for insert / erase moves O(n/2) elements,
+// unless the ring buffer needs to grow (infrequent), in which case it's O(n).
+template <typename Delegate>
+class FlatTable {
+ public:
+  FlatTable() : ring_buffer_(4), front_(0), back_(0), search_step_size_(1) {
+    ComputeModulusMask();
+  }
+
+  using key_type = typename Delegate::key_type;
+  using value_type = typename Delegate::value_type;
+
+  bool empty() const { return front_ == back_; }
+
+  void clear() {
+    ring_buffer_.clear();
+    ring_buffer_.resize(4);
+    front_ = 0;
+    back_ = 0;
+    search_step_size_ = 1;
+    ComputeModulusMask();
+  }
+
+  size_t size() const { return RingDistance(front_, back_); }
+
+  template <typename IteratorDelegate>
+  class FlatTableIterator {
+   public:
+    using ValueType =
+        typename std::conditional<IteratorDelegate::is_const,
+                                  const typename IteratorDelegate::value_type,
+                                  typename IteratorDelegate::value_type>::type;
+    using FlatTableDelegate = typename IteratorDelegate::FlatTableDelegate;
+    using FlatTableType =
+        typename std::conditional<IteratorDelegate::is_const,
+                                  const FlatTable<FlatTableDelegate>,
+                                  FlatTable<FlatTableDelegate>>::type;
+
+    FlatTableIterator& operator++() {
+      pos_ = IteratorDelegate::next(pos_) & flatTable_->modulus_mask_;
+      return *this;
+    }
+
+    FlatTableIterator& operator--() {
+      pos_ = IteratorDelegate::prev(pos_) & flatTable_->modulus_mask_;
+      return *this;
+    }
+
+    FlatTableIterator operator++(int /*unused*/) {
+      FlatTableIterator result(*this);
+      pos_ = IteratorDelegate::next(pos_) & flatTable_->modulus_mask_;
+      return result;
+    }
+
+    FlatTableIterator operator--(int /*unused*/) {
+      FlatTableIterator result(*this);
+      pos_ = IteratorDelegate::prev(pos_) & flatTable_->modulus_mask;
+      return result;
+    }
+
+    ValueType* operator->() const {
+      DCHECK(flatTable_->ValidIndex(pos_)) << "pos_ = " << pos_;
+#ifndef NDEBUG
+      DCHECK_EQ(iterator_generation_, flatTable_->iterator_generation_);
+#endif
+      return &flatTable_->ring_buffer_[pos_];
+    }
+
+    ValueType& operator*() const {
+      DCHECK(flatTable_->ValidIndex(pos_)) << "pos_ = " << pos_;
+#ifndef NDEBUG
+      DCHECK_EQ(iterator_generation_, flatTable_->iterator_generation_);
+#endif
+      return flatTable_->ring_buffer_[pos_];
+    }
+
+    template <typename OtherT>
+    bool operator==(const OtherT& other) const {
+      return flatTable_ == other.flatTable_ && pos_ == other.pos_;
+    }
+
+    template <typename OtherT>
+    bool operator!=(const OtherT& other) const {
+      return flatTable_ != other.flatTable_ || pos_ != other.pos_;
+    }
+
+   private:
+    friend class FlatTable<FlatTableDelegate>;
+
+    FlatTableIterator(size_t pos, FlatTableType* flatTable)
+        : pos_(pos), flatTable_(flatTable) {
+      DCHECK(flatTable_);
+#ifndef NDEBUG
+      iterator_generation_ = flatTable_->iterator_generation_;
+#endif
+    }
+
+    size_t pos_;
+    FlatTableType* flatTable_;
+
+#ifndef NDEBUG
+    size_t iterator_generation_;
+#endif
+  };
+
+  using iterator = FlatTableIterator<ForwardIteratorDelegate<Delegate>>;
+  using const_iterator =
+      FlatTableIterator<ConstForwardIteratorDelegate<Delegate>>;
+  using reverse_iterator = FlatTableIterator<ReverseIteratorDelegate<Delegate>>;
+  using const_reverse_iterator =
+      FlatTableIterator<ConstReverseIteratorDelegate<Delegate>>;
+
+  // Inserts |value| into the map, invalidating any iterators.
+  // Returns a std::pair containing an iterator pointing to the inserted |value|
+  // and a boolean which is true if a new entry was inserted or false if an
+  // existing entry was overwritten.
+  // O(log n + n / 2)
+  std::pair<iterator, bool> insert(value_type value) {
+    if (empty()) {
+      ring_buffer_[back_] = std::move(value);
+      back_ = RingNext(back_);
+      search_step_size_ = 1;
+#ifndef NDEBUG
+      InvalidateIterators();
+#endif
+      return std::make_pair(iterator(front_, this), true);
+    }
+
+    size_t index;
+    if (BinarySearch(Delegate::ToKey(value), &index)) {
+      // Replace existing value.
+      ring_buffer_[index] = std::move(value);
+      return std::make_pair(iterator(index, this), false);
+    }
+
+    return std::make_pair(iterator(InsertUniqueImpl(std::move(value)), this),
+                          true);
+  }
+
+  // Inserts |value| into the map, whose key must be unique, invalidating any
+  // iterators. O(n / 2)
+  void insertUnique(value_type value) {
+    if (empty()) {
+      ring_buffer_[back_] = std::move(value);
+      back_ = RingNext(back_);
+      search_step_size_ = 1;
+
+#ifndef NDEBUG
+      InvalidateIterators();
+#endif
+      return;
+    }
+
+    InsertUniqueImpl(value);
+  }
+
+  // Erases an entry corresponding to |key|, if any, from the map.
+  // Invalidates any iterators. O(log n + n / 2)
+  size_t erase(const key_type& key) {
+    if (empty())
+      return 0;
+
+    size_t keyIndex;
+    if (!BinarySearch(key, &keyIndex))
+      return 0;
+
+    erase(iterator(keyIndex, this));
+    return 1u;
+  }
+
+  // Erases |it| from the map, invalidating any iterators. O(n / 2)
+  template <typename Iterator>
+  void erase(const Iterator& it) {
+    DCHECK_EQ(it.flatTable_, this);
+#ifndef NDEBUG
+    DCHECK_EQ(iterator_generation_, it.iterator_generation_);
+    key_type key = Delegate::ToKey(ring_buffer_[it.pos_]);
+#endif
+    if (it.pos_ == back_)
+      return;
+
+    DCHECK(ValidIndex(it.pos_)) << "it.pos_ = " << it.pos_;
+    size_t eraseFrontCost = RingDistance(front_, it.pos_);
+    size_t eraseBackCost = RingDistance(it.pos_, back_);
+
+    if (eraseFrontCost >= eraseBackCost) {
+      EraseByMovingBack(it.pos_);
+    } else {
+      EraseByMovingFront(it.pos_);
+    }
+
+    if (search_step_size_ > 1 && size() <= search_step_size_)
+      search_step_size_ /= 2;
+
+#ifndef NDEBUG
+    DCHECK(find(key) == end());
+    InvalidateIterators();
+#endif
+  }
+
+  // O(log n)
+  iterator find(const key_type& key) {
+    size_t keyIndex;
+    if (!BinarySearch(key, &keyIndex))
+      return end();
+
+    return iterator(keyIndex, this);
+  }
+
+  // O(log n)
+  const_iterator find(const key_type& key) const {
+    size_t keyIndex;
+    if (!BinarySearch(key, &keyIndex))
+      return end();
+
+    return iterator(keyIndex, this);
+  }
+
+  iterator begin() { return iterator(front_, this); }
+  iterator end() { return iterator(back_, this); }
+  const_iterator begin() const { return const_iterator(front_, this); }
+  const_iterator end() const { return const_iterator(back_, this); }
+
+  reverse_iterator rbegin() { return reverse_iterator(RingPrev(back_), this); }
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(RingPrev(back_), this);
+  }
+  reverse_iterator rend() { return reverse_iterator(RingPrev(front_), this); }
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(RingPrev(front_), this);
+  }
+
+ protected:
+  template <typename Iterator>
+  size_t IteratorPosition(const Iterator& it) const {
+    DCHECK_EQ(this, it.flatTable_);
+#ifndef NDEBUG
+    DCHECK_EQ(iterator_generation_, it.iterator_generation_);
+#endif
+    return it.pos_;
+  }
+
+  size_t InsertUniqueImpl(value_type value) {
+    // Grow the vector if needed.
+    if (RingNext(back_) == front_)
+      Grow();
+
+    // Shuffle Elements to make way for |value|.
+    size_t mid = (front_ + (size() / 2)) & modulus_mask_;
+    DCHECK(ValidIndex(mid)) << "mid = " << mid;
+    size_t i;
+    if (value < ring_buffer_[mid]) {
+      front_ = RingPrev(front_);
+      for (i = front_; ring_buffer_[RingNext(i)] < value; i = RingNext(i)) {
+        ring_buffer_[i] = std::move(ring_buffer_[RingNext(i)]);
+      }
+    } else {
+      DCHECK_LT(Delegate::ToKey(ring_buffer_[mid]), Delegate::ToKey(value));
+      for (i = back_; value < ring_buffer_[RingPrev(i)]; i = RingPrev(i)) {
+        ring_buffer_[i] = std::move(ring_buffer_[RingPrev(i)]);
+      }
+      back_ = RingNext(back_);
+    }
+
+    DCHECK(i == front_ || i == RingPrev(back_) || ring_buffer_[i] != value)
+        << "expected a unique key " << Delegate::ToKey(value);
+    ring_buffer_[i] = std::move(value);
+
+    if ((size() / 2) >= search_step_size_)
+      search_step_size_ *= 2;
+
+#ifndef NDEBUG
+    InvalidateIterators();
+#endif
+    return i;
+  }
+
+  void Grow() {
+    std::vector<value_type> new_buffer(ring_buffer_.size() * 2);
+    size_t old_back = back_;
+    back_ = 0;
+    for (size_t i = front_; i != old_back; i = RingNext(i)) {
+      new_buffer[back_++] = std::move(ring_buffer_[i]);
+    }
+    front_ = 0;
+    std::swap(ring_buffer_, new_buffer);
+    ComputeModulusMask();
+  }
+
+  bool BinarySearch(const key_type& key, size_t* index) const {
+    size_t low = front_;
+    for (size_t step_size = search_step_size_; step_size; step_size /= 2) {
+      size_t mid = low + step_size;
+      if (mid >= ContigiousBack())
+        continue;
+      if (!(key < Delegate::ToKey(ring_buffer_[mid & modulus_mask_]))) {
+        low = mid;
+      }
+    }
+    low &= modulus_mask_;
+    *index = low;
+    return key == Delegate::ToKey(ring_buffer_[low]);
+  }
+
+  void EraseByMovingFront(size_t index_to_erase) {
+    DCHECK(ValidIndex(index_to_erase)) << "index_to_erase = " << index_to_erase;
+    if (index_to_erase == front_) {
+      ring_buffer_[index_to_erase] = value_type();
+    }
+    for (size_t i = index_to_erase; i != front_; i = RingPrev(i)) {
+      ring_buffer_[i] = std::move(ring_buffer_[RingPrev(i)]);
+    }
+    front_ = RingNext(front_);
+  }
+
+  void EraseByMovingBack(size_t index_to_erase) {
+    DCHECK(ValidIndex(index_to_erase)) << "index_to_erase = " << index_to_erase;
+    size_t old_back = back_;
+    back_ = RingPrev(back_);
+    if (index_to_erase == back_) {
+      ring_buffer_[index_to_erase] = value_type();
+    }
+
+    for (size_t i = index_to_erase; i != old_back; i = RingNext(i)) {
+      ring_buffer_[i] = std::move(ring_buffer_[RingNext(i)]);
+    }
+  }
+
+  size_t RingPrev(size_t index) const { return (index - 1) & modulus_mask_; }
+
+  size_t RingNext(size_t index) const { return (index + 1) & modulus_mask_; }
+
+  // Returns true if |index| is within the active section of the ring buffer.
+  bool ValidIndex(size_t index) const {
+    if (back_ > front_)
+      return index >= front_ && index < back_;
+    return index <= back_ || (index >= front_ && index < ring_buffer_.size());
+  }
+
+  void ComputeModulusMask() {
+    DCHECK_EQ(0u, (ring_buffer_.size() & (ring_buffer_.size() - 1)))
+        << "ring_buffer_.size() must be a power of two.";
+
+    modulus_mask_ = ring_buffer_.size() - 1;
+  }
+
+  size_t ContigiousBack() const { return front_ + size(); }
+
+  // Computes how many positions |later_in_ring| is ahead of |earlier_in_ring|.
+  size_t RingDistance(size_t earlier_in_ring, size_t later_in_ring) const {
+    return (later_in_ring - earlier_in_ring) & modulus_mask_;
+  }
+
+#ifndef NDEBUG
+  void InvalidateIterators() { iterator_generation_++; }
+#endif
+
+  // The ring buffer is always a power of two in size, because computing
+  // modulus for powers of two is super fast.
+  std::vector<value_type> ring_buffer_;
+
+  // Since |ring_buffer_| is a power of two in size, we can compute the modulus
+  // using a bitwise and with |modulus_mask_|.
+  size_t modulus_mask_;
+
+  // The index of the first element.
+  size_t front_;
+
+  // The index of the last element + 1.
+  size_t back_;
+
+  // Equivalent to 2 ^ ceil(log2(size()) - 1).
+  size_t search_step_size_;
+
+#ifndef NDEBUG
+  // Used to check for stale iterators.
+  size_t iterator_generation_ = 0;
+#endif
+};
+
+}  // namespace WTF
+
+#endif  // WTF_FlatTable_h