diff options
Diffstat (limited to '3rdparty/plibsys/tests/ptree_test.cpp')
| -rw-r--r-- | 3rdparty/plibsys/tests/ptree_test.cpp | 633 |
1 files changed, 633 insertions, 0 deletions
diff --git a/3rdparty/plibsys/tests/ptree_test.cpp b/3rdparty/plibsys/tests/ptree_test.cpp new file mode 100644 index 0000000..e038ebb --- /dev/null +++ b/3rdparty/plibsys/tests/ptree_test.cpp @@ -0,0 +1,633 @@ +/* + * The MIT License + * + * Copyright (C) 2015-2017 Alexander Saprykin <saprykin.spb@gmail.com> + * + * 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 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 "plibsys.h" +#include "ptestmacros.h" + +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <math.h> + +P_TEST_MODULE_INIT (); + +#define PTREE_STRESS_ITERATIONS 20 +#define PTREE_STRESS_NODES 10000 +#define PTREE_STRESS_ROOT_MIN 10000 +#define PTREE_STRESS_TRAVS 30 + +typedef struct _TreeData { + pint cmp_counter; + pint key_destroy_counter; + pint value_destroy_counter; + pint traverse_counter; + pint traverse_thres; + pint key_sum; + pint value_sum; + pint last_key; + pint key_order_errors; +} TreeData; + +static TreeData tree_data = {0, 0, 0, 0, 0, 0, 0, 0, 0}; + +extern "C" ppointer pmem_alloc (psize nbytes) +{ + P_UNUSED (nbytes); + return (ppointer) NULL; +} + +extern "C" ppointer pmem_realloc (ppointer block, psize nbytes) +{ + P_UNUSED (block); + P_UNUSED (nbytes); + return (ppointer) NULL; +} + +extern "C" void pmem_free (ppointer block) +{ + P_UNUSED (block); +} + +static pint +tree_complexity (PTree *tree) +{ + if (tree == NULL || p_tree_get_nnodes (tree) == 0) + return 0; + + switch (p_tree_get_type (tree)) { + case P_TREE_TYPE_BINARY: + return p_tree_get_nnodes (tree); + case P_TREE_TYPE_RB: + return 2 * ((pint) (log ((double) p_tree_get_nnodes (tree) + 1) / log (2.0))); + case P_TREE_TYPE_AVL: + { + double phi = (1 + sqrt (5.0)) / 2.0; + return (pint) (log (sqrt (5.0) * (p_tree_get_nnodes (tree) + 2)) / log (phi) - 2); + } + default: + return p_tree_get_nnodes (tree); + } +} + +static pint +compare_keys (pconstpointer a, pconstpointer b) +{ + int p1 = PPOINTER_TO_INT (a); + int p2 = PPOINTER_TO_INT (b); + + if (p1 < p2) + return -1; + else if (p1 > p2) + return 1; + else + return 0; +} + +static pint +compare_keys_data (pconstpointer a, pconstpointer b, ppointer data) +{ + int p1 = PPOINTER_TO_INT (a); + int p2 = PPOINTER_TO_INT (b); + + if (data != NULL) + ((TreeData *) data)->cmp_counter++; + + if (p1 < p2) + return -1; + else if (p1 > p2) + return 1; + else + return 0; +} + +static void +key_destroy_notify (ppointer data) +{ + tree_data.key_destroy_counter++; + tree_data.key_sum += PPOINTER_TO_INT (data); +} + +static void +value_destroy_notify (ppointer data) +{ + tree_data.value_destroy_counter++; + tree_data.value_sum += PPOINTER_TO_INT (data); +} + +static pboolean +tree_traverse (ppointer key, ppointer value, ppointer data) +{ + TreeData* tdata = ((TreeData *) data); + + tdata->key_sum += PPOINTER_TO_INT (key); + tdata->value_sum += PPOINTER_TO_INT (value); + tdata->traverse_counter++; + + if (tdata->last_key >= PPOINTER_TO_INT (key)) + tdata->key_order_errors++; + + tdata->last_key = PPOINTER_TO_INT (key); + + return FALSE; +} + +static pboolean +tree_traverse_thres (ppointer key, ppointer value, ppointer data) +{ + TreeData* tdata = ((TreeData *) data); + + tree_traverse (key, value, data); + + return tdata->traverse_counter >= tdata->traverse_thres ? TRUE : FALSE; +} + +static bool +check_tree_data_is_zero () +{ + return tree_data.cmp_counter == 0 && + tree_data.key_destroy_counter == 0 && + tree_data.value_destroy_counter == 0 && + tree_data.traverse_counter == 0 && + tree_data.traverse_thres == 0 && + tree_data.key_sum == 0 && + tree_data.value_sum == 0 && + tree_data.last_key == 0 && + tree_data.key_order_errors == 0; +} + +static bool +general_tree_test (PTree *tree, PTreeType type, bool check_cmp, bool check_notify) +{ + memset (&tree_data, 0, sizeof (tree_data)); + + P_TEST_REQUIRE (tree != NULL); + P_TEST_CHECK (p_tree_get_nnodes (tree) == 0); + P_TEST_CHECK (p_tree_get_type (tree) == type); + P_TEST_CHECK (p_tree_lookup (tree, NULL) == NULL); + P_TEST_CHECK (p_tree_remove (tree, NULL) == FALSE); + + p_tree_insert (tree, NULL, PINT_TO_POINTER (10)); + P_TEST_CHECK (p_tree_get_nnodes (tree) == 1); + P_TEST_CHECK (p_tree_lookup (tree, NULL) == PINT_TO_POINTER (10)); + P_TEST_CHECK (p_tree_lookup (tree, PINT_TO_POINTER (2)) == NULL); + P_TEST_CHECK (p_tree_remove (tree, NULL) == TRUE); + P_TEST_CHECK (p_tree_get_nnodes (tree) == 0); + + p_tree_foreach (tree, (PTraverseFunc) tree_traverse, &tree_data); + P_TEST_CHECK (tree_data.traverse_counter == 0); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + /* Because we have NULL-key node */ + P_TEST_CHECK (tree_data.key_sum == 0); + + if (check_notify) + P_TEST_CHECK (tree_data.value_sum == 10); + else + P_TEST_CHECK (tree_data.value_sum == 0); + + memset (&tree_data, 0, sizeof (tree_data)); + + p_tree_insert (tree, PINT_TO_POINTER (4), PINT_TO_POINTER (40)); + p_tree_insert (tree, PINT_TO_POINTER (1), PINT_TO_POINTER (10)); + p_tree_insert (tree, PINT_TO_POINTER (5), PINT_TO_POINTER (50)); + p_tree_insert (tree, PINT_TO_POINTER (2), PINT_TO_POINTER (20)); + p_tree_insert (tree, PINT_TO_POINTER (6), PINT_TO_POINTER (60)); + p_tree_insert (tree, PINT_TO_POINTER (3), PINT_TO_POINTER (30)); + + P_TEST_CHECK (p_tree_get_nnodes (tree) == 6); + + p_tree_insert (tree, PINT_TO_POINTER (1), PINT_TO_POINTER (100)); + p_tree_insert (tree, PINT_TO_POINTER (5), PINT_TO_POINTER (500)); + + P_TEST_CHECK (p_tree_get_nnodes (tree) == 6); + + p_tree_insert (tree, PINT_TO_POINTER (1), PINT_TO_POINTER (10)); + p_tree_insert (tree, PINT_TO_POINTER (5), PINT_TO_POINTER (50)); + + P_TEST_CHECK (p_tree_get_nnodes (tree) == 6); + + if (check_cmp) + P_TEST_CHECK (tree_data.cmp_counter > 0); + else + P_TEST_CHECK (tree_data.cmp_counter == 0); + + if (check_notify) { + P_TEST_CHECK (tree_data.key_sum == 12); + P_TEST_CHECK (tree_data.value_sum == 660); + } else { + P_TEST_CHECK (tree_data.key_sum == 0); + P_TEST_CHECK (tree_data.value_sum == 0); + } + + P_TEST_CHECK (tree_data.traverse_counter == 0); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + memset (&tree_data, 0, sizeof (tree_data)); + + p_tree_foreach (tree, (PTraverseFunc) tree_traverse, &tree_data); + P_TEST_CHECK (p_tree_get_nnodes (tree) == 6); + + P_TEST_CHECK (tree_data.cmp_counter == 0); + P_TEST_CHECK (tree_data.key_sum == 21); + P_TEST_CHECK (tree_data.value_sum == 210); + P_TEST_CHECK (tree_data.traverse_counter == 6); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + memset (&tree_data, 0, sizeof (tree_data)); + + for (int i = 0; i < 7; ++i) + P_TEST_CHECK (p_tree_lookup (tree, PINT_TO_POINTER (i)) == PINT_TO_POINTER (i * 10)); + + if (check_cmp) + P_TEST_CHECK (tree_data.cmp_counter > 0); + else + P_TEST_CHECK (tree_data.cmp_counter == 0); + + P_TEST_CHECK (tree_data.key_sum == 0); + P_TEST_CHECK (tree_data.value_sum == 0); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + tree_data.cmp_counter = 0; + + P_TEST_CHECK (p_tree_remove (tree, PINT_TO_POINTER (7)) == FALSE); + + if (check_cmp) + P_TEST_CHECK (tree_data.cmp_counter > 0 && + tree_data.cmp_counter <= tree_complexity (tree)); + else + P_TEST_CHECK (tree_data.cmp_counter == 0); + + if (check_notify) { + P_TEST_CHECK (tree_data.key_sum == 0); + P_TEST_CHECK (tree_data.value_sum == 0); + } + + tree_data.cmp_counter = 0; + + for (int i = 0; i < 7; ++i) + P_TEST_CHECK (p_tree_lookup (tree, PINT_TO_POINTER (i)) == PINT_TO_POINTER (i * 10)); + + if (check_cmp) + P_TEST_CHECK (tree_data.cmp_counter > 0); + else + P_TEST_CHECK (tree_data.cmp_counter == 0); + + P_TEST_CHECK (tree_data.key_sum == 0); + P_TEST_CHECK (tree_data.value_sum == 0); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + memset (&tree_data, 0, sizeof (tree_data)); + + tree_data.traverse_thres = 5; + + p_tree_foreach (tree, (PTraverseFunc) tree_traverse_thres, &tree_data); + P_TEST_CHECK (p_tree_get_nnodes (tree) == 6); + + P_TEST_CHECK (tree_data.cmp_counter == 0); + P_TEST_CHECK (tree_data.key_sum == 15); + P_TEST_CHECK (tree_data.value_sum == 150); + P_TEST_CHECK (tree_data.traverse_counter == 5); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + memset (&tree_data, 0, sizeof (tree_data)); + + tree_data.traverse_thres = 3; + + p_tree_foreach (tree, (PTraverseFunc) tree_traverse_thres, &tree_data); + P_TEST_CHECK (p_tree_get_nnodes (tree) == 6); + + P_TEST_CHECK (tree_data.cmp_counter == 0); + P_TEST_CHECK (tree_data.key_sum == 6); + P_TEST_CHECK (tree_data.value_sum == 60); + P_TEST_CHECK (tree_data.traverse_counter == 3); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + memset (&tree_data, 0, sizeof (tree_data)); + + P_TEST_CHECK (p_tree_remove (tree, PINT_TO_POINTER (1)) == TRUE); + P_TEST_CHECK (p_tree_remove (tree, PINT_TO_POINTER (6)) == TRUE); + P_TEST_CHECK (p_tree_lookup (tree, PINT_TO_POINTER (1)) == NULL); + P_TEST_CHECK (p_tree_lookup (tree, PINT_TO_POINTER (6)) == NULL); + + if (check_cmp) + P_TEST_CHECK (tree_data.cmp_counter > 0); + else + P_TEST_CHECK (tree_data.cmp_counter == 0); + + if (check_notify) { + P_TEST_CHECK (tree_data.key_sum == 7); + P_TEST_CHECK (tree_data.value_sum == 70); + } else { + P_TEST_CHECK (tree_data.key_sum == 0); + P_TEST_CHECK (tree_data.value_sum == 0); + } + + tree_data.cmp_counter = 0; + + for (int i = 2; i < 6; ++i) + P_TEST_CHECK (p_tree_lookup (tree, PINT_TO_POINTER (i)) == PINT_TO_POINTER (i * 10)); + + if (check_cmp) + P_TEST_CHECK (tree_data.cmp_counter > 0); + else + P_TEST_CHECK (tree_data.cmp_counter == 0); + + if (check_notify) { + P_TEST_CHECK (tree_data.key_sum == 7); + P_TEST_CHECK (tree_data.value_sum == 70); + } else { + P_TEST_CHECK (tree_data.key_sum == 0); + P_TEST_CHECK (tree_data.value_sum == 0); + } + + P_TEST_CHECK (tree_data.key_order_errors == 0); + + tree_data.cmp_counter = 0; + + p_tree_foreach (tree, NULL, NULL); + + P_TEST_CHECK (tree_data.cmp_counter == 0); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + p_tree_clear (tree); + + P_TEST_CHECK (tree_data.cmp_counter == 0); + P_TEST_CHECK (tree_data.key_order_errors == 0); + + if (check_notify) { + P_TEST_CHECK (tree_data.key_sum == 21); + P_TEST_CHECK (tree_data.value_sum == 210); + } else { + P_TEST_CHECK (tree_data.key_sum == 0); + P_TEST_CHECK (tree_data.value_sum == 0); + } + + P_TEST_CHECK (p_tree_get_nnodes (tree) == 0); + + return true; +} + +static bool +stress_tree_test (PTree *tree, int node_count) +{ + P_TEST_REQUIRE (tree != NULL); + P_TEST_REQUIRE (node_count > 0); + P_TEST_CHECK (p_tree_get_nnodes (tree) == 0); + + srand ((unsigned int) time (NULL)); + + int counter = 0; + + memset (&tree_data, 0, sizeof (tree_data)); + + pint *keys = (pint *) p_malloc0 ((psize) node_count * sizeof (pint)); + pint *values = (pint *) p_malloc0 ((psize) node_count * sizeof (pint)); + + P_TEST_REQUIRE (keys != NULL); + P_TEST_REQUIRE (values != NULL); + + while (counter != node_count) { + pint rand_number = rand (); + + if (counter == 0 && rand_number < PTREE_STRESS_ROOT_MIN) + continue; + + memset (&tree_data, 0, sizeof (tree_data)); + + if (p_tree_lookup (tree, PINT_TO_POINTER (rand_number)) != NULL) + continue; + + if (counter > 0) + P_TEST_CHECK (tree_data.cmp_counter > 0 && + tree_data.cmp_counter <= tree_complexity (tree)); + + memset (&tree_data, 0, sizeof (tree_data)); + + keys[counter] = rand_number; + values[counter] = rand () + 1; + + p_tree_insert (tree, PINT_TO_POINTER (keys[counter]), PINT_TO_POINTER (values[counter])); + + if (counter > 0) + P_TEST_CHECK (tree_data.cmp_counter > 0 && + tree_data.cmp_counter <= tree_complexity (tree)); + + ++counter; + } + + for (int i = 0; i < PTREE_STRESS_TRAVS; ++i) { + memset (&tree_data, 0, sizeof (tree_data)); + + tree_data.traverse_thres = i + 1; + tree_data.last_key = -1; + + p_tree_foreach (tree, (PTraverseFunc) tree_traverse_thres, &tree_data); + + P_TEST_CHECK (tree_data.traverse_counter == i + 1); + P_TEST_CHECK (tree_data.key_order_errors == 0); + } + + for (int i = 0; i < node_count; ++i) { + memset (&tree_data, 0, sizeof (tree_data)); + + P_TEST_CHECK (p_tree_lookup (tree, PINT_TO_POINTER (keys[i])) == + PINT_TO_POINTER (values[i])); + + P_TEST_CHECK (tree_data.cmp_counter > 0 && + tree_data.cmp_counter <= tree_complexity (tree)); + + P_TEST_CHECK (p_tree_remove (tree, PINT_TO_POINTER (keys[i])) == TRUE); + P_TEST_CHECK (p_tree_lookup (tree, PINT_TO_POINTER (keys[i])) == NULL); + } + + P_TEST_CHECK (p_tree_get_nnodes (tree) == 0); + + for (int i = 0; i < node_count; ++i) + p_tree_insert (tree, PINT_TO_POINTER (keys[i]), PINT_TO_POINTER (values[i])); + + P_TEST_CHECK (p_tree_get_nnodes (tree) == node_count); + + p_tree_clear (tree); + + P_TEST_CHECK (p_tree_get_nnodes (tree) == 0); + + p_free (keys); + p_free (values); + + return true; +} + +P_TEST_CASE_BEGIN (ptree_nomem_test) +{ + p_libsys_init (); + + PMemVTable vtable; + + for (int i = (int) P_TREE_TYPE_BINARY; i <= (int) P_TREE_TYPE_AVL; ++i) { + PTree *tree = p_tree_new ((PTreeType) i, (PCompareFunc) compare_keys); + P_TEST_CHECK (tree != NULL); + + vtable.free = pmem_free; + vtable.malloc = pmem_alloc; + vtable.realloc = pmem_realloc; + + P_TEST_CHECK (p_mem_set_vtable (&vtable) == TRUE); + + P_TEST_CHECK (p_tree_new ((PTreeType) i, (PCompareFunc) compare_keys) == NULL); + p_tree_insert (tree, PINT_TO_POINTER (1), PINT_TO_POINTER (10)); + P_TEST_CHECK (p_tree_get_nnodes (tree) == 0); + + p_mem_restore_vtable (); + + p_tree_free (tree); + } + + p_libsys_shutdown (); +} +P_TEST_CASE_END () + +P_TEST_CASE_BEGIN (ptree_invalid_test) +{ + p_libsys_init (); + + for (int i = (int) P_TREE_TYPE_BINARY; i <= (int) P_TREE_TYPE_AVL; ++i) { + /* Invalid usage */ + P_TEST_CHECK (p_tree_new ((PTreeType) i, NULL) == NULL); + P_TEST_CHECK (p_tree_new ((PTreeType) -1, (PCompareFunc) compare_keys) == NULL); + P_TEST_CHECK (p_tree_new ((PTreeType) -1, NULL) == NULL); + + P_TEST_CHECK (p_tree_new_with_data ((PTreeType) i, NULL, NULL) == NULL); + P_TEST_CHECK (p_tree_new_with_data ((PTreeType) -1, (PCompareDataFunc) compare_keys, NULL) == NULL); + P_TEST_CHECK (p_tree_new_with_data ((PTreeType) -1, NULL, NULL) == NULL); + + P_TEST_CHECK (p_tree_new_full ((PTreeType) i, + NULL, + NULL, + NULL, + NULL) == NULL); + P_TEST_CHECK (p_tree_new_full ((PTreeType) -1, + (PCompareDataFunc) compare_keys, + NULL, + NULL, + NULL) == NULL); + P_TEST_CHECK (p_tree_new_full ((PTreeType) -1, + NULL, + NULL, + NULL, + NULL) == NULL); + + P_TEST_CHECK (p_tree_remove (NULL, NULL) == FALSE); + P_TEST_CHECK (p_tree_lookup (NULL, NULL) == NULL); + P_TEST_CHECK (p_tree_get_type (NULL) == (PTreeType) -1); + P_TEST_CHECK (p_tree_get_nnodes (NULL) == 0); + + p_tree_insert (NULL, NULL, NULL); + p_tree_foreach (NULL, NULL, NULL); + p_tree_clear (NULL); + p_tree_free (NULL); + } + + p_libsys_shutdown (); +} +P_TEST_CASE_END () + +P_TEST_CASE_BEGIN (ptree_general_test) +{ + PTree *tree; + + p_libsys_init (); + + for (int i = (int) P_TREE_TYPE_BINARY; i <= (int) P_TREE_TYPE_AVL; ++i) { + /* Test 1 */ + tree = p_tree_new ((PTreeType) i, (PCompareFunc) compare_keys); + + P_TEST_CHECK (general_tree_test (tree, (PTreeType) i, false, false) == true); + + memset (&tree_data, 0, sizeof (tree_data)); + p_tree_free (tree); + + P_TEST_CHECK (check_tree_data_is_zero () == true); + + /* Test 2 */ + tree = p_tree_new_with_data ((PTreeType) i, + (PCompareDataFunc) compare_keys_data, + &tree_data); + + P_TEST_CHECK (general_tree_test (tree, (PTreeType) i, true, false) == true); + + memset (&tree_data, 0, sizeof (tree_data)); + p_tree_free (tree); + + P_TEST_CHECK (check_tree_data_is_zero () == true); + + /* Test 3 */ + tree = p_tree_new_full ((PTreeType) i, + (PCompareDataFunc) compare_keys_data, + &tree_data, + (PDestroyFunc) key_destroy_notify, + (PDestroyFunc) value_destroy_notify); + P_TEST_CHECK (general_tree_test (tree, (PTreeType) i, true, true) == true); + + memset (&tree_data, 0, sizeof (tree_data)); + p_tree_free (tree); + + P_TEST_CHECK (check_tree_data_is_zero () == true); + } + + p_libsys_shutdown (); +} +P_TEST_CASE_END () + +P_TEST_CASE_BEGIN (ptree_stress_test) +{ + PTree *tree; + + p_libsys_init (); + + for (int i = (int) P_TREE_TYPE_BINARY; i <= (int) P_TREE_TYPE_AVL; ++i) { + tree = p_tree_new_full ((PTreeType) i, + (PCompareDataFunc) compare_keys_data, + &tree_data, + (PDestroyFunc) key_destroy_notify, + (PDestroyFunc) value_destroy_notify); + + for (int j = 0; j < PTREE_STRESS_ITERATIONS; ++j) + P_TEST_CHECK (stress_tree_test (tree, PTREE_STRESS_NODES) == true); + + p_tree_free (tree); + } + + p_libsys_shutdown (); +} +P_TEST_CASE_END () + +P_TEST_SUITE_BEGIN() +{ + P_TEST_SUITE_RUN_CASE (ptree_nomem_test); + P_TEST_SUITE_RUN_CASE (ptree_invalid_test); + P_TEST_SUITE_RUN_CASE (ptree_general_test); + P_TEST_SUITE_RUN_CASE (ptree_stress_test); +} +P_TEST_SUITE_END() |