3 * $Id: StatHist.cc,v 1.25 2001/01/12 00:37:14 wessels Exp $
5 * DEBUG: section 62 Generic Histogram
6 * AUTHOR: Duane Wessels
8 * SQUID Web Proxy Cache http://www.squid-cache.org/
9 * ----------------------------------------------------------
11 * Squid is the result of efforts by numerous individuals from
12 * the Internet community; see the CONTRIBUTORS file for full
13 * details. Many organizations have provided support for Squid's
14 * development; see the SPONSORS file for full details. Squid is
15 * Copyrighted (C) 2001 by the Regents of the University of
16 * California; see the COPYRIGHT file for full details. Squid
17 * incorporates software developed and/or copyrighted by other
18 * sources; see the CREDITS file for full details.
20 * This program is free software; you can redistribute it and/or modify
21 * it under the terms of the GNU General Public License as published by
22 * the Free Software Foundation; either version 2 of the License, or
23 * (at your option) any later version.
25 * This program is distributed in the hope that it will be useful,
26 * but WITHOUT ANY WARRANTY; without even the implied warranty of
27 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 * GNU General Public License for more details.
30 * You should have received a copy of the GNU General Public License
31 * along with this program; if not, write to the Free Software
32 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
37 * Important restrictions on val_in and val_out functions:
39 * - val_in: ascending, defined on [0, oo), val_in(0) == 0;
40 * - val_out: x == val_out(val_in(x)) where val_in(x) is defined
42 * In practice, the requirements are less strict,
43 * but then it gets hard to define them without math notation.
44 * val_in is applied after offseting the value but before scaling
45 * See log and linear based histograms for examples
51 static void statHistInit(StatHist
* H
, int capacity
, hbase_f
* val_in
, hbase_f
* val_out
, double min
, double max
);
52 static int statHistBin(const StatHist
* H
, double v
);
53 static double statHistVal(const StatHist
* H
, int bin
);
54 static StatHistBinDumper statHistBinDumper
;
55 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
57 * HP-UX and GCC (2.8?) give strange errors when these simple
58 * functions are static.
65 /* low level init, higher level functions has less params */
67 statHistInit(StatHist
* H
, int capacity
, hbase_f
* val_in
, hbase_f
* val_out
, double min
, double max
)
71 assert(val_in
&& val_out
);
72 /* check before we divide to get scale */
73 assert(val_in(max
- min
) > 0);
74 H
->bins
= xcalloc(capacity
, sizeof(int));
77 H
->capacity
= capacity
;
78 H
->scale
= capacity
/ val_in(max
- min
);
82 /* HPUX users: If you get one of the assertions below, please send
83 * [at least] the values of all variables involved in the assertions
84 * when reporting a bug!
87 /* check that functions are valid */
88 /* a min value should go into bin[0] */
89 assert(statHistBin(H
, min
) == 0);
90 /* a max value should go into the last bin */
91 assert(statHistBin(H
, max
) == H
->capacity
- 1);
92 /* it is hard to test val_out, here is a crude test */
93 assert(((int) floor(0.99L + statHistVal(H
, 0) - min
)) == 0);
97 statHistClean(StatHist
* H
)
103 /* assumes that somebody already called init for Dest */
105 statHistCopy(StatHist
* Dest
, const StatHist
* Orig
)
109 debug(62, 3) ("statHistCopy: Dest=%p, Orig=%p\n", Dest
, Orig
);
111 /* better be safe than sorry */
112 debug(62, 3) ("statHistCopy: capacity %d %d\n",
113 Dest
->capacity
, Orig
->capacity
);
114 assert(Dest
->capacity
== Orig
->capacity
);
115 debug(62, 3) ("statHistCopy: min %f %f\n", Dest
->min
, Orig
->min
);
116 assert(Dest
->min
== Orig
->min
);
117 debug(62, 3) ("statHistCopy: max %f %f\n", Dest
->max
, Orig
->max
);
118 assert(Dest
->max
== Orig
->max
);
119 debug(62, 3) ("statHistCopy: scale %f %f\n", Dest
->scale
, Orig
->scale
);
120 assert(Dest
->scale
== Orig
->scale
);
121 assert(Dest
->val_in
== Orig
->val_in
);
122 assert(Dest
->val_out
== Orig
->val_out
);
124 debug(62, 3) ("statHistCopy: copying %d bytes to %p from %p\n",
125 Dest
->capacity
* sizeof(*Dest
->bins
),
128 xmemcpy(Dest
->bins
, Orig
->bins
, Dest
->capacity
* sizeof(*Dest
->bins
));
132 * same as statHistCopy but will do nothing if capacities do not match; the
133 * latter happens, for example, when #peers changes during reconfiguration;
134 * if it happens too often we should think about more general solution..
137 statHistSafeCopy(StatHist
* Dest
, const StatHist
* Orig
)
139 assert(Dest
&& Orig
);
141 if (Dest
->capacity
== Orig
->capacity
)
142 statHistCopy(Dest
, Orig
);
146 statHistCount(StatHist
* H
, double val
)
148 const int bin
= statHistBin(H
, val
);
149 assert(H
->bins
); /* make sure it got initialized */
150 assert(0 <= bin
&& bin
< H
->capacity
);
155 statHistBin(const StatHist
* H
, double v
)
158 #if BROKEN_STAT_HIST_BIN
162 v
-= H
->min
; /* offset */
163 if (v
<= 0.0) /* too small */
165 bin
= (int) floor(H
->scale
* H
->val_in(v
) + 0.5);
166 if (bin
< 0) /* should not happen */
168 if (bin
>= H
->capacity
) /* too big */
169 bin
= H
->capacity
- 1;
174 statHistVal(const StatHist
* H
, int bin
)
176 return H
->val_out((double) bin
/ H
->scale
) + H
->min
;
180 statHistDeltaMedian(const StatHist
* A
, const StatHist
* B
)
191 int *D
= xcalloc(A
->capacity
, sizeof(int));
192 assert(A
->capacity
== B
->capacity
);
193 for (i
= 0; i
< A
->capacity
; i
++) {
194 D
[i
] = B
->bins
[i
] - A
->bins
[i
];
197 for (i
= 0; i
< A
->capacity
; i
++)
200 for (i
= 0; i
< A
->capacity
; i
++) {
203 if (a
<= h
&& h
<= b
)
217 f
= (h
- a
) / (b
- a
);
218 K
= (int) floor(f
* (double) (J
- I
) + I
);
219 return statHistVal(A
, K
);
223 statHistBinDumper(StoreEntry
* sentry
, int idx
, double val
, double size
, int count
)
226 storeAppendPrintf(sentry
, "\t%3d/%f\t%d\t%f\n",
227 idx
, val
, count
, count
/ size
);
231 statHistDump(const StatHist
* H
, StoreEntry
* sentry
, StatHistBinDumper
* bd
)
234 double left_border
= H
->min
;
236 bd
= statHistBinDumper
;
237 for (i
= 0; i
< H
->capacity
; i
++) {
238 const double right_border
= statHistVal(H
, i
+ 1);
239 assert(right_border
- left_border
> 0.0);
240 bd(sentry
, i
, left_border
, right_border
- left_border
, H
->bins
[i
]);
241 left_border
= right_border
;
245 /* log based histogram */
246 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
252 assert((x
+ 1.0) >= 0.0);
256 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
266 statHistLogInit(StatHist
* H
, int capacity
, double min
, double max
)
268 statHistInit(H
, capacity
, Log
, Exp
, min
, max
);
271 /* linear histogram for enums */
272 /* we want to be have [-1,last_enum+1] range to track out of range enums */
273 #if !defined(_SQUID_HPUX_) || !defined(__GNUC__)
283 statHistEnumInit(StatHist
* H
, int last_enum
)
285 statHistInit(H
, last_enum
+ 3, Null
, Null
, (double) -1, (double) (last_enum
+ 1 + 1));
289 statHistEnumDumper(StoreEntry
* sentry
, int idx
, double val
, double size
, int count
)
292 storeAppendPrintf(sentry
, "%2d\t %5d\t %5d\n",
293 idx
, (int) val
, count
);
297 statHistIntInit(StatHist
* H
, int n
)
299 statHistInit(H
, n
, Null
, Null
, (double) 0, (double) n
- 1);
303 statHistIntDumper(StoreEntry
* sentry
, int idx
, double val
, double size
, int count
)
306 storeAppendPrintf(sentry
, "%9d\t%9d\n", (int) val
, count
);