src/server/ucx/map.c

Thu, 23 Feb 2012 13:10:04 +0100

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Thu, 23 Feb 2012 13:10:04 +0100
changeset 24
1a7853a4257e
parent 21
627b09ee74e4
child 31
280250e45ba6
permissions
-rw-r--r--

removed some NSPR dependencies

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
21
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
5 #include <stdio.h>
15
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
6 #include <stdlib.h>
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
7 #include <string.h>
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
8
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
9 #include "map.h"
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
10
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
11 UcxMap *ucx_map_new(size_t size) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
12 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap));
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
13 if(map == NULL) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
14 return NULL;
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
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
17 map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement));
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
18 if(map->map == NULL) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
19 free(map);
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
20 return NULL;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
21 }
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
22 map->size = size;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
23
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
24 return map;
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
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
27 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
28 if(key.hash == 0) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
29 key.hash = ucx_hash((char*)key.data, key.len);
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
30 }
21
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
31 void *kd = calloc(1, key.len);
15
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32 memcpy(kd, key.data, key.len);
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33 key.data = kd;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
34
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
35 UcxMapElement *elm = &map->map[key.hash%map->size];
21
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
36 if(elm->key.hash != 0) {
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
37 UcxMapElement *e = elm;
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
38 for(;;) {
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
39 /* check if the key is already in use */
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
40 if(key.hash == e->key.hash) {
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
41 int n = (key.len > elm->key.len) ? elm->key.len : key.len;
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
42 if(memcmp(elm->key.data, key.data, n) == 0) {
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
43 /* use elm as storage place */
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
44 elm = e;
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
45 break;
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
46 }
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
47 }
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
48
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
49 /* check if this is the last element */
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
50 if(e->next == NULL) {
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
51 /* create new element */
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
52 UcxMapElement *en = (UcxMapElement*)malloc(sizeof(UcxMapElement));
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
53 if(en == NULL) {
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
54 return -1;
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
55 }
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
56 e->next = en;
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
57 elm = en;
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
58 break;
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
59 }
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
60
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
61 e = e->next;
15
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 }
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 }
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 elm->key = key;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 elm->data = data;
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 return 0;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 }
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 void* ucx_map_get(UcxMap *map, UcxKey key) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
72 if(key.hash == 0) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73 key.hash = ucx_hash((char*)key.data, key.len);
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
74 }
21
627b09ee74e4 New configuration loader
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 15
diff changeset
75
15
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76 UcxMapElement *elm = &map->map[key.hash%map->size];
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 while(elm != NULL) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
78 if(elm->key.hash == key.hash) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
79 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
80 if(memcmp(elm->key.data, key.data, n) == 0) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
81 return elm->data;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
82 }
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 elm = elm->next;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
85 }
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 return NULL;
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
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
90 UcxKey ucx_key(void *data, size_t len) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
91 UcxKey key;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
92 key.data = data;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
93 key.len = len;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
94 key.hash = ucx_hash(data, len);
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
95 return key;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
96 }
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
97
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
98
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
99 int ucx_hash(char *data, size_t len) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
100 /* murmur hash 2 */
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102 int m = 0x5bd1e995;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
103 int r = 24;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
104
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
105 int h = 25 ^ len;
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 int i = 0;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 while (len >= 4) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109 int k = data[i + 0] & 0xFF;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110 k |= (data[i + 1] & 0xFF) << 8;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 k |= (data[i + 2] & 0xFF) << 16;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
112 k |= (data[i + 3] & 0xFF) << 24;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
113
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
114 k *= m;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
115 k ^= k >> r;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116 k *= m;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
117
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
118 h *= m;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
119 h ^= k;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
120
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
121 i += 4;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
122 len -= 4;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
123 }
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
124
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
125 switch (len) {
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126 case 3: h ^= (data[i + 2] & 0xFF) << 16;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127 case 2: h ^= (data[i + 1] & 0xFF) << 8;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
128 case 1: h ^= (data[i + 0] & 0xFF); h *= m;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
129 }
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
130
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 h ^= h >> 13;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132 h *= m;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 h ^= h >> 15;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
135 return h;
cff9c4101dd7 Replaced old utils with ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
136 }

mercurial