diff options
| author | Mitja Felicijan <mitja.felicijan@gmail.com> | 2026-01-21 22:52:54 +0100 |
|---|---|---|
| committer | Mitja Felicijan <mitja.felicijan@gmail.com> | 2026-01-21 22:52:54 +0100 |
| commit | dcacc00e3750300617ba6e16eb346713f91a783a (patch) | |
| tree | 38e2d4fb5ed9d119711d4295c6eda4b014af73fd /examples/redis-unstable/deps/hdr_histogram | |
| parent | 58dac10aeb8f5a041c46bddbeaf4c7966a99b998 (diff) | |
| download | crep-dcacc00e3750300617ba6e16eb346713f91a783a.tar.gz | |
Remove testing data
Diffstat (limited to 'examples/redis-unstable/deps/hdr_histogram')
9 files changed, 0 insertions, 2198 deletions
diff --git a/examples/redis-unstable/deps/hdr_histogram/COPYING.txt b/examples/redis-unstable/deps/hdr_histogram/COPYING.txt deleted file mode 100644 index 0e259d4..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/COPYING.txt +++ /dev/null @@ -1,121 +0,0 @@ -Creative Commons Legal Code - -CC0 1.0 Universal - - CREATIVE COMMONS CORPORATION IS NOT A LAW FIRM AND DOES NOT PROVIDE - LEGAL SERVICES. DISTRIBUTION OF THIS DOCUMENT DOES NOT CREATE AN - ATTORNEY-CLIENT RELATIONSHIP. CREATIVE COMMONS PROVIDES THIS - INFORMATION ON AN "AS-IS" BASIS. CREATIVE COMMONS MAKES NO WARRANTIES - REGARDING THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS - PROVIDED HEREUNDER, AND DISCLAIMS LIABILITY FOR DAMAGES RESULTING FROM - THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS PROVIDED - HEREUNDER. - -Statement of Purpose - -The laws of most jurisdictions throughout the world automatically confer -exclusive Copyright and Related Rights (defined below) upon the creator -and subsequent owner(s) (each and all, an "owner") of an original work of -authorship and/or a database (each, a "Work"). - -Certain owners wish to permanently relinquish those rights to a Work for -the purpose of contributing to a commons of creative, cultural and -scientific works ("Commons") that the public can reliably and without fear -of later claims of infringement build upon, modify, incorporate in other -works, reuse and redistribute as freely as possible in any form whatsoever -and for any purposes, including without limitation commercial purposes. -These owners may contribute to the Commons to promote the ideal of a free -culture and the further production of creative, cultural and scientific -works, or to gain reputation or greater distribution for their Work in -part through the use and efforts of others. - -For these and/or other purposes and motivations, and without any -expectation of additional consideration or compensation, the person -associating CC0 with a Work (the "Affirmer"), to the extent that he or she -is an owner of Copyright and Related Rights in the Work, voluntarily -elects to apply CC0 to the Work and publicly distribute the Work under its -terms, with knowledge of his or her Copyright and Related Rights in the -Work and the meaning and intended legal effect of CC0 on those rights. - -1. Copyright and Related Rights. A Work made available under CC0 may be -protected by copyright and related or neighboring rights ("Copyright and -Related Rights"). Copyright and Related Rights include, but are not -limited to, the following: - - i. the right to reproduce, adapt, distribute, perform, display, - communicate, and translate a Work; - ii. moral rights retained by the original author(s) and/or performer(s); -iii. publicity and privacy rights pertaining to a person's image or - likeness depicted in a Work; - iv. rights protecting against unfair competition in regards to a Work, - subject to the limitations in paragraph 4(a), below; - v. rights protecting the extraction, dissemination, use and reuse of data - in a Work; - vi. database rights (such as those arising under Directive 96/9/EC of the - European Parliament and of the Council of 11 March 1996 on the legal - protection of databases, and under any national implementation - thereof, including any amended or successor version of such - directive); and -vii. other similar, equivalent or corresponding rights throughout the - world based on applicable law or treaty, and any national - implementations thereof. - -2. Waiver. To the greatest extent permitted by, but not in contravention -of, applicable law, Affirmer hereby overtly, fully, permanently, -irrevocably and unconditionally waives, abandons, and surrenders all of -Affirmer's Copyright and Related Rights and associated claims and causes -of action, whether now known or unknown (including existing as well as -future claims and causes of action), in the Work (i) in all territories -worldwide, (ii) for the maximum duration provided by applicable law or -treaty (including future time extensions), (iii) in any current or future -medium and for any number of copies, and (iv) for any purpose whatsoever, -including without limitation commercial, advertising or promotional -purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each -member of the public at large and to the detriment of Affirmer's heirs and -successors, fully intending that such Waiver shall not be subject to -revocation, rescission, cancellation, termination, or any other legal or -equitable action to disrupt the quiet enjoyment of the Work by the public -as contemplated by Affirmer's express Statement of Purpose. - -3. Public License Fallback. Should any part of the Waiver for any reason -be judged legally invalid or ineffective under applicable law, then the -Waiver shall be preserved to the maximum extent permitted taking into -account Affirmer's express Statement of Purpose. In addition, to the -extent the Waiver is so judged Affirmer hereby grants to each affected -person a royalty-free, non transferable, non sublicensable, non exclusive, -irrevocable and unconditional license to exercise Affirmer's Copyright and -Related Rights in the Work (i) in all territories worldwide, (ii) for the -maximum duration provided by applicable law or treaty (including future -time extensions), (iii) in any current or future medium and for any number -of copies, and (iv) for any purpose whatsoever, including without -limitation commercial, advertising or promotional purposes (the -"License"). The License shall be deemed effective as of the date CC0 was -applied by Affirmer to the Work. Should any part of the License for any -reason be judged legally invalid or ineffective under applicable law, such -partial invalidity or ineffectiveness shall not invalidate the remainder -of the License, and in such case Affirmer hereby affirms that he or she -will not (i) exercise any of his or her remaining Copyright and Related -Rights in the Work or (ii) assert any associated claims and causes of -action with respect to the Work, in either case contrary to Affirmer's -express Statement of Purpose. - -4. Limitations and Disclaimers. - - a. No trademark or patent rights held by Affirmer are waived, abandoned, - surrendered, licensed or otherwise affected by this document. - b. Affirmer offers the Work as-is and makes no representations or - warranties of any kind concerning the Work, express, implied, - statutory or otherwise, including without limitation warranties of - title, merchantability, fitness for a particular purpose, non - infringement, or the absence of latent or other defects, accuracy, or - the present or absence of errors, whether or not discoverable, all to - the greatest extent permissible under applicable law. - c. Affirmer disclaims responsibility for clearing rights of other persons - that may apply to the Work or any use thereof, including without - limitation any person's Copyright and Related Rights in the Work. - Further, Affirmer disclaims responsibility for obtaining any necessary - consents, permissions or other rights required for any use of the - Work. - d. Affirmer understands and acknowledges that Creative Commons is not a - party to this document and has no duty or obligation with respect to - 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 deleted file mode 100644 index 9b4e66e..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/LICENSE.txt +++ /dev/null @@ -1,41 +0,0 @@ -The code in this repository code was Written by Gil Tene, Michael Barker, -and Matt Warren, and released to the public domain, as explained at -http://creativecommons.org/publicdomain/zero/1.0/ - -For users of this code who wish to consume it under the "BSD" license -rather than under the public domain or CC0 contribution text mentioned -above, the code found under this directory is *also* provided under the -following license (commonly referred to as the BSD 2-Clause License). This -license does not detract from the above stated release of the code into -the public domain, and simply represents an additional license granted by -the Author. - ------------------------------------------------------------------------------ -** Beginning of "BSD 2-Clause License" text. ** - - Copyright (c) 2012, 2013, 2014 Gil Tene - Copyright (c) 2014 Michael Barker - Copyright (c) 2014 Matt Warren - All rights reserved. - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions are met: - - 1. Redistributions of source code must retain the above copyright notice, - this list of conditions and the following disclaimer. - - 2. Redistributions in binary form must reproduce the above copyright notice, - this list of conditions and the following disclaimer in the documentation - and/or other materials provided with the distribution. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF - THE POSSIBILITY OF SUCH DAMAGE. diff --git a/examples/redis-unstable/deps/hdr_histogram/Makefile b/examples/redis-unstable/deps/hdr_histogram/Makefile deleted file mode 100644 index 28dd93e..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/Makefile +++ /dev/null @@ -1,27 +0,0 @@ -STD= -std=c99 -WARN= -Wall -OPT= -Os - -R_CFLAGS= $(STD) $(WARN) $(OPT) $(DEBUG) $(CFLAGS) -DHDR_MALLOC_INCLUDE=\"hdr_redis_malloc.h\" -R_LDFLAGS= $(LDFLAGS) -DEBUG= -g - -R_CC=$(CC) $(R_CFLAGS) -R_LD=$(CC) $(R_LDFLAGS) - -AR= ar -ARFLAGS= rcs - -libhdrhistogram.a: hdr_histogram.o - $(AR) $(ARFLAGS) $@ $+ - -hdr_histogram.o: hdr_histogram.h hdr_histogram.c - -.c.o: - $(R_CC) -c $< - -clean: - rm -f *.o - rm -f *.a - - diff --git a/examples/redis-unstable/deps/hdr_histogram/README.md b/examples/redis-unstable/deps/hdr_histogram/README.md deleted file mode 100644 index 93a156e..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/README.md +++ /dev/null @@ -1,78 +0,0 @@ -HdrHistogram_c: 'C' port of High Dynamic Range (HDR) Histogram - -HdrHistogram ----------------------------------------------- - -[](https://gitter.im/HdrHistogram/HdrHistogram) - -This port contains a subset of the functionality supported by the Java -implementation. The current supported features are: - -* Standard histogram with 64 bit counts (32/16 bit counts not supported) -* All iterator types (all values, recorded, percentiles, linear, logarithmic) -* Histogram serialisation (encoding version 1.2, decoding 1.0-1.2) -* Reader/writer phaser and interval recorder - -Features not supported, but planned - -* Auto-resizing of histograms - -Features unlikely to be implemented - -* Double histograms -* Atomic/Concurrent histograms -* 16/32 bit histograms - -# Simple Tutorial - -## Recording values - -```C -#include <hdr_histogram.h> - -struct hdr_histogram* histogram; - -// Initialise the histogram -hdr_init( - 1, // Minimum value - INT64_C(3600000000), // Maximum value - 3, // Number of significant figures - &histogram) // Pointer to initialise - -// Record value -hdr_record_value( - histogram, // Histogram to record to - value) // Value to record - -// Record value n times -hdr_record_values( - histogram, // Histogram to record to - value, // Value to record - 10) // Record value 10 times - -// Record value with correction for co-ordinated omission. -hdr_record_corrected_value( - histogram, // Histogram to record to - value, // Value to record - 1000) // Record with expected interval of 1000. - -// Print out the values of the histogram -hdr_percentiles_print( - histogram, - stdout, // File to write to - 5, // Granularity of printed values - 1.0, // Multiplier for results - CLASSIC); // Format CLASSIC/CSV supported. -``` - -## More examples - -For more detailed examples of recording and logging results look at the -[hdr_decoder](examples/hdr_decoder.c) -and [hiccup](examples/hiccup.c) -examples. You can run hiccup and decoder -and pipe the results of one into the other. - -``` -$ ./examples/hiccup | ./examples/hdr_decoder -``` diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_atomic.h b/examples/redis-unstable/deps/hdr_histogram/hdr_atomic.h deleted file mode 100644 index ae1056a..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/hdr_atomic.h +++ /dev/null @@ -1,146 +0,0 @@ -/** - * hdr_atomic.h - * Written by Philip Orwig and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - */ - -#ifndef HDR_ATOMIC_H__ -#define HDR_ATOMIC_H__ - - -#if defined(_MSC_VER) - -#include <stdint.h> -#include <intrin.h> -#include <stdbool.h> - -static void __inline * hdr_atomic_load_pointer(void** pointer) -{ - _ReadBarrier(); - return *pointer; -} - -static void hdr_atomic_store_pointer(void** pointer, void* value) -{ - _WriteBarrier(); - *pointer = value; -} - -static int64_t __inline hdr_atomic_load_64(int64_t* field) -{ - _ReadBarrier(); - return *field; -} - -static void __inline hdr_atomic_store_64(int64_t* field, int64_t value) -{ - _WriteBarrier(); - *field = value; -} - -static int64_t __inline hdr_atomic_exchange_64(volatile int64_t* field, int64_t value) -{ -#if defined(_WIN64) - return _InterlockedExchange64(field, value); -#else - int64_t comparand; - int64_t initial_value = *field; - do - { - comparand = initial_value; - initial_value = _InterlockedCompareExchange64(field, value, comparand); - } - while (comparand != initial_value); - - return initial_value; -#endif -} - -static int64_t __inline hdr_atomic_add_fetch_64(volatile int64_t* field, int64_t value) -{ -#if defined(_WIN64) - return _InterlockedExchangeAdd64(field, value) + value; -#else - int64_t comparand; - int64_t initial_value = *field; - do - { - comparand = initial_value; - initial_value = _InterlockedCompareExchange64(field, comparand + value, comparand); - } - while (comparand != initial_value); - - return initial_value + value; -#endif -} - -static bool __inline hdr_atomic_compare_exchange_64(volatile int64_t* field, int64_t* expected, int64_t desired) -{ - return *expected == _InterlockedCompareExchange64(field, desired, *expected); -} - -#elif defined(__ATOMIC_SEQ_CST) - -#define hdr_atomic_load_pointer(x) __atomic_load_n(x, __ATOMIC_SEQ_CST) -#define hdr_atomic_store_pointer(f,v) __atomic_store_n(f,v, __ATOMIC_SEQ_CST) -#define hdr_atomic_load_64(x) __atomic_load_n(x, __ATOMIC_SEQ_CST) -#define hdr_atomic_store_64(f,v) __atomic_store_n(f,v, __ATOMIC_SEQ_CST) -#define hdr_atomic_exchange_64(f,i) __atomic_exchange_n(f,i, __ATOMIC_SEQ_CST) -#define hdr_atomic_add_fetch_64(field, value) __atomic_add_fetch(field, value, __ATOMIC_SEQ_CST) -#define hdr_atomic_compare_exchange_64(field, expected, desired) __atomic_compare_exchange_n(field, expected, desired, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) - -#elif defined(__x86_64__) - -#include <stdint.h> -#include <stdbool.h> - -static inline void* hdr_atomic_load_pointer(void** pointer) -{ - void* p = *pointer; - asm volatile ("" ::: "memory"); - return p; -} - -static inline void hdr_atomic_store_pointer(void** pointer, void* value) -{ - asm volatile ("lock; xchgq %0, %1" : "+q" (value), "+m" (*pointer)); -} - -static inline int64_t hdr_atomic_load_64(int64_t* field) -{ - int64_t i = *field; - asm volatile ("" ::: "memory"); - return i; -} - -static inline void hdr_atomic_store_64(int64_t* field, int64_t value) -{ - asm volatile ("lock; xchgq %0, %1" : "+q" (value), "+m" (*field)); -} - -static inline int64_t hdr_atomic_exchange_64(volatile int64_t* field, int64_t value) -{ - int64_t result = 0; - asm volatile ("lock; xchgq %1, %2" : "=r" (result), "+q" (value), "+m" (*field)); - return result; -} - -static inline int64_t hdr_atomic_add_fetch_64(volatile int64_t* field, int64_t value) -{ - return __sync_add_and_fetch(field, value); -} - -static inline bool hdr_atomic_compare_exchange_64(volatile int64_t* field, int64_t* expected, int64_t desired) -{ - int64_t original; - asm volatile( "lock; cmpxchgq %2, %1" : "=a"(original), "+m"(*field) : "q"(desired), "0"(*expected)); - return original == *expected; -} - -#else - -#error "Unable to determine atomic operations for your platform" - -#endif - -#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 deleted file mode 100644 index f469347..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.c +++ /dev/null @@ -1,1229 +0,0 @@ -/** - * hdr_histogram.c - * Written by Michael Barker and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - */ - -#include <stdlib.h> -#include <stdbool.h> -#include <math.h> -#include <stdio.h> -#include <string.h> -#include <stdint.h> -#include <errno.h> -#include <inttypes.h> - -#include "hdr_histogram.h" -#include "hdr_tests.h" -#include "hdr_atomic.h" - -#ifndef HDR_MALLOC_INCLUDE -#define HDR_MALLOC_INCLUDE "hdr_malloc.h" -#endif - -#include HDR_MALLOC_INCLUDE - -/* ###### ####### ## ## ## ## ######## ###### */ -/* ## ## ## ## ## ## ### ## ## ## ## */ -/* ## ## ## ## ## #### ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ###### */ -/* ## ## ## ## ## ## #### ## ## */ -/* ## ## ## ## ## ## ## ### ## ## ## */ -/* ###### ####### ####### ## ## ## ###### */ - -static int32_t normalize_index(const struct hdr_histogram* h, int32_t index) -{ - int32_t normalized_index; - int32_t adjustment = 0; - if (h->normalizing_index_offset == 0) - { - return index; - } - - normalized_index = index - h->normalizing_index_offset; - - if (normalized_index < 0) - { - adjustment = h->counts_len; - } - else if (normalized_index >= h->counts_len) - { - adjustment = -h->counts_len; - } - - return normalized_index + adjustment; -} - -static int64_t counts_get_direct(const struct hdr_histogram* h, int32_t index) -{ - return h->counts[index]; -} - -static int64_t counts_get_normalised(const struct hdr_histogram* h, int32_t index) -{ - return counts_get_direct(h, normalize_index(h, index)); -} - -static void counts_inc_normalised( - struct hdr_histogram* h, int32_t index, int64_t value) -{ - int32_t normalised_index = normalize_index(h, index); - h->counts[normalised_index] += value; - h->total_count += value; -} - -static void counts_inc_normalised_atomic( - struct hdr_histogram* h, int32_t index, int64_t value) -{ - int32_t normalised_index = normalize_index(h, index); - - hdr_atomic_add_fetch_64(&h->counts[normalised_index], value); - hdr_atomic_add_fetch_64(&h->total_count, value); -} - -static void update_min_max(struct hdr_histogram* h, int64_t value) -{ - h->min_value = (value < h->min_value && value != 0) ? value : h->min_value; - h->max_value = (value > h->max_value) ? value : h->max_value; -} - -static void update_min_max_atomic(struct hdr_histogram* h, int64_t value) -{ - int64_t current_min_value; - int64_t current_max_value; - do - { - current_min_value = hdr_atomic_load_64(&h->min_value); - - if (0 == value || current_min_value <= value) - { - break; - } - } - while (!hdr_atomic_compare_exchange_64(&h->min_value, ¤t_min_value, value)); - - do - { - current_max_value = hdr_atomic_load_64(&h->max_value); - - if (value <= current_max_value) - { - break; - } - } - while (!hdr_atomic_compare_exchange_64(&h->max_value, ¤t_max_value, value)); -} - - -/* ## ## ######## #### ## #### ######## ## ## */ -/* ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## #### */ -/* ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## */ -/* ####### ## #### ######## #### ## ## */ - -static int64_t power(int64_t base, int64_t exp) -{ - int64_t result = 1; - while(exp) - { - result *= base; exp--; - } - return result; -} - -#if defined(_MSC_VER) -# if defined(_WIN64) -# pragma intrinsic(_BitScanReverse64) -# else -# pragma intrinsic(_BitScanReverse) -# endif -#endif - -static int32_t count_leading_zeros_64(int64_t value) -{ -#if defined(_MSC_VER) - uint32_t leading_zero = 0; -#if defined(_WIN64) - _BitScanReverse64(&leading_zero, value); -#else - uint32_t high = value >> 32; - if (_BitScanReverse(&leading_zero, high)) - { - leading_zero += 32; - } - else - { - uint32_t low = value & 0x00000000FFFFFFFF; - _BitScanReverse(&leading_zero, low); - } -#endif - return 63 - leading_zero; /* smallest power of 2 containing value */ -#else - return __builtin_clzll(value); /* smallest power of 2 containing value */ -#endif -} - -static int32_t get_bucket_index(const struct hdr_histogram* h, int64_t value) -{ - int32_t pow2ceiling = 64 - count_leading_zeros_64(value | h->sub_bucket_mask); /* smallest power of 2 containing value */ - return pow2ceiling - h->unit_magnitude - (h->sub_bucket_half_count_magnitude + 1); -} - -static int32_t get_sub_bucket_index(int64_t value, int32_t bucket_index, int32_t unit_magnitude) -{ - return (int32_t)(value >> (bucket_index + unit_magnitude)); -} - -static int32_t counts_index(const struct hdr_histogram* h, int32_t bucket_index, int32_t sub_bucket_index) -{ - /* Calculate the index for the first entry in the bucket: */ - /* (The following is the equivalent of ((bucket_index + 1) * subBucketHalfCount) ): */ - int32_t bucket_base_index = (bucket_index + 1) << h->sub_bucket_half_count_magnitude; - /* Calculate the offset in the bucket: */ - int32_t offset_in_bucket = sub_bucket_index - h->sub_bucket_half_count; - /* The following is the equivalent of ((sub_bucket_index - subBucketHalfCount) + bucketBaseIndex; */ - return bucket_base_index + offset_in_bucket; -} - -static int64_t value_from_index(int32_t bucket_index, int32_t sub_bucket_index, int32_t unit_magnitude) -{ - return ((int64_t) sub_bucket_index) << (bucket_index + unit_magnitude); -} - -int32_t counts_index_for(const struct hdr_histogram* h, int64_t value) -{ - int32_t bucket_index = get_bucket_index(h, value); - int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude); - - return counts_index(h, bucket_index, sub_bucket_index); -} - -int64_t hdr_value_at_index(const struct hdr_histogram *h, int32_t index) -{ - int32_t bucket_index = (index >> h->sub_bucket_half_count_magnitude) - 1; - int32_t sub_bucket_index = (index & (h->sub_bucket_half_count - 1)) + h->sub_bucket_half_count; - - if (bucket_index < 0) - { - sub_bucket_index -= h->sub_bucket_half_count; - bucket_index = 0; - } - - return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude); -} - -int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value) -{ - int32_t bucket_index = get_bucket_index(h, value); - int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude); - int32_t adjusted_bucket = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index; - return INT64_C(1) << (h->unit_magnitude + adjusted_bucket); -} - -static int64_t size_of_equivalent_value_range_given_bucket_indices( - const struct hdr_histogram *h, - int32_t bucket_index, - int32_t sub_bucket_index) -{ - const int32_t adjusted_bucket = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index; - return INT64_C(1) << (h->unit_magnitude + adjusted_bucket); -} - -static int64_t lowest_equivalent_value(const struct hdr_histogram* h, int64_t value) -{ - int32_t bucket_index = get_bucket_index(h, value); - int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude); - return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude); -} - -static int64_t lowest_equivalent_value_given_bucket_indices( - const struct hdr_histogram *h, - int32_t bucket_index, - int32_t sub_bucket_index) -{ - return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude); -} - -int64_t hdr_next_non_equivalent_value(const struct hdr_histogram *h, int64_t value) -{ - return lowest_equivalent_value(h, value) + hdr_size_of_equivalent_value_range(h, value); -} - -static int64_t highest_equivalent_value(const struct hdr_histogram* h, int64_t value) -{ - return hdr_next_non_equivalent_value(h, value) - 1; -} - -int64_t hdr_median_equivalent_value(const struct hdr_histogram *h, int64_t value) -{ - return lowest_equivalent_value(h, value) + (hdr_size_of_equivalent_value_range(h, value) >> 1); -} - -static int64_t non_zero_min(const struct hdr_histogram* h) -{ - if (INT64_MAX == h->min_value) - { - return INT64_MAX; - } - - return lowest_equivalent_value(h, h->min_value); -} - -void hdr_reset_internal_counters(struct hdr_histogram* h) -{ - int min_non_zero_index = -1; - int max_index = -1; - int64_t observed_total_count = 0; - int i; - - for (i = 0; i < h->counts_len; i++) - { - int64_t count_at_index; - - if ((count_at_index = counts_get_direct(h, i)) > 0) - { - observed_total_count += count_at_index; - max_index = i; - if (min_non_zero_index == -1 && i != 0) - { - min_non_zero_index = i; - } - } - } - - if (max_index == -1) - { - h->max_value = 0; - } - else - { - int64_t max_value = hdr_value_at_index(h, max_index); - h->max_value = highest_equivalent_value(h, max_value); - } - - if (min_non_zero_index == -1) - { - h->min_value = INT64_MAX; - } - else - { - h->min_value = hdr_value_at_index(h, min_non_zero_index); - } - - h->total_count = observed_total_count; -} - -static int32_t buckets_needed_to_cover_value(int64_t value, int32_t sub_bucket_count, int32_t unit_magnitude) -{ - int64_t smallest_untrackable_value = ((int64_t) sub_bucket_count) << unit_magnitude; - int32_t buckets_needed = 1; - while (smallest_untrackable_value <= value) - { - if (smallest_untrackable_value > INT64_MAX / 2) - { - return buckets_needed + 1; - } - smallest_untrackable_value <<= 1; - buckets_needed++; - } - - return buckets_needed; -} - -/* ## ## ######## ## ## ####### ######## ## ## */ -/* ### ### ## ### ### ## ## ## ## ## ## */ -/* #### #### ## #### #### ## ## ## ## #### */ -/* ## ### ## ###### ## ### ## ## ## ######## ## */ -/* ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ######## ## ## ####### ## ## ## */ - -int hdr_calculate_bucket_config( - int64_t lowest_discernible_value, - int64_t highest_trackable_value, - int significant_figures, - struct hdr_histogram_bucket_config* cfg) -{ - int32_t sub_bucket_count_magnitude; - int64_t largest_value_with_single_unit_resolution; - - if (lowest_discernible_value < 1 || - significant_figures < 1 || 5 < significant_figures || - lowest_discernible_value * 2 > highest_trackable_value) - { - return EINVAL; - } - - cfg->lowest_discernible_value = lowest_discernible_value; - cfg->significant_figures = significant_figures; - cfg->highest_trackable_value = highest_trackable_value; - - largest_value_with_single_unit_resolution = 2 * power(10, significant_figures); - sub_bucket_count_magnitude = (int32_t) ceil(log((double)largest_value_with_single_unit_resolution) / log(2)); - cfg->sub_bucket_half_count_magnitude = ((sub_bucket_count_magnitude > 1) ? sub_bucket_count_magnitude : 1) - 1; - - double unit_magnitude = log((double)lowest_discernible_value) / log(2); - if (INT32_MAX < unit_magnitude) - { - return EINVAL; - } - - cfg->unit_magnitude = (int32_t) unit_magnitude; - cfg->sub_bucket_count = (int32_t) pow(2, (cfg->sub_bucket_half_count_magnitude + 1)); - cfg->sub_bucket_half_count = cfg->sub_bucket_count / 2; - cfg->sub_bucket_mask = ((int64_t) cfg->sub_bucket_count - 1) << cfg->unit_magnitude; - - if (cfg->unit_magnitude + cfg->sub_bucket_half_count_magnitude > 61) - { - return EINVAL; - } - - cfg->bucket_count = buckets_needed_to_cover_value(highest_trackable_value, cfg->sub_bucket_count, (int32_t)cfg->unit_magnitude); - cfg->counts_len = (cfg->bucket_count + 1) * (cfg->sub_bucket_count / 2); - - return 0; -} - -void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg) -{ - h->lowest_discernible_value = cfg->lowest_discernible_value; - h->highest_trackable_value = cfg->highest_trackable_value; - h->unit_magnitude = (int32_t)cfg->unit_magnitude; - h->significant_figures = (int32_t)cfg->significant_figures; - h->sub_bucket_half_count_magnitude = cfg->sub_bucket_half_count_magnitude; - h->sub_bucket_half_count = cfg->sub_bucket_half_count; - h->sub_bucket_mask = cfg->sub_bucket_mask; - h->sub_bucket_count = cfg->sub_bucket_count; - h->min_value = INT64_MAX; - h->max_value = 0; - h->normalizing_index_offset = 0; - h->conversion_ratio = 1.0; - h->bucket_count = cfg->bucket_count; - h->counts_len = cfg->counts_len; - h->total_count = 0; -} - -int hdr_init( - int64_t lowest_discernible_value, - int64_t highest_trackable_value, - int significant_figures, - struct hdr_histogram** result) -{ - int64_t* counts; - struct hdr_histogram_bucket_config cfg; - struct hdr_histogram* histogram; - - int r = hdr_calculate_bucket_config(lowest_discernible_value, highest_trackable_value, significant_figures, &cfg); - if (r) - { - return r; - } - - counts = (int64_t*) hdr_calloc((size_t) cfg.counts_len, sizeof(int64_t)); - if (!counts) - { - return ENOMEM; - } - - histogram = (struct hdr_histogram*) hdr_calloc(1, sizeof(struct hdr_histogram)); - if (!histogram) - { - hdr_free(counts); - return ENOMEM; - } - - histogram->counts = counts; - - hdr_init_preallocated(histogram, &cfg); - *result = histogram; - - return 0; -} - -void hdr_close(struct hdr_histogram* h) -{ - if (h) { - hdr_free(h->counts); - hdr_free(h); - } -} - -int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result) -{ - return hdr_init(1, highest_trackable_value, significant_figures, result); -} - -/* reset a histogram to zero. */ -void hdr_reset(struct hdr_histogram *h) -{ - h->total_count=0; - h->min_value = INT64_MAX; - h->max_value = 0; - memset(h->counts, 0, (sizeof(int64_t) * h->counts_len)); -} - -size_t hdr_get_memory_size(struct hdr_histogram *h) -{ - return sizeof(struct hdr_histogram) + h->counts_len * sizeof(int64_t); -} - -/* ## ## ######## ######## ### ######## ######## ###### */ -/* ## ## ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ######## ## ## ## ## ## ###### ###### */ -/* ## ## ## ## ## ######### ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## */ -/* ####### ## ######## ## ## ## ######## ###### */ - - -bool hdr_record_value(struct hdr_histogram* h, int64_t value) -{ - return hdr_record_values(h, value, 1); -} - -bool hdr_record_value_atomic(struct hdr_histogram* h, int64_t value) -{ - return hdr_record_values_atomic(h, value, 1); -} - -bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count) -{ - int32_t counts_index; - - if (value < 0) - { - return false; - } - - counts_index = counts_index_for(h, value); - - if (counts_index < 0 || h->counts_len <= counts_index) - { - return false; - } - - counts_inc_normalised(h, counts_index, count); - update_min_max(h, value); - - return true; -} - -bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count) -{ - int32_t counts_index; - - if (value < 0) - { - return false; - } - - counts_index = counts_index_for(h, value); - - if (counts_index < 0 || h->counts_len <= counts_index) - { - return false; - } - - counts_inc_normalised_atomic(h, counts_index, count); - update_min_max_atomic(h, value); - - return true; -} - -bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval) -{ - return hdr_record_corrected_values(h, value, 1, expected_interval); -} - -bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expected_interval) -{ - return hdr_record_corrected_values_atomic(h, value, 1, expected_interval); -} - -bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval) -{ - int64_t missing_value; - - if (!hdr_record_values(h, value, count)) - { - return false; - } - - if (expected_interval <= 0 || value <= expected_interval) - { - return true; - } - - missing_value = value - expected_interval; - for (; missing_value >= expected_interval; missing_value -= expected_interval) - { - if (!hdr_record_values(h, missing_value, count)) - { - return false; - } - } - - return true; -} - -bool hdr_record_corrected_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval) -{ - int64_t missing_value; - - if (!hdr_record_values_atomic(h, value, count)) - { - return false; - } - - if (expected_interval <= 0 || value <= expected_interval) - { - return true; - } - - missing_value = value - expected_interval; - for (; missing_value >= expected_interval; missing_value -= expected_interval) - { - if (!hdr_record_values_atomic(h, missing_value, count)) - { - return false; - } - } - - return true; -} - -int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from) -{ - struct hdr_iter iter; - int64_t dropped = 0; - hdr_iter_recorded_init(&iter, from); - - while (hdr_iter_next(&iter)) - { - int64_t value = iter.value; - int64_t count = iter.count; - - if (!hdr_record_values(h, value, count)) - { - dropped += count; - } - } - - return dropped; -} - -int64_t hdr_add_while_correcting_for_coordinated_omission( - struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval) -{ - struct hdr_iter iter; - int64_t dropped = 0; - hdr_iter_recorded_init(&iter, from); - - while (hdr_iter_next(&iter)) - { - int64_t value = iter.value; - int64_t count = iter.count; - - if (!hdr_record_corrected_values(h, value, count, expected_interval)) - { - dropped += count; - } - } - - return dropped; -} - - - -/* ## ## ### ## ## ## ######## ###### */ -/* ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ###### ###### */ -/* ## ## ######### ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## */ -/* ### ## ## ######## ####### ######## ###### */ - - -int64_t hdr_max(const struct hdr_histogram* h) -{ - if (0 == h->max_value) - { - return 0; - } - - return highest_equivalent_value(h, h->max_value); -} - -int64_t hdr_min(const struct hdr_histogram* h) -{ - if (0 < hdr_count_at_index(h, 0)) - { - return 0; - } - - return non_zero_min(h); -} - -static int64_t get_value_from_idx_up_to_count(const struct hdr_histogram* h, int64_t count_at_percentile) -{ - int64_t count_to_idx = 0; - - count_at_percentile = 0 < count_at_percentile ? count_at_percentile : 1; - for (int32_t idx = 0; idx < h->counts_len; idx++) - { - count_to_idx += h->counts[idx]; - if (count_to_idx >= count_at_percentile) - { - return hdr_value_at_index(h, idx); - } - } - - return 0; -} - - -int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile) -{ - double requested_percentile = percentile < 100.0 ? percentile : 100.0; - int64_t count_at_percentile = - (int64_t) (((requested_percentile / 100) * h->total_count) + 0.5); - int64_t value_from_idx = get_value_from_idx_up_to_count(h, count_at_percentile); - if (percentile == 0.0) - { - return lowest_equivalent_value(h, value_from_idx); - } - return highest_equivalent_value(h, value_from_idx); -} - -int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length) -{ - if (NULL == percentiles || NULL == values) - { - return EINVAL; - } - - struct hdr_iter iter; - const int64_t total_count = h->total_count; - // to avoid allocations we use the values array for intermediate computation - // i.e. to store the expected cumulative count at each percentile - for (size_t i = 0; i < length; i++) - { - const double requested_percentile = percentiles[i] < 100.0 ? percentiles[i] : 100.0; - const int64_t count_at_percentile = - (int64_t) (((requested_percentile / 100) * total_count) + 0.5); - values[i] = count_at_percentile > 1 ? count_at_percentile : 1; - } - - hdr_iter_init(&iter, h); - int64_t total = 0; - size_t at_pos = 0; - while (hdr_iter_next(&iter) && at_pos < length) - { - total += iter.count; - while (at_pos < length && total >= values[at_pos]) - { - values[at_pos] = highest_equivalent_value(h, iter.value); - at_pos++; - } - } - return 0; -} - -double hdr_mean(const struct hdr_histogram* h) -{ - struct hdr_iter iter; - int64_t total = 0; - - hdr_iter_init(&iter, h); - - while (hdr_iter_next(&iter)) - { - if (0 != iter.count) - { - total += iter.count * hdr_median_equivalent_value(h, iter.value); - } - } - - return (total * 1.0) / h->total_count; -} - -double hdr_stddev(const struct hdr_histogram* h) -{ - double mean = hdr_mean(h); - double geometric_dev_total = 0.0; - - struct hdr_iter iter; - hdr_iter_init(&iter, h); - - while (hdr_iter_next(&iter)) - { - if (0 != iter.count) - { - double dev = (hdr_median_equivalent_value(h, iter.value) * 1.0) - mean; - geometric_dev_total += (dev * dev) * iter.count; - } - } - - return sqrt(geometric_dev_total / h->total_count); -} - -bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b) -{ - return lowest_equivalent_value(h, a) == lowest_equivalent_value(h, b); -} - -int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value) -{ - return lowest_equivalent_value(h, value); -} - -int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value) -{ - return counts_get_normalised(h, counts_index_for(h, value)); -} - -int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index) -{ - return counts_get_normalised(h, index); -} - - -/* #### ######## ######## ######## ### ######## ####### ######## ###### */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ###### ######## ## ## ## ## ## ######## ###### */ -/* ## ## ## ## ## ######### ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ -/* #### ## ######## ## ## ## ## ## ####### ## ## ###### */ - - -static bool has_buckets(struct hdr_iter* iter) -{ - return iter->counts_index < iter->h->counts_len; -} - -static bool has_next(struct hdr_iter* iter) -{ - return iter->cumulative_count < iter->total_count; -} - -static bool move_next(struct hdr_iter* iter) -{ - iter->counts_index++; - - if (!has_buckets(iter)) - { - return false; - } - - iter->count = counts_get_normalised(iter->h, iter->counts_index); - iter->cumulative_count += iter->count; - const int64_t value = hdr_value_at_index(iter->h, iter->counts_index); - const int32_t bucket_index = get_bucket_index(iter->h, value); - const int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, iter->h->unit_magnitude); - const int64_t leq = lowest_equivalent_value_given_bucket_indices(iter->h, bucket_index, sub_bucket_index); - const int64_t size_of_equivalent_value_range = size_of_equivalent_value_range_given_bucket_indices( - iter->h, bucket_index, sub_bucket_index); - iter->lowest_equivalent_value = leq; - iter->value = value; - iter->highest_equivalent_value = leq + size_of_equivalent_value_range - 1; - iter->median_equivalent_value = leq + (size_of_equivalent_value_range >> 1); - - return true; -} - -static int64_t peek_next_value_from_index(struct hdr_iter* iter) -{ - return hdr_value_at_index(iter->h, iter->counts_index + 1); -} - -static bool next_value_greater_than_reporting_level_upper_bound( - struct hdr_iter *iter, int64_t reporting_level_upper_bound) -{ - if (iter->counts_index >= iter->h->counts_len) - { - return false; - } - - return peek_next_value_from_index(iter) > reporting_level_upper_bound; -} - -static bool basic_iter_next(struct hdr_iter *iter) -{ - if (!has_next(iter) || iter->counts_index >= iter->h->counts_len) - { - return false; - } - - move_next(iter); - - return true; -} - -static void update_iterated_values(struct hdr_iter* iter, int64_t new_value_iterated_to) -{ - iter->value_iterated_from = iter->value_iterated_to; - iter->value_iterated_to = new_value_iterated_to; -} - -static bool all_values_iter_next(struct hdr_iter* iter) -{ - bool result = move_next(iter); - - if (result) - { - update_iterated_values(iter, iter->value); - } - - return result; -} - -void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h) -{ - iter->h = h; - - iter->counts_index = -1; - iter->total_count = h->total_count; - iter->count = 0; - iter->cumulative_count = 0; - iter->value = 0; - iter->highest_equivalent_value = 0; - iter->value_iterated_from = 0; - iter->value_iterated_to = 0; - - iter->_next_fp = all_values_iter_next; -} - -bool hdr_iter_next(struct hdr_iter* iter) -{ - return iter->_next_fp(iter); -} - -/* ######## ######## ######## ###### ######## ## ## ######## #### ## ######## ###### */ -/* ## ## ## ## ## ## ## ## ### ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## #### ## ## ## ## ## ## */ -/* ######## ###### ######## ## ###### ## ## ## ## ## ## ###### ###### */ -/* ## ## ## ## ## ## ## #### ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ### ## ## ## ## ## ## */ -/* ## ######## ## ## ###### ######## ## ## ## #### ######## ######## ###### */ - -static bool percentile_iter_next(struct hdr_iter* iter) -{ - int64_t temp, half_distance, percentile_reporting_ticks; - - struct hdr_iter_percentiles* percentiles = &iter->specifics.percentiles; - - if (!has_next(iter)) - { - if (percentiles->seen_last_value) - { - return false; - } - - percentiles->seen_last_value = true; - percentiles->percentile = 100.0; - - return true; - } - - if (iter->counts_index == -1 && !basic_iter_next(iter)) - { - return false; - } - - do - { - double current_percentile = (100.0 * (double) iter->cumulative_count) / iter->h->total_count; - if (iter->count != 0 && - percentiles->percentile_to_iterate_to <= current_percentile) - { - update_iterated_values(iter, highest_equivalent_value(iter->h, iter->value)); - - percentiles->percentile = percentiles->percentile_to_iterate_to; - temp = (int64_t)(log(100 / (100.0 - (percentiles->percentile_to_iterate_to))) / log(2)) + 1; - half_distance = (int64_t) pow(2, (double) temp); - percentile_reporting_ticks = percentiles->ticks_per_half_distance * half_distance; - percentiles->percentile_to_iterate_to += 100.0 / percentile_reporting_ticks; - - return true; - } - } - while (basic_iter_next(iter)); - - return true; -} - -void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance) -{ - iter->h = h; - - hdr_iter_init(iter, h); - - iter->specifics.percentiles.seen_last_value = false; - iter->specifics.percentiles.ticks_per_half_distance = ticks_per_half_distance; - iter->specifics.percentiles.percentile_to_iterate_to = 0.0; - iter->specifics.percentiles.percentile = 0.0; - - iter->_next_fp = percentile_iter_next; -} - -static void format_line_string(char* str, size_t len, int significant_figures, format_type format) -{ -#if defined(_MSC_VER) -#define snprintf _snprintf -#pragma warning(push) -#pragma warning(disable: 4996) -#endif - const char* format_str = "%s%d%s"; - - switch (format) - { - case CSV: - snprintf(str, len, format_str, "%.", significant_figures, "f,%f,%d,%.2f\n"); - break; - case CLASSIC: - snprintf(str, len, format_str, "%12.", significant_figures, "f %12f %12d %12.2f\n"); - break; - default: - snprintf(str, len, format_str, "%12.", significant_figures, "f %12f %12d %12.2f\n"); - } -#if defined(_MSC_VER) -#undef snprintf -#pragma warning(pop) -#endif -} - - -/* ######## ######## ###### ####### ######## ######## ######## ######## */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## */ -/* ######## ###### ## ## ## ######## ## ## ###### ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ######## ###### ####### ## ## ######## ######## ######## */ - - -static bool recorded_iter_next(struct hdr_iter* iter) -{ - while (basic_iter_next(iter)) - { - if (iter->count != 0) - { - update_iterated_values(iter, iter->value); - - iter->specifics.recorded.count_added_in_this_iteration_step = iter->count; - return true; - } - } - - return false; -} - -void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h) -{ - hdr_iter_init(iter, h); - - iter->specifics.recorded.count_added_in_this_iteration_step = 0; - - iter->_next_fp = recorded_iter_next; -} - -/* ## #### ## ## ######## ### ######## */ -/* ## ## ### ## ## ## ## ## ## */ -/* ## ## #### ## ## ## ## ## ## */ -/* ## ## ## ## ## ###### ## ## ######## */ -/* ## ## ## #### ## ######### ## ## */ -/* ## ## ## ### ## ## ## ## ## */ -/* ######## #### ## ## ######## ## ## ## ## */ - - -static bool iter_linear_next(struct hdr_iter* iter) -{ - struct hdr_iter_linear* linear = &iter->specifics.linear; - - linear->count_added_in_this_iteration_step = 0; - - if (has_next(iter) || - next_value_greater_than_reporting_level_upper_bound( - iter, linear->next_value_reporting_level_lowest_equivalent)) - { - do - { - if (iter->value >= linear->next_value_reporting_level_lowest_equivalent) - { - update_iterated_values(iter, linear->next_value_reporting_level); - - linear->next_value_reporting_level += linear->value_units_per_bucket; - linear->next_value_reporting_level_lowest_equivalent = - lowest_equivalent_value(iter->h, linear->next_value_reporting_level); - - return true; - } - - if (!move_next(iter)) - { - return true; - } - - linear->count_added_in_this_iteration_step += iter->count; - } - while (true); - } - - return false; -} - - -void hdr_iter_linear_init(struct hdr_iter* iter, const struct hdr_histogram* h, int64_t value_units_per_bucket) -{ - hdr_iter_init(iter, h); - - iter->specifics.linear.count_added_in_this_iteration_step = 0; - iter->specifics.linear.value_units_per_bucket = value_units_per_bucket; - iter->specifics.linear.next_value_reporting_level = value_units_per_bucket; - iter->specifics.linear.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_per_bucket); - - iter->_next_fp = iter_linear_next; -} - -void hdr_iter_linear_set_value_units_per_bucket(struct hdr_iter* iter, int64_t value_units_per_bucket) -{ - iter->specifics.linear.value_units_per_bucket = value_units_per_bucket; -} - -/* ## ####### ###### ### ######## #### ######## ## ## ## ## #### ###### */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## ### ### ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## ## #### #### ## ## */ -/* ## ## ## ## #### ## ## ######## ## ## ######### ## ### ## ## ## */ -/* ## ## ## ## ## ######### ## ## ## ## ## ## ## ## ## ## */ -/* ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ -/* ######## ####### ###### ## ## ## ## #### ## ## ## ## ## #### ###### */ - -static bool log_iter_next(struct hdr_iter *iter) -{ - struct hdr_iter_log* logarithmic = &iter->specifics.log; - - logarithmic->count_added_in_this_iteration_step = 0; - - if (has_next(iter) || - next_value_greater_than_reporting_level_upper_bound( - iter, logarithmic->next_value_reporting_level_lowest_equivalent)) - { - do - { - if (iter->value >= logarithmic->next_value_reporting_level_lowest_equivalent) - { - update_iterated_values(iter, logarithmic->next_value_reporting_level); - - logarithmic->next_value_reporting_level *= (int64_t)logarithmic->log_base; - logarithmic->next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(iter->h, logarithmic->next_value_reporting_level); - - return true; - } - - if (!move_next(iter)) - { - return true; - } - - logarithmic->count_added_in_this_iteration_step += iter->count; - } - while (true); - } - - return false; -} - -void hdr_iter_log_init( - struct hdr_iter* iter, - const struct hdr_histogram* h, - int64_t value_units_first_bucket, - double log_base) -{ - hdr_iter_init(iter, h); - iter->specifics.log.count_added_in_this_iteration_step = 0; - iter->specifics.log.log_base = log_base; - iter->specifics.log.next_value_reporting_level = value_units_first_bucket; - iter->specifics.log.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_first_bucket); - - iter->_next_fp = log_iter_next; -} - -/* Printing. */ - -static const char* format_head_string(format_type format) -{ - switch (format) - { - case CSV: - return "%s,%s,%s,%s\n"; - case CLASSIC: - default: - return "%12s %12s %12s %12s\n\n"; - } -} - -static const char CLASSIC_FOOTER[] = - "#[Mean = %12.3f, StdDeviation = %12.3f]\n" - "#[Max = %12.3f, Total count = %12" PRIu64 "]\n" - "#[Buckets = %12d, SubBuckets = %12d]\n"; - -int hdr_percentiles_print( - struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance, - double value_scale, format_type format) -{ - char line_format[25]; - const char* head_format; - int rc = 0; - struct hdr_iter iter; - struct hdr_iter_percentiles * percentiles; - - format_line_string(line_format, 25, h->significant_figures, format); - head_format = format_head_string(format); - - hdr_iter_percentile_init(&iter, h, ticks_per_half_distance); - - if (fprintf( - stream, head_format, - "Value", "Percentile", "TotalCount", "1/(1-Percentile)") < 0) - { - rc = EIO; - goto cleanup; - } - - percentiles = &iter.specifics.percentiles; - while (hdr_iter_next(&iter)) - { - double value = iter.highest_equivalent_value / value_scale; - double percentile = percentiles->percentile / 100.0; - int64_t total_count = iter.cumulative_count; - double inverted_percentile = (1.0 / (1.0 - percentile)); - - if (fprintf( - stream, line_format, value, percentile, total_count, inverted_percentile) < 0) - { - rc = EIO; - goto cleanup; - } - } - - if (CLASSIC == format) - { - double mean = hdr_mean(h) / value_scale; - double stddev = hdr_stddev(h) / value_scale; - double max = hdr_max(h) / value_scale; - - if (fprintf( - stream, CLASSIC_FOOTER, mean, stddev, max, - h->total_count, h->bucket_count, h->sub_bucket_count) < 0) - { - rc = EIO; - goto cleanup; - } - } - - cleanup: - return rc; -} diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.h b/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.h deleted file mode 100644 index 01b1e08..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/hdr_histogram.h +++ /dev/null @@ -1,521 +0,0 @@ -/** - * hdr_histogram.h - * Written by Michael Barker and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - * - * The source for the hdr_histogram utilises a few C99 constructs, specifically - * the use of stdint/stdbool and inline variable declaration. - */ - -#ifndef HDR_HISTOGRAM_H -#define HDR_HISTOGRAM_H 1 - -#include <stdint.h> -#include <stdbool.h> -#include <stdio.h> - -struct hdr_histogram -{ - int64_t lowest_discernible_value; - int64_t highest_trackable_value; - int32_t unit_magnitude; - int32_t significant_figures; - int32_t sub_bucket_half_count_magnitude; - int32_t sub_bucket_half_count; - int64_t sub_bucket_mask; - int32_t sub_bucket_count; - int32_t bucket_count; - int64_t min_value; - int64_t max_value; - int32_t normalizing_index_offset; - double conversion_ratio; - int32_t counts_len; - int64_t total_count; - int64_t* counts; -}; - -#ifdef __cplusplus -extern "C" { -#endif - -/** - * Allocate the memory and initialise the hdr_histogram. - * - * Due to the size of the histogram being the result of some reasonably - * involved math on the input parameters this function it is tricky to stack allocate. - * The histogram should be released with hdr_close - * - * @param lowest_discernible_value The smallest possible value that is distinguishable from 0. - * Must be a positive integer that is >= 1. May be internally rounded down to nearest power of 2. - * @param highest_trackable_value The largest possible value to be put into the - * histogram. - * @param significant_figures The level of precision for this histogram, i.e. the number - * of figures in a decimal number that will be maintained. E.g. a value of 3 will mean - * the results from the histogram will be accurate up to the first three digits. Must - * be a value between 1 and 5 (inclusive). - * @param result Output parameter to capture allocated histogram. - * @return 0 on success, EINVAL if lowest_discernible_value is < 1 or the - * significant_figure value is outside of the allowed range, ENOMEM if malloc - * failed. - */ -int hdr_init( - int64_t lowest_discernible_value, - int64_t highest_trackable_value, - int significant_figures, - struct hdr_histogram** result); - -/** - * Free the memory and close the hdr_histogram. - * - * @param h The histogram you want to close. - */ -void hdr_close(struct hdr_histogram* h); - -/** - * Allocate the memory and initialise the hdr_histogram. This is the equivalent of calling - * hdr_init(1, highest_trackable_value, significant_figures, result); - * - * @deprecated use hdr_init. - */ -int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result); - - -/** - * Reset a histogram to zero - empty out a histogram and re-initialise it - * - * If you want to re-use an existing histogram, but reset everything back to zero, this - * is the routine to use. - * - * @param h The histogram you want to reset to empty. - * - */ -void hdr_reset(struct hdr_histogram* h); - -/** - * Get the memory size of the hdr_histogram. - * - * @param h "This" pointer - * @return The amount of memory used by the hdr_histogram in bytes - */ -size_t hdr_get_memory_size(struct hdr_histogram* h); - -/** - * Records a value in the histogram, will round this value of to a precision at or better - * than the significant_figure specified at construction time. - * - * @param h "This" pointer - * @param value Value to add to the histogram - * @return false if the value is larger than the highest_trackable_value and can't be recorded, - * true otherwise. - */ -bool hdr_record_value(struct hdr_histogram* h, int64_t value); - -/** - * Records a value in the histogram, will round this value of to a precision at or better - * than the significant_figure specified at construction time. - * - * Will record this value atomically, however the whole structure may appear inconsistent - * when read concurrently with this update. Do NOT mix calls to this method with calls - * to non-atomic updates. - * - * @param h "This" pointer - * @param value Value to add to the histogram - * @return false if the value is larger than the highest_trackable_value and can't be recorded, - * true otherwise. - */ -bool hdr_record_value_atomic(struct hdr_histogram* h, int64_t value); - -/** - * Records count values in the histogram, will round this value of to a - * precision at or better than the significant_figure specified at construction - * time. - * - * @param h "This" pointer - * @param value Value to add to the histogram - * @param count Number of 'value's to add to the histogram - * @return false if any value is larger than the highest_trackable_value and can't be recorded, - * true otherwise. - */ -bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count); - -/** - * Records count values in the histogram, will round this value of to a - * precision at or better than the significant_figure specified at construction - * time. - * - * Will record this value atomically, however the whole structure may appear inconsistent - * when read concurrently with this update. Do NOT mix calls to this method with calls - * to non-atomic updates. - * - * @param h "This" pointer - * @param value Value to add to the histogram - * @param count Number of 'value's to add to the histogram - * @return false if any value is larger than the highest_trackable_value and can't be recorded, - * true otherwise. - */ -bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count); - -/** - * Record a value in the histogram and backfill based on an expected interval. - * - * Records a value in the histogram, will round this value of to a precision at or better - * than the significant_figure specified at construction time. This is specifically used - * for recording latency. If the value is larger than the expected_interval then the - * latency recording system has experienced co-ordinated omission. This method fills in the - * values that would have occurred had the client providing the load not been blocked. - - * @param h "This" pointer - * @param value Value to add to the histogram - * @param expected_interval The delay between recording values. - * @return false if the value is larger than the highest_trackable_value and can't be recorded, - * true otherwise. - */ -bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval); - -/** - * Record a value in the histogram and backfill based on an expected interval. - * - * Records a value in the histogram, will round this value of to a precision at or better - * than the significant_figure specified at construction time. This is specifically used - * for recording latency. If the value is larger than the expected_interval then the - * latency recording system has experienced co-ordinated omission. This method fills in the - * values that would have occurred had the client providing the load not been blocked. - * - * Will record this value atomically, however the whole structure may appear inconsistent - * when read concurrently with this update. Do NOT mix calls to this method with calls - * to non-atomic updates. - * - * @param h "This" pointer - * @param value Value to add to the histogram - * @param expected_interval The delay between recording values. - * @return false if the value is larger than the highest_trackable_value and can't be recorded, - * true otherwise. - */ -bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expected_interval); - -/** - * Record a value in the histogram 'count' times. Applies the same correcting logic - * as 'hdr_record_corrected_value'. - * - * @param h "This" pointer - * @param value Value to add to the histogram - * @param count Number of 'value's to add to the histogram - * @param expected_interval The delay between recording values. - * @return false if the value is larger than the highest_trackable_value and can't be recorded, - * true otherwise. - */ -bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval); - -/** - * Record a value in the histogram 'count' times. Applies the same correcting logic - * as 'hdr_record_corrected_value'. - * - * Will record this value atomically, however the whole structure may appear inconsistent - * when read concurrently with this update. Do NOT mix calls to this method with calls - * to non-atomic updates. - * - * @param h "This" pointer - * @param value Value to add to the histogram - * @param count Number of 'value's to add to the histogram - * @param expected_interval The delay between recording values. - * @return false if the value is larger than the highest_trackable_value and can't be recorded, - * true otherwise. - */ -bool hdr_record_corrected_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval); - -/** - * Adds all of the values from 'from' to 'this' histogram. Will return the - * number of values that are dropped when copying. Values will be dropped - * if they around outside of h.lowest_discernible_value and - * h.highest_trackable_value. - * - * @param h "This" pointer - * @param from Histogram to copy values from. - * @return The number of values dropped when copying. - */ -int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from); - -/** - * Adds all of the values from 'from' to 'this' histogram. Will return the - * number of values that are dropped when copying. Values will be dropped - * if they around outside of h.lowest_discernible_value and - * h.highest_trackable_value. - * - * @param h "This" pointer - * @param from Histogram to copy values from. - * @return The number of values dropped when copying. - */ -int64_t hdr_add_while_correcting_for_coordinated_omission( - struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval); - -/** - * Get minimum value from the histogram. Will return 2^63-1 if the histogram - * is empty. - * - * @param h "This" pointer - */ -int64_t hdr_min(const struct hdr_histogram* h); - -/** - * Get maximum value from the histogram. Will return 0 if the histogram - * is empty. - * - * @param h "This" pointer - */ -int64_t hdr_max(const struct hdr_histogram* h); - -/** - * Get the value at a specific percentile. - * - * @param h "This" pointer. - * @param percentile The percentile to get the value for - */ -int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile); - -/** - * Get the values at the given percentiles. - * - * @param h "This" pointer. - * @param percentiles The ordered percentiles array to get the values for. - * @param length Number of elements in the arrays. - * @param values Destination array containing the values at the given percentiles. - * The values array should be allocated by the caller. - * @return 0 on success, ENOMEM if the provided destination array is null. - */ -int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length); - -/** - * Gets the standard deviation for the values in the histogram. - * - * @param h "This" pointer - * @return The standard deviation - */ -double hdr_stddev(const struct hdr_histogram* h); - -/** - * Gets the mean for the values in the histogram. - * - * @param h "This" pointer - * @return The mean - */ -double hdr_mean(const struct hdr_histogram* h); - -/** - * Determine if two values are equivalent with the histogram's resolution. - * Where "equivalent" means that value samples recorded for any two - * equivalent values are counted in a common total count. - * - * @param h "This" pointer - * @param a first value to compare - * @param b second value to compare - * @return 'true' if values are equivalent with the histogram's resolution. - */ -bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b); - -/** - * Get the lowest value that is equivalent to the given value within the histogram's resolution. - * Where "equivalent" means that value samples recorded for any two - * equivalent values are counted in a common total count. - * - * @param h "This" pointer - * @param value The given value - * @return The lowest value that is equivalent to the given value within the histogram's resolution. - */ -int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value); - -/** - * Get the count of recorded values at a specific value - * (to within the histogram resolution at the value level). - * - * @param h "This" pointer - * @param value The value for which to provide the recorded count - * @return The total count of values recorded in the histogram within the value range that is - * {@literal >=} lowestEquivalentValue(<i>value</i>) and {@literal <=} highestEquivalentValue(<i>value</i>) - */ -int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value); - -int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index); - -int64_t hdr_value_at_index(const struct hdr_histogram* h, int32_t index); - -struct hdr_iter_percentiles -{ - bool seen_last_value; - int32_t ticks_per_half_distance; - double percentile_to_iterate_to; - double percentile; -}; - -struct hdr_iter_recorded -{ - int64_t count_added_in_this_iteration_step; -}; - -struct hdr_iter_linear -{ - int64_t value_units_per_bucket; - int64_t count_added_in_this_iteration_step; - int64_t next_value_reporting_level; - int64_t next_value_reporting_level_lowest_equivalent; -}; - -struct hdr_iter_log -{ - double log_base; - int64_t count_added_in_this_iteration_step; - int64_t next_value_reporting_level; - int64_t next_value_reporting_level_lowest_equivalent; -}; - -/** - * The basic iterator. This is a generic structure - * that supports all of the types of iteration. Use - * the appropriate initialiser to get the desired - * iteration. - * - * @ - */ -struct hdr_iter -{ - const struct hdr_histogram* h; - /** raw index into the counts array */ - int32_t counts_index; - /** snapshot of the length at the time the iterator is created */ - int64_t total_count; - /** value directly from array for the current counts_index */ - int64_t count; - /** sum of all of the counts up to and including the count at this index */ - int64_t cumulative_count; - /** The current value based on counts_index */ - int64_t value; - int64_t highest_equivalent_value; - int64_t lowest_equivalent_value; - int64_t median_equivalent_value; - int64_t value_iterated_from; - int64_t value_iterated_to; - - union - { - struct hdr_iter_percentiles percentiles; - struct hdr_iter_recorded recorded; - struct hdr_iter_linear linear; - struct hdr_iter_log log; - } specifics; - - bool (* _next_fp)(struct hdr_iter* iter); - -}; - -/** - * Initalises the basic iterator. - * - * @param itr 'This' pointer - * @param h The histogram to iterate over - */ -void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h); - -/** - * Initialise the iterator for use with percentiles. - */ -void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance); - -/** - * Initialise the iterator for use with recorded values. - */ -void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h); - -/** - * Initialise the iterator for use with linear values. - */ -void hdr_iter_linear_init( - struct hdr_iter* iter, - const struct hdr_histogram* h, - int64_t value_units_per_bucket); - -/** - * Update the iterator value units per bucket - */ -void hdr_iter_linear_set_value_units_per_bucket(struct hdr_iter* iter, int64_t value_units_per_bucket); - -/** - * Initialise the iterator for use with logarithmic values - */ -void hdr_iter_log_init( - struct hdr_iter* iter, - const struct hdr_histogram* h, - int64_t value_units_first_bucket, - double log_base); - -/** - * Iterate to the next value for the iterator. If there are no more values - * available return faluse. - * - * @param itr 'This' pointer - * @return 'false' if there are no values remaining for this iterator. - */ -bool hdr_iter_next(struct hdr_iter* iter); - -typedef enum -{ - CLASSIC, - CSV -} format_type; - -/** - * Print out a percentile based histogram to the supplied stream. Note that - * this call will not flush the FILE, this is left up to the user. - * - * @param h 'This' pointer - * @param stream The FILE to write the output to - * @param ticks_per_half_distance The number of iteration steps per half-distance to 100% - * @param value_scale Scale the output values by this amount - * @param format_type Format to use, e.g. CSV. - * @return 0 on success, error code on failure. EIO if an error occurs writing - * the output. - */ -int hdr_percentiles_print( - struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance, - double value_scale, format_type format); - -/** -* Internal allocation methods, used by hdr_dbl_histogram. -*/ -struct hdr_histogram_bucket_config -{ - int64_t lowest_discernible_value; - int64_t highest_trackable_value; - int64_t unit_magnitude; - int64_t significant_figures; - int32_t sub_bucket_half_count_magnitude; - int32_t sub_bucket_half_count; - int64_t sub_bucket_mask; - int32_t sub_bucket_count; - int32_t bucket_count; - int32_t counts_len; -}; - -int hdr_calculate_bucket_config( - int64_t lowest_discernible_value, - int64_t highest_trackable_value, - int significant_figures, - struct hdr_histogram_bucket_config* cfg); - -void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg); - -int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value); - -int64_t hdr_next_non_equivalent_value(const struct hdr_histogram* h, int64_t value); - -int64_t hdr_median_equivalent_value(const struct hdr_histogram* h, int64_t value); - -/** - * Used to reset counters after importing data manually into the histogram, used by the logging code - * and other custom serialisation tools. - */ -void hdr_reset_internal_counters(struct hdr_histogram* h); - -#ifdef __cplusplus -} -#endif - -#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 deleted file mode 100644 index d9401ca..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/hdr_redis_malloc.h +++ /dev/null @@ -1,13 +0,0 @@ -#ifndef HDR_MALLOC_H__ -#define HDR_MALLOC_H__ - -void *zmalloc(size_t size); -void *zcalloc_num(size_t num, size_t size); -void *zrealloc(void *ptr, size_t size); -void zfree(void *ptr); - -#define hdr_malloc zmalloc -#define hdr_calloc zcalloc_num -#define hdr_realloc zrealloc -#define hdr_free zfree -#endif diff --git a/examples/redis-unstable/deps/hdr_histogram/hdr_tests.h b/examples/redis-unstable/deps/hdr_histogram/hdr_tests.h deleted file mode 100644 index c016d3a..0000000 --- a/examples/redis-unstable/deps/hdr_histogram/hdr_tests.h +++ /dev/null @@ -1,22 +0,0 @@ -#ifndef HDR_TESTS_H -#define HDR_TESTS_H - -/* These are functions used in tests and are not intended for normal usage. */ - -#include "hdr_histogram.h" - -#ifdef __cplusplus -extern "C" { -#endif - -int32_t counts_index_for(const struct hdr_histogram* h, int64_t value); -int hdr_encode_compressed(struct hdr_histogram* h, uint8_t** compressed_histogram, size_t* compressed_len); -int hdr_decode_compressed(uint8_t* buffer, size_t length, struct hdr_histogram** histogram); -void hdr_base64_decode_block(const char* input, uint8_t* output); -void hdr_base64_encode_block(const uint8_t* input, char* output); - -#ifdef __cplusplus -} -#endif - -#endif |
