diff options
Diffstat (limited to 'collections/map/map.c')
-rw-r--r-- | collections/map/map.c | 252 |
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; } |