p2.h File Reference

Piece_wise parabolic predicition (P2). More...

#include <stddef.h>

Include dependency graph for p2.h:

Go to the source code of this file.

Typedefs
typedef struct sa_p2_quantile	sa_p2_quantile
typedef struct sa_p2_histogram	sa_p2_histogram

Functions
sa_p2_quantile *	sa_create_p2_quantile (double p)
	Allocates and initializes the data structure. More...
void	sa_init_p2_quantile (sa_p2_quantile *p2q)
	Zeros out the quantile. More...
double	sa_add_p2_quantile (sa_p2_quantile *p2q, double x)
	Updates the quantile with the provided observation. More...
unsigned long long	sa_count_p2_quantile (sa_p2_quantile *p2q, unsigned short marker)
	Returns the number of observations that are less than or equal to the marker. More...
double	sa_estimate_p2_quantile (sa_p2_quantile *p2q, unsigned short marker)
	Returns the estimated quantile value for the specified marker. More...
void	sa_destroy_p2_quantile (sa_p2_quantile *p2q)
	Free the associated memory. More...
char *	sa_serialize_p2_quantile (sa_p2_quantile *p2q, size_t *len)
	Serialize the internal state to a buffer. More...
int	sa_deserialize_p2_quantile (sa_p2_quantile *p2q, const char *buf, size_t len)
	Restores the internal state from the serialized output. More...
sa_p2_histogram *	sa_create_p2_histogram (unsigned short buckets)
	Allocates and initializes the data structures. More...
void	sa_init_p2_histogram (sa_p2_histogram *p2h)
	Zeros out the histogram counters. More...
void	sa_add_p2_histogram (sa_p2_histogram *p2h, double x)
	Updates the histogram with the provided observation. More...
unsigned long long	sa_count_p2_histogram (sa_p2_histogram *p2h, unsigned short marker)
	Gets the number of observations that are less than or equal to the marker. More...
double	sa_estimate_p2_histogram (sa_p2_histogram *p2h, unsigned short marker)
	Gets the estimated quantile value for the specified marker. More...
void	sa_destroy_p2_histogram (sa_p2_histogram *p2h)
	Free the associated memory. More...
char *	sa_serialize_p2_histogram (sa_p2_histogram *p2h, size_t *len)
	Serialize the internal state to a buffer. More...
int	sa_deserialize_p2_histogram (sa_p2_histogram *p2h, const char *buf, size_t len)
	Restores the internal state from the serialized output. More...

Detailed Description

Piece_wise parabolic predicition (P2).

Dynamic calculation of quantiles and histograms without storing observations. http://www.cs.wustl.edu/~jain/papers/ftp/psqr.pdf

Definition in file p2.h.

Typedef Documentation

typedef struct sa_p2_histogram sa_p2_histogram

Definition at line 18 of file p2.h.

typedef struct sa_p2_quantile sa_p2_quantile

Definition at line 17 of file p2.h.

Function Documentation

void sa_add_p2_histogram	(	sa_p2_histogram *	p2h,
		double	x
	)

Updates the histogram with the provided observation.

Parameters

p2h	Histogram struct
x	Observation to add

double sa_add_p2_quantile	(	sa_p2_quantile *	p2q,
		double	x
	)

Updates the quantile with the provided observation.

Parameters

p2q	Quantile struct
x	Observation to add

Returns

p_quantile estimate

unsigned long long sa_count_p2_histogram	(	sa_p2_histogram *	p2h,
		unsigned short	marker
	)

Gets the number of observations that are less than or equal to the marker.

• Parameters

  p2h	Histogram struct
  marker	Selects the percentile (marker/buckets)

unsigned long long sa_count_p2_quantile	(	sa_p2_quantile *	p2q,
		unsigned short	marker
	)

Returns the number of observations that are less than or equal to the marker.

Parameters

p2q	Quantile struct
marker	Selects the percentile 0 = min 1 = p/2 2 = p 3 = (1+p)/2 4 = max

sa_p2_histogram* sa_create_p2_histogram

(

unsigned short

buckets

)

Allocates and initializes the data structures.

Parameters

buckets

Number of histogram buckets

sa_p2_quantile* sa_create_p2_quantile

(

double

p

)

Allocates and initializes the data structure.

Parameters

p	p_quantile to calculate (e.g. 0.5 == median)

int sa_deserialize_p2_histogram	(	sa_p2_histogram *	p2h,
		const char *	buf,
		size_t	len
	)

Restores the internal state from the serialized output.

Parameters

p2h	Histogram struct
buf	Buffer containing the output of serialize_p2_histogram
len	Length of the buffer

Returns

0 = success 1 = invalid buffer length 2 = invalid cnt

int sa_deserialize_p2_quantile	(	sa_p2_quantile *	p2q,
		const char *	buf,
		size_t	len
	)

Restores the internal state from the serialized output.

Parameters

p2q	Quantile struct
buf	Buffer containing the output of serialize_p2_quantile
len	Length of the buffer

Returns

0 = success 1 = invalid buffer length 2 = invalid cnt 3 = mis-matched percentile

void sa_destroy_p2_histogram

(

sa_p2_histogram *

p2h

)

Free the associated memory.

Parameters

p2h	Histogram struct

void sa_destroy_p2_quantile

(

sa_p2_quantile *

p2q

)

Free the associated memory.

Parameters

p2q	Quantile struct

double sa_estimate_p2_histogram	(	sa_p2_histogram *	p2h,
		unsigned short	marker
	)

Gets the estimated quantile value for the specified marker.

Parameters

p2h	Histogram struct
marker	Selects the percentile (marker/buckets)

double sa_estimate_p2_quantile	(	sa_p2_quantile *	p2q,
		unsigned short	marker
	)

Returns the estimated quantile value for the specified marker.

Parameters

p2q	Quantile struct
marker	0-4 see sa_count_p2_quantile

void sa_init_p2_histogram

(

sa_p2_histogram *

p2h

)

Zeros out the histogram counters.

Parameters

p2h	Histogram struct

void sa_init_p2_quantile

(

sa_p2_quantile *

p2q

)

Zeros out the quantile.

Parameters

p2q	Quantile struct

char* sa_serialize_p2_histogram	(	sa_p2_histogram *	p2h,
		size_t *	len
	)

Serialize the internal state to a buffer.

Parameters

p2h	Histogram struct
len	Length of the returned buffer

Returns

char* Serialized representation MUST be freed by the caller

char* sa_serialize_p2_quantile	(	sa_p2_quantile *	p2q,
		size_t *	len
	)

Serialize the internal state to a buffer.

Parameters

p2q	Quantile struct
len	Length of the returned buffer

Returns

char* Serialized representation MUST be freed by the caller