Mercurial > hg > webserver / file diff

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/server/ucx/map.c	Sat Jan 14 14:33:38 2012 +0100
@@ -0,0 +1,118 @@
+/*
+ *
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "map.h"
+
+UcxMap *ucx_map_new(size_t size) {
+    UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
+    if(map == NULL) {
+        return NULL;
+    }
+
+    map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement));
+    if(map->map == NULL) {
+        free(map);
+        return NULL;
+    }
+    map->size = size;
+
+    return map;
+}
+
+int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
+    if(key.hash == 0) {
+        key.hash = ucx_hash((char*)key.data, key.len);
+    }
+    void *kd = malloc(key.len);
+    memcpy(kd, key.data, key.len);
+    key.data = kd;
+
+    UcxMapElement *elm = &map->map[key.hash%map->size];
+    if(elm->next != NULL) {
+        while(elm->next != NULL) {
+            elm = elm->next;
+        }
+        UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
+        if(e == NULL) {
+            return -1;
+        }
+        elm->next = e;
+        elm = e;
+    }
+
+    elm->key = key;
+    elm->data = data;
+
+    return 0;
+}
+
+void* ucx_map_get(UcxMap *map, UcxKey key) {
+    if(key.hash == 0) {
+        key.hash = ucx_hash((char*)key.data, key.len);
+    }
+    
+    UcxMapElement *elm = &map->map[key.hash%map->size];
+    while(elm != NULL) {
+        if(elm->key.hash == key.hash) {
+            int n = (key.len > elm->key.len) ? elm->key.len : key.len;
+            if(memcmp(elm->key.data, key.data, n) == 0) {
+                return elm->data;
+            }
+        }
+        elm = elm->next;
+    }
+
+    return NULL;
+}
+
+UcxKey ucx_key(void *data, size_t len) {
+    UcxKey key;
+    key.data = data;
+    key.len = len;
+    key.hash = ucx_hash(data, len);
+    return key;
+}
+
+
+int ucx_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;
+}