diff options
| author | Sergey Polovko <sergey@polovko.me> | 2022-02-10 16:47:02 +0300 |
|---|---|---|
| committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:02 +0300 |
| commit | 3e0b762a82514bac89c1dd6ea7211e381d8aa248 (patch) | |
| tree | c2d1b379ecaf05ca8f11ed0b5da9d1a950e6e554 /contrib/libs/hdr_histogram | |
| parent | ab3783171cc30e262243a0227c86118f7080c896 (diff) | |
| download | ydb-3e0b762a82514bac89c1dd6ea7211e381d8aa248.tar.gz | |
Restoring authorship annotation for Sergey Polovko <sergey@polovko.me>. Commit 1 of 2.
Diffstat (limited to 'contrib/libs/hdr_histogram')
19 files changed, 2835 insertions, 2835 deletions
diff --git a/contrib/libs/hdr_histogram/COPYING.txt b/contrib/libs/hdr_histogram/COPYING.txt index 0e259d42c9..32ae9cf3ff 100644 --- a/contrib/libs/hdr_histogram/COPYING.txt +++ b/contrib/libs/hdr_histogram/COPYING.txt @@ -1,121 +1,121 @@ -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. +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/contrib/libs/hdr_histogram/LICENSE.txt b/contrib/libs/hdr_histogram/LICENSE.txt index 9b4e66ed7d..bda854f683 100644 --- a/contrib/libs/hdr_histogram/LICENSE.txt +++ b/contrib/libs/hdr_histogram/LICENSE.txt @@ -1,41 +1,41 @@ -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. +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/contrib/libs/hdr_histogram/README.md b/contrib/libs/hdr_histogram/README.md index b669c3fe95..dbb56a7ae0 100644 --- a/contrib/libs/hdr_histogram/README.md +++ b/contrib/libs/hdr_histogram/README.md @@ -1,79 +1,79 @@ -HdrHistogram_c: 'C' port of High Dynamic Range (HDR) Histogram - -HdrHistogram ----------------------------------------------- -[](https://gitter.im/HdrHistogram/HdrHistogram?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge&utm_content=badge) - -Windows Build:  - -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 -``` +HdrHistogram_c: 'C' port of High Dynamic Range (HDR) Histogram + +HdrHistogram +---------------------------------------------- +[](https://gitter.im/HdrHistogram/HdrHistogram?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge&utm_content=badge) + +Windows Build:  + +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/contrib/libs/hdr_histogram/src/hdr_atomic.h b/contrib/libs/hdr_histogram/src/hdr_atomic.h index 7015d985da..4c44aa350a 100644 --- a/contrib/libs/hdr_histogram/src/hdr_atomic.h +++ b/contrib/libs/hdr_histogram/src/hdr_atomic.h @@ -1,59 +1,59 @@ -/** - * 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> - -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) +/** + * 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> + +static void __inline * hdr_atomic_load_pointer(void** pointer) { - _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 initial) -{ - return _InterlockedExchange64(field, initial); -} - -static int64_t __inline hdr_atomic_add_fetch_64(volatile int64_t* field, int64_t value) -{ - return _InterlockedExchangeAdd64(field, value) + value; -} - -#else -#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) -#endif - -#endif /* HDR_ATOMIC_H__ */ + _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 initial) +{ + return _InterlockedExchange64(field, initial); +} + +static int64_t __inline hdr_atomic_add_fetch_64(volatile int64_t* field, int64_t value) +{ + return _InterlockedExchangeAdd64(field, value) + value; +} + +#else +#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) +#endif + +#endif /* HDR_ATOMIC_H__ */ diff --git a/contrib/libs/hdr_histogram/src/hdr_encoding.c b/contrib/libs/hdr_histogram/src/hdr_encoding.c index 758cf68ebb..43db22a3fa 100644 --- a/contrib/libs/hdr_histogram/src/hdr_encoding.c +++ b/contrib/libs/hdr_histogram/src/hdr_encoding.c @@ -1,313 +1,313 @@ -// -// Created by barkerm on 9/09/15. -// - -#include <errno.h> -#include <stddef.h> -#include <math.h> - -#include "hdr_encoding.h" -#include "hdr_tests.h" - -int zig_zag_encode_i64(uint8_t* buffer, int64_t signed_value) -{ - int64_t value = signed_value; - - value = (value << 1) ^ (value >> 63); - int bytesWritten = 0; - if (value >> 7 == 0) - { - buffer[0] = (uint8_t) value; - bytesWritten = 1; - } - else - { - buffer[0] = (uint8_t) ((value & 0x7F) | 0x80); - if (value >> 14 == 0) - { - buffer[1] = (uint8_t) (value >> 7); - bytesWritten = 2; - } - else - { - buffer[1] = (uint8_t) ((value >> 7 | 0x80)); - if (value >> 21 == 0) - { - buffer[2] = (uint8_t) (value >> 14); - bytesWritten = 3; - } - else - { - buffer[2] = (uint8_t) (value >> 14 | 0x80); - if (value >> 28 == 0) - { - buffer[3] = (uint8_t) (value >> 21); - bytesWritten = 4; - } - else - { - buffer[3] = (uint8_t) (value >> 21 | 0x80); - if (value >> 35 == 0) - { - buffer[4] = (uint8_t) (value >> 28); - bytesWritten = 5; - } - else - { - buffer[4] = (uint8_t) (value >> 28 | 0x80); - if (value >> 42 == 0) - { - buffer[5] = (uint8_t) (value >> 35); - bytesWritten = 6; - } - else - { - buffer[5] = (uint8_t) (value >> 35 | 0x80); - if (value >> 49 == 0) - { - buffer[6] = (uint8_t) (value >> 42); - bytesWritten = 7; - } - else - { - buffer[6] = (uint8_t) (value >> 42 | 0x80); - if (value >> 56 == 0) - { - buffer[7] = (uint8_t) (value >> 49); - bytesWritten = 8; - } - else - { - buffer[7] = (uint8_t) (value >> 49 | 0x80); - buffer[8] = (uint8_t) (value >> 56); - bytesWritten = 9; - } - } - } - } - } - } - } - } - - return bytesWritten; -} - -int zig_zag_decode_i64(const uint8_t* buffer, int64_t* retVal) -{ - uint64_t v = buffer[0]; - uint64_t value = v & 0x7F; - int bytesRead = 1; - if ((v & 0x80) != 0) - { - bytesRead = 2; - v = buffer[1]; - value |= (v & 0x7F) << 7; - if ((v & 0x80) != 0) - { - bytesRead = 3; - v = buffer[2]; - value |= (v & 0x7F) << 14; - if ((v & 0x80) != 0) - { - bytesRead = 4; - v = buffer[3]; - value |= (v & 0x7F) << 21; - if ((v & 0x80) != 0) - { - bytesRead = 5; - v = buffer[4]; - value |= (v & 0x7F) << 28; - if ((v & 0x80) != 0) - { - bytesRead = 6; - v = buffer[5]; - value |= (v & 0x7F) << 35; - if ((v & 0x80) != 0) - { - bytesRead = 7; - v = buffer[6]; - value |= (v & 0x7F) << 42; - if ((v & 0x80) != 0) - { - bytesRead = 8; - v = buffer[7]; - value |= (v & 0x7F) << 49; - if ((v & 0x80) != 0) - { - bytesRead = 9; - v = buffer[8]; - value |= v << 56; - } - } - } - } - } - } - } - } - - value = (value >> 1) ^ (-(value & 1)); - *retVal = (int64_t) value; - - return bytesRead; -} - -static const char base64_table[] = - { - 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', - 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', - 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', - 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', - '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/', '\0' - }; - -static char get_base_64(uint32_t _24_bit_value, int shift) -{ - uint32_t _6_bit_value = 0x3F & (_24_bit_value >> shift); - return base64_table[_6_bit_value]; -} - -static int from_base_64(int c) -{ - if ('A' <= c && c <= 'Z') - { - return c - 'A'; - } - else if ('a' <= c && c <= 'z') - { - return (c - 'a') + 26; - } - else if ('0' <= c && c <= '9') - { - return (c - '0') + 52; - } - else if ('+' == c) - { - return 62; - } - else if ('/' == c) - { - return 63; - } - else if ('=' == c) - { - return 0; - } - - return EINVAL; -} - -size_t hdr_base64_encoded_len(size_t decoded_size) -{ - return (size_t) (ceil(decoded_size / 3.0) * 4.0); -} - -size_t hdr_base64_decoded_len(size_t encoded_size) -{ - return (encoded_size / 4) * 3; -} - -static void hdr_base64_encode_block_pad(const uint8_t* input, char* output, size_t pad) -{ - uint32_t _24_bit_value = 0; - - switch (pad) - { - case 2: - _24_bit_value = (input[0] << 16) + (input[1] << 8); - - output[0] = get_base_64(_24_bit_value, 18); - output[1] = get_base_64(_24_bit_value, 12); - output[2] = get_base_64(_24_bit_value, 6); - output[3] = '='; - - break; - - case 1: - _24_bit_value = (input[0] << 16); - - output[0] = get_base_64(_24_bit_value, 18); - output[1] = get_base_64(_24_bit_value, 12); - output[2] = '='; - output[3] = '='; - - break; - - default: - // No-op - break; - } -} - -/** - * Assumes that there is 3 input bytes and 4 output chars. - */ -void hdr_base64_encode_block(const uint8_t* input, char* output) -{ - uint32_t _24_bit_value = (input[0] << 16) + (input[1] << 8) + (input[2]); - - output[0] = get_base_64(_24_bit_value, 18); - output[1] = get_base_64(_24_bit_value, 12); - output[2] = get_base_64(_24_bit_value, 6); - output[3] = get_base_64(_24_bit_value, 0); -} - -int hdr_base64_encode( - const uint8_t* input, size_t input_len, char* output, size_t output_len) -{ - if (hdr_base64_encoded_len(input_len) != output_len) - { - return EINVAL; - } - - size_t i = 0; - size_t j = 0; - for (; input_len - i >= 3 && j < output_len; i += 3, j += 4) - { - hdr_base64_encode_block(&input[i], &output[j]); - } - - size_t remaining = input_len - i; - - hdr_base64_encode_block_pad(&input[i], &output[j], remaining); - - return 0; -} - -/** - * Assumes that there is 4 input chars available and 3 output chars. - */ -void hdr_base64_decode_block(const char* input, uint8_t* output) -{ - uint32_t _24_bit_value = 0; - - _24_bit_value |= from_base_64(input[0]) << 18; - _24_bit_value |= from_base_64(input[1]) << 12; - _24_bit_value |= from_base_64(input[2]) << 6; - _24_bit_value |= from_base_64(input[3]); - - output[0] = (uint8_t) ((_24_bit_value >> 16) & 0xFF); - output[1] = (uint8_t) ((_24_bit_value >> 8) & 0xFF); - output[2] = (uint8_t) ((_24_bit_value) & 0xFF); -} - -int hdr_base64_decode( - const char* input, size_t input_len, uint8_t* output, size_t output_len) -{ - size_t i, j; - - if (input_len < 4 || - (input_len & 3) != 0 || - (input_len / 4) * 3 != output_len) - { - return EINVAL; - } - - for (i = 0, j = 0; i < input_len; i += 4, j += 3) - { - hdr_base64_decode_block(&input[i], &output[j]); - } - - return 0; -} +// +// Created by barkerm on 9/09/15. +// + +#include <errno.h> +#include <stddef.h> +#include <math.h> + +#include "hdr_encoding.h" +#include "hdr_tests.h" + +int zig_zag_encode_i64(uint8_t* buffer, int64_t signed_value) +{ + int64_t value = signed_value; + + value = (value << 1) ^ (value >> 63); + int bytesWritten = 0; + if (value >> 7 == 0) + { + buffer[0] = (uint8_t) value; + bytesWritten = 1; + } + else + { + buffer[0] = (uint8_t) ((value & 0x7F) | 0x80); + if (value >> 14 == 0) + { + buffer[1] = (uint8_t) (value >> 7); + bytesWritten = 2; + } + else + { + buffer[1] = (uint8_t) ((value >> 7 | 0x80)); + if (value >> 21 == 0) + { + buffer[2] = (uint8_t) (value >> 14); + bytesWritten = 3; + } + else + { + buffer[2] = (uint8_t) (value >> 14 | 0x80); + if (value >> 28 == 0) + { + buffer[3] = (uint8_t) (value >> 21); + bytesWritten = 4; + } + else + { + buffer[3] = (uint8_t) (value >> 21 | 0x80); + if (value >> 35 == 0) + { + buffer[4] = (uint8_t) (value >> 28); + bytesWritten = 5; + } + else + { + buffer[4] = (uint8_t) (value >> 28 | 0x80); + if (value >> 42 == 0) + { + buffer[5] = (uint8_t) (value >> 35); + bytesWritten = 6; + } + else + { + buffer[5] = (uint8_t) (value >> 35 | 0x80); + if (value >> 49 == 0) + { + buffer[6] = (uint8_t) (value >> 42); + bytesWritten = 7; + } + else + { + buffer[6] = (uint8_t) (value >> 42 | 0x80); + if (value >> 56 == 0) + { + buffer[7] = (uint8_t) (value >> 49); + bytesWritten = 8; + } + else + { + buffer[7] = (uint8_t) (value >> 49 | 0x80); + buffer[8] = (uint8_t) (value >> 56); + bytesWritten = 9; + } + } + } + } + } + } + } + } + + return bytesWritten; +} + +int zig_zag_decode_i64(const uint8_t* buffer, int64_t* retVal) +{ + uint64_t v = buffer[0]; + uint64_t value = v & 0x7F; + int bytesRead = 1; + if ((v & 0x80) != 0) + { + bytesRead = 2; + v = buffer[1]; + value |= (v & 0x7F) << 7; + if ((v & 0x80) != 0) + { + bytesRead = 3; + v = buffer[2]; + value |= (v & 0x7F) << 14; + if ((v & 0x80) != 0) + { + bytesRead = 4; + v = buffer[3]; + value |= (v & 0x7F) << 21; + if ((v & 0x80) != 0) + { + bytesRead = 5; + v = buffer[4]; + value |= (v & 0x7F) << 28; + if ((v & 0x80) != 0) + { + bytesRead = 6; + v = buffer[5]; + value |= (v & 0x7F) << 35; + if ((v & 0x80) != 0) + { + bytesRead = 7; + v = buffer[6]; + value |= (v & 0x7F) << 42; + if ((v & 0x80) != 0) + { + bytesRead = 8; + v = buffer[7]; + value |= (v & 0x7F) << 49; + if ((v & 0x80) != 0) + { + bytesRead = 9; + v = buffer[8]; + value |= v << 56; + } + } + } + } + } + } + } + } + + value = (value >> 1) ^ (-(value & 1)); + *retVal = (int64_t) value; + + return bytesRead; +} + +static const char base64_table[] = + { + 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', + 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', + 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', + 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', + '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/', '\0' + }; + +static char get_base_64(uint32_t _24_bit_value, int shift) +{ + uint32_t _6_bit_value = 0x3F & (_24_bit_value >> shift); + return base64_table[_6_bit_value]; +} + +static int from_base_64(int c) +{ + if ('A' <= c && c <= 'Z') + { + return c - 'A'; + } + else if ('a' <= c && c <= 'z') + { + return (c - 'a') + 26; + } + else if ('0' <= c && c <= '9') + { + return (c - '0') + 52; + } + else if ('+' == c) + { + return 62; + } + else if ('/' == c) + { + return 63; + } + else if ('=' == c) + { + return 0; + } + + return EINVAL; +} + +size_t hdr_base64_encoded_len(size_t decoded_size) +{ + return (size_t) (ceil(decoded_size / 3.0) * 4.0); +} + +size_t hdr_base64_decoded_len(size_t encoded_size) +{ + return (encoded_size / 4) * 3; +} + +static void hdr_base64_encode_block_pad(const uint8_t* input, char* output, size_t pad) +{ + uint32_t _24_bit_value = 0; + + switch (pad) + { + case 2: + _24_bit_value = (input[0] << 16) + (input[1] << 8); + + output[0] = get_base_64(_24_bit_value, 18); + output[1] = get_base_64(_24_bit_value, 12); + output[2] = get_base_64(_24_bit_value, 6); + output[3] = '='; + + break; + + case 1: + _24_bit_value = (input[0] << 16); + + output[0] = get_base_64(_24_bit_value, 18); + output[1] = get_base_64(_24_bit_value, 12); + output[2] = '='; + output[3] = '='; + + break; + + default: + // No-op + break; + } +} + +/** + * Assumes that there is 3 input bytes and 4 output chars. + */ +void hdr_base64_encode_block(const uint8_t* input, char* output) +{ + uint32_t _24_bit_value = (input[0] << 16) + (input[1] << 8) + (input[2]); + + output[0] = get_base_64(_24_bit_value, 18); + output[1] = get_base_64(_24_bit_value, 12); + output[2] = get_base_64(_24_bit_value, 6); + output[3] = get_base_64(_24_bit_value, 0); +} + +int hdr_base64_encode( + const uint8_t* input, size_t input_len, char* output, size_t output_len) +{ + if (hdr_base64_encoded_len(input_len) != output_len) + { + return EINVAL; + } + + size_t i = 0; + size_t j = 0; + for (; input_len - i >= 3 && j < output_len; i += 3, j += 4) + { + hdr_base64_encode_block(&input[i], &output[j]); + } + + size_t remaining = input_len - i; + + hdr_base64_encode_block_pad(&input[i], &output[j], remaining); + + return 0; +} + +/** + * Assumes that there is 4 input chars available and 3 output chars. + */ +void hdr_base64_decode_block(const char* input, uint8_t* output) +{ + uint32_t _24_bit_value = 0; + + _24_bit_value |= from_base_64(input[0]) << 18; + _24_bit_value |= from_base_64(input[1]) << 12; + _24_bit_value |= from_base_64(input[2]) << 6; + _24_bit_value |= from_base_64(input[3]); + + output[0] = (uint8_t) ((_24_bit_value >> 16) & 0xFF); + output[1] = (uint8_t) ((_24_bit_value >> 8) & 0xFF); + output[2] = (uint8_t) ((_24_bit_value) & 0xFF); +} + +int hdr_base64_decode( + const char* input, size_t input_len, uint8_t* output, size_t output_len) +{ + size_t i, j; + + if (input_len < 4 || + (input_len & 3) != 0 || + (input_len / 4) * 3 != output_len) + { + return EINVAL; + } + + for (i = 0, j = 0; i < input_len; i += 4, j += 3) + { + hdr_base64_decode_block(&input[i], &output[j]); + } + + return 0; +} diff --git a/contrib/libs/hdr_histogram/src/hdr_encoding.h b/contrib/libs/hdr_histogram/src/hdr_encoding.h index 141093ba3b..dc9076d7bb 100644 --- a/contrib/libs/hdr_histogram/src/hdr_encoding.h +++ b/contrib/libs/hdr_histogram/src/hdr_encoding.h @@ -1,77 +1,77 @@ -// -// Created by barkerm on 9/09/15. -// - -#ifndef HDR_ENCODING_H -#define HDR_ENCODING_H - -#include <stdint.h> - -#define MAX_BYTES_LEB128 9 - -#ifdef __cplusplus -extern "C" { -#endif - -/** - * Writes a int64_t value to the given buffer in LEB128 ZigZag encoded format - * - * @param buffer the buffer to write to - * @param signed_value the value to write to the buffer - * @return the number of bytes written to the buffer - */ -int zig_zag_encode_i64(uint8_t* buffer, int64_t signed_value); - -/** - * Read an LEB128 ZigZag encoded long value from the given buffer - * - * @param buffer the buffer to read from - * @param retVal out value to capture the read value - * @return the number of bytes read from the buffer - */ -int zig_zag_decode_i64(const uint8_t* buffer, int64_t* signed_value); - -/** - * Gets the length in bytes of base64 data, given the input size. - * - * @param decoded_size the size of the unencoded values. - * @return the encoded size - */ -size_t hdr_base64_encoded_len(size_t decoded_size); - -/** - * Encode into base64. - * - * @param input the data to encode - * @param input_len the length of the data to encode - * @param output the buffer to write the output to - * @param output_len the number of bytes to write to the output - */ -int hdr_base64_encode( - const uint8_t* input, size_t input_len, char* output, size_t output_len); - -/** - * Gets the length in bytes of decoded base64 data, given the size of the base64 encoded - * data. - * - * @param encoded_size the size of the encoded value. - * @return the decoded size - */ -size_t hdr_base64_decoded_len(size_t encoded_size); - -/** - * Decode from base64. - * - * @param input the base64 encoded data - * @param input_len the size in bytes of the endcoded data - * @param output the buffer to write the decoded data to - * @param output_len the number of bytes to write to the output data - */ -int hdr_base64_decode( - const char* input, size_t input_len, uint8_t* output, size_t output_len); - -#ifdef __cplusplus -} -#endif - -#endif //HDR_HISTOGRAM_HDR_ENCODING_H +// +// Created by barkerm on 9/09/15. +// + +#ifndef HDR_ENCODING_H +#define HDR_ENCODING_H + +#include <stdint.h> + +#define MAX_BYTES_LEB128 9 + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * Writes a int64_t value to the given buffer in LEB128 ZigZag encoded format + * + * @param buffer the buffer to write to + * @param signed_value the value to write to the buffer + * @return the number of bytes written to the buffer + */ +int zig_zag_encode_i64(uint8_t* buffer, int64_t signed_value); + +/** + * Read an LEB128 ZigZag encoded long value from the given buffer + * + * @param buffer the buffer to read from + * @param retVal out value to capture the read value + * @return the number of bytes read from the buffer + */ +int zig_zag_decode_i64(const uint8_t* buffer, int64_t* signed_value); + +/** + * Gets the length in bytes of base64 data, given the input size. + * + * @param decoded_size the size of the unencoded values. + * @return the encoded size + */ +size_t hdr_base64_encoded_len(size_t decoded_size); + +/** + * Encode into base64. + * + * @param input the data to encode + * @param input_len the length of the data to encode + * @param output the buffer to write the output to + * @param output_len the number of bytes to write to the output + */ +int hdr_base64_encode( + const uint8_t* input, size_t input_len, char* output, size_t output_len); + +/** + * Gets the length in bytes of decoded base64 data, given the size of the base64 encoded + * data. + * + * @param encoded_size the size of the encoded value. + * @return the decoded size + */ +size_t hdr_base64_decoded_len(size_t encoded_size); + +/** + * Decode from base64. + * + * @param input the base64 encoded data + * @param input_len the size in bytes of the endcoded data + * @param output the buffer to write the decoded data to + * @param output_len the number of bytes to write to the output data + */ +int hdr_base64_decode( + const char* input, size_t input_len, uint8_t* output, size_t output_len); + +#ifdef __cplusplus +} +#endif + +#endif //HDR_HISTOGRAM_HDR_ENCODING_H diff --git a/contrib/libs/hdr_histogram/src/hdr_endian.h b/contrib/libs/hdr_histogram/src/hdr_endian.h index 839fdb16b1..a677e5a44a 100644 --- a/contrib/libs/hdr_histogram/src/hdr_endian.h +++ b/contrib/libs/hdr_histogram/src/hdr_endian.h @@ -1,116 +1,116 @@ -/** -* hdr_time.h -* Released to the public domain, as explained at http://creativecommons.org/publicdomain/zero/1.0/ -*/ - -#ifndef HDR_ENDIAN_H__ -#define HDR_ENDIAN_H__ - -#if (defined(_WIN16) || defined(_WIN32) || defined(_WIN64)) && !defined(__WINDOWS__) - -# define __WINDOWS__ - -#endif - -#if defined(__linux__) || defined(__CYGWIN__) - -# include <endian.h> - -#elif defined(__APPLE__) - -# include <libkern/OSByteOrder.h> - -# define htobe16(x) OSSwapHostToBigInt16(x) -# define htole16(x) OSSwapHostToLittleInt16(x) -# define be16toh(x) OSSwapBigToHostInt16(x) -# define le16toh(x) OSSwapLittleToHostInt16(x) - -# define htobe32(x) OSSwapHostToBigInt32(x) -# define htole32(x) OSSwapHostToLittleInt32(x) -# define be32toh(x) OSSwapBigToHostInt32(x) -# define le32toh(x) OSSwapLittleToHostInt32(x) - -# define htobe64(x) OSSwapHostToBigInt64(x) -# define htole64(x) OSSwapHostToLittleInt64(x) -# define be64toh(x) OSSwapBigToHostInt64(x) -# define le64toh(x) OSSwapLittleToHostInt64(x) - -# define __BYTE_ORDER BYTE_ORDER -# define __BIG_ENDIAN BIG_ENDIAN -# define __LITTLE_ENDIAN LITTLE_ENDIAN -# define __PDP_ENDIAN PDP_ENDIAN - -#elif defined(__OpenBSD__) - -# include <sys/endian.h> - -#elif defined(__NetBSD__) || defined(__FreeBSD__) || defined(__DragonFly__) - -# include <sys/endian.h> - -# define be16toh(x) betoh16(x) -# define le16toh(x) letoh16(x) - -# define be32toh(x) betoh32(x) -# define le32toh(x) letoh32(x) - -# define be64toh(x) betoh64(x) -# define le64toh(x) letoh64(x) - -#elif defined(__WINDOWS__) - -# include <winsock2.h> - -# if BYTE_ORDER == LITTLE_ENDIAN - -# define htobe16(x) htons(x) -# define htole16(x) (x) -# define be16toh(x) ntohs(x) -# define le16toh(x) (x) - -# define htobe32(x) htonl(x) -# define htole32(x) (x) -# define be32toh(x) ntohl(x) -# define le32toh(x) (x) - -# define htobe64(x) htonll(x) -# define htole64(x) (x) -# define be64toh(x) ntohll(x) -# define le64toh(x) (x) - -# elif BYTE_ORDER == BIG_ENDIAN - - /* that would be xbox 360 */ -# define htobe16(x) (x) -# define htole16(x) __builtin_bswap16(x) -# define be16toh(x) (x) -# define le16toh(x) __builtin_bswap16(x) - -# define htobe32(x) (x) -# define htole32(x) __builtin_bswap32(x) -# define be32toh(x) (x) -# define le32toh(x) __builtin_bswap32(x) - -# define htobe64(x) (x) -# define htole64(x) __builtin_bswap64(x) -# define be64toh(x) (x) -# define le64toh(x) __builtin_bswap64(x) - -# else - -# error byte order not supported - -# endif - -# define __BYTE_ORDER BYTE_ORDER -# define __BIG_ENDIAN BIG_ENDIAN -# define __LITTLE_ENDIAN LITTLE_ENDIAN -# define __PDP_ENDIAN PDP_ENDIAN - -#else - -# error platform not supported - -#endif - -#endif +/** +* hdr_time.h +* Released to the public domain, as explained at http://creativecommons.org/publicdomain/zero/1.0/ +*/ + +#ifndef HDR_ENDIAN_H__ +#define HDR_ENDIAN_H__ + +#if (defined(_WIN16) || defined(_WIN32) || defined(_WIN64)) && !defined(__WINDOWS__) + +# define __WINDOWS__ + +#endif + +#if defined(__linux__) || defined(__CYGWIN__) + +# include <endian.h> + +#elif defined(__APPLE__) + +# include <libkern/OSByteOrder.h> + +# define htobe16(x) OSSwapHostToBigInt16(x) +# define htole16(x) OSSwapHostToLittleInt16(x) +# define be16toh(x) OSSwapBigToHostInt16(x) +# define le16toh(x) OSSwapLittleToHostInt16(x) + +# define htobe32(x) OSSwapHostToBigInt32(x) +# define htole32(x) OSSwapHostToLittleInt32(x) +# define be32toh(x) OSSwapBigToHostInt32(x) +# define le32toh(x) OSSwapLittleToHostInt32(x) + +# define htobe64(x) OSSwapHostToBigInt64(x) +# define htole64(x) OSSwapHostToLittleInt64(x) +# define be64toh(x) OSSwapBigToHostInt64(x) +# define le64toh(x) OSSwapLittleToHostInt64(x) + +# define __BYTE_ORDER BYTE_ORDER +# define __BIG_ENDIAN BIG_ENDIAN +# define __LITTLE_ENDIAN LITTLE_ENDIAN +# define __PDP_ENDIAN PDP_ENDIAN + +#elif defined(__OpenBSD__) + +# include <sys/endian.h> + +#elif defined(__NetBSD__) || defined(__FreeBSD__) || defined(__DragonFly__) + +# include <sys/endian.h> + +# define be16toh(x) betoh16(x) +# define le16toh(x) letoh16(x) + +# define be32toh(x) betoh32(x) +# define le32toh(x) letoh32(x) + +# define be64toh(x) betoh64(x) +# define le64toh(x) letoh64(x) + +#elif defined(__WINDOWS__) + +# include <winsock2.h> + +# if BYTE_ORDER == LITTLE_ENDIAN + +# define htobe16(x) htons(x) +# define htole16(x) (x) +# define be16toh(x) ntohs(x) +# define le16toh(x) (x) + +# define htobe32(x) htonl(x) +# define htole32(x) (x) +# define be32toh(x) ntohl(x) +# define le32toh(x) (x) + +# define htobe64(x) htonll(x) +# define htole64(x) (x) +# define be64toh(x) ntohll(x) +# define le64toh(x) (x) + +# elif BYTE_ORDER == BIG_ENDIAN + + /* that would be xbox 360 */ +# define htobe16(x) (x) +# define htole16(x) __builtin_bswap16(x) +# define be16toh(x) (x) +# define le16toh(x) __builtin_bswap16(x) + +# define htobe32(x) (x) +# define htole32(x) __builtin_bswap32(x) +# define be32toh(x) (x) +# define le32toh(x) __builtin_bswap32(x) + +# define htobe64(x) (x) +# define htole64(x) __builtin_bswap64(x) +# define be64toh(x) (x) +# define le64toh(x) __builtin_bswap64(x) + +# else + +# error byte order not supported + +# endif + +# define __BYTE_ORDER BYTE_ORDER +# define __BIG_ENDIAN BIG_ENDIAN +# define __LITTLE_ENDIAN LITTLE_ENDIAN +# define __PDP_ENDIAN PDP_ENDIAN + +#else + +# error platform not supported + +#endif + +#endif diff --git a/contrib/libs/hdr_histogram/src/hdr_histogram.c b/contrib/libs/hdr_histogram/src/hdr_histogram.c index 8cad5a0d61..044afe2a22 100644 --- a/contrib/libs/hdr_histogram/src/hdr_histogram.c +++ b/contrib/libs/hdr_histogram/src/hdr_histogram.c @@ -1,1010 +1,1010 @@ -/** - * 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 <assert.h> -#include <stdio.h> -#include <string.h> -#include <stdint.h> -#include <errno.h> -#include <inttypes.h> - -#include "hdr_histogram.h" -#include "hdr_tests.h" - -// ###### ####### ## ## ## ## ######## ###### -// ## ## ## ## ## ## ### ## ## ## ## -// ## ## ## ## ## #### ## ## ## -// ## ## ## ## ## ## ## ## ## ###### -// ## ## ## ## ## ## #### ## ## -// ## ## ## ## ## ## ## ### ## ## ## -// ###### ####### ####### ## ## ## ###### - -static int32_t normalize_index(const struct hdr_histogram* h, int32_t index) -{ - if (h->normalizing_index_offset == 0) - { - return index; - } - - int32_t normalized_index = index - h->normalizing_index_offset; - int32_t adjustment = 0; - - 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 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 int64_t power(int64_t base, int64_t exp) -{ - int64_t result = 1; - while(exp) - { - result *= base; exp--; - } - return result; -} - -#if defined(_MSC_VER) -#pragma intrinsic(_BitScanReverse64) -#endif - -static int32_t get_bucket_index(const struct hdr_histogram* h, int64_t value) -{ -#if defined(_MSC_VER) - uint32_t leading_zero = 0; - _BitScanReverse64(&leading_zero, value | h->sub_bucket_mask); - int32_t pow2ceiling = 64 - (63 - leading_zero); // smallest power of 2 containing value -#else - int32_t pow2ceiling = 64 - __builtin_clzll(value | h->sub_bucket_mask); // smallest power of 2 containing value -#endif - 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 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); -} - -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_trackable_value, - int64_t highest_trackable_value, - int significant_figures, - struct hdr_histogram_bucket_config* cfg) -{ - if (lowest_trackable_value < 1 || - significant_figures < 1 || 5 < significant_figures) - { - return EINVAL; - } - else if (lowest_trackable_value * 2 > highest_trackable_value) - { - return EINVAL; - } - - cfg->lowest_trackable_value = lowest_trackable_value; - cfg->significant_figures = significant_figures; - cfg->highest_trackable_value = highest_trackable_value; - - int64_t largest_value_with_single_unit_resolution = 2 * power(10, significant_figures); - int32_t 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; - - cfg->unit_magnitude = (int32_t) floor(log((double)lowest_trackable_value) / log(2)); - - 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; - - // determine exponent range needed to support the trackable value with no overflow: - 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_trackable_value = cfg->lowest_trackable_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_trackable_value, - int64_t highest_trackable_value, - int significant_figures, - struct hdr_histogram** result) -{ - struct hdr_histogram_bucket_config cfg; - - int r = hdr_calculate_bucket_config(lowest_trackable_value, highest_trackable_value, significant_figures, &cfg); - if (r) - { - return r; - } - - size_t histogram_size = sizeof(struct hdr_histogram) + cfg.counts_len * sizeof(int64_t); - struct hdr_histogram* histogram = malloc(histogram_size); - - if (!histogram) - { - return ENOMEM; - } - - // memset will ensure that all of the function pointers are null. - memset((void*) histogram, 0, histogram_size); - - hdr_init_preallocated(histogram, &cfg); - *result = histogram; - - return 0; -} - - -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((void *) &h->counts, 0, (sizeof(int64_t) * h->counts_len)); - return; -} - -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_values(struct hdr_histogram* h, int64_t value, int64_t count) -{ - if (value < 0) - { - return false; - } - - int32_t 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_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_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval) -{ - if (!hdr_record_values(h, value, count)) - { - return false; - } - - if (expected_interval <= 0 || value <= expected_interval) - { - return true; - } - - int64_t 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; -} - -int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from) -{ - struct hdr_iter iter; - hdr_iter_recorded_init(&iter, from); - int64_t dropped = 0; - - 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; - hdr_iter_recorded_init(&iter, from); - int64_t dropped = 0; - - 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); -} - -int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile) -{ - struct hdr_iter iter; - hdr_iter_init(&iter, h); - - double requested_percentile = percentile < 100.0 ? percentile : 100.0; - int64_t count_at_percentile = - (int64_t) (((requested_percentile / 100) * h->total_count) + 0.5); - count_at_percentile = count_at_percentile > 1 ? count_at_percentile : 1; - int64_t total = 0; - - while (hdr_iter_next(&iter)) - { - total += iter.count; - - if (total >= count_at_percentile) - { - int64_t value_from_index = iter.value; - return highest_equivalent_value(h, value_from_index); - } - } - - 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; - - iter->value = hdr_value_at_index(iter->h, iter->counts_index); - iter->highest_equivalent_value = highest_equivalent_value(iter->h, iter->value); - iter->lowest_equivalent_value = lowest_equivalent_value(iter->h, iter->value); - iter->median_equivalent_value = hdr_median_equivalent_value(iter->h, iter->value); - - 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)) - { - 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) -{ - 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; - int64_t temp = (int64_t)(log(100 / (100.0 - (percentiles->percentile_to_iterate_to))) / log(2)) + 1; - int64_t half_distance = (int64_t) pow(2, (double) temp); - int64_t 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; -} - -// ## ####### ###### ### ######## #### ######## ## ## ## ## #### ###### -// ## ## ## ## ## ## ## ## ## ## ## ## ## ### ### ## ## ## -// ## ## ## ## ## ## ## ## ## ## ## ## #### #### ## ## -// ## ## ## ## #### ## ## ######## ## ## ######### ## ### ## ## ## -// ## ## ## ## ## ######### ## ## ## ## ## ## ## ## ## ## -// ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## -// ######## ####### ###### ## ## ## ## #### ## ## ## ## ## #### ###### - -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: - return "%12s %12s %12s %12s\n\n"; - 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]; - format_line_string(line_format, 25, h->significant_figures, format); - const char* head_format = format_head_string(format); - int rc = 0; - - struct hdr_iter iter; - 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; - } - - struct hdr_iter_percentiles * 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; -} +/** + * 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 <assert.h> +#include <stdio.h> +#include <string.h> +#include <stdint.h> +#include <errno.h> +#include <inttypes.h> + +#include "hdr_histogram.h" +#include "hdr_tests.h" + +// ###### ####### ## ## ## ## ######## ###### +// ## ## ## ## ## ## ### ## ## ## ## +// ## ## ## ## ## #### ## ## ## +// ## ## ## ## ## ## ## ## ## ###### +// ## ## ## ## ## ## #### ## ## +// ## ## ## ## ## ## ## ### ## ## ## +// ###### ####### ####### ## ## ## ###### + +static int32_t normalize_index(const struct hdr_histogram* h, int32_t index) +{ + if (h->normalizing_index_offset == 0) + { + return index; + } + + int32_t normalized_index = index - h->normalizing_index_offset; + int32_t adjustment = 0; + + 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 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 int64_t power(int64_t base, int64_t exp) +{ + int64_t result = 1; + while(exp) + { + result *= base; exp--; + } + return result; +} + +#if defined(_MSC_VER) +#pragma intrinsic(_BitScanReverse64) +#endif + +static int32_t get_bucket_index(const struct hdr_histogram* h, int64_t value) +{ +#if defined(_MSC_VER) + uint32_t leading_zero = 0; + _BitScanReverse64(&leading_zero, value | h->sub_bucket_mask); + int32_t pow2ceiling = 64 - (63 - leading_zero); // smallest power of 2 containing value +#else + int32_t pow2ceiling = 64 - __builtin_clzll(value | h->sub_bucket_mask); // smallest power of 2 containing value +#endif + 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 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); +} + +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_trackable_value, + int64_t highest_trackable_value, + int significant_figures, + struct hdr_histogram_bucket_config* cfg) +{ + if (lowest_trackable_value < 1 || + significant_figures < 1 || 5 < significant_figures) + { + return EINVAL; + } + else if (lowest_trackable_value * 2 > highest_trackable_value) + { + return EINVAL; + } + + cfg->lowest_trackable_value = lowest_trackable_value; + cfg->significant_figures = significant_figures; + cfg->highest_trackable_value = highest_trackable_value; + + int64_t largest_value_with_single_unit_resolution = 2 * power(10, significant_figures); + int32_t 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; + + cfg->unit_magnitude = (int32_t) floor(log((double)lowest_trackable_value) / log(2)); + + 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; + + // determine exponent range needed to support the trackable value with no overflow: + 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_trackable_value = cfg->lowest_trackable_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_trackable_value, + int64_t highest_trackable_value, + int significant_figures, + struct hdr_histogram** result) +{ + struct hdr_histogram_bucket_config cfg; + + int r = hdr_calculate_bucket_config(lowest_trackable_value, highest_trackable_value, significant_figures, &cfg); + if (r) + { + return r; + } + + size_t histogram_size = sizeof(struct hdr_histogram) + cfg.counts_len * sizeof(int64_t); + struct hdr_histogram* histogram = malloc(histogram_size); + + if (!histogram) + { + return ENOMEM; + } + + // memset will ensure that all of the function pointers are null. + memset((void*) histogram, 0, histogram_size); + + hdr_init_preallocated(histogram, &cfg); + *result = histogram; + + return 0; +} + + +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((void *) &h->counts, 0, (sizeof(int64_t) * h->counts_len)); + return; +} + +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_values(struct hdr_histogram* h, int64_t value, int64_t count) +{ + if (value < 0) + { + return false; + } + + int32_t 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_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_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval) +{ + if (!hdr_record_values(h, value, count)) + { + return false; + } + + if (expected_interval <= 0 || value <= expected_interval) + { + return true; + } + + int64_t 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; +} + +int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from) +{ + struct hdr_iter iter; + hdr_iter_recorded_init(&iter, from); + int64_t dropped = 0; + + 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; + hdr_iter_recorded_init(&iter, from); + int64_t dropped = 0; + + 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); +} + +int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile) +{ + struct hdr_iter iter; + hdr_iter_init(&iter, h); + + double requested_percentile = percentile < 100.0 ? percentile : 100.0; + int64_t count_at_percentile = + (int64_t) (((requested_percentile / 100) * h->total_count) + 0.5); + count_at_percentile = count_at_percentile > 1 ? count_at_percentile : 1; + int64_t total = 0; + + while (hdr_iter_next(&iter)) + { + total += iter.count; + + if (total >= count_at_percentile) + { + int64_t value_from_index = iter.value; + return highest_equivalent_value(h, value_from_index); + } + } + + 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; + + iter->value = hdr_value_at_index(iter->h, iter->counts_index); + iter->highest_equivalent_value = highest_equivalent_value(iter->h, iter->value); + iter->lowest_equivalent_value = lowest_equivalent_value(iter->h, iter->value); + iter->median_equivalent_value = hdr_median_equivalent_value(iter->h, iter->value); + + 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)) + { + 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) +{ + 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; + int64_t temp = (int64_t)(log(100 / (100.0 - (percentiles->percentile_to_iterate_to))) / log(2)) + 1; + int64_t half_distance = (int64_t) pow(2, (double) temp); + int64_t 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; +} + +// ## ####### ###### ### ######## #### ######## ## ## ## ## #### ###### +// ## ## ## ## ## ## ## ## ## ## ## ## ## ### ### ## ## ## +// ## ## ## ## ## ## ## ## ## ## ## ## #### #### ## ## +// ## ## ## ## #### ## ## ######## ## ## ######### ## ### ## ## ## +// ## ## ## ## ## ######### ## ## ## ## ## ## ## ## ## ## +// ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## +// ######## ####### ###### ## ## ## ## #### ## ## ## ## ## #### ###### + +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: + return "%12s %12s %12s %12s\n\n"; + 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]; + format_line_string(line_format, 25, h->significant_figures, format); + const char* head_format = format_head_string(format); + int rc = 0; + + struct hdr_iter iter; + 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; + } + + struct hdr_iter_percentiles * 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/contrib/libs/hdr_histogram/src/hdr_histogram.h b/contrib/libs/hdr_histogram/src/hdr_histogram.h index c4ba1a43f9..3d124e8fe9 100644 --- a/contrib/libs/hdr_histogram/src/hdr_histogram.h +++ b/contrib/libs/hdr_histogram/src/hdr_histogram.h @@ -1,428 +1,428 @@ -/** - * 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_trackable_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[0]; -}; - -#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 is allocated in a single contigious block so can be delete via free, - * without any structure specific destructor. - * - * @param lowest_trackable_value The smallest possible value to be put into the - * histogram. - * @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_trackable_value is < 1 or the - * significant_figure value is outside of the allowed range, ENOMEM if malloc - * failed. - */ -int hdr_init( - int64_t lowest_trackable_value, - int64_t highest_trackable_value, - int significant_figures, - struct hdr_histogram** result); - -/** - * 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 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); - - -/** - * 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 contruction 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 occured 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 expexcted_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); - -/** - * 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_trackable_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_trackable_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); - -/** - * 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 */ - int32_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); - -/** - * 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_trackable_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_trackable_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 manuallying 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 +/** + * 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_trackable_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[0]; +}; + +#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 is allocated in a single contigious block so can be delete via free, + * without any structure specific destructor. + * + * @param lowest_trackable_value The smallest possible value to be put into the + * histogram. + * @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_trackable_value is < 1 or the + * significant_figure value is outside of the allowed range, ENOMEM if malloc + * failed. + */ +int hdr_init( + int64_t lowest_trackable_value, + int64_t highest_trackable_value, + int significant_figures, + struct hdr_histogram** result); + +/** + * 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 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); + + +/** + * 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 contruction 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 occured 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 expexcted_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); + +/** + * 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_trackable_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_trackable_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); + +/** + * 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 */ + int32_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); + +/** + * 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_trackable_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_trackable_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 manuallying 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/contrib/libs/hdr_histogram/src/hdr_interval_recorder.c b/contrib/libs/hdr_histogram/src/hdr_interval_recorder.c index 2b0ba87cae..2c4f955193 100644 --- a/contrib/libs/hdr_histogram/src/hdr_interval_recorder.c +++ b/contrib/libs/hdr_histogram/src/hdr_interval_recorder.c @@ -1,53 +1,53 @@ -/** - * hdr_interval_recorder.h - * Written by Michael Barker and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - */ - -#include "hdr_atomic.h" -#include "hdr_interval_recorder.h" - -int hdr_interval_recorder_init(struct hdr_interval_recorder* r) -{ - return hdr_writer_reader_phaser_init(&r->phaser); -} - -void hdr_interval_recorder_destroy(struct hdr_interval_recorder* r) -{ - hdr_writer_reader_phaser_destory(&r->phaser); -} - -void hdr_interval_recorder_update( - struct hdr_interval_recorder* r, - void(*update_action)(void*, void*), - void* arg) -{ - int64_t val = hdr_phaser_writer_enter(&r->phaser); - - void* active = hdr_atomic_load_pointer(&r->active); - - update_action(active, arg); - - hdr_phaser_writer_exit(&r->phaser, val); -} - -void* hdr_interval_recorder_sample(struct hdr_interval_recorder* r) -{ - void* temp; - - hdr_phaser_reader_lock(&r->phaser); - - temp = r->inactive; - - // volatile read - r->inactive = hdr_atomic_load_pointer(&r->active); - - // volatile write - hdr_atomic_store_pointer(&r->active, temp); - - hdr_phaser_flip_phase(&r->phaser, 0); - - hdr_phaser_reader_unlock(&r->phaser); - - return r->inactive; -} +/** + * hdr_interval_recorder.h + * Written by Michael Barker and released to the public domain, + * as explained at http://creativecommons.org/publicdomain/zero/1.0/ + */ + +#include "hdr_atomic.h" +#include "hdr_interval_recorder.h" + +int hdr_interval_recorder_init(struct hdr_interval_recorder* r) +{ + return hdr_writer_reader_phaser_init(&r->phaser); +} + +void hdr_interval_recorder_destroy(struct hdr_interval_recorder* r) +{ + hdr_writer_reader_phaser_destory(&r->phaser); +} + +void hdr_interval_recorder_update( + struct hdr_interval_recorder* r, + void(*update_action)(void*, void*), + void* arg) +{ + int64_t val = hdr_phaser_writer_enter(&r->phaser); + + void* active = hdr_atomic_load_pointer(&r->active); + + update_action(active, arg); + + hdr_phaser_writer_exit(&r->phaser, val); +} + +void* hdr_interval_recorder_sample(struct hdr_interval_recorder* r) +{ + void* temp; + + hdr_phaser_reader_lock(&r->phaser); + + temp = r->inactive; + + // volatile read + r->inactive = hdr_atomic_load_pointer(&r->active); + + // volatile write + hdr_atomic_store_pointer(&r->active, temp); + + hdr_phaser_flip_phase(&r->phaser, 0); + + hdr_phaser_reader_unlock(&r->phaser); + + return r->inactive; +} diff --git a/contrib/libs/hdr_histogram/src/hdr_interval_recorder.h b/contrib/libs/hdr_histogram/src/hdr_interval_recorder.h index e363c23c66..3774e4e427 100644 --- a/contrib/libs/hdr_histogram/src/hdr_interval_recorder.h +++ b/contrib/libs/hdr_histogram/src/hdr_interval_recorder.h @@ -1,40 +1,40 @@ -/** - * hdr_interval_recorder.h - * Written by Michael Barker and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - */ - -#ifndef HDR_INTERVAL_RECORDER_H -#define HDR_INTERVAL_RECORDER_H 1 - -#include "hdr_writer_reader_phaser.h" - -HDR_ALIGN_PREFIX(8) -struct hdr_interval_recorder -{ - void* active; - void* inactive; - struct hdr_writer_reader_phaser phaser; +/** + * hdr_interval_recorder.h + * Written by Michael Barker and released to the public domain, + * as explained at http://creativecommons.org/publicdomain/zero/1.0/ + */ + +#ifndef HDR_INTERVAL_RECORDER_H +#define HDR_INTERVAL_RECORDER_H 1 + +#include "hdr_writer_reader_phaser.h" + +HDR_ALIGN_PREFIX(8) +struct hdr_interval_recorder +{ + void* active; + void* inactive; + struct hdr_writer_reader_phaser phaser; +} +HDR_ALIGN_SUFFIX(8); + +#ifdef __cplusplus +extern "C" { +#endif + +int hdr_interval_recorder_init(struct hdr_interval_recorder* r); + +void hdr_interval_recorder_destroy(struct hdr_interval_recorder* r); + +void hdr_interval_recorder_update( + struct hdr_interval_recorder* r, + void(*update_action)(void*, void*), + void* arg); + +void* hdr_interval_recorder_sample(struct hdr_interval_recorder* r); + +#ifdef __cplusplus } -HDR_ALIGN_SUFFIX(8); - -#ifdef __cplusplus -extern "C" { -#endif - -int hdr_interval_recorder_init(struct hdr_interval_recorder* r); - -void hdr_interval_recorder_destroy(struct hdr_interval_recorder* r); - -void hdr_interval_recorder_update( - struct hdr_interval_recorder* r, - void(*update_action)(void*, void*), - void* arg); - -void* hdr_interval_recorder_sample(struct hdr_interval_recorder* r); - -#ifdef __cplusplus -} -#endif - -#endif +#endif + +#endif diff --git a/contrib/libs/hdr_histogram/src/hdr_tests.h b/contrib/libs/hdr_histogram/src/hdr_tests.h index c016d3a6de..34f67c9a64 100644 --- a/contrib/libs/hdr_histogram/src/hdr_tests.h +++ b/contrib/libs/hdr_histogram/src/hdr_tests.h @@ -1,22 +1,22 @@ -#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 +#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 diff --git a/contrib/libs/hdr_histogram/src/hdr_thread.c b/contrib/libs/hdr_histogram/src/hdr_thread.c index 721780edb9..a38e64f2ad 100644 --- a/contrib/libs/hdr_histogram/src/hdr_thread.c +++ b/contrib/libs/hdr_histogram/src/hdr_thread.c @@ -1,102 +1,102 @@ -/** -* hdr_thread.c -* Written by Philip Orwig and released to the public domain, -* as explained at http://creativecommons.org/publicdomain/zero/1.0/ -*/ - -#include <stdlib.h> -#include "hdr_thread.h" - -struct hdr_mutex* hdr_mutex_alloc(void) -{ - return malloc(sizeof(hdr_mutex)); -} - -void hdr_mutex_free(struct hdr_mutex* mutex) -{ - free(mutex); -} - -#if defined(_WIN32) || defined(_WIN64) || defined(__CYGWIN__) - -#if !defined(WIN32_LEAN_AND_MEAN) -#define WIN32_LEAN_AND_MEAN -#endif - -#include <windows.h> -#include <WinSock2.h> - -int hdr_mutex_init(struct hdr_mutex* mutex) -{ - InitializeCriticalSection((CRITICAL_SECTION*)(mutex->_critical_section)); - return 0; -} - -void hdr_mutex_destroy(struct hdr_mutex* mutex) -{ - DeleteCriticalSection((CRITICAL_SECTION*)(mutex->_critical_section)); -} - -void hdr_mutex_lock(struct hdr_mutex* mutex) -{ - EnterCriticalSection((CRITICAL_SECTION*)(mutex->_critical_section)); -} - -void hdr_mutex_unlock(struct hdr_mutex* mutex) -{ - LeaveCriticalSection((CRITICAL_SECTION*)(mutex->_critical_section)); -} - -void hdr_yield() -{ - Sleep(0); -} - -int hdr_usleep(unsigned int useconds) -{ - struct timeval tv; - - tv.tv_sec = (long)useconds / 1000000; - tv.tv_usec = useconds % 1000000; - select(0, NULL, NULL, NULL, &tv); - - return 0; -} - - -#else -#include <pthread.h> -#include <unistd.h> - -int hdr_mutex_init(struct hdr_mutex* mutex) -{ - return pthread_mutex_init(&mutex->_mutex, NULL); -} - -void hdr_mutex_destroy(struct hdr_mutex* mutex) -{ - pthread_mutex_destroy(&mutex->_mutex); -} - -void hdr_mutex_lock(struct hdr_mutex* mutex) -{ - pthread_mutex_lock(&mutex->_mutex); -} - -void hdr_mutex_unlock(struct hdr_mutex* mutex) -{ - pthread_mutex_unlock(&mutex->_mutex); -} - -void hdr_yield() -{ - sched_yield(); -} - -int hdr_usleep(unsigned int useconds) -{ - return usleep(useconds); -} - - -#endif +/** +* hdr_thread.c +* Written by Philip Orwig and released to the public domain, +* as explained at http://creativecommons.org/publicdomain/zero/1.0/ +*/ + +#include <stdlib.h> +#include "hdr_thread.h" + +struct hdr_mutex* hdr_mutex_alloc(void) +{ + return malloc(sizeof(hdr_mutex)); +} + +void hdr_mutex_free(struct hdr_mutex* mutex) +{ + free(mutex); +} + +#if defined(_WIN32) || defined(_WIN64) || defined(__CYGWIN__) + +#if !defined(WIN32_LEAN_AND_MEAN) +#define WIN32_LEAN_AND_MEAN +#endif + +#include <windows.h> +#include <WinSock2.h> + +int hdr_mutex_init(struct hdr_mutex* mutex) +{ + InitializeCriticalSection((CRITICAL_SECTION*)(mutex->_critical_section)); + return 0; +} + +void hdr_mutex_destroy(struct hdr_mutex* mutex) +{ + DeleteCriticalSection((CRITICAL_SECTION*)(mutex->_critical_section)); +} + +void hdr_mutex_lock(struct hdr_mutex* mutex) +{ + EnterCriticalSection((CRITICAL_SECTION*)(mutex->_critical_section)); +} + +void hdr_mutex_unlock(struct hdr_mutex* mutex) +{ + LeaveCriticalSection((CRITICAL_SECTION*)(mutex->_critical_section)); +} + +void hdr_yield() +{ + Sleep(0); +} + +int hdr_usleep(unsigned int useconds) +{ + struct timeval tv; + + tv.tv_sec = (long)useconds / 1000000; + tv.tv_usec = useconds % 1000000; + select(0, NULL, NULL, NULL, &tv); + + return 0; +} + + +#else +#include <pthread.h> +#include <unistd.h> + +int hdr_mutex_init(struct hdr_mutex* mutex) +{ + return pthread_mutex_init(&mutex->_mutex, NULL); +} + +void hdr_mutex_destroy(struct hdr_mutex* mutex) +{ + pthread_mutex_destroy(&mutex->_mutex); +} + +void hdr_mutex_lock(struct hdr_mutex* mutex) +{ + pthread_mutex_lock(&mutex->_mutex); +} + +void hdr_mutex_unlock(struct hdr_mutex* mutex) +{ + pthread_mutex_unlock(&mutex->_mutex); +} + +void hdr_yield() +{ + sched_yield(); +} + +int hdr_usleep(unsigned int useconds) +{ + return usleep(useconds); +} + + +#endif diff --git a/contrib/libs/hdr_histogram/src/hdr_thread.h b/contrib/libs/hdr_histogram/src/hdr_thread.h index a7d77c02b7..da51b70507 100644 --- a/contrib/libs/hdr_histogram/src/hdr_thread.h +++ b/contrib/libs/hdr_histogram/src/hdr_thread.h @@ -1,55 +1,55 @@ -/** - * hdr_thread.h - * Written by Philip Orwig and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - */ - -#ifndef HDR_THREAD_H__ -#define HDR_THREAD_H__ - -#include <stdint.h> - -#if defined(_WIN32) || defined(_WIN64) || defined(__CYGWIN__) - - -#define HDR_ALIGN_PREFIX(alignment) __declspec( align(alignment) ) -#define HDR_ALIGN_SUFFIX(alignment) - -typedef struct hdr_mutex -{ - uint8_t _critical_section[40]; -} hdr_mutex; - -#else - -#include <pthread.h> - -#define HDR_ALIGN_PREFIX(alignment) -#define HDR_ALIGN_SUFFIX(alignment) __attribute__((aligned(alignment))) - -typedef struct hdr_mutex -{ - pthread_mutex_t _mutex; -} hdr_mutex; -#endif - -#ifdef __cplusplus -extern "C" { -#endif - -struct hdr_mutex* hdr_mutex_alloc(void); -void hdr_mutex_free(struct hdr_mutex*); - -int hdr_mutex_init(struct hdr_mutex* mutex); -void hdr_mutex_destroy(struct hdr_mutex* mutex); - -void hdr_mutex_lock(struct hdr_mutex* mutex); -void hdr_mutex_unlock(struct hdr_mutex* mutex); - -void hdr_yield(); -int hdr_usleep(unsigned int useconds); - -#ifdef __cplusplus -} -#endif -#endif +/** + * hdr_thread.h + * Written by Philip Orwig and released to the public domain, + * as explained at http://creativecommons.org/publicdomain/zero/1.0/ + */ + +#ifndef HDR_THREAD_H__ +#define HDR_THREAD_H__ + +#include <stdint.h> + +#if defined(_WIN32) || defined(_WIN64) || defined(__CYGWIN__) + + +#define HDR_ALIGN_PREFIX(alignment) __declspec( align(alignment) ) +#define HDR_ALIGN_SUFFIX(alignment) + +typedef struct hdr_mutex +{ + uint8_t _critical_section[40]; +} hdr_mutex; + +#else + +#include <pthread.h> + +#define HDR_ALIGN_PREFIX(alignment) +#define HDR_ALIGN_SUFFIX(alignment) __attribute__((aligned(alignment))) + +typedef struct hdr_mutex +{ + pthread_mutex_t _mutex; +} hdr_mutex; +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +struct hdr_mutex* hdr_mutex_alloc(void); +void hdr_mutex_free(struct hdr_mutex*); + +int hdr_mutex_init(struct hdr_mutex* mutex); +void hdr_mutex_destroy(struct hdr_mutex* mutex); + +void hdr_mutex_lock(struct hdr_mutex* mutex); +void hdr_mutex_unlock(struct hdr_mutex* mutex); + +void hdr_yield(); +int hdr_usleep(unsigned int useconds); + +#ifdef __cplusplus +} +#endif +#endif diff --git a/contrib/libs/hdr_histogram/src/hdr_time.c b/contrib/libs/hdr_histogram/src/hdr_time.c index 44742076ad..584e1142a0 100644 --- a/contrib/libs/hdr_histogram/src/hdr_time.c +++ b/contrib/libs/hdr_histogram/src/hdr_time.c @@ -1,70 +1,70 @@ -/** -* hdr_time.h -* Written by Michael Barker and Philip Orwig and released to the public domain, -* as explained at http://creativecommons.org/publicdomain/zero/1.0/ -*/ - -#include "hdr_time.h" - -#if defined(_WIN32) || defined(_WIN64) - -#if !defined(WIN32_LEAN_AND_MEAN) -#define WIN32_LEAN_AND_MEAN -#endif - -#include <windows.h> - -static int s_clockPeriodSet = 0; -static double s_clockPeriod = 1.0; - -void hdr_gettime(hdr_timespec* t) -{ - LARGE_INTEGER num; - /* if this is distasteful, we can add in an hdr_time_init() */ - if (!s_clockPeriodSet) - { - QueryPerformanceFrequency(&num); - s_clockPeriod = 1.0 / (double) num.QuadPart; - s_clockPeriodSet = 1; - } - - QueryPerformanceCounter(&num); - double seconds = num.QuadPart * s_clockPeriod; - double integral; - double remainder = modf(seconds, &integral); - - t->tv_sec = (long) integral; - t->tv_nsec = (long) (remainder * 1000000000); -} - -#elif defined(__APPLE__) - -#include <mach/clock.h> -#include <mach/mach.h> - - -void hdr_gettime(hdr_timespec* ts) -{ - clock_serv_t cclock; - mach_timespec_t mts; - host_get_clock_service(mach_host_self(), CALENDAR_CLOCK, &cclock); - clock_get_time(cclock, &mts); - mach_port_deallocate(mach_task_self(), cclock); - ts->tv_sec = mts.tv_sec; - ts->tv_nsec = mts.tv_nsec; -} - -#elif defined(__linux__) || defined(__CYGWIN__) - - -void hdr_gettime(hdr_timespec* t) -{ - clock_gettime(CLOCK_MONOTONIC, (struct timespec*)t); -} - -#else - -#warning "Platform not supported\n" - -#endif - +/** +* hdr_time.h +* Written by Michael Barker and Philip Orwig and released to the public domain, +* as explained at http://creativecommons.org/publicdomain/zero/1.0/ +*/ + +#include "hdr_time.h" + +#if defined(_WIN32) || defined(_WIN64) + +#if !defined(WIN32_LEAN_AND_MEAN) +#define WIN32_LEAN_AND_MEAN +#endif + +#include <windows.h> + +static int s_clockPeriodSet = 0; +static double s_clockPeriod = 1.0; + +void hdr_gettime(hdr_timespec* t) +{ + LARGE_INTEGER num; + /* if this is distasteful, we can add in an hdr_time_init() */ + if (!s_clockPeriodSet) + { + QueryPerformanceFrequency(&num); + s_clockPeriod = 1.0 / (double) num.QuadPart; + s_clockPeriodSet = 1; + } + + QueryPerformanceCounter(&num); + double seconds = num.QuadPart * s_clockPeriod; + double integral; + double remainder = modf(seconds, &integral); + + t->tv_sec = (long) integral; + t->tv_nsec = (long) (remainder * 1000000000); +} + +#elif defined(__APPLE__) + +#include <mach/clock.h> +#include <mach/mach.h> + + +void hdr_gettime(hdr_timespec* ts) +{ + clock_serv_t cclock; + mach_timespec_t mts; + host_get_clock_service(mach_host_self(), CALENDAR_CLOCK, &cclock); + clock_get_time(cclock, &mts); + mach_port_deallocate(mach_task_self(), cclock); + ts->tv_sec = mts.tv_sec; + ts->tv_nsec = mts.tv_nsec; +} + +#elif defined(__linux__) || defined(__CYGWIN__) + + +void hdr_gettime(hdr_timespec* t) +{ + clock_gettime(CLOCK_MONOTONIC, (struct timespec*)t); +} + +#else + +#warning "Platform not supported\n" + +#endif + diff --git a/contrib/libs/hdr_histogram/src/hdr_time.h b/contrib/libs/hdr_histogram/src/hdr_time.h index 8b1a71ec8a..829599c394 100644 --- a/contrib/libs/hdr_histogram/src/hdr_time.h +++ b/contrib/libs/hdr_histogram/src/hdr_time.h @@ -1,42 +1,42 @@ -/** - * hdr_time.h - * Written by Michael Barker and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - */ - -#ifndef HDR_TIME_H__ -#define HDR_TIME_H__ - -#include <math.h> -#include <time.h> - -#if defined(_WIN32) || defined(_WIN64) || defined(__CYGWIN__) - -typedef struct hdr_timespec -{ - long tv_sec; - long tv_nsec; -} hdr_timespec; - -#else - -typedef struct timespec hdr_timespec; - -#endif - -#ifdef __cplusplus -extern "C" { -#endif - -#if defined(_MSC_VER) -void hdr_gettime(hdr_timespec* t); -#else -void hdr_gettime(hdr_timespec* t); -#endif - -#ifdef __cplusplus -} -#endif - -#endif - +/** + * hdr_time.h + * Written by Michael Barker and released to the public domain, + * as explained at http://creativecommons.org/publicdomain/zero/1.0/ + */ + +#ifndef HDR_TIME_H__ +#define HDR_TIME_H__ + +#include <math.h> +#include <time.h> + +#if defined(_WIN32) || defined(_WIN64) || defined(__CYGWIN__) + +typedef struct hdr_timespec +{ + long tv_sec; + long tv_nsec; +} hdr_timespec; + +#else + +typedef struct timespec hdr_timespec; + +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +#if defined(_MSC_VER) +void hdr_gettime(hdr_timespec* t); +#else +void hdr_gettime(hdr_timespec* t); +#endif + +#ifdef __cplusplus +} +#endif + +#endif + diff --git a/contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.c b/contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.c index 21d3adeeaa..1d3eda8f54 100644 --- a/contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.c +++ b/contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.c @@ -1,135 +1,135 @@ -/** - * hdr_writer_reader_phaser.h - * Written by Michael Barker and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - */ - -#include <stdint.h> -#include <stdbool.h> -#include <errno.h> - -#include "hdr_atomic.h" -#include "hdr_thread.h" - -#include "hdr_writer_reader_phaser.h" - -static int64_t _hdr_phaser_get_epoch(int64_t* field) -{ - return hdr_atomic_load_64(field); -} - -static void _hdr_phaser_set_epoch(int64_t* field, int64_t val) -{ - hdr_atomic_store_64(field, val); -} - -static int64_t _hdr_phaser_reset_epoch(int64_t* field, int64_t initial_value) -{ - return hdr_atomic_exchange_64(field, initial_value); -} - -int hdr_writer_reader_phaser_init(struct hdr_writer_reader_phaser* p) -{ - if (NULL == p) - { - return EINVAL; - } - - p->start_epoch = 0; - p->even_end_epoch = 0; - p->odd_end_epoch = INT64_MIN; - p->reader_mutex = hdr_mutex_alloc(); - - if (!p->reader_mutex) - { - return ENOMEM; - } - - int rc = hdr_mutex_init(p->reader_mutex); - if (0 != rc) - { - return rc; - } - - // TODO: Should I fence here. - - return 0; -} - -void hdr_writer_reader_phaser_destory(struct hdr_writer_reader_phaser* p) -{ - hdr_mutex_destroy(p->reader_mutex); -} - -int64_t hdr_phaser_writer_enter(struct hdr_writer_reader_phaser* p) -{ - return hdr_atomic_add_fetch_64(&p->start_epoch, 1); -} - -void hdr_phaser_writer_exit( - struct hdr_writer_reader_phaser* p, int64_t critical_value_at_enter) -{ - int64_t* end_epoch = - (critical_value_at_enter < 0) ? &p->odd_end_epoch : &p->even_end_epoch; - hdr_atomic_add_fetch_64(end_epoch, 1); -} - -void hdr_phaser_reader_lock(struct hdr_writer_reader_phaser* p) -{ - hdr_mutex_lock(p->reader_mutex); -} - -void hdr_phaser_reader_unlock(struct hdr_writer_reader_phaser* p) -{ - hdr_mutex_unlock(p->reader_mutex); -} - -void hdr_phaser_flip_phase( - struct hdr_writer_reader_phaser* p, int64_t sleep_time_ns) -{ - // TODO: is_held_by_current_thread - unsigned int sleep_time_us = sleep_time_ns < 1000000000 ? (unsigned int) (sleep_time_ns / 1000) : 1000000; - - int64_t start_epoch = _hdr_phaser_get_epoch(&p->start_epoch); - - bool next_phase_is_even = (start_epoch < 0); - - // Clear currently used phase end epoch. - int64_t initial_start_value; - if (next_phase_is_even) - { - initial_start_value = 0; - _hdr_phaser_set_epoch(&p->even_end_epoch, initial_start_value); - } - else - { - initial_start_value = INT64_MIN; - _hdr_phaser_set_epoch(&p->odd_end_epoch, initial_start_value); - } - - // Reset start value, indicating new phase. - int64_t start_value_at_flip = - _hdr_phaser_reset_epoch(&p->start_epoch, initial_start_value); - - bool caught_up = false; - do - { - int64_t* end_epoch = - next_phase_is_even ? &p->odd_end_epoch : &p->even_end_epoch; - - caught_up = _hdr_phaser_get_epoch(end_epoch) == start_value_at_flip; - - if (!caught_up) - { - if (sleep_time_us <= 0) - { - hdr_yield(); - } - else - { - hdr_usleep(sleep_time_us); - } - } - } - while (!caught_up); -} +/** + * hdr_writer_reader_phaser.h + * Written by Michael Barker and released to the public domain, + * as explained at http://creativecommons.org/publicdomain/zero/1.0/ + */ + +#include <stdint.h> +#include <stdbool.h> +#include <errno.h> + +#include "hdr_atomic.h" +#include "hdr_thread.h" + +#include "hdr_writer_reader_phaser.h" + +static int64_t _hdr_phaser_get_epoch(int64_t* field) +{ + return hdr_atomic_load_64(field); +} + +static void _hdr_phaser_set_epoch(int64_t* field, int64_t val) +{ + hdr_atomic_store_64(field, val); +} + +static int64_t _hdr_phaser_reset_epoch(int64_t* field, int64_t initial_value) +{ + return hdr_atomic_exchange_64(field, initial_value); +} + +int hdr_writer_reader_phaser_init(struct hdr_writer_reader_phaser* p) +{ + if (NULL == p) + { + return EINVAL; + } + + p->start_epoch = 0; + p->even_end_epoch = 0; + p->odd_end_epoch = INT64_MIN; + p->reader_mutex = hdr_mutex_alloc(); + + if (!p->reader_mutex) + { + return ENOMEM; + } + + int rc = hdr_mutex_init(p->reader_mutex); + if (0 != rc) + { + return rc; + } + + // TODO: Should I fence here. + + return 0; +} + +void hdr_writer_reader_phaser_destory(struct hdr_writer_reader_phaser* p) +{ + hdr_mutex_destroy(p->reader_mutex); +} + +int64_t hdr_phaser_writer_enter(struct hdr_writer_reader_phaser* p) +{ + return hdr_atomic_add_fetch_64(&p->start_epoch, 1); +} + +void hdr_phaser_writer_exit( + struct hdr_writer_reader_phaser* p, int64_t critical_value_at_enter) +{ + int64_t* end_epoch = + (critical_value_at_enter < 0) ? &p->odd_end_epoch : &p->even_end_epoch; + hdr_atomic_add_fetch_64(end_epoch, 1); +} + +void hdr_phaser_reader_lock(struct hdr_writer_reader_phaser* p) +{ + hdr_mutex_lock(p->reader_mutex); +} + +void hdr_phaser_reader_unlock(struct hdr_writer_reader_phaser* p) +{ + hdr_mutex_unlock(p->reader_mutex); +} + +void hdr_phaser_flip_phase( + struct hdr_writer_reader_phaser* p, int64_t sleep_time_ns) +{ + // TODO: is_held_by_current_thread + unsigned int sleep_time_us = sleep_time_ns < 1000000000 ? (unsigned int) (sleep_time_ns / 1000) : 1000000; + + int64_t start_epoch = _hdr_phaser_get_epoch(&p->start_epoch); + + bool next_phase_is_even = (start_epoch < 0); + + // Clear currently used phase end epoch. + int64_t initial_start_value; + if (next_phase_is_even) + { + initial_start_value = 0; + _hdr_phaser_set_epoch(&p->even_end_epoch, initial_start_value); + } + else + { + initial_start_value = INT64_MIN; + _hdr_phaser_set_epoch(&p->odd_end_epoch, initial_start_value); + } + + // Reset start value, indicating new phase. + int64_t start_value_at_flip = + _hdr_phaser_reset_epoch(&p->start_epoch, initial_start_value); + + bool caught_up = false; + do + { + int64_t* end_epoch = + next_phase_is_even ? &p->odd_end_epoch : &p->even_end_epoch; + + caught_up = _hdr_phaser_get_epoch(end_epoch) == start_value_at_flip; + + if (!caught_up) + { + if (sleep_time_us <= 0) + { + hdr_yield(); + } + else + { + hdr_usleep(sleep_time_us); + } + } + } + while (!caught_up); +} diff --git a/contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.h b/contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.h index f14a7db6e7..3ee0a57ba4 100644 --- a/contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.h +++ b/contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.h @@ -1,51 +1,51 @@ -/** - * hdr_writer_reader_phaser.h - * Written by Michael Barker and released to the public domain, - * as explained at http://creativecommons.org/publicdomain/zero/1.0/ - */ - -#ifndef HDR_WRITER_READER_PHASER_H -#define HDR_WRITER_READER_PHASER_H 1 - -#include <stdlib.h> -#include <stdbool.h> -#include <stdlib.h> -#include <errno.h> - -#include "hdr_thread.h" - -HDR_ALIGN_PREFIX(8) -struct hdr_writer_reader_phaser -{ - int64_t start_epoch; - int64_t even_end_epoch; - int64_t odd_end_epoch; - hdr_mutex* reader_mutex; +/** + * hdr_writer_reader_phaser.h + * Written by Michael Barker and released to the public domain, + * as explained at http://creativecommons.org/publicdomain/zero/1.0/ + */ + +#ifndef HDR_WRITER_READER_PHASER_H +#define HDR_WRITER_READER_PHASER_H 1 + +#include <stdlib.h> +#include <stdbool.h> +#include <stdlib.h> +#include <errno.h> + +#include "hdr_thread.h" + +HDR_ALIGN_PREFIX(8) +struct hdr_writer_reader_phaser +{ + int64_t start_epoch; + int64_t even_end_epoch; + int64_t odd_end_epoch; + hdr_mutex* reader_mutex; +} +HDR_ALIGN_SUFFIX(8); + +#ifdef __cplusplus +extern "C" { +#endif + + int hdr_writer_reader_phaser_init(struct hdr_writer_reader_phaser* p); + + void hdr_writer_reader_phaser_destory(struct hdr_writer_reader_phaser* p); + + int64_t hdr_phaser_writer_enter(struct hdr_writer_reader_phaser* p); + + void hdr_phaser_writer_exit( + struct hdr_writer_reader_phaser* p, int64_t critical_value_at_enter); + + void hdr_phaser_reader_lock(struct hdr_writer_reader_phaser* p); + + void hdr_phaser_reader_unlock(struct hdr_writer_reader_phaser* p); + + void hdr_phaser_flip_phase( + struct hdr_writer_reader_phaser* p, int64_t sleep_time_ns); + +#ifdef __cplusplus } -HDR_ALIGN_SUFFIX(8); - -#ifdef __cplusplus -extern "C" { -#endif - - int hdr_writer_reader_phaser_init(struct hdr_writer_reader_phaser* p); - - void hdr_writer_reader_phaser_destory(struct hdr_writer_reader_phaser* p); - - int64_t hdr_phaser_writer_enter(struct hdr_writer_reader_phaser* p); - - void hdr_phaser_writer_exit( - struct hdr_writer_reader_phaser* p, int64_t critical_value_at_enter); - - void hdr_phaser_reader_lock(struct hdr_writer_reader_phaser* p); - - void hdr_phaser_reader_unlock(struct hdr_writer_reader_phaser* p); - - void hdr_phaser_flip_phase( - struct hdr_writer_reader_phaser* p, int64_t sleep_time_ns); - -#ifdef __cplusplus -} -#endif - -#endif +#endif + +#endif diff --git a/contrib/libs/hdr_histogram/ya.make b/contrib/libs/hdr_histogram/ya.make index b20d977b57..c2d1cc92c9 100644 --- a/contrib/libs/hdr_histogram/ya.make +++ b/contrib/libs/hdr_histogram/ya.make @@ -1,5 +1,5 @@ -LIBRARY() - +LIBRARY() + LICENSE( BSD-2-Clause AND CC0-1.0 @@ -9,31 +9,31 @@ LICENSE_TEXTS(.yandex_meta/licenses.list.txt) VERSION(0.9.5) -OWNER( - jamel +OWNER( + jamel g:contrib g:cpp-contrib -) - -NO_UTIL() - -NO_COMPILER_WARNINGS() +) + +NO_UTIL() +NO_COMPILER_WARNINGS() + ADDINCL( contrib/libs/hdr_histogram/src ) - -SRCS( - src/hdr_encoding.c - src/hdr_interval_recorder.c - src/hdr_histogram.c - src/hdr_writer_reader_phaser.c - src/hdr_time.c - src/hdr_thread.c -) - -PEERDIR( - contrib/libs/zlib -) - -END() + +SRCS( + src/hdr_encoding.c + src/hdr_interval_recorder.c + src/hdr_histogram.c + src/hdr_writer_reader_phaser.c + src/hdr_time.c + src/hdr_thread.c +) + +PEERDIR( + contrib/libs/zlib +) + +END() |