Mercurial > hg > ucx / changeset

     1.1 --- a/test/Makefile	Wed Jan 11 12:19:48 2012 +0100
     1.2 +++ b/test/Makefile	Sat Jan 14 13:07:18 2012 +0100
     1.3 @@ -28,7 +28,7 @@
     1.4  
     1.5  include ../$(CONF).mk
     1.6  
     1.7 -SRC = main.c list_tests.c mpool_tests.c
     1.8 +SRC = main.c list_tests.c mpool_tests.c map_tests.c
     1.9  
    1.10  OBJ = $(SRC:%.c=../build/%.$(OBJ_EXT))
    1.11  

     2.1 --- a/test/main.c	Wed Jan 11 12:19:48 2012 +0100
     2.2 +++ b/test/main.c	Sat Jan 14 13:07:18 2012 +0100
     2.3 @@ -31,6 +31,7 @@
     2.4  
     2.5  #include "list_tests.h"
     2.6  #include "mpool_tests.h"
     2.7 +#include "map_tests.h"
     2.8  
     2.9  int main(int argc, char **argv) {
    2.10      printf("UCX Tests\n---------\n");
    2.11 @@ -46,6 +47,11 @@
    2.12      if(mpool_tests()) {
    2.13          fprintf(stderr, "mpool_tests failed\n");
    2.14      }
    2.15 +
    2.16 +    printf("\nUcxMap Tests\n");
    2.17 +    if(map_tests()) {
    2.18 +        fprintf(stderr, "map_tests failed\n");
    2.19 +    }
    2.20      
    2.21      return EXIT_SUCCESS; 
    2.22  }

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/test/map_tests.c	Sat Jan 14 13:07:18 2012 +0100
     3.3 @@ -0,0 +1,44 @@
     3.4 +/*
     3.5 + *
     3.6 + */
     3.7 +
     3.8 +#include <stdio.h>
     3.9 +#include <stdlib.h>
    3.10 +#include <string.h>
    3.11 +
    3.12 +#include "map_tests.h"
    3.13 +
    3.14 +int map_tests() {
    3.15 +    printf("   Test ucx_map_new\n");
    3.16 +    UcxMap *map = ucx_map_new(16);
    3.17 +    if(map == NULL) {
    3.18 +        return -1;
    3.19 +    }
    3.20 +
    3.21 +    printf("   Test ucx_map_put\n");
    3.22 +    char *txt = "text/plain";
    3.23 +    char *xml = "text/xml";
    3.24 +    ucx_map_cstr_put(map, "txt", txt);
    3.25 +    ucx_map_cstr_put(map, "xml", xml);
    3.26 +
    3.27 +    printf("   Test ucx_map_get\n");
    3.28 +    if(ucx_map_cstr_get(map, "txt") != txt) {
    3.29 +        fprintf(stderr, "ucx_map_get failed\n");
    3.30 +        return -1;
    3.31 +    }
    3.32 +    char xmlkey[4];
    3.33 +    xmlkey[0] = 'x';
    3.34 +    xmlkey[1] = 'm';
    3.35 +    xmlkey[2] = 'l';
    3.36 +    xmlkey[3] = 0;
    3.37 +    if(ucx_map_cstr_get(map, xmlkey) != xml) {
    3.38 +        fprintf(stderr, "ucx_map_get failed\n");
    3.39 +        return -1;
    3.40 +    }
    3.41 +    if(ucx_map_cstr_get(map, "nokey") != NULL) {
    3.42 +        fprintf(stderr, "ucx_map_get failed\n");
    3.43 +        return -1;
    3.44 +    }
    3.45 +
    3.46 +    return 0;
    3.47 +}

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/test/map_tests.h	Sat Jan 14 13:07:18 2012 +0100
     4.3 @@ -0,0 +1,22 @@
     4.4 +/* 
     4.5 + *
     4.6 + */
     4.7 +
     4.8 +#ifndef MAP_TESTS_H
     4.9 +#define	MAP_TESTS_H
    4.10 +
    4.11 +#include "ucx/map.h"
    4.12 +
    4.13 +#ifdef	__cplusplus
    4.14 +extern "C" {
    4.15 +#endif
    4.16 +
    4.17 +int map_tests();
    4.18 +
    4.19 +
    4.20 +#ifdef	__cplusplus
    4.21 +}
    4.22 +#endif
    4.23 +
    4.24 +#endif	/* MAP_TESTS_H */
    4.25 +

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

     6.1 --- a/ucx/map.c	Wed Jan 11 12:19:48 2012 +0100
     6.2 +++ b/ucx/map.c	Sat Jan 14 13:07:18 2012 +0100
     6.3 @@ -1,1 +1,118 @@
     6.4 +/*
     6.5 + *
     6.6 + */
     6.7  
     6.8 +#include <stdlib.h>
     6.9 +#include <string.h>
    6.10 +
    6.11 +#include "map.h"
    6.12 +
    6.13 +UcxMap *ucx_map_new(size_t size) {
    6.14 +    UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
    6.15 +    if(map == NULL) {
    6.16 +        return NULL;
    6.17 +    }
    6.18 +
    6.19 +    map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement));
    6.20 +    if(map->map == NULL) {
    6.21 +        free(map);
    6.22 +        return NULL;
    6.23 +    }
    6.24 +    map->size = size;
    6.25 +
    6.26 +    return map;
    6.27 +}
    6.28 +
    6.29 +int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
    6.30 +    if(key.hash == 0) {
    6.31 +        key.hash = ucx_hash((char*)key.data, key.len);
    6.32 +    }
    6.33 +    void *kd = malloc(key.len);
    6.34 +    memcpy(kd, key.data, key.len);
    6.35 +    key.data = kd;
    6.36 +
    6.37 +    UcxMapElement *elm = &map->map[key.hash%map->size];
    6.38 +    if(elm->next != NULL) {
    6.39 +        while(elm->next != NULL) {
    6.40 +            elm = elm->next;
    6.41 +        }
    6.42 +        UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
    6.43 +        if(e == NULL) {
    6.44 +            return -1;
    6.45 +        }
    6.46 +        elm->next = e;
    6.47 +        elm = e;
    6.48 +    }
    6.49 +
    6.50 +    elm->key = key;
    6.51 +    elm->data = data;
    6.52 +
    6.53 +    return 0;
    6.54 +}
    6.55 +
    6.56 +void* ucx_map_get(UcxMap *map, UcxKey key) {
    6.57 +    if(key.hash == 0) {
    6.58 +        key.hash = ucx_hash((char*)key.data, key.len);
    6.59 +    }
    6.60 +    
    6.61 +    UcxMapElement *elm = &map->map[key.hash%map->size];
    6.62 +    while(elm != NULL) {
    6.63 +        if(elm->key.hash == key.hash) {
    6.64 +            int n = (key.len > elm->key.len) ? elm->key.len : key.len;
    6.65 +            if(memcmp(elm->key.data, key.data, n) == 0) {
    6.66 +                return elm->data;
    6.67 +            }
    6.68 +        }
    6.69 +        elm = elm->next;
    6.70 +    }
    6.71 +
    6.72 +    return NULL;
    6.73 +}
    6.74 +
    6.75 +UcxKey ucx_key(void *data, size_t len) {
    6.76 +    UcxKey key;
    6.77 +    key.data = data;
    6.78 +    key.len = len;
    6.79 +    key.hash = ucx_hash(data, len);
    6.80 +    return key;
    6.81 +}
    6.82 +
    6.83 +
    6.84 +int ucx_hash(char *data, size_t len) {
    6.85 +    /* murmur hash 2 */
    6.86 +
    6.87 +    int m = 0x5bd1e995;
    6.88 +    int r = 24;
    6.89 +
    6.90 +    int h = 25 ^ len;
    6.91 +
    6.92 +    int i = 0;
    6.93 +    while (len >= 4) {
    6.94 +        int k = data[i + 0] & 0xFF;
    6.95 +        k |= (data[i + 1] & 0xFF) << 8;
    6.96 +        k |= (data[i + 2] & 0xFF) << 16;
    6.97 +        k |= (data[i + 3] & 0xFF) << 24;
    6.98 +
    6.99 +        k *= m;
   6.100 +        k ^= k >> r;
   6.101 +        k *= m;
   6.102 +
   6.103 +        h *= m;
   6.104 +        h ^= k;
   6.105 +
   6.106 +        i += 4;
   6.107 +        len -= 4;
   6.108 +    }
   6.109 +
   6.110 +    switch (len) {
   6.111 +        case 3: h ^= (data[i + 2] & 0xFF) << 16;
   6.112 +        case 2: h ^= (data[i + 1] & 0xFF) << 8;
   6.113 +        case 1: h ^= (data[i + 0] & 0xFF); h *= m;
   6.114 +    }
   6.115 +
   6.116 +    h ^= h >> 13;
   6.117 +    h *= m;
   6.118 +    h ^= h >> 15;
   6.119 +
   6.120 +    return h;
   6.121 +}

     7.1 --- a/ucx/map.h	Wed Jan 11 12:19:48 2012 +0100
     7.2 +++ b/ucx/map.h	Sat Jan 14 13:07:18 2012 +0100
     7.3 @@ -5,12 +5,48 @@
     7.4  #ifndef MAP_H
     7.5  #define	MAP_H
     7.6  
     7.7 +#include "ucx.h"
     7.8 +#include "string.h"
     7.9 +
    7.10  #ifdef	__cplusplus
    7.11  extern "C" {
    7.12  #endif
    7.13  
    7.14 +typedef struct UcxMap        UcxMap;
    7.15 +typedef struct UcxKey        UcxKey;
    7.16 +typedef struct UcxMapElement UcxMapElement;
    7.17  
    7.18 +struct UcxMap {
    7.19 +    UcxMapElement *map;
    7.20 +    size_t        size;
    7.21 +};
    7.22  
    7.23 +struct UcxKey {
    7.24 +    void   *data;
    7.25 +    size_t len;
    7.26 +    int    hash;
    7.27 +};
    7.28 +
    7.29 +struct UcxMapElement {
    7.30 +    void          *data;
    7.31 +    UcxMapElement *next;
    7.32 +    UcxKey        key;
    7.33 +};
    7.34 +
    7.35 +
    7.36 +UcxMap *ucx_map_new(size_t size);
    7.37 +
    7.38 +int ucx_map_put(UcxMap *map, UcxKey key, void *data);
    7.39 +void* ucx_map_get(UcxMap *map, UcxKey key);
    7.40 +
    7.41 +#define ucx_map_sstr_put(m, s, d) ucx_map_put(m, ucx_key(s.ptr, s.length), d)
    7.42 +#define ucx_map_cstr_put(m, s, d) ucx_map_put(m, ucx_key(s, strlen(s)), d)
    7.43 +#define ucx_map_sstr_get(m, s) ucx_map_get(m, ucx_key(s.ptr, s.length))
    7.44 +#define ucx_map_cstr_get(m, s) ucx_map_get(m, ucx_key(s, strlen(s)))
    7.45 +
    7.46 +UcxKey ucx_key(void *data, size_t len);
    7.47 +
    7.48 +int ucx_hash(char *data, size_t len);
    7.49  
    7.50  #ifdef	__cplusplus
    7.51  }

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/ucx/string.c	Sat Jan 14 13:07:18 2012 +0100
     8.3 @@ -0,0 +1,99 @@
     8.4 +/*
     8.5 + * File:   sstring.c
     8.6 + * Author: olaf
     8.7 + *
     8.8 + * Created on 17. Juni 2010, 13:27
     8.9 + */
    8.10 +
    8.11 +#include <stdlib.h>
    8.12 +#include <string.h>
    8.13 +#include <stdarg.h>
    8.14 +
    8.15 +#include "string.h"
    8.16 +
    8.17 +sstr_t sstr (char *s) {
    8.18 +    sstr_t string;
    8.19 +    string.ptr = s;
    8.20 +    string.length = strlen(s);
    8.21 +    return string;
    8.22 +}
    8.23 +
    8.24 +sstr_t sstrn (char *s, size_t n) {
    8.25 +    sstr_t string;
    8.26 +    string.ptr = s;
    8.27 +    string.length = n;
    8.28 +    return string;
    8.29 +}
    8.30 +
    8.31 +size_t sstrnlen (size_t n, sstr_t s, ...) {
    8.32 +    va_list ap;
    8.33 +    size_t size = s.length;
    8.34 +    va_start(ap, s);
    8.35 +
    8.36 +    for (int i=0;i<n-1;i++) {
    8.37 +        sstr_t str = va_arg(ap, sstr_t);
    8.38 +        size += str.length;
    8.39 +    }
    8.40 +
    8.41 +    return size;
    8.42 +}
    8.43 +
    8.44 +sstr_t sstrcat (sstr_t s, ...) {
    8.45 +    va_list ap;
    8.46 +    va_start(ap, s);
    8.47 +    s.ptr[0] = 0;
    8.48 +
    8.49 +    sstr_t str = va_arg (ap, sstr_t);
    8.50 +    while (str.ptr != NULL) {
    8.51 +        s.ptr = strncat (s.ptr, str.ptr, s.length);
    8.52 +        str = va_arg (ap, sstr_t);
    8.53 +    }
    8.54 +
    8.55 +    return s;
    8.56 +}
    8.57 +
    8.58 +sstr_t sstrncat (size_t n, sstr_t s, sstr_t c1, ...) {
    8.59 +    va_list ap;
    8.60 +    va_start(ap, c1);
    8.61 +    s.ptr[0] = 0;
    8.62 +
    8.63 +    s.ptr = strncat (s.ptr, c1.ptr, s.length);
    8.64 +    for (int i=0;i<n-1;i++) {
    8.65 +        sstr_t str = va_arg (ap, sstr_t);
    8.66 +        s.ptr = strncat (s.ptr, str.ptr, s.length);
    8.67 +    }
    8.68 +
    8.69 +    return s;
    8.70 +}
    8.71 +
    8.72 +sstr_t sstrsubs (sstr_t s, size_t start) {
    8.73 +    return sstrsubsl (s, start, s.length-start);
    8.74 +}
    8.75 +
    8.76 +sstr_t sstrsubsl (sstr_t s, size_t start, size_t length) {
    8.77 +    sstr_t new_sstr;
    8.78 +    if (start < 0 || start >= s.length || length < 0) {
    8.79 +        return s;
    8.80 +    }
    8.81 +    if (length > s.length-start) {
    8.82 +        length = s.length-start;
    8.83 +    }
    8.84 +    new_sstr.ptr = &s.ptr[start];
    8.85 +    new_sstr.length = length;
    8.86 +    return new_sstr;
    8.87 +}
    8.88 +
    8.89 +int sstrcmp(sstr_t s1, sstr_t s2) {
    8.90 +    return strncmp(s1.ptr, s2.ptr, s1.length>s2.length ? s2.length: s1.length);
    8.91 +}
    8.92 +
    8.93 +sstr_t sstrdub(sstr_t s) {
    8.94 +    sstr_t newstring;
    8.95 +    newstring.ptr = malloc(s.length + 1);
    8.96 +    newstring.length = s.length;
    8.97 +    newstring.ptr[newstring.length] = 0;
    8.98 +
    8.99 +    memcpy(newstring.ptr, s.ptr, s.length);
   8.100 +
   8.101 +    return newstring;
   8.102 +}

     9.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     9.2 +++ b/ucx/string.h	Sat Jan 14 13:07:18 2012 +0100
     9.3 @@ -0,0 +1,78 @@
     9.4 +/*
     9.5 + * File:   sstring.h
     9.6 + * Author: olaf
     9.7 + *
     9.8 + * Created on 17. Juni 2010, 13:26
     9.9 + */
    9.10 +
    9.11 +#ifndef _SSTRING_H
    9.12 +#define	_SSTRING_H
    9.13 +
    9.14 +#define S(s) { s, sizeof(s)-1 }
    9.15 +#define ST(s) sstrn(s, sizeof(s)-1)
    9.16 +
    9.17 +#ifdef	__cplusplus
    9.18 +extern "C" {
    9.19 +#endif
    9.20 +
    9.21 +typedef struct sstring {
    9.22 +    char   *ptr;
    9.23 +    size_t length;
    9.24 +} sstr_t;
    9.25 +
    9.26 +/*
    9.27 + * creates a new sstr_t from a null terminated string
    9.28 + *
    9.29 + * s  null terminated string
    9.30 + */
    9.31 +sstr_t sstr (char *s);
    9.32 +
    9.33 +/*
    9.34 + * creates a new sstr_t from a string and length
    9.35 + *
    9.36 + * s  string
    9.37 + * n  length of string
    9.38 + */
    9.39 +sstr_t sstrn (char *s, size_t n);
    9.40 +
    9.41 +
    9.42 +/*
    9.43 + * gets the length of n sstr_t strings
    9.44 + *
    9.45 + * n    number of strings
    9.46 + * s    string
    9.47 + * ...  strings
    9.48 + */
    9.49 +size_t sstrnlen (size_t n, sstr_t s, ...);
    9.50 +
    9.51 +
    9.52 +/*
    9.53 + * concatenates n strings
    9.54 + *
    9.55 + * n    number of strings
    9.56 + * s    new string with enough memory allocated
    9.57 + * ...  strings
    9.58 + */
    9.59 +sstr_t sstrncat (size_t n, sstr_t s, sstr_t c1, ...);
    9.60 +
    9.61 +
    9.62 +/*
    9.63 + *
    9.64 + */
    9.65 +sstr_t sstrsubs (sstr_t s, size_t start);
    9.66 +
    9.67 +/*
    9.68 + *
    9.69 + */
    9.70 +sstr_t sstrsubsl (sstr_t s, size_t start, size_t end);
    9.71 +
    9.72 +
    9.73 +int sstrcmp(sstr_t s1, sstr_t s2);
    9.74 +
    9.75 +sstr_t sstrdub(sstr_t s);
    9.76 +
    9.77 +#ifdef	__cplusplus
    9.78 +}
    9.79 +#endif
    9.80 +
    9.81 +#endif	/* _SSTRING_H */