CoreFW  map.c at [ebf63ac6c8]

File src/map.c artifact c5e3bf3b39 part of check-in ebf63ac6c8

/*
 * Copyright (c) 2012, Jonathan Schleifer <js@webkeks.org>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <stdlib.h>

#include "object.h"
#include "map.h"
#include "hash.h"

static struct bucket {
	CFWObject *key, *obj;
	uint32_t hash;
} deleted = { NULL, NULL, 0 };

struct CFWMap {
	CFWObject obj;
	struct bucket **data;
	uint32_t size;
	size_t items;
};

static bool
ctor(void *ptr, va_list args)
{
	CFWMap *map = ptr;
	void *key;

	map->data = NULL;
	map->size = 0;
	map->items = 0;

	while ((key = va_arg(args, void*)) != NULL)
		if (!cfw_map_set(map, key, va_arg(args, void*)))
			return false;

	return true;
}

static void
dtor(void *ptr)
{
	CFWMap *map = ptr;
	uint32_t i;

	for (i = 0; i < map->size; i++) {
		if (map->data[i] != NULL && map->data[i] != &deleted) {
			cfw_unref(map->data[i]->key);
			cfw_unref(map->data[i]->obj);
		}
	}

	if (map->data != NULL)
		free(map->data);
}

static bool
equal(void *ptr1, void *ptr2)
{
	CFWObject *obj2 = ptr2;
	CFWMap *map1, *map2;
	uint32_t i;

	if (obj2->cls != cfw_map)
		return false;

	map1 = ptr1;
	map2 = ptr2;

	if (map1->items != map2->items)
		return false;

	for (i = 0; i < map1->size; i++)
		if (map1->data[i] != NULL && map1->data[i] != &deleted &&
		    !cfw_equal(cfw_map_get(map2, map1->data[i]->key),
		    map1->data[i]->obj))
			return false;

	return true;
}

static uint32_t
hash(void *ptr)
{
	CFWMap *map = ptr;
	uint32_t i, hash = 0;

	for (i = 0; i < map->size; i++) {
		if (map->data[i] != NULL && map->data[i] != &deleted) {
			hash += map->data[i]->hash;
			hash += cfw_hash(map->data[i]->obj);
		}
	}

	return hash;
}

static void*
copy(void *ptr)
{
	CFWMap *map = ptr;
	CFWMap *new;
	uint32_t i;

	if ((new = cfw_new(cfw_map, NULL)) == NULL)
		return NULL;

	if ((new->data = malloc(sizeof(*new->data) * map->size)) == NULL)
		return NULL;
	new->size = map->size;

	for (i = 0; i < map->size; i++) {
		if (map->data[i] != NULL && map->data[i] != &deleted) {
			struct bucket *bucket;

			if ((bucket = malloc(sizeof(*bucket))) == NULL)
				return NULL;

			bucket->key = cfw_ref(map->data[i]->key);
			bucket->obj = cfw_ref(map->data[i]->obj);
			bucket->hash = map->data[i]->hash;

			new->data[i] = bucket;
		} else
			new->data[i] = NULL;
	}

	return new;
}

bool
resize(CFWMap *map, uint32_t items)
{
	size_t fullness = items * 4 / map->size;
	struct bucket **ndata;
	uint32_t i, nsize;

	if (items > UINT32_MAX)
		return false;

	if (fullness >= 3)
		nsize = map->size << 1;
	else if (fullness <= 1)
		nsize = map->size >> 1;
	else
		return true;

	if (nsize == 0)
		return false;

	if ((ndata = malloc(nsize * sizeof(*ndata))) == NULL)
		return false;

	for (i = 0; i < nsize; i++)
		ndata[i] = NULL;

	for (i = 0; i < map->size; i++) {
		if (map->data[i] != NULL && map->data[i] != &deleted) {
			uint32_t j, last;

			last = nsize;

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

			/* In case the last bucket is already used */
			if (j >= last) {
				last = map->data[i]->hash & (nsize - 1);

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

			if (j >= last) {
				free(ndata);
				return false;
			}

			ndata[j] = map->data[i];
		}
	}

	free(map->data);
	map->data = ndata;
	map->size = nsize;

	return true;
}

size_t
cfw_map_size(CFWMap *map)
{
	return map->items;
}

void*
cfw_map_get(CFWMap *map, void *key)
{
	uint32_t i, hash, last;

	if (key == NULL)
		return NULL;

	hash = cfw_hash(key);
	last = map->size;

	for (i = hash & (map->size - 1);
	    i < last && map->data[i] != NULL; i++) {
		if (map->data[i] == &deleted)
			continue;

		if (cfw_equal(map->data[i]->key, key))
			return map->data[i]->obj;
	}

	if (i < last)
		return NULL;

	/* In case the last bucket is already used */
	last = hash & (map->size - 1);

	for (i = 0; i < last && map->data[i] != NULL; i++) {
		if (map->data[i] == &deleted)
			continue;

		if (cfw_equal(map->data[i]->key, key))
			return map->data[i]->obj;
	}

	return NULL;
}

bool
cfw_map_set(CFWMap *map, void *key, void *obj)
{
	uint32_t i, hash, last;

	if (key == NULL)
		return false;

	if (map->data == NULL) {
		if ((map->data = malloc(sizeof(*map->data))) == NULL)
			return false;

		map->data[0] = NULL;
		map->size = 1;
		map->items = 0;
	}

	hash = cfw_hash(key);
	last = map->size;

	for (i = hash & (map->size - 1);
	    i < last && map->data[i] != NULL; i++) {
		if (map->data[i] == &deleted)
			continue;

		if (cfw_equal(map->data[i]->key, key))
			break;
	}

	/* In case the last bucket is already used */
	if (i >= last) {
		last = hash & (map->size - 1);

		for (i = 0; i < last && map->data[i] != NULL; i++) {
			if (map->data[i] == &deleted)
				continue;

			if (cfw_equal(map->data[i]->key, key))
				break;
		}
	}

	/* Key not in dictionary */
	if (i >= last || map->data[i] == NULL || map->data[i] == &deleted ||
	    !cfw_equal(map->data[i]->key, key)) {
		struct bucket *bucket;

		if (obj == NULL)
			return true;

		if (!resize(map, map->items + 1))
			return false;

		last = map->size;

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

		/* In case the last bucket is already used */
		if (i >= last) {
			last = hash & (map->size - 1);

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

		if (i >= last)
			return false;

		if ((bucket = malloc(sizeof(*bucket))) == NULL)
			return false;

		if ((bucket->key = cfw_copy(key)) == NULL)
			return false;

		bucket->obj = cfw_ref(obj);
		bucket->hash = cfw_hash(key);

		map->data[i] = bucket;
		map->items++;

		return true;
	}

	if (obj != NULL) {
		void *old = map->data[i]->obj;
		map->data[i]->obj = cfw_ref(obj);
		cfw_unref(old);
	} else {
		cfw_unref(map->data[i]->key);
		cfw_unref(map->data[i]->obj);

		free(map->data[i]);
		map->data[i] = &deleted;

		map->items--;

		if (!resize(map, map->items))
			return false;
	}

	return true;
}

void
cfw_map_iter(CFWMap *map, cfw_map_iter_t *iter)
{
	iter->_map = map;
	iter->_pos = 0;

	cfw_map_iter_next(iter);
}

void
cfw_map_iter_next(cfw_map_iter_t *iter)
{
	CFWMap *map = iter->_map;

	for (; iter->_pos < map->size &&
	    (map->data[iter->_pos] == NULL ||
	    map->data[iter->_pos] == &deleted); iter->_pos++);

	if (iter->_pos < map->size) {
		iter->key = map->data[iter->_pos]->key;
		iter->obj = map->data[iter->_pos]->obj;
		iter->_pos++;
	} else {
		iter->key = NULL;
		iter->obj = NULL;
	}
}

static CFWClass class = {
	.name = "CFWMap",
	.size = sizeof(CFWMap),
	.ctor = ctor,
	.dtor = dtor,
	.equal = equal,
	.hash = hash,
	.copy = copy
};
CFWClass *cfw_map = &class;