aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/ext/census/hash_table.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/core/ext/census/hash_table.c')
-rw-r--r--src/core/ext/census/hash_table.c303
1 files changed, 303 insertions, 0 deletions
diff --git a/src/core/ext/census/hash_table.c b/src/core/ext/census/hash_table.c
new file mode 100644
index 0000000000..ee6fdfc6e8
--- /dev/null
+++ b/src/core/ext/census/hash_table.c
@@ -0,0 +1,303 @@
+/*
+ *
+ * Copyright 2015, 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/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; }