aboutsummaryrefslogtreecommitdiff
path: root/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c
diff options
context:
space:
mode:
authorMitja Felicijan <mitja.felicijan@gmail.com>2026-01-21 22:52:54 +0100
committerMitja Felicijan <mitja.felicijan@gmail.com>2026-01-21 22:52:54 +0100
commitdcacc00e3750300617ba6e16eb346713f91a783a (patch)
tree38e2d4fb5ed9d119711d4295c6eda4b014af73fd /examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c
parent58dac10aeb8f5a041c46bddbeaf4c7966a99b998 (diff)
downloadcrep-dcacc00e3750300617ba6e16eb346713f91a783a.tar.gz
Remove testing data
Diffstat (limited to 'examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c')
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c1229
1 files changed, 0 insertions, 1229 deletions
diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c b/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c
deleted file mode 100644
index f469347..0000000
--- a/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c
+++ /dev/null
@@ -1,1229 +0,0 @@
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 <stdio.h>
11#include <string.h>
12#include <stdint.h>
13#include <errno.h>
14#include <inttypes.h>
15
16#include "hdr_histogram.h"
17#include "hdr_tests.h"
18#include "hdr_atomic.h"
19
20#ifndef HDR_MALLOC_INCLUDE
21#define HDR_MALLOC_INCLUDE "hdr_malloc.h"
22#endif
23
24#include HDR_MALLOC_INCLUDE
25
26/* ###### ####### ## ## ## ## ######## ###### */
27/* ## ## ## ## ## ## ### ## ## ## ## */
28/* ## ## ## ## ## #### ## ## ## */
29/* ## ## ## ## ## ## ## ## ## ###### */
30/* ## ## ## ## ## ## #### ## ## */
31/* ## ## ## ## ## ## ## ### ## ## ## */
32/* ###### ####### ####### ## ## ## ###### */
33
34static int32_t normalize_index(const struct hdr_histogram* h, int32_t index)
35{
36 int32_t normalized_index;
37 int32_t adjustment = 0;
38 if (h->normalizing_index_offset == 0)
39 {
40 return index;
41 }
42
43 normalized_index = index - h->normalizing_index_offset;
44
45 if (normalized_index < 0)
46 {
47 adjustment = h->counts_len;
48 }
49 else if (normalized_index >= h->counts_len)
50 {
51 adjustment = -h->counts_len;
52 }
53
54 return normalized_index + adjustment;
55}
56
57static int64_t counts_get_direct(const struct hdr_histogram* h, int32_t index)
58{
59 return h->counts[index];
60}
61
62static int64_t counts_get_normalised(const struct hdr_histogram* h, int32_t index)
63{
64 return counts_get_direct(h, normalize_index(h, index));
65}
66
67static void counts_inc_normalised(
68 struct hdr_histogram* h, int32_t index, int64_t value)
69{
70 int32_t normalised_index = normalize_index(h, index);
71 h->counts[normalised_index] += value;
72 h->total_count += value;
73}
74
75static void counts_inc_normalised_atomic(
76 struct hdr_histogram* h, int32_t index, int64_t value)
77{
78 int32_t normalised_index = normalize_index(h, index);
79
80 hdr_atomic_add_fetch_64(&h->counts[normalised_index], value);
81 hdr_atomic_add_fetch_64(&h->total_count, value);
82}
83
84static void update_min_max(struct hdr_histogram* h, int64_t value)
85{
86 h->min_value = (value < h->min_value && value != 0) ? value : h->min_value;
87 h->max_value = (value > h->max_value) ? value : h->max_value;
88}
89
90static void update_min_max_atomic(struct hdr_histogram* h, int64_t value)
91{
92 int64_t current_min_value;
93 int64_t current_max_value;
94 do
95 {
96 current_min_value = hdr_atomic_load_64(&h->min_value);
97
98 if (0 == value || current_min_value <= value)
99 {
100 break;
101 }
102 }
103 while (!hdr_atomic_compare_exchange_64(&h->min_value, &current_min_value, value));
104
105 do
106 {
107 current_max_value = hdr_atomic_load_64(&h->max_value);
108
109 if (value <= current_max_value)
110 {
111 break;
112 }
113 }
114 while (!hdr_atomic_compare_exchange_64(&h->max_value, &current_max_value, value));
115}
116
117
118/* ## ## ######## #### ## #### ######## ## ## */
119/* ## ## ## ## ## ## ## ## ## */
120/* ## ## ## ## ## ## ## #### */
121/* ## ## ## ## ## ## ## ## */
122/* ## ## ## ## ## ## ## ## */
123/* ## ## ## ## ## ## ## ## */
124/* ####### ## #### ######## #### ## ## */
125
126static int64_t power(int64_t base, int64_t exp)
127{
128 int64_t result = 1;
129 while(exp)
130 {
131 result *= base; exp--;
132 }
133 return result;
134}
135
136#if defined(_MSC_VER)
137# if defined(_WIN64)
138# pragma intrinsic(_BitScanReverse64)
139# else
140# pragma intrinsic(_BitScanReverse)
141# endif
142#endif
143
144static int32_t count_leading_zeros_64(int64_t value)
145{
146#if defined(_MSC_VER)
147 uint32_t leading_zero = 0;
148#if defined(_WIN64)
149 _BitScanReverse64(&leading_zero, value);
150#else
151 uint32_t high = value >> 32;
152 if (_BitScanReverse(&leading_zero, high))
153 {
154 leading_zero += 32;
155 }
156 else
157 {
158 uint32_t low = value & 0x00000000FFFFFFFF;
159 _BitScanReverse(&leading_zero, low);
160 }
161#endif
162 return 63 - leading_zero; /* smallest power of 2 containing value */
163#else
164 return __builtin_clzll(value); /* smallest power of 2 containing value */
165#endif
166}
167
168static int32_t get_bucket_index(const struct hdr_histogram* h, int64_t value)
169{
170 int32_t pow2ceiling = 64 - count_leading_zeros_64(value | h->sub_bucket_mask); /* smallest power of 2 containing value */
171 return pow2ceiling - h->unit_magnitude - (h->sub_bucket_half_count_magnitude + 1);
172}
173
174static int32_t get_sub_bucket_index(int64_t value, int32_t bucket_index, int32_t unit_magnitude)
175{
176 return (int32_t)(value >> (bucket_index + unit_magnitude));
177}
178
179static int32_t counts_index(const struct hdr_histogram* h, int32_t bucket_index, int32_t sub_bucket_index)
180{
181 /* Calculate the index for the first entry in the bucket: */
182 /* (The following is the equivalent of ((bucket_index + 1) * subBucketHalfCount) ): */
183 int32_t bucket_base_index = (bucket_index + 1) << h->sub_bucket_half_count_magnitude;
184 /* Calculate the offset in the bucket: */
185 int32_t offset_in_bucket = sub_bucket_index - h->sub_bucket_half_count;
186 /* The following is the equivalent of ((sub_bucket_index - subBucketHalfCount) + bucketBaseIndex; */
187 return bucket_base_index + offset_in_bucket;
188}
189
190static int64_t value_from_index(int32_t bucket_index, int32_t sub_bucket_index, int32_t unit_magnitude)
191{
192 return ((int64_t) sub_bucket_index) << (bucket_index + unit_magnitude);
193}
194
195int32_t counts_index_for(const struct hdr_histogram* h, int64_t value)
196{
197 int32_t bucket_index = get_bucket_index(h, value);
198 int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
199
200 return counts_index(h, bucket_index, sub_bucket_index);
201}
202
203int64_t hdr_value_at_index(const struct hdr_histogram *h, int32_t index)
204{
205 int32_t bucket_index = (index >> h->sub_bucket_half_count_magnitude) - 1;
206 int32_t sub_bucket_index = (index & (h->sub_bucket_half_count - 1)) + h->sub_bucket_half_count;
207
208 if (bucket_index < 0)
209 {
210 sub_bucket_index -= h->sub_bucket_half_count;
211 bucket_index = 0;
212 }
213
214 return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
215}
216
217int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value)
218{
219 int32_t bucket_index = get_bucket_index(h, value);
220 int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
221 int32_t adjusted_bucket = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index;
222 return INT64_C(1) << (h->unit_magnitude + adjusted_bucket);
223}
224
225static int64_t size_of_equivalent_value_range_given_bucket_indices(
226 const struct hdr_histogram *h,
227 int32_t bucket_index,
228 int32_t sub_bucket_index)
229{
230 const int32_t adjusted_bucket = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index;
231 return INT64_C(1) << (h->unit_magnitude + adjusted_bucket);
232}
233
234static int64_t lowest_equivalent_value(const struct hdr_histogram* h, int64_t value)
235{
236 int32_t bucket_index = get_bucket_index(h, value);
237 int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude);
238 return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
239}
240
241static int64_t lowest_equivalent_value_given_bucket_indices(
242 const struct hdr_histogram *h,
243 int32_t bucket_index,
244 int32_t sub_bucket_index)
245{
246 return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
247}
248
249int64_t hdr_next_non_equivalent_value(const struct hdr_histogram *h, int64_t value)
250{
251 return lowest_equivalent_value(h, value) + hdr_size_of_equivalent_value_range(h, value);
252}
253
254static int64_t highest_equivalent_value(const struct hdr_histogram* h, int64_t value)
255{
256 return hdr_next_non_equivalent_value(h, value) - 1;
257}
258
259int64_t hdr_median_equivalent_value(const struct hdr_histogram *h, int64_t value)
260{
261 return lowest_equivalent_value(h, value) + (hdr_size_of_equivalent_value_range(h, value) >> 1);
262}
263
264static int64_t non_zero_min(const struct hdr_histogram* h)
265{
266 if (INT64_MAX == h->min_value)
267 {
268 return INT64_MAX;
269 }
270
271 return lowest_equivalent_value(h, h->min_value);
272}
273
274void hdr_reset_internal_counters(struct hdr_histogram* h)
275{
276 int min_non_zero_index = -1;
277 int max_index = -1;
278 int64_t observed_total_count = 0;
279 int i;
280
281 for (i = 0; i < h->counts_len; i++)
282 {
283 int64_t count_at_index;
284
285 if ((count_at_index = counts_get_direct(h, i)) > 0)
286 {
287 observed_total_count += count_at_index;
288 max_index = i;
289 if (min_non_zero_index == -1 && i != 0)
290 {
291 min_non_zero_index = i;
292 }
293 }
294 }
295
296 if (max_index == -1)
297 {
298 h->max_value = 0;
299 }
300 else
301 {
302 int64_t max_value = hdr_value_at_index(h, max_index);
303 h->max_value = highest_equivalent_value(h, max_value);
304 }
305
306 if (min_non_zero_index == -1)
307 {
308 h->min_value = INT64_MAX;
309 }
310 else
311 {
312 h->min_value = hdr_value_at_index(h, min_non_zero_index);
313 }
314
315 h->total_count = observed_total_count;
316}
317
318static int32_t buckets_needed_to_cover_value(int64_t value, int32_t sub_bucket_count, int32_t unit_magnitude)
319{
320 int64_t smallest_untrackable_value = ((int64_t) sub_bucket_count) << unit_magnitude;
321 int32_t buckets_needed = 1;
322 while (smallest_untrackable_value <= value)
323 {
324 if (smallest_untrackable_value > INT64_MAX / 2)
325 {
326 return buckets_needed + 1;
327 }
328 smallest_untrackable_value <<= 1;
329 buckets_needed++;
330 }
331
332 return buckets_needed;
333}
334
335/* ## ## ######## ## ## ####### ######## ## ## */
336/* ### ### ## ### ### ## ## ## ## ## ## */
337/* #### #### ## #### #### ## ## ## ## #### */
338/* ## ### ## ###### ## ### ## ## ## ######## ## */
339/* ## ## ## ## ## ## ## ## ## ## */
340/* ## ## ## ## ## ## ## ## ## ## */
341/* ## ## ######## ## ## ####### ## ## ## */
342
343int hdr_calculate_bucket_config(
344 int64_t lowest_discernible_value,
345 int64_t highest_trackable_value,
346 int significant_figures,
347 struct hdr_histogram_bucket_config* cfg)
348{
349 int32_t sub_bucket_count_magnitude;
350 int64_t largest_value_with_single_unit_resolution;
351
352 if (lowest_discernible_value < 1 ||
353 significant_figures < 1 || 5 < significant_figures ||
354 lowest_discernible_value * 2 > highest_trackable_value)
355 {
356 return EINVAL;
357 }
358
359 cfg->lowest_discernible_value = lowest_discernible_value;
360 cfg->significant_figures = significant_figures;
361 cfg->highest_trackable_value = highest_trackable_value;
362
363 largest_value_with_single_unit_resolution = 2 * power(10, significant_figures);
364 sub_bucket_count_magnitude = (int32_t) ceil(log((double)largest_value_with_single_unit_resolution) / log(2));
365 cfg->sub_bucket_half_count_magnitude = ((sub_bucket_count_magnitude > 1) ? sub_bucket_count_magnitude : 1) - 1;
366
367 double unit_magnitude = log((double)lowest_discernible_value) / log(2);
368 if (INT32_MAX < unit_magnitude)
369 {
370 return EINVAL;
371 }
372
373 cfg->unit_magnitude = (int32_t) unit_magnitude;
374 cfg->sub_bucket_count = (int32_t) pow(2, (cfg->sub_bucket_half_count_magnitude + 1));
375 cfg->sub_bucket_half_count = cfg->sub_bucket_count / 2;
376 cfg->sub_bucket_mask = ((int64_t) cfg->sub_bucket_count - 1) << cfg->unit_magnitude;
377
378 if (cfg->unit_magnitude + cfg->sub_bucket_half_count_magnitude > 61)
379 {
380 return EINVAL;
381 }
382
383 cfg->bucket_count = buckets_needed_to_cover_value(highest_trackable_value, cfg->sub_bucket_count, (int32_t)cfg->unit_magnitude);
384 cfg->counts_len = (cfg->bucket_count + 1) * (cfg->sub_bucket_count / 2);
385
386 return 0;
387}
388
389void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg)
390{
391 h->lowest_discernible_value = cfg->lowest_discernible_value;
392 h->highest_trackable_value = cfg->highest_trackable_value;
393 h->unit_magnitude = (int32_t)cfg->unit_magnitude;
394 h->significant_figures = (int32_t)cfg->significant_figures;
395 h->sub_bucket_half_count_magnitude = cfg->sub_bucket_half_count_magnitude;
396 h->sub_bucket_half_count = cfg->sub_bucket_half_count;
397 h->sub_bucket_mask = cfg->sub_bucket_mask;
398 h->sub_bucket_count = cfg->sub_bucket_count;
399 h->min_value = INT64_MAX;
400 h->max_value = 0;
401 h->normalizing_index_offset = 0;
402 h->conversion_ratio = 1.0;
403 h->bucket_count = cfg->bucket_count;
404 h->counts_len = cfg->counts_len;
405 h->total_count = 0;
406}
407
408int hdr_init(
409 int64_t lowest_discernible_value,
410 int64_t highest_trackable_value,
411 int significant_figures,
412 struct hdr_histogram** result)
413{
414 int64_t* counts;
415 struct hdr_histogram_bucket_config cfg;
416 struct hdr_histogram* histogram;
417
418 int r = hdr_calculate_bucket_config(lowest_discernible_value, highest_trackable_value, significant_figures, &cfg);
419 if (r)
420 {
421 return r;
422 }
423
424 counts = (int64_t*) hdr_calloc((size_t) cfg.counts_len, sizeof(int64_t));
425 if (!counts)
426 {
427 return ENOMEM;
428 }
429
430 histogram = (struct hdr_histogram*) hdr_calloc(1, sizeof(struct hdr_histogram));
431 if (!histogram)
432 {
433 hdr_free(counts);
434 return ENOMEM;
435 }
436
437 histogram->counts = counts;
438
439 hdr_init_preallocated(histogram, &cfg);
440 *result = histogram;
441
442 return 0;
443}
444
445void hdr_close(struct hdr_histogram* h)
446{
447 if (h) {
448 hdr_free(h->counts);
449 hdr_free(h);
450 }
451}
452
453int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result)
454{
455 return hdr_init(1, highest_trackable_value, significant_figures, result);
456}
457
458/* reset a histogram to zero. */
459void hdr_reset(struct hdr_histogram *h)
460{
461 h->total_count=0;
462 h->min_value = INT64_MAX;
463 h->max_value = 0;
464 memset(h->counts, 0, (sizeof(int64_t) * h->counts_len));
465}
466
467size_t hdr_get_memory_size(struct hdr_histogram *h)
468{
469 return sizeof(struct hdr_histogram) + h->counts_len * sizeof(int64_t);
470}
471
472/* ## ## ######## ######## ### ######## ######## ###### */
473/* ## ## ## ## ## ## ## ## ## ## ## ## */
474/* ## ## ## ## ## ## ## ## ## ## ## */
475/* ## ## ######## ## ## ## ## ## ###### ###### */
476/* ## ## ## ## ## ######### ## ## ## */
477/* ## ## ## ## ## ## ## ## ## ## ## */
478/* ####### ## ######## ## ## ## ######## ###### */
479
480
481bool hdr_record_value(struct hdr_histogram* h, int64_t value)
482{
483 return hdr_record_values(h, value, 1);
484}
485
486bool hdr_record_value_atomic(struct hdr_histogram* h, int64_t value)
487{
488 return hdr_record_values_atomic(h, value, 1);
489}
490
491bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count)
492{
493 int32_t counts_index;
494
495 if (value < 0)
496 {
497 return false;
498 }
499
500 counts_index = counts_index_for(h, value);
501
502 if (counts_index < 0 || h->counts_len <= counts_index)
503 {
504 return false;
505 }
506
507 counts_inc_normalised(h, counts_index, count);
508 update_min_max(h, value);
509
510 return true;
511}
512
513bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count)
514{
515 int32_t counts_index;
516
517 if (value < 0)
518 {
519 return false;
520 }
521
522 counts_index = counts_index_for(h, value);
523
524 if (counts_index < 0 || h->counts_len <= counts_index)
525 {
526 return false;
527 }
528
529 counts_inc_normalised_atomic(h, counts_index, count);
530 update_min_max_atomic(h, value);
531
532 return true;
533}
534
535bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval)
536{
537 return hdr_record_corrected_values(h, value, 1, expected_interval);
538}
539
540bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expected_interval)
541{
542 return hdr_record_corrected_values_atomic(h, value, 1, expected_interval);
543}
544
545bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval)
546{
547 int64_t missing_value;
548
549 if (!hdr_record_values(h, value, count))
550 {
551 return false;
552 }
553
554 if (expected_interval <= 0 || value <= expected_interval)
555 {
556 return true;
557 }
558
559 missing_value = value - expected_interval;
560 for (; missing_value >= expected_interval; missing_value -= expected_interval)
561 {
562 if (!hdr_record_values(h, missing_value, count))
563 {
564 return false;
565 }
566 }
567
568 return true;
569}
570
571bool hdr_record_corrected_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval)
572{
573 int64_t missing_value;
574
575 if (!hdr_record_values_atomic(h, value, count))
576 {
577 return false;
578 }
579
580 if (expected_interval <= 0 || value <= expected_interval)
581 {
582 return true;
583 }
584
585 missing_value = value - expected_interval;
586 for (; missing_value >= expected_interval; missing_value -= expected_interval)
587 {
588 if (!hdr_record_values_atomic(h, missing_value, count))
589 {
590 return false;
591 }
592 }
593
594 return true;
595}
596
597int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from)
598{
599 struct hdr_iter iter;
600 int64_t dropped = 0;
601 hdr_iter_recorded_init(&iter, from);
602
603 while (hdr_iter_next(&iter))
604 {
605 int64_t value = iter.value;
606 int64_t count = iter.count;
607
608 if (!hdr_record_values(h, value, count))
609 {
610 dropped += count;
611 }
612 }
613
614 return dropped;
615}
616
617int64_t hdr_add_while_correcting_for_coordinated_omission(
618 struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval)
619{
620 struct hdr_iter iter;
621 int64_t dropped = 0;
622 hdr_iter_recorded_init(&iter, from);
623
624 while (hdr_iter_next(&iter))
625 {
626 int64_t value = iter.value;
627 int64_t count = iter.count;
628
629 if (!hdr_record_corrected_values(h, value, count, expected_interval))
630 {
631 dropped += count;
632 }
633 }
634
635 return dropped;
636}
637
638
639
640/* ## ## ### ## ## ## ######## ###### */
641/* ## ## ## ## ## ## ## ## ## ## */
642/* ## ## ## ## ## ## ## ## ## */
643/* ## ## ## ## ## ## ## ###### ###### */
644/* ## ## ######### ## ## ## ## ## */
645/* ## ## ## ## ## ## ## ## ## ## */
646/* ### ## ## ######## ####### ######## ###### */
647
648
649int64_t hdr_max(const struct hdr_histogram* h)
650{
651 if (0 == h->max_value)
652 {
653 return 0;
654 }
655
656 return highest_equivalent_value(h, h->max_value);
657}
658
659int64_t hdr_min(const struct hdr_histogram* h)
660{
661 if (0 < hdr_count_at_index(h, 0))
662 {
663 return 0;
664 }
665
666 return non_zero_min(h);
667}
668
669static int64_t get_value_from_idx_up_to_count(const struct hdr_histogram* h, int64_t count_at_percentile)
670{
671 int64_t count_to_idx = 0;
672
673 count_at_percentile = 0 < count_at_percentile ? count_at_percentile : 1;
674 for (int32_t idx = 0; idx < h->counts_len; idx++)
675 {
676 count_to_idx += h->counts[idx];
677 if (count_to_idx >= count_at_percentile)
678 {
679 return hdr_value_at_index(h, idx);
680 }
681 }
682
683 return 0;
684}
685
686
687int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile)
688{
689 double requested_percentile = percentile < 100.0 ? percentile : 100.0;
690 int64_t count_at_percentile =
691 (int64_t) (((requested_percentile / 100) * h->total_count) + 0.5);
692 int64_t value_from_idx = get_value_from_idx_up_to_count(h, count_at_percentile);
693 if (percentile == 0.0)
694 {
695 return lowest_equivalent_value(h, value_from_idx);
696 }
697 return highest_equivalent_value(h, value_from_idx);
698}
699
700int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length)
701{
702 if (NULL == percentiles || NULL == values)
703 {
704 return EINVAL;
705 }
706
707 struct hdr_iter iter;
708 const int64_t total_count = h->total_count;
709 // to avoid allocations we use the values array for intermediate computation
710 // i.e. to store the expected cumulative count at each percentile
711 for (size_t i = 0; i < length; i++)
712 {
713 const double requested_percentile = percentiles[i] < 100.0 ? percentiles[i] : 100.0;
714 const int64_t count_at_percentile =
715 (int64_t) (((requested_percentile / 100) * total_count) + 0.5);
716 values[i] = count_at_percentile > 1 ? count_at_percentile : 1;
717 }
718
719 hdr_iter_init(&iter, h);
720 int64_t total = 0;
721 size_t at_pos = 0;
722 while (hdr_iter_next(&iter) && at_pos < length)
723 {
724 total += iter.count;
725 while (at_pos < length && total >= values[at_pos])
726 {
727 values[at_pos] = highest_equivalent_value(h, iter.value);
728 at_pos++;
729 }
730 }
731 return 0;
732}
733
734double hdr_mean(const struct hdr_histogram* h)
735{
736 struct hdr_iter iter;
737 int64_t total = 0;
738
739 hdr_iter_init(&iter, h);
740
741 while (hdr_iter_next(&iter))
742 {
743 if (0 != iter.count)
744 {
745 total += iter.count * hdr_median_equivalent_value(h, iter.value);
746 }
747 }
748
749 return (total * 1.0) / h->total_count;
750}
751
752double hdr_stddev(const struct hdr_histogram* h)
753{
754 double mean = hdr_mean(h);
755 double geometric_dev_total = 0.0;
756
757 struct hdr_iter iter;
758 hdr_iter_init(&iter, h);
759
760 while (hdr_iter_next(&iter))
761 {
762 if (0 != iter.count)
763 {
764 double dev = (hdr_median_equivalent_value(h, iter.value) * 1.0) - mean;
765 geometric_dev_total += (dev * dev) * iter.count;
766 }
767 }
768
769 return sqrt(geometric_dev_total / h->total_count);
770}
771
772bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b)
773{
774 return lowest_equivalent_value(h, a) == lowest_equivalent_value(h, b);
775}
776
777int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value)
778{
779 return lowest_equivalent_value(h, value);
780}
781
782int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value)
783{
784 return counts_get_normalised(h, counts_index_for(h, value));
785}
786
787int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index)
788{
789 return counts_get_normalised(h, index);
790}
791
792
793/* #### ######## ######## ######## ### ######## ####### ######## ###### */
794/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */
795/* ## ## ## ## ## ## ## ## ## ## ## ## ## */
796/* ## ## ###### ######## ## ## ## ## ## ######## ###### */
797/* ## ## ## ## ## ######### ## ## ## ## ## ## */
798/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */
799/* #### ## ######## ## ## ## ## ## ####### ## ## ###### */
800
801
802static bool has_buckets(struct hdr_iter* iter)
803{
804 return iter->counts_index < iter->h->counts_len;
805}
806
807static bool has_next(struct hdr_iter* iter)
808{
809 return iter->cumulative_count < iter->total_count;
810}
811
812static bool move_next(struct hdr_iter* iter)
813{
814 iter->counts_index++;
815
816 if (!has_buckets(iter))
817 {
818 return false;
819 }
820
821 iter->count = counts_get_normalised(iter->h, iter->counts_index);
822 iter->cumulative_count += iter->count;
823 const int64_t value = hdr_value_at_index(iter->h, iter->counts_index);
824 const int32_t bucket_index = get_bucket_index(iter->h, value);
825 const int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, iter->h->unit_magnitude);
826 const int64_t leq = lowest_equivalent_value_given_bucket_indices(iter->h, bucket_index, sub_bucket_index);
827 const int64_t size_of_equivalent_value_range = size_of_equivalent_value_range_given_bucket_indices(
828 iter->h, bucket_index, sub_bucket_index);
829 iter->lowest_equivalent_value = leq;
830 iter->value = value;
831 iter->highest_equivalent_value = leq + size_of_equivalent_value_range - 1;
832 iter->median_equivalent_value = leq + (size_of_equivalent_value_range >> 1);
833
834 return true;
835}
836
837static int64_t peek_next_value_from_index(struct hdr_iter* iter)
838{
839 return hdr_value_at_index(iter->h, iter->counts_index + 1);
840}
841
842static bool next_value_greater_than_reporting_level_upper_bound(
843 struct hdr_iter *iter, int64_t reporting_level_upper_bound)
844{
845 if (iter->counts_index >= iter->h->counts_len)
846 {
847 return false;
848 }
849
850 return peek_next_value_from_index(iter) > reporting_level_upper_bound;
851}
852
853static bool basic_iter_next(struct hdr_iter *iter)
854{
855 if (!has_next(iter) || iter->counts_index >= iter->h->counts_len)
856 {
857 return false;
858 }
859
860 move_next(iter);
861
862 return true;
863}
864
865static void update_iterated_values(struct hdr_iter* iter, int64_t new_value_iterated_to)
866{
867 iter->value_iterated_from = iter->value_iterated_to;
868 iter->value_iterated_to = new_value_iterated_to;
869}
870
871static bool all_values_iter_next(struct hdr_iter* iter)
872{
873 bool result = move_next(iter);
874
875 if (result)
876 {
877 update_iterated_values(iter, iter->value);
878 }
879
880 return result;
881}
882
883void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h)
884{
885 iter->h = h;
886
887 iter->counts_index = -1;
888 iter->total_count = h->total_count;
889 iter->count = 0;
890 iter->cumulative_count = 0;
891 iter->value = 0;
892 iter->highest_equivalent_value = 0;
893 iter->value_iterated_from = 0;
894 iter->value_iterated_to = 0;
895
896 iter->_next_fp = all_values_iter_next;
897}
898
899bool hdr_iter_next(struct hdr_iter* iter)
900{
901 return iter->_next_fp(iter);
902}
903
904/* ######## ######## ######## ###### ######## ## ## ######## #### ## ######## ###### */
905/* ## ## ## ## ## ## ## ## ### ## ## ## ## ## ## ## */
906/* ## ## ## ## ## ## ## #### ## ## ## ## ## ## */
907/* ######## ###### ######## ## ###### ## ## ## ## ## ## ###### ###### */
908/* ## ## ## ## ## ## ## #### ## ## ## ## ## */
909/* ## ## ## ## ## ## ## ## ### ## ## ## ## ## ## */
910/* ## ######## ## ## ###### ######## ## ## ## #### ######## ######## ###### */
911
912static bool percentile_iter_next(struct hdr_iter* iter)
913{
914 int64_t temp, half_distance, percentile_reporting_ticks;
915
916 struct hdr_iter_percentiles* percentiles = &iter->specifics.percentiles;
917
918 if (!has_next(iter))
919 {
920 if (percentiles->seen_last_value)
921 {
922 return false;
923 }
924
925 percentiles->seen_last_value = true;
926 percentiles->percentile = 100.0;
927
928 return true;
929 }
930
931 if (iter->counts_index == -1 && !basic_iter_next(iter))
932 {
933 return false;
934 }
935
936 do
937 {
938 double current_percentile = (100.0 * (double) iter->cumulative_count) / iter->h->total_count;
939 if (iter->count != 0 &&
940 percentiles->percentile_to_iterate_to <= current_percentile)
941 {
942 update_iterated_values(iter, highest_equivalent_value(iter->h, iter->value));
943
944 percentiles->percentile = percentiles->percentile_to_iterate_to;
945 temp = (int64_t)(log(100 / (100.0 - (percentiles->percentile_to_iterate_to))) / log(2)) + 1;
946 half_distance = (int64_t) pow(2, (double) temp);
947 percentile_reporting_ticks = percentiles->ticks_per_half_distance * half_distance;
948 percentiles->percentile_to_iterate_to += 100.0 / percentile_reporting_ticks;
949
950 return true;
951 }
952 }
953 while (basic_iter_next(iter));
954
955 return true;
956}
957
958void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance)
959{
960 iter->h = h;
961
962 hdr_iter_init(iter, h);
963
964 iter->specifics.percentiles.seen_last_value = false;
965 iter->specifics.percentiles.ticks_per_half_distance = ticks_per_half_distance;
966 iter->specifics.percentiles.percentile_to_iterate_to = 0.0;
967 iter->specifics.percentiles.percentile = 0.0;
968
969 iter->_next_fp = percentile_iter_next;
970}
971
972static void format_line_string(char* str, size_t len, int significant_figures, format_type format)
973{
974#if defined(_MSC_VER)
975#define snprintf _snprintf
976#pragma warning(push)
977#pragma warning(disable: 4996)
978#endif
979 const char* format_str = "%s%d%s";
980
981 switch (format)
982 {
983 case CSV:
984 snprintf(str, len, format_str, "%.", significant_figures, "f,%f,%d,%.2f\n");
985 break;
986 case CLASSIC:
987 snprintf(str, len, format_str, "%12.", significant_figures, "f %12f %12d %12.2f\n");
988 break;
989 default:
990 snprintf(str, len, format_str, "%12.", significant_figures, "f %12f %12d %12.2f\n");
991 }
992#if defined(_MSC_VER)
993#undef snprintf
994#pragma warning(pop)
995#endif
996}
997
998
999/* ######## ######## ###### ####### ######## ######## ######## ######## */
1000/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */
1001/* ## ## ## ## ## ## ## ## ## ## ## ## ## */
1002/* ######## ###### ## ## ## ######## ## ## ###### ## ## */
1003/* ## ## ## ## ## ## ## ## ## ## ## ## ## */
1004/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */
1005/* ## ## ######## ###### ####### ## ## ######## ######## ######## */
1006
1007
1008static bool recorded_iter_next(struct hdr_iter* iter)
1009{
1010 while (basic_iter_next(iter))
1011 {
1012 if (iter->count != 0)
1013 {
1014 update_iterated_values(iter, iter->value);
1015
1016 iter->specifics.recorded.count_added_in_this_iteration_step = iter->count;
1017 return true;
1018 }
1019 }
1020
1021 return false;
1022}
1023
1024void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h)
1025{
1026 hdr_iter_init(iter, h);
1027
1028 iter->specifics.recorded.count_added_in_this_iteration_step = 0;
1029
1030 iter->_next_fp = recorded_iter_next;
1031}
1032
1033/* ## #### ## ## ######## ### ######## */
1034/* ## ## ### ## ## ## ## ## ## */
1035/* ## ## #### ## ## ## ## ## ## */
1036/* ## ## ## ## ## ###### ## ## ######## */
1037/* ## ## ## #### ## ######### ## ## */
1038/* ## ## ## ### ## ## ## ## ## */
1039/* ######## #### ## ## ######## ## ## ## ## */
1040
1041
1042static bool iter_linear_next(struct hdr_iter* iter)
1043{
1044 struct hdr_iter_linear* linear = &iter->specifics.linear;
1045
1046 linear->count_added_in_this_iteration_step = 0;
1047
1048 if (has_next(iter) ||
1049 next_value_greater_than_reporting_level_upper_bound(
1050 iter, linear->next_value_reporting_level_lowest_equivalent))
1051 {
1052 do
1053 {
1054 if (iter->value >= linear->next_value_reporting_level_lowest_equivalent)
1055 {
1056 update_iterated_values(iter, linear->next_value_reporting_level);
1057
1058 linear->next_value_reporting_level += linear->value_units_per_bucket;
1059 linear->next_value_reporting_level_lowest_equivalent =
1060 lowest_equivalent_value(iter->h, linear->next_value_reporting_level);
1061
1062 return true;
1063 }
1064
1065 if (!move_next(iter))
1066 {
1067 return true;
1068 }
1069
1070 linear->count_added_in_this_iteration_step += iter->count;
1071 }
1072 while (true);
1073 }
1074
1075 return false;
1076}
1077
1078
1079void hdr_iter_linear_init(struct hdr_iter* iter, const struct hdr_histogram* h, int64_t value_units_per_bucket)
1080{
1081 hdr_iter_init(iter, h);
1082
1083 iter->specifics.linear.count_added_in_this_iteration_step = 0;
1084 iter->specifics.linear.value_units_per_bucket = value_units_per_bucket;
1085 iter->specifics.linear.next_value_reporting_level = value_units_per_bucket;
1086 iter->specifics.linear.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_per_bucket);
1087
1088 iter->_next_fp = iter_linear_next;
1089}
1090
1091void hdr_iter_linear_set_value_units_per_bucket(struct hdr_iter* iter, int64_t value_units_per_bucket)
1092{
1093 iter->specifics.linear.value_units_per_bucket = value_units_per_bucket;
1094}
1095
1096/* ## ####### ###### ### ######## #### ######## ## ## ## ## #### ###### */
1097/* ## ## ## ## ## ## ## ## ## ## ## ## ## ### ### ## ## ## */
1098/* ## ## ## ## ## ## ## ## ## ## ## ## #### #### ## ## */
1099/* ## ## ## ## #### ## ## ######## ## ## ######### ## ### ## ## ## */
1100/* ## ## ## ## ## ######### ## ## ## ## ## ## ## ## ## ## */
1101/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## */
1102/* ######## ####### ###### ## ## ## ## #### ## ## ## ## ## #### ###### */
1103
1104static bool log_iter_next(struct hdr_iter *iter)
1105{
1106 struct hdr_iter_log* logarithmic = &iter->specifics.log;
1107
1108 logarithmic->count_added_in_this_iteration_step = 0;
1109
1110 if (has_next(iter) ||
1111 next_value_greater_than_reporting_level_upper_bound(
1112 iter, logarithmic->next_value_reporting_level_lowest_equivalent))
1113 {
1114 do
1115 {
1116 if (iter->value >= logarithmic->next_value_reporting_level_lowest_equivalent)
1117 {
1118 update_iterated_values(iter, logarithmic->next_value_reporting_level);
1119
1120 logarithmic->next_value_reporting_level *= (int64_t)logarithmic->log_base;
1121 logarithmic->next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(iter->h, logarithmic->next_value_reporting_level);
1122
1123 return true;
1124 }
1125
1126 if (!move_next(iter))
1127 {
1128 return true;
1129 }
1130
1131 logarithmic->count_added_in_this_iteration_step += iter->count;
1132 }
1133 while (true);
1134 }
1135
1136 return false;
1137}
1138
1139void hdr_iter_log_init(
1140 struct hdr_iter* iter,
1141 const struct hdr_histogram* h,
1142 int64_t value_units_first_bucket,
1143 double log_base)
1144{
1145 hdr_iter_init(iter, h);
1146 iter->specifics.log.count_added_in_this_iteration_step = 0;
1147 iter->specifics.log.log_base = log_base;
1148 iter->specifics.log.next_value_reporting_level = value_units_first_bucket;
1149 iter->specifics.log.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_first_bucket);
1150
1151 iter->_next_fp = log_iter_next;
1152}
1153
1154/* Printing. */
1155
1156static const char* format_head_string(format_type format)
1157{
1158 switch (format)
1159 {
1160 case CSV:
1161 return "%s,%s,%s,%s\n";
1162 case CLASSIC:
1163 default:
1164 return "%12s %12s %12s %12s\n\n";
1165 }
1166}
1167
1168static const char CLASSIC_FOOTER[] =
1169 "#[Mean = %12.3f, StdDeviation = %12.3f]\n"
1170 "#[Max = %12.3f, Total count = %12" PRIu64 "]\n"
1171 "#[Buckets = %12d, SubBuckets = %12d]\n";
1172
1173int hdr_percentiles_print(
1174 struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance,
1175 double value_scale, format_type format)
1176{
1177 char line_format[25];
1178 const char* head_format;
1179 int rc = 0;
1180 struct hdr_iter iter;
1181 struct hdr_iter_percentiles * percentiles;
1182
1183 format_line_string(line_format, 25, h->significant_figures, format);
1184 head_format = format_head_string(format);
1185
1186 hdr_iter_percentile_init(&iter, h, ticks_per_half_distance);
1187
1188 if (fprintf(
1189 stream, head_format,
1190 "Value", "Percentile", "TotalCount", "1/(1-Percentile)") < 0)
1191 {
1192 rc = EIO;
1193 goto cleanup;
1194 }
1195
1196 percentiles = &iter.specifics.percentiles;
1197 while (hdr_iter_next(&iter))
1198 {
1199 double value = iter.highest_equivalent_value / value_scale;
1200 double percentile = percentiles->percentile / 100.0;
1201 int64_t total_count = iter.cumulative_count;
1202 double inverted_percentile = (1.0 / (1.0 - percentile));
1203
1204 if (fprintf(
1205 stream, line_format, value, percentile, total_count, inverted_percentile) < 0)
1206 {
1207 rc = EIO;
1208 goto cleanup;
1209 }
1210 }
1211
1212 if (CLASSIC == format)
1213 {
1214 double mean = hdr_mean(h) / value_scale;
1215 double stddev = hdr_stddev(h) / value_scale;
1216 double max = hdr_max(h) / value_scale;
1217
1218 if (fprintf(
1219 stream, CLASSIC_FOOTER, mean, stddev, max,
1220 h->total_count, h->bucket_count, h->sub_bucket_count) < 0)
1221 {
1222 rc = EIO;
1223 goto cleanup;
1224 }
1225 }
1226
1227 cleanup:
1228 return rc;
1229}
generated by cgit v1.2.3 (git 2.46.0) at 2026-04-30 02:06:05 +0000