From 351ad5f4af15eff9157d1b8d071d18ab7ae82e3d Mon Sep 17 00:00:00 2001 From: Eric Anholt Date: Wed, 2 Mar 2016 00:10:40 -0800 Subject: Add a testcase for the replacement bug fixed in the previous commit. --- tests/.gitignore | 1 + tests/Makefile.am | 1 + tests/collision_replacement.c | 73 +++++++++++++++++++++++++++++++++++ tests/int-set/.gitignore | 1 + tests/int-set/Makefile.am | 1 + tests/int-set/collision_replacement.c | 53 +++++++++++++++++++++++++ tests/set/.gitignore | 1 + tests/set/Makefile.am | 1 + tests/set/collision_replacement.c | 65 +++++++++++++++++++++++++++++++ 9 files changed, 197 insertions(+) create mode 100644 tests/collision_replacement.c create mode 100644 tests/int-set/collision_replacement.c create mode 100644 tests/set/collision_replacement.c (limited to 'tests') diff --git a/tests/.gitignore b/tests/.gitignore index a3d6f5b..b9f82ee 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -1,6 +1,7 @@ *.log *.trs collision +collision_replacement delete_and_lookup delete_management deleted_key diff --git a/tests/Makefile.am b/tests/Makefile.am index d0b4e9f..5981981 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -26,6 +26,7 @@ LDADD = ../libhash_table.la TESTS = \ collision \ + collision_replacement \ delete_and_lookup \ delete_management \ deleted_key \ diff --git a/tests/collision_replacement.c b/tests/collision_replacement.c new file mode 100644 index 0000000..d20d835 --- /dev/null +++ b/tests/collision_replacement.c @@ -0,0 +1,73 @@ +/* + * Copyright © 2009 Intel Corporation + * Copyright © 2016 Broadcom Limited + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include +#include +#include +#include +#include "hash_table.h" +#include "fnv_hash.h" + +/* Return collisions, so we can test the deletion behavior for chained + * objects. + */ +static uint32_t +badhash(const void *key) +{ + return 1; +} + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + const char *str1 = "test1"; + const char *str2 = "test2"; + uint8_t data = 0; + struct hash_entry *entry; + + ht = hash_table_create(badhash, string_key_equals); + + hash_table_insert(ht, str1, NULL); + hash_table_insert(ht, str2, NULL); + hash_table_remove(ht, str1); + hash_table_insert(ht, str2, &data); + + /* Make sure that we actually replaced our str2's data, even + * though it was chained off of str1. + */ + entry = hash_table_search(ht, str2); + assert(entry->data == &data); + + /* Make sure that if we remove str2, it wasn't just occupying + * str1's old slot with the old str2 still present. + */ + hash_table_remove(ht, str2); + entry = hash_table_search(ht, str2); + assert(entry == NULL); + + hash_table_destroy(ht, NULL); + + return 0; +} diff --git a/tests/int-set/.gitignore b/tests/int-set/.gitignore index a330800..3375097 100644 --- a/tests/int-set/.gitignore +++ b/tests/int-set/.gitignore @@ -1,5 +1,6 @@ *.log *.trs +collision_replacement delete_and_lookup delete_management destroy_callback diff --git a/tests/int-set/Makefile.am b/tests/int-set/Makefile.am index 1b70801..8d8c2c6 100644 --- a/tests/int-set/Makefile.am +++ b/tests/int-set/Makefile.am @@ -23,6 +23,7 @@ AM_CFLAGS = $(WARN_CFLAGS) -I$(top_srcdir) LDADD = ../../libint-set.la TESTS = \ + collision_replacement \ delete_and_lookup \ delete_management \ insert_and_lookup \ diff --git a/tests/int-set/collision_replacement.c b/tests/int-set/collision_replacement.c new file mode 100644 index 0000000..419c718 --- /dev/null +++ b/tests/int-set/collision_replacement.c @@ -0,0 +1,53 @@ +/* + * Copyright © 2009 Intel Corporation + * Copyright © 2016 Broadcom Limited + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include +#include +#include +#include +#include "int-set.h" +#include "fnv_hash.h" + +int +main(int argc, char **argv) +{ + struct int_set *set = int_set_create(); + + /* Unlike the hash table equivalent of this test, use an extra + * number so that the rehash happens at the right time. + * Values are chosen to make sure that we chain on the third + * number against the second. + */ + int_set_add(set, 1); + int_set_add(set, 2); + int_set_add(set, 15); + int_set_remove(set, 2); + int_set_add(set, 15); + int_set_remove(set, 15); + assert(!int_set_contains(set, 15)); + + int_set_destroy(set); + + return 0; +} diff --git a/tests/set/.gitignore b/tests/set/.gitignore index ffe2af0..d51b7fa 100644 --- a/tests/set/.gitignore +++ b/tests/set/.gitignore @@ -1,5 +1,6 @@ *.log *.trs +collision_replacement delete_and_lookup delete_management deleted_key diff --git a/tests/set/Makefile.am b/tests/set/Makefile.am index b93a146..ebfd0aa 100644 --- a/tests/set/Makefile.am +++ b/tests/set/Makefile.am @@ -23,6 +23,7 @@ AM_CFLAGS = $(WARN_CFLAGS) -I$(srcdir)/../.. LDADD = ../../libset.la TESTS = \ + collision_replacement \ delete_and_lookup \ delete_management \ deleted_key \ diff --git a/tests/set/collision_replacement.c b/tests/set/collision_replacement.c new file mode 100644 index 0000000..bea65e4 --- /dev/null +++ b/tests/set/collision_replacement.c @@ -0,0 +1,65 @@ +/* + * Copyright © 2009 Intel Corporation + * Copyright © 2016 Broadcom Limited + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include +#include +#include +#include +#include "set.h" +#include "fnv_hash.h" + +/* Return collisions, so we can test the deletion behavior for chained + * objects. + */ +static uint32_t +badhash(const void *key) +{ + return 1; +} + +int +main(int argc, char **argv) +{ + struct set *set; + const char *str1 = "test1"; + const char *str2 = "test2"; + const char *str3 = "test3"; + + set = set_create(badhash, string_key_equals); + + /* Unlike the hash table equivalent of this test, use an extra + * string so that the rehash happens at the right time. + */ + set_add(set, str1); + set_add(set, str2); + set_add(set, str3); + set_remove(set, str2); + set_add(set, str3); + set_remove(set, str3); + assert(!set_contains(set, str3)); + + set_destroy(set, NULL); + + return 0; +} -- cgit v1.2.3