aboutsummaryrefslogtreecommitdiff
path: root/collections/map/map.c
diff options
context:
space:
mode:
Diffstat (limited to 'collections/map/map.c')
-rw-r--r--collections/map/map.c252
1 files changed, 189 insertions, 63 deletions
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;
}
generated by cgit v1.1 at 2024-05-17 02:53:58 +0000