Mercurial > hg > ucx / changeset

--- a/test/Makefile	Wed Jan 11 12:19:48 2012 +0100
+++ b/test/Makefile	Sat Jan 14 13:07:18 2012 +0100
@@ -28,7 +28,7 @@
 
 include ../$(CONF).mk
 
-SRC = main.c list_tests.c mpool_tests.c
+SRC = main.c list_tests.c mpool_tests.c map_tests.c
 
 OBJ = $(SRC:%.c=../build/%.$(OBJ_EXT))
 

--- a/test/main.c	Wed Jan 11 12:19:48 2012 +0100
+++ b/test/main.c	Sat Jan 14 13:07:18 2012 +0100
@@ -31,6 +31,7 @@
 
 #include "list_tests.h"
 #include "mpool_tests.h"
+#include "map_tests.h"
 
 int main(int argc, char **argv) {
     printf("UCX Tests\n---------\n");
@@ -46,6 +47,11 @@
     if(mpool_tests()) {
         fprintf(stderr, "mpool_tests failed\n");
     }
+
+    printf("\nUcxMap Tests\n");
+    if(map_tests()) {
+        fprintf(stderr, "map_tests failed\n");
+    }
     
     return EXIT_SUCCESS; 
 }

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/map_tests.c	Sat Jan 14 13:07:18 2012 +0100
@@ -0,0 +1,44 @@
+/*
+ *
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "map_tests.h"
+
+int map_tests() {
+    printf("   Test ucx_map_new\n");
+    UcxMap *map = ucx_map_new(16);
+    if(map == NULL) {
+        return -1;
+    }
+
+    printf("   Test ucx_map_put\n");
+    char *txt = "text/plain";
+    char *xml = "text/xml";
+    ucx_map_cstr_put(map, "txt", txt);
+    ucx_map_cstr_put(map, "xml", xml);
+
+    printf("   Test ucx_map_get\n");
+    if(ucx_map_cstr_get(map, "txt") != txt) {
+        fprintf(stderr, "ucx_map_get failed\n");
+        return -1;
+    }
+    char xmlkey[4];
+    xmlkey[0] = 'x';
+    xmlkey[1] = 'm';
+    xmlkey[2] = 'l';
+    xmlkey[3] = 0;
+    if(ucx_map_cstr_get(map, xmlkey) != xml) {
+        fprintf(stderr, "ucx_map_get failed\n");
+        return -1;
+    }
+    if(ucx_map_cstr_get(map, "nokey") != NULL) {
+        fprintf(stderr, "ucx_map_get failed\n");
+        return -1;
+    }
+
+    return 0;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/map_tests.h	Sat Jan 14 13:07:18 2012 +0100
@@ -0,0 +1,22 @@
+/* 
+ *
+ */
+
+#ifndef MAP_TESTS_H
+#define	MAP_TESTS_H
+
+#include "ucx/map.h"
+
+#ifdef	__cplusplus
+extern "C" {
+#endif
+
+int map_tests();
+
+
+#ifdef	__cplusplus
+}
+#endif
+
+#endif	/* MAP_TESTS_H */
+

--- a/ucx/Makefile	Wed Jan 11 12:19:48 2012 +0100
+++ b/ucx/Makefile	Sat Jan 14 13:07:18 2012 +0100
@@ -29,7 +29,7 @@
 include ../$(CONF).mk
 
 # list of source files
-SRC = list.c dlist.c map.c mempool.c
+SRC = list.c dlist.c map.c mempool.c string.o
 
 OBJ = $(SRC:%.c=../build/%.$(OBJ_EXT))
 

--- a/ucx/map.c	Wed Jan 11 12:19:48 2012 +0100
+++ b/ucx/map.c	Sat Jan 14 13:07:18 2012 +0100
@@ -1,1 +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;
+}

--- a/ucx/map.h	Wed Jan 11 12:19:48 2012 +0100
+++ b/ucx/map.h	Sat Jan 14 13:07:18 2012 +0100
@@ -5,12 +5,48 @@
 #ifndef MAP_H
 #define	MAP_H
 
+#include "ucx.h"
+#include "string.h"
+
 #ifdef	__cplusplus
 extern "C" {
 #endif
 
+typedef struct UcxMap        UcxMap;
+typedef struct UcxKey        UcxKey;
+typedef struct UcxMapElement UcxMapElement;
+
+struct UcxMap {
+    UcxMapElement *map;
+    size_t        size;
+};
+
+struct UcxKey {
+    void   *data;
+    size_t len;
+    int    hash;
+};
+
+struct UcxMapElement {
+    void          *data;
+    UcxMapElement *next;
+    UcxKey        key;
+};
 
 
+UcxMap *ucx_map_new(size_t size);
+
+int ucx_map_put(UcxMap *map, UcxKey key, void *data);
+void* ucx_map_get(UcxMap *map, UcxKey key);
+
+#define ucx_map_sstr_put(m, s, d) ucx_map_put(m, ucx_key(s.ptr, s.length), d)
+#define ucx_map_cstr_put(m, s, d) ucx_map_put(m, ucx_key(s, strlen(s)), d)
+#define ucx_map_sstr_get(m, s) ucx_map_get(m, ucx_key(s.ptr, s.length))
+#define ucx_map_cstr_get(m, s) ucx_map_get(m, ucx_key(s, strlen(s)))
+
+UcxKey ucx_key(void *data, size_t len);
+
+int ucx_hash(char *data, size_t len);
 
 #ifdef	__cplusplus
 }

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ucx/string.c	Sat Jan 14 13:07:18 2012 +0100
@@ -0,0 +1,99 @@
+/*
+ * File:   sstring.c
+ * Author: olaf
+ *
+ * Created on 17. Juni 2010, 13:27
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+
+#include "string.h"
+
+sstr_t sstr (char *s) {
+    sstr_t string;
+    string.ptr = s;
+    string.length = strlen(s);
+    return string;
+}
+
+sstr_t sstrn (char *s, size_t n) {
+    sstr_t string;
+    string.ptr = s;
+    string.length = n;
+    return string;
+}
+
+size_t sstrnlen (size_t n, sstr_t s, ...) {
+    va_list ap;
+    size_t size = s.length;
+    va_start(ap, s);
+
+    for (int i=0;i<n-1;i++) {
+        sstr_t str = va_arg(ap, sstr_t);
+        size += str.length;
+    }
+
+    return size;
+}
+
+sstr_t sstrcat (sstr_t s, ...) {
+    va_list ap;
+    va_start(ap, s);
+    s.ptr[0] = 0;
+
+    sstr_t str = va_arg (ap, sstr_t);
+    while (str.ptr != NULL) {
+        s.ptr = strncat (s.ptr, str.ptr, s.length);
+        str = va_arg (ap, sstr_t);
+    }
+
+    return s;
+}
+
+sstr_t sstrncat (size_t n, sstr_t s, sstr_t c1, ...) {
+    va_list ap;
+    va_start(ap, c1);
+    s.ptr[0] = 0;
+
+    s.ptr = strncat (s.ptr, c1.ptr, s.length);
+    for (int i=0;i<n-1;i++) {
+        sstr_t str = va_arg (ap, sstr_t);
+        s.ptr = strncat (s.ptr, str.ptr, s.length);
+    }
+
+    return s;
+}
+
+sstr_t sstrsubs (sstr_t s, size_t start) {
+    return sstrsubsl (s, start, s.length-start);
+}
+
+sstr_t sstrsubsl (sstr_t s, size_t start, size_t length) {
+    sstr_t new_sstr;
+    if (start < 0 || start >= s.length || length < 0) {
+        return s;
+    }
+    if (length > s.length-start) {
+        length = s.length-start;
+    }
+    new_sstr.ptr = &s.ptr[start];
+    new_sstr.length = length;
+    return new_sstr;
+}
+
+int sstrcmp(sstr_t s1, sstr_t s2) {
+    return strncmp(s1.ptr, s2.ptr, s1.length>s2.length ? s2.length: s1.length);
+}
+
+sstr_t sstrdub(sstr_t s) {
+    sstr_t newstring;
+    newstring.ptr = malloc(s.length + 1);
+    newstring.length = s.length;
+    newstring.ptr[newstring.length] = 0;
+
+    memcpy(newstring.ptr, s.ptr, s.length);
+
+    return newstring;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ucx/string.h	Sat Jan 14 13:07:18 2012 +0100
@@ -0,0 +1,78 @@
+/*
+ * File:   sstring.h
+ * Author: olaf
+ *
+ * Created on 17. Juni 2010, 13:26
+ */
+
+#ifndef _SSTRING_H
+#define	_SSTRING_H
+
+#define S(s) { s, sizeof(s)-1 }
+#define ST(s) sstrn(s, sizeof(s)-1)
+
+#ifdef	__cplusplus
+extern "C" {
+#endif
+
+typedef struct sstring {
+    char   *ptr;
+    size_t length;
+} sstr_t;
+
+/*
+ * creates a new sstr_t from a null terminated string
+ *
+ * s  null terminated string
+ */
+sstr_t sstr (char *s);
+
+/*
+ * creates a new sstr_t from a string and length
+ *
+ * s  string
+ * n  length of string
+ */
+sstr_t sstrn (char *s, size_t n);
+
+
+/*
+ * gets the length of n sstr_t strings
+ *
+ * n    number of strings
+ * s    string
+ * ...  strings
+ */
+size_t sstrnlen (size_t n, sstr_t s, ...);
+
+
+/*
+ * concatenates n strings
+ *
+ * n    number of strings
+ * s    new string with enough memory allocated
+ * ...  strings
+ */
+sstr_t sstrncat (size_t n, sstr_t s, sstr_t c1, ...);
+
+
+/*
+ *
+ */
+sstr_t sstrsubs (sstr_t s, size_t start);
+
+/*
+ *
+ */
+sstr_t sstrsubsl (sstr_t s, size_t start, size_t end);
+
+
+int sstrcmp(sstr_t s1, sstr_t s2);
+
+sstr_t sstrdub(sstr_t s);
+
+#ifdef	__cplusplus
+}
+#endif
+
+#endif	/* _SSTRING_H */