Implemented Count-Min Sketch [count how many times a value has been observed]

- ndpi_cm_sketch_init()
- ndpi_cm_sketch_add()
- ndpi_cm_sketch_count()
- ndpi_cm_sketch_destroy()

1 files changed, 12 insertions, 2 deletions

diff --git a/src/include/ndpi_api.h b/src/include/ndpi_api.h
index 258c09ae8..ce124bbf6 100644
--- a/src/include/ndpi_api.h
+++ b/src/include/ndpi_api.h
@@ -1747,7 +1747,8 @@ extern "C" {
   /* ******************************* */
 
   u_int32_t ndpi_crc32(const void* data, size_t n_bytes);
-
+  u_int32_t ndpi_nearest_power_of_two(u_int32_t x);
+  
   /* ******************************* */
 
   int ndpi_des_init(struct ndpi_des_struct *des, double alpha, double beta, float significance);
@@ -1793,7 +1794,7 @@ extern "C" {
   
   /* ******************************* */
 
-  /* HyperLogLog cardinality estimator */
+  /* HyperLogLog cardinality estimator [count unique items] */
 
   /* Memory lifecycle */
   int ndpi_hll_init(struct ndpi_hll *hll, u_int8_t bits);
@@ -1809,6 +1810,15 @@ extern "C" {
 
   /* ******************************* */
 
+  /* Count-Min Sketch [count how many times a value has been observed] */
+
+  struct ndpi_cm_sketch *ndpi_cm_sketch_init(u_int16_t depth);
+  void ndpi_cm_sketch_add(struct ndpi_cm_sketch *sketch, u_int32_t element);
+  u_int32_t ndpi_cm_sketch_count(struct ndpi_cm_sketch *sketch, u_int32_t element);
+  void ndpi_cm_sketch_destroy(struct ndpi_cm_sketch *sketch);
+  
+  /* ******************************* */
+
   int  ndpi_init_bin(struct ndpi_bin *b, enum ndpi_bin_family f, u_int16_t num_bins);
   void ndpi_free_bin(struct ndpi_bin *b);
   struct ndpi_bin* ndpi_clone_bin(struct ndpi_bin *b);