aboutsummaryrefslogtreecommitdiff
path: root/examples/redis-unstable/deps/hdr_histogram
diff options
context:
space:
mode:
Diffstat (limited to 'examples/redis-unstable/deps/hdr_histogram')
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/COPYING.txt121
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/LICENSE.txt41
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/Makefile27
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/README.md78
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/hdr_atomic.h146
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c1229
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/hdr_histogram.h521
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/hdr_redis_malloc.h13
-rw-r--r--examples/redis-unstable/deps/hdr_histogram/hdr_tests.h22
9 files changed, 2198 insertions, 0 deletions
diff --git a/examples/redis-unstable/deps/hdr_histogram/COPYING.txt b/examples/redis-unstable/deps/hdr_histogram/COPYING.txt
new file mode 100644
index 0000000..0e259d4
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/COPYING.txt
@@ -0,0 +1,121 @@
1Creative Commons Legal Code
2
3CC0 1.0 Universal
4
5 CREATIVE COMMONS CORPORATION IS NOT A LAW FIRM AND DOES NOT PROVIDE
6 LEGAL SERVICES. DISTRIBUTION OF THIS DOCUMENT DOES NOT CREATE AN
7 ATTORNEY-CLIENT RELATIONSHIP. CREATIVE COMMONS PROVIDES THIS
8 INFORMATION ON AN "AS-IS" BASIS. CREATIVE COMMONS MAKES NO WARRANTIES
9 REGARDING THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS
10 PROVIDED HEREUNDER, AND DISCLAIMS LIABILITY FOR DAMAGES RESULTING FROM
11 THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS PROVIDED
12 HEREUNDER.
13
14Statement of Purpose
15
16The laws of most jurisdictions throughout the world automatically confer
17exclusive Copyright and Related Rights (defined below) upon the creator
18and subsequent owner(s) (each and all, an "owner") of an original work of
19authorship and/or a database (each, a "Work").
20
21Certain owners wish to permanently relinquish those rights to a Work for
22the purpose of contributing to a commons of creative, cultural and
23scientific works ("Commons") that the public can reliably and without fear
24of later claims of infringement build upon, modify, incorporate in other
25works, reuse and redistribute as freely as possible in any form whatsoever
26and for any purposes, including without limitation commercial purposes.
27These owners may contribute to the Commons to promote the ideal of a free
28culture and the further production of creative, cultural and scientific
29works, or to gain reputation or greater distribution for their Work in
30part through the use and efforts of others.
31
32For these and/or other purposes and motivations, and without any
33expectation of additional consideration or compensation, the person
34associating CC0 with a Work (the "Affirmer"), to the extent that he or she
35is an owner of Copyright and Related Rights in the Work, voluntarily
36elects to apply CC0 to the Work and publicly distribute the Work under its
37terms, with knowledge of his or her Copyright and Related Rights in the
38Work and the meaning and intended legal effect of CC0 on those rights.
39
401. Copyright and Related Rights. A Work made available under CC0 may be
41protected by copyright and related or neighboring rights ("Copyright and
42Related Rights"). Copyright and Related Rights include, but are not
43limited to, the following:
44
45 i. the right to reproduce, adapt, distribute, perform, display,
46 communicate, and translate a Work;
47 ii. moral rights retained by the original author(s) and/or performer(s);
48iii. publicity and privacy rights pertaining to a person's image or
49 likeness depicted in a Work;
50 iv. rights protecting against unfair competition in regards to a Work,
51 subject to the limitations in paragraph 4(a), below;
52 v. rights protecting the extraction, dissemination, use and reuse of data
53 in a Work;
54 vi. database rights (such as those arising under Directive 96/9/EC of the
55 European Parliament and of the Council of 11 March 1996 on the legal
56 protection of databases, and under any national implementation
57 thereof, including any amended or successor version of such
58 directive); and
59vii. other similar, equivalent or corresponding rights throughout the
60 world based on applicable law or treaty, and any national
61 implementations thereof.
62
632. Waiver. To the greatest extent permitted by, but not in contravention
64of, applicable law, Affirmer hereby overtly, fully, permanently,
65irrevocably and unconditionally waives, abandons, and surrenders all of
66Affirmer's Copyright and Related Rights and associated claims and causes
67of action, whether now known or unknown (including existing as well as
68future claims and causes of action), in the Work (i) in all territories
69worldwide, (ii) for the maximum duration provided by applicable law or
70treaty (including future time extensions), (iii) in any current or future
71medium and for any number of copies, and (iv) for any purpose whatsoever,
72including without limitation commercial, advertising or promotional
73purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each
74member of the public at large and to the detriment of Affirmer's heirs and
75successors, fully intending that such Waiver shall not be subject to
76revocation, rescission, cancellation, termination, or any other legal or
77equitable action to disrupt the quiet enjoyment of the Work by the public
78as contemplated by Affirmer's express Statement of Purpose.
79
803. Public License Fallback. Should any part of the Waiver for any reason
81be judged legally invalid or ineffective under applicable law, then the
82Waiver shall be preserved to the maximum extent permitted taking into
83account Affirmer's express Statement of Purpose. In addition, to the
84extent the Waiver is so judged Affirmer hereby grants to each affected
85person a royalty-free, non transferable, non sublicensable, non exclusive,
86irrevocable and unconditional license to exercise Affirmer's Copyright and
87Related Rights in the Work (i) in all territories worldwide, (ii) for the
88maximum duration provided by applicable law or treaty (including future
89time extensions), (iii) in any current or future medium and for any number
90of copies, and (iv) for any purpose whatsoever, including without
91limitation commercial, advertising or promotional purposes (the
92"License"). The License shall be deemed effective as of the date CC0 was
93applied by Affirmer to the Work. Should any part of the License for any
94reason be judged legally invalid or ineffective under applicable law, such
95partial invalidity or ineffectiveness shall not invalidate the remainder
96of the License, and in such case Affirmer hereby affirms that he or she
97will not (i) exercise any of his or her remaining Copyright and Related
98Rights in the Work or (ii) assert any associated claims and causes of
99action with respect to the Work, in either case contrary to Affirmer's
100express Statement of Purpose.
101
1024. Limitations and Disclaimers.
103
104 a. No trademark or patent rights held by Affirmer are waived, abandoned,
105 surrendered, licensed or otherwise affected by this document.
106 b. Affirmer offers the Work as-is and makes no representations or
107 warranties of any kind concerning the Work, express, implied,
108 statutory or otherwise, including without limitation warranties of
109 title, merchantability, fitness for a particular purpose, non
110 infringement, or the absence of latent or other defects, accuracy, or
111 the present or absence of errors, whether or not discoverable, all to
112 the greatest extent permissible under applicable law.
113 c. Affirmer disclaims responsibility for clearing rights of other persons
114 that may apply to the Work or any use thereof, including without
115 limitation any person's Copyright and Related Rights in the Work.
116 Further, Affirmer disclaims responsibility for obtaining any necessary
117 consents, permissions or other rights required for any use of the
118 Work.
119 d. Affirmer understands and acknowledges that Creative Commons is not a
120 party to this document and has no duty or obligation with respect to
121 this CC0 or use of the Work.
diff --git a/examples/redis-unstable/deps/hdr_histogram/LICENSE.txt b/examples/redis-unstable/deps/hdr_histogram/LICENSE.txt
new file mode 100644
index 0000000..9b4e66e
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/LICENSE.txt
@@ -0,0 +1,41 @@
1The code in this repository code was Written by Gil Tene, Michael Barker,
2and Matt Warren, and released to the public domain, as explained at
3http://creativecommons.org/publicdomain/zero/1.0/
4
5For users of this code who wish to consume it under the "BSD" license
6rather than under the public domain or CC0 contribution text mentioned
7above, the code found under this directory is *also* provided under the
8following license (commonly referred to as the BSD 2-Clause License). This
9license does not detract from the above stated release of the code into
10the public domain, and simply represents an additional license granted by
11the Author.
12
13-----------------------------------------------------------------------------
14** Beginning of "BSD 2-Clause License" text. **
15
16 Copyright (c) 2012, 2013, 2014 Gil Tene
17 Copyright (c) 2014 Michael Barker
18 Copyright (c) 2014 Matt Warren
19 All rights reserved.
20
21 Redistribution and use in source and binary forms, with or without
22 modification, are permitted provided that the following conditions are met:
23
24 1. Redistributions of source code must retain the above copyright notice,
25 this list of conditions and the following disclaimer.
26
27 2. Redistributions in binary form must reproduce the above copyright notice,
28 this list of conditions and the following disclaimer in the documentation
29 and/or other materials provided with the distribution.
30
31 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
32 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
33 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
34 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
35 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
36 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
37 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
38 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
39 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
41 THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/examples/redis-unstable/deps/hdr_histogram/Makefile b/examples/redis-unstable/deps/hdr_histogram/Makefile
new file mode 100644
index 0000000..28dd93e
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/Makefile
@@ -0,0 +1,27 @@
1STD= -std=c99
2WARN= -Wall
3OPT= -Os
4
5R_CFLAGS= $(STD) $(WARN) $(OPT) $(DEBUG) $(CFLAGS) -DHDR_MALLOC_INCLUDE=\"hdr_redis_malloc.h\"
6R_LDFLAGS= $(LDFLAGS)
7DEBUG= -g
8
9R_CC=$(CC) $(R_CFLAGS)
10R_LD=$(CC) $(R_LDFLAGS)
11
12AR= ar
13ARFLAGS= rcs
14
15libhdrhistogram.a: hdr_histogram.o
16 $(AR) $(ARFLAGS) $@ $+
17
18hdr_histogram.o: hdr_histogram.h hdr_histogram.c
19
20.c.o:
21 $(R_CC) -c $<
22
23clean:
24 rm -f *.o
25 rm -f *.a
26
27
diff --git a/examples/redis-unstable/deps/hdr_histogram/README.md b/examples/redis-unstable/deps/hdr_histogram/README.md
new file mode 100644
index 0000000..93a156e
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/README.md
@@ -0,0 +1,78 @@
1HdrHistogram_c: 'C' port of High Dynamic Range (HDR) Histogram
2
3HdrHistogram
4----------------------------------------------
5
6[![Gitter chat](https://badges.gitter.im/HdrHistogram/HdrHistogram.png)](https://gitter.im/HdrHistogram/HdrHistogram)
7
8This port contains a subset of the functionality supported by the Java
9implementation. The current supported features are:
10
11* Standard histogram with 64 bit counts (32/16 bit counts not supported)
12* All iterator types (all values, recorded, percentiles, linear, logarithmic)
13* Histogram serialisation (encoding version 1.2, decoding 1.0-1.2)
14* Reader/writer phaser and interval recorder
15
16Features not supported, but planned
17
18* Auto-resizing of histograms
19
20Features unlikely to be implemented
21
22* Double histograms
23* Atomic/Concurrent histograms
24* 16/32 bit histograms
25
26# Simple Tutorial
27
28## Recording values
29
30```C
31#include <hdr_histogram.h>
32
33struct hdr_histogram* histogram;
34
35// Initialise the histogram
36hdr_init(
37 1, // Minimum value
38 INT64_C(3600000000), // Maximum value
39 3, // Number of significant figures
40 &histogram) // Pointer to initialise
41
42// Record value
43hdr_record_value(
44 histogram, // Histogram to record to
45 value) // Value to record
46
47// Record value n times
48hdr_record_values(
49 histogram, // Histogram to record to
50 value, // Value to record
51 10) // Record value 10 times
52
53// Record value with correction for co-ordinated omission.
54hdr_record_corrected_value(
55 histogram, // Histogram to record to
56 value, // Value to record
57 1000) // Record with expected interval of 1000.
58
59// Print out the values of the histogram
60hdr_percentiles_print(
61 histogram,
62 stdout, // File to write to
63 5, // Granularity of printed values
64 1.0, // Multiplier for results
65 CLASSIC); // Format CLASSIC/CSV supported.
66```
67
68## More examples
69
70For more detailed examples of recording and logging results look at the
71[hdr_decoder](examples/hdr_decoder.c)
72and [hiccup](examples/hiccup.c)
73examples. You can run hiccup and decoder
74and pipe the results of one into the other.
75
76```
77$ ./examples/hiccup | ./examples/hdr_decoder
78```
diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_atomic.h b/examples/redis-unstable/deps/hdr_histogram/hdr_atomic.h
new file mode 100644
index 0000000..ae1056a
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/hdr_atomic.h
@@ -0,0 +1,146 @@
1/**
2 * hdr_atomic.h
3 * Written by Philip Orwig and released to the public domain,
4 * as explained at http://creativecommons.org/publicdomain/zero/1.0/
5 */
6
7#ifndef HDR_ATOMIC_H__
8#define HDR_ATOMIC_H__
9
10
11#if defined(_MSC_VER)
12
13#include <stdint.h>
14#include <intrin.h>
15#include <stdbool.h>
16
17static void __inline * hdr_atomic_load_pointer(void** pointer)
18{
19 _ReadBarrier();
20 return *pointer;
21}
22
23static void hdr_atomic_store_pointer(void** pointer, void* value)
24{
25 _WriteBarrier();
26 *pointer = value;
27}
28
29static int64_t __inline hdr_atomic_load_64(int64_t* field)
30{
31 _ReadBarrier();
32 return *field;
33}
34
35static void __inline hdr_atomic_store_64(int64_t* field, int64_t value)
36{
37 _WriteBarrier();
38 *field = value;
39}
40
41static int64_t __inline hdr_atomic_exchange_64(volatile int64_t* field, int64_t value)
42{
43#if defined(_WIN64)
44 return _InterlockedExchange64(field, value);
45#else
46 int64_t comparand;
47 int64_t initial_value = *field;
48 do
49 {
50 comparand = initial_value;
51 initial_value = _InterlockedCompareExchange64(field, value, comparand);
52 }
53 while (comparand != initial_value);
54
55 return initial_value;
56#endif
57}
58
59static int64_t __inline hdr_atomic_add_fetch_64(volatile int64_t* field, int64_t value)
60{
61#if defined(_WIN64)
62 return _InterlockedExchangeAdd64(field, value) + value;
63#else
64 int64_t comparand;
65 int64_t initial_value = *field;
66 do
67 {
68 comparand = initial_value;
69 initial_value = _InterlockedCompareExchange64(field, comparand + value, comparand);
70 }
71 while (comparand != initial_value);
72
73 return initial_value + value;
74#endif
75}
76
77static bool __inline hdr_atomic_compare_exchange_64(volatile int64_t* field, int64_t* expected, int64_t desired)
78{
79 return *expected == _InterlockedCompareExchange64(field, desired, *expected);
80}
81
82#elif defined(__ATOMIC_SEQ_CST)
83
84#define hdr_atomic_load_pointer(x) __atomic_load_n(x, __ATOMIC_SEQ_CST)
85#define hdr_atomic_store_pointer(f,v) __atomic_store_n(f,v, __ATOMIC_SEQ_CST)
86#define hdr_atomic_load_64(x) __atomic_load_n(x, __ATOMIC_SEQ_CST)
87#define hdr_atomic_store_64(f,v) __atomic_store_n(f,v, __ATOMIC_SEQ_CST)
88#define hdr_atomic_exchange_64(f,i) __atomic_exchange_n(f,i, __ATOMIC_SEQ_CST)
89#define hdr_atomic_add_fetch_64(field, value) __atomic_add_fetch(field, value, __ATOMIC_SEQ_CST)
90#define hdr_atomic_compare_exchange_64(field, expected, desired) __atomic_compare_exchange_n(field, expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
91
92#elif defined(__x86_64__)
93
94#include <stdint.h>
95#include <stdbool.h>
96
97static inline void* hdr_atomic_load_pointer(void** pointer)
98{
99 void* p = *pointer;
100 asm volatile ("" ::: "memory");
101 return p;
102}
103
104static inline void hdr_atomic_store_pointer(void** pointer, void* value)
105{
106 asm volatile ("lock; xchgq %0, %1" : "+q" (value), "+m" (*pointer));
107}
108
109static inline int64_t hdr_atomic_load_64(int64_t* field)
110{
111 int64_t i = *field;
112 asm volatile ("" ::: "memory");
113 return i;
114}
115
116static inline void hdr_atomic_store_64(int64_t* field, int64_t value)
117{
118 asm volatile ("lock; xchgq %0, %1" : "+q" (value), "+m" (*field));
119}
120
121static inline int64_t hdr_atomic_exchange_64(volatile int64_t* field, int64_t value)
122{
123 int64_t result = 0;
124 asm volatile ("lock; xchgq %1, %2" : "=r" (result), "+q" (value), "+m" (*field));
125 return result;
126}
127
128static inline int64_t hdr_atomic_add_fetch_64(volatile int64_t* field, int64_t value)
129{
130 return __sync_add_and_fetch(field, value);
131}
132
133static inline bool hdr_atomic_compare_exchange_64(volatile int64_t* field, int64_t* expected, int64_t desired)
134{
135 int64_t original;
136 asm volatile( "lock; cmpxchgq %2, %1" : "=a"(original), "+m"(*field) : "q"(desired), "0"(*expected));
137 return original == *expected;
138}
139
140#else
141
142#error "Unable to determine atomic operations for your platform"
143
144#endif
145
146#endif /* HDR_ATOMIC_H__ */
diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c b/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c
new file mode 100644
index 0000000..f469347
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c
@@ -0,0 +1,1229 @@
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}
diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.h b/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.h
new file mode 100644
index 0000000..01b1e08
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.h
@@ -0,0 +1,521 @@
1/**
2 * hdr_histogram.h
3 * Written by Michael Barker and released to the public domain,
4 * as explained at http://creativecommons.org/publicdomain/zero/1.0/
5 *
6 * The source for the hdr_histogram utilises a few C99 constructs, specifically
7 * the use of stdint/stdbool and inline variable declaration.
8 */
9
10#ifndef HDR_HISTOGRAM_H
11#define HDR_HISTOGRAM_H 1
12
13#include <stdint.h>
14#include <stdbool.h>
15#include <stdio.h>
16
17struct hdr_histogram
18{
19 int64_t lowest_discernible_value;
20 int64_t highest_trackable_value;
21 int32_t unit_magnitude;
22 int32_t significant_figures;
23 int32_t sub_bucket_half_count_magnitude;
24 int32_t sub_bucket_half_count;
25 int64_t sub_bucket_mask;
26 int32_t sub_bucket_count;
27 int32_t bucket_count;
28 int64_t min_value;
29 int64_t max_value;
30 int32_t normalizing_index_offset;
31 double conversion_ratio;
32 int32_t counts_len;
33 int64_t total_count;
34 int64_t* counts;
35};
36
37#ifdef __cplusplus
38extern "C" {
39#endif
40
41/**
42 * Allocate the memory and initialise the hdr_histogram.
43 *
44 * Due to the size of the histogram being the result of some reasonably
45 * involved math on the input parameters this function it is tricky to stack allocate.
46 * The histogram should be released with hdr_close
47 *
48 * @param lowest_discernible_value The smallest possible value that is distinguishable from 0.
49 * Must be a positive integer that is >= 1. May be internally rounded down to nearest power of 2.
50 * @param highest_trackable_value The largest possible value to be put into the
51 * histogram.
52 * @param significant_figures The level of precision for this histogram, i.e. the number
53 * of figures in a decimal number that will be maintained. E.g. a value of 3 will mean
54 * the results from the histogram will be accurate up to the first three digits. Must
55 * be a value between 1 and 5 (inclusive).
56 * @param result Output parameter to capture allocated histogram.
57 * @return 0 on success, EINVAL if lowest_discernible_value is < 1 or the
58 * significant_figure value is outside of the allowed range, ENOMEM if malloc
59 * failed.
60 */
61int hdr_init(
62 int64_t lowest_discernible_value,
63 int64_t highest_trackable_value,
64 int significant_figures,
65 struct hdr_histogram** result);
66
67/**
68 * Free the memory and close the hdr_histogram.
69 *
70 * @param h The histogram you want to close.
71 */
72void hdr_close(struct hdr_histogram* h);
73
74/**
75 * Allocate the memory and initialise the hdr_histogram. This is the equivalent of calling
76 * hdr_init(1, highest_trackable_value, significant_figures, result);
77 *
78 * @deprecated use hdr_init.
79 */
80int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result);
81
82
83/**
84 * Reset a histogram to zero - empty out a histogram and re-initialise it
85 *
86 * If you want to re-use an existing histogram, but reset everything back to zero, this
87 * is the routine to use.
88 *
89 * @param h The histogram you want to reset to empty.
90 *
91 */
92void hdr_reset(struct hdr_histogram* h);
93
94/**
95 * Get the memory size of the hdr_histogram.
96 *
97 * @param h "This" pointer
98 * @return The amount of memory used by the hdr_histogram in bytes
99 */
100size_t hdr_get_memory_size(struct hdr_histogram* h);
101
102/**
103 * Records a value in the histogram, will round this value of to a precision at or better
104 * than the significant_figure specified at construction time.
105 *
106 * @param h "This" pointer
107 * @param value Value to add to the histogram
108 * @return false if the value is larger than the highest_trackable_value and can't be recorded,
109 * true otherwise.
110 */
111bool hdr_record_value(struct hdr_histogram* h, int64_t value);
112
113/**
114 * Records a value in the histogram, will round this value of to a precision at or better
115 * than the significant_figure specified at construction time.
116 *
117 * Will record this value atomically, however the whole structure may appear inconsistent
118 * when read concurrently with this update. Do NOT mix calls to this method with calls
119 * to non-atomic updates.
120 *
121 * @param h "This" pointer
122 * @param value Value to add to the histogram
123 * @return false if the value is larger than the highest_trackable_value and can't be recorded,
124 * true otherwise.
125 */
126bool hdr_record_value_atomic(struct hdr_histogram* h, int64_t value);
127
128/**
129 * Records count values in the histogram, will round this value of to a
130 * precision at or better than the significant_figure specified at construction
131 * time.
132 *
133 * @param h "This" pointer
134 * @param value Value to add to the histogram
135 * @param count Number of 'value's to add to the histogram
136 * @return false if any value is larger than the highest_trackable_value and can't be recorded,
137 * true otherwise.
138 */
139bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count);
140
141/**
142 * Records count values in the histogram, will round this value of to a
143 * precision at or better than the significant_figure specified at construction
144 * time.
145 *
146 * Will record this value atomically, however the whole structure may appear inconsistent
147 * when read concurrently with this update. Do NOT mix calls to this method with calls
148 * to non-atomic updates.
149 *
150 * @param h "This" pointer
151 * @param value Value to add to the histogram
152 * @param count Number of 'value's to add to the histogram
153 * @return false if any value is larger than the highest_trackable_value and can't be recorded,
154 * true otherwise.
155 */
156bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count);
157
158/**
159 * Record a value in the histogram and backfill based on an expected interval.
160 *
161 * Records a value in the histogram, will round this value of to a precision at or better
162 * than the significant_figure specified at construction time. This is specifically used
163 * for recording latency. If the value is larger than the expected_interval then the
164 * latency recording system has experienced co-ordinated omission. This method fills in the
165 * values that would have occurred had the client providing the load not been blocked.
166
167 * @param h "This" pointer
168 * @param value Value to add to the histogram
169 * @param expected_interval The delay between recording values.
170 * @return false if the value is larger than the highest_trackable_value and can't be recorded,
171 * true otherwise.
172 */
173bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval);
174
175/**
176 * Record a value in the histogram and backfill based on an expected interval.
177 *
178 * Records a value in the histogram, will round this value of to a precision at or better
179 * than the significant_figure specified at construction time. This is specifically used
180 * for recording latency. If the value is larger than the expected_interval then the
181 * latency recording system has experienced co-ordinated omission. This method fills in the
182 * values that would have occurred had the client providing the load not been blocked.
183 *
184 * Will record this value atomically, however the whole structure may appear inconsistent
185 * when read concurrently with this update. Do NOT mix calls to this method with calls
186 * to non-atomic updates.
187 *
188 * @param h "This" pointer
189 * @param value Value to add to the histogram
190 * @param expected_interval The delay between recording values.
191 * @return false if the value is larger than the highest_trackable_value and can't be recorded,
192 * true otherwise.
193 */
194bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expected_interval);
195
196/**
197 * Record a value in the histogram 'count' times. Applies the same correcting logic
198 * as 'hdr_record_corrected_value'.
199 *
200 * @param h "This" pointer
201 * @param value Value to add to the histogram
202 * @param count Number of 'value's to add to the histogram
203 * @param expected_interval The delay between recording values.
204 * @return false if the value is larger than the highest_trackable_value and can't be recorded,
205 * true otherwise.
206 */
207bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval);
208
209/**
210 * Record a value in the histogram 'count' times. Applies the same correcting logic
211 * as 'hdr_record_corrected_value'.
212 *
213 * Will record this value atomically, however the whole structure may appear inconsistent
214 * when read concurrently with this update. Do NOT mix calls to this method with calls
215 * to non-atomic updates.
216 *
217 * @param h "This" pointer
218 * @param value Value to add to the histogram
219 * @param count Number of 'value's to add to the histogram
220 * @param expected_interval The delay between recording values.
221 * @return false if the value is larger than the highest_trackable_value and can't be recorded,
222 * true otherwise.
223 */
224bool hdr_record_corrected_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval);
225
226/**
227 * Adds all of the values from 'from' to 'this' histogram. Will return the
228 * number of values that are dropped when copying. Values will be dropped
229 * if they around outside of h.lowest_discernible_value and
230 * h.highest_trackable_value.
231 *
232 * @param h "This" pointer
233 * @param from Histogram to copy values from.
234 * @return The number of values dropped when copying.
235 */
236int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from);
237
238/**
239 * Adds all of the values from 'from' to 'this' histogram. Will return the
240 * number of values that are dropped when copying. Values will be dropped
241 * if they around outside of h.lowest_discernible_value and
242 * h.highest_trackable_value.
243 *
244 * @param h "This" pointer
245 * @param from Histogram to copy values from.
246 * @return The number of values dropped when copying.
247 */
248int64_t hdr_add_while_correcting_for_coordinated_omission(
249 struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval);
250
251/**
252 * Get minimum value from the histogram. Will return 2^63-1 if the histogram
253 * is empty.
254 *
255 * @param h "This" pointer
256 */
257int64_t hdr_min(const struct hdr_histogram* h);
258
259/**
260 * Get maximum value from the histogram. Will return 0 if the histogram
261 * is empty.
262 *
263 * @param h "This" pointer
264 */
265int64_t hdr_max(const struct hdr_histogram* h);
266
267/**
268 * Get the value at a specific percentile.
269 *
270 * @param h "This" pointer.
271 * @param percentile The percentile to get the value for
272 */
273int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile);
274
275/**
276 * Get the values at the given percentiles.
277 *
278 * @param h "This" pointer.
279 * @param percentiles The ordered percentiles array to get the values for.
280 * @param length Number of elements in the arrays.
281 * @param values Destination array containing the values at the given percentiles.
282 * The values array should be allocated by the caller.
283 * @return 0 on success, ENOMEM if the provided destination array is null.
284 */
285int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length);
286
287/**
288 * Gets the standard deviation for the values in the histogram.
289 *
290 * @param h "This" pointer
291 * @return The standard deviation
292 */
293double hdr_stddev(const struct hdr_histogram* h);
294
295/**
296 * Gets the mean for the values in the histogram.
297 *
298 * @param h "This" pointer
299 * @return The mean
300 */
301double hdr_mean(const struct hdr_histogram* h);
302
303/**
304 * Determine if two values are equivalent with the histogram's resolution.
305 * Where "equivalent" means that value samples recorded for any two
306 * equivalent values are counted in a common total count.
307 *
308 * @param h "This" pointer
309 * @param a first value to compare
310 * @param b second value to compare
311 * @return 'true' if values are equivalent with the histogram's resolution.
312 */
313bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b);
314
315/**
316 * Get the lowest value that is equivalent to the given value within the histogram's resolution.
317 * Where "equivalent" means that value samples recorded for any two
318 * equivalent values are counted in a common total count.
319 *
320 * @param h "This" pointer
321 * @param value The given value
322 * @return The lowest value that is equivalent to the given value within the histogram's resolution.
323 */
324int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value);
325
326/**
327 * Get the count of recorded values at a specific value
328 * (to within the histogram resolution at the value level).
329 *
330 * @param h "This" pointer
331 * @param value The value for which to provide the recorded count
332 * @return The total count of values recorded in the histogram within the value range that is
333 * {@literal >=} lowestEquivalentValue(<i>value</i>) and {@literal <=} highestEquivalentValue(<i>value</i>)
334 */
335int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value);
336
337int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index);
338
339int64_t hdr_value_at_index(const struct hdr_histogram* h, int32_t index);
340
341struct hdr_iter_percentiles
342{
343 bool seen_last_value;
344 int32_t ticks_per_half_distance;
345 double percentile_to_iterate_to;
346 double percentile;
347};
348
349struct hdr_iter_recorded
350{
351 int64_t count_added_in_this_iteration_step;
352};
353
354struct hdr_iter_linear
355{
356 int64_t value_units_per_bucket;
357 int64_t count_added_in_this_iteration_step;
358 int64_t next_value_reporting_level;
359 int64_t next_value_reporting_level_lowest_equivalent;
360};
361
362struct hdr_iter_log
363{
364 double log_base;
365 int64_t count_added_in_this_iteration_step;
366 int64_t next_value_reporting_level;
367 int64_t next_value_reporting_level_lowest_equivalent;
368};
369
370/**
371 * The basic iterator. This is a generic structure
372 * that supports all of the types of iteration. Use
373 * the appropriate initialiser to get the desired
374 * iteration.
375 *
376 * @
377 */
378struct hdr_iter
379{
380 const struct hdr_histogram* h;
381 /** raw index into the counts array */
382 int32_t counts_index;
383 /** snapshot of the length at the time the iterator is created */
384 int64_t total_count;
385 /** value directly from array for the current counts_index */
386 int64_t count;
387 /** sum of all of the counts up to and including the count at this index */
388 int64_t cumulative_count;
389 /** The current value based on counts_index */
390 int64_t value;
391 int64_t highest_equivalent_value;
392 int64_t lowest_equivalent_value;
393 int64_t median_equivalent_value;
394 int64_t value_iterated_from;
395 int64_t value_iterated_to;
396
397 union
398 {
399 struct hdr_iter_percentiles percentiles;
400 struct hdr_iter_recorded recorded;
401 struct hdr_iter_linear linear;
402 struct hdr_iter_log log;
403 } specifics;
404
405 bool (* _next_fp)(struct hdr_iter* iter);
406
407};
408
409/**
410 * Initalises the basic iterator.
411 *
412 * @param itr 'This' pointer
413 * @param h The histogram to iterate over
414 */
415void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h);
416
417/**
418 * Initialise the iterator for use with percentiles.
419 */
420void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance);
421
422/**
423 * Initialise the iterator for use with recorded values.
424 */
425void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h);
426
427/**
428 * Initialise the iterator for use with linear values.
429 */
430void hdr_iter_linear_init(
431 struct hdr_iter* iter,
432 const struct hdr_histogram* h,
433 int64_t value_units_per_bucket);
434
435/**
436 * Update the iterator value units per bucket
437 */
438void hdr_iter_linear_set_value_units_per_bucket(struct hdr_iter* iter, int64_t value_units_per_bucket);
439
440/**
441 * Initialise the iterator for use with logarithmic values
442 */
443void hdr_iter_log_init(
444 struct hdr_iter* iter,
445 const struct hdr_histogram* h,
446 int64_t value_units_first_bucket,
447 double log_base);
448
449/**
450 * Iterate to the next value for the iterator. If there are no more values
451 * available return faluse.
452 *
453 * @param itr 'This' pointer
454 * @return 'false' if there are no values remaining for this iterator.
455 */
456bool hdr_iter_next(struct hdr_iter* iter);
457
458typedef enum
459{
460 CLASSIC,
461 CSV
462} format_type;
463
464/**
465 * Print out a percentile based histogram to the supplied stream. Note that
466 * this call will not flush the FILE, this is left up to the user.
467 *
468 * @param h 'This' pointer
469 * @param stream The FILE to write the output to
470 * @param ticks_per_half_distance The number of iteration steps per half-distance to 100%
471 * @param value_scale Scale the output values by this amount
472 * @param format_type Format to use, e.g. CSV.
473 * @return 0 on success, error code on failure. EIO if an error occurs writing
474 * the output.
475 */
476int hdr_percentiles_print(
477 struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance,
478 double value_scale, format_type format);
479
480/**
481* Internal allocation methods, used by hdr_dbl_histogram.
482*/
483struct hdr_histogram_bucket_config
484{
485 int64_t lowest_discernible_value;
486 int64_t highest_trackable_value;
487 int64_t unit_magnitude;
488 int64_t significant_figures;
489 int32_t sub_bucket_half_count_magnitude;
490 int32_t sub_bucket_half_count;
491 int64_t sub_bucket_mask;
492 int32_t sub_bucket_count;
493 int32_t bucket_count;
494 int32_t counts_len;
495};
496
497int hdr_calculate_bucket_config(
498 int64_t lowest_discernible_value,
499 int64_t highest_trackable_value,
500 int significant_figures,
501 struct hdr_histogram_bucket_config* cfg);
502
503void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg);
504
505int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value);
506
507int64_t hdr_next_non_equivalent_value(const struct hdr_histogram* h, int64_t value);
508
509int64_t hdr_median_equivalent_value(const struct hdr_histogram* h, int64_t value);
510
511/**
512 * Used to reset counters after importing data manually into the histogram, used by the logging code
513 * and other custom serialisation tools.
514 */
515void hdr_reset_internal_counters(struct hdr_histogram* h);
516
517#ifdef __cplusplus
518}
519#endif
520
521#endif
diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_redis_malloc.h b/examples/redis-unstable/deps/hdr_histogram/hdr_redis_malloc.h
new file mode 100644
index 0000000..d9401ca
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/hdr_redis_malloc.h
@@ -0,0 +1,13 @@
1#ifndef HDR_MALLOC_H__
2#define HDR_MALLOC_H__
3
4void *zmalloc(size_t size);
5void *zcalloc_num(size_t num, size_t size);
6void *zrealloc(void *ptr, size_t size);
7void zfree(void *ptr);
8
9#define hdr_malloc zmalloc
10#define hdr_calloc zcalloc_num
11#define hdr_realloc zrealloc
12#define hdr_free zfree
13#endif
diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_tests.h b/examples/redis-unstable/deps/hdr_histogram/hdr_tests.h
new file mode 100644
index 0000000..c016d3a
--- /dev/null
+++ b/examples/redis-unstable/deps/hdr_histogram/hdr_tests.h
@@ -0,0 +1,22 @@
1#ifndef HDR_TESTS_H
2#define HDR_TESTS_H
3
4/* These are functions used in tests and are not intended for normal usage. */
5
6#include "hdr_histogram.h"
7
8#ifdef __cplusplus
9extern "C" {
10#endif
11
12int32_t counts_index_for(const struct hdr_histogram* h, int64_t value);
13int hdr_encode_compressed(struct hdr_histogram* h, uint8_t** compressed_histogram, size_t* compressed_len);
14int hdr_decode_compressed(uint8_t* buffer, size_t length, struct hdr_histogram** histogram);
15void hdr_base64_decode_block(const char* input, uint8_t* output);
16void hdr_base64_encode_block(const uint8_t* input, char* output);
17
18#ifdef __cplusplus
19}
20#endif
21
22#endif
generated by cgit v1.2.3 (git 2.46.0) at 2026-04-30 03:57:46 +0000