components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/ranked_list.cc

+// Copyright 2015 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.
+
+#include "components/metrics/leak_detector/ranked_list.h"
+
+namespace leak_detector {
+
+void RankedList::Add(const ValueType& value, int count) {
+  // Determine where to insert the value.
+  int index = GetInsertionIndex(count);
+  if (index == -1)
+    return;
+
+  entries_.emplace(entries_.begin() + index, Entry({count, value}));
+
+  // Limit the list size if it exceeds the maximum allowed size.
+  if (entries_.size() > max_size_)
+    entries_.resize(max_size_);
+}
+
+int RankedList::GetInsertionIndex(int count) const {
+  // If the list is full, do not add any entry with |count| if does not exceed
+  // the lowest count of the entries in the list.
+  if (size() == max_size_ && count <= min_count())
+    return -1;
+  // If larger than the current largest item, insert it before.
+  if (count >= max_count())
+    return 0;
+  // If smaller than the current smallest item, but the list is not full,
+  // insert it after.
+  if (count <= min_count())
+    return size();
+
+    // Otherwise it's somewhere in the middle, so look for it there.
+  int min_pos = 0;
+  int max_pos = size() - 1;
+  while (max_pos >= min_pos) {
+    int midpoint = (max_pos + min_pos) / 2;
+    if (count >= entries_[midpoint].count &&
+        count <= entries_[midpoint - 1].count) {
+      return midpoint;
+    }
+    // The list is reverse sorted.
+    if (entries_[midpoint].count >= count)
+      min_pos = midpoint + 1;
+    else
+      max_pos = midpoint - 1;
+  }
+  return max_pos;
+}
+
+}  // namespace leak_detector