components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/ranked_list.cc

Index: components/metrics/leak_detector/ranked_list.cc
diff --git a/components/metrics/leak_detector/ranked_list.cc b/components/metrics/leak_detector/ranked_list.cc
new file mode 100644
index 0000000000000000000000000000000000000000..4ac48a15a50d01dfa8a9456f6f0126d0ea4ccbe0
--- /dev/null
+++ b/components/metrics/leak_detector/ranked_list.cc
@@ -0,0 +1,53 @@
+// 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_)

[jar (doing other things), 2015/08/21 02:48:43]

Wouldn't this test be better (with slight adjustment) before line 15, so that we
avoid potentially reallocating (larger than the reserved size)?

[Simon Que, 2015/08/23 23:30:53]

No longer an issue with list implementation.

+    entries_.resize(max_size_);
+}
+
+int RankedList::GetInsertionIndex(int count) const {

[jar (doing other things), 2015/08/21 02:48:43]

Have you considered using std::binary_search?

There are a lot of ways to write this code incorrectly... not dealing with
underflows, overflows, or edge conditions... and it is much easier to use (the
faster) standard function.

On the other hand.... given that (I think) you routinely do numerous O(N)
operations when you do a binary search (before and after), I bet a linear search
would be about as efficient.

[Simon Que, 2015/08/21 05:44:05]

Yes I could consider a linear search.

[Simon Que, 2015/08/23 23:30:53]

Replaced with std::upper_bound.

+  // 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.

[jar (doing other things), 2015/08/21 02:48:43]

nit: undent

[Simon Que, 2015/08/21 21:59:20]

Done.

+  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