Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

129 lines (107 sloc) 4.016 kb
// histogram.h
/**
* Copyright (C) 2008 10gen Inc.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License, version 3,
* as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef UTIL_HISTOGRAM_HEADER
#define UTIL_HISTOGRAM_HEADER
#include "../pch.h"
#include <string>
namespace mongo {
using std::string;
/**
* A histogram for a 32-bit integer range.
*/
class Histogram {
public:
/**
* Construct a histogram with 'numBuckets' buckets, optionally
* having the first bucket start at 'initialValue' rather than
* 0. By default, the histogram buckets will be 'bucketSize' wide.
*
* Usage example:
* Histogram::Options opts;
* opts.numBuckets = 3;
* opts.bucketSize = 10;
* Histogram h( opts );
*
* Generates the bucket ranges [0..10],[11..20],[21..max_int]
*
* Alternatively, the flag 'exponential' could be turned on, in
* which case a bucket's maximum value will be
* initialValue + bucketSize * 2 ^ [0..numBuckets-1]
*
* Usage example:
* Histogram::Options opts;
* opts.numBuckets = 4;
* opts.bucketSize = 125;
* opts.exponential = true;
* Histogram h( opts );
*
* Generates the bucket ranges [0..125],[126..250],[251..500],[501..max_int]
*/
struct Options {
boost::uint32_t numBuckets;
boost::uint32_t bucketSize;
boost::uint32_t initialValue;
// use exponential buckets?
bool exponential;
Options()
: numBuckets(0)
, bucketSize(0)
, initialValue(0)
, exponential(false){}
};
explicit Histogram( const Options& opts );
~Histogram();
/**
* Find the bucket that 'element' falls into and increment its count.
*/
void insert( boost::uint32_t element );
/**
* Render the histogram as string that can be used inside an
* HTML doc.
*/
string toHTML() const;
// testing interface below -- consider it private
/**
* Return the count for the 'bucket'-th bucket.
*/
boost::uint64_t getCount( boost::uint32_t bucket ) const;
/**
* Return the maximum element that would fall in the
* 'bucket'-th bucket.
*/
boost::uint32_t getBoundary( boost::uint32_t bucket ) const;
/**
* Return the number of buckets in this histogram.
*/
boost::uint32_t getBucketsNum() const;
private:
/**
* Returns the bucket where 'element' should fall
* into. Currently assumes that 'element' is greater than the
* minimum 'inialValue'.
*/
boost::uint32_t _findBucket( boost::uint32_t element ) const;
boost::uint32_t _initialValue; // no value lower than it is recorded
boost::uint32_t _numBuckets; // total buckets in the histogram
// all below owned here
boost::uint32_t* _boundaries; // maximum element of each bucket
boost::uint64_t* _buckets; // current count of each bucket
Histogram( const Histogram& );
Histogram& operator=( const Histogram& );
};
} // namespace mongo
#endif // UTIL_HISTOGRAM_HEADER
Jump to Line
Something went wrong with that request. Please try again.