Thu, 05 Jan 2012 14:53:54 +0100
added some map functions
test/Makefile | file | annotate | diff | comparison | revisions | |
test/main.c | file | annotate | diff | comparison | revisions | |
test/map_tests.c | file | annotate | diff | comparison | revisions | |
test/map_tests.h | file | annotate | diff | comparison | revisions | |
ucx/Makefile | file | annotate | diff | comparison | revisions | |
ucx/map.c | file | annotate | diff | comparison | revisions | |
ucx/map.h | file | annotate | diff | comparison | revisions | |
ucx/string.c | file | annotate | diff | comparison | revisions | |
ucx/string.h | file | annotate | diff | comparison | revisions |
1.1 --- a/test/Makefile Sat Dec 31 22:48:28 2011 +0100 1.2 +++ b/test/Makefile Thu Jan 05 14:53:54 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 Sat Dec 31 22:48:28 2011 +0100 2.2 +++ b/test/main.c Thu Jan 05 14:53:54 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 @@ -49,6 +50,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 Thu Jan 05 14:53:54 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 Thu Jan 05 14:53:54 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 Sat Dec 31 22:48:28 2011 +0100 5.2 +++ b/ucx/Makefile Thu Jan 05 14:53:54 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 Sat Dec 31 22:48:28 2011 +0100 6.2 +++ b/ucx/map.c Thu Jan 05 14:53:54 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 Sat Dec 31 22:48:28 2011 +0100 7.2 +++ b/ucx/map.h Thu Jan 05 14:53:54 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 Thu Jan 05 14:53:54 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 Thu Jan 05 14:53:54 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 */