aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/hdr_histogram
diff options
context:
space:
mode:
authorSergey Polovko <sergey@polovko.me>2022-02-10 16:47:03 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:47:03 +0300
commit2e714b5ebd40a1f4cc31c27f1ad6e49ca6d895f5 (patch)
treeb83306b6e37edeea782e9eed673d89286c4fef35 /contrib/libs/hdr_histogram
parent3e0b762a82514bac89c1dd6ea7211e381d8aa248 (diff)
downloadydb-2e714b5ebd40a1f4cc31c27f1ad6e49ca6d895f5.tar.gz
Restoring authorship annotation for Sergey Polovko <sergey@polovko.me>. Commit 2 of 2.
Diffstat (limited to 'contrib/libs/hdr_histogram')
-rw-r--r--contrib/libs/hdr_histogram/COPYING.txt242
-rw-r--r--contrib/libs/hdr_histogram/LICENSE.txt82
-rw-r--r--contrib/libs/hdr_histogram/README.md158
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_atomic.h116
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_encoding.c626
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_encoding.h154
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_endian.h232
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_histogram.c2020
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_histogram.h856
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_interval_recorder.c106
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_interval_recorder.h78
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_tests.h44
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_thread.c204
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_thread.h110
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_time.c140
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_time.h84
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.c270
-rw-r--r--contrib/libs/hdr_histogram/src/hdr_writer_reader_phaser.h100
-rw-r--r--contrib/libs/hdr_histogram/ya.make48
19 files changed, 2835 insertions, 2835 deletions
diff --git a/contrib/libs/hdr_histogram/COPYING.txt b/contrib/libs/hdr_histogram/COPYING.txt
index 32ae9cf3ff..0e259d42c9 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 bda854f683..9b4e66ed7d 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 dbb56a7ae0..b669c3fe95 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
-----------------------------------------------
-[![Gitter](https://badges.gitter.im/Join Chat.svg)](https://gitter.im/HdrHistogram/HdrHistogram?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge&utm_content=badge)
-
-Windows Build: ![AppVeyor](https://ci.appveyor.com/api/projects/status/github/HdrHistogram/HdrHistogram_c)
-
-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
+----------------------------------------------
+[![Gitter](https://badges.gitter.im/Join Chat.svg)](https://gitter.im/HdrHistogram/HdrHistogram?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge&utm_content=badge)
+
+Windows Build: ![AppVeyor](https://ci.appveyor.com/api/projects/status/github/HdrHistogram/HdrHistogram_c)
+
+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 4c44aa350a..7015d985da 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)
+/**
+ * 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)
{
- _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__ */
+ _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 43db22a3fa..758cf68ebb 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 dc9076d7bb..141093ba3b 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 a677e5a44a..839fdb16b1 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 044afe2a22..8cad5a0d61 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 3d124e8fe9..c4ba1a43f9 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 2c4f955193..2b0ba87cae 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 3774e4e427..e363c23c66 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_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_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;
}
-#endif
-
-#endif
+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
diff --git a/contrib/libs/hdr_histogram/src/hdr_tests.h b/contrib/libs/hdr_histogram/src/hdr_tests.h
index 34f67c9a64..c016d3a6de 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 a38e64f2ad..721780edb9 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 da51b70507..a7d77c02b7 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 584e1142a0..44742076ad 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 829599c394..8b1a71ec8a 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 1d3eda8f54..21d3adeeaa 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 3ee0a57ba4..f14a7db6e7 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_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_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;
}
-#endif
-
-#endif
+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
diff --git a/contrib/libs/hdr_histogram/ya.make b/contrib/libs/hdr_histogram/ya.make
index c2d1cc92c9..b20d977b57 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_UTIL()
+
+NO_COMPILER_WARNINGS()
-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()