comparison: ucx/kv_list.c
ucx/kv_list.c
- changeset 30
- d33eaaec15da
- parent 23
- b26390e77237
equal
deleted
inserted
replaced
| 29:b8c826c720f3 | 30:d33eaaec15da |
|---|---|
| 283 return iter; | 283 return iter; |
| 284 } | 284 } |
| 285 | 285 |
| 286 static void cx_kvl_map_deallocate(struct cx_map_s *map) { | 286 static void cx_kvl_map_deallocate(struct cx_map_s *map) { |
| 287 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; | 287 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; |
| 288 cx_kv_list_update_destructors(kv_list); | |
| 288 kv_list->map_methods->deallocate(map); | 289 kv_list->map_methods->deallocate(map); |
| 289 kv_list->list_methods->deallocate(&kv_list->list.base); | 290 kv_list->list_methods->deallocate(&kv_list->list.base); |
| 290 } | 291 } |
| 291 | 292 |
| 292 static void cx_kvl_map_clear(struct cx_map_s *map) { | 293 static void cx_kvl_map_clear(struct cx_map_s *map) { |
| 294 cx_kv_list_update_destructors(kv_list); | 295 cx_kv_list_update_destructors(kv_list); |
| 295 kv_list->list_methods->clear(&kv_list->list.base); | 296 kv_list->list_methods->clear(&kv_list->list.base); |
| 296 kv_list->map_methods->clear(map); | 297 kv_list->map_methods->clear(map); |
| 297 } | 298 } |
| 298 | 299 |
| 300 static void *cx_kvl_map_get(const CxMap *map, CxHashKey key) { | |
| 301 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; | |
| 302 void *node_data = kv_list->map_methods->get(map, key); | |
| 303 if (node_data == NULL) return NULL; // LCOV_EXCL_LINE | |
| 304 // return the node data | |
| 305 return kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data; | |
| 306 } | |
| 307 | |
| 308 static int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) { | |
| 309 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; | |
| 310 | |
| 311 void *node_data; | |
| 312 if (kv_list->map_methods->remove(map, key, &node_data)) { | |
| 313 return 1; | |
| 314 } | |
| 315 // we cannot just call a list method (because we don't have the index) | |
| 316 // and tbh. we also don't want to (because it's not performant when we | |
| 317 // can have the node ptr directly instead) | |
| 318 // therefore, we re-implement the logic ourselves | |
| 319 | |
| 320 // check if the outside caller want's us to return or to destroy the element | |
| 321 if (targetbuf == NULL) { | |
| 322 // patch the destructors and invoke them through the wrapper | |
| 323 cx_kv_list_update_destructors(kv_list); | |
| 324 cx_invoke_advanced_destructor(&kv_list->list.base, node_data); | |
| 325 } else { | |
| 326 // copy the element to the target buffer | |
| 327 memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size); | |
| 328 } | |
| 329 | |
| 330 // calculate the address of the node | |
| 331 void *node_ptr = (char*)node_data - kv_list->list.loc_data; | |
| 332 | |
| 333 // unlink the node | |
| 334 cx_linked_list_remove( | |
| 335 &kv_list->list.begin, | |
| 336 &kv_list->list.end, | |
| 337 kv_list->list.loc_prev, | |
| 338 kv_list->list.loc_next, | |
| 339 node_ptr | |
| 340 ); | |
| 341 | |
| 342 // decrement the list's size | |
| 343 kv_list->list.base.collection.size--; | |
| 344 | |
| 345 // deallocate the node | |
| 346 cxFree(kv_list->list.base.collection.allocator, node_ptr); | |
| 347 | |
| 348 return 0; | |
| 349 } | |
| 350 | |
| 299 static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) { | 351 static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) { |
| 300 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; | 352 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; |
| 301 // if the hash has not yet been computed, do it now | 353 // if the hash has not yet been computed, do it now |
| 302 if (key.hash == 0) { | 354 if (key.hash == 0) { |
| 303 cx_hash_murmur(&key); | 355 cx_hash_murmur(&key); |
| 304 } | 356 } |
| 305 | 357 |
| 306 // reserve memory in the map first | 358 // remove any existing element first |
| 359 cx_kvl_map_remove(map, key, NULL); | |
| 360 | |
| 361 // now reserve new memory in the map | |
| 307 void **map_data = kv_list->map_methods->put(map, key, NULL); | 362 void **map_data = kv_list->map_methods->put(map, key, NULL); |
| 308 if (map_data == NULL) return NULL; // LCOV_EXCL_LINE | 363 if (map_data == NULL) return NULL; // LCOV_EXCL_LINE |
| 309 | 364 |
| 310 // insert the data into the list (which most likely destroys the sorted property) | 365 // insert the data into the list (which most likely destroys the sorted property) |
| 311 kv_list->list.base.collection.sorted = false; | 366 kv_list->list.base.collection.sorted = false; |
| 326 *key_ptr = key; | 381 *key_ptr = key; |
| 327 | 382 |
| 328 // we must return node_data here and not map_data, | 383 // we must return node_data here and not map_data, |
| 329 // because the node_data is the actual element of this collection | 384 // because the node_data is the actual element of this collection |
| 330 return node_data; | 385 return node_data; |
| 331 } | |
| 332 | |
| 333 void *cx_kvl_map_get(const CxMap *map, CxHashKey key) { | |
| 334 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; | |
| 335 void *node_data = kv_list->map_methods->get(map, key); | |
| 336 if (node_data == NULL) return NULL; // LCOV_EXCL_LINE | |
| 337 // return the node data | |
| 338 return kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data; | |
| 339 } | |
| 340 | |
| 341 int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) { | |
| 342 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; | |
| 343 | |
| 344 void *node_data; | |
| 345 if (kv_list->map_methods->remove(map, key, &node_data)) { | |
| 346 return 1; | |
| 347 } | |
| 348 // we cannot just call a list method (because we don't have the index) | |
| 349 // and tbh. we also don't want to (because it's not performant when we | |
| 350 // can have the node ptr directly instead) | |
| 351 // therefore, we re-implement the logic ourselves | |
| 352 | |
| 353 // check if the outside caller want's us to return or to destroy the element | |
| 354 if (targetbuf == NULL) { | |
| 355 // patch the destructors and invoke them through the wrapper | |
| 356 cx_kv_list_update_destructors(kv_list); | |
| 357 cx_invoke_advanced_destructor(&kv_list->list.base, node_data); | |
| 358 } else { | |
| 359 // copy the element to the target buffer | |
| 360 memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size); | |
| 361 } | |
| 362 | |
| 363 // calculate the address of the node | |
| 364 void *node_ptr = (char*)node_data - kv_list->list.loc_data; | |
| 365 | |
| 366 // unlink the node | |
| 367 cx_linked_list_remove( | |
| 368 &kv_list->list.begin, | |
| 369 &kv_list->list.end, | |
| 370 kv_list->list.loc_prev, | |
| 371 kv_list->list.loc_next, | |
| 372 node_ptr | |
| 373 ); | |
| 374 | |
| 375 // decrement the list's size | |
| 376 kv_list->list.base.collection.size--; | |
| 377 | |
| 378 // deallocate the node | |
| 379 cxFree(kv_list->list.base.collection.allocator, node_ptr); | |
| 380 | |
| 381 return 0; | |
| 382 } | 386 } |
| 383 | 387 |
| 384 static void *cx_kvl_iter_current_entry(const void *it) { | 388 static void *cx_kvl_iter_current_entry(const void *it) { |
| 385 const CxMapIterator *iter = it; | 389 const CxMapIterator *iter = it; |
| 386 return (void*)&iter->entry; | 390 return (void*)&iter->entry; |
| 453 static bool cx_kvl_iter_valid(const void *it) { | 457 static bool cx_kvl_iter_valid(const void *it) { |
| 454 const CxMapIterator *iter = it; | 458 const CxMapIterator *iter = it; |
| 455 return iter->elem != NULL; | 459 return iter->elem != NULL; |
| 456 } | 460 } |
| 457 | 461 |
| 458 CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) { | 462 static CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) { |
| 459 CxMapIterator iter = {0}; | 463 CxMapIterator iter = {0}; |
| 460 | 464 |
| 461 iter.type = type; | 465 iter.type = type; |
| 462 iter.map = (CxMap*)map; | 466 iter.map = (CxMap*)map; |
| 463 // although we iterate over the list, we only report that many elements that have a key in the map | 467 // although we iterate over the list, we only report that many elements that have a key in the map |
