Signed-off-by: Siddharth Singh <siddhartth@xxxxxxxxxx> --- Since v1 - rewrote the code keeping coding style guidelines in mind. - refactored tests to improve their implementation.. - added a few more tests that cause collisions in the hashmap. In the v1 patch, there were concerns that new tests were unnecessary because of upstream tests. However, I believe it would be beneficial to have tests based on the khash implementation in the git codebase because the existing tests[1] for khash do not use the same code for khash as the git codebase. E.g. in khash.h file of “attractivechaos/klib/khash.h” [2]. There's an implementation for `KHASH_MAP_INIT_INT64` which isn’t defined in “git/git/khash.h”[3]. So, there’s a possibility that the khash.h in a different repository might move forward and end up being different from out implementation, so writing tests for “git/git/khash.h” would ensure that our tests are relevant to the actual usage of the library. While my colleagues are currently investigating whether C Tap harness is the best way to test libified code, this RFC is intended to discuss the content of unit tests and what other tests would be useful for khash.h. I am unsure of what tests will be valuable in the future, so I would appreciate your thoughts on the matter. Many test cases are easier to construct in C TAP harness than in test-tool. For example, In C TAP harness, non-string values can be used directly in hash maps. However, in test-tool, non-string values must be passed as an argument to a shell executable, parsed into the correct type, and then operated on. I'm also very new to writing unit tests in C and git codebase in general, so I'll appreciate constructive feedback and discussion.. With this RFC, I hope you can help me answer these questions. What are the unit test cases to include in khash.h? What are the other types of tests that would be useful for khash.h? [1] https://github.com/attractivechaos/klib/blob/master/test/khash_test.c [2] https://github.com/attractivechaos/klib/blob/master/khash.h [3] https://github.com/git/git/blob/master/khash.h Makefile | 2 + t/khash_test.c | 214 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 216 insertions(+) create mode 100644 t/khash_test.c diff --git a/Makefile b/Makefile index 660c72d72e..d3ad2fa23c 100644 --- a/Makefile +++ b/Makefile @@ -3847,11 +3847,13 @@ $(UNIT_TEST_RUNNER): t/runtests.c UNIT_TEST_PROGS += t/unit-tests/unit-test-t UNIT_TEST_PROGS += t/unit-tests/strbuf-t +UNIT_TEST_PROGS += t/unit-tests/khash-t $(UNIT_TEST_PROGS): $(CTAP_OBJS) $(LIBS) $(QUIET)mkdir -p t/unit-tests $(QUIET_CC)$(CC) -It -o t/unit-tests/unit-test-t t/unit-test.c $(CTAP_OBJS) $(QUIET_CC)$(CC) -It -o t/unit-tests/strbuf-t t/strbuf-test.c -DSKIP_COMMON_MAIN common-main.c $(CTAP_OBJS) $(LIBS) + $(QUIET_CC)$(CC) -It -o t/unit-tests/khash-t t/khash_test.c -DSKIP_COMMON_MAIN common-main.c $(CTAP_OBJS) $(LIBS) .PHONY: unit-tests unit-tests: $(UNIT_TEST_PROGS) $(UNIT_TEST_RUNNER) diff --git a/t/khash_test.c b/t/khash_test.c new file mode 100644 index 0000000000..d1a43add13 --- /dev/null +++ b/t/khash_test.c @@ -0,0 +1,214 @@ +#include "../git-compat-util.h" +#include "../khash.h" +#include <tap/basic.h> + +/* + These tests are for base assumptions; if they fails, library is broken +*/ +int hash_string_succeeds() { + const char *str = "test_string"; + khint_t value = __ac_X31_hash_string(str); + return value == 0xf1a6305e; +} + +int hash_string_with_non_alphabets_succeeds() { + const char *str = "test_string #2"; + khint_t value = __ac_X31_hash_string(str); + return value == 0xfa970771; +} + +KHASH_INIT(str, const char *, int *, 1, kh_str_hash_func, kh_str_hash_equal); + +int initialized_hashmap_pointer_not_null() { + kh_str_t *hashmap = kh_init_str(); + + if(hashmap != NULL){ + free(hashmap); + return 1; + } + return 0; +} + +int put_key_into_hashmap_once_succeeds() { + int ret, value; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + pos = kh_put_str(hashmap, "test_key", &ret); + if(!ret) + return 0; + return pos != 0; +} + +int put_same_key_into_hashmap_twice_fails() { + int first_return_value, second_return_value, value; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + kh_put_str(hashmap, "test_key", &first_return_value); + kh_put_str(hashmap, "test_key", &second_return_value); + return !second_return_value; +} + +int put_value_into_hashmap_once_succeeds() { + int ret, value = 14; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + pos = kh_put_str(hashmap, "test_key", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos) = xstrdup("test_key"); + kh_value(hashmap, pos) = &value; + return *kh_value(hashmap, pos) == value; +} + +int put_same_value_into_hashmap_twice_fails() { + int first_return_value, second_return_value, value = 14; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + pos = kh_put_str(hashmap, "test_key", &first_return_value); + if (!first_return_value) + return 0; + kh_key(hashmap, pos) = xstrdup("test_key"); + kh_value(hashmap, pos) = &value; + kh_put_str(hashmap, "test_key", &second_return_value); + return !second_return_value; +} + +int get_existing_kv_from_hashmap_succeeds() { + int ret, value =14; + int expected = value; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + pos = kh_put_str(hashmap, "test_key", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos) = xstrdup("test_key"); + kh_value(hashmap, pos) = &value; + return *kh_value(hashmap, kh_get_str(hashmap, "test_key")) == expected; +} + +int get_nonexisting_kv_from_hashmap_fails() { + int value = 14; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + return !kh_get_str(hashmap, "test_key"); +} + +int deletion_from_hashmap_sets_flag() { + int ret, value = 14; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + pos = kh_put_str(hashmap, "test_key", &ret); + if (!ret) + return 0; + if(!kh_exist(hashmap, pos)) + return 0; + kh_key(hashmap, pos) = xstrdup("test_key"); + kh_value(hashmap, pos) = &value; + kh_del_str(hashmap, pos); + return !kh_exist(hashmap, pos); +} + +int deletion_from_hashmap_updates_size() { + int ret, value = 14, current_size; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + pos = kh_put_str(hashmap, "test_key", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos) = xstrdup("test_key"); + kh_value(hashmap, pos) = &value; + current_size = hashmap->size; + kh_del_str(hashmap, pos); + return hashmap->size + 1 == current_size; +} + +int deletion_from_hashmap_does_not_update_kv() { + int ret, value = 14, current_size; + khint_t pos; + kh_str_t *hashmap = kh_init_str(); + pos = kh_put_str(hashmap, "test_key", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos) = xstrdup("test_key"); + kh_value(hashmap, pos) = &value; + kh_del_str(hashmap, pos); + return !strcmp(kh_key(hashmap, pos),"test_key"); +} + +int update_value_after_deletion_succeeds() { + int ret, value1 = 14, value2 = 15; + khint_t pos1, pos2; + kh_str_t *hashmap = kh_init_str(); + // adding the kv to the hashmap + pos1 = kh_put_str(hashmap, "test_key", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos1) = xstrdup("test_key"); + kh_value(hashmap, pos1) = &value1; + // delete the kv from the hashmap + kh_del_str(hashmap, pos1); + // adding the same key with different value + pos2 = kh_put_str(hashmap, "test_key", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos2) = xstrdup("test_key"); + kh_value(hashmap, pos2) = &value2; + // check if the value is different + return *kh_value(hashmap, kh_get_str(hashmap, "test_key")) == value2; +} + +int hashmap_size_matches_number_of_added_elements() { + int ret, value1 = 14, value2 = 15, value3 = 16; + khint_t pos1, pos2, pos3; + kh_str_t *hashmap = kh_init_str(); + pos1 = kh_put_str(hashmap, "test_key1", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos1) = xstrdup("test_key1"); + kh_value(hashmap, pos1) = &value1; + pos2 = kh_put_str(hashmap, "test_key2", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos2) = xstrdup("test_key2"); + kh_value(hashmap, pos2) = &value2; + pos3 = kh_put_str(hashmap, "test_key3", &ret); + if (!ret) + return 0; + kh_key(hashmap, pos3) = xstrdup("test_key3"); + kh_value(hashmap, pos3) = &value3; + return kh_size(hashmap) == 3; +} + +int main(void) { + plan(14); + + ok(hash_string_succeeds(), "X31 hash value of a string is correct"); + ok(hash_string_with_non_alphabets_succeeds(), + "Get X31 hash value for a string with non-alphabets in it."); + ok(initialized_hashmap_pointer_not_null(), + "Successfully initialize a hashmap and it's not NULL"); + ok(put_key_into_hashmap_once_succeeds(), + "Put a key into hashmap that doesn't exist."); + ok(put_same_key_into_hashmap_twice_fails(), + "Put a key into hashmap twice that causes collision."); + ok(put_value_into_hashmap_once_succeeds(), + "Put a unique key-value pair into hashmap."); + ok(put_same_value_into_hashmap_twice_fails(), + "Put a key-value pair into hashmap twice that causes collision."); + ok(get_existing_kv_from_hashmap_succeeds(), + "Get the value from a key that exists in hashmap"); + ok(get_nonexisting_kv_from_hashmap_fails(), + "Get the value from a key that doesn't exist in hashmap"); + ok(deletion_from_hashmap_sets_flag(), + "Delete the key-value from hashmap and the flag is set to false"); + ok(deletion_from_hashmap_updates_size(), + "Delete the key-value from hashmap and the size changes"); + ok(deletion_from_hashmap_does_not_update_kv(), + "Delete the key-value from hashmap but it can be fetched using iterator"); + ok(update_value_after_deletion_succeeds(), + "Updates the value of a key after deleting it"); + ok(hashmap_size_matches_number_of_added_elements(), + "size of hashmap is correct after adding 3 elements"); + + return 0; +} -- 2.40.GIT
