diff options
Diffstat (limited to 'src/core/lib/statistics/hash_table.c')
-rw-r--r-- | src/core/lib/statistics/hash_table.c | 303 |
1 files changed, 0 insertions, 303 deletions
diff --git a/src/core/lib/statistics/hash_table.c b/src/core/lib/statistics/hash_table.c deleted file mode 100644 index 18b7442a0c..0000000000 --- a/src/core/lib/statistics/hash_table.c +++ /dev/null @@ -1,303 +0,0 @@ -/* - * - * Copyright 2015-2016, Google Inc. - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following disclaimer - * in the documentation and/or other materials provided with the - * distribution. - * * Neither the name of Google Inc. nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - */ - -#include "src/core/lib/statistics/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; } |