1/*
2 * This license covers this C port of
3 * Coda Hale's Golang HdrHistogram https://github.com/codahale/hdrhistogram
4 * at revision 3a0bb77429bd3a61596f5e8a3172445844342120
5 *
6 * ----------------------------------------------------------------------------
7 *
8 * The MIT License (MIT)
9 *
10 * Copyright (c) 2014 Coda Hale
11 *
12 * Permission is hereby granted, free of charge, to any person obtaining a copy
13 * of this software and associated documentation files (the "Software"), to deal
14 * in the Software without restriction, including without limitation the rights
15 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
16 * copies of the Software, and to permit persons to whom the Software is
17 * furnished to do so, subject to the following conditions:
18 *
19 * The above copyright notice and this permission notice shall be included in
20 * all copies or substantial portions of the Software.
21 *
22 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
25 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
28 * THE SOFTWARE.
29*/
30
31/*
32 * librdkafka - Apache Kafka C library
33 *
34 * Copyright (c) 2018, Magnus Edenhill
35 * All rights reserved.
36 *
37 * Redistribution and use in source and binary forms, with or without
38 * modification, are permitted provided that the following conditions are met:
39 *
40 * 1. Redistributions of source code must retain the above copyright notice,
41 * this list of conditions and the following disclaimer.
42 * 2. Redistributions in binary form must reproduce the above copyright notice,
43 * this list of conditions and the following disclaimer in the documentation
44 * and/or other materials provided with the distribution.
45 *
46 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
47 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
50 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
51 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
52 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
53 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
54 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
55 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
56 * POSSIBILITY OF SUCH DAMAGE.
57 */
58
59/**
60 * Minimal C Hdr_Histogram based on Coda Hale's Golang implementation.
61 * https://github.com/codahale/hdr_histogram
62 *
63 *
64 * A Histogram is a lossy data structure used to record the distribution of
65 * non-normally distributed data (like latency) with a high degree of accuracy
66 * and a bounded degree of precision.
67 *
68 *
69 */
70
71#include "rd.h"
72
73#include <stdlib.h>
74#include <string.h>
75#include <math.h>
76
77#include "rdhdrhistogram.h"
78#include "rdunittest.h"
79#include "rdfloat.h"
80
81void rd_hdr_histogram_destroy (rd_hdr_histogram_t *hdr) {
82 free(hdr);
83}
84
85rd_hdr_histogram_t *rd_hdr_histogram_new (int64_t minValue, int64_t maxValue,
86 int significantFigures) {
87 rd_hdr_histogram_t *hdr;
88 int64_t largestValueWithSingleUnitResolution;
89 int32_t subBucketCountMagnitude;
90 int32_t subBucketHalfCountMagnitude;
91 int32_t unitMagnitude;
92 int32_t subBucketCount;
93 int32_t subBucketHalfCount;
94 int64_t subBucketMask;
95 int64_t smallestUntrackableValue;
96 int32_t bucketsNeeded = 1;
97 int32_t bucketCount;
98 int32_t countsLen;
99
100 if (significantFigures < 1 || significantFigures > 5)
101 return NULL;
102
103 largestValueWithSingleUnitResolution =
104 (int64_t)(2.0 * pow(10.0, (double)significantFigures));
105
106 subBucketCountMagnitude =
107 (int32_t)ceil(
108 log2((double)largestValueWithSingleUnitResolution));
109
110 subBucketHalfCountMagnitude = RD_MAX(subBucketCountMagnitude, 1) - 1;
111
112 unitMagnitude = (int32_t)RD_MAX(floor(log2((double)minValue)), 0);
113
114 subBucketCount = (int32_t)pow(2,
115 (double)subBucketHalfCountMagnitude+1.0);
116
117 subBucketHalfCount = subBucketCount / 2;
118
119 subBucketMask = (int64_t)(subBucketCount-1) << unitMagnitude;
120
121 /* Determine exponent range needed to support the trackable
122 * value with no overflow: */
123 smallestUntrackableValue = (int64_t)subBucketCount << unitMagnitude;
124 while (smallestUntrackableValue < maxValue) {
125 smallestUntrackableValue <<= 1;
126 bucketsNeeded++;
127 }
128
129 bucketCount = bucketsNeeded;
130 countsLen = (bucketCount + 1) * (subBucketCount / 2);
131 hdr = calloc(1, sizeof(*hdr) + (sizeof(*hdr->counts) * countsLen));
132 hdr->counts = (int64_t *)(hdr+1);
133 hdr->allocatedSize = sizeof(*hdr) + (sizeof(*hdr->counts) * countsLen);
134
135 hdr->lowestTrackableValue = minValue;
136 hdr->highestTrackableValue = maxValue;
137 hdr->unitMagnitude = unitMagnitude;
138 hdr->significantFigures = significantFigures;
139 hdr->subBucketHalfCountMagnitude = subBucketHalfCountMagnitude;
140 hdr->subBucketHalfCount = subBucketHalfCount;
141 hdr->subBucketMask = subBucketMask;
142 hdr->subBucketCount = subBucketCount;
143 hdr->bucketCount = bucketCount;
144 hdr->countsLen = countsLen;
145 hdr->totalCount = 0;
146 hdr->lowestOutOfRange = minValue;
147 hdr->highestOutOfRange = maxValue;
148
149 return hdr;
150}
151
152/**
153 * @brief Deletes all recorded values and resets histogram.
154 */
155void rd_hdr_histogram_reset (rd_hdr_histogram_t *hdr) {
156 int32_t i;
157 hdr->totalCount = 0;
158 for (i = 0 ; i < hdr->countsLen ; i++)
159 hdr->counts[i] = 0;
160}
161
162
163
164static int32_t
165rd_hdr_countsIndex (const rd_hdr_histogram_t *hdr,
166 int32_t bucketIdx, int32_t subBucketIdx) {
167 int32_t bucketBaseIdx = (bucketIdx + 1) <<
168 hdr->subBucketHalfCountMagnitude;
169 int32_t offsetInBucket = subBucketIdx - hdr->subBucketHalfCount;
170 return bucketBaseIdx + offsetInBucket;
171}
172
173static __inline int64_t
174rd_hdr_getCountAtIndex (const rd_hdr_histogram_t *hdr,
175 int32_t bucketIdx, int32_t subBucketIdx) {
176 return hdr->counts[rd_hdr_countsIndex(hdr, bucketIdx, subBucketIdx)];
177}
178
179
180static __inline int64_t bitLen (int64_t x) {
181 int64_t n = 0;
182 for (; x >= 0x8000; x >>= 16)
183 n += 16;
184 if (x >= 0x80) {
185 x >>= 8;
186 n += 8;
187 }
188 if (x >= 0x8) {
189 x >>= 4;
190 n += 4;
191 }
192 if (x >= 0x2) {
193 x >>= 2;
194 n += 2;
195 }
196 if (x >= 0x1)
197 n++;
198 return n;
199}
200
201
202static __inline int32_t
203rd_hdr_getBucketIndex (const rd_hdr_histogram_t *hdr, int64_t v) {
204 int64_t pow2Ceiling = bitLen(v | hdr->subBucketMask);
205 return (int32_t)(pow2Ceiling - (int64_t)hdr->unitMagnitude -
206 (int64_t)(hdr->subBucketHalfCountMagnitude+1));
207}
208
209static __inline int32_t
210rd_hdr_getSubBucketIdx (const rd_hdr_histogram_t *hdr, int64_t v, int32_t idx) {
211 return (int32_t)(v >> ((int64_t)idx + (int64_t)hdr->unitMagnitude));
212}
213
214static __inline int64_t
215rd_hdr_valueFromIndex (const rd_hdr_histogram_t *hdr,
216 int32_t bucketIdx, int32_t subBucketIdx) {
217 return (int64_t)subBucketIdx <<
218 ((int64_t)bucketIdx + hdr->unitMagnitude);
219}
220
221static __inline int64_t
222rd_hdr_sizeOfEquivalentValueRange (const rd_hdr_histogram_t *hdr, int64_t v) {
223 int32_t bucketIdx = rd_hdr_getBucketIndex(hdr, v);
224 int32_t subBucketIdx = rd_hdr_getSubBucketIdx(hdr, v, bucketIdx);
225 int32_t adjustedBucket = bucketIdx;
226 if (subBucketIdx >= hdr->subBucketCount)
227 adjustedBucket++;
228 return (int64_t)1 << (hdr->unitMagnitude + (int64_t)adjustedBucket);
229}
230
231static __inline int64_t
232rd_hdr_lowestEquivalentValue (const rd_hdr_histogram_t *hdr, int64_t v) {
233 int32_t bucketIdx = rd_hdr_getBucketIndex(hdr, v);
234 int32_t subBucketIdx = rd_hdr_getSubBucketIdx(hdr, v, bucketIdx);
235 return rd_hdr_valueFromIndex(hdr, bucketIdx, subBucketIdx);
236}
237
238
239static __inline int64_t
240rd_hdr_nextNonEquivalentValue (const rd_hdr_histogram_t *hdr, int64_t v) {
241 return rd_hdr_lowestEquivalentValue(hdr, v) +
242 rd_hdr_sizeOfEquivalentValueRange(hdr, v);
243}
244
245
246static __inline int64_t
247rd_hdr_highestEquivalentValue (const rd_hdr_histogram_t *hdr, int64_t v) {
248 return rd_hdr_nextNonEquivalentValue(hdr, v) - 1;
249}
250
251static __inline int64_t
252rd_hdr_medianEquivalentValue (const rd_hdr_histogram_t *hdr, int64_t v) {
253 return rd_hdr_lowestEquivalentValue(hdr, v) +
254 (rd_hdr_sizeOfEquivalentValueRange(hdr, v) >> 1);
255}
256
257
258static __inline int32_t
259rd_hdr_countsIndexFor (const rd_hdr_histogram_t *hdr, int64_t v) {
260 int32_t bucketIdx = rd_hdr_getBucketIndex(hdr, v);
261 int32_t subBucketIdx = rd_hdr_getSubBucketIdx(hdr, v, bucketIdx);
262 return rd_hdr_countsIndex(hdr, bucketIdx, subBucketIdx);
263}
264
265
266
267typedef struct rd_hdr_iter_s {
268 const rd_hdr_histogram_t *hdr;
269 int bucketIdx;
270 int subBucketIdx;
271 int64_t countAtIdx;
272 int64_t countToIdx;
273 int64_t valueFromIdx;
274 int64_t highestEquivalentValue;
275} rd_hdr_iter_t;
276
277#define RD_HDR_ITER_INIT(hdr) { .hdr = hdr, .subBucketIdx = -1 }
278
279static int rd_hdr_iter_next (rd_hdr_iter_t *it) {
280 const rd_hdr_histogram_t *hdr = it->hdr;
281
282 if (it->countToIdx >= hdr->totalCount)
283 return 0;
284
285 it->subBucketIdx++;
286 if (it->subBucketIdx >= hdr->subBucketCount) {
287 it->subBucketIdx = hdr->subBucketHalfCount;
288 it->bucketIdx++;
289 }
290
291 if (it->bucketIdx >= hdr->bucketCount)
292 return 0;
293
294 it->countAtIdx = rd_hdr_getCountAtIndex(hdr,
295 it->bucketIdx,
296 it->subBucketIdx);
297 it->countToIdx += it->countAtIdx;
298 it->valueFromIdx = rd_hdr_valueFromIndex(hdr,
299 it->bucketIdx,
300 it->subBucketIdx);
301 it->highestEquivalentValue =
302 rd_hdr_highestEquivalentValue(hdr, it->valueFromIdx);
303
304 return 1;
305}
306
307
308double rd_hdr_histogram_stddev (rd_hdr_histogram_t *hdr) {
309 double mean;
310 double geometricDevTotal = 0.0;
311 rd_hdr_iter_t it = RD_HDR_ITER_INIT(hdr);
312
313 if (hdr->totalCount == 0)
314 return 0;
315
316 mean = rd_hdr_histogram_mean(hdr);
317
318
319 while (rd_hdr_iter_next(&it)) {
320 double dev;
321
322 if (it.countAtIdx == 0)
323 continue;
324
325 dev = (double)rd_hdr_medianEquivalentValue(
326 hdr, it.valueFromIdx) - mean;
327 geometricDevTotal += (dev * dev) * (double)it.countAtIdx;
328 }
329
330 return sqrt(geometricDevTotal / (double)hdr->totalCount);
331}
332
333
334/**
335 * @returns the approximate maximum recorded value.
336 */
337int64_t rd_hdr_histogram_max (const rd_hdr_histogram_t *hdr) {
338 int64_t vmax = 0;
339 rd_hdr_iter_t it = RD_HDR_ITER_INIT(hdr);
340
341 while (rd_hdr_iter_next(&it)) {
342 if (it.countAtIdx != 0)
343 vmax = it.highestEquivalentValue;
344 }
345 return rd_hdr_highestEquivalentValue(hdr, vmax);
346}
347
348/**
349 * @returns the approximate minimum recorded value.
350 */
351int64_t rd_hdr_histogram_min (const rd_hdr_histogram_t *hdr) {
352 int64_t vmin = 0;
353 rd_hdr_iter_t it = RD_HDR_ITER_INIT(hdr);
354
355 while (rd_hdr_iter_next(&it)) {
356 if (it.countAtIdx != 0 && vmin == 0) {
357 vmin = it.highestEquivalentValue;
358 break;
359 }
360 }
361 return rd_hdr_lowestEquivalentValue(hdr, vmin);
362}
363
364/**
365 * @returns the approximate arithmetic mean of the recorded values.
366 */
367double rd_hdr_histogram_mean (const rd_hdr_histogram_t *hdr) {
368 int64_t total = 0;
369 rd_hdr_iter_t it = RD_HDR_ITER_INIT(hdr);
370
371 if (hdr->totalCount == 0)
372 return 0.0;
373
374 while (rd_hdr_iter_next(&it)) {
375 if (it.countAtIdx != 0)
376 total += it.countAtIdx *
377 rd_hdr_medianEquivalentValue(hdr,
378 it.valueFromIdx);
379 }
380 return (double)total / (double)hdr->totalCount;
381}
382
383
384
385/**
386 * @brief Records the given value.
387 *
388 * @returns 1 if value was recorded or 0 if value is out of range.
389 */
390
391int rd_hdr_histogram_record (rd_hdr_histogram_t *hdr, int64_t v) {
392 int32_t idx = rd_hdr_countsIndexFor(hdr, v);
393
394 if (idx < 0 || hdr->countsLen <= idx) {
395 hdr->outOfRangeCount++;
396 if (v > hdr->highestOutOfRange)
397 hdr->highestOutOfRange = v;
398 if (v < hdr->lowestOutOfRange)
399 hdr->lowestOutOfRange = v;
400 return 0;
401 }
402
403 hdr->counts[idx]++;
404 hdr->totalCount++;
405
406 return 1;
407}
408
409
410/**
411 * @returns the recorded value at the given quantile (0..100).
412 */
413int64_t rd_hdr_histogram_quantile (const rd_hdr_histogram_t *hdr, double q) {
414 int64_t total = 0;
415 int64_t countAtPercentile;
416 rd_hdr_iter_t it = RD_HDR_ITER_INIT(hdr);
417
418 if (q > 100.0)
419 q = 100.0;
420
421 countAtPercentile =
422 (int64_t)(((q / 100.0) * (double)hdr->totalCount) + 0.5);
423
424 while (rd_hdr_iter_next(&it)) {
425 total += it.countAtIdx;
426 if (total >= countAtPercentile)
427 return rd_hdr_highestEquivalentValue(
428 hdr, it.valueFromIdx);
429 }
430
431 return 0;
432}
433
434
435
436/**
437 * @name Unit tests
438 * @{
439 *
440 *
441 *
442 */
443
444/**
445 * @returns 0 on success or 1 on failure.
446 */
447static int ut_high_sigfig (void) {
448 rd_hdr_histogram_t *hdr;
449 const int64_t input[] = {
450 459876, 669187, 711612, 816326, 931423,
451 1033197, 1131895, 2477317, 3964974, 12718782,
452 };
453 size_t i;
454 int64_t v;
455 const int64_t exp = 1048575;
456
457 hdr = rd_hdr_histogram_new(459876, 12718782, 5);
458 for (i = 0 ; i < RD_ARRAYSIZE(input) ; i++) {
459 /* Ignore errors (some should fail) */
460 rd_hdr_histogram_record(hdr, input[i]);
461 }
462
463 v = rd_hdr_histogram_quantile(hdr, 50);
464 RD_UT_ASSERT(v == exp, "Median is %"PRId64", expected %"PRId64,
465 v, exp);
466
467 rd_hdr_histogram_destroy(hdr);
468 RD_UT_PASS();
469}
470
471static int ut_quantile (void) {
472 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 10000000, 3);
473 size_t i;
474 const struct {
475 double q;
476 int64_t v;
477 } exp[] = {
478 { 50, 500223 },
479 { 75, 750079 },
480 { 90, 900095 },
481 { 95, 950271 },
482 { 99, 990207 },
483 { 99.9, 999423 },
484 { 99.99, 999935 },
485 };
486
487 for (i = 0 ; i < 1000000 ; i++) {
488 int r = rd_hdr_histogram_record(hdr, (int64_t)i);
489 RD_UT_ASSERT(r, "record(%"PRId64") failed\n", (int64_t)i);
490 }
491
492 for (i = 0 ; i < RD_ARRAYSIZE(exp) ; i++) {
493 int64_t v = rd_hdr_histogram_quantile(hdr, exp[i].q);
494 RD_UT_ASSERT(v == exp[i].v,
495 "P%.2f is %"PRId64", expected %"PRId64,
496 exp[i].q, v, exp[i].v);
497 }
498
499 rd_hdr_histogram_destroy(hdr);
500 RD_UT_PASS();
501}
502
503static int ut_mean (void) {
504 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 10000000, 3);
505 size_t i;
506 const double exp = 500000.013312;
507 double v;
508
509 for (i = 0 ; i < 1000000 ; i++) {
510 int r = rd_hdr_histogram_record(hdr, (int64_t)i);
511 RD_UT_ASSERT(r, "record(%"PRId64") failed\n", (int64_t)i);
512 }
513
514 v = rd_hdr_histogram_mean(hdr);
515 RD_UT_ASSERT(rd_dbl_eq0(v, exp, 0.0000001),
516 "Mean is %f, expected %f", v, exp);
517
518 rd_hdr_histogram_destroy(hdr);
519 RD_UT_PASS();
520}
521
522
523static int ut_stddev (void) {
524 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 10000000, 3);
525 size_t i;
526 const double exp = 288675.140368;
527 const double epsilon = 0.000001;
528 double v;
529
530 for (i = 0 ; i < 1000000 ; i++) {
531 int r = rd_hdr_histogram_record(hdr, (int64_t)i);
532 RD_UT_ASSERT(r, "record(%"PRId64") failed\n", (int64_t)i);
533 }
534
535 v = rd_hdr_histogram_stddev(hdr);
536 RD_UT_ASSERT(rd_dbl_eq0(v, exp, epsilon),
537 "StdDev is %.6f, expected %.6f: diff %.6f vs epsilon %.6f",
538 v, exp, fabs(v - exp), epsilon);
539
540 rd_hdr_histogram_destroy(hdr);
541 RD_UT_PASS();
542}
543
544static int ut_totalcount (void) {
545 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 10000000, 3);
546 int64_t i;
547
548 for (i = 0 ; i < 1000000 ; i++) {
549 int64_t v;
550 int r = rd_hdr_histogram_record(hdr, i);
551 RD_UT_ASSERT(r, "record(%"PRId64") failed\n", i);
552
553 v = hdr->totalCount;
554 RD_UT_ASSERT(v == i+1,
555 "total_count is %"PRId64", expected %"PRId64,
556 v, i+1);
557 }
558
559 rd_hdr_histogram_destroy(hdr);
560 RD_UT_PASS();
561}
562
563
564static int ut_max (void) {
565 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 10000000, 3);
566 int64_t i, v;
567 const int64_t exp = 1000447;
568
569 for (i = 0 ; i < 1000000 ; i++) {
570 int r = rd_hdr_histogram_record(hdr, i);
571 RD_UT_ASSERT(r, "record(%"PRId64") failed\n", i);
572 }
573
574 v = rd_hdr_histogram_max(hdr);
575 RD_UT_ASSERT(v == exp,
576 "Max is %"PRId64", expected %"PRId64, v, exp);
577
578 rd_hdr_histogram_destroy(hdr);
579 RD_UT_PASS();
580}
581
582static int ut_min (void) {
583 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 10000000, 3);
584 int64_t i, v;
585 const int64_t exp = 0;
586
587 for (i = 0 ; i < 1000000 ; i++) {
588 int r = rd_hdr_histogram_record(hdr, i);
589 RD_UT_ASSERT(r, "record(%"PRId64") failed\n", i);
590 }
591
592 v = rd_hdr_histogram_min(hdr);
593 RD_UT_ASSERT(v == exp,
594 "Min is %"PRId64", expected %"PRId64, v, exp);
595
596 rd_hdr_histogram_destroy(hdr);
597 RD_UT_PASS();
598}
599
600static int ut_reset (void) {
601 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 10000000, 3);
602 int64_t i, v;
603 const int64_t exp = 0;
604
605 for (i = 0 ; i < 1000000 ; i++) {
606 int r = rd_hdr_histogram_record(hdr, i);
607 RD_UT_ASSERT(r, "record(%"PRId64") failed\n", i);
608 }
609
610 rd_hdr_histogram_reset(hdr);
611
612 v = rd_hdr_histogram_max(hdr);
613 RD_UT_ASSERT(v == exp,
614 "Max is %"PRId64", expected %"PRId64, v, exp);
615
616 rd_hdr_histogram_destroy(hdr);
617 RD_UT_PASS();
618}
619
620
621static int ut_nan (void) {
622 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 100000, 3);
623 double v;
624
625 v = rd_hdr_histogram_mean(hdr);
626 RD_UT_ASSERT(!isnan(v), "Mean is %f, expected NaN", v);
627 v = rd_hdr_histogram_stddev(hdr);
628 RD_UT_ASSERT(!isnan(v), "StdDev is %f, expected NaN", v);
629
630 rd_hdr_histogram_destroy(hdr);
631 RD_UT_PASS();
632}
633
634
635static int ut_sigfigs (void) {
636 int sigfigs;
637
638 for (sigfigs = 1 ; sigfigs <= 5 ; sigfigs++) {
639 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(1, 10, sigfigs);
640 RD_UT_ASSERT(hdr->significantFigures == sigfigs,
641 "Significant figures is %"PRId64", expected %d",
642 hdr->significantFigures, sigfigs);
643 rd_hdr_histogram_destroy(hdr);
644 }
645
646 RD_UT_PASS();
647}
648
649static int ut_minmax_trackable (void) {
650 const int64_t minval = 2;
651 const int64_t maxval = 11;
652 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(minval, maxval, 3);
653
654 RD_UT_ASSERT(hdr->lowestTrackableValue == minval,
655 "lowestTrackableValue is %"PRId64", expected %"PRId64,
656 hdr->lowestTrackableValue, minval);
657 RD_UT_ASSERT(hdr->highestTrackableValue == maxval,
658 "highestTrackableValue is %"PRId64", expected %"PRId64,
659 hdr->highestTrackableValue, maxval);
660
661 rd_hdr_histogram_destroy(hdr);
662 RD_UT_PASS();
663}
664
665
666static int ut_unitmagnitude_overflow (void) {
667 rd_hdr_histogram_t *hdr = rd_hdr_histogram_new(0, 200, 4);
668 int r = rd_hdr_histogram_record(hdr, 11);
669 RD_UT_ASSERT(r, "record(11) failed\n");
670
671 rd_hdr_histogram_destroy(hdr);
672 RD_UT_PASS();
673}
674
675static int ut_subbucketmask_overflow (void) {
676 rd_hdr_histogram_t *hdr;
677 const int64_t input[] = { (int64_t)1e8, (int64_t)2e7, (int64_t)3e7 };
678 const struct {
679 double q;
680 int64_t v;
681 } exp[] = {
682 { 50, 33554431 },
683 { 83.33, 33554431 },
684 { 83.34, 100663295 },
685 { 99, 100663295 },
686 };
687 size_t i;
688
689 hdr = rd_hdr_histogram_new((int64_t)2e7, (int64_t)1e8, 5);
690
691 for (i = 0 ; i < RD_ARRAYSIZE(input) ; i++) {
692 /* Ignore errors (some should fail) */
693 int r = rd_hdr_histogram_record(hdr, input[i]);
694 RD_UT_ASSERT(r, "record(%"PRId64") failed\n", input[i]);
695 }
696
697 for (i = 0 ; i < RD_ARRAYSIZE(exp) ; i++) {
698 int64_t v = rd_hdr_histogram_quantile(hdr, exp[i].q);
699 RD_UT_ASSERT(v == exp[i].v,
700 "P%.2f is %"PRId64", expected %"PRId64,
701 exp[i].q, v, exp[i].v);
702 }
703
704 rd_hdr_histogram_destroy(hdr);
705 RD_UT_PASS();
706}
707
708
709int unittest_rdhdrhistogram (void) {
710 int fails = 0;
711
712 fails += ut_high_sigfig();
713 fails += ut_quantile();
714 fails += ut_mean();
715 fails += ut_stddev();
716 fails += ut_totalcount();
717 fails += ut_max();
718 fails += ut_min();
719 fails += ut_reset();
720 fails += ut_nan();
721 fails += ut_sigfigs();
722 fails += ut_minmax_trackable();
723 fails += ut_unitmagnitude_overflow();
724 fails += ut_subbucketmask_overflow();
725
726 return fails;
727}
728
729/**@}*/
730