src/server/ucx/map.c

Sat, 28 Jan 2012 16:01:07 +0100

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Sat, 28 Jan 2012 16:01:07 +0100
changeset 20
7b235fa88008
parent 15
cff9c4101dd7
child 21
627b09ee74e4
permissions
-rw-r--r--

Some fixes for mod_jk

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

mercurial