comparison: ucx/hash_map.c
ucx/hash_map.c
- changeset 112
- c3f2f16fa4b8
- parent 102
- 64ded9f6a6c6
- child 113
- dde28a806552
equal
deleted
inserted
replaced
| 111:81c4f73236a4 | 112:c3f2f16fa4b8 |
|---|---|
| 76 | 76 |
| 77 // free the map structure | 77 // free the map structure |
| 78 cxFree(map->collection.allocator, map); | 78 cxFree(map->collection.allocator, map); |
| 79 } | 79 } |
| 80 | 80 |
| 81 static int cx_hash_map_put( | 81 static void *cx_hash_map_put( |
| 82 CxMap *map, | 82 CxMap *map, |
| 83 CxHashKey key, | 83 CxHashKey key, |
| 84 void *value | 84 void *value |
| 85 ) { | 85 ) { |
| 86 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 86 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 99 while (elm != NULL && elm->key.hash < hash) { | 99 while (elm != NULL && elm->key.hash < hash) { |
| 100 prev = elm; | 100 prev = elm; |
| 101 elm = elm->next; | 101 elm = elm->next; |
| 102 } | 102 } |
| 103 | 103 |
| 104 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && | 104 if (elm != NULL && cx_hash_key_cmp(&elm->key, &key) == 0) { |
| 105 memcmp(elm->key.data, key.data, key.len) == 0) { | |
| 106 // overwrite existing element, but call destructors first | 105 // overwrite existing element, but call destructors first |
| 107 cx_invoke_destructor(map, elm->data); | 106 cx_invoke_destructor(map, elm->data); |
| 108 if (map->collection.store_pointer) { | 107 if (value == NULL) { |
| 108 memset(elm->data, 0, map->collection.elem_size); | |
| 109 } else if (map->collection.store_pointer) { | |
| 109 memcpy(elm->data, &value, sizeof(void *)); | 110 memcpy(elm->data, &value, sizeof(void *)); |
| 110 } else { | 111 } else { |
| 111 memcpy(elm->data, value, map->collection.elem_size); | 112 memcpy(elm->data, value, map->collection.elem_size); |
| 112 } | 113 } |
| 113 } else { | 114 } else { |
| 114 // allocate new element | 115 // allocate new element |
| 115 struct cx_hash_map_element_s *e = cxMalloc( | 116 struct cx_hash_map_element_s *e = cxMalloc( |
| 116 allocator, | 117 allocator, |
| 117 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size | 118 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size |
| 118 ); | 119 ); |
| 119 if (e == NULL) return -1; | 120 if (e == NULL) return NULL; |
| 120 | 121 |
| 121 // write the value | 122 // write the value |
| 122 if (map->collection.store_pointer) { | 123 if (value == NULL) { |
| 124 memset(e->data, 0, map->collection.elem_size); | |
| 125 } else if (map->collection.store_pointer) { | |
| 123 memcpy(e->data, &value, sizeof(void *)); | 126 memcpy(e->data, &value, sizeof(void *)); |
| 124 } else { | 127 } else { |
| 125 memcpy(e->data, value, map->collection.elem_size); | 128 memcpy(e->data, value, map->collection.elem_size); |
| 126 } | 129 } |
| 127 | 130 |
| 128 // copy the key | 131 // copy the key |
| 129 void *kd = cxMalloc(allocator, key.len); | 132 void *kd = cxMalloc(allocator, key.len); |
| 130 if (kd == NULL) return -1; | 133 if (kd == NULL) { |
| 134 cxFree(allocator, e); | |
| 135 return NULL; | |
| 136 } | |
| 131 memcpy(kd, key.data, key.len); | 137 memcpy(kd, key.data, key.len); |
| 132 e->key.data = kd; | 138 e->key.data = kd; |
| 133 e->key.len = key.len; | 139 e->key.len = key.len; |
| 134 e->key.hash = hash; | 140 e->key.hash = hash; |
| 135 | 141 |
| 138 hash_map->buckets[slot] = e; | 144 hash_map->buckets[slot] = e; |
| 139 } else { | 145 } else { |
| 140 prev->next = e; | 146 prev->next = e; |
| 141 } | 147 } |
| 142 e->next = elm; | 148 e->next = elm; |
| 149 elm = e; | |
| 143 | 150 |
| 144 // increase the size | 151 // increase the size |
| 145 map->collection.size++; | 152 map->collection.size++; |
| 146 } | 153 } |
| 147 | 154 |
| 148 return 0; | 155 // return pointer to the element |
| 156 return elm->data; | |
| 149 } | 157 } |
| 150 | 158 |
| 151 static void cx_hash_map_unlink( | 159 static void cx_hash_map_unlink( |
| 152 struct cx_hash_map_s *hash_map, | 160 struct cx_hash_map_s *hash_map, |
| 153 size_t slot, | 161 size_t slot, |
| 203 | 211 |
| 204 size_t slot = hash % hash_map->bucket_count; | 212 size_t slot = hash % hash_map->bucket_count; |
| 205 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; | 213 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; |
| 206 struct cx_hash_map_element_s *prev = NULL; | 214 struct cx_hash_map_element_s *prev = NULL; |
| 207 while (elm && elm->key.hash <= hash) { | 215 while (elm && elm->key.hash <= hash) { |
| 208 if (elm->key.hash == hash && elm->key.len == key.len) { | 216 if (cx_hash_key_cmp(&elm->key, &key) == 0) { |
| 209 if (memcmp(elm->key.data, key.data, key.len) == 0) { | 217 if (remove) { |
| 210 if (remove) { | 218 if (targetbuf == NULL) { |
| 211 if (targetbuf == NULL) { | 219 cx_invoke_destructor(map, elm->data); |
| 212 cx_invoke_destructor(map, elm->data); | |
| 213 } else { | |
| 214 memcpy(targetbuf, elm->data, map->collection.elem_size); | |
| 215 } | |
| 216 cx_hash_map_unlink(hash_map, slot, prev, elm); | |
| 217 } else { | 220 } else { |
| 218 assert(targetbuf != NULL); | 221 memcpy(targetbuf, elm->data, map->collection.elem_size); |
| 219 void *data = NULL; | |
| 220 if (map->collection.store_pointer) { | |
| 221 data = *(void **) elm->data; | |
| 222 } else { | |
| 223 data = elm->data; | |
| 224 } | |
| 225 memcpy(targetbuf, &data, sizeof(void *)); | |
| 226 } | 222 } |
| 227 return 0; | 223 cx_hash_map_unlink(hash_map, slot, prev, elm); |
| 224 } else { | |
| 225 assert(targetbuf != NULL); | |
| 226 void *data = NULL; | |
| 227 if (map->collection.store_pointer) { | |
| 228 data = *(void **) elm->data; | |
| 229 } else { | |
| 230 data = elm->data; | |
| 231 } | |
| 232 memcpy(targetbuf, &data, sizeof(void *)); | |
| 228 } | 233 } |
| 234 return 0; | |
| 229 } | 235 } |
| 230 prev = elm; | 236 prev = elm; |
| 231 elm = prev->next; | 237 elm = prev->next; |
| 232 } | 238 } |
| 233 | 239 |
| 258 return (void*) &iter->entry; | 264 return (void*) &iter->entry; |
| 259 } | 265 } |
| 260 | 266 |
| 261 static void *cx_hash_map_iter_current_key(const void *it) { | 267 static void *cx_hash_map_iter_current_key(const void *it) { |
| 262 const CxMapIterator *iter = it; | 268 const CxMapIterator *iter = it; |
| 263 struct cx_hash_map_element_s *elm = iter->elem; | 269 return (void*) iter->entry.key; |
| 264 return &elm->key; | |
| 265 } | 270 } |
| 266 | 271 |
| 267 static void *cx_hash_map_iter_current_value(const void *it) { | 272 static void *cx_hash_map_iter_current_value(const void *it) { |
| 268 const CxMapIterator *iter = it; | 273 const CxMapIterator *iter = it; |
| 269 const CxMap *map = iter->map.c; | 274 return iter->entry.value; |
| 270 struct cx_hash_map_element_s *elm = iter->elem; | |
| 271 if (map->collection.store_pointer) { | |
| 272 return *(void **) elm->data; | |
| 273 } else { | |
| 274 return elm->data; | |
| 275 } | |
| 276 } | 275 } |
| 277 | 276 |
| 278 static bool cx_hash_map_iter_valid(const void *it) { | 277 static bool cx_hash_map_iter_valid(const void *it) { |
| 279 const CxMapIterator *iter = it; | 278 const CxMapIterator *iter = it; |
| 280 return iter->elem != NULL; | 279 return iter->elem != NULL; |
| 307 // destroy | 306 // destroy |
| 308 cx_invoke_destructor(map, elm->data); | 307 cx_invoke_destructor(map, elm->data); |
| 309 | 308 |
| 310 // unlink | 309 // unlink |
| 311 cx_hash_map_unlink(hmap, iter->slot, prev, elm); | 310 cx_hash_map_unlink(hmap, iter->slot, prev, elm); |
| 311 iter->elem_count--; | |
| 312 | 312 |
| 313 // advance | 313 // advance |
| 314 elm = next; | 314 elm = next; |
| 315 } else { | 315 } else { |
| 316 // just advance | 316 // just advance |
