components/metrics: Add runtime memory leak detector

third_party/tcmalloc/chromium/src/ranked_list.h

+// Copyright (c) 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.
+
+// ---
+// Author: Simon Que
+
+#ifndef _RANKED_LIST_H_
+#define _RANKED_LIST_H_
+
+#include <cstdio>
+#include <cstring>
+
+#include "base/basictypes.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 {
+
+template <typename T>
+class RankedList {
+ public:
+  typedef void* (*Allocator)(size_t size);
+  typedef void  (*DeAllocator)(void* ptr);
+
+  // A single entry in the RankedList. The RankedList sorts entries by |count|.
+  struct Entry {
+    int count;
+    T value;
+  };
+
+  RankedList(int max_size, Allocator alloc, DeAllocator dealloc);
+  ~RankedList();
+
+  RankedList& operator=(const RankedList& other);
+
+  // Access the array of entries.
+  const Entry* entries() const {
+    return entries_;
+  }
+  // Access individual element. Does not do boundary checking.
+  const Entry& entry(int index) const {
+    return entries_[index];
+  }
+  const int size() const {
+    return size_;
+  }
+
+  // Add a new value-count pair to the list. Does not check for existing entries
+  // with the same value.
+  void Add(const T& value, int count);
+
+ private:
+  // Returns the position to insert a new value. Returns -1 if it cannot be
+  // inserted.
+  int GetInsertionIndex(int count) const;
+
+  // Max and min counts.
+  const int max_count() const {
+    if (size_ == 0)
+      return 0;
+    return entries_[0].count;
+  }
+  const int min_count() const {
+    if (size_ == 0)
+      return 0;
+    return entries_[size_ - 1].count;
+  }
+
+  // For memory allocation.
+  Allocator alloc_;
+  DeAllocator dealloc_;
+
+  // Max items in the list.
+  int max_size_;
+
+  // The current number of items in the list.
+  int size_;
+
+  // Points to the array of entries.
+  Entry* entries_;
+};
+
+template <typename T>
+RankedList<T>::RankedList(int max_size, Allocator alloc, DeAllocator dealloc)
+    : alloc_(alloc),
+      dealloc_(dealloc),
+      max_size_(max_size),
+      size_(0) {
+  // Allocate array of elements, with an extra element at end as an overflow
+  // bucket.
+  size_t entries_size = sizeof(Entry) * (max_size + 1);
+  entries_ = static_cast<Entry*>(alloc_(entries_size));
+  memset(entries_, 0, entries_size);
+}
+
+template <typename T>
+RankedList<T>::~RankedList() {
+  dealloc_(entries_);
+  entries_ = NULL;
+}
+
+template <typename T>
+RankedList<T>& RankedList<T>::operator=(const RankedList<T>& other) {
+  // Delete currently allocated memory.
+  dealloc_(entries_);
+  entries_ = NULL;
+
+  // Allocate the space for the new data.
+  max_size_ = other.max_size_;
+  size_t entries_size = sizeof(Entry) * (max_size_ + 1);
+  entries_ = static_cast<Entry*>(alloc_(entries_size));
+  memset(entries_, 0, entries_size);
+
+  // Copy over the new data.
+  size_ = other.size_;
+  memcpy(entries_, other.entries_, sizeof(Entry) * size_);
+}
+
+template <typename T>
+void RankedList<T>::Add(const T& value, int count) {
+  // Determine where to insert the value.
+  int index = GetInsertionIndex(count);
+  if (index == -1)
+    return;
+  // Shift the other elements down. Use memmove to deal with source/dest
+  // overlaps.
+  memmove(&entries_[index + 1], &entries_[index],
+          (size_ - index) * sizeof(Entry));
+  // Finally, insert the new entry.
+  entries_[index].count = count;
+  entries_[index].value = value;
+  // Update size.
+  if (size_ < max_size_)
+    ++size_;
+}
+
+template <typename T>
+int RankedList<T>::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
+
+#endif  // _RANKED_LIST_H_