comparison ext/sord/src/zix/hash.c @ 226:c5cdc9e6a4bf

Add these external library files

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