comparison: ucx/map.c
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 } |
