libcircllhist
Data Structures | Macros | Typedefs | Functions
circllhist.h File Reference
#include <stdlib.h>
#include <sys/types.h>
#include <stdint.h>

Go to the source code of this file.

Data Structures

struct  hist_bucket
 
struct  hist_allocator
 

Macros

#define DEFAULT_HIST_SIZE   100
 
#define HIST_BUCKET_MAX_STRING_SIZE   9
 Maximal size of hist bucket standard string format (inc. terminator)
 
#define API_EXPORT(type)   extern type
 

Typedefs

typedef struct histogram histogram_t
 
typedef struct hist_rollup_config hist_rollup_config_t
 
typedef struct hist_bucket hist_bucket_t
 
typedef struct hist_allocator hist_allocator_t
 

Functions

double hist_bucket_to_double (hist_bucket_t hb)
 Returns the edge of the histogram bucket closer to zero.
 
double hist_bucket_midpoint (hist_bucket_t in)
 Calculate mid-point of the bucket.
 
double hist_bucket_to_double_bin_width (hist_bucket_t hb)
 Get the width of the hist_bucket.
 
hist_bucket_t double_to_hist_bucket (double d)
 Create the bucket that a value belongs to.
 
hist_bucket_t int_scale_to_hist_bucket (int64_t value, int scale)
 Create the bucket that value * 10^(scale) belongs to.
 
int hist_bucket_to_string (hist_bucket_t hb, char *buf)
 
histogram_t * hist_alloc (void)
 Create a new histogram, uses default allocator.
 
histogram_t * hist_alloc_nbins (int nbins)
 Create a new histogram with preallocated bins, uses default allocator.
 
histogram_t * hist_fast_alloc (void)
 Create a fast-histogram. More...
 
histogram_t * hist_fast_alloc_nbins (int nbins)
 Create a fast-histogram with preallocated bins, uses default allocator.
 
histogram_t * hist_clone (const histogram_t *other)
 Create an exact copy of other, uses default allocator.
 
histogram_t * hist_alloc_with_allocator (const hist_allocator_t *alloc)
 Create a new histogram, uses custom allocator.
 
histogram_t * hist_alloc_nbins_with_allocator (int nbins, const hist_allocator_t *alloc)
 Create a new histogram with preallocated bins, uses custom allocator.
 
histogram_t * hist_fast_alloc_with_allocator (const hist_allocator_t *alloc)
 Create a fast-histogram. More...
 
histogram_t * hist_fast_alloc_nbins_with_allocator (int nbins, const hist_allocator_t *alloc)
 Create a fast-histogram with preallocated bins, uses custom allocator.
 
histogram_t * hist_clone_with_allocator (const histogram_t *other, const hist_allocator_t *alloc)
 Create an exact copy of other, uses custom allocator.
 
void hist_free (histogram_t *hist)
 Free a (fast-) histogram, frees with allocator chosen during the alloc/clone.
 
uint64_t hist_insert (histogram_t *hist, double val, uint64_t count)
 insert a value into a histogram count times More...
 
uint64_t hist_remove (histogram_t *hist, double val, uint64_t count)
 Remove data from a histogram count times, returns the actual count removed protecting from underflow.
 
uint64_t hist_remove_raw (histogram_t *hist, hist_bucket_t hb, uint64_t count)
 Remove data from a histogram count times, returns the actual count removed protecting from underflow.
 
uint64_t hist_insert_raw (histogram_t *hist, hist_bucket_t hb, uint64_t count)
 
uint64_t hist_insert_raw_end (histogram_t *hist, hist_bucket_t hb, uint64_t count)
 
int hist_bucket_count (const histogram_t *hist)
 Get the number of used buckets in a histogram.
 
int hist_num_buckets (const histogram_t *hist)
 Same as hist_bucket_count.
 
uint64_t hist_sample_count (const histogram_t *hist)
 Get the total number of values stored in the histogram.
 
int hist_bucket_idx (const histogram_t *hist, int idx, double *v, uint64_t *c)
 Get value+count for bucket at position idx. Valid positions are 0 .. hist_bucket_count()
 
int hist_bucket_idx_bucket (const histogram_t *hist, int idx, hist_bucket_t *b, uint64_t *c)
 Get bucket+count for bucket at position idx. Valid positions are 0 .. hist_bucket_count()
 
int hist_accumulate (histogram_t *tgt, const histogram_t *const *src, int cnt)
 Accumulate bins from each of cnt histograms in src onto tgt.
 
int hist_subtract (histogram_t *tgt, const histogram_t *const *src, int cnt)
 Subtract bins from each of cnt histograms in src from tgt, return -1 on underrun error.
 
int hist_subtract_as_int64 (histogram_t *tgt, const histogram_t *src)
 Subtract bins in src from tgt treating the result count as signed, return -1 on overflow error.
 
int hist_add_as_int64 (histogram_t *tgt, const histogram_t *src)
 Add bins in src from tgt treating src counts as signed, return -1 on overflow error.
 
void hist_clear (histogram_t *hist)
 Clear data fast. Keeps buckets allocated.
 
uint64_t hist_insert_intscale (histogram_t *hist, int64_t val, int scale, uint64_t count)
 Insert a value into a histogram value = val * 10^(scale)
 
ssize_t hist_serialize (const histogram_t *h, void *buff, ssize_t len)
 Serialize histogram to binary data.
 
ssize_t hist_deserialize (histogram_t *h, const void *buff, ssize_t len)
 
ssize_t hist_serialize_estimate (const histogram_t *h)
 
ssize_t hist_serialize_b64 (const histogram_t *h, char *b64_serialized_histo_buff, ssize_t buff_len)
 Return histogram serialization as base64 encoded string.
 
ssize_t hist_deserialize_b64 (histogram_t *h, const void *b64_string, ssize_t b64_string_len)
 
ssize_t hist_serialize_b64_estimate (const histogram_t *h)
 
void hist_remove_zeroes (histogram_t *h)
 
histogram_t * hist_compress_mbe (const histogram_t *h, int8_t mbe)
 
double hist_approx_mean (const histogram_t *)
 Approximate mean value of all values stored in the histogram.
 
double hist_approx_sum (const histogram_t *)
 Approximate the sum of all values stored in the histogram.
 
double hist_approx_stddev (const histogram_t *)
 Approximate the standard deviation of all values stored in the histogram.
 
double hist_approx_moment (const histogram_t *hist, double k)
 
void hist_clamp (histogram_t *hist, double lower, double upper)
 
uint64_t hist_approx_count_below (const histogram_t *hist, double threshold)
 
uint64_t hist_approx_count_above (const histogram_t *hist, double threshold)
 
uint64_t hist_approx_count_nearby (const histogram_t *hist, double value)
 
int hist_approx_quantile (const histogram_t *, const double *q_in, int nq, double *q_out)
 
int hist_approx_inverse_quantile (const histogram_t *, const double *iq_in, int niq, double *iq_out)
 

Typedef Documentation

◆ hist_bucket_t

typedef struct hist_bucket hist_bucket_t

A hist_bucket structure represents a histogram bucket with the following dimensions:

  • (val < -99 || 99 < val) => Invalid bucket
  • (-10 < val && val < 10) => (-10^-127 .. +10^-127) zero bucket
  • val > 0 => [ (val/10)*10^exp .. (val+1)/10*10^exp )
  • val < 0 => ( (val-1)/10*10^exp .. (val/10)*10^exp ]

Function Documentation

◆ hist_approx_count_above()

uint64_t hist_approx_count_above ( const histogram_t *  hist,
double  threshold 
)

Returns the number of values in buckets that are entirely larger than or equal to threshold

Parameters
hist
threshold

◆ hist_approx_count_below()

uint64_t hist_approx_count_below ( const histogram_t *  hist,
double  threshold 
)

Returns the number of values in buckets that are entirely lower than or equal to threshold

Parameters
hist
threshold

◆ hist_approx_count_nearby()

uint64_t hist_approx_count_nearby ( const histogram_t *  hist,
double  value 
)

Returns the number of samples in the histogram that are in the same bucket as the provided value

Parameters
hist
value

◆ hist_approx_inverse_quantile()

int hist_approx_inverse_quantile ( const histogram_t *  ,
const double *  iq_in,
int  niq,
double *  iq_out 
)

Approximate n inverse quantiles (ratio below threshold) of all values stored in the histogram

Parameters
*iq_inarray of inverse quantiles to compute
niqlength of inverse quantile array
*iq_outpre-allocated array where results shall be written to

◆ hist_approx_moment()

double hist_approx_moment ( const histogram_t *  hist,
double  k 
)

Approximate the k-th moment of all values stored in the histogram

Parameters
hist
k

◆ hist_approx_quantile()

int hist_approx_quantile ( const histogram_t *  ,
const double *  q_in,
int  nq,
double *  q_out 
)

Approximate n quantiles of all values stored in the histogram

Parameters
*q_inarray of quantiles to compute
nqlength of quantile array
*q_outpre-allocated array where results shall be written to

◆ hist_bucket_to_string()

int hist_bucket_to_string ( hist_bucket_t  hb,
char *  buf 
)

Writes a standardized string representation to buf Buf must be of size HIST_BUCKET_MAX_STRING_SIZE or larger.

Returns
of characters of bytes written into the buffer excluding terminator

Format spec: "sxxetyyy", where

  • s = '+' or '-' global sign
  • xx – two digits representing val as decimal integer (in 10 .. 99)
  • e = 'e' literal character
  • t = '+' or '-' exponent sign
  • yyy – three digits representing exp as decimal integer with leading 0s

Exception: The zero bucket is represented as "0" Exception: Invalid buckets are represented as "NaN"

Examples: 1 => '+10e-001'; 12 => '+12e+000'; -0.23 => '-23e-003'; 23000 => '+23e+003';

◆ hist_clamp()

void hist_clamp ( histogram_t *  hist,
double  lower,
double  upper 
)

Modifies the histogram to remove all counts for sample with values outside the provided range.

Parameters
hist
lower
upper

◆ hist_compress_mbe()

histogram_t* hist_compress_mbe ( const histogram_t *  h,
int8_t  mbe 
)

Compress histogram by squshing together adjacent buckets

This compression is lossy. mean/quantiles will be affected by compression. Intended use cases is visualization.

Parameters
hist
mbethe Minimum Bucket Exponent
Returns
the compressed histogram as new value

◆ hist_fast_alloc()

histogram_t* hist_fast_alloc ( void  )

Create a fast-histogram.

Fast allocations consume 2kb + N * 512b more memory where N is the number of used exponents. It allows for O(1) increments for prexisting keys, uses default allocator

◆ hist_fast_alloc_with_allocator()

histogram_t* hist_fast_alloc_with_allocator ( const hist_allocator_t alloc)

Create a fast-histogram.

Fast allocations consume 2kb + N * 512b more memory where N is the number of used exponents. It allows for O(1) increments for prexisting keys, uses custom allocator

◆ hist_insert()

uint64_t hist_insert ( histogram_t *  hist,
double  val,
uint64_t  count 
)

insert a value into a histogram count times

Inserting double values converts from IEEE double to a small static integer base and can suffer from floating point math skew. Using the intscale variant is more precise and significantly faster if you already have integer measurements.

◆ hist_insert_raw()

uint64_t hist_insert_raw ( histogram_t *  hist,
hist_bucket_t  hb,
uint64_t  count 
)

Insert a single bucket + count into a histogram

Updates counts if the bucket exists Handles re-allocation of new buckets if needed

◆ hist_insert_raw_end()

uint64_t hist_insert_raw_end ( histogram_t *  hist,
hist_bucket_t  hb,
uint64_t  count 
)

Like hist_insert_raw, but optimizes for the case that this bin does not exist, there is room, and is larger than any existing bin.