comparison: ucx/hash_map.c
ucx/hash_map.c
- branch
- dav-2
- changeset 891
- 4d58cbcc9efa
- parent 889
- 42cdbf9bbd49
equal
deleted
inserted
replaced
| 890:e77ccf1c4bb3 | 891:4d58cbcc9efa |
|---|---|
| 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 void *cx_hash_map_put( | 81 static CxMapEntry 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; |
| 115 // allocate new element | 115 // allocate new element |
| 116 struct cx_hash_map_element_s *e = cxMalloc( | 116 struct cx_hash_map_element_s *e = cxMalloc( |
| 117 allocator, | 117 allocator, |
| 118 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size | 118 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size |
| 119 ); | 119 ); |
| 120 if (e == NULL) return NULL; | 120 if (e == NULL) return (CxMapEntry){NULL, NULL}; // LCOV_EXCL_LINE |
| 121 | 121 |
| 122 // write the value | 122 // write the value |
| 123 if (value == NULL) { | 123 if (value == NULL) { |
| 124 memset(e->data, 0, map->collection.elem_size); | 124 memset(e->data, 0, map->collection.elem_size); |
| 125 } else if (map->collection.store_pointer) { | 125 } else if (map->collection.store_pointer) { |
| 128 memcpy(e->data, value, map->collection.elem_size); | 128 memcpy(e->data, value, map->collection.elem_size); |
| 129 } | 129 } |
| 130 | 130 |
| 131 // copy the key | 131 // copy the key |
| 132 void *kd = cxMalloc(allocator, key.len); | 132 void *kd = cxMalloc(allocator, key.len); |
| 133 if (kd == NULL) { | 133 if (kd == NULL) { // LCOV_EXCL_START |
| 134 cxFree(allocator, e); | 134 cxFree(allocator, e); |
| 135 return NULL; | 135 return (CxMapEntry){NULL, NULL}; |
| 136 } | 136 } // LCOV_EXCL_STOP |
| 137 memcpy(kd, key.data, key.len); | 137 memcpy(kd, key.data, key.len); |
| 138 e->key.data = kd; | 138 e->key.data = kd; |
| 139 e->key.len = key.len; | 139 e->key.len = key.len; |
| 140 e->key.hash = hash; | 140 e->key.hash = hash; |
| 141 | 141 |
| 150 | 150 |
| 151 // increase the size | 151 // increase the size |
| 152 map->collection.size++; | 152 map->collection.size++; |
| 153 } | 153 } |
| 154 | 154 |
| 155 // return pointer to the element | 155 // return the entry |
| 156 return elm->data; | 156 return (CxMapEntry){&elm->key, elm->data}; |
| 157 } | 157 } |
| 158 | 158 |
| 159 static void cx_hash_map_unlink( | 159 static void cx_hash_map_unlink( |
| 160 struct cx_hash_map_s *hash_map, | 160 struct cx_hash_map_s *hash_map, |
| 161 size_t slot, | 161 size_t slot, |
| 412 if (buckets == 0) { | 412 if (buckets == 0) { |
| 413 // implementation defined default | 413 // implementation defined default |
| 414 buckets = 16; | 414 buckets = 16; |
| 415 } | 415 } |
| 416 | 416 |
| 417 struct cx_hash_map_s *map = cxCalloc(allocator, 1, | 417 struct cx_hash_map_s *map = cxZalloc(allocator, sizeof(struct cx_hash_map_s)); |
| 418 sizeof(struct cx_hash_map_s)); | |
| 419 if (map == NULL) return NULL; | 418 if (map == NULL) return NULL; |
| 420 | 419 |
| 421 // initialize hash map members | 420 // initialize hash map members |
| 422 map->bucket_count = buckets; | 421 map->bucket_count = buckets; |
| 423 map->buckets = cxCalloc(allocator, buckets, | 422 map->buckets = cxCalloc(allocator, buckets, |
| 431 map->base.cl = &cx_hash_map_class; | 430 map->base.cl = &cx_hash_map_class; |
| 432 map->base.collection.allocator = allocator; | 431 map->base.collection.allocator = allocator; |
| 433 | 432 |
| 434 if (itemsize > 0) { | 433 if (itemsize > 0) { |
| 435 map->base.collection.elem_size = itemsize; | 434 map->base.collection.elem_size = itemsize; |
| 435 map->base.collection.advanced_cmp = cx_ccmp_memcmp; | |
| 436 map->base.collection.cmp_data = &map->base.collection.elem_size; | |
| 436 } else { | 437 } else { |
| 437 map->base.collection.elem_size = sizeof(void *); | 438 map->base.collection.elem_size = sizeof(void *); |
| 438 map->base.collection.store_pointer = true; | 439 map->base.collection.store_pointer = true; |
| 440 map->base.collection.simple_cmp = cx_cmp_ptr; | |
| 439 } | 441 } |
| 440 | 442 |
| 441 return (CxMap *) map; | 443 return (CxMap *) map; |
| 442 } | 444 } |
| 443 | 445 |
| 445 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 447 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 446 if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) { | 448 if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) { |
| 447 | 449 |
| 448 size_t new_bucket_count = (map->collection.size * 5) >> 1; | 450 size_t new_bucket_count = (map->collection.size * 5) >> 1; |
| 449 if (new_bucket_count < hash_map->bucket_count) { | 451 if (new_bucket_count < hash_map->bucket_count) { |
| 452 // LCOV_EXCL_START | |
| 450 errno = EOVERFLOW; | 453 errno = EOVERFLOW; |
| 451 return 1; | 454 return 1; |
| 452 } | 455 } // LCOV_EXCL_STOP |
| 453 struct cx_hash_map_element_s **new_buckets = cxCalloc( | 456 struct cx_hash_map_element_s **new_buckets = cxCalloc( |
| 454 map->collection.allocator, | 457 map->collection.allocator, |
| 455 new_bucket_count, sizeof(struct cx_hash_map_element_s *) | 458 new_bucket_count, sizeof(struct cx_hash_map_element_s *) |
| 456 ); | 459 ); |
| 457 | 460 |
| 458 if (new_buckets == NULL) return 1; | 461 if (new_buckets == NULL) return 1; // LCOV_EXCL_LINE |
| 459 | 462 |
| 460 // iterate through the elements and assign them to their new slots | 463 // iterate through the elements and assign them to their new slots |
| 461 for (size_t slot = 0; slot < hash_map->bucket_count; slot++) { | 464 for (size_t slot = 0; slot < hash_map->bucket_count; slot++) { |
| 462 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; | 465 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; |
| 463 while (elm != NULL) { | 466 while (elm != NULL) { |
