Added simple hash implementation to the nDPI API

1 files changed, 103 insertions, 0 deletions

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);
+}
+