1/**
2 * hdr_histogram.c
3 * Written by Michael Barker and released to the public domain,
4 * as explained at http://creativecommons.org/publicdomain/zero/1.0/
5 */
6
7#include <stdlib.h>
8#include <stdbool.h>
9#include <math.h>
10#include <assert.h>
11#include <stdio.h>
12#include <string.h>
13#include <stdint.h>
14#include <errno.h>
15#include <inttypes.h>
16
17#include "hdr_histogram.h"
18#include "hdr_tests.h"
19
20//  ######   #######  ##     ## ##    ## ########  ######
21// ##    ## ##     ## ##     ## ###   ##    ##    ##    ##
22// ##       ##     ## ##     ## ####  ##    ##    ##
23// ##       ##     ## ##     ## ## ## ##    ##     ######
24// ##       ##     ## ##     ## ##  ####    ##          ##
25// ##    ## ##     ## ##     ## ##   ###    ##    ##    ##
26//  ######   #######   #######  ##    ##    ##     ######
27
28static int32_t normalize_index(const struct hdr_histogram* h, int32_t index)
29{
30    if (h->normalizing_index_offset == 0)
31    {
32        return index;
33    }
34
35    int32_t normalized_index = index - h->normalizing_index_offset;
36    int32_t adjustment = 0;
37
38    if (normalized_index < 0)
39    {
40        adjustment = h->counts_len;
41    }
42    else if (normalized_index >= h->counts_len)
43    {
44        adjustment = -h->counts_len;
45    }
46
47    return normalized_index + adjustment;
48}
49
50static int64_t counts_get_direct(const struct hdr_histogram* h, int32_t index)
51{
52    return h->counts[index];
53}
54
55static int64_t counts_get_normalised(const struct hdr_histogram* h, int32_t index)
56{
57    return counts_get_direct(h, normalize_index(h, index));
58}
59
60static void counts_inc_normalised(
61    struct hdr_histogram* h, int32_t index, int64_t value)
62{
63    int32_t normalised_index = normalize_index(h, index);
64    h->counts[normalised_index] += value;
65    h->total_count += value;
66}
67
68static void update_min_max(struct hdr_histogram* h, int64_t value)
69{
70    h->min_value = (value < h->min_value && value != 0) ? value : h->min_value;
71    h->max_value = (value > h->max_value) ? value : h->max_value;
72}
73
74// ##     ## ######## #### ##       #### ######## ##    ##
75// ##     ##    ##     ##  ##        ##     ##     ##  ##
76// ##     ##    ##     ##  ##        ##     ##      ####
77// ##     ##    ##     ##  ##        ##     ##       ##
78// ##     ##    ##     ##  ##        ##     ##       ##
79// ##     ##    ##     ##  ##        ##     ##       ##
80//  #######     ##    #### ######## ####    ##       ##
81
82static int64_t power(int64_t base, int64_t exp)
83{
84    int64_t result = 1;
85    while(exp)
86    {
87        result *= base; exp--;
88    }
89    return result;
90}
91
92#if defined(_MSC_VER)
93#pragma intrinsic(_BitScanReverse64)
94#endif
95
96static int32_t get_bucket_index(const struct hdr_histogram* h, int64_t value)
97{
98#if defined(_MSC_VER)
99    uint32_t leading_zero = 0;
100    _BitScanReverse64(&leading_zero, value | h->sub_bucket_mask);
101    int32_t pow2ceiling = 64 - (63 - leading_zero); // smallest power of 2 containing value
102#else
103    int32_t pow2ceiling = 64 - __builtin_clzll(value | h->sub_bucket_mask); // smallest power of 2 containing value
104#endif
105    return pow2ceiling - h->unit_magnitude - (h->sub_bucket_half_count_magnitude + 1);
106}
107
108static int32_t get_sub_bucket_index(int64_t value, int32_t bucket_index, int32_t unit_magnitude)
109{
110    return (int32_t)(value >> (bucket_index + unit_magnitude));
111}
112
113static int32_t counts_index(const struct hdr_histogram* h, int32_t bucket_index, int32_t sub_bucket_index)
114{
115    // Calculate the index for the first entry in the bucket:
116    // (The following is the equivalent of ((bucket_index + 1) * subBucketHalfCount) ):
117    int32_t bucket_base_index = (bucket_index + 1) << h->sub_bucket_half_count_magnitude;
118    // Calculate the offset in the bucket:
119    int32_t offset_in_bucket = sub_bucket_index - h->sub_bucket_half_count;
120    // The following is the equivalent of ((sub_bucket_index  - subBucketHalfCount) + bucketBaseIndex;
121    return bucket_base_index + offset_in_bucket;
122}
123
124static int64_t value_from_index(int32_t bucket_index, int32_t sub_bucket_index, int32_t unit_magnitude)
125{
126    return ((int64_t) sub_bucket_index) << (bucket_index + unit_magnitude);
127}
128
129int32_t counts_index_for(const struct hdr_histogram* h, int64_t value)
130{
131    int32_t bucket_index     = get_bucket_index(h, value);
132    int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
133
134    return counts_index(h, bucket_index, sub_bucket_index);
135}
136
137int64_t hdr_value_at_index(const struct hdr_histogram *h, int32_t index)
138{
139    int32_t bucket_index = (index >> h->sub_bucket_half_count_magnitude) - 1;
140    int32_t sub_bucket_index = (index & (h->sub_bucket_half_count - 1)) + h->sub_bucket_half_count;
141
142    if (bucket_index < 0)
143    {
144        sub_bucket_index -= h->sub_bucket_half_count;
145        bucket_index = 0;
146    }
147
148    return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
149}
150
151int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value)
152{
153    int32_t bucket_index     = get_bucket_index(h, value);
154    int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
155    int32_t adjusted_bucket  = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index;
156    return INT64_C(1) << (h->unit_magnitude + adjusted_bucket);
157}
158
159static int64_t lowest_equivalent_value(const struct hdr_histogram* h, int64_t value)
160{
161    int32_t bucket_index     = get_bucket_index(h, value);
162    int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
163    return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
164}
165
166int64_t hdr_next_non_equivalent_value(const struct hdr_histogram *h, int64_t value)
167{
168    return lowest_equivalent_value(h, value) + hdr_size_of_equivalent_value_range(h, value);
169}
170
171static int64_t highest_equivalent_value(const struct hdr_histogram* h, int64_t value)
172{
173    return hdr_next_non_equivalent_value(h, value) - 1;
174}
175
176int64_t hdr_median_equivalent_value(const struct hdr_histogram *h, int64_t value)
177{
178    return lowest_equivalent_value(h, value) + (hdr_size_of_equivalent_value_range(h, value) >> 1);
179}
180
181static int64_t non_zero_min(const struct hdr_histogram* h)
182{
183    if (INT64_MAX == h->min_value)
184    {
185        return INT64_MAX;
186    }
187
188    return lowest_equivalent_value(h, h->min_value);
189}
190
191void hdr_reset_internal_counters(struct hdr_histogram* h)
192{
193    int min_non_zero_index = -1;
194    int max_index = -1;
195    int64_t observed_total_count = 0;
196    int i;
197
198    for (i = 0; i < h->counts_len; i++)
199    {
200        int64_t count_at_index;
201
202        if ((count_at_index = counts_get_direct(h, i)) > 0)
203        {
204            observed_total_count += count_at_index;
205            max_index = i;
206            if (min_non_zero_index == -1 && i != 0)
207            {
208                min_non_zero_index = i;
209            }
210        }
211    }
212
213    if (max_index == -1)
214    {
215        h->max_value = 0;
216    }
217    else
218    {
219        int64_t max_value = hdr_value_at_index(h, max_index);
220        h->max_value = highest_equivalent_value(h, max_value);
221    }
222
223    if (min_non_zero_index == -1)
224    {
225        h->min_value = INT64_MAX;
226    }
227    else
228    {
229        h->min_value = hdr_value_at_index(h, min_non_zero_index);
230    }
231
232    h->total_count = observed_total_count;
233}
234
235static int32_t buckets_needed_to_cover_value(int64_t value, int32_t sub_bucket_count, int32_t unit_magnitude)
236{
237    int64_t smallest_untrackable_value = ((int64_t) sub_bucket_count) << unit_magnitude;
238    int32_t buckets_needed = 1;
239    while (smallest_untrackable_value <= value)
240    {
241        if (smallest_untrackable_value > INT64_MAX / 2)
242        {
243            return buckets_needed + 1;
244        }
245        smallest_untrackable_value <<= 1;
246        buckets_needed++;
247    }
248
249    return buckets_needed;
250}
251
252// ##     ## ######## ##     ##  #######  ########  ##    ##
253// ###   ### ##       ###   ### ##     ## ##     ##  ##  ##
254// #### #### ##       #### #### ##     ## ##     ##   ####
255// ## ### ## ######   ## ### ## ##     ## ########     ##
256// ##     ## ##       ##     ## ##     ## ##   ##      ##
257// ##     ## ##       ##     ## ##     ## ##    ##     ##
258// ##     ## ######## ##     ##  #######  ##     ##    ##
259
260int hdr_calculate_bucket_config(
261        int64_t lowest_trackable_value,
262        int64_t highest_trackable_value,
263        int significant_figures,
264        struct hdr_histogram_bucket_config* cfg)
265{
266    if (lowest_trackable_value < 1 ||
267            significant_figures < 1 || 5 < significant_figures)
268    {
269        return EINVAL;
270    }
271    else if (lowest_trackable_value * 2 > highest_trackable_value)
272    {
273        return EINVAL;
274    }
275
276    cfg->lowest_trackable_value = lowest_trackable_value;
277    cfg->significant_figures = significant_figures;
278    cfg->highest_trackable_value = highest_trackable_value;
279
280    int64_t largest_value_with_single_unit_resolution = 2 * power(10, significant_figures);
281    int32_t sub_bucket_count_magnitude = (int32_t) ceil(log((double)largest_value_with_single_unit_resolution) / log(2));
282    cfg->sub_bucket_half_count_magnitude = ((sub_bucket_count_magnitude > 1) ? sub_bucket_count_magnitude : 1) - 1;
283
284    cfg->unit_magnitude = (int32_t) floor(log((double)lowest_trackable_value) / log(2));
285
286    cfg->sub_bucket_count      = (int32_t) pow(2, (cfg->sub_bucket_half_count_magnitude + 1));
287    cfg->sub_bucket_half_count = cfg->sub_bucket_count / 2;
288    cfg->sub_bucket_mask       = ((int64_t) cfg->sub_bucket_count - 1) << cfg->unit_magnitude;
289
290    // determine exponent range needed to support the trackable value with no overflow:
291    cfg->bucket_count = buckets_needed_to_cover_value(highest_trackable_value, cfg->sub_bucket_count, (int32_t)cfg->unit_magnitude);
292    cfg->counts_len = (cfg->bucket_count + 1) * (cfg->sub_bucket_count / 2);
293
294    return 0;
295}
296
297void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg)
298{
299    h->lowest_trackable_value          = cfg->lowest_trackable_value;
300    h->highest_trackable_value         = cfg->highest_trackable_value;
301    h->unit_magnitude                  = (int32_t)cfg->unit_magnitude;
302    h->significant_figures             = (int32_t)cfg->significant_figures;
303    h->sub_bucket_half_count_magnitude = cfg->sub_bucket_half_count_magnitude;
304    h->sub_bucket_half_count           = cfg->sub_bucket_half_count;
305    h->sub_bucket_mask                 = cfg->sub_bucket_mask;
306    h->sub_bucket_count                = cfg->sub_bucket_count;
307    h->min_value                       = INT64_MAX;
308    h->max_value                       = 0;
309    h->normalizing_index_offset        = 0;
310    h->conversion_ratio                = 1.0;
311    h->bucket_count                    = cfg->bucket_count;
312    h->counts_len                      = cfg->counts_len;
313    h->total_count                     = 0;
314}
315
316int hdr_init(
317        int64_t lowest_trackable_value,
318        int64_t highest_trackable_value,
319        int significant_figures,
320        struct hdr_histogram** result)
321{
322    struct hdr_histogram_bucket_config cfg;
323
324    int r = hdr_calculate_bucket_config(lowest_trackable_value, highest_trackable_value, significant_figures, &cfg);
325    if (r)
326    {
327        return r;
328    }
329
330    size_t histogram_size           = sizeof(struct hdr_histogram) + cfg.counts_len * sizeof(int64_t);
331    struct hdr_histogram* histogram = malloc(histogram_size);
332
333    if (!histogram)
334    {
335        return ENOMEM;
336    }
337
338    // memset will ensure that all of the function pointers are null.
339    memset((void*) histogram, 0, histogram_size);
340
341    hdr_init_preallocated(histogram, &cfg);
342    *result = histogram;
343
344    return 0;
345}
346
347
348int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result)
349{
350    return hdr_init(1, highest_trackable_value, significant_figures, result);
351}
352
353// reset a histogram to zero.
354void hdr_reset(struct hdr_histogram *h)
355{
356     h->total_count=0;
357     h->min_value = INT64_MAX;
358     h->max_value = 0;
359     memset((void *) &h->counts, 0, (sizeof(int64_t) * h->counts_len));
360     return;
361}
362
363size_t hdr_get_memory_size(struct hdr_histogram *h)
364{
365    return sizeof(struct hdr_histogram) + h->counts_len * sizeof(int64_t);
366}
367
368// ##     ## ########  ########     ###    ######## ########  ######
369// ##     ## ##     ## ##     ##   ## ##      ##    ##       ##    ##
370// ##     ## ##     ## ##     ##  ##   ##     ##    ##       ##
371// ##     ## ########  ##     ## ##     ##    ##    ######    ######
372// ##     ## ##        ##     ## #########    ##    ##             ##
373// ##     ## ##        ##     ## ##     ##    ##    ##       ##    ##
374//  #######  ##        ########  ##     ##    ##    ########  ######
375
376
377bool hdr_record_value(struct hdr_histogram* h, int64_t value)
378{
379    return hdr_record_values(h, value, 1);
380}
381
382bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count)
383{
384    if (value < 0)
385    {
386        return false;
387    }
388
389    int32_t counts_index = counts_index_for(h, value);
390
391    if (counts_index < 0 || h->counts_len <= counts_index)
392    {
393        return false;
394    }
395
396    counts_inc_normalised(h, counts_index, count);
397    update_min_max(h, value);
398
399    return true;
400}
401
402bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval)
403{
404    return hdr_record_corrected_values(h, value, 1, expected_interval);
405}
406
407
408bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval)
409{
410    if (!hdr_record_values(h, value, count))
411    {
412        return false;
413    }
414
415    if (expected_interval <= 0 || value <= expected_interval)
416    {
417        return true;
418    }
419
420    int64_t missing_value = value - expected_interval;
421    for (; missing_value >= expected_interval; missing_value -= expected_interval)
422    {
423        if (!hdr_record_values(h, missing_value, count))
424        {
425            return false;
426        }
427    }
428
429    return true;
430}
431
432int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from)
433{
434    struct hdr_iter iter;
435    hdr_iter_recorded_init(&iter, from);
436    int64_t dropped = 0;
437
438    while (hdr_iter_next(&iter))
439    {
440        int64_t value = iter.value;
441        int64_t count = iter.count;
442
443        if (!hdr_record_values(h, value, count))
444        {
445            dropped += count;
446        }
447    }
448
449    return dropped;
450}
451
452int64_t hdr_add_while_correcting_for_coordinated_omission(
453        struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval)
454{
455    struct hdr_iter iter;
456    hdr_iter_recorded_init(&iter, from);
457    int64_t dropped = 0;
458
459    while (hdr_iter_next(&iter))
460    {
461        int64_t value = iter.value;
462        int64_t count = iter.count;
463
464        if (!hdr_record_corrected_values(h, value, count, expected_interval))
465        {
466            dropped += count;
467        }
468    }
469
470    return dropped;
471}
472
473
474
475// ##     ##    ###    ##       ##     ## ########  ######
476// ##     ##   ## ##   ##       ##     ## ##       ##    ##
477// ##     ##  ##   ##  ##       ##     ## ##       ##
478// ##     ## ##     ## ##       ##     ## ######    ######
479//  ##   ##  ######### ##       ##     ## ##             ##
480//   ## ##   ##     ## ##       ##     ## ##       ##    ##
481//    ###    ##     ## ########  #######  ########  ######
482
483
484int64_t hdr_max(const struct hdr_histogram* h)
485{
486    if (0 == h->max_value)
487    {
488        return 0;
489    }
490
491    return highest_equivalent_value(h, h->max_value);
492}
493
494int64_t hdr_min(const struct hdr_histogram* h)
495{
496    if (0 < hdr_count_at_index(h, 0))
497    {
498        return 0;
499    }
500
501    return non_zero_min(h);
502}
503
504int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile)
505{
506    struct hdr_iter iter;
507    hdr_iter_init(&iter, h);
508
509    double requested_percentile = percentile < 100.0 ? percentile : 100.0;
510    int64_t count_at_percentile =
511        (int64_t) (((requested_percentile / 100) * h->total_count) + 0.5);
512    count_at_percentile = count_at_percentile > 1 ? count_at_percentile : 1;
513    int64_t total = 0;
514
515    while (hdr_iter_next(&iter))
516    {
517        total += iter.count;
518
519        if (total >= count_at_percentile)
520        {
521            int64_t value_from_index = iter.value;
522            return highest_equivalent_value(h, value_from_index);
523        }
524    }
525
526    return 0;
527}
528
529double hdr_mean(const struct hdr_histogram* h)
530{
531    struct hdr_iter iter;
532    int64_t total = 0;
533
534    hdr_iter_init(&iter, h);
535
536    while (hdr_iter_next(&iter))
537    {
538        if (0 != iter.count)
539        {
540            total += iter.count * hdr_median_equivalent_value(h, iter.value);
541        }
542    }
543
544    return (total * 1.0) / h->total_count;
545}
546
547double hdr_stddev(const struct hdr_histogram* h)
548{
549    double mean = hdr_mean(h);
550    double geometric_dev_total = 0.0;
551
552    struct hdr_iter iter;
553    hdr_iter_init(&iter, h);
554
555    while (hdr_iter_next(&iter))
556    {
557        if (0 != iter.count)
558        {
559            double dev = (hdr_median_equivalent_value(h, iter.value) * 1.0) - mean;
560            geometric_dev_total += (dev * dev) * iter.count;
561        }
562    }
563
564    return sqrt(geometric_dev_total / h->total_count);
565}
566
567bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b)
568{
569    return lowest_equivalent_value(h, a) == lowest_equivalent_value(h, b);
570}
571
572int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value)
573{
574    return lowest_equivalent_value(h, value);
575}
576
577int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value)
578{
579    return counts_get_normalised(h, counts_index_for(h, value));
580}
581
582int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index)
583{
584    return counts_get_normalised(h, index);
585}
586
587
588// #### ######## ######## ########     ###    ########  #######  ########   ######
589//  ##     ##    ##       ##     ##   ## ##      ##    ##     ## ##     ## ##    ##
590//  ##     ##    ##       ##     ##  ##   ##     ##    ##     ## ##     ## ##
591//  ##     ##    ######   ########  ##     ##    ##    ##     ## ########   ######
592//  ##     ##    ##       ##   ##   #########    ##    ##     ## ##   ##         ##
593//  ##     ##    ##       ##    ##  ##     ##    ##    ##     ## ##    ##  ##    ##
594// ####    ##    ######## ##     ## ##     ##    ##     #######  ##     ##  ######
595
596
597static bool has_buckets(struct hdr_iter* iter)
598{
599    return iter->counts_index < iter->h->counts_len;
600}
601
602static bool has_next(struct hdr_iter* iter)
603{
604    return iter->cumulative_count < iter->total_count;
605}
606
607static bool move_next(struct hdr_iter* iter)
608{
609    iter->counts_index++;
610
611    if (!has_buckets(iter))
612    {
613        return false;
614    }
615
616    iter->count = counts_get_normalised(iter->h, iter->counts_index);
617    iter->cumulative_count += iter->count;
618
619    iter->value = hdr_value_at_index(iter->h, iter->counts_index);
620    iter->highest_equivalent_value = highest_equivalent_value(iter->h, iter->value);
621    iter->lowest_equivalent_value = lowest_equivalent_value(iter->h, iter->value);
622    iter->median_equivalent_value = hdr_median_equivalent_value(iter->h, iter->value);
623
624    return true;
625}
626
627static int64_t peek_next_value_from_index(struct hdr_iter* iter)
628{
629    return hdr_value_at_index(iter->h, iter->counts_index + 1);
630}
631
632static bool next_value_greater_than_reporting_level_upper_bound(
633    struct hdr_iter *iter, int64_t reporting_level_upper_bound)
634{
635    if (iter->counts_index >= iter->h->counts_len)
636    {
637        return false;
638    }
639
640    return peek_next_value_from_index(iter) > reporting_level_upper_bound;
641}
642
643static bool _basic_iter_next(struct hdr_iter *iter)
644{
645    if (!has_next(iter) || iter->counts_index >= iter->h->counts_len)
646    {
647        return false;
648    }
649
650    move_next(iter);
651
652    return true;
653}
654
655static void _update_iterated_values(struct hdr_iter* iter, int64_t new_value_iterated_to)
656{
657    iter->value_iterated_from = iter->value_iterated_to;
658    iter->value_iterated_to = new_value_iterated_to;
659}
660
661static bool _all_values_iter_next(struct hdr_iter* iter)
662{
663    bool result = move_next(iter);
664
665    if (result)
666    {
667        _update_iterated_values(iter, iter->value);
668    }
669
670    return result;
671}
672
673void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h)
674{
675    iter->h = h;
676
677    iter->counts_index = -1;
678    iter->total_count = h->total_count;
679    iter->count = 0;
680    iter->cumulative_count = 0;
681    iter->value = 0;
682    iter->highest_equivalent_value = 0;
683    iter->value_iterated_from = 0;
684    iter->value_iterated_to = 0;
685
686    iter->_next_fp = _all_values_iter_next;
687}
688
689bool hdr_iter_next(struct hdr_iter* iter)
690{
691    return iter->_next_fp(iter);
692}
693
694// ########  ######## ########   ######  ######## ##    ## ######## #### ##       ########  ######
695// ##     ## ##       ##     ## ##    ## ##       ###   ##    ##     ##  ##       ##       ##    ##
696// ##     ## ##       ##     ## ##       ##       ####  ##    ##     ##  ##       ##       ##
697// ########  ######   ########  ##       ######   ## ## ##    ##     ##  ##       ######    ######
698// ##        ##       ##   ##   ##       ##       ##  ####    ##     ##  ##       ##             ##
699// ##        ##       ##    ##  ##    ## ##       ##   ###    ##     ##  ##       ##       ##    ##
700// ##        ######## ##     ##  ######  ######## ##    ##    ##    #### ######## ########  ######
701
702static bool _percentile_iter_next(struct hdr_iter* iter)
703{
704    struct hdr_iter_percentiles* percentiles = &iter->specifics.percentiles;
705
706    if (!has_next(iter))
707    {
708        if (percentiles->seen_last_value)
709        {
710            return false;
711        }
712
713        percentiles->seen_last_value = true;
714        percentiles->percentile = 100.0;
715
716        return true;
717    }
718
719    if (iter->counts_index == -1 && !_basic_iter_next(iter))
720    {
721        return false;
722    }
723
724    do
725    {
726        double current_percentile = (100.0 * (double) iter->cumulative_count) / iter->h->total_count;
727        if (iter->count != 0 &&
728                percentiles->percentile_to_iterate_to <= current_percentile)
729        {
730            _update_iterated_values(iter, highest_equivalent_value(iter->h, iter->value));
731
732            percentiles->percentile = percentiles->percentile_to_iterate_to;
733            int64_t temp = (int64_t)(log(100 / (100.0 - (percentiles->percentile_to_iterate_to))) / log(2)) + 1;
734            int64_t half_distance = (int64_t) pow(2, (double) temp);
735            int64_t percentile_reporting_ticks = percentiles->ticks_per_half_distance * half_distance;
736            percentiles->percentile_to_iterate_to += 100.0 / percentile_reporting_ticks;
737
738            return true;
739        }
740    }
741    while (_basic_iter_next(iter));
742
743    return true;
744}
745
746void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance)
747{
748    iter->h = h;
749
750    hdr_iter_init(iter, h);
751
752    iter->specifics.percentiles.seen_last_value          = false;
753    iter->specifics.percentiles.ticks_per_half_distance  = ticks_per_half_distance;
754    iter->specifics.percentiles.percentile_to_iterate_to = 0.0;
755    iter->specifics.percentiles.percentile               = 0.0;
756
757    iter->_next_fp = _percentile_iter_next;
758}
759
760static void format_line_string(char* str, size_t len, int significant_figures, format_type format)
761{
762#if defined(_MSC_VER)
763#define snprintf _snprintf
764#pragma warning(push)
765#pragma warning(disable: 4996)
766#endif
767    const char* format_str = "%s%d%s";
768
769    switch (format)
770    {
771        case CSV:
772            snprintf(str, len, format_str, "%.", significant_figures, "f,%f,%d,%.2f\n");
773            break;
774        case CLASSIC:
775            snprintf(str, len, format_str, "%12.", significant_figures, "f %12f %12d %12.2f\n");
776            break;
777        default:
778            snprintf(str, len, format_str, "%12.", significant_figures, "f %12f %12d %12.2f\n");
779    }
780#if defined(_MSC_VER)
781#undef snprintf
782#pragma warning(pop)
783#endif
784}
785
786
787// ########  ########  ######   #######  ########  ########  ######## ########
788// ##     ## ##       ##    ## ##     ## ##     ## ##     ## ##       ##     ##
789// ##     ## ##       ##       ##     ## ##     ## ##     ## ##       ##     ##
790// ########  ######   ##       ##     ## ########  ##     ## ######   ##     ##
791// ##   ##   ##       ##       ##     ## ##   ##   ##     ## ##       ##     ##
792// ##    ##  ##       ##    ## ##     ## ##    ##  ##     ## ##       ##     ##
793// ##     ## ########  ######   #######  ##     ## ########  ######## ########
794
795
796static bool _recorded_iter_next(struct hdr_iter* iter)
797{
798    while (_basic_iter_next(iter))
799    {
800        if (iter->count != 0)
801        {
802            _update_iterated_values(iter, iter->value);
803
804            iter->specifics.recorded.count_added_in_this_iteration_step = iter->count;
805            return true;
806        }
807    }
808
809    return false;
810}
811
812void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h)
813{
814    hdr_iter_init(iter, h);
815
816    iter->specifics.recorded.count_added_in_this_iteration_step = 0;
817
818    iter->_next_fp = _recorded_iter_next;
819}
820
821// ##       #### ##    ## ########    ###    ########
822// ##        ##  ###   ## ##         ## ##   ##     ##
823// ##        ##  ####  ## ##        ##   ##  ##     ##
824// ##        ##  ## ## ## ######   ##     ## ########
825// ##        ##  ##  #### ##       ######### ##   ##
826// ##        ##  ##   ### ##       ##     ## ##    ##
827// ######## #### ##    ## ######## ##     ## ##     ##
828
829
830static bool _iter_linear_next(struct hdr_iter* iter)
831{
832    struct hdr_iter_linear* linear = &iter->specifics.linear;
833
834    linear->count_added_in_this_iteration_step = 0;
835
836    if (has_next(iter) ||
837        next_value_greater_than_reporting_level_upper_bound(
838            iter, linear->next_value_reporting_level_lowest_equivalent))
839    {
840        do
841        {
842            if (iter->value >= linear->next_value_reporting_level_lowest_equivalent)
843            {
844                _update_iterated_values(iter, linear->next_value_reporting_level);
845
846                linear->next_value_reporting_level += linear->value_units_per_bucket;
847                linear->next_value_reporting_level_lowest_equivalent =
848                    lowest_equivalent_value(iter->h, linear->next_value_reporting_level);
849
850                return true;
851            }
852
853            if (!move_next(iter))
854            {
855                return true;
856            }
857
858            linear->count_added_in_this_iteration_step += iter->count;
859        }
860        while (true);
861    }
862
863    return false;
864}
865
866
867void hdr_iter_linear_init(struct hdr_iter* iter, const struct hdr_histogram* h, int64_t value_units_per_bucket)
868{
869    hdr_iter_init(iter, h);
870
871    iter->specifics.linear.count_added_in_this_iteration_step = 0;
872    iter->specifics.linear.value_units_per_bucket = value_units_per_bucket;
873    iter->specifics.linear.next_value_reporting_level = value_units_per_bucket;
874    iter->specifics.linear.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_per_bucket);
875
876    iter->_next_fp = _iter_linear_next;
877}
878
879// ##        #######   ######      ###    ########  #### ######## ##     ## ##     ## ####  ######
880// ##       ##     ## ##    ##    ## ##   ##     ##  ##     ##    ##     ## ###   ###  ##  ##    ##
881// ##       ##     ## ##         ##   ##  ##     ##  ##     ##    ##     ## #### ####  ##  ##
882// ##       ##     ## ##   #### ##     ## ########   ##     ##    ######### ## ### ##  ##  ##
883// ##       ##     ## ##    ##  ######### ##   ##    ##     ##    ##     ## ##     ##  ##  ##
884// ##       ##     ## ##    ##  ##     ## ##    ##   ##     ##    ##     ## ##     ##  ##  ##    ##
885// ########  #######   ######   ##     ## ##     ## ####    ##    ##     ## ##     ## ####  ######
886
887static bool _log_iter_next(struct hdr_iter *iter)
888{
889    struct hdr_iter_log* logarithmic = &iter->specifics.log;
890
891    logarithmic->count_added_in_this_iteration_step = 0;
892
893    if (has_next(iter) ||
894        next_value_greater_than_reporting_level_upper_bound(
895            iter, logarithmic->next_value_reporting_level_lowest_equivalent))
896    {
897        do
898        {
899            if (iter->value >= logarithmic->next_value_reporting_level_lowest_equivalent)
900            {
901                _update_iterated_values(iter, logarithmic->next_value_reporting_level);
902
903                logarithmic->next_value_reporting_level *= (int64_t)logarithmic->log_base;
904                logarithmic->next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(iter->h, logarithmic->next_value_reporting_level);
905
906                return true;
907            }
908
909            if (!move_next(iter))
910            {
911                return true;
912            }
913
914            logarithmic->count_added_in_this_iteration_step += iter->count;
915        }
916        while (true);
917    }
918
919    return false;
920}
921
922void hdr_iter_log_init(
923        struct hdr_iter* iter,
924        const struct hdr_histogram* h,
925        int64_t value_units_first_bucket,
926        double log_base)
927{
928    hdr_iter_init(iter, h);
929    iter->specifics.log.count_added_in_this_iteration_step = 0;
930    iter->specifics.log.log_base = log_base;
931    iter->specifics.log.next_value_reporting_level = value_units_first_bucket;
932    iter->specifics.log.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_first_bucket);
933
934    iter->_next_fp = _log_iter_next;
935}
936
937// Printing.
938
939static const char* format_head_string(format_type format)
940{
941    switch (format)
942    {
943        case CSV:
944            return "%s,%s,%s,%s\n";
945        case CLASSIC:
946            return "%12s %12s %12s %12s\n\n";
947        default:
948            return "%12s %12s %12s %12s\n\n";
949    }
950}
951
952static const char CLASSIC_FOOTER[] =
953    "#[Mean    = %12.3f, StdDeviation   = %12.3f]\n"
954    "#[Max     = %12.3f, Total count    = %12" PRIu64 "]\n"
955    "#[Buckets = %12d, SubBuckets     = %12d]\n";
956
957int hdr_percentiles_print(
958        struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance,
959        double value_scale, format_type format)
960{
961    char line_format[25];
962    format_line_string(line_format, 25, h->significant_figures, format);
963    const char* head_format = format_head_string(format);
964    int rc = 0;
965
966    struct hdr_iter iter;
967    hdr_iter_percentile_init(&iter, h, ticks_per_half_distance);
968
969    if (fprintf(
970            stream, head_format,
971            "Value", "Percentile", "TotalCount", "1/(1-Percentile)") < 0)
972    {
973        rc = EIO;
974        goto cleanup;
975    }
976
977    struct hdr_iter_percentiles * percentiles = &iter.specifics.percentiles;
978    while (hdr_iter_next(&iter))
979    {
980        double  value               = iter.highest_equivalent_value / value_scale;
981        double  percentile          = percentiles->percentile / 100.0;
982        int64_t total_count         = iter.cumulative_count;
983        double  inverted_percentile = (1.0 / (1.0 - percentile));
984
985        if (fprintf(
986                stream, line_format, value, percentile, total_count, inverted_percentile) < 0)
987        {
988            rc = EIO;
989            goto cleanup;
990        }
991    }
992
993    if (CLASSIC == format)
994    {
995        double mean   = hdr_mean(h)   / value_scale;
996        double stddev = hdr_stddev(h) / value_scale;
997        double max    = hdr_max(h)    / value_scale;
998
999        if (fprintf(
1000                stream, CLASSIC_FOOTER,  mean, stddev, max,
1001                h->total_count, h->bucket_count, h->sub_bucket_count) < 0)
1002        {
1003            rc = EIO;
1004            goto cleanup;
1005        }
1006    }
1007
1008    cleanup:
1009    return rc;
1010}
1011