comparison: src/hash_map.c
src/hash_map.c
- changeset 688
- c27fa8b67286
- parent 686
- 64919f63f059
- child 690
- 2c2304622981
equal
deleted
inserted
replaced
| 687:612ed521b1c5 | 688:c27fa8b67286 |
|---|---|
| 222 | 222 |
| 223 static void *cx_hash_map_get( | 223 static void *cx_hash_map_get( |
| 224 CxMap const *map, | 224 CxMap const *map, |
| 225 CxHashKey key | 225 CxHashKey key |
| 226 ) { | 226 ) { |
| 227 // we can safely cast, because we know when remove=false, the map stays untouched | 227 // we can safely cast, because we know the map stays untouched |
| 228 return cx_hash_map_get_remove((CxMap *) map, key, false, false); | 228 return cx_hash_map_get_remove((CxMap *) map, key, false, false); |
| 229 } | 229 } |
| 230 | 230 |
| 231 static void *cx_hash_map_remove( | 231 static void *cx_hash_map_remove( |
| 232 CxMap *map, | 232 CxMap *map, |
| 426 if (buckets == 0) { | 426 if (buckets == 0) { |
| 427 // implementation defined default | 427 // implementation defined default |
| 428 buckets = 16; | 428 buckets = 16; |
| 429 } | 429 } |
| 430 | 430 |
| 431 struct cx_hash_map_s *map = cxCalloc(allocator, 1, sizeof(struct cx_hash_map_s)); | 431 struct cx_hash_map_s *map = cxCalloc(allocator, 1, |
| 432 sizeof(struct cx_hash_map_s)); | |
| 432 if (map == NULL) return NULL; | 433 if (map == NULL) return NULL; |
| 433 | 434 |
| 434 // initialize hash map members | 435 // initialize hash map members |
| 435 map->bucket_count = buckets; | 436 map->bucket_count = buckets; |
| 436 map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *)); | 437 map->buckets = cxCalloc(allocator, buckets, |
| 438 sizeof(struct cx_hash_map_element_s *)); | |
| 437 if (map->buckets == NULL) { | 439 if (map->buckets == NULL) { |
| 438 cxFree(allocator, map); | 440 cxFree(allocator, map); |
| 439 return NULL; | 441 return NULL; |
| 440 } | 442 } |
| 441 | 443 |
| 457 int cxMapRehash(CxMap *map) { | 459 int cxMapRehash(CxMap *map) { |
| 458 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 460 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 459 if (map->size > ((hash_map->bucket_count * 3) >> 2)) { | 461 if (map->size > ((hash_map->bucket_count * 3) >> 2)) { |
| 460 | 462 |
| 461 size_t new_bucket_count = (map->size * 5) >> 1; | 463 size_t new_bucket_count = (map->size * 5) >> 1; |
| 462 struct cx_hash_map_element_s **new_buckets = cxCalloc(map->allocator, | 464 struct cx_hash_map_element_s **new_buckets = cxCalloc( |
| 463 new_bucket_count, sizeof(struct cx_hash_map_element_s *)); | 465 map->allocator, |
| 466 new_bucket_count, sizeof(struct cx_hash_map_element_s *) | |
| 467 ); | |
| 464 | 468 |
| 465 if (new_buckets == NULL) { | 469 if (new_buckets == NULL) { |
| 466 return 1; | 470 return 1; |
| 467 } | 471 } |
| 468 | 472 |
| 474 size_t new_slot = elm->key.hash % new_bucket_count; | 478 size_t new_slot = elm->key.hash % new_bucket_count; |
| 475 | 479 |
| 476 // find position where to insert | 480 // find position where to insert |
| 477 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot]; | 481 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot]; |
| 478 struct cx_hash_map_element_s *bucket_prev = NULL; | 482 struct cx_hash_map_element_s *bucket_prev = NULL; |
| 479 while (bucket_next != NULL && bucket_next->key.hash < elm->key.hash) { | 483 while (bucket_next != NULL && |
| 484 bucket_next->key.hash < elm->key.hash) { | |
| 480 bucket_prev = bucket_next; | 485 bucket_prev = bucket_next; |
| 481 bucket_next = bucket_next->next; | 486 bucket_next = bucket_next->next; |
| 482 } | 487 } |
| 483 | 488 |
| 484 // insert | 489 // insert |
