cm_sketch.h File Reference

Count-min sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch. More...

#include <stdint.h>

Include dependency graph for cm_sketch.h:

Go to the source code of this file.

Typedefs
typedef struct sa_cm_sketch	sa_cm_sketch

Functions
sa_cm_sketch *	sa_create_cms (double epsilon, double delta)
	Allocate and initialize the data structure. More...
void	sa_init_cms (sa_cm_sketch *cms)
	Zero out the data structure. More...
void	sa_destroy_cms (sa_cm_sketch *cms)
	Free the associated memory. More...
uint32_t	sa_point_query_cms (sa_cm_sketch *cms, void *item, size_t len)
	Point query the frequency count of item. More...
uint32_t	sa_update_cms (sa_cm_sketch *cms, void *item, size_t len, int n)
	Increment/Decrement the Count-min sketch with the specified item and value. More...
uint64_t	sa_item_count_cms (sa_cm_sketch *cms)
	Return the total number of items added to the sketch. More...
uint64_t	sa_unique_count_cms (sa_cm_sketch *cms)
	Return the total number of unique items added to the sketch. More...
char *	sa_serialize_cms (sa_cm_sketch *cms, size_t *len)
	Serialize the internal state to a buffer. More...
int	sa_deserialize_cms (sa_cm_sketch *cms, const char *buf, size_t len)
	Restore the internal state from the serialized output. More...

Detailed Description

Count-min sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch.

Definition in file cm_sketch.h.

Typedef Documentation

typedef struct sa_cm_sketch sa_cm_sketch

Definition at line 15 of file cm_sketch.h.

Function Documentation

sa_cm_sketch* sa_create_cms	(	double	epsilon,
		double	delta
	)

Allocate and initialize the data structure.

Parameters

epsilon	Approximation factor
delta	Probability of failure

Returns

Count-min sketch struct

int sa_deserialize_cms	(	sa_cm_sketch *	cms,
		const char *	buf,
		size_t	len
	)

Restore the internal state from the serialized output.

Parameters

cms	Count-min sketch struct
buf	Buffer containing the output of serialize_cms
len	Length of the buffer

Returns

0 = success 1 = invalid buffer length

void sa_destroy_cms

(

sa_cm_sketch *

cms

)

Free the associated memory.

Parameters

cms	Count-min sketch struct

void sa_init_cms

(

sa_cm_sketch *

cms

)

Zero out the data structure.

Parameters

cms	Count-min sketch struct

uint64_t sa_item_count_cms

(

sa_cm_sketch *

cms

)

Return the total number of items added to the sketch.

Parameters

cms	Count-min sketch struct

Returns

size_t Number of items added to the sketch

uint32_t sa_point_query_cms	(	sa_cm_sketch *	cms,
		void *	item,
		size_t	len
	)

Point query the frequency count of item.

Parameters

cms	Count-min sketch struct
item	Item to query
len	Length of the item in bytes

Returns

int Estimated count

char* sa_serialize_cms	(	sa_cm_sketch *	cms,
		size_t *	len
	)

Serialize the internal state to a buffer.

Parameters

cms	Count-min sketch struct
len	Length of the returned buffer

Returns

char* Serialized representation MUST be freed by the caller

uint64_t sa_unique_count_cms

(

sa_cm_sketch *

cms

)

Return the total number of unique items added to the sketch.

Parameters

cms	Count-min sketch struct

Returns

size_t Number of unique items added to the sketch

uint32_t sa_update_cms	(	sa_cm_sketch *	cms,
		void *	item,
		size_t	len,
		int	n
	)

Increment/Decrement the Count-min sketch with the specified item and value.

Parameters

cms	Count-min sketch struct
item	Item to add
len	Length of the item in bytes
n	Number of items to add/remove

Returns

int Estimated count