From af1c42d4bf235779d05c135a87f2c95c83df6940 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Wed, 8 Jul 2020 14:34:24 -0400 Subject: 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 Date: Wed Jul 8 14:33:39 2020 -0400 Fix map free types with auxiliary function for map trees commit 1014cb41b38e987062040afd338f34a12fc0e7bc Author: Tucker Evans Date: Wed Jul 8 14:33:03 2020 -0400 Fix map clear types with auxiliary function for map trees commit 913d1f5e4358e7a8a3057027698320050a1ea472 Author: Tucker Evans Date: Wed Jul 8 14:28:54 2020 -0400 Fix index map types with auxiliary function for map trees commit 8d76fc0b4abcd49f67f7bff55a4da83b7ab457d6 Author: Tucker Evans 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 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 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 Date: Wed Jul 8 14:04:00 2020 -0400 Fix map insert types with auxiliary function for map trees commit 2a561c8320f6be8b415d62e1175ef4ff4f845962 Author: Tucker Evans Date: Wed Jul 8 14:00:15 2020 -0400 Fix map size types with auxiliary function for map trees commit 361645cbb4578900d6b3d32a84b9a2b94716d5d1 Author: Tucker Evans Date: Wed Jul 8 13:59:32 2020 -0400 Fix change new function for map type change commit 9a99bc4149307a1fa012bcb98bedf2a8569a822c Author: Tucker Evans Date: Wed Jul 8 13:58:57 2020 -0400 Fix internal functions for change in map type commit 0335d8fd4f7aaf2e24e282bd39d02bc2714b0061 Author: Tucker Evans 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. --- collections/map/map.adoc | 34 +++++-- collections/map/map.c | 252 +++++++++++++++++++++++++++++++++++------------ collections/map/map.h | 3 +- 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 + +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 #include +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*); -- cgit v1.1