Index: src/Makefile
==================================================================
--- src/Makefile
+++ src/Makefile
@@ -2,14 +2,15 @@
 LIB_MAJOR = 0
 LIB_MINOR = 0
 
 SRCS = array.c	\
        class.c	\
+       map.c	\
        object.c	\
        range.c	\
        string.c
 
 INCLUDES = ${SRCS:.c=.h}	\
 	   corefw.h		\
 	   hash.h
 
 include ../buildsys.mk

ADDED   src/map.c
Index: src/map.c
==================================================================
--- src/map.c
+++ src/map.c
@@ -0,0 +1,367 @@
+/*
+ * 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 = {};
+
+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;
+}
+
+static CFWClass class = {
+	.name = "CFWMap",
+	.size = sizeof(CFWMap),
+	.ctor = ctor,
+	.dtor = dtor,
+	.equal = equal,
+	.hash = hash,
+	.copy = copy
+};
+CFWClass *cfw_map = &class;

ADDED   src/map.h
Index: src/map.h
==================================================================
--- src/map.h
+++ src/map.h
@@ -0,0 +1,38 @@
+/*
+ * 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.
+ */
+
+#ifndef __COREFW_MAP_H__
+#define __COREFW_MAP_H__
+
+#include "class.h"
+
+typedef struct CFWMap CFWMap;
+extern CFWClass *cfw_map;
+extern size_t cfw_map_size(CFWMap*);
+extern void* cfw_map_get(CFWMap*, void*);
+extern bool cfw_map_set(CFWMap*, void*, void*);
+
+#endif

Index: tests/tests.c
==================================================================
--- tests/tests.c
+++ tests/tests.c
@@ -27,16 +27,18 @@
 #include <stdio.h>
 
 #include "object.h"
 #include "string.h"
 #include "array.h"
+#include "map.h"
 
 int
 main()
 {
 	CFWString *s[3];
 	CFWArray *a;
+	CFWMap *m;
 	size_t i;
 
 	s[0] = cfw_new(cfw_string, "Hallo");
 	s[1] = cfw_new(cfw_string, " Welt");
 	s[2] = cfw_new(cfw_string, "!");
@@ -59,8 +61,29 @@
 	s[1] = cfw_new(cfw_string, "ll");
 	printf("%zd\n", cfw_string_find(s[0], s[1], cfw_range_all));
 	cfw_unref(s[1]);
 
 	cfw_unref(s[0]);
+
+	s[0] = cfw_new(cfw_string, "Hallo");
+	s[1] = cfw_new(cfw_string, "Welt!");
+
+	m = cfw_new(cfw_map, s[0], s[1], NULL);
+
+	cfw_unref(s[1]);
+
+	puts(cfw_string_c(cfw_map_get(m, s[0])));
+
+	s[1] = cfw_new(cfw_string, "Test");
+	cfw_map_set(m, s[0], s[1]);
+	cfw_unref(s[1]);
+
+	puts(cfw_string_c(cfw_map_get(m, s[0])));
+
+	cfw_map_set(m, s[0], NULL);
+	printf("%p\n", cfw_map_get(m, s[0]));
+
+	cfw_unref(s[0]);
+	cfw_unref(m);
 
 	return 0;
 }