From 187f0393347d8962d445286171db720e24242703 Mon Sep 17 00:00:00 2001 From: Jonas Gunz Date: Tue, 23 Jun 2020 09:55:14 +0200 Subject: implemented tree_balanced_insert() and test functions --- src/main.c | 4 ++ src/test.c | 40 +++++++++++++++---- src/tree.c | 132 +++++++++++++++++++++++++++++++++++++++++-------------------- src/tree.h | 2 + 4 files changed, 129 insertions(+), 49 deletions(-) diff --git a/src/main.c b/src/main.c index d66b7fb..848f04e 100644 --- a/src/main.c +++ b/src/main.c @@ -10,6 +10,10 @@ #include "log.h" #include "server.h" +#ifdef _TEST +#include "test.h" +#endif + int main(int argc, char* argv[]) { //CMD line arg parsing goes in here diff --git a/src/test.c b/src/test.c index 07dbb7d..f88aa3a 100644 --- a/src/test.c +++ b/src/test.c @@ -9,6 +9,7 @@ void run_test () { + log_init_stdout(_LOG_DEBUG); //Space for temporary tests //tree_balanced_insert(NULL, NULL, NULL, 15 ); @@ -21,20 +22,45 @@ void run_test () int test_tree () { - printf("\n-> test_tree()\n======\n\n"); + unsigned const int len = pow ( 'z' - 'a' + 1, 2); + unsigned int len_cnt = 0; + char* keys[len]; + char* data[len]; struct tree_node* root = NULL; - tree_insert ( &root, "eins", "Test eins" ); - tree_insert ( &root, "zwei", "Test zwei" ); + printf("\n-> test_tree()\n======\n\n"); + + for ( char i = 'a'; i <= 'z'; i++ ) { + for ( char j = 'a'; j <= 'z'; j++ ) { + keys[len_cnt] = malloc (3); + keys[len_cnt][0] = i; + keys[len_cnt][1] = j; + keys[len_cnt][2] = 0; + + data[len_cnt] = malloc(10); + snprintf( data[len_cnt], 10, "N%i", len_cnt ); + + len_cnt ++; + } + } + + printf("len_cnt %i\n", len_cnt); + + tree_balanced_insert( &root, data, keys, len ); printf("After Insert\n"); - printf("%s\n", tree_get(&root, "zwei")); + printf("%s\n", tree_get(&root, "aa")); + + for ( int i = 0; i < len; i++ ) { + if ( ! tree_get(&root, keys[i]) ) + LOGPRINTF(_LOG_WARNING, "%s not found in tree", keys[i]); + } printf("After Get\n"); - tree_destroy (&root,0); + tree_destroy (&root, _TREE_FREE_DATA | _TREE_FREE_KEY); printf("After destroy\n"); @@ -103,7 +129,7 @@ int test_dns_qname_fuzz() } float valid_percent = (float)valid_cnt / (float)limit * 100; - printf("# of valid qnames in random data: %i / %i = %f%%\n", valid_cnt, limit, valid_percent); + printf("# of valid qnames in random data: %lu / %lu = %f%%\n", valid_cnt, limit, valid_percent); return 0; } @@ -130,7 +156,7 @@ int test_dns_message_fuzz() } float valid_percent = (float)valid_cnt / (float)limit * 100; - printf("# of valid messages in random data: %i / %i = %f%%\n", valid_cnt, limit, valid_percent); + printf("# of valid messages in random data: %lu / %lu = %f%%\n", valid_cnt, limit, valid_percent); return 0; } diff --git a/src/tree.c b/src/tree.c index 479e2a6..4395c81 100644 --- a/src/tree.c +++ b/src/tree.c @@ -8,6 +8,46 @@ static int string_compare ( char* _1, char* _2 ); +/** + * ignore-case alphabetical string compare + * returns: + * 0 :: _1 == _2 + * -1 :: _1 < _2 + * +1 :: _1 > _2 + * */ +static int string_compare ( char* _1, char* _2 ) +{ + if ( !_1 || !_2 ) + return 99; + + int i; + for (i = 0; _1[i] && _2[i]; i++) { + char c1 = _1[i]; + char c2 = _2[i]; + + //Convert to uppercase + if ( c1 >= 97 && c1 <= 122 ) + c1 -= 32; + if ( c2 >= 97 && c2 <= 122 ) + c2 -= 32; + + if (c1 > c2) + return 1; + if (c1 < c2) + return -1; + } + + if ( _1[i] == _2[i] ) + return 0; + if ( _1[i] ) + return 1; + if ( _2[i] ) + return -1; + + //TODO not so great + return 99; +} + int tree_insert ( struct tree_node** _root, char* _key, void* _data ) { struct tree_node** node = _root; @@ -34,64 +74,74 @@ int tree_insert ( struct tree_node** _root, char* _key, void* _data ) return 0; } -int tree_balance ( struct tree_node** _root ) +int tree_balanced_insert ( struct tree_node** _root, void* _data[], char* _key[], unsigned int _len) { - return 1; + // n is the smallest n, for which 2^(n+1) - 1 >= _len, + // thus describes the minimal tree depth required to store + // _len amount of elements + unsigned int n = 0; + for (n = 0; pow( 2, n+1 ) - 1 < _len; n++); + + + // The maximum size of a tree with depth n; + unsigned int virtual_len = pow( 2, n+1 ) - 1; + + unsigned int indices[ virtual_len ]; + unsigned int indices_cnt = 0; + + LOGPRINTF(_LOG_DEBUG, "Elements: %u Rounded size: %u Optimal depth: %u", _len, virtual_len, n); + + // Creates the series + // 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, ... + for (unsigned int i = 0; i <= n+1; i++) { + unsigned int pow_2_i = pow(2,i); + for (unsigned int o = 1; o < pow(2,i); o+=2) { + indices[ indices_cnt++ ] = virtual_len * o / pow_2_i; + } + } + + for ( unsigned int i = 0; i < virtual_len; i++ ) { + if ( indices[i] < _len ) { + if (tree_insert ( _root, _key[indices[i]], _data[indices[i]] )){ + LOGPRINTF(_LOG_WARNING, "tree_insert failed on \"%s\". Double?", _key[indices[i]]); + } + } + } + + return 0; } int tree_destroy ( struct tree_node** _root, uint8_t _options ) { + //Not efficient, but this code is for testing only. + unsigned int max_depth = 0; + unsigned int node_cnt = 0; while(*_root) { struct tree_node** node = _root; - - while( (*node)->above || (*node)->below ) + unsigned int depth = 0; + + while( (*node)->above || (*node)->below ) { node= (*node)->above ? & (*node)->above : & (*node)->below ; - - printf( "%s\n", (*node)->data ); + depth ++; + } - if (_options & _TREE_FREE_KEY) + if (_options & _TREE_FREE_DATA) free( (*node)->data ); if (_options & _TREE_FREE_KEY) free( (*node)->key ); - - free ( *node ); - *node = NULL; - } - - return 0; -} - -static int string_compare ( char* _1, char* _2 ) -{ - if ( !_1 || !_2 ) - return 99; - int i; - for (i = 0; _1[i] && _2[i]; i++) { - char c1 = _1[i]; - char c2 = _2[i]; - //Convert to uppercase - if ( c1 >= 97 && c1 <= 122 ) - c1 -= 32; - if ( c2 >= 97 && c2 <= 122 ) - c2 -= 32; + if ( depth > max_depth ) + max_depth = depth; - if (c1 > c2) - return 1; - if (c1 < c2) - return -1; + free ( *node ); + *node = NULL; + node_cnt ++; } - if ( _1[i] == _2[i] ) - return 0; - if ( _1[i] ) - return 1; - if ( _2[i] ) - return -1; + LOGPRINTF(_LOG_DEBUG, "%i nodes deleted. Max depth %i", node_cnt, max_depth); - //TODO WARN may reach end of non-void function - return 99; + return 0; } void* tree_get ( struct tree_node** _root, char* _query ) @@ -110,6 +160,4 @@ void* tree_get ( struct tree_node** _root, char* _query ) } return *node ? (*node)->data : NULL; - - return 0; } diff --git a/src/tree.h b/src/tree.h index 98019c8..55dfb8b 100644 --- a/src/tree.h +++ b/src/tree.h @@ -43,6 +43,8 @@ //TODO remove #include +#include "log.h" + #define _TREE_FREE_DATA 0x01 #define _TREE_FREE_KEY 0x02 -- cgit v1.2.3