comparison: src/hash_map.c
src/hash_map.c
- changeset 686
- 64919f63f059
- parent 685
- 2dd841e364af
- child 688
- c27fa8b67286
equal
deleted
inserted
replaced
| 685:2dd841e364af | 686:64919f63f059 |
|---|---|
| 46 cx_for_n(i, hash_map->bucket_count) { | 46 cx_for_n(i, hash_map->bucket_count) { |
| 47 struct cx_hash_map_element_s *elem = hash_map->buckets[i]; | 47 struct cx_hash_map_element_s *elem = hash_map->buckets[i]; |
| 48 if (elem != NULL) { | 48 if (elem != NULL) { |
| 49 do { | 49 do { |
| 50 struct cx_hash_map_element_s *next = elem->next; | 50 struct cx_hash_map_element_s *next = elem->next; |
| 51 // invoke the destructor | |
| 52 cx_invoke_destructor(map, elem->data); | |
| 51 // free the key data | 53 // free the key data |
| 52 cxFree(map->allocator, elem->key.data.obj); | 54 cxFree(map->allocator, elem->key.data.obj); |
| 53 // free the node | 55 // free the node |
| 54 cxFree(map->allocator, elem); | 56 cxFree(map->allocator, elem); |
| 55 // proceed | 57 // proceed |
| 78 CxMap *map, | 80 CxMap *map, |
| 79 CxHashKey key, | 81 CxHashKey key, |
| 80 void *value | 82 void *value |
| 81 ) { | 83 ) { |
| 82 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 84 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 83 CxAllocator *allocator = map->allocator; | 85 CxAllocator const *allocator = map->allocator; |
| 84 | 86 |
| 85 unsigned hash = key.hash; | 87 unsigned hash = key.hash; |
| 86 if (hash == 0) { | 88 if (hash == 0) { |
| 87 cx_hash_murmur(&key); | 89 cx_hash_murmur(&key); |
| 88 hash = key.hash; | 90 hash = key.hash; |
| 170 * Helper function to avoid code duplication. | 172 * Helper function to avoid code duplication. |
| 171 * | 173 * |
| 172 * @param map the map | 174 * @param map the map |
| 173 * @param key the key to look up | 175 * @param key the key to look up |
| 174 * @param remove flag indicating whether the looked up entry shall be removed | 176 * @param remove flag indicating whether the looked up entry shall be removed |
| 177 * @param destroy flag indicating whether the destructor shall be invoked | |
| 175 * @return a pointer to the value corresponding to the key or \c NULL | 178 * @return a pointer to the value corresponding to the key or \c NULL |
| 176 */ | 179 */ |
| 177 static void *cx_hash_map_get_remove( | 180 static void *cx_hash_map_get_remove( |
| 178 CxMap *map, | 181 CxMap *map, |
| 179 CxHashKey key, | 182 CxHashKey key, |
| 180 bool remove | 183 bool remove, |
| 184 bool destroy | |
| 181 ) { | 185 ) { |
| 182 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 186 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 183 | 187 |
| 184 unsigned hash = key.hash; | 188 unsigned hash = key.hash; |
| 185 if (hash == 0) { | 189 if (hash == 0) { |
| 192 struct cx_hash_map_element_s *prev = NULL; | 196 struct cx_hash_map_element_s *prev = NULL; |
| 193 while (elm && elm->key.hash <= hash) { | 197 while (elm && elm->key.hash <= hash) { |
| 194 if (elm->key.hash == hash && elm->key.len == key.len) { | 198 if (elm->key.hash == hash && elm->key.len == key.len) { |
| 195 if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { | 199 if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { |
| 196 void *data = NULL; | 200 void *data = NULL; |
| 197 if (map->store_pointer) { | 201 if (destroy) { |
| 198 data = *(void **) elm->data; | 202 cx_invoke_destructor(map, elm->data); |
| 199 } else if (!remove) { | 203 } else { |
| 200 data = elm->data; | 204 if (map->store_pointer) { |
| 205 data = *(void **) elm->data; | |
| 206 } else { | |
| 207 data = elm->data; | |
| 208 } | |
| 201 } | 209 } |
| 202 if (remove) { | 210 if (remove) { |
| 203 cx_hash_map_unlink(hash_map, slot, prev, elm); | 211 cx_hash_map_unlink(hash_map, slot, prev, elm); |
| 204 } | 212 } |
| 205 return data; | 213 return data; |
| 215 static void *cx_hash_map_get( | 223 static void *cx_hash_map_get( |
| 216 CxMap const *map, | 224 CxMap const *map, |
| 217 CxHashKey key | 225 CxHashKey key |
| 218 ) { | 226 ) { |
| 219 // we can safely cast, because we know when remove=false, the map stays untouched | 227 // we can safely cast, because we know when remove=false, the map stays untouched |
| 220 return cx_hash_map_get_remove((CxMap *) map, key, false); | 228 return cx_hash_map_get_remove((CxMap *) map, key, false, false); |
| 221 } | 229 } |
| 222 | 230 |
| 223 static void *cx_hash_map_remove( | 231 static void *cx_hash_map_remove( |
| 224 CxMap *map, | 232 CxMap *map, |
| 225 CxHashKey key | 233 CxHashKey key, |
| 234 bool destroy | |
| 226 ) { | 235 ) { |
| 227 return cx_hash_map_get_remove(map, key, true); | 236 return cx_hash_map_get_remove(map, key, true, destroy); |
| 228 } | 237 } |
| 229 | 238 |
| 230 static void *cx_hash_map_iter_current_entry(void const *it) { | 239 static void *cx_hash_map_iter_current_entry(void const *it) { |
| 231 struct cx_iterator_s const *iter = it; | 240 struct cx_iterator_s const *iter = it; |
| 232 // struct has to have a compatible signature | 241 // struct has to have a compatible signature |
| 277 prev = map->buckets[iter->slot]; | 286 prev = map->buckets[iter->slot]; |
| 278 while (prev->next != elm) { | 287 while (prev->next != elm) { |
| 279 prev = prev->next; | 288 prev = prev->next; |
| 280 } | 289 } |
| 281 } | 290 } |
| 291 | |
| 292 // destroy | |
| 293 cx_invoke_destructor((struct cx_map_s *) map, elm->data); | |
| 282 | 294 |
| 283 // unlink | 295 // unlink |
| 284 cx_hash_map_unlink(map, iter->slot, prev, elm); | 296 cx_hash_map_unlink(map, iter->slot, prev, elm); |
| 285 | 297 |
| 286 // advance | 298 // advance |
