aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--collections/map/map.adoc34
-rw-r--r--collections/map/map.c252
-rw-r--r--collections/map/map.h3
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*);
generated by cgit v1.1 at 2024-05-17 02:19:46 +0000