Revert of [Reland] Optimize blink scheduler with an intrusive heap

third_party/WebKit/Source/platform/scheduler/base/intrusive_heap.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 THIRD_PARTY_WEBKIT_SOURCE_PLATFORM_SCHEDULER_BASE_INTRUSIVE_HEAP_H_
-#define THIRD_PARTY_WEBKIT_SOURCE_PLATFORM_SCHEDULER_BASE_INTRUSIVE_HEAP_H_
-
-#include <algorithm>
-#include <vector>
-
-#include "base/logging.h"
-
-namespace blink {
-namespace scheduler {
-
-template <typename T>
-class IntrusiveHeap;
-
-// Intended as an opaque wrapper around |index_|.
-class HeapHandle {
- public:
-  HeapHandle() : index_(0u) {}
-
-  bool IsValid() const { return index_ != 0u; }
-
- private:
-  template <typename T>
-  friend class IntrusiveHeap;
-
-  HeapHandle(size_t index) : index_(index) {}
-
-  size_t index_;
-};
-
-// A standard min-heap with the following assumptions:
-// 1. T has operator <=
-// 2. T has method void SetHeapHandle(HeapHandle handle)
-// 3. T is moveable
-// 4. T is default constructible
-// 5. The heap size never gets terribly big so reclaiming memory on pop/erase
-// isn't a priority.
-//
-// The reason IntrusiveHeap exists is to provide similar performance to
-// std::priority_queue while allowing removal of arbitrary elements.
-template <typename T>
-class IntrusiveHeap {
- public:
-  IntrusiveHeap() : nodes_(kMinimumHeapSize), size_(0) {}
-
-  bool empty() const { return size_ == 0; }
-
-  size_t size() const { return size_; }
-
-  void clear() {
-    nodes_.resize(kMinimumHeapSize);
-    size_ = 0;
-  }
-
-  const T& min() const {
-    DCHECK_GE(size_, 1u);
-    return nodes_[1];
-  }
-
-  void pop() {
-    DCHECK_GE(size_, 1u);
-    MakeHole(1u);
-    size_t top_index = size_--;
-    if (!empty())
-      MoveHoleDownAndFillWithLeafElement(1u, std::move(nodes_[top_index]));
-  }
-
-  void insert(T&& element) {
-    size_++;
-    if (size_ >= nodes_.size())
-      nodes_.resize(nodes_.size() * 2);
-    // Notionally we have a hole in the tree at index |size_|, move this up
-    // to find the right insertion point.
-    MoveHoleUpAndFillWithElement(size_, std::move(element));
-  }
-
-  void erase(HeapHandle handle) {
-    DCHECK_GT(handle.index_, 0u);
-    DCHECK_LE(handle.index_, size_);
-    MakeHole(handle.index_);
-    size_t top_index = size_--;
-    if (empty() || top_index == handle.index_)
-      return;
-    if (nodes_[handle.index_] <= nodes_[top_index]) {
-      MoveHoleDownAndFillWithLeafElement(handle.index_,
-                                         std::move(nodes_[top_index]));
-    } else {
-      MoveHoleUpAndFillWithElement(handle.index_, std::move(nodes_[top_index]));
-    }
-  }
-
-  void ReplaceMin(T&& element) {
-    // Note |element| might not be a leaf node so we can't use
-    // MoveHoleDownAndFillWithLeafElement.
-    MoveHoleDownAndFillWithElement(1u, std::move(element));
-  }
-
-  // Caution mutating the heap invalidates the iterators.
-  const T* begin() const { return &nodes_[1u]; }
-  const T* end() const { return begin() + size_; }
-
- private:
-  enum {
-    // The majority of sets in the scheduler have 0-3 items in them (a few will
-    // have perhaps up to 100), so this means we usually only have to allocate
-    // memory once.
-    kMinimumHeapSize = 4u
-  };
-
-  size_t MoveHole(size_t new_hole_pos, size_t old_hole_pos) {
-    DCHECK_GT(new_hole_pos, 0u);
-    DCHECK_LE(new_hole_pos, size_);
-    DCHECK_GT(new_hole_pos, 0u);
-    DCHECK_LE(new_hole_pos, size_);
-    DCHECK_NE(old_hole_pos, new_hole_pos);
-    nodes_[old_hole_pos] = std::move(nodes_[new_hole_pos]);
-    nodes_[old_hole_pos].SetHeapHandle(HeapHandle(old_hole_pos));
-    return new_hole_pos;
-  }
-
-  // Notionally creates a hole in the tree at |index|.
-  void MakeHole(size_t index) {
-    DCHECK_GT(index, 0u);
-    DCHECK_LE(index, size_);
-    nodes_[index].SetHeapHandle(HeapHandle(0u));
-  }
-
-  void FillHole(size_t hole, T&& element) {
-    DCHECK_GT(hole, 0u);
-    DCHECK_LE(hole, size_);
-    nodes_[hole] = std::move(element);
-    nodes_[hole].SetHeapHandle(HeapHandle(hole));
-    DCHECK(std::is_heap(begin(), end(), CompareNodes));
-  }
-
-  static bool CompareNodes(const T& a, const T& b) { return b <= a; }
-
-  // Moves the |hole| up the tree and when the right position has been found
-  // |element| is moved in.
-  void MoveHoleUpAndFillWithElement(size_t hole, T&& element) {
-    DCHECK_GT(hole, 0u);
-    DCHECK_LE(hole, size_);
-    while (hole >= 2u) {
-      size_t parent_pos = hole / 2;
-      if (nodes_[parent_pos] <= element)
-        break;
-
-      hole = MoveHole(parent_pos, hole);
-    }
-    FillHole(hole, std::move(element));
-  }
-
-  // Moves the |hole| down the tree and when the right position has been found
-  // |element| is moved in.
-  void MoveHoleDownAndFillWithElement(size_t hole, T&& element) {
-    DCHECK_GT(hole, 0u);
-    DCHECK_LE(hole, size_);
-    size_t child_pos = hole * 2;
-    while (child_pos < size_) {
-      if (nodes_[child_pos + 1] <= nodes_[child_pos])
-        child_pos++;
-
-      if (element <= nodes_[child_pos])
-        break;
-
-      hole = MoveHole(child_pos, hole);
-      child_pos *= 2;
-    }
-    if (child_pos == size_ && !(element <= nodes_[child_pos]))
-      hole = MoveHole(child_pos, hole);
-    FillHole(hole, std::move(element));
-  }
-
-  // Moves the |hole| down the tree and when the right position has been found
-  // |leaf_element| is moved in.  Faster than MoveHoleDownAndFillWithElement
-  // (it does one key comparison per level instead of two) but only valid for
-  // leaf elements (i.e. one of the max values).
-  void MoveHoleDownAndFillWithLeafElement(size_t hole, T&& leaf_element) {
-    DCHECK_GT(hole, 0u);
-    DCHECK_LE(hole, size_);
-    size_t child_pos = hole * 2;
-    while (child_pos < size_) {
-      size_t second_child = child_pos + 1;
-      if (nodes_[second_child] <= nodes_[child_pos])
-        child_pos = second_child;
-
-      hole = MoveHole(child_pos, hole);
-      child_pos *= 2;
-    }
-    if (child_pos == size_)
-      hole = MoveHole(child_pos, hole);
-    MoveHoleUpAndFillWithElement(hole, std::move(leaf_element));
-  }
-
-  std::vector<T> nodes_;  // NOTE we use 1-based indexing
-  size_t size_;
-};
-
-}  // namespace scheduler
-}  // namespace blink
-
-#endif  // THIRD_PARTY_WEBKIT_SOURCE_PLATFORM_SCHEDULER_BASE_INTRUSIVE_HEAP_H_