components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/ranked_list.h

+// 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.
+
+#ifndef COMPONENTS_METRICS_LEAK_DETECTOR_RANKED_LIST_H_
+#define COMPONENTS_METRICS_LEAK_DETECTOR_RANKED_LIST_H_
+
+#include <stdint.h>
+
+#include <vector>
+
+#include "components/metrics/leak_detector/leak_detector_value_type.h"
+#include "components/metrics/leak_detector/stl_allocator.h"
+#include <gperftools/custom_allocator.h>
+
+// RankedList lets you add entries and automatically sorts them internally, so
+// they can be accessed in sorted order. The entries are stored as a vector
+// array.
+
+namespace leak_detector {
+
+class RankedList {

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

This name is IMO slightly deceptive. A "list" usually means (to me?) a linked
(or doubly-linked) list.  This data structure is really a vector, with all the
complexity that entails (when adding members).  If you want to keep this name,
you should at *least* surface this fact in the method comments (as noted below).

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

I'm going to rethink this entire implementation and perhaps make it a STL list
instead.

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

Done.

+ public:
+  using ValueType = LeakDetectorValueType;
+
+  // A single entry in the RankedList. The RankedList sorts entries by |count|.
+  struct Entry {
+    int count;
+    ValueType value;
+  };
+
+  explicit RankedList(size_t max_size) : max_size_(max_size) {
+    entries_.reserve(max_size + 1);
+  }
+  ~RankedList() {}
+
+  // Access individual element. Does not do boundary checking.
+  const Entry& entry(int index) const {
+    return entries_[index];
+  }
+
+  size_t size() const {
+    return entries_.size();
+  }
+
+  // Add a new value-count pair to the list. Does not check for existing entries
+  // with the same value.

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

nit: Add comment that this is an O(N) insertion into a vector.

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

Now a O(1) insertion into a linked list. :)

[Simon Que, 2015/08/31 05:47:03]

Actually that's wrong... it's O(N) due to ordering.

OTOH, the new implementation makes it trivial to replace the list with a
std::set if necessary.

+  void Add(const ValueType& value, int count);
+
+ private:
+  // Returns the position to insert a new value. Returns -1 if it cannot be
+  // inserted.
+  int GetInsertionIndex(int count) const;

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

nit: Add comment that this is a binary search, of complexity O(log(N)).

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

Removed this function, replaced with upper_bound (linear search of ranked list)

+
+  // Max and min counts. Returns 0 if the list is empty.
+  const int max_count() const {
+    return entries_.empty() ? 0 : entries_[0].count;
+  }
+  const int min_count() const {
+    return entries_.empty() ? 0 : entries_[size() - 1].count;
+  }
+
+  // Max number of items in the list.
+  size_t max_size_;
+
+  // Points to the array of entries.
+  std::vector<Entry, STL_Allocator<Entry, CustomAllocator>> entries_;
+};
+
+}  // namespace leak_detector
+
+#endif  // COMPONENTS_METRICS_LEAK_DETECTOR_RANKED_LIST_H_