implemented tree_balanced_insert() and test functions

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 <stdio.h>
 
+#include "log.h"
+
 #define _TREE_FREE_DATA 0x01
 #define _TREE_FREE_KEY	0x02