ell/hashmap.c

/*
 *
 *  Embedded Linux library
 *
 *  Copyright (C) 2011-2014  Intel Corporation. All rights reserved.
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library 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
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "util.h"
#include "hashmap.h"
#include "private.h"

/**
 * SECTION:hashmap
 * @short_description: Hash table support
 *
 * Hash table support
 */

#define NBUCKETS 127

struct entry {
	void *key;
	void *value;
	struct entry *next;
	unsigned int hash;
};

/**
 * l_hashmap:
 *
 * Opague object representing the hash table.
 */
struct l_hashmap {
	l_hashmap_hash_func_t hash_func;
	l_hashmap_compare_func_t compare_func;
	l_hashmap_key_new_func_t key_new_func;
	l_hashmap_key_free_func_t key_free_func;
	unsigned int entries;
	struct entry buckets[NBUCKETS];
};

static inline void *get_key_new(const struct l_hashmap *hashmap,
				const void *key)
{
	if (hashmap->key_new_func)
		return hashmap->key_new_func(key);

	return (void *)key;
}

static inline void free_key(const struct l_hashmap *hashmap, void *key)
{
	if (hashmap->key_free_func)
		hashmap->key_free_func(key);
}

static inline unsigned int hash_superfast(const uint8_t *key, unsigned int len)
{
	/*
	 * Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
	 * used by WebCore (http://webkit.org/blog/8/hashtables-part-2/),
	 * EFL's eina, kmod and possible others.
	 */
	unsigned int tmp, hash = len, rem = len & 3;

	len /= 4;

	/* Main loop */
	for (; len > 0; len--) {
		hash += l_get_u16(key);
		tmp = (l_get_u16(key + 2) << 11) ^ hash;
		hash = (hash << 16) ^ tmp;
		key += 4;
		hash += hash >> 11;
	}

	/* Handle end cases */
	switch (rem) {
	case 3:
		hash += l_get_u16(key);
		hash ^= hash << 16;
		hash ^= key[2] << 18;
		hash += hash >> 11;
		break;

	case 2:
		hash += l_get_u16(key);
		hash ^= hash << 11;
		hash += hash >> 17;
		break;

	case 1:
		hash += *key;
		hash ^= hash << 10;
		hash += hash >> 1;
		break;
	}

	/* Force "avalanching" of final 127 bits */
	hash ^= hash << 3;
	hash += hash >> 5;
	hash ^= hash << 4;
	hash += hash >> 17;
	hash ^= hash << 25;
	hash += hash >> 6;

	return hash;
}

static unsigned int direct_hash_func(const void *p)
{
	return L_PTR_TO_UINT(p);
}

static int direct_compare_func(const void *a, const void *b)
{
        return a < b ? -1 : (a > b ? 1 : 0);
}

/**
 * l_hashmap_new:
 *
 * Create a new hash table. The keys are managed as pointers, that is,
 * the pointer value is hashed and looked up.
 *
 * No error handling is needed since. In case of real memory allocation
 * problems abort() will be called.
 *
 * See also l_hashmap_string_new().
 *
 * Returns: a newly allocated #l_hashmap object
 **/
LIB_EXPORT struct l_hashmap *l_hashmap_new(void)
{
	struct l_hashmap *hashmap;

	hashmap = l_new(struct l_hashmap, 1);

	hashmap->hash_func = direct_hash_func;
	hashmap->compare_func = direct_compare_func;
	hashmap->entries = 0;

	return hashmap;
}

LIB_EXPORT unsigned int l_str_hash(const void *p)
{
	const char *s = p;
	size_t len = strlen(s);

	return hash_superfast((const uint8_t *)s, len);
}

/**
 * l_hashmap_string_new:
 *
 * Create a new hash table. The keys are considered strings and are
 * copied.
 *
 * No error handling is needed since. In case of real memory allocation
 * problems abort() will be called.
 *
 * See also l_hashmap_new().
 *
 * Returns: a newly allocated #l_hashmap object
 **/
LIB_EXPORT struct l_hashmap *l_hashmap_string_new(void)
{
	struct l_hashmap *hashmap;

	hashmap = l_new(struct l_hashmap, 1);

	hashmap->hash_func = l_str_hash;
	hashmap->compare_func = (l_hashmap_compare_func_t) strcmp;
	hashmap->key_new_func = (l_hashmap_key_new_func_t) l_strdup;
	hashmap->key_free_func = l_free;
	hashmap->entries = 0;

	return hashmap;
}

/**
 * l_hashmap_set_hash_function:
 * @hashmap: hash table object
 * @func: Key hashing function
 *
 * Sets the hashing function to be used by this object.
 *
 * This function can only be called when the @hashmap is empty.
 *
 * Returns: #true when the hashing function could be updated successfully,
 * and #false otherwise.
 **/
LIB_EXPORT bool l_hashmap_set_hash_function(struct l_hashmap *hashmap,
						l_hashmap_hash_func_t func)
{
	if (unlikely(!hashmap))
		return false;

	if (hashmap->entries != 0)
		return false;

	hashmap->hash_func = func;

	return true;
}

/**
 * l_hashmap_set_compare_function:
 * @hashmap: hash table object
 * @func: Key compare function
 *
 * Sets the key comparison function to be used by this object.
 *
 * This function can only be called when the @hashmap is empty.
 *
 * Returns: #true when the comparison function could be updated successfully,
 * and #false otherwise.
 **/
LIB_EXPORT bool l_hashmap_set_compare_function(struct l_hashmap *hashmap,
						l_hashmap_compare_func_t func)
{
	if (unlikely(!hashmap))
		return false;

	if (hashmap->entries != 0)
		return false;

	hashmap->compare_func = func;

	return true;
}

/**
 * l_hashmap_set_key_copy_function:
 * @hashmap: hash table object
 * @func: Key duplication function
 *
 * Sets the key duplication function to be used by this object.  If the
 * function is NULL, then the keys are assigned directly.
 *
 * This function can only be called when the @hashmap is empty.
 *
 * Returns: #true when the key copy function could be updated successfully,
 * and #false otherwise.
 **/
LIB_EXPORT bool l_hashmap_set_key_copy_function(struct l_hashmap *hashmap,
						l_hashmap_key_new_func_t func)
{
	if (unlikely(!hashmap))
		return false;

	if (hashmap->entries != 0)
		return false;

	hashmap->key_new_func = func;

	return true;
}

/**
 * l_hashmap_set_key_free_function:
 * @hashmap: hash table object
 * @func: Key destructor function
 *
 * Sets the key destructor function to be used by this object.  This function
 * should undo the result of the function specified in
 * l_hashmap_set_key_copy_function(). This function can be NULL, in which
 * case no destructor is called.
 *
 * This function can only be called when the @hashmap is empty.
 *
 * Returns: #true when the key free function could be updated successfully,
 * and #false otherwise.
 **/
LIB_EXPORT bool l_hashmap_set_key_free_function(struct l_hashmap *hashmap,
						l_hashmap_key_free_func_t func)
{
	if (unlikely(!hashmap))
		return false;

	if (hashmap->entries != 0)
		return false;

	hashmap->key_free_func = func;

	return true;
}

/**
 * l_hashmap_destroy:
 * @hashmap: hash table object
 * @destroy: destroy function
 *
 * Free hash table and call @destory on all remaining entries.
 *
 * NOTE: While the destroy is in progress, the hashmap is assumed to be
 * invariant.  The behavior of adding or removing entries while a destroy
 * operation is in progress is undefined.
 **/
LIB_EXPORT void l_hashmap_destroy(struct l_hashmap *hashmap,
				l_hashmap_destroy_func_t destroy)
{
	unsigned int i;

	if (unlikely(!hashmap))
		return;

	for (i = 0; i < NBUCKETS; i++) {
		struct entry *entry, *next, *head = &hashmap->buckets[i];

		if (!head->next)
			continue;

		for (entry = head;; entry = next) {
			if (destroy)
				destroy(entry->value);

			free_key(hashmap, entry->key);

			next = entry->next;

			if (entry != head)
				l_free(entry);

			if (next == head)
				break;
		}
	}

	l_free(hashmap);
}

/**
 * l_hashmap_insert:
 * @hashmap: hash table object
 * @key: key pointer
 * @value: value pointer
 *
 * Insert new @value entry with @key.
 *
 * Returns: #true when value has been added and #false in case of failure
 **/
LIB_EXPORT bool l_hashmap_insert(struct l_hashmap *hashmap,
				const void *key, void *value)
{
	struct entry *entry, *head;
	unsigned int hash;
	void *key_new;

	if (unlikely(!hashmap))
		return false;

	key_new = get_key_new(hashmap, key);
	hash = hashmap->hash_func(key_new);
	head = &hashmap->buckets[hash % NBUCKETS];

	if (!head->next) {
		head->key = key_new;
		head->value = value;
		head->hash = hash;
		head->next = head;
		goto done;
	}

	entry = l_new(struct entry, 1);
	entry->key = key_new;
	entry->value = value;
	entry->hash = hash;
	entry->next = head;

	while (head->next != entry->next)
		head = head->next;

	head->next = entry;

done:
	hashmap->entries++;

	return true;
}

/**
 * l_hashmap_remove:
 * @hashmap: hash table object
 * @key: key pointer
 *
 * Remove entry for @key.
 *
 * Returns: value pointer of the removed entry or #NULL in case of failure
 **/
LIB_EXPORT void *l_hashmap_remove(struct l_hashmap *hashmap, const void *key)
{
	struct entry *entry, *head, *prev;
	unsigned int hash;

	if (unlikely(!hashmap))
		return NULL;

	hash = hashmap->hash_func(key);
	head = &hashmap->buckets[hash % NBUCKETS];

	if (!head->next)
		return NULL;

	for (entry = head, prev = NULL;; prev = entry, entry = entry->next) {
		void *value;

		if (entry->hash != hash)
			goto next;

		if (hashmap->compare_func(key, entry->key))
			goto next;

		value = entry->value;

		if (entry == head) {
			if (entry->next == head) {
				free_key(hashmap, entry->key);
				head->key = NULL;
				head->value = NULL;
				head->hash = 0;
				head->next = NULL;
			} else {
				entry = entry->next;
				free_key(hashmap, head->key);
				head->key = entry->key;
				head->value = entry->value;
				head->hash = entry->hash;
				head->next = entry->next;
				l_free(entry);
			}
		} else {
			prev->next = entry->next;
			free_key(hashmap, entry->key);
			l_free(entry);
		}

		hashmap->entries--;

		return value;

next:
		if (entry->next == head)
			break;
	}

	return NULL;
}

/**
 * l_hashmap_lookup:
 * @hashmap: hash table object
 * @key: key pointer
 *
 * Lookup entry for @key.
 *
 * Returns: value pointer for @key or #NULL in case of failure
 **/
LIB_EXPORT void *l_hashmap_lookup(struct l_hashmap *hashmap, const void *key)
{
	struct entry *entry, *head;
	unsigned int hash;

	if (unlikely(!hashmap))
		return NULL;

	hash = hashmap->hash_func(key);
	head = &hashmap->buckets[hash % NBUCKETS];

	if (!head->next)
		return NULL;

	for (entry = head;; entry = entry->next) {
		if (entry->hash == hash &&
				!hashmap->compare_func(key, entry->key))
			return entry->value;

		if (entry->next == head)
			break;
	}

	return NULL;
}

/**
 * l_hashmap_foreach:
 * @hashmap: hash table object
 * @function: callback function
 * @user_data: user data given to callback function
 *
 * Call @function for every entry in @hashmap.
 *
 * NOTE: While the foreach is in progress, the hashmap is assumed to be
 * invariant.  The behavior of adding or removing entries while a foreach
 * operation is in progress is undefined.
 **/
LIB_EXPORT void l_hashmap_foreach(struct l_hashmap *hashmap,
			l_hashmap_foreach_func_t function, void *user_data)
{
	unsigned int i;

	if (unlikely(!hashmap || !function))
		return;

	for (i = 0; i < NBUCKETS; i++) {
		struct entry *entry, *head = &hashmap->buckets[i];

		if (!head->next)
			continue;

		for (entry = head;; entry = entry->next) {
			function(entry->key, entry->value, user_data);

			if (entry->next == head)
				break;
		}
	}
}

/**
 * l_hashmap_foreach_remove:
 * @hashmap: hash table object
 * @function: callback function
 * @user_data: user data given to callback function
 *
 * Call @function for every entry in @hashmap.  If the @function returns
 * true, then the object will be removed from the hashmap.
 *
 * NOTE: While the foreach is in progress, the hashmap is assumed to be
 * invariant.  The behavior of adding or removing entries while a foreach
 * operation is in progress is undefined.
 *
 * Returns: Number of entries removed.
 **/
LIB_EXPORT unsigned int l_hashmap_foreach_remove(struct l_hashmap *hashmap,
					l_hashmap_remove_func_t function,
					void *user_data)
{
	unsigned int i;
	unsigned int nremoved = 0;

	if (unlikely(!hashmap || !function))
		return 0;

	for (i = 0; i < NBUCKETS; i++) {
		struct entry *head = &hashmap->buckets[i];
		struct entry *entry;
		struct entry *prev;
		bool remove;

		if (head->next == NULL)
			continue;

		entry = head;
		prev = NULL;

		while (true) {
			remove = function(entry->key, entry->value, user_data);

			if (!remove)
				goto next;

			nremoved += 1;
			hashmap->entries -= 1;

			if (entry == head) {
				if (entry->next == head) {
					free_key(hashmap, entry->key);
					head->key = NULL;
					head->value = NULL;
					head->hash = 0;
					head->next = NULL;
					break;
				} else {
					entry = entry->next;
					free_key(hashmap, head->key);
					head->key = entry->key;
					head->value = entry->value;
					head->hash = entry->hash;
					head->next = entry->next;
					l_free(entry);
					entry = head;
					continue;
				}
			} else {
				prev->next = entry->next;
				free_key(hashmap, entry->key);
				l_free(entry);
				entry = prev->next;
				if (entry == head)
					break;
				continue;
			}

next:
			if (entry->next == head)
				break;

			prev = entry;
			entry = entry->next;
		}
	}

	return nremoved;
}

/**
 * l_hashmap_size:
 * @hashmap: hash table object
 *
 * Returns: entries in the hash table
 **/
LIB_EXPORT unsigned int l_hashmap_size(struct l_hashmap *hashmap)
{
	if (unlikely(!hashmap))
		return 0;

	return hashmap->entries;
}

/**
 * l_hashmap_isempty:
 * @hashmap: hash table object
 *
 * Returns: #true if hash table is empty and #false if not
 **/
LIB_EXPORT bool l_hashmap_isempty(struct l_hashmap *hashmap)
{
	if (unlikely(!hashmap))
		return true;

	return hashmap->entries == 0;
}