From b7ebd3b8c6fe39f99c40b10c1b563e4adb607b6c Mon Sep 17 00:00:00 2001 From: Nicolas Noble Date: Wed, 26 Nov 2014 16:33:03 -0800 Subject: Initial import. --- src/core/statistics/hash_table.c | 303 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 303 insertions(+) create mode 100644 src/core/statistics/hash_table.c (limited to 'src/core/statistics/hash_table.c') diff --git a/src/core/statistics/hash_table.c b/src/core/statistics/hash_table.c new file mode 100644 index 0000000000..f0105ee683 --- /dev/null +++ b/src/core/statistics/hash_table.c @@ -0,0 +1,303 @@ +/* + * + * Copyright 2014, 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/statistics/hash_table.h" + +#include +#include + +#include +#include +#include + +#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. */ + gpr_int32 prev_non_empty_bucket; + /* -1 if all buckets are empty. */ + gpr_int32 next_non_empty_bucket; +} bucket; + +struct unresizable_hash_table { + /* Number of entries in the table */ + size_t size; + /* Number of buckets */ + gpr_uint32 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. */ + gpr_int32 first_non_empty_bucket; + /* Index of the last non_empty bucket. -1 iff size == 0. */ + gpr_int32 last_non_empty_bucket; + /* Immutable options of this hash table, initialized at creation time. */ + census_ht_option options; +}; + +typedef struct entry_locator { + gpr_int32 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 gpr_uint64 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 gpr_int32 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) { + if (opt->key_type == CENSUS_HT_UINT64) return p->key.val == key.val; + if (opt->key_type == CENSUS_HT_POINTER) + return !opt->compare_keys((p->key).ptr, key.ptr); + return 0; +} + +static entry_locator ht_find(const census_ht* ht, census_ht_key key) { + entry_locator loc = {0, 0, 0, NULL}; + gpr_int32 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) { + gpr_int32 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; + gpr_int32 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) { + int 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; } -- cgit v1.2.3