ucx/map.c

changeset 20
db7d9860dbbd
parent 2
79646375a420
child 29
bce0d7f2912b
equal deleted inserted replaced
17:2e7050c3a18e 20:db7d9860dbbd
1 /*
2 *
3 */
1 4
5 #include <stdlib.h>
6 #include <string.h>
7
8 #include "map.h"
9
10 UcxMap *ucx_map_new(size_t size) {
11 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
12 if(map == NULL) {
13 return NULL;
14 }
15
16 map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement));
17 if(map->map == NULL) {
18 free(map);
19 return NULL;
20 }
21 map->size = size;
22
23 return map;
24 }
25
26 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
27 if(key.hash == 0) {
28 key.hash = ucx_hash((char*)key.data, key.len);
29 }
30 void *kd = malloc(key.len);
31 memcpy(kd, key.data, key.len);
32 key.data = kd;
33
34 UcxMapElement *elm = &map->map[key.hash%map->size];
35 if(elm->next != NULL) {
36 while(elm->next != NULL) {
37 elm = elm->next;
38 }
39 UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement));
40 if(e == NULL) {
41 return -1;
42 }
43 elm->next = e;
44 elm = e;
45 }
46
47 elm->key = key;
48 elm->data = data;
49
50 return 0;
51 }
52
53 void* ucx_map_get(UcxMap *map, UcxKey key) {
54 if(key.hash == 0) {
55 key.hash = ucx_hash((char*)key.data, key.len);
56 }
57
58 UcxMapElement *elm = &map->map[key.hash%map->size];
59 while(elm != NULL) {
60 if(elm->key.hash == key.hash) {
61 int n = (key.len > elm->key.len) ? elm->key.len : key.len;
62 if(memcmp(elm->key.data, key.data, n) == 0) {
63 return elm->data;
64 }
65 }
66 elm = elm->next;
67 }
68
69 return NULL;
70 }
71
72 UcxKey ucx_key(void *data, size_t len) {
73 UcxKey key;
74 key.data = data;
75 key.len = len;
76 key.hash = ucx_hash(data, len);
77 return key;
78 }
79
80
81 int ucx_hash(char *data, size_t len) {
82 /* murmur hash 2 */
83
84 int m = 0x5bd1e995;
85 int r = 24;
86
87 int h = 25 ^ len;
88
89 int i = 0;
90 while (len >= 4) {
91 int k = data[i + 0] & 0xFF;
92 k |= (data[i + 1] & 0xFF) << 8;
93 k |= (data[i + 2] & 0xFF) << 16;
94 k |= (data[i + 3] & 0xFF) << 24;
95
96 k *= m;
97 k ^= k >> r;
98 k *= m;
99
100 h *= m;
101 h ^= k;
102
103 i += 4;
104 len -= 4;
105 }
106
107 switch (len) {
108 case 3: h ^= (data[i + 2] & 0xFF) << 16;
109 case 2: h ^= (data[i + 1] & 0xFF) << 8;
110 case 1: h ^= (data[i + 0] & 0xFF); h *= m;
111 }
112
113 h ^= h >> 13;
114 h *= m;
115 h ^= h >> 15;
116
117 return h;
118 }

mercurial