aboutsummaryrefslogtreecommitdiffhomepage
path: root/test/core/statistics/hash_table_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'test/core/statistics/hash_table_test.cc')
-rw-r--r--test/core/statistics/hash_table_test.cc286
1 files changed, 0 insertions, 286 deletions
diff --git a/test/core/statistics/hash_table_test.cc b/test/core/statistics/hash_table_test.cc
deleted file mode 100644
index b660006b8a..0000000000
--- a/test/core/statistics/hash_table_test.cc
+++ /dev/null
@@ -1,286 +0,0 @@
-/*
- *
- * 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 <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "src/core/ext/census/hash_table.h"
-
-#include <grpc/support/alloc.h>
-#include <grpc/support/log.h>
-#include <grpc/support/time.h>
-#include "src/core/lib/support/murmur_hash.h"
-#include "src/core/lib/support/string.h"
-#include "test/core/util/test_config.h"
-
-static uint64_t hash64(const void* k) {
- size_t len = strlen(k);
- uint64_t higher = gpr_murmur_hash3((const char*)k, len / 2, 0);
- return higher << 32 |
- gpr_murmur_hash3((const char*)(k) + len / 2, len - len / 2, 0);
-}
-
-static int cmp_str_keys(const void* k1, const void* k2) {
- return strcmp((const char*)k1, (const char*)k2);
-}
-
-static uint64_t force_collision(const void* k) {
- return (1997 + hash64(k) % 3);
-}
-
-static void free_data(void* data) { gpr_free(data); }
-
-/* Basic tests that empty hash table can be created and destroyed. */
-static void test_create_table(void) {
- /* Create table with uint64 key type */
- census_ht* ht = NULL;
- census_ht_option ht_options = {
- CENSUS_HT_UINT64, 1999, NULL, NULL, NULL, NULL};
- ht = census_ht_create(&ht_options);
- GPR_ASSERT(ht != NULL);
- GPR_ASSERT(census_ht_get_size(ht) == 0);
- census_ht_destroy(ht);
- /* Create table with pointer key type */
- ht = NULL;
- ht_options.key_type = CENSUS_HT_POINTER;
- ht_options.hash = &hash64;
- ht_options.compare_keys = &cmp_str_keys;
- ht = census_ht_create(&ht_options);
- GPR_ASSERT(ht != NULL);
- GPR_ASSERT(census_ht_get_size(ht) == 0);
- census_ht_destroy(ht);
-}
-
-static void test_table_with_int_key(void) {
- census_ht_option opt = {CENSUS_HT_UINT64, 7, NULL, NULL, NULL, NULL};
- census_ht* ht = census_ht_create(&opt);
- uint64_t i = 0;
- uint64_t sum_of_keys = 0;
- size_t num_elements;
- census_ht_kv* elements = NULL;
- GPR_ASSERT(ht != NULL);
- GPR_ASSERT(census_ht_get_size(ht) == 0);
- elements = census_ht_get_all_elements(ht, &num_elements);
- GPR_ASSERT(num_elements == 0);
- GPR_ASSERT(elements == NULL);
- for (i = 0; i < 20; ++i) {
- census_ht_key key;
- key.val = i;
- census_ht_insert(ht, key, (void*)(intptr_t)i);
- GPR_ASSERT(census_ht_get_size(ht) == i + 1);
- }
- for (i = 0; i < 20; i++) {
- uint64_t* val = NULL;
- census_ht_key key;
- key.val = i;
- val = static_cast<uint64_t*>(census_ht_find(ht, key));
- GPR_ASSERT(val == (void*)(intptr_t)i);
- }
- elements = census_ht_get_all_elements(ht, &num_elements);
- GPR_ASSERT(elements != NULL);
- GPR_ASSERT(num_elements == 20);
- for (i = 0; i < num_elements; i++) {
- sum_of_keys += elements[i].k.val;
- }
- GPR_ASSERT(sum_of_keys == 190);
- gpr_free(elements);
- census_ht_destroy(ht);
-}
-
-/* Test that there is no memory leak when keys and values are owned by table. */
-static void test_value_and_key_deleter(void) {
- census_ht_option opt = {CENSUS_HT_POINTER, 7, &hash64,
- &cmp_str_keys, &free_data, &free_data};
- census_ht* ht = census_ht_create(&opt);
- census_ht_key key;
- char* val = NULL;
- char* val2 = NULL;
- key.ptr = gpr_malloc(100);
- val = static_cast<char*>(gpr_malloc(10));
- strcpy(val, "value");
- strcpy(key.ptr, "some string as a key");
- GPR_ASSERT(ht != NULL);
- GPR_ASSERT(census_ht_get_size(ht) == 0);
- census_ht_insert(ht, key, val);
- GPR_ASSERT(census_ht_get_size(ht) == 1);
- val = static_cast<char*>(census_ht_find(ht, key));
- GPR_ASSERT(val != NULL);
- GPR_ASSERT(strcmp(val, "value") == 0);
- /* Insert same key different value, old value is overwritten. */
- val2 = static_cast<char*>(gpr_malloc(10));
- strcpy(val2, "v2");
- census_ht_insert(ht, key, val2);
- GPR_ASSERT(census_ht_get_size(ht) == 1);
- val2 = static_cast<char*>(census_ht_find(ht, key));
- GPR_ASSERT(val2 != NULL);
- GPR_ASSERT(strcmp(val2, "v2") == 0);
- census_ht_destroy(ht);
-}
-
-/* Test simple insert and erase operations. */
-static void test_simple_add_and_erase(void) {
- census_ht_option opt = {CENSUS_HT_UINT64, 7, NULL, NULL, NULL, NULL};
- census_ht* ht = census_ht_create(&opt);
- GPR_ASSERT(ht != NULL);
- GPR_ASSERT(census_ht_get_size(ht) == 0);
- {
- census_ht_key key;
- int val = 3;
- key.val = 2;
- census_ht_insert(ht, key, (void*)&val);
- GPR_ASSERT(census_ht_get_size(ht) == 1);
- census_ht_erase(ht, key);
- GPR_ASSERT(census_ht_get_size(ht) == 0);
- /* Erasing a key from an empty table should be noop. */
- census_ht_erase(ht, key);
- GPR_ASSERT(census_ht_get_size(ht) == 0);
- /* Erasing a non-existant key from a table should be noop. */
- census_ht_insert(ht, key, (void*)&val);
- key.val = 3;
- census_ht_insert(ht, key, (void*)&val);
- key.val = 9;
- census_ht_insert(ht, key, (void*)&val);
- GPR_ASSERT(census_ht_get_size(ht) == 3);
- key.val = 1;
- census_ht_erase(ht, key);
- /* size unchanged after deleting non-existant key. */
- GPR_ASSERT(census_ht_get_size(ht) == 3);
- /* size decrease by 1 after deleting an existant key. */
- key.val = 2;
- census_ht_erase(ht, key);
- GPR_ASSERT(census_ht_get_size(ht) == 2);
- }
- census_ht_destroy(ht);
-}
-
-static void test_insertion_and_deletion_with_high_collision_rate(void) {
- census_ht_option opt = {CENSUS_HT_POINTER, 13, &force_collision,
- &cmp_str_keys, NULL, NULL};
- census_ht* ht = census_ht_create(&opt);
- char key_str[1000][GPR_LTOA_MIN_BUFSIZE];
- uint64_t val = 0;
- unsigned i = 0;
- for (i = 0; i < 1000; i++) {
- census_ht_key key;
- key.ptr = key_str[i];
- gpr_ltoa(i, key_str[i]);
- census_ht_insert(ht, key, (void*)(&val));
- gpr_log(GPR_INFO, "%d\n", i);
- GPR_ASSERT(census_ht_get_size(ht) == (i + 1));
- }
- for (i = 0; i < 1000; i++) {
- census_ht_key key;
- key.ptr = key_str[i];
- census_ht_erase(ht, key);
- GPR_ASSERT(census_ht_get_size(ht) == (999 - i));
- }
- census_ht_destroy(ht);
-}
-
-static void test_table_with_string_key(void) {
- census_ht_option opt = {CENSUS_HT_POINTER, 7, &hash64,
- &cmp_str_keys, NULL, NULL};
- census_ht* ht = census_ht_create(&opt);
- const char* keys[] = {
- "k1", "a", "000", "apple", "banana_a_long_long_long_banana",
- "%$", "111", "foo", "b"};
- const int vals[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
- int i = 0;
- GPR_ASSERT(ht != NULL);
- GPR_ASSERT(census_ht_get_size(ht) == 0);
- for (i = 0; i < 9; i++) {
- census_ht_key key;
- key.ptr = (void*)(keys[i]);
- census_ht_insert(ht, key, (void*)(vals + i));
- }
- GPR_ASSERT(census_ht_get_size(ht) == 9);
- for (i = 0; i < 9; i++) {
- census_ht_key key;
- int* val_ptr;
- key.ptr = (void*)(keys[i]);
- val_ptr = static_cast<int*>(census_ht_find(ht, key));
- GPR_ASSERT(*val_ptr == vals[i]);
- }
- {
- /* inserts duplicate keys */
- census_ht_key key;
- int* val_ptr = NULL;
- key.ptr = (void*)(keys[2]);
- census_ht_insert(ht, key, (void*)(vals + 8));
- /* expect value to be over written by new insertion */
- GPR_ASSERT(census_ht_get_size(ht) == 9);
- val_ptr = static_cast<int*>(census_ht_find(ht, key));
- GPR_ASSERT(*val_ptr == vals[8]);
- }
- for (i = 0; i < 9; i++) {
- census_ht_key key;
- int* val_ptr;
- uint32_t expected_tbl_sz = 9 - i;
- GPR_ASSERT(census_ht_get_size(ht) == expected_tbl_sz);
- key.ptr = (void*)(keys[i]);
- val_ptr = static_cast<int*>(census_ht_find(ht, key));
- GPR_ASSERT(val_ptr != NULL);
- census_ht_erase(ht, key);
- GPR_ASSERT(census_ht_get_size(ht) == expected_tbl_sz - 1);
- val_ptr = static_cast<int*>(census_ht_find(ht, key));
- GPR_ASSERT(val_ptr == NULL);
- }
- census_ht_destroy(ht);
-}
-
-static void test_insertion_with_same_key(void) {
- census_ht_option opt = {CENSUS_HT_UINT64, 11, NULL, NULL, NULL, NULL};
- census_ht* ht = census_ht_create(&opt);
- census_ht_key key;
- const char vals[] = {'a', 'b', 'c'};
- char* val_ptr;
- key.val = 3;
- census_ht_insert(ht, key, (void*)&(vals[0]));
- GPR_ASSERT(census_ht_get_size(ht) == 1);
- val_ptr = (char*)census_ht_find(ht, key);
- GPR_ASSERT(val_ptr != NULL);
- GPR_ASSERT(*val_ptr == 'a');
- key.val = 4;
- val_ptr = (char*)census_ht_find(ht, key);
- GPR_ASSERT(val_ptr == NULL);
- key.val = 3;
- census_ht_insert(ht, key, (void*)&(vals[1]));
- GPR_ASSERT(census_ht_get_size(ht) == 1);
- val_ptr = (char*)census_ht_find(ht, key);
- GPR_ASSERT(val_ptr != NULL);
- GPR_ASSERT(*val_ptr == 'b');
- census_ht_insert(ht, key, (void*)&(vals[2]));
- GPR_ASSERT(census_ht_get_size(ht) == 1);
- val_ptr = (char*)census_ht_find(ht, key);
- GPR_ASSERT(val_ptr != NULL);
- GPR_ASSERT(*val_ptr == 'c');
- census_ht_destroy(ht);
-}
-
-int main(int argc, char** argv) {
- grpc_test_init(argc, argv);
- test_create_table();
- test_simple_add_and_erase();
- test_table_with_int_key();
- test_table_with_string_key();
- test_value_and_key_deleter();
- test_insertion_with_same_key();
- test_insertion_and_deletion_with_high_collision_rate();
- return 0;
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-09 00:14:54 +0000