diff options
| -rw-r--r-- | example/ndpiReader.c | 23 | ||||
| -rw-r--r-- | src/include/ndpi_api.h.in | 9 | ||||
| -rw-r--r-- | src/include/ndpi_typedefs.h | 17 | ||||
| -rw-r--r-- | src/lib/ndpi_utils.c | 103 |
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); +} + |