| /* |
| * |
| * Copyright 2015 gRPC authors. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| * |
| */ |
| |
| #include "src/core/ext/census/hash_table.h" |
| |
| #include <stddef.h> |
| #include <stdio.h> |
| |
| #include <grpc/support/alloc.h> |
| #include <grpc/support/log.h> |
| #include <grpc/support/port_platform.h> |
| |
| #define CENSUS_HT_NUM_BUCKETS 1999 |
| |
| /* A single hash table data entry */ |
| typedef struct ht_entry { |
| census_ht_key key; |
| void *data; |
| struct ht_entry *next; |
| } ht_entry; |
| |
| /* hash table bucket */ |
| typedef struct bucket { |
| /* NULL if bucket is empty */ |
| ht_entry *next; |
| /* -1 if all buckets are empty. */ |
| int32_t prev_non_empty_bucket; |
| /* -1 if all buckets are empty. */ |
| int32_t next_non_empty_bucket; |
| } bucket; |
| |
| struct unresizable_hash_table { |
| /* Number of entries in the table */ |
| size_t size; |
| /* Number of buckets */ |
| uint32_t num_buckets; |
| /* Array of buckets initialized at creation time. Memory consumption is |
| 16 bytes per bucket on a 64-bit platform. */ |
| bucket *buckets; |
| /* Index of the first non-empty bucket. -1 iff size == 0. */ |
| int32_t first_non_empty_bucket; |
| /* Index of the last non_empty bucket. -1 iff size == 0. */ |
| int32_t last_non_empty_bucket; |
| /* Immutable options of this hash table, initialized at creation time. */ |
| census_ht_option options; |
| }; |
| |
| typedef struct entry_locator { |
| int32_t bucket_idx; |
| int is_first_in_chain; |
| int found; |
| ht_entry *prev_entry; |
| } entry_locator; |
| |
| /* Asserts if option is not valid. */ |
| void check_options(const census_ht_option *option) { |
| GPR_ASSERT(option != NULL); |
| GPR_ASSERT(option->num_buckets > 0); |
| GPR_ASSERT(option->key_type == CENSUS_HT_UINT64 || |
| option->key_type == CENSUS_HT_POINTER); |
| if (option->key_type == CENSUS_HT_UINT64) { |
| GPR_ASSERT(option->hash == NULL); |
| } else if (option->key_type == CENSUS_HT_POINTER) { |
| GPR_ASSERT(option->hash != NULL); |
| GPR_ASSERT(option->compare_keys != NULL); |
| } |
| } |
| |
| #define REMOVE_NEXT(options, ptr) \ |
| do { \ |
| ht_entry *tmp = (ptr)->next; \ |
| (ptr)->next = tmp->next; \ |
| delete_entry(options, tmp); \ |
| } while (0) |
| |
| static void delete_entry(const census_ht_option *opt, ht_entry *p) { |
| if (opt->delete_data != NULL) { |
| opt->delete_data(p->data); |
| } |
| if (opt->delete_key != NULL) { |
| opt->delete_key(p->key.ptr); |
| } |
| gpr_free(p); |
| } |
| |
| static uint64_t hash(const census_ht_option *opt, census_ht_key key) { |
| return opt->key_type == CENSUS_HT_UINT64 ? key.val : opt->hash(key.ptr); |
| } |
| |
| census_ht *census_ht_create(const census_ht_option *option) { |
| int i; |
| census_ht *ret = NULL; |
| check_options(option); |
| ret = (census_ht *)gpr_malloc(sizeof(census_ht)); |
| ret->size = 0; |
| ret->num_buckets = option->num_buckets; |
| ret->buckets = (bucket *)gpr_malloc(sizeof(bucket) * ret->num_buckets); |
| ret->options = *option; |
| /* initialize each bucket */ |
| for (i = 0; i < ret->options.num_buckets; i++) { |
| ret->buckets[i].prev_non_empty_bucket = -1; |
| ret->buckets[i].next_non_empty_bucket = -1; |
| ret->buckets[i].next = NULL; |
| } |
| return ret; |
| } |
| |
| static int32_t find_bucket_idx(const census_ht *ht, census_ht_key key) { |
| return hash(&ht->options, key) % ht->num_buckets; |
| } |
| |
| static int keys_match(const census_ht_option *opt, const ht_entry *p, |
| const census_ht_key key) { |
| GPR_ASSERT(opt->key_type == CENSUS_HT_UINT64 || |
| opt->key_type == CENSUS_HT_POINTER); |
| if (opt->key_type == CENSUS_HT_UINT64) return p->key.val == key.val; |
| return !opt->compare_keys((p->key).ptr, key.ptr); |
| } |
| |
| static entry_locator ht_find(const census_ht *ht, census_ht_key key) { |
| entry_locator loc = {0, 0, 0, NULL}; |
| int32_t idx = 0; |
| ht_entry *ptr = NULL; |
| GPR_ASSERT(ht != NULL); |
| idx = find_bucket_idx(ht, key); |
| ptr = ht->buckets[idx].next; |
| if (ptr == NULL) { |
| /* bucket is empty */ |
| return loc; |
| } |
| if (keys_match(&ht->options, ptr, key)) { |
| loc.bucket_idx = idx; |
| loc.is_first_in_chain = 1; |
| loc.found = 1; |
| return loc; |
| } else { |
| for (; ptr->next != NULL; ptr = ptr->next) { |
| if (keys_match(&ht->options, ptr->next, key)) { |
| loc.bucket_idx = idx; |
| loc.is_first_in_chain = 0; |
| loc.found = 1; |
| loc.prev_entry = ptr; |
| return loc; |
| } |
| } |
| } |
| /* Could not find the key */ |
| return loc; |
| } |
| |
| void *census_ht_find(const census_ht *ht, census_ht_key key) { |
| entry_locator loc = ht_find(ht, key); |
| if (loc.found == 0) { |
| return NULL; |
| } |
| return loc.is_first_in_chain ? ht->buckets[loc.bucket_idx].next->data |
| : loc.prev_entry->next->data; |
| } |
| |
| void census_ht_insert(census_ht *ht, census_ht_key key, void *data) { |
| int32_t idx = find_bucket_idx(ht, key); |
| ht_entry *ptr = NULL; |
| entry_locator loc = ht_find(ht, key); |
| if (loc.found) { |
| /* Replace old value with new value. */ |
| ptr = loc.is_first_in_chain ? ht->buckets[loc.bucket_idx].next |
| : loc.prev_entry->next; |
| if (ht->options.delete_data != NULL) { |
| ht->options.delete_data(ptr->data); |
| } |
| ptr->data = data; |
| return; |
| } |
| |
| /* first entry in the table. */ |
| if (ht->size == 0) { |
| ht->buckets[idx].next_non_empty_bucket = -1; |
| ht->buckets[idx].prev_non_empty_bucket = -1; |
| ht->first_non_empty_bucket = idx; |
| ht->last_non_empty_bucket = idx; |
| } else if (ht->buckets[idx].next == NULL) { |
| /* first entry in the bucket. */ |
| ht->buckets[ht->last_non_empty_bucket].next_non_empty_bucket = idx; |
| ht->buckets[idx].prev_non_empty_bucket = ht->last_non_empty_bucket; |
| ht->buckets[idx].next_non_empty_bucket = -1; |
| ht->last_non_empty_bucket = idx; |
| } |
| ptr = (ht_entry *)gpr_malloc(sizeof(ht_entry)); |
| ptr->key = key; |
| ptr->data = data; |
| ptr->next = ht->buckets[idx].next; |
| ht->buckets[idx].next = ptr; |
| ht->size++; |
| } |
| |
| void census_ht_erase(census_ht *ht, census_ht_key key) { |
| entry_locator loc = ht_find(ht, key); |
| if (loc.found == 0) { |
| /* noop if not found */ |
| return; |
| } |
| ht->size--; |
| if (loc.is_first_in_chain) { |
| bucket *b = &ht->buckets[loc.bucket_idx]; |
| GPR_ASSERT(b->next != NULL); |
| /* The only entry in the bucket */ |
| if (b->next->next == NULL) { |
| int prev = b->prev_non_empty_bucket; |
| int next = b->next_non_empty_bucket; |
| if (prev != -1) { |
| ht->buckets[prev].next_non_empty_bucket = next; |
| } else { |
| ht->first_non_empty_bucket = next; |
| } |
| if (next != -1) { |
| ht->buckets[next].prev_non_empty_bucket = prev; |
| } else { |
| ht->last_non_empty_bucket = prev; |
| } |
| } |
| REMOVE_NEXT(&ht->options, b); |
| } else { |
| GPR_ASSERT(loc.prev_entry->next != NULL); |
| REMOVE_NEXT(&ht->options, loc.prev_entry); |
| } |
| } |
| |
| /* Returns NULL if input table is empty. */ |
| census_ht_kv *census_ht_get_all_elements(const census_ht *ht, size_t *num) { |
| census_ht_kv *ret = NULL; |
| int i = 0; |
| int32_t idx = -1; |
| GPR_ASSERT(ht != NULL && num != NULL); |
| *num = ht->size; |
| if (*num == 0) { |
| return NULL; |
| } |
| |
| ret = (census_ht_kv *)gpr_malloc(sizeof(census_ht_kv) * ht->size); |
| idx = ht->first_non_empty_bucket; |
| while (idx >= 0) { |
| ht_entry *ptr = ht->buckets[idx].next; |
| for (; ptr != NULL; ptr = ptr->next) { |
| ret[i].k = ptr->key; |
| ret[i].v = ptr->data; |
| i++; |
| } |
| idx = ht->buckets[idx].next_non_empty_bucket; |
| } |
| return ret; |
| } |
| |
| static void ht_delete_entry_chain(const census_ht_option *options, |
| ht_entry *first) { |
| if (first == NULL) { |
| return; |
| } |
| if (first->next != NULL) { |
| ht_delete_entry_chain(options, first->next); |
| } |
| delete_entry(options, first); |
| } |
| |
| void census_ht_destroy(census_ht *ht) { |
| unsigned i; |
| for (i = 0; i < ht->num_buckets; ++i) { |
| ht_delete_entry_chain(&ht->options, ht->buckets[i].next); |
| } |
| gpr_free(ht->buckets); |
| gpr_free(ht); |
| } |
| |
| size_t census_ht_get_size(const census_ht *ht) { return ht->size; } |