Fix separate base map type from tree structure (nodes)

This was initially needed so we can rotate on the root node, also should
cut down on memory usage (albeit by a tiny amount)  by not copying the
comparison function pointer with every node. It feels like a more clean
solution anyways.

----------------------------------------------------------------------
Squashed commit of the following:

commit 056e73216cd850ae563fb6da27657cf17d0514b6
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 14:33:39 2020 -0400

    Fix map free types with auxiliary function for map trees

commit 1014cb41b38e987062040afd338f34a12fc0e7bc
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 14:33:03 2020 -0400

    Fix map clear types with auxiliary function for map trees

commit 913d1f5e4358e7a8a3057027698320050a1ea472
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 14:28:54 2020 -0400

    Fix index map types with auxiliary function for map trees

commit 8d76fc0b4abcd49f67f7bff55a4da83b7ab457d6
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 14:27:42 2020 -0400

    Fix map set key types with auxilary function for map trees

commit fec252a5214ab02dccfe90bfe8b548e0e872f6ef
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 14:22:59 2020 -0400

    Fix check key ptr types with auxiliary function for map tree

commit 9170db7f6aaefa1b0824e0b4a2a4acc73865c151
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 14:17:22 2020 -0400

    Fix change set val types with auxilary function for map trees

commit 9be9d3d5fd07541fbe6d4c1ec97be9c943b1455d
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 14:04:00 2020 -0400

    Fix map insert types with auxiliary function for map trees

commit 2a561c8320f6be8b415d62e1175ef4ff4f845962
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 14:00:15 2020 -0400

    Fix map size types with auxiliary function for map trees

commit 361645cbb4578900d6b3d32a84b9a2b94716d5d1
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 13:59:32 2020 -0400

    Fix change new function for map type change

commit 9a99bc4149307a1fa012bcb98bedf2a8569a822c
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 13:58:57 2020 -0400

    Fix internal functions for change in map type

commit 0335d8fd4f7aaf2e24e282bd39d02bc2714b0061
Author: Tucker Evans <tucker@tuckerevans.com>
Date:   Wed Jul 8 13:53:44 2020 -0400

    Add struct to hold metadata/root of tree for map

    This was needed so we can rotate on the root node, also should cut down
    on memory usage (albeit by a tiny amount)  by not copying the comparison
    function pointer with every node.

3 files changed, 219 insertions, 70 deletions

diff --git a/collections/map/map.adoc b/collections/map/map.adoc
index ce4999b..09dfde7 100644
--- a/collections/map/map.adoc
+++ b/collections/map/map.adoc
@@ -1,7 +1,7 @@
 Map
 ===
 Tucker Evans
-v0.5, 2020-07-06
+v0.6, 2020-07-06
 
 A basic map implemented in an AVL tree.
 
@@ -96,6 +96,25 @@ else
 	assert(map_size(dict) == 1);
 ----
 
+[[map_set_val]]
++void* map_set_val(map *self, void *key, void *val)+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+This replaces the value stored at +key+ (or equivalent) with +val+, the value
+that is overwritten is return so the user can free it.
+
+Examples
+^^^^^^^^
+[source,c]
+----
+#include "map.h"
+#include <string.h>
+
+map *dict = map_new((cmp_func) strcmp);
+
+map_insert(dict, strdup("ONE"), strdup("VALUE"));
+free(map_set_val(dict, "ONE", "NEW_VALUE"));
+----
+
 [[map_check_key_ptr]]
 +int map_check_key_ptr(map *self, void *key)+
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
@@ -122,7 +141,6 @@ eq_key2 = strdup("ONE");
 if (!map_check_key_ptr(dict, eq_key2)) {
 	free(map_set_key(dict, eq_key2));
 }
-
 ----
 
 [[map_set_key]]
@@ -140,10 +158,14 @@ Examples
 
 map *dict = map_new((cmp_func) strcmp);
 
-map_insert(dict, strdup("ONE"), "VALUE");
-assert(map_insert(dict, "ONE", "NEW_VALUE") < 0);
-free(map_set_key(dict "ONE"));
-assert(map_insert(dict, "ONE", "NEW_VALUE") == 0);
+map_insert(dict, strdup("ONE"), NULL);
+
+eq_key2 = strdup("ONE");
+
+/*Want to free key1 for some reason*/
+if (!map_check_key_ptr(dict, eq_key2)) {
+	free(map_set_key(dict, eq_key2));
+}
 ----
 
 [[map_index]]
diff --git a/collections/map/map.c b/collections/map/map.c
index 66382ba..5de4ae3 100644
--- a/collections/map/map.c
+++ b/collections/map/map.c
@@ -5,19 +5,24 @@
 #include <stdio.h>
 #include <assert.h>
 
+struct map_root {
+	struct map_node *root;
+
+	cmp_func cmp;
+};
+
 struct map_node {
 	void *key, *val;
-	cmp_func cmp;
 
 	struct map_node *left, *right, *parent;
 };
 
 int map_height(root)
-map *root;
+struct map_node *root;
 {
 	int l, r;
 
-	if (!root || !root->key)
+	if (!root)
 		return 0;
 
 	l = map_height(root->left);
@@ -27,7 +32,7 @@ map *root;
 }
 
 int map_bal_factor(root)
-map *root;
+struct map_node *root;
 {
 	return map_height(root->right) - map_height(root->left);
 }
@@ -41,32 +46,41 @@ cmp_func cmp;
 	assert(tmp);
 
 	tmp->cmp = cmp;
-	tmp->key = tmp->val = tmp->left = tmp->right = tmp->parent = NULL;
+	tmp->root = NULL;
 
 	return tmp;
 }
 
-map* map_new_from_parent(root)
-map *root;
+struct map_node* map_new_node()
 {
-	map *tmp;
+	struct map_node *tmp;
 
-	tmp = map_new(root->cmp);
-	tmp->parent = root;
+	assert(tmp = malloc(sizeof(struct map_node)));
+	tmp->parent = tmp->left = tmp-> right = tmp-> key = tmp->val = NULL;
 	return tmp;
 }
 
+int map_size_aux(root)
+struct map_node *root;
+{
+	if (!root)
+		return 1;
+
+	return map_size_aux(root->left) + map_size_aux(root->right) + 1;
+}
+
 int map_size(root)
 map *root;
 {
-	if (!root || !root->key)
+	if (!root || !root->root)
 		return 0;
 
-	return map_size(root->left) + map_size(root->right) + 1;
+	return map_size_aux(root->root);
 }
 
-int map_insert(root, key, val)
-map *root;
+int map_insert_aux(root, cmpf, key, val)
+struct map_node *root;
+cmp_func cmpf;
 void *key, *val;
 {
 	int cmp;
@@ -74,135 +88,247 @@ void *key, *val;
 	if (!root)
 		return -1;
 
-	if (!root->key) {
-		root->key = key;
-		root->val = val;
-		return 0;
-	}
-
-	cmp = root->cmp(root->key, key);
+	cmp = cmpf(root->key, key);
 
 	if (cmp < 0) {
 
-		if (!root->left)
-			root->left = map_new_from_parent(root);
+		if (!root->left) {
+			root->left = map_new_node(root);
 
-		map_insert(root->left, key, val);
-		return 0;
+			root->left->parent = root;
+			root->left->key = key;
+			root->left->val = val;
+			return 0;
+		}
+
+		return map_insert_aux(root->left, cmpf, key, val);
 	}
 
 	if (cmp > 0) {
-		if (!root->right)
-			root->right = map_new_from_parent(root);
+		if (!root->right) {
+			root->right = map_new_node(root);
 
-		map_insert(root->right, key, val);
-		return 0;
+			root->right->parent = root;
+			root->right->key = key;
+			root->right->val = val;
+			return 0;
+		}
+
+		return map_insert_aux(root->right, cmpf, key, val);
 	}
 
 	return -1;
 }
 
-int map_check_key_ptr(root, key)
+int map_insert(root, key, val)
+map *root;
+void *key, *val;
+{
+	int cmp;
+
+	if (!root)
+		return -1;
+
+	if (!root->root) {
+		root->root = map_new_node();
+		root->root->key = key;
+		root->root->val = val;
+		return 0;
+	}
+
+	return map_insert_aux(root->root, root->cmp, key, val);
+}
+
+void* map_set_val_aux(root, cmpf, key, val)
+struct map_node *root;
+cmp_func cmpf;
+void *key, *val;
+{
+	int cmp;
+
+	if (!root)
+		return NULL;
+
+	cmp = cmpf(root->key, key);
+
+	if (cmp < 0)
+		return map_set_val_aux(root->left, cmpf, key, val);
+
+	if (cmp > 0)
+		return map_set_val_aux(root->right, cmpf, key, val);
+
+	tmp = root->val;
+	root->val = val;
+	return tmp;
+}
+
+void* map_set_val(root, key, val)
 map *root;
+void *key, *val;
+{
+	if (!root)
+		return NULL;
+
+	return map_set_val_aux(root->root, root->cmp, key, val);
+}
+
+int map_check_key_ptr_aux(root, cmpf, key)
+struct map_node *root;
+cmp_func cmpf;
 void *key;
 {
 	int cmp;
 
-	if (!root || !key)
+	if(!root)
 		return 0;
 
-	cmp = root->cmp(root->key, key);
+	cmp = cmpf(root->key, key);
 
 	if (cmp < 0)
-		return map_check_key_ptr(root->left, key);
+		return map_check_key_ptr_aux(root->left, cmpf, key);
 	if (cmp > 0)
-		return map_check_key_ptr(root->right, key);
+		return map_check_key_ptr_aux(root->right, cmpf, key);
 
 	return root->key == key;
 }
 
-void* map_set_key(root, key)
+int map_check_key_ptr(root, key)
 map *root;
 void *key;
 {
+	if (!root)
+		return 0;
+
+	return map_check_key_ptr_aux(root->root, root->cmp, key);
+}
+
+void* map_set_key_aux(root, cmpf, key)
+struct map_node *root;
+cmp_func cmpf;
+void *key;
+{
 	void *tmp;
 	int cmp;
 
-	if (!root || !key)
+	if (!root)
 		return NULL;
 
-	cmp = root->cmp(root->key, key);
+	cmp = cmpf(root->key, key);
 
 	if (cmp < 0)
-		return map_set_key(root->left, key);
+		return map_set_key_aux(root->left, cmpf, key);
 
 	if (cmp > 0)
-		return map_set_key(root->right, key);
+		return map_set_key_aux(root->right, cmpf, key);
 
 	tmp = root->key;
 	root->key = key;
 	return tmp;
 }
 
-void* map_index(root, key)
+void* map_set_key(root, key)
 map *root;
 void *key;
 {
+
+	if (!root)
+		return NULL;
+
+	return map_set_key_aux(root->root, root->cmp, key);
+}
+
+void* map_index_aux(root, cmpf, key)
+struct map_node *root;
+cmp_func cmpf;
+void *key;
+{
 	int cmp;
-	if (!root || !root->key)
+
+	if (!root)
 		return NULL;
 
-	cmp = root->cmp(root->key, key);
+	cmp = cmpf(root->key, key);
 
 	if (cmp < 0)
-		return map_index(root->left, key);
+		return map_index_aux(root->left, cmpf, key);
 
 	if (cmp > 0)
-		return map_index(root->right, key);
+		return map_index_aux(root->right, cmpf, key);
 
 	return root->val;
 }
 
-void map_clear(root)
+void* map_index(root, key)
 map *root;
+void *key;
 {
-	map *l, *r;
+	if (!root)
+		return NULL;
 
-	l = root->left;
-	r = root->right;
+	return map_index_aux(root->root, root->cmp, key);
+}
 
+void map_clear_aux(root)
+struct map_node *root;
+{
 	if (!root)
 		return;
 
-	if (root->parent) {
-		free(root->key);
-		root->key = NULL;
+	map_clear_aux(root->left);
+	root->left = NULL;
 
-		free(root->val);
-		root->val = NULL;
+	map_clear_aux(root->right);
+	root->right= NULL;
 
-		root->parent = NULL;
 
-		free(root);
-	}
+	free(root->key);
+	root->key = NULL;
+
+	free(root->val);
+	root->val = NULL;
 
-	map_clear(l);
-	map_clear(r);
+	root->parent = NULL;
+	free(root);
+
+	return;
 }
 
-void map_free(root)
+void map_clear(root)
 map *root;
 {
 	if (!root)
 		return;
 
-	root->key = NULL;
+	map_clear_aux(root->root);
+	root->root = NULL;
+}
+
+void map_free_aux(root)
+struct map_node *root;
+{
+	if (!root)
+		return;
 
-	map_free(root->left);
+	map_free_aux(root->left);
 	root->left = NULL;
 
-	map_free(root->right);
-	root->right = NULL;
+	map_free_aux(root->right);
+	root->right= NULL;
+
+	root->parent = NULL;
+
+	free(root);
+	return;
+}
+
+void map_free(root)
+map *root;
+{
+	if (!root)
+		return;
+
+	map_free_aux(root->root);
 
 	free(root);
+	return;
 }
diff --git a/collections/map/map.h b/collections/map/map.h
index 38e3e11..f67b559 100644
--- a/collections/map/map.h
+++ b/collections/map/map.h
@@ -1,7 +1,7 @@
 #ifndef MAP_H
 #define MAP_H
 
-typedef struct map_node map;
+typedef struct map_root map;
 typedef int (*cmp_func)(void*, void*);
 
 /*constructors*/
@@ -13,6 +13,7 @@ int map_size(map*);
 /*data*/
 int map_insert(map*, void*, void*);
 void* map_index(map*, void*);
+void* map_set_val(map*, void*, void*);
 
 int map_check_key_ptr(map*, void*);
 void* map_set_key(map*, void*);