diff options
Diffstat (limited to 'test/core/census/intrusive_hash_map_test.c')
| -rw-r--r-- | test/core/census/intrusive_hash_map_test.c | 299 |
1 files changed, 299 insertions, 0 deletions
diff --git a/test/core/census/intrusive_hash_map_test.c b/test/core/census/intrusive_hash_map_test.c new file mode 100644 index 0000000000..552546f9a3 --- /dev/null +++ b/test/core/census/intrusive_hash_map_test.c @@ -0,0 +1,299 @@ +/* + * + * Copyright 2017, 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/intrusive_hash_map.h" + +#include <grpc/support/log.h> +#include <grpc/support/useful.h> +#include "test/core/util/test_config.h" + +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/* The initial size of an intrusive hash map will be 2 to this power. */ +static const uint32_t kInitialLog2Size = 4; + +/* Simple object used for testing intrusive_hash_map. */ +typedef struct object { uint64_t val; } object; + +/* Helper function to allocate and initialize object. */ +static __inline object *make_new_object(uint64_t val) { + object *obj = (object *)gpr_malloc(sizeof(object)); + obj->val = val; + return obj; +} + +/* Wrapper struct for object. */ +typedef struct ptr_item { + INTRUSIVE_HASH_MAP_HEADER; + object *obj; +} ptr_item; + +/* Helper function that creates a new hash map item. It is up to the user to + * free the item that was allocated. */ +static __inline ptr_item *make_ptr_item(uint64_t key, uint64_t value) { + ptr_item *new_item = (ptr_item *)gpr_malloc(sizeof(ptr_item)); + new_item->IHM_key = key; + new_item->IHM_hash_link = NULL; + new_item->obj = make_new_object(value); + return new_item; +} + +/* Helper function to deallocate ptr_item. */ +static void free_ptr_item(void *ptr) { gpr_free(((ptr_item *)ptr)->obj); } + +/* Simple string object used for testing intrusive_hash_map. */ +typedef struct string_item { + INTRUSIVE_HASH_MAP_HEADER; + // User data. + char buf[32]; + uint16_t len; +} string_item; + +/* Helper function to allocate and initialize string object. */ +static string_item *make_string_item(uint64_t key, const char *buf, + uint16_t len) { + string_item *item = (string_item *)gpr_malloc(sizeof(string_item)); + item->IHM_key = key; + item->IHM_hash_link = NULL; + item->len = len; + memcpy(item->buf, buf, sizeof(char) * len); + return item; +} + +/* Helper function for comparing two string objects. */ +static bool compare_string_item(const string_item *A, const string_item *B) { + if (A->IHM_key != B->IHM_key || A->len != B->len) + return false; + else { + for (int i = 0; i < A->len; ++i) { + if (A->buf[i] != B->buf[i]) return false; + } + } + + return true; +} + +void test_empty() { + intrusive_hash_map hash_map; + intrusive_hash_map_init(&hash_map, kInitialLog2Size); + GPR_ASSERT(0 == intrusive_hash_map_size(&hash_map)); + GPR_ASSERT(intrusive_hash_map_empty(&hash_map)); + intrusive_hash_map_free(&hash_map, NULL); +} + +void test_single_item() { + intrusive_hash_map hash_map; + intrusive_hash_map_init(&hash_map, kInitialLog2Size); + + ptr_item *new_item = make_ptr_item(10, 20); + bool ok = intrusive_hash_map_insert(&hash_map, (hm_item *)new_item); + GPR_ASSERT(ok); + + ptr_item *item1 = + (ptr_item *)intrusive_hash_map_find(&hash_map, (uint64_t)10); + GPR_ASSERT(item1->obj->val == 20); + GPR_ASSERT(item1 == new_item); + + ptr_item *item2 = + (ptr_item *)intrusive_hash_map_erase(&hash_map, (uint64_t)10); + GPR_ASSERT(item2 == new_item); + + gpr_free(new_item->obj); + gpr_free(new_item); + GPR_ASSERT(0 == intrusive_hash_map_size(&hash_map)); + intrusive_hash_map_free(&hash_map, &free_ptr_item); +} + +void test_two_items() { + intrusive_hash_map hash_map; + intrusive_hash_map_init(&hash_map, kInitialLog2Size); + + string_item *new_item1 = make_string_item(10, "test1", 5); + bool ok = intrusive_hash_map_insert(&hash_map, (hm_item *)new_item1); + GPR_ASSERT(ok); + string_item *new_item2 = make_string_item(20, "test2", 5); + ok = intrusive_hash_map_insert(&hash_map, (hm_item *)new_item2); + GPR_ASSERT(ok); + + string_item *item1 = + (string_item *)intrusive_hash_map_find(&hash_map, (uint64_t)10); + GPR_ASSERT(compare_string_item(new_item1, item1)); + GPR_ASSERT(item1 == new_item1); + string_item *item2 = + (string_item *)intrusive_hash_map_find(&hash_map, (uint64_t)20); + GPR_ASSERT(compare_string_item(new_item2, item2)); + GPR_ASSERT(item2 == new_item2); + + item1 = (string_item *)intrusive_hash_map_erase(&hash_map, (uint64_t)10); + GPR_ASSERT(item1 == new_item1); + item2 = (string_item *)intrusive_hash_map_erase(&hash_map, (uint64_t)20); + GPR_ASSERT(item2 == new_item2); + + gpr_free(new_item1); + gpr_free(new_item2); + GPR_ASSERT(0 == intrusive_hash_map_size(&hash_map)); + intrusive_hash_map_free(&hash_map, NULL); +} + +// Test resetting and clearing the hash map. +void test_reset_clear() { + intrusive_hash_map hash_map; + intrusive_hash_map_init(&hash_map, kInitialLog2Size); + + // Add some data to the hash_map. + for (uint64_t i = 0; i < 3; ++i) { + intrusive_hash_map_insert(&hash_map, (hm_item *)make_ptr_item(i, i)); + } + GPR_ASSERT(3 == intrusive_hash_map_size(&hash_map)); + + // Test find. + for (uint64_t i = 0; i < 3; ++i) { + ptr_item *item = (ptr_item *)intrusive_hash_map_find(&hash_map, i); + GPR_ASSERT(item != NULL); + GPR_ASSERT(item->IHM_key == i && item->obj->val == i); + } + + intrusive_hash_map_clear(&hash_map, &free_ptr_item); + GPR_ASSERT(intrusive_hash_map_empty(&hash_map)); + intrusive_hash_map_free(&hash_map, &free_ptr_item); +} + +// Check that the hash_map contains every key between [min_value, max_value] +// (inclusive). +void check_hash_map_values(intrusive_hash_map *hash_map, uint64_t min_value, + uint64_t max_value) { + GPR_ASSERT(intrusive_hash_map_size(hash_map) == max_value - min_value + 1); + + for (uint64_t i = min_value; i <= max_value; ++i) { + ptr_item *item = (ptr_item *)intrusive_hash_map_find(hash_map, i); + GPR_ASSERT(item != NULL); + GPR_ASSERT(item->obj->val == i); + } +} + +// Add many items and cause the hash_map to extend. +void test_extend() { + intrusive_hash_map hash_map; + intrusive_hash_map_init(&hash_map, kInitialLog2Size); + + const uint64_t kNumValues = (1 << 16); + + for (uint64_t i = 0; i < kNumValues; ++i) { + ptr_item *item = make_ptr_item(i, i); + bool ok = intrusive_hash_map_insert(&hash_map, (hm_item *)item); + GPR_ASSERT(ok); + if (i % 1000 == 0) { + check_hash_map_values(&hash_map, 0, i); + } + } + + for (uint64_t i = 0; i < kNumValues; ++i) { + ptr_item *item = (ptr_item *)intrusive_hash_map_find(&hash_map, i); + GPR_ASSERT(item != NULL); + GPR_ASSERT(item->IHM_key == i && item->obj->val == i); + ptr_item *item2 = (ptr_item *)intrusive_hash_map_erase(&hash_map, i); + GPR_ASSERT(item == item2); + gpr_free(item->obj); + gpr_free(item); + } + + GPR_ASSERT(intrusive_hash_map_empty(&hash_map)); + intrusive_hash_map_free(&hash_map, &free_ptr_item); +} + +void test_stress() { + intrusive_hash_map hash_map; + intrusive_hash_map_init(&hash_map, kInitialLog2Size); + size_t n = 0; + + // Randomly add and insert entries 1000000 times. + for (uint64_t i = 0; i < 1000000; ++i) { + int op = rand() & 0x1; + + switch (op) { + // Case 0 is insertion of entry. + case 0: { + uint64_t key = (uint64_t)(rand() % 10000); + ptr_item *item = make_ptr_item(key, key); + bool ok = intrusive_hash_map_insert(&hash_map, (hm_item *)item); + if (ok) { + n++; + } else { + gpr_free(item->obj); + gpr_free(item); + } + break; + } + // Case 1 is removal of entry. + case 1: { + uint64_t key = (uint64_t)(rand() % 10000); + ptr_item *item = (ptr_item *)intrusive_hash_map_find(&hash_map, key); + if (item != NULL) { + n--; + GPR_ASSERT(key == item->obj->val); + ptr_item *item2 = + (ptr_item *)intrusive_hash_map_erase(&hash_map, key); + GPR_ASSERT(item == item2); + gpr_free(item->obj); + gpr_free(item); + } + break; + } + } + } + // Check size + GPR_ASSERT(n == intrusive_hash_map_size(&hash_map)); + + // Clean the hash_map up. + intrusive_hash_map_clear(&hash_map, &free_ptr_item); + GPR_ASSERT(intrusive_hash_map_empty(&hash_map)); + intrusive_hash_map_free(&hash_map, &free_ptr_item); +} + +int main(int argc, char **argv) { + grpc_test_init(argc, argv); + gpr_time_init(); + srand((unsigned)gpr_now(GPR_CLOCK_REALTIME).tv_nsec); + + test_empty(); + test_single_item(); + test_two_items(); + test_reset_clear(); + test_extend(); + test_stress(); + + return 0; +} |