comparison: ucx/map.c
ucx/map.c
- changeset 29
- bce0d7f2912b
- parent 20
- db7d9860dbbd
- child 30
- 23bb65cbf7a4
equal
deleted
inserted
replaced
| 28:1666cbeb1db8 | 29:bce0d7f2912b |
|---|---|
| 11 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap)); | 11 UcxMap *map = (UcxMap*)malloc(sizeof(UcxMap)); |
| 12 if(map == NULL) { | 12 if(map == NULL) { |
| 13 return NULL; | 13 return NULL; |
| 14 } | 14 } |
| 15 | 15 |
| 16 map->map = (UcxMapElement*)calloc(size, sizeof(UcxMapElement)); | 16 map->map = (UcxMapElement**)calloc(size, sizeof(UcxMapElement*)); |
| 17 if(map->map == NULL) { | 17 if(map->map == NULL) { |
| 18 free(map); | 18 free(map); |
| 19 return NULL; | 19 return NULL; |
| 20 } | 20 } |
| 21 map->size = size; | 21 map->size = size; |
| 22 | 22 |
| 23 return map; | 23 return map; |
| 24 } | 24 } |
| 25 | 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); | |
| 33 elem = next; | |
| 34 } while (elem != NULL); | |
| 35 } | |
| 36 } | |
| 37 free(map); | |
| 38 } | |
| 39 | |
| 26 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { | 40 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { |
| 27 if(key.hash == 0) { | 41 if(key.hash == 0) { |
| 28 key.hash = ucx_hash((char*)key.data, key.len); | 42 key.hash = ucx_hash((char*)key.data, key.len); |
| 29 } | 43 } |
| 30 void *kd = malloc(key.len); | 44 void *kd = malloc(key.len); |
| 45 if (kd == NULL) { | |
| 46 return -1; | |
| 47 } | |
| 31 memcpy(kd, key.data, key.len); | 48 memcpy(kd, key.data, key.len); |
| 32 key.data = kd; | 49 key.data = kd; |
| 33 | 50 |
| 34 UcxMapElement *elm = &map->map[key.hash%map->size]; | 51 size_t slot = key.hash%map->size; |
| 35 if(elm->next != NULL) { | 52 UcxMapElement *elm = map->map[slot]; |
| 36 while(elm->next != NULL) { | 53 UcxMapElement *prev = NULL; |
| 37 elm = elm->next; | 54 |
| 38 } | 55 while (elm != NULL && elm->key.hash < key.hash) { |
| 56 prev = elm; | |
| 57 elm = elm->next; | |
| 58 } | |
| 59 | |
| 60 if (elm == NULL || elm->key.hash != key.hash) { | |
| 39 UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement)); | 61 UcxMapElement *e = (UcxMapElement*)malloc(sizeof(UcxMapElement)); |
| 40 if(e == NULL) { | 62 if(e == NULL) { |
| 41 return -1; | 63 return -1; |
| 42 } | 64 } |
| 43 elm->next = e; | 65 if (prev == NULL) { |
| 66 map->map[slot] = e; | |
| 67 } else { | |
| 68 prev->next = e; | |
| 69 } | |
| 70 e->next = elm; | |
| 44 elm = e; | 71 elm = e; |
| 45 } | 72 } |
| 46 | 73 |
| 47 elm->key = key; | 74 elm->key = key; |
| 48 elm->data = data; | 75 elm->data = data; |
| 49 | 76 |
| 50 return 0; | 77 return 0; |
| 51 } | 78 } |
| 53 void* ucx_map_get(UcxMap *map, UcxKey key) { | 80 void* ucx_map_get(UcxMap *map, UcxKey key) { |
| 54 if(key.hash == 0) { | 81 if(key.hash == 0) { |
| 55 key.hash = ucx_hash((char*)key.data, key.len); | 82 key.hash = ucx_hash((char*)key.data, key.len); |
| 56 } | 83 } |
| 57 | 84 |
| 58 UcxMapElement *elm = &map->map[key.hash%map->size]; | 85 UcxMapElement *elm = map->map[key.hash%map->size]; |
| 59 while(elm != NULL) { | 86 while (elm != NULL && elm->key.hash <= key.hash) { |
| 60 if(elm->key.hash == key.hash) { | 87 if(elm->key.hash == key.hash) { |
| 61 int n = (key.len > elm->key.len) ? elm->key.len : key.len; | 88 int n = (key.len > elm->key.len) ? elm->key.len : key.len; |
| 62 if(memcmp(elm->key.data, key.data, n) == 0) { | 89 if (memcmp(elm->key.data, key.data, n) == 0) { |
| 63 return elm->data; | 90 return elm->data; |
| 64 } | 91 } |
| 65 } | 92 } |
| 66 elm = elm->next; | 93 elm = elm->next; |
| 67 } | 94 } |
