-
/*
- * $Id: StatHist.cc,v 1.18 1998/10/19 22:36:56 wessels Exp $
- *
- * DEBUG: section 62 Generic Histogram
- * AUTHOR: Duane Wessels
- *
- * SQUID Internet Object Cache http://squid.nlanr.net/Squid/
- * ----------------------------------------------------------
- *
- * Squid is the result of efforts by numerous individuals from the
- * Internet community. Development is led by Duane Wessels of the
- * National Laboratory for Applied Network Research and funded by the
- * National Science Foundation. Squid is Copyrighted (C) 1998 by
- * Duane Wessels and the University of California San Diego. Please
- * see the COPYRIGHT file for full details. Squid incorporates
- * software developed and/or copyrighted by other sources. Please see
- * the CREDITS file for full details.
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
+ * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
*
+ * Squid software is distributed under GPLv2+ license and includes
+ * contributions from numerous individuals and organizations.
+ * Please see the COPYING and CONTRIBUTORS files for details.
*/
-/*
- * Important restrictions on val_in and val_out functions:
- *
- * - val_in: ascending, defined on [0, oo), val_in(0) == 0;
- * - val_out: x == val_out(val_in(x)) where val_in(x) is defined
- *
- * In practice, the requirements are less strict,
- * but then it gets hard to define them without math notation.
- * val_in is applied after offseting the value but before scaling
- * See log and linear based histograms for examples
- */
+/* DEBUG: section 62 Generic Histogram */
#include "squid.h"
+#include "StatHist.h"
+
+#include <cmath>
/* Local functions */
-static void statHistInit(StatHist * H, int capacity, hbase_f * val_in, hbase_f * val_out, double min, double max);
-static int statHistBin(const StatHist * H, double v);
-static double statHistVal(const StatHist * H, int bin);
static StatHistBinDumper statHistBinDumper;
-static hbase_f Log;
-static hbase_f Exp;
-static hbase_f Null;
-/* low level init, higher level functions has less params */
-static void
-statHistInit(StatHist * H, int capacity, hbase_f * val_in, hbase_f * val_out, double min, double max)
+namespace Math
{
- assert(H);
- assert(capacity > 0);
- assert(val_in && val_out);
- /* check before we divide to get scale */
- assert(val_in(max - min) > 0);
- H->bins = xcalloc(capacity, sizeof(int));
- H->min = min;
- H->max = max;
- H->capacity = capacity;
- H->scale = capacity / val_in(max - min);
- H->val_in = val_in;
- H->val_out = val_out;
- /* check that functions are valid */
- /* a min value should go into bin[0] */
- assert(statHistBin(H, min) == 0);
- /* a max value should go into the last bin */
- assert(statHistBin(H, max) == H->capacity - 1);
- /* it is hard to test val_out, here is a crude test */
- assert(((int) (0.99 + statHistVal(H, 0) - min)) == 0);
-}
+hbase_f Log;
+hbase_f Exp;
+hbase_f Null;
+};
+/* low level init, higher level functions has less params */
void
-statHistClean(StatHist * H)
-{
- xfree(H->bins);
- H->bins = NULL;
+StatHist::init(unsigned int newCapacity, hbase_f * val_in_, hbase_f * val_out_, double newMin, double newMax)
+{
+ /* check before we divide to get scale_ */
+ assert(val_in_(newMax - newMin) > 0);
+ min_ = newMin;
+ max_ = newMax;
+ capacity_ = newCapacity;
+ val_in = val_in_;
+ val_out = val_out_;
+ bins = static_cast<bins_type *>(xcalloc(capacity_, sizeof(bins_type)));
+ scale_ = capacity_ / val_in(max_ - min_);
+}
+
+StatHist::StatHist(const StatHist &src) :
+ capacity_(src.capacity_), min_(src.min_), max_(src.max_),
+ scale_(src.scale_), val_in(src.val_in), val_out(src.val_out)
+{
+ if (src.bins!=NULL) {
+ bins = static_cast<bins_type *>(xcalloc(src.capacity_, sizeof(bins_type)));
+ memcpy(bins,src.bins,capacity_*sizeof(*bins));
+ }
}
-/* assumes that somebody already called init for Dest */
void
-statHistCopy(StatHist * Dest, const StatHist * Orig)
+StatHist::count(double v)
{
- assert(Dest);
- assert(Orig);
- debug(62, 3) ("statHistCopy: Dest=%p, Orig=%p\n", Dest, Orig);
- assert(Dest->bins);
- /* better be safe than sorry */
- debug(62, 3) ("statHistCopy: capacity %d %d\n",
- Dest->capacity, Orig->capacity);
- assert(Dest->capacity == Orig->capacity);
- debug(62, 3) ("statHistCopy: min %f %f\n", Dest->min, Orig->min);
- assert(Dest->min == Orig->min);
- debug(62, 3) ("statHistCopy: max %f %f\n", Dest->max, Orig->max);
- assert(Dest->max == Orig->max);
- debug(62, 3) ("statHistCopy: scale %f %f\n", Dest->scale, Orig->scale);
- assert(Dest->scale == Orig->scale);
- assert(Dest->val_in == Orig->val_in);
- assert(Dest->val_out == Orig->val_out);
- /* actual copy */
- debug(62, 3) ("statHistCopy: copying %d bytes to %p from %p\n",
- Dest->capacity * sizeof(*Dest->bins),
- Dest->bins,
- Orig->bins);
- xmemcpy(Dest->bins, Orig->bins, Dest->capacity * sizeof(*Dest->bins));
+ if (bins==NULL) //do not count before initialization or after destruction
+ return;
+ const unsigned int bin = findBin(v);
+ ++bins[bin];
}
-/*
- * same as statHistCopy but will do nothing if capacities do not match; the
- * latter happens, for example, when #peers changes during reconfiguration;
- * if it happens too often we should think about more general solution..
- */
-void
-statHistSafeCopy(StatHist * Dest, const StatHist * Orig)
+unsigned int
+StatHist::findBin(double v)
{
- assert(Dest && Orig);
- assert(Dest->bins);
- if (Dest->capacity == Orig->capacity)
- statHistCopy(Dest, Orig);
+
+ v -= min_; /* offset */
+
+ if (v <= 0.0) /* too small */
+ return 0;
+
+ unsigned int bin;
+ double tmp_bin=floor(scale_ * val_in(v) + 0.5);
+
+ if (tmp_bin < 0.0) // should not happen
+ return 0;
+ bin = static_cast <unsigned int>(tmp_bin);
+
+ if (bin >= capacity_) /* too big */
+ bin = capacity_ - 1;
+
+ return bin;
}
-void
-statHistCount(StatHist * H, double val)
+double
+StatHist::val(unsigned int bin) const
{
- const int bin = statHistBin(H, val);
- assert(H->bins); /* make sure it got initialized */
- assert(0 <= bin && bin < H->capacity);
- H->bins[bin]++;
+ return val_out((double) bin / scale_) + min_;
}
-static int
-statHistBin(const StatHist * H, double v)
+double
+statHistDeltaMedian(const StatHist & A, const StatHist & B)
{
- int bin;
-#if BROKEN_STAT_HIST_BIN
- return 0;
- /* NOTREACHED */
-#endif
- v -= H->min; /* offset */
- if (v <= 0.0) /* too small */
- return 0;
- bin = (int) (H->scale * H->val_in(v) + 0.5);
- if (bin < 0) /* should not happen */
- bin = 0;
- if (bin >= H->capacity) /* too big */
- bin = H->capacity - 1;
- return bin;
+ return statHistDeltaPctile(A, B, 0.5);
}
-static double
-statHistVal(const StatHist * H, int bin)
+double
+statHistDeltaPctile(const StatHist & A, const StatHist & B, double pctile)
{
- return H->val_out(bin / H->scale) + H->min;
+ return A.deltaPctile(B, pctile);
}
double
-statHistDeltaMedian(const StatHist * A, const StatHist * B)
-{
- int i;
- int s1 = 0;
- int h = 0;
- int a = 0;
- int b = 0;
- int I = 0;
- int J = A->capacity;
- int K;
+StatHist::deltaPctile(const StatHist & B, double pctile) const
+{
+ unsigned int i;
+ bins_type s1 = 0;
+ bins_type h = 0;
+ bins_type a = 0;
+ bins_type b = 0;
+ unsigned int I = 0;
+ unsigned int J = capacity_;
+ unsigned int K;
double f;
- int *D = xcalloc(A->capacity, sizeof(int));
- assert(A->capacity == B->capacity);
- for (i = 0; i < A->capacity; i++) {
- D[i] = B->bins[i] - A->bins[i];
- assert(D[i] >= 0);
+
+ assert(capacity_ == B.capacity_);
+
+ int *D = static_cast<int *>(xcalloc(capacity_, sizeof(int)));
+
+ for (i = 0; i < capacity_; ++i) {
+ D[i] = B.bins[i] - bins[i];
+ assert(D[i] >= 0);
}
- for (i = 0; i < A->capacity; i++)
- s1 += D[i];
- h = s1 >> 1;
- for (i = 0; i < A->capacity; i++) {
- J = i;
- b += D[J];
- if (a <= h && h <= b)
- break;
- I = i;
- a += D[I];
+
+ for (i = 0; i < capacity_; ++i)
+ s1 += D[i];
+
+ h = int(s1 * pctile);
+
+ for (i = 0; i < capacity_; ++i) {
+ J = i;
+ b += D[J];
+
+ if (a <= h && h <= b)
+ break;
+
+ I = i;
+
+ a += D[I];
}
+
xfree(D);
+
if (s1 == 0)
- return 0.0;
+ return 0.0;
+
if (a > h)
- return 0.0;
+ return 0.0;
+
if (a >= b)
- return 0.0;
+ return 0.0;
+
if (I >= J)
- return 0.0;
+ return 0.0;
+
f = (h - a) / (b - a);
- K = (int) (f * (double) (J - I) + I);
- return statHistVal(A, K);
+
+ K = (unsigned int) floor(f * (double) (J - I) + I);
+
+ return val(K);
}
static void
statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count)
{
if (count)
- storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n",
- idx, val, count, count / size);
+ storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n",
+ idx, val, count, count / size);
}
void
-statHistDump(const StatHist * H, StoreEntry * sentry, StatHistBinDumper * bd)
+StatHist::dump(StoreEntry * sentry, StatHistBinDumper * bd) const
{
- int i;
- double left_border = H->min;
+ double left_border = min_;
+
if (!bd)
- bd = statHistBinDumper;
- for (i = 0; i < H->capacity; i++) {
- const double right_border = statHistVal(H, i + 1);
- assert(right_border - left_border > 0.0);
- bd(sentry, i, left_border, right_border - left_border, H->bins[i]);
- left_border = right_border;
+ bd = statHistBinDumper;
+
+ for (unsigned int i = 0; i < capacity_; ++i) {
+ const double right_border = val(i + 1);
+ assert(right_border - left_border > 0.0);
+ bd(sentry, i, left_border, right_border - left_border, bins[i]);
+ left_border = right_border;
}
}
+StatHist &
+StatHist::operator += (const StatHist &B)
+{
+ Must(capacity_ == B.capacity_);
+ Must(min_ == B.min_);
+ Must(max_ == B.max_);
+
+ if (B.bins == NULL) { // B was not yet initializted
+ return *this;
+ }
+ if (bins == NULL) { // this histogram was not yet initialized
+ *this = B;
+ return *this;
+ }
+ for (unsigned int i = 0; i < capacity_; ++i) {
+ bins[i] += B.bins[i];
+ }
+ return *this;
+}
+
/* log based histogram */
-static double
-Log(double x)
+double
+Math::Log(double x)
{
assert((x + 1.0) >= 0.0);
return log(x + 1.0);
}
-static double
-Exp(double x)
+
+double
+Math::Exp(double x)
{
return exp(x) - 1.0;
}
+
void
-statHistLogInit(StatHist * H, int capacity, double min, double max)
+StatHist::logInit(unsigned int capacity, double min, double max)
{
- statHistInit(H, capacity, Log, Exp, min, max);
+ init(capacity, Math::Log, Math::Exp, min, max);
}
/* linear histogram for enums */
/* we want to be have [-1,last_enum+1] range to track out of range enums */
-static double
-Null(double x)
+double
+Math::Null(double x)
{
return x;
}
void
-statHistEnumInit(StatHist * H, int last_enum)
+StatHist::enumInit(unsigned int last_enum)
{
- statHistInit(H, last_enum + 3, Null, Null, (double) -1, (double) (last_enum + 1 + 1));
+ init(last_enum + 3, Math::Null, Math::Null, -1.0, (2.0 + last_enum));
}
void
-statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count)
+statHistEnumDumper(StoreEntry * sentry, int idx, double val, double, int count)
{
if (count)
- storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n",
- idx, (int) val, count);
-}
-
-void
-statHistIntInit(StatHist * H, int n)
-{
- statHistInit(H, n, Null, Null, 0, n - 1);
+ storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n",
+ idx, (int) val, count);
}
void
-statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count)
+statHistIntDumper(StoreEntry * sentry, int, double val, double, int count)
{
if (count)
- storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count);
+ storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count);
}
+
projects / thirdparty / squid.git / blobdiff