comparison: src/server/ucx/map.c
src/server/ucx/map.c
- changeset 31
- 280250e45ba6
- parent 21
- 627b09ee74e4
- child 36
- 450d2d5f4735
equal
deleted
inserted
replaced
| 30:27c7511c0e34 | 31:280250e45ba6 |
|---|---|
| 1 /* | 1 /* |
| 2 * | 2 * |
| 3 */ | 3 */ |
| 4 | 4 |
| 5 #include <stdio.h> | |
| 6 #include <stdlib.h> | 5 #include <stdlib.h> |
| 7 #include <string.h> | 6 #include <string.h> |
| 8 | 7 |
| 9 #include "map.h" | 8 #include "map.h" |
| 10 | 9 |
| 12 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap)); | 11 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap)); |
| 13 if(map == NULL) { | 12 if(map == NULL) { |
| 14 return NULL; | 13 return NULL; |
| 15 } | 14 } |
| 16 | 15 |
| 17 map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement)); | 16 map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*)); |
| 18 if(map->map == NULL) { | 17 if(map->map == NULL) { |
| 19 free(map); | 18 free(map); |
| 20 return NULL; | 19 return NULL; |
| 21 } | 20 } |
| 22 map->size = size; | 21 map->size = size; |
| 23 | 22 |
| 24 return map; | 23 return map; |
| 25 } | 24 } |
| 26 | 25 |
| 26 void ucx_map_free(UcxMap *map) { | |
| 27 for (size_t n = 0 ; n < map->size ; n++) { | |
| 28 UcxMapElement *elem = map->map[n]; | |
| 29 if (elem != NULL) { | |
| 30 do { | |
| 31 UcxMapElement *next = elem->next; | |
| 32 free(elem->key.data); | |
| 33 free(elem); | |
| 34 elem = next; | |
| 35 } while (elem != NULL); | |
| 36 } | |
| 37 } | |
| 38 free(map->map); | |
| 39 free(map); | |
| 40 } | |
| 41 | |
| 27 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { | 42 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { |
| 28 if(key.hash == 0) { | 43 if(key.hash == 0) { |
| 29 key.hash = ucx_hash((char*)key.data, key.len); | 44 key.hash = ucx_hash((char*)key.data, key.len); |
| 30 } | 45 } |
| 31 void *kd = calloc(1, key.len); | |
| 32 memcpy(kd, key.data, key.len); | |
| 33 key.data = kd; | |
| 34 | 46 |
| 35 UcxMapElement *elm = &map->map[key.hash%map->size]; | 47 size_t slot = key.hash%map->size; |
| 36 if(elm->key.hash != 0) { | 48 UcxMapElement *elm = map->map[slot]; |
| 37 UcxMapElement *e = elm; | 49 UcxMapElement *prev = NULL; |
| 38 for(;;) { | |
| 39 /* check if the key is already in use */ | |
| 40 if(key.hash == e->key.hash) { | |
| 41 int n = (key.len > elm->key.len) ? elm->key.len : key.len; | |
| 42 if(memcmp(elm->key.data, key.data, n) == 0) { | |
| 43 /* use elm as storage place */ | |
| 44 elm = e; | |
| 45 break; | |
| 46 } | |
| 47 } | |
| 48 | 50 |
| 49 /* check if this is the last element */ | 51 while (elm != NULL && elm->key.hash < key.hash) { |
| 50 if(e->next == NULL) { | 52 prev = elm; |
| 51 /* create new element */ | 53 elm = elm->next; |
| 52 UcxMapElement *en = (UcxMapElement*)malloc(sizeof(UcxMapElement)); | 54 } |
| 53 if(en == NULL) { | 55 |
| 54 return -1; | 56 if (elm == NULL || elm->key.hash != key.hash) { |
| 55 } | 57 UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement)); |
| 56 e->next = en; | 58 if(e == NULL) { |
| 57 elm = en; | 59 return -1; |
| 58 break; | |
| 59 } | |
| 60 | |
| 61 e = e->next; | |
| 62 } | 60 } |
| 61 e->key.data = NULL; | |
| 62 if (prev == NULL) { | |
| 63 map->map[slot] = e; | |
| 64 } else { | |
| 65 prev->next = e; | |
| 66 } | |
| 67 e->next = elm; | |
| 68 elm = e; | |
| 63 } | 69 } |
| 64 | 70 |
| 65 elm->key = key; | 71 if(elm->key.data == NULL) { |
| 72 void *kd = malloc(key.len); | |
| 73 if (kd == NULL) { | |
| 74 return -1; | |
| 75 } | |
| 76 memcpy(kd, key.data, key.len); | |
| 77 key.data = kd; | |
| 78 elm->key = key; | |
| 79 } | |
| 66 elm->data = data; | 80 elm->data = data; |
| 67 | 81 |
| 68 return 0; | 82 return 0; |
| 69 } | 83 } |
| 70 | 84 |
| 71 void* ucx_map_get(UcxMap *map, UcxKey key) { | 85 void* ucx_map_get(UcxMap *map, UcxKey key) { |
| 72 if(key.hash == 0) { | 86 if(key.hash == 0) { |
| 73 key.hash = ucx_hash((char*)key.data, key.len); | 87 key.hash = ucx_hash((char*)key.data, key.len); |
| 74 } | 88 } |
| 75 | 89 |
| 76 UcxMapElement *elm = &map->map[key.hash%map->size]; | 90 UcxMapElement *elm = map->map[key.hash%map->size]; |
| 77 while(elm != NULL) { | 91 while (elm != NULL && elm->key.hash <= key.hash) { |
| 78 if(elm->key.hash == key.hash) { | 92 if(elm->key.hash == key.hash) { |
| 79 int n = (key.len > elm->key.len) ? elm->key.len : key.len; | 93 int n = (key.len > elm->key.len) ? elm->key.len : key.len; |
| 80 if(memcmp(elm->key.data, key.data, n) == 0) { | 94 if (memcmp(elm->key.data, key.data, n) == 0) { |
| 81 return elm->data; | 95 return elm->data; |
| 82 } | 96 } |
| 83 } | 97 } |
| 84 elm = elm->next; | 98 elm = elm->next; |
| 85 } | 99 } |
| 132 h *= m; | 146 h *= m; |
| 133 h ^= h >> 15; | 147 h ^= h >> 15; |
| 134 | 148 |
| 135 return h; | 149 return h; |
| 136 } | 150 } |
| 151 | |
| 152 UcxMapIterator ucx_map_iterator(UcxMap *map) { | |
| 153 UcxMapIterator i; | |
| 154 i.map = map; | |
| 155 i.cur = NULL; | |
| 156 i.index = 0; | |
| 157 return i; | |
| 158 } | |
| 159 | |
| 160 int ucx_map_iter_next(UcxMapIterator *i, void **elm) { | |
| 161 UcxMapElement *e = i->cur; | |
| 162 | |
| 163 if(e == NULL) { | |
| 164 e = i->map->map[0]; | |
| 165 } else { | |
| 166 e = e->next; | |
| 167 } | |
| 168 | |
| 169 while(i->index < i->map->size) { | |
| 170 if(e != NULL) { | |
| 171 if(e->data != NULL) { | |
| 172 i->cur = e; | |
| 173 *elm = e->data; | |
| 174 return 0; | |
| 175 } | |
| 176 | |
| 177 e = e->next; | |
| 178 } else { | |
| 179 i->index++; | |
| 180 | |
| 181 if(i->index < i->map->size) { | |
| 182 e = i->map->map[i->index]; | |
| 183 } | |
| 184 } | |
| 185 } | |
| 186 | |
| 187 return 1; | |
| 188 } |
