123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413 |
- /*!
- Temelia - Hash map implementation source file.
- Hash map maps keys to values; it's implemented using red-black trees, because
- those are the fastest data structures at general operations: search, insert and remove.
- Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
- @author Dascalu Laurentiu
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/common.h"
- #include "include/hash_map.h"
- #include "include/red_black_tree.h"
- #include "include/pair.h"
- #include <stdlib.h>
- struct _hash_map_t
- {
- /*!
- * Hash map's red black tree root
- */
- red_black_tree_t root;
- int size;
- };
- static void _hash_map_node_delete(void *key, void *context)
- {
- pair_delete(key);
- }
- static int _hash_map_compare_keys(void *node1, void *node2, void *context)
- {
- pair_t context_pair = (pair_t) context;
- int (*user_compare)(void *key1, void *key2, void *context) = pair_get_key(
- context_pair);
- void *user_context = pair_get_value(context_pair);
- return user_compare(pair_get_key(node1), pair_get_key(node2), user_context);
- }
- hash_map_t hash_map_new()
- {
- hash_map_t hash_map = _new(sizeof(struct _hash_map_t));
- if (hash_map)
- {
- hash_map->root = NULL;
- hash_map->size = 0;
- }
- return hash_map;
- }
- void hash_map_clear(hash_map_t hash_map)
- {
- _ASSERT(hash_map, ==, NULL, NULL_POINTER,);
- if (hash_map->root)
- {
- red_black_tree_inorder(hash_map->root, _hash_map_node_delete, NULL);
- red_black_tree_delete(hash_map->root);
- }
- hash_map->root = NULL;
- hash_map->size = 0;
- }
- void hash_map_delete(hash_map_t hash_map)
- {
- _ASSERT(hash_map, ==, NULL, NULL_POINTER,);
- hash_map_clear(hash_map);
- _delete(hash_map);
- }
- static red_black_tree_t _hash_map_do_search(hash_map_t hash_map, void *key,
- int compare_keys(void *x, void *y, void *context), void *context)
- {
- pair_t _key, _context;
- red_black_tree_t result;
- _ASSERT(hash_map, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare_keys, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(hash_map->size, <=, 0, INVALID_INPUT, NULL);
- _key = pair_new(key, NULL);
- _context = pair_new(compare_keys, context);
- _ASSERT(_key, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(_context, ==, NULL, NULL_POINTER, NULL);
- result = red_black_tree_search(hash_map->root, _key,
- _hash_map_compare_keys, _context);
- pair_delete(_key);
- pair_delete(_context);
- return result;
- }
- int hash_map_contains_key(hash_map_t hash_map, void *key, int compare_keys(
- void *x, void *y, void *context), void *context)
- {
- return _hash_map_do_search(hash_map, key, compare_keys, context) != NULL;
- }
- void *hash_map_get_key_value(hash_map_t hash_map, void *key, int compare_keys(
- void *x, void *y, void *context), void *context)
- {
- return pair_get_value(red_black_tree_get_key(_hash_map_do_search(hash_map,
- key, compare_keys, context)));
- }
- static volatile int _result;
- static volatile void *_key, *_value;
- static int (*_compare)(void *x, void *y, void *context);
- static void _hash_map_search_value(void *key, void *context)
- {
- if (_result)
- return;
- if (!_compare((void *) _value, pair_get_value(key), context))
- _result = 1;
- }
- int hash_map_contains_value(hash_map_t hash_map, void *value,
- int compare_values(void *x, void *y, void *context), void *context)
- {
- int result;
- _ASSERT(hash_map, ==, NULL, NULL_POINTER, -1);
- _ASSERT(compare_values, ==, NULL, NULL_POINTER, -1);
- _ASSERT(hash_map->size, <=, 0, INVALID_INPUT, -1);
- _result = 0;
- _value = value;
- _compare = compare_values;
- red_black_tree_inorder(hash_map->root, _hash_map_search_value, context);
- _value = NULL;
- _compare = NULL;
- result = _result;
- _result = 0;
- return result;
- }
- int hash_map_is_empty(hash_map_t hash_map)
- {
- _ASSERT(hash_map, ==, NULL, NULL_POINTER, -1);
- return hash_map->size == 0;
- }
- int hash_map_get_size(hash_map_t hash_map)
- {
- _ASSERT(hash_map, ==, NULL, NULL_POINTER, -1);
- return hash_map->size;
- }
- void *hash_map_put(hash_map_t hash_map, void *key, void *value,
- int compare_keys(void *x, void *y, void *context), void *context)
- {
- pair_t _key, _context, _pair;
- void *old_value;
- red_black_tree_t node;
- _ASSERT(hash_map, ==, NULL, NULL_POINTER, NULL);
- if (hash_map->root == NULL)
- {
- hash_map->root = red_black_tree_new(pair_new(key, value));
- hash_map->size++;
- return NULL;
- }
- _ASSERT(compare_keys, ==, NULL, NULL_POINTER, NULL);
- _key = pair_new(key, value);
- _context = pair_new(compare_keys, context);
- _ASSERT(_key, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(_context, ==, NULL, NULL_POINTER, NULL);
- node = red_black_tree_search(hash_map->root, _key, _hash_map_compare_keys,
- _context);
- if (node == NULL)
- {
- _pair = _key;
- red_black_tree_insert(&hash_map->root, _pair, _hash_map_compare_keys,
- _context, 1);
- hash_map->size++;
- pair_delete(_context);
- return NULL;
- }
- else
- {
- pair_delete(_context);
- pair_delete(_key);
- _pair = (pair_t) red_black_tree_get_key(node);
- if (_pair)
- {
- old_value = pair_get_value(_pair);
- pair_set_value(_pair, value);
- return old_value;
- }
- }
- return NULL;
- }
- int hash_map_remove_key(hash_map_t hash_map, void *key, int compare_keys(
- void *x, void *y, void *context), void *context)
- {
- pair_t _key, _context, _aux;
- red_black_tree_t result;
- int removed;
- _ASSERT(hash_map, ==, NULL, NULL_POINTER, -1);
- _ASSERT(compare_keys, ==, NULL, NULL_POINTER, -1);
- _ASSERT(hash_map->size, <=, 0, INVALID_INPUT, -1);
- if (hash_map->size == 1)
- {
- if (!compare_keys(pair_get_key(red_black_tree_get_key(hash_map->root)),
- key, context))
- {
- pair_delete(red_black_tree_get_key(hash_map->root));
- red_black_tree_delete_node(hash_map->root);
- hash_map->root = NULL;
- hash_map->size = 0;
- return 1;
- }
- return 0;
- }
- _key = pair_new(key, NULL);
- _context = pair_new(compare_keys, context);
- // Remove the node containing key
- result = red_black_tree_search(hash_map->root, _key,
- _hash_map_compare_keys, _context);
- if (result)
- {
- _aux = red_black_tree_get_key(result);
- removed = red_black_tree_remove(&hash_map->root, _key,
- _hash_map_compare_keys, _context, 1);
- if (removed > 0)
- {
- hash_map->size--;
- pair_delete(_aux);
- }
- }
- pair_delete(_key);
- pair_delete(_context);
- return result != NULL;
- }
- static void _hash_map_remove_value(void *key, void *context)
- {
- if (_result)
- return;
- if (!_compare((void *) _value, pair_get_value(key), context))
- {
- _key = pair_get_key(key);
- _result = 1;
- }
- }
- int hash_map_remove_value(hash_map_t hash_map, void *value, int compare_values(
- void *x, void *y, void *context), void *context)
- {
- int result;
- _ASSERT(hash_map, ==, NULL, NULL_POINTER, -1);
- _ASSERT(compare_values, ==, NULL, NULL_POINTER, -1);
- _ASSERT(hash_map->size, <=, 0, INVALID_INPUT, -1);
- _result = 0;
- _key = NULL;
- _value = value;
- _compare = compare_values;
- red_black_tree_inorder(hash_map->root, _hash_map_remove_value, context);
- if (_result && _key)
- hash_map_remove_key(hash_map, (void *) _key, compare_values, context);
- _key = NULL;
- _value = NULL;
- _compare = NULL;
- result = _result;
- _result = 0;
- return result;
- }
- void *hash_map_get_internal_representation(hash_map_t hash_map)
- {
- _ASSERT(hash_map, ==, NULL, NULL_POINTER, NULL);
- return hash_map->root;
- }
- static void _hash_map_iterate_keys_handler(void *key, void *context)
- {
- pair_t context_pair = (pair_t) context;
- int (*user_key_handler)(void *key, void *context) = pair_get_key(
- context_pair);
- void *user_context = pair_get_value(context_pair);
- user_key_handler(pair_get_key(key), user_context);
- }
- void hash_map_iterate_keys(hash_map_t hash_map, void handler(void *key,
- void *context), void *context)
- {
- pair_t context_pair;
- _ASSERT(hash_map, ==, NULL, NULL_POINTER,);
- _ASSERT(handler, ==, NULL, NULL_POINTER,);
- _ASSERT(hash_map->size, <=, 0, INVALID_INPUT,);
- context_pair = pair_new(handler, context);
- red_black_tree_inorder(hash_map->root, _hash_map_iterate_keys_handler,
- context_pair);
- pair_delete(context_pair);
- }
- static void _hash_map_iterate_values_handler(void *key, void *context)
- {
- pair_t context_pair = (pair_t) context;
- int (*user_key_handler)(void *key, void *context) = pair_get_key(
- context_pair);
- void *user_context = pair_get_value(context_pair);
- user_key_handler(pair_get_value(key), user_context);
- }
- void hash_map_iterate_values(hash_map_t hash_map, void handler(void *value,
- void *context), void *context)
- {
- pair_t context_pair;
- _ASSERT(hash_map, ==, NULL, NULL_POINTER,);
- _ASSERT(handler, ==, NULL, NULL_POINTER,);
- _ASSERT(hash_map->size, <=, 0, INVALID_INPUT,);
- context_pair = pair_new(handler, context);
- red_black_tree_inorder(hash_map->root, _hash_map_iterate_values_handler,
- context_pair);
- pair_delete(context_pair);
- }
- static void _hash_map_iterate_handler(void *key, void *context)
- {
- pair_t context_pair = (pair_t) context;
- int (*user_key_handler)(void *key, void *value, void *context) =
- pair_get_key(context_pair);
- void *user_context = pair_get_value(context_pair);
- user_key_handler(pair_get_key(key), pair_get_value(key), user_context);
- }
- void hash_map_iterate(hash_map_t hash_map, void handler(void *key, void *value,
- void *context), void *context)
- {
- pair_t context_pair;
- _ASSERT(hash_map, ==, NULL, NULL_POINTER,);
- _ASSERT(handler, ==, NULL, NULL_POINTER,);
- _ASSERT(hash_map->size, <=, 0, INVALID_INPUT,);
- context_pair = pair_new(handler, context);
- red_black_tree_inorder(hash_map->root, _hash_map_iterate_handler,
- context_pair);
- pair_delete(context_pair);
- }
|