cannam@226: /*
cannam@226:   Copyright 2011-2014 David Robillard <http://drobilla.net>
cannam@226: 
cannam@226:   Permission to use, copy, modify, and/or distribute this software for any
cannam@226:   purpose with or without fee is hereby granted, provided that the above
cannam@226:   copyright notice and this permission notice appear in all copies.
cannam@226: 
cannam@226:   THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
cannam@226:   WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
cannam@226:   MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
cannam@226:   ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
cannam@226:   WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
cannam@226:   ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
cannam@226:   OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
cannam@226: */
cannam@226: 
cannam@226: #include <assert.h>
cannam@226: #include <stdint.h>
cannam@226: #include <stdlib.h>
cannam@226: #include <string.h>
cannam@226: 
cannam@245: #include "hash.h"
cannam@226: 
cannam@226: /**
cannam@226:    Primes, each slightly less than twice its predecessor, and as far away
cannam@226:    from powers of two as possible.
cannam@226: */
cannam@226: static const unsigned sizes[] = {
cannam@226: 	53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
cannam@226: 	196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
cannam@226: 	50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 0
cannam@226: };
cannam@226: 
cannam@226: typedef struct ZixHashEntry {
cannam@226: 	struct ZixHashEntry* next;  ///< Next entry in bucket
cannam@226: 	uint32_t             hash;  ///< Non-modulo hash value
cannam@226: 	// Value follows here (access with zix_hash_value)
cannam@226: } ZixHashEntry;
cannam@226: 
cannam@226: struct ZixHashImpl {
cannam@226: 	ZixHashFunc     hash_func;
cannam@226: 	ZixEqualFunc    equal_func;
cannam@226: 	ZixHashEntry**  buckets;
cannam@226: 	const unsigned* n_buckets;
cannam@226: 	size_t          value_size;
cannam@226: 	unsigned        count;
cannam@226: };
cannam@226: 
cannam@226: static inline void*
cannam@226: zix_hash_value(ZixHashEntry* entry)
cannam@226: {
cannam@226: 	return entry + 1;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixHash*
cannam@226: zix_hash_new(ZixHashFunc  hash_func,
cannam@226:              ZixEqualFunc equal_func,
cannam@226:              size_t       value_size)
cannam@226: {
cannam@226: 	ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
cannam@226: 	if (hash) {
cannam@226: 		hash->hash_func  = hash_func;
cannam@226: 		hash->equal_func = equal_func;
cannam@226: 		hash->n_buckets  = &sizes[0];
cannam@226: 		hash->value_size = value_size;
cannam@226: 		hash->count      = 0;
cannam@226: 		if (!(hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
cannam@226: 		                                             sizeof(ZixHashEntry*)))) {
cannam@226: 			free(hash);
cannam@226: 			return NULL;
cannam@226: 		}
cannam@226: 	}
cannam@226: 	return hash;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API void
cannam@226: zix_hash_free(ZixHash* hash)
cannam@226: {
cannam@226: 	for (unsigned b = 0; b < *hash->n_buckets; ++b) {
cannam@226: 		ZixHashEntry* bucket = hash->buckets[b];
cannam@226: 		for (ZixHashEntry* e = bucket; e;) {
cannam@226: 			ZixHashEntry* next = e->next;
cannam@226: 			free(e);
cannam@226: 			e = next;
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	free(hash->buckets);
cannam@226: 	free(hash);
cannam@226: }
cannam@226: 
cannam@226: ZIX_API size_t
cannam@226: zix_hash_size(const ZixHash* hash)
cannam@226: {
cannam@226: 	return hash->count;
cannam@226: }
cannam@226: 
cannam@226: static inline void
cannam@226: insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry)
cannam@226: {
cannam@226: 	entry->next = *bucket;
cannam@226: 	*bucket     = entry;
cannam@226: }
cannam@226: 
cannam@226: static inline ZixStatus
cannam@226: rehash(ZixHash* hash, unsigned new_n_buckets)
cannam@226: {
cannam@226: 	ZixHashEntry** new_buckets = (ZixHashEntry**)calloc(
cannam@226: 		new_n_buckets, sizeof(ZixHashEntry*));
cannam@226: 	if (!new_buckets) {
cannam@226: 		return ZIX_STATUS_NO_MEM;
cannam@226: 	}
cannam@226: 
cannam@226: 	const unsigned old_n_buckets = *hash->n_buckets;
cannam@226: 	for (unsigned b = 0; b < old_n_buckets; ++b) {
cannam@226: 		for (ZixHashEntry* e = hash->buckets[b]; e;) {
cannam@226: 			ZixHashEntry* const next = e->next;
cannam@226: 			const unsigned      h    = e->hash % new_n_buckets;
cannam@226: 			insert_entry(&new_buckets[h], e);
cannam@226: 			e = next;
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	free(hash->buckets);
cannam@226: 	hash->buckets = new_buckets;
cannam@226: 
cannam@226: 	return ZIX_STATUS_SUCCESS;
cannam@226: }
cannam@226: 
cannam@226: static inline ZixHashEntry*
cannam@226: find_entry(const ZixHash* hash,
cannam@226:            const void*    key,
cannam@226:            const unsigned h,
cannam@226:            const unsigned h_nomod)
cannam@226: {
cannam@226: 	for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
cannam@226: 		if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) {
cannam@226: 			return e;
cannam@226: 		}
cannam@226: 	}
cannam@226: 	return NULL;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API const void*
cannam@226: zix_hash_find(const ZixHash* hash, const void* value)
cannam@226: {
cannam@226: 	const unsigned h_nomod = hash->hash_func(value);
cannam@226: 	const unsigned h       = h_nomod % *hash->n_buckets;
cannam@226: 	ZixHashEntry* const entry = find_entry(hash, value, h, h_nomod);
cannam@226: 	return entry ? zix_hash_value(entry) : 0;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixStatus
cannam@226: zix_hash_insert(ZixHash* hash, const void* value, const void** inserted)
cannam@226: {
cannam@226: 	unsigned h_nomod = hash->hash_func(value);
cannam@226: 	unsigned h       = h_nomod % *hash->n_buckets;
cannam@226: 
cannam@226: 	ZixHashEntry* elem = find_entry(hash, value, h, h_nomod);
cannam@226: 	if (elem) {
cannam@226: 		assert(elem->hash == h_nomod);
cannam@226: 		if (inserted) {
cannam@226: 			*inserted = zix_hash_value(elem);
cannam@226: 		}
cannam@226: 		return ZIX_STATUS_EXISTS;
cannam@226: 	}
cannam@226: 
cannam@226: 	elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size);
cannam@226: 	if (!elem) {
cannam@226: 		return ZIX_STATUS_NO_MEM;
cannam@226: 	}
cannam@226: 	elem->next = NULL;
cannam@226: 	elem->hash = h_nomod;
cannam@226: 	memcpy(elem + 1, value, hash->value_size);
cannam@226: 
cannam@226: 	const unsigned next_n_buckets = *(hash->n_buckets + 1);
cannam@226: 	if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) {
cannam@226: 		if (!rehash(hash, next_n_buckets)) {
cannam@226: 			h = h_nomod % *(++hash->n_buckets);
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	insert_entry(&hash->buckets[h], elem);
cannam@226: 	++hash->count;
cannam@226: 	if (inserted) {
cannam@226: 		*inserted = zix_hash_value(elem);
cannam@226: 	}
cannam@226: 	return ZIX_STATUS_SUCCESS;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API ZixStatus
cannam@226: zix_hash_remove(ZixHash* hash, const void* value)
cannam@226: {
cannam@226: 	const unsigned h_nomod = hash->hash_func(value);
cannam@226: 	const unsigned h       = h_nomod % *hash->n_buckets;
cannam@226: 
cannam@226: 	ZixHashEntry** next_ptr = &hash->buckets[h];
cannam@226: 	for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
cannam@226: 		if (h_nomod == e->hash &&
cannam@226: 			hash->equal_func(zix_hash_value(e), value)) {
cannam@226: 			*next_ptr = e->next;
cannam@226: 			free(e);
cannam@226: 			return ZIX_STATUS_SUCCESS;
cannam@226: 		}
cannam@226: 		next_ptr = &e->next;
cannam@226: 	}
cannam@226: 
cannam@226: 	if (hash->n_buckets != sizes) {
cannam@226: 		const unsigned prev_n_buckets = *(hash->n_buckets - 1);
cannam@226: 		if (hash->count - 1 <= prev_n_buckets) {
cannam@226: 			if (!rehash(hash, prev_n_buckets)) {
cannam@226: 				--hash->n_buckets;
cannam@226: 			}
cannam@226: 		}
cannam@226: 	}
cannam@226: 
cannam@226: 	--hash->count;
cannam@226: 	return ZIX_STATUS_NOT_FOUND;
cannam@226: }
cannam@226: 
cannam@226: ZIX_API void
cannam@226: zix_hash_foreach(ZixHash*         hash,
cannam@226:                  ZixHashVisitFunc f,
cannam@226:                  void*            user_data)
cannam@226: {
cannam@226: 	for (unsigned b = 0; b < *hash->n_buckets; ++b) {
cannam@226: 		ZixHashEntry* bucket = hash->buckets[b];
cannam@226: 		for (ZixHashEntry* e = bucket; e; e = e->next) {
cannam@226: 			f(zix_hash_value(e), user_data);
cannam@226: 		}
cannam@226: 	}
cannam@226: }