ObjFW  Diff

#include <stdint.h>
#include <string.h>

#import "runtime.h"
#import "runtime-private.h"

uint32_t
objc_hash_string(const char *str)
objc_hash_string(const void *str_)
{
	const char *str = str_;
	uint32_t hash = 0;

	while (*str != 0) {
		hash += *str;
		hash += (hash << 10);
		hash ^= (hash >> 6);
		str++;
	}

	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);

	return hash;
}

bool
objc_equal_string(const void *obj1, const void *obj2)
{
	return !strcmp(obj1, obj2);
}

struct objc_hashtable*
objc_hashtable_new(uint32_t size)
objc_hashtable_new(uint32_t (*hash)(const void*),
    bool (*equal)(const void*, const void*), uint32_t size)
{
	struct objc_hashtable *h;
	struct objc_hashtable *table;
	uint32_t i;

	if ((h = malloc(sizeof(struct objc_hashtable))) == NULL)
	if ((table = malloc(sizeof(struct objc_hashtable))) == NULL)
		OBJC_ERROR("Not enough memory to allocate hash table!");

	table->hash = hash;
	table->equal = equal;

	h->count = 0;
	h->last_idx = size - 1;
	h->data = malloc(size * sizeof(struct objc_hashtable_bucket*));
	table->count = 0;
	table->size = size;
	table->data = calloc(size, sizeof(struct objc_hashtable_bucket*));

	if (h->data == NULL)
	if (table->data == NULL)
		OBJC_ERROR("Not enough memory to allocate hash table!");

	for (i = 0; i < size; i++)
		h->data[i] = NULL;

	return h;
	return table;
}

static void
insert(struct objc_hashtable *h, const char *key, const void *obj)
insert(struct objc_hashtable *table, const void *key, const void *obj)
{
	uint32_t i, hash, last;
	struct objc_hashtable_bucket *bucket;

	hash = objc_hash_string(key);
	hash = table->hash(key);

	if (h->count + 1 > UINT32_MAX / 4)
	if (table->count + 1 > UINT32_MAX / 4)
		OBJC_ERROR("Integer overflow!");

	if ((h->count + 1) * 4 / (h->last_idx + 1) >= 3) {
		struct objc_hashtable_bucket **ndata;
		uint32_t nsize = (h->last_idx + 1) * 2;
	if ((table->count + 1) * 4 / table->size >= 3) {
		struct objc_hashtable_bucket **newData;
		uint32_t newSize;

		if (nsize == 0)
		if (table->size > UINT32_MAX / 2)
			OBJC_ERROR("Integer overflow!");

		newSize = table->size * 2;

		if ((newData = calloc(newSize,
		ndata = malloc(nsize * sizeof(struct objc_hashtable_bucket*));
		    sizeof(struct objc_hashtable_bucket*))) == NULL)
		if (ndata == NULL)
			OBJC_ERROR("Not enough memory to insert into hash "
			    "table!");

		for (i = 0; i < nsize; i++)
		for (i = 0; i < table->size; i++) {
			ndata[i] = NULL;

		for (i = 0; i <= h->last_idx; i++) {
			if (h->data[i] != NULL) {
			if (table->data[i] != NULL) {
				uint32_t j;

				last = nsize;
				last = newSize;

				for (j = h->data[i]->hash & (nsize - 1);
				    j < last && ndata[j] != NULL; j++);
				for (j = table->data[i]->hash & (newSize - 1);
				    j < last && newData[j] != NULL; j++);

				if (j >= last) {
					last = h->data[i]->hash & (nsize - 1);
					last = table->data[i]->hash &
					    (newSize - 1);

					for (j = 0; j < last &&
					    ndata[j] != NULL; j++);
					    newData[j] != NULL; j++);
				}

				if (j >= last)
					OBJC_ERROR("No free bucket!");

				ndata[j] = h->data[i];
				newData[j] = table->data[i];
			}
		}

		free(h->data);
		h->data = ndata;
		h->last_idx = nsize - 1;
		free(table->data);
		table->data = newData;
		table->size = newSize;
	}

	last = h->last_idx + 1;
	last = table->size;

	for (i = hash & (table->size - 1);
	for (i = hash & h->last_idx; i < last && h->data[i] != NULL; i++);
	    i < last && table->data[i] != NULL; i++);

	if (i >= last) {
		last = hash & h->last_idx;
		last = hash & (table->size - 1);

		for (i = 0; i < last && h->data[i] != NULL; i++);
		for (i = 0; i < last && table->data[i] != NULL; i++);
	}

	if (i >= last)
		OBJC_ERROR("No free bucket!");

	if ((bucket = malloc(sizeof(struct objc_hashtable_bucket))) == NULL)
		OBJC_ERROR("Not enough memory to allocate hash table bucket!");

	bucket->key = key;
	bucket->hash = hash;
	bucket->obj = obj;

	h->data[i] = bucket;
	h->count++;
	table->data[i] = bucket;
	table->count++;
}

static inline int64_t
index_for_key(struct objc_hashtable *h, const char *key)
index_for_key(struct objc_hashtable *table, const void *key)
{
	uint32_t i, hash;

	hash = objc_hash_string(key) & h->last_idx;
	hash = table->hash(key) & (table->size - 1);

	for (i = hash; i <= h->last_idx && h->data[i] != NULL; i++)
		if (!strcmp(h->data[i]->key, key))
	for (i = hash; i < table->size && table->data[i] != NULL; i++)
		if (table->equal(table->data[i]->key, key))
			return i;

	if (i <= h->last_idx)
	if (i < table->size)
		return -1;

	for (i = 0; i < hash && h->data[i] != NULL; i++)
		if (!strcmp(h->data[i]->key, key))
	for (i = 0; i < hash && table->data[i] != NULL; i++)
		if (table->equal(table->data[i]->key, key))
			return i;

	return -1;
}

void
objc_hashtable_set(struct objc_hashtable *h, const char *key, const void *obj)
objc_hashtable_set(struct objc_hashtable *table, const void *key,
    const void *obj)
{
	int64_t idx = index_for_key(h, key);
	int64_t idx = index_for_key(table, key);

	if (idx < 0) {
		insert(h, key, obj);
		insert(table, key, obj);
		return;
	}

	h->data[idx]->obj = obj;
	table->data[idx]->obj = obj;
}

void*
objc_hashtable_get(struct objc_hashtable *h, const char *key)
objc_hashtable_get(struct objc_hashtable *table, const void *key)
{
	int64_t idx = index_for_key(h, key);
	int64_t idx = index_for_key(table, key);

	if (idx < 0)
		return NULL;

	return (void*)h->data[idx]->obj;
	return (void*)table->data[idx]->obj;
}

void
objc_hashtable_free(struct objc_hashtable *h)
objc_hashtable_free(struct objc_hashtable *table)
{
	uint32_t i;

	for (i = 0; i <= h->last_idx; i++)
		if (h->data[i] != NULL)
			free(h->data[i]);
	for (i = 0; i < table->size; i++)
		if (table->data[i] != NULL)
			free(table->data[i]);

	free(h->data);
	free(h);
	free(table->data);
	free(table);
}