temelia/src/hash_map.c

/*!
 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);
}