Add SampleMap and use it in SparseHistogram

base/metrics/sample_map.cc

Index: base/metrics/sample_map.cc
diff --git a/base/metrics/sample_map.cc b/base/metrics/sample_map.cc
new file mode 100644
index 0000000000000000000000000000000000000000..1c2b073ffe9c322c64d8b3c79c3f0d114f90093b
--- /dev/null
+++ b/base/metrics/sample_map.cc
@@ -0,0 +1,93 @@
+// Copyright (c) 2012 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 "base/metrics/sample_map.h"
+
+#include "base/logging.h"
+
+using std::map;
+
+namespace base {
+
+typedef HistogramBase::Count Count;
+typedef HistogramBase::Sample Sample;
+
+SampleMap::SampleMap() {}
+
+SampleMap::~SampleMap() {}
+
+void SampleMap::Accumulate(Sample value, Count count) {
+  base::AutoLock auto_lock(lock_);
+  sample_counts_[value] += count;
+  IncreaseSum(count * value);
+  IncreaseRedundantCount(count);
+}
+
+Count SampleMap::GetCount(Sample value) const {

[jar (doing other things), 2012/10/02 17:41:11]

This is a surprising API.  I would assume that you get the list of values by
iterating over the map.... but then it is surprising to (after releasing the
lock) see to look at the associated values.  

I'm becoming suspicious that for the lifetime of the iterator, the lock should
be held by the iterator, to prevent the map from changing during the iterations.

To say it another way... I'm wondering if the pulling of the iterator class out
makes sense, or whether it should *only* be used within the map class for
introspection and copying.  Perhaps the iterator should not be long lived, and
should only exist for the duration of one acquisition and release of the lock.

+  base::AutoLock auto_lock(lock_);
+  map<Sample, Count>::const_iterator it = sample_counts_.find(value);
+  if (it == sample_counts_.end())
+    return 0;
+  return it->second;
+}
+
+Count SampleMap::TotalCount() const {

[jar (doing other things), 2012/10/02 17:41:11]

Note that this approach, of gathering the total count under a lock, produces a
result that can't be compared with the RedundantCount.

To make them comparable, you must gather all stats under one acquisition of the
lock.

I think you can live with this... but it was a little surprising to me (I
envisioned that once we took the expense of using a lock, we'd have perfect
synchronization (except for when we got overwritten by memory smashers).

+  Count count = 0;
+
+  base::AutoLock auto_lock(lock_);
+  for (map<Sample, Count>::const_iterator it = sample_counts_.begin();
+       it != sample_counts_.end();
+       ++it) {
+    count += it->second;
+  }
+  return count;
+}
+
+scoped_ptr<SampleCountIterator> SampleMap::Iterator() const {

[jar (doing other things), 2012/10/02 17:41:11]

This is the scary interface.  We're giving away an iterator to a data structure
that is lock protected... and we don't hold the lock.  The iterator can become
invalid at any point now :-(.

+  return scoped_ptr<SampleCountIterator>(new SampleMapIterator(sample_counts_));
+}
+
+bool SampleMap::AddSubtractImpl(SampleCountIterator* iter,
+                                HistogramSamples::Instruction instruction) {
+  Sample min;
+  Sample max;
+  Count count;
+
+  base::AutoLock auto_lock(lock_);
+  for (; !iter->Done(); iter->Next()) {
+    iter->Get(&min, &max, &count);
+    if (min + 1 != max)
+      return false;  // SparseHistogram only supports bucket with size 1.
+    sample_counts_[min] +=
+        (instruction ==  HistogramSamples::ADD) ? count : -count;
+  }
+  return true;
+}
+
+SampleMapIterator::SampleMapIterator(const map<Sample, Count>& sample_counts)
+    : iter_(sample_counts.begin()),
+      end_(sample_counts.end()) {}
+
+SampleMapIterator::~SampleMapIterator() {}
+
+bool SampleMapIterator::Done() const {
+  return iter_ == end_;
+}
+
+void SampleMapIterator::Next() {
+  DCHECK(!Done());
+  iter_++;
+}
+
+void SampleMapIterator::Get(Sample* min, Sample* max, Count* count) const {
+  DCHECK(!Done());
+  if (min != NULL)
+    *min = iter_->first;
+  if (max != NULL)
+    *max = iter_->first + 1;
+  if (count != NULL)
+    *count = iter_->second;
+}
+
+}  // namespace base