Added simple hash implementation to the nDPI API

4 files changed, 151 insertions, 1 deletions

diff --git a/example/ndpiReader.c b/example/ndpiReader.c
index 98eef139d..5fbf9ebe2 100644
--- a/example/ndpiReader.c
+++ b/example/ndpiReader.c
@@ -114,7 +114,7 @@ struct info_pair {
   int count;
 };
 
-typedef struct node_a{
+typedef struct node_a {
   u_int32_t addr;
   u_int8_t version; /* IP version */
   char proto[16]; /*app level protocol*/
@@ -3690,6 +3690,25 @@ void rulesUnitTest() {
 
 /* *********************************************** */
 
+void hashUnitTest() {
+  ndpi_str_hash *h = ndpi_hash_alloc(16384);
+  char* dict[] = { "hello", "world", NULL };
+  int i;
+  
+  assert(h);
+
+  for(i=0; dict[i] != NULL; i++) {
+    u_int8_t l = strlen(dict[i]), v;
+
+    assert(ndpi_hash_add_entry(h, dict[i], l, i) == 0);
+    assert(ndpi_hash_find_entry(h, dict[i], l, &v) == 0);
+  }
+  
+  ndpi_hash_free(h);
+}
+
+/* *********************************************** */
+
 /**
    @brief MAIN FUNCTION
 **/
@@ -3712,6 +3731,7 @@ int orginal_main(int argc, char **argv) {
 
     /* Internal checks */
     // binUnitTest();
+    hashUnitTest();
     dgaUnitTest();
     hllUnitTest();
     bitmapUnitTest();
@@ -3811,3 +3831,4 @@ int orginal_main(int argc, char **argv) {
     return 0;
   }
 #endif /* WIN32 */
+
diff --git a/src/include/ndpi_api.h.in b/src/include/ndpi_api.h.in
index f5b5f15db..18936f9ff 100644
--- a/src/include/ndpi_api.h.in
+++ b/src/include/ndpi_api.h.in
@@ -1433,8 +1433,17 @@ extern "C" {
 			u_int8_t num_clusters, u_int16_t *cluster_ids,
 			struct ndpi_bin *centroids);
 
+  /* ******************************* */
+  
   u_int32_t ndpi_quick_16_byte_hash(u_int8_t *in_16_bytes_long);
 
+  /* ******************************* */
+
+  ndpi_str_hash* ndpi_hash_alloc(u_int32_t max_num_entries);
+  void ndpi_hash_free(ndpi_str_hash *h);
+  int ndpi_hash_find_entry(ndpi_str_hash *h, char *key, u_int key_len, u_int8_t *value);
+  int ndpi_hash_add_entry(ndpi_str_hash *h, char *key, u_int8_t key_len, u_int8_t value);
+  
 #ifdef __cplusplus
 }
 #endif
diff --git a/src/include/ndpi_typedefs.h b/src/include/ndpi_typedefs.h
index 6f9cc9885..76f9198da 100644
--- a/src/include/ndpi_typedefs.h
+++ b/src/include/ndpi_typedefs.h
@@ -1559,4 +1559,21 @@ struct ndpi_bin {
   } u;
 };
 
+/* **************************************** */
+
+struct ndpi_str_hash_info {
+  char *key;         /* Key   */
+  u_int8_t key_len;
+  u_int8_t value;    /* Value */
+  struct ndpi_str_hash_info *next;
+};
+
+typedef struct {
+  u_int32_t num_buckets, max_num_entries;
+  struct ndpi_str_hash_info **buckets;
+} ndpi_str_hash;
+
+
+/* **************************************** */
+
 #endif /* __NDPI_TYPEDEFS_H__ */
diff --git a/src/lib/ndpi_utils.c b/src/lib/ndpi_utils.c
index cb6cb5e92..4f31369af 100644
--- a/src/lib/ndpi_utils.c
+++ b/src/lib/ndpi_utils.c
@@ -1821,3 +1821,106 @@ u_int32_t ndpi_quick_16_byte_hash(u_int8_t *in_16_bytes_long) {
 }
 
 /* ******************************************************************** */
+
+ndpi_str_hash* ndpi_hash_alloc(u_int32_t max_num_entries) {
+  ndpi_str_hash *h = (ndpi_str_hash*)malloc(sizeof(ndpi_str_hash));
+
+  if(!h) return(NULL);
+  if(max_num_entries < 1024) max_num_entries = 1024;
+  if(max_num_entries > 10000000) max_num_entries = 10000000;
+  
+  h->max_num_entries = max_num_entries, h->num_buckets = max_num_entries/2;
+  h->buckets = (struct ndpi_str_hash_info**)calloc(sizeof(struct ndpi_str_hash_info*), h->num_buckets);
+
+  if(h->buckets == NULL) {
+    free(h);
+    return(NULL);
+  } else
+    return(h);
+}
+
+/* ******************************************************************** */
+
+void ndpi_hash_free(ndpi_str_hash *h) {
+  u_int32_t i;
+  
+  for(i=0; i<h->num_buckets; i++) {
+    struct ndpi_str_hash_info *head = h->buckets[i];
+
+    while(head != NULL) {
+      struct ndpi_str_hash_info *next = head->next;
+
+      free(head->key);
+      free(head);
+      head = next;
+    }
+  }
+
+  free(h->buckets);
+  free(h);
+}
+
+/* ******************************************************************** */
+
+static u_int32_t _ndpi_hash_function(ndpi_str_hash *h, char *key, u_int8_t key_len) {
+  u_int32_t hv = 0;
+  u_int8_t i;
+
+  for(i=0; i<key_len; i++)
+    hv += key[i]*(i+1);
+
+  return(hv % h->num_buckets);
+}
+
+/* ******************************************************************** */
+
+static int _ndpi_hash_find_entry(ndpi_str_hash *h, u_int32_t hashval, char *key, u_int key_len, u_int8_t *value) {
+  struct ndpi_str_hash_info *head = h->buckets[hashval];
+  
+  while(head != NULL) {
+    if((head->key_len == key_len) && (memcmp(head->key, key, key_len) == 0)) {
+      *value = head->value;
+      return(0); /* Found */
+    }
+    
+    head = head-> next;
+  }
+
+  return(-1); /* Not found */
+}
+
+/* ******************************************************************** */
+
+int ndpi_hash_find_entry(ndpi_str_hash *h, char *key, u_int key_len, u_int8_t *value) {
+  u_int32_t hv = _ndpi_hash_function(h, key, key_len);
+
+  return(_ndpi_hash_find_entry(h, hv, key, key_len, value));
+}
+
+/* ******************************************************************** */
+
+int ndpi_hash_add_entry(ndpi_str_hash *h, char *key, u_int8_t key_len, u_int8_t value) {
+  u_int32_t hv = _ndpi_hash_function(h, key, key_len);
+  u_int8_t ret_value;
+  int rc = _ndpi_hash_find_entry(h, hv, key, key_len, &ret_value);
+
+  if(rc == -1) {
+    /* Not found */
+    struct ndpi_str_hash_info *e = (struct ndpi_str_hash_info*)malloc(sizeof(struct ndpi_str_hash_info));
+
+    if(e == NULL)
+      return(-2);
+    
+    if((e->key = (char*)malloc(key_len)) == NULL)
+      return(-3);
+
+    memcpy(e->key, key, key_len);
+    e->key_len = key_len, e->value = value;
+    e->next = h->buckets[hv];
+    h->buckets[hv] = e;
+
+    return(0);
+  } else
+    return(0);
+}
+