--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/server/util/map.c Sat Jan 14 13:53:44 2012 +0100
@@ -0,0 +1,134 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Copyright 2011 Olaf Wintermann. 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 HOLDER 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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "map.h"
+
+hashmap_t* hashmap_new(size_t size) {
+ hashmap_t *map = malloc(sizeof(hashmap_t));
+ map->map = calloc(size, sizeof(sdlist_t));
+ map->len = size;
+
+ return map;
+}
+
+void hashmap_free(hashmap_t *map) {
+ for(int i=0;i<map->len;i++) {
+ sdlist_t *list = map->map[0];
+ while(list != NULL) {
+ hashmap_elm_t *elm = (hashmap_elm_t*)list->data;
+ free(elm->key.ptr);
+ sdlist_t *l = list;
+ list = list->next;
+ free(elm);
+ free(l);
+ }
+ }
+ free(map->map);
+ free(map);
+}
+
+
+void hashmap_put(hashmap_t *map, sstr_t key, void *value) {
+ int hash = hashmap_hash(key.ptr, key.length);
+
+ sdlist_t *list = map->map[hash%map->len];
+
+ sstr_t k = sstrdub(key);
+
+ hashmap_elm_t *elm = malloc(sizeof(hashmap_elm_t));
+ elm->data = value;
+ elm->hash = hash;
+ elm->key = k;
+
+ map->map[hash%map->len] = sdlist_add(list, elm);
+}
+
+void* hashmap_get(hashmap_t *map, sstr_t key) {
+ int hash = hashmap_hash(key.ptr, key.length);
+ sdlist_t *list = map->map[hash%map->len];
+ void *value = NULL;
+
+ while (list != NULL) {
+ hashmap_elm_t *elm = list->data;
+ if (elm->hash == hash &&
+ strncmp(key.ptr, elm->key.ptr, key.length) == 0) {
+ value = elm->data;
+ break;
+ }
+ list = list->next;
+ }
+
+ return value;
+}
+
+
+
+
+/* hash function */
+int hashmap_hash(char *data, size_t len) {
+ /* murmur hash 2 */
+
+ int m = 0x5bd1e995;
+ int r = 24;
+
+ int h = 25 ^ len;
+
+ int i = 0;
+ while (len >= 4) {
+ int k = data[i + 0] & 0xFF;
+ k |= (data[i + 1] & 0xFF) << 8;
+ k |= (data[i + 2] & 0xFF) << 16;
+ k |= (data[i + 3] & 0xFF) << 24;
+
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+
+ h *= m;
+ h ^= k;
+
+ i += 4;
+ len -= 4;
+ }
+
+ switch (len) {
+ case 3: h ^= (data[i + 2] & 0xFF) << 16;
+ case 2: h ^= (data[i + 1] & 0xFF) << 8;
+ case 1: h ^= (data[i + 0] & 0xFF); h *= m;
+ }
+
+ h ^= h >> 13;
+ h *= m;
+ h ^= h >> 15;
+
+ return h;
+}