comparison: src/hash_map.c
src/hash_map.c
- changeset 562
- fd3368c20413
- parent 560
- 2d6a3e2dc8ff
- child 563
- 69a83fad8a35
equal
deleted
inserted
replaced
| 561:bb17790af41e | 562:fd3368c20413 |
|---|---|
| 394 map->base.allocator = allocator; | 394 map->base.allocator = allocator; |
| 395 map->base.size = 0; | 395 map->base.size = 0; |
| 396 | 396 |
| 397 return (CxMap *) map; | 397 return (CxMap *) map; |
| 398 } | 398 } |
| 399 | |
| 400 int cxMapRehash(CxMap *map) { | |
| 401 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | |
| 402 if (map->size > ((hash_map->bucket_count * 3) >> 2)) { | |
| 403 | |
| 404 size_t new_bucket_count = (map->size * 5) >> 1; | |
| 405 struct cx_hash_map_element_s **new_buckets = cxCalloc(map->allocator, | |
| 406 new_bucket_count, sizeof(struct cx_hash_map_element_s *)); | |
| 407 | |
| 408 if (new_buckets == NULL) { | |
| 409 return 1; | |
| 410 } | |
| 411 | |
| 412 // iterate through the elements and assign them to their new slots | |
| 413 cx_for_n(slot, hash_map->bucket_count) { | |
| 414 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; | |
| 415 while (elm != NULL) { | |
| 416 struct cx_hash_map_element_s *next = elm->next; | |
| 417 size_t new_slot = elm->key.hash % new_bucket_count; | |
| 418 | |
| 419 // find position where to insert | |
| 420 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot]; | |
| 421 struct cx_hash_map_element_s *bucket_prev = NULL; | |
| 422 while (bucket_next != NULL && bucket_next->key.hash < elm->key.hash) { | |
| 423 bucket_prev = bucket_next; | |
| 424 bucket_next = bucket_next->next; | |
| 425 } | |
| 426 | |
| 427 // insert | |
| 428 if (bucket_prev == NULL) { | |
| 429 elm->next = new_buckets[new_slot]; | |
| 430 new_buckets[new_slot] = elm; | |
| 431 } else { | |
| 432 bucket_prev->next = elm; | |
| 433 elm->next = bucket_next; | |
| 434 } | |
| 435 | |
| 436 // advance | |
| 437 elm = next; | |
| 438 } | |
| 439 } | |
| 440 | |
| 441 // assign result to the map | |
| 442 hash_map->bucket_count = new_bucket_count; | |
| 443 cxFree(map->allocator, hash_map->buckets); | |
| 444 hash_map->buckets = new_buckets; | |
| 445 } | |
| 446 return 0; | |
| 447 } |
