From ec688b4723a041044226358bcd4dd6e2da39da49 Mon Sep 17 00:00:00 2001 From: Luca Muscariello Date: Thu, 23 Feb 2017 17:01:02 +0100 Subject: Initial commit: cframework. Longbow and Libparc Change-Id: I90378dbd30da6033b20fb1f829b3b822cf366c59 Signed-off-by: Luca Muscariello --- libparc/parc/algol/test/test_parc_TreeRedBlack.c | 1462 ++++++++++++++++++++++ 1 file changed, 1462 insertions(+) create mode 100755 libparc/parc/algol/test/test_parc_TreeRedBlack.c (limited to 'libparc/parc/algol/test/test_parc_TreeRedBlack.c') diff --git a/libparc/parc/algol/test/test_parc_TreeRedBlack.c b/libparc/parc/algol/test/test_parc_TreeRedBlack.c new file mode 100755 index 00000000..cf2f19ca --- /dev/null +++ b/libparc/parc/algol/test/test_parc_TreeRedBlack.c @@ -0,0 +1,1462 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * 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 +#include +#include +#include +#include + +#include +#include + +#include "../parc_TreeRedBlack.c" + + +void * +keyNewInt(int key) +{ + int *newKey = parcMemory_Allocate(sizeof(int)); + assertNotNull(newKey, "parcMemory_Allocate(%zu) returned NULL", sizeof(int)); + *newKey = key; + return newKey; +} + +void * +valueNewInt(int value) +{ + int *newValue = parcMemory_Allocate(sizeof(int)); + assertNotNull(newValue, "parcMemory_Allocate(%zu) returned NULL", sizeof(int)); + *newValue = value; + return newValue; +} + +void * +keyCopy(const void *key) +{ + return keyNewInt(*(int *) key); +} + +void * +valueCopy(const void *value) +{ + return valueNewInt(*(int *) value); +} + +void * +keyNew(char *key) +{ + return parcMemory_StringDuplicate(key, strlen(key)); +} + +void * +valueNew(char *value) +{ + return parcMemory_StringDuplicate(value, strlen(value)); +} + +int +intComp(const void *key1, const void *key2) +{ + if (*(int *) key1 < *(int *) key2) { + return -1; + } + if (*(int *) key1 == *(int *) key2) { + return 0; + } + return 1; +} + +bool +intEquals(const void *int1, const void *int2) +{ + return intComp(int1, int2) == 0; +} + +int +pointerComp(const void *key1, const void *key2) +{ + if (key1 < key2) { + return -1; + } + if (key1 == key2) { + return 0; + } + return 1; +} + +int +stringComp(const void *key1, const void *key2) +{ + // We assume all keys are strings. + return strcmp(key1, key2); +} + +void +keyFree(void **value) +{ + parcMemory_Deallocate((void **) value); + *value = NULL; +} + +void +valueFree(void **key) +{ + parcMemory_Deallocate((void **) key); + *key = NULL; +} + + +LONGBOW_TEST_RUNNER(PARC_TreeRedBlack) +{ + LONGBOW_RUN_TEST_FIXTURE(Global); + LONGBOW_RUN_TEST_FIXTURE(Local); + LONGBOW_RUN_TEST_FIXTURE(Stress); +} + +LONGBOW_TEST_RUNNER_SETUP(PARC_TreeRedBlack) +{ + int seed = (int) time(NULL); + printf("Seed = %u\n", seed); + srandom(seed); + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_RUNNER_TEARDOWN(PARC_TreeRedBlack) +{ + uint32_t outstandingAllocations = parcSafeMemory_ReportAllocation(STDERR_FILENO); + if (outstandingAllocations != 0) { + printf("%s leaks memory by %d allocations\n", longBowTestRunner_GetName(testRunner), outstandingAllocations); + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE(Global) +{ + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_Ordered); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Create); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Destroy); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Ordered); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Insert_OutOfOrder); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Overwrite); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_DestroyTillEmpty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Size_Empty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Size); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Size_Overwrite); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_EmptyTree); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_NonExistent); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_First); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_Last); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_Biggest); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_Smallest); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_FirstKey); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_LastKey); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_FirstKey_Empty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Get_LastKey_Empty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_First); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_Last); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_NonExistent); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_First); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_Last); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_NonExistent); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_WithSuccessorNonRoot); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Remove_LeftChildRightChild); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Keys); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Values); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Empty); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Func); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_DifferentLength); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Values); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Values_Func); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Keys); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Copy); + LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_Copy_Direct); + //LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_ExerciseRandom); + //LONGBOW_RUN_TEST_CASE(Global, PARC_TreeRedBlack_ExerciseRootFailure); +} + +LONGBOW_TEST_FIXTURE_SETUP(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Global) +{ + /* + * uint32_t outstandingAllocations = parcSafeMemory_ReportAllocation(STDERR_FILENO); + * if (outstandingAllocations != 0) { + * printf("%s leaks memory by %d allocations\n", longBowTestCase_GetName(testCase), outstandingAllocations); + * return LONGBOW_STATUS_MEMORYLEAK; + * } + */ + return LONGBOW_STATUS_SUCCEEDED; +} + +static +int +strComp(const void *s1, const void *s2) +{ + return strcmp((char *) s1, (char *) s2); +} + +static +bool +strEquals(const void *s1, const void *s2) +{ + return strcmp(s1, s2) == 0; +} + +static +int +recursiveCheckBlackDepth(const PARCTreeRedBlack *tree, const Node *node) +{ + assertNotNull(tree, "Null tree?\n"); + assertNotNull(node, "Null node?\n"); + if (node == tree->nil) { + return 0; + } + int right_depth = recursiveCheckBlackDepth(tree, node->right_child); + int left_depth = recursiveCheckBlackDepth(tree, node->left_child); + assertTrue(right_depth == left_depth, "Wrong depth!!\n"); + if (_rbNodeColor(node) == BLACK) { + return right_depth + 1; + } + return right_depth; +} + +static +void +rbCheckTree(const PARCTreeRedBlack *tree) +{ + assertNotNull(tree, "Tree can't be NULL"); + //printf("--- TREE ---\n"); + _rbNodeAssertTreeInvariants(tree); + if (tree->size > 0) { + //_rbNodeRecursiveRun((PARCTreeRedBlack *)tree,tree->root,rbCheckNode,(void *)tree); + recursiveCheckBlackDepth(tree, tree->root); + } +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_Ordered) +{ + char *insertList[16] = { + "01", + "02", + "03", + "04", + "05", + "06", + "07", + "08", + "09", + "10", + "11", + "12", + "13", + "14", + "15", + "16" + }; + + PARCTreeRedBlack *tree1; + + tree1 = parcTreeRedBlack_Create(strComp, NULL, NULL, strEquals, NULL, NULL); + + for (int i = 0; i < 16; i++) { + parcTreeRedBlack_Insert(tree1, insertList[i], insertList[i]); + } + + for (int i = 0; i < 14; i++) { + //rbPrintTreeString(tree1); + void *data = parcTreeRedBlack_Remove(tree1, insertList[i]); + assertNotNull(data, "Data is null!"); + } + + parcTreeRedBlack_Destroy(&tree1); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Create) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(stringComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Destroy(&tree); + + tree = parcTreeRedBlack_Create(stringComp, keyFree, NULL, NULL, valueFree, NULL); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Destroy) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(stringComp, keyFree, NULL, NULL, valueFree, NULL); + + void *value1 = valueNew("value 1"); + void *key1 = keyNew("1"); + void *value2 = valueNew("value 2"); + void *key2 = keyNew("2"); + void *value3 = valueNew("value 3"); + void *key3 = keyNew("3"); + + parcTreeRedBlack_Insert(tree, key1, value1); + parcTreeRedBlack_Insert(tree, key2, value2); + parcTreeRedBlack_Insert(tree, key3, value3); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Overwrite) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(stringComp, keyFree, NULL, NULL, valueFree, NULL); + + parcTreeRedBlack_Insert(tree, keyNew("1"), valueNew("v1")); + parcTreeRedBlack_Insert(tree, keyNew("2"), valueNew("v2")); + parcTreeRedBlack_Insert(tree, keyNew("3"), valueNew("v3")); + parcTreeRedBlack_Insert(tree, keyNew("3"), valueNew("v4")); + parcTreeRedBlack_Insert(tree, keyNew("3"), valueNew("v5")); + + assertTrue(3 == parcTreeRedBlack_Size(tree), "Wrong size of tree should stay at 3"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Insert_Ordered) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 1, (void *) 1001); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Insert_OutOfOrder) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 4, (void *) 1004); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + parcTreeRedBlack_Insert(tree, (void *) 1, (void *) 1001); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Size_Empty) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + assertTrue(0 == parcTreeRedBlack_Size(tree), "Wrong size of tree - empty, start"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Size) +{ + PARCTreeRedBlack *tree; + size_t size; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 4, (void *) 1004); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + + assertTrue(3 == parcTreeRedBlack_Size(tree), "Wrong size of tree after add 3"); + + parcTreeRedBlack_Insert(tree, (void *) 1, (void *) 1001); + + assertTrue(4 == parcTreeRedBlack_Size(tree), "Wrong size of tree after add 1 more"); + + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 2); + + size = parcTreeRedBlack_Size(tree); + + assertTrue(3 == size, "Wrong size of tree after 1 delete (%zu instead of 3)", size); + + parcTreeRedBlack_Insert(tree, (void *) 7, (void *) 1007); + + assertTrue(4 == parcTreeRedBlack_Size(tree), "Wrong size of tree after add 1 more"); + + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 3); + assertTrue(3 == parcTreeRedBlack_Size(tree), "Wrong size of tree after del 1 more - 3"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_DestroyTillEmpty) +{ + PARCTreeRedBlack *tree; + size_t size; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 4, (void *) 1004); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + parcTreeRedBlack_Insert(tree, (void *) 1, (void *) 1001); + parcTreeRedBlack_Insert(tree, (void *) 5, (void *) 1001); + parcTreeRedBlack_Insert(tree, (void *) 7, (void *) 1001); + parcTreeRedBlack_Insert(tree, (void *) 6, (void *) 1001); + + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 3); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 1); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 4); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 2); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 6); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 5); + parcTreeRedBlack_RemoveAndDestroy(tree, (void *) 7); + + size = parcTreeRedBlack_Size(tree); + + assertTrue(0 == size, "Wrong size of tree - empty (got %zu)", size); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Size_Overwrite) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + parcTreeRedBlack_Insert(tree, (void *) 4, (void *) 1004); + parcTreeRedBlack_Insert(tree, (void *) 2, (void *) 1002); + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1003); + + // Size is 3 here, we'll insert the same number now.. + + parcTreeRedBlack_Insert(tree, (void *) 3, (void *) 1033); + + assertTrue(3 == parcTreeRedBlack_Size(tree), "Wrong size of tree after overwrite"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_EmptyTree) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + void *value = parcTreeRedBlack_Get(tree, (void *) 1); + + assertTrue(NULL == value, "Object did not exist, must return NULL"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_NonExistent) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *value = parcTreeRedBlack_Get(tree, (void *) 100); + + assertTrue(NULL == value, "Object did not exist, must return NULL"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_First) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < 4; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *value = parcTreeRedBlack_Get(tree, (void *) 1); + + assertTrue((1 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *value = parcTreeRedBlack_Get(tree, (void *) 4); + + assertTrue((4 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_Last) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *value = parcTreeRedBlack_Get(tree, (void *) 9); + + assertTrue((9 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_Smallest) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + + void *value = parcTreeRedBlack_Get(tree, (void *) 1); + + assertTrue((1 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_Biggest) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + + void *value = parcTreeRedBlack_Get(tree, (void *) 39); + + assertTrue((39 << 8) == (long) value, "Wrong value, got %ld", (long) value); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_FirstKey) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *key = parcTreeRedBlack_FirstKey(tree); + + assertTrue(1 == (long) key, "Wrong value, got %ld", (long) key); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_FirstKey_Empty) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + void *key = parcTreeRedBlack_FirstKey(tree); + + assertNull(key, "Should get NULL on empty tree"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_LastKey_Empty) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + void *key = parcTreeRedBlack_LastKey(tree); + + assertNull(key, "Should get NULL on empty tree"); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Get_LastKey) +{ + PARCTreeRedBlack *tree; + + tree = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree, (void *) i, (void *) (i << 8)); + } + + void *key = parcTreeRedBlack_LastKey(tree); + + assertTrue(39 == (long) key, "Wrong value, got %ld", (long) key); + + parcTreeRedBlack_Destroy(&tree); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_First) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + tree2 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + + for (int i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + parcTreeRedBlack_Insert(tree1, keyNewInt(1), valueNewInt(1 << 8)); + + for (int i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + for (int i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + int searchKey = 1; + + void *data = parcTreeRedBlack_Remove(tree1, &searchKey); + + valueFree(&data); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + tree2 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + + for (int i = 31; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + parcTreeRedBlack_Insert(tree1, keyNewInt(30), valueNewInt(31 << 8)); + + for (int i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + for (int i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + int searchKey = 30; + + void *data = parcTreeRedBlack_Remove(tree1, &searchKey); + + valueFree(&data); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_Last) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + tree2 = parcTreeRedBlack_Create(intComp, keyFree, NULL, intEquals, valueFree, NULL); + + for (int i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + parcTreeRedBlack_Insert(tree1, keyNewInt(100), valueNewInt(100 << 8)); + for (int i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + for (int i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, keyNewInt(i), valueNewInt(i << 8)); + parcTreeRedBlack_Insert(tree2, keyNewInt(i), valueNewInt(i << 8)); + } + + int searchKey = 100; + + void *data = parcTreeRedBlack_Remove(tree1, &searchKey); + + valueFree(&data); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_First) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_Insert(tree1, (void *) 1, (void *) (1 << 8)); + + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 1); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 31; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_Insert(tree1, (void *) 30, (void *) (30 << 8)); + + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 30); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_NonExistent) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + void *element = parcTreeRedBlack_Remove(tree1, (void *) 100); + + assertNull(element, "Return value must be NULL on non existing element"); + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_NonExistent) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 100); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_WithSuccessorNonRoot) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + long insert1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }; + long insert2[13] = { 8, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + + + for (int i = 0; i < 15; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) insert1[i], (void *) (insert1[i] << 8)); + } + + for (int i = 0; i < 13; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree2, (void *) insert2[i], (void *) (insert2[i] << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 4); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 12); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Remove_LeftChildRightChild) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + long insert1[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }; + long insert2[15] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 }; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + + + for (int i = 0; i < 15; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) insert1[i], (void *) (insert1[i] << 8)); + } + + for (int i = 0; i < 15; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree2, (void *) insert2[i], (void *) (insert2[i] << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 13); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 7); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 14); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 6); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 15); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 12); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 11); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 10); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 9); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 8); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 5); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 4); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 3); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 2); + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 1); + + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 1); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 2); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 3); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 4); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 5); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 6); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 7); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 8); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 9); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 10); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 11); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 12); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 13); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 14); + parcTreeRedBlack_RemoveAndDestroy(tree2, (void *) 15); + + //assertTrue(parcTreeRedBlack_Equals(tree1,tree2),"Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_RemoveAndDestroy_Last) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 30; i < 40; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + parcTreeRedBlack_Insert(tree1, (void *) 100, (void *) (100 << 8)); + for (long i = 2; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + for (long i = 20; i < 30; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, (void *) i, (void *) (i << 8)); + } + + parcTreeRedBlack_RemoveAndDestroy(tree1, (void *) 100); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Trees dont match after remove"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Keys) +{ + PARCTreeRedBlack *tree1; + PARCArrayList *list; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + list = parcArrayList_Create(NULL); + + // Insert in tree out of order + for (long i = 10; i < 20; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + } + + // Insert in list in order + for (long i = 1; i < 20; i++) { + // Add some elements to the tree + parcArrayList_Add(list, (void *) i); + } + + PARCArrayList *keys = parcTreeRedBlack_Keys(tree1); + + assertTrue(parcArrayList_Equals(list, keys), "Key list doesnt' match"); + + parcArrayList_Destroy(&keys); + parcArrayList_Destroy(&list); + parcTreeRedBlack_Destroy(&tree1); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Values) +{ + PARCTreeRedBlack *tree1; + PARCArrayList *list; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + list = parcArrayList_Create(NULL); + + // Insert in tree out of order + for (long i = 10; i < 20; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + } + for (long i = 1; i < 10; i++) { + // Add some elements to the tree + parcTreeRedBlack_Insert(tree1, (void *) i, (void *) (i << 8)); + } + + // Insert in list in order + for (long i = 1; i < 20; i++) { + // Add some elements to the tree + parcArrayList_Add(list, (void *) (i << 8)); + } + + PARCArrayList *values = parcTreeRedBlack_Values(tree1); + + assertTrue(parcArrayList_Equals(list, values), "Key list doesnt' match"); + + parcArrayList_Destroy(&values); + parcArrayList_Destroy(&list); + parcTreeRedBlack_Destroy(&tree1); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Empty) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Empty lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_DifferentLength) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, + (void *) (compareInserts - i), + (void *) ((compareInserts - i) << 8)); + } + parcTreeRedBlack_Insert(tree2, (void *) (1000), (void *) ((12304) << 8)); + + assertFalse(parcTreeRedBlack_Equals(tree1, tree2), "Lists are equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Values) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, + (void *) (compareInserts - i), + (void *) ((compareInserts + i) << 8)); + } + + assertFalse(parcTreeRedBlack_Equals(tree1, tree2), "Lists are equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Values_Func) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + tree2 = parcTreeRedBlack_Create(pointerComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + + for (int i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + keyNewInt(i), + valueNewInt(i + 1000)); + parcTreeRedBlack_Insert(tree2, + keyNewInt(i), + valueNewInt(i + 2000)); + } + + assertFalse(parcTreeRedBlack_Equals(tree1, tree2), "Lists are equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Not_Keys) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, + (void *) (compareInserts + i), + (void *) ((compareInserts - i) << 8)); + } + + assertFalse(parcTreeRedBlack_Equals(tree1, tree2), "Lists are equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + tree2 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + parcTreeRedBlack_Insert(tree2, + (void *) (compareInserts - i), + (void *) ((compareInserts - i) << 8)); + } + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Equals_Func) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 100; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + tree2 = parcTreeRedBlack_Create(intComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + + for (int i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + keyNewInt(i), + valueNewInt(i + 1000)); + parcTreeRedBlack_Insert(tree2, + keyNewInt(i), + valueNewInt(i + 1000)); + } + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Copy) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 20; + + tree1 = parcTreeRedBlack_Create(intComp, keyFree, keyCopy, intEquals, valueFree, valueCopy); + + for (int i = 1; i < compareInserts; i++) { + void *key = keyNewInt(i); + void *value = valueNewInt(i + 1000); + //value = (void *) &((*(int*)value) + 100); + parcTreeRedBlack_Insert(tree1, key, value); + } + + tree2 = parcTreeRedBlack_Copy(tree1); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_CASE(Global, PARC_TreeRedBlack_Copy_Direct) +{ + PARCTreeRedBlack *tree1; + PARCTreeRedBlack *tree2; + + int compareInserts = 20; + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + for (long i = 1; i < compareInserts; i++) { + parcTreeRedBlack_Insert(tree1, + (void *) i, + (void *) (i << 8)); + } + + tree2 = parcTreeRedBlack_Copy(tree1); + + assertTrue(parcTreeRedBlack_Equals(tree1, tree2), "Lists are not equal"); + + parcTreeRedBlack_Destroy(&tree1); + parcTreeRedBlack_Destroy(&tree2); +} + +LONGBOW_TEST_FIXTURE(Local) +{ + //LONGBOW_RUN_TEST_CASE(Local, PARC_TreeRedBlack_EnsureRemaining_NonEmpty); +} + +LONGBOW_TEST_FIXTURE_SETUP(Local) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Local) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE(Stress) +{ + // LongBow could use a command line option to enable/disable tests + // See LongBow issue #5 + if (getenv("LongBowStress")) { + LONGBOW_RUN_TEST_CASE(Stress, PARC_TreeRedBlack_ExerciseRandomSeededSmall); + LONGBOW_RUN_TEST_CASE(Stress, PARC_TreeRedBlack_ExerciseRandomSeeded); + } +} + +LONGBOW_TEST_FIXTURE_SETUP(Stress) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Stress) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_CASE(Stress, PARC_TreeRedBlack_ExerciseRandomSeededSmall) +{ + PARCTreeRedBlack *tree1; + unsigned seed; + char *seedString; + + seedString = getenv("RBSeed"); + if (seedString) { + seed = (unsigned) atol(seedString); + } else { + seed = 4179329122; // known to fail + } + + for (int j = 0; j < 1; j++) { + // this test case should obtain a seed and number of iterations from a + // command line option once LongBow has that feature available + + printf("Random seed %u\n", seed); + + srandom(seed); + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + int inserts = 0; + int deletes = 0; + + for (int i = 0; i < 100; i++) { + intptr_t item = 1 + (random() % 100); + int operation = random() % 1000; + if (operation < 400) { + inserts++; + parcTreeRedBlack_Insert(tree1, (void *) item, (void *) (item << 8)); + } else { + deletes++; + parcTreeRedBlack_Remove(tree1, (void *) item); + } + rbCheckTree(tree1); + } + + parcTreeRedBlack_Destroy(&tree1); + } +} + +LONGBOW_TEST_CASE(Stress, PARC_TreeRedBlack_ExerciseRandomSeeded) +{ + PARCTreeRedBlack *tree1; + unsigned seed; + char *seedString; + + // this test case should obtain a seed and number of iterations from a + // command line option once LongBow has that feature available + seedString = getenv("RBSeed"); + if (seedString) { + seed = (unsigned) atol(seedString); + } else { + seed = 4179329122; // known to fail + } + printf("Random seed %u\n", seed); + + srandom(seed); + + tree1 = parcTreeRedBlack_Create(pointerComp, NULL, NULL, NULL, NULL, NULL); + + int inserts = 0; + int deletes = 0; + + for (int i = 0; i < 100000; i++) { + intptr_t item = 1 + (random() % 10000); + int operation = random() % 1000; + if (operation < 400) { + inserts++; + parcTreeRedBlack_Insert(tree1, (void *) item, (void *) (item << 8)); + } else { + deletes++; + parcTreeRedBlack_Remove(tree1, (void *) item); + } + rbCheckTree(tree1); + } + + parcTreeRedBlack_Destroy(&tree1); +} + +int +main(int argc, char *argv[]) +{ + LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(PARC_TreeRedBlack); + int exitStatus = LONGBOW_TEST_MAIN(argc, argv, testRunner); + longBowTestRunner_Destroy(&testRunner); + exit(exitStatus); +} -- cgit 1.2.3-korg From 40418e3e4261cad4cb57b7b40e46bf2fdbf8c77b Mon Sep 17 00:00:00 2001 From: michele papalini Date: Tue, 8 Aug 2017 18:19:51 +0200 Subject: removed recoursive debuggin functions from RB tree Change-Id: I53aa3b7848c1560cf67de10d6ad34ceba51f6891 Signed-off-by: michele papalini --- libparc/parc/algol/parc_TreeRedBlack.c | 59 ------------------------ libparc/parc/algol/test/test_parc_TreeRedBlack.c | 1 - 2 files changed, 60 deletions(-) (limited to 'libparc/parc/algol/test/test_parc_TreeRedBlack.c') diff --git a/libparc/parc/algol/parc_TreeRedBlack.c b/libparc/parc/algol/parc_TreeRedBlack.c index 05480d67..2d772555 100755 --- a/libparc/parc/algol/parc_TreeRedBlack.c +++ b/libparc/parc/algol/parc_TreeRedBlack.c @@ -28,8 +28,6 @@ #define RED 1 #define BLACK 0 -#define ASSERT_INVARIANTS - struct redblack_node; typedef struct redblack_node Node; @@ -250,50 +248,12 @@ _rbNodeFix(PARCTreeRedBlack *tree, Node *startNode) _rbNodeSetColor(tree->root, BLACK); } -static void -_rbNodeAssertNodeInvariants(Node *node, void *data) -{ - PARCTreeRedBlack *tree = (PARCTreeRedBlack *) data; - assertNotNull(node->parent, "Node has NULL parent"); - assertNotNull(node->left_child, "Left child NULL"); - assertNotNull(node->right_child, "Richt child NULL"); - if (node != tree->root) { - assertTrue(node->parent != tree->nil, "Paren't can't be nill for node!"); - // Don't need to compare to parent, they compared to us - } - assertNotNull(node->key, "We have a null key!!"); - assertNotNull(node->value, "We have a null value!!"); - if (node->left_child != tree->nil) { - assertTrue(tree->keyCompare(node->key, node->left_child->key) > 0, "Left child not smaller?"); - } - if (node->right_child != tree->nil) { - assertTrue(tree->keyCompare(node->key, node->right_child->key) < 0, "Right child not bigger?"); - } -} - -static -void -_rbNodeAssertTreeInvariants(const PARCTreeRedBlack *tree) -{ - assertNotNull(tree, "Tree is null!"); - assertTrue(tree->size >= 0, "Tree has negative size"); - assertNotNull(tree->keyCompare, "No key compare function"); - if (tree->size != 0) { - assertTrue(tree->root != tree->nil, "Tree size = %d > 0 but root is nil", tree->size); - assertNotNull(tree->root, "Tree size > 0 but root is NULL"); -#ifdef ASSERT_INVARIANTS - _rbNodeRecursiveRun((PARCTreeRedBlack *) tree, tree->root, _rbNodeAssertNodeInvariants, (void *) tree); -#endif - } -} - static void _rbNodeFixDelete(PARCTreeRedBlack *tree, Node *node) { Node *fixNode; while ((node != tree->root) && (_rbNodeColor(node) == BLACK)) { - _rbNodeAssertTreeInvariants(tree); if (node == node->parent->left_child) { fixNode = node->parent->right_child; if (_rbNodeColor(fixNode) == RED) { @@ -355,7 +315,6 @@ _rbNodeFixDelete(PARCTreeRedBlack *tree, Node *node) static void _rbNodeRemove(PARCTreeRedBlack *tree, Node *node) { - _rbNodeAssertTreeInvariants(tree); Node *fixupNode; int deleteNodeColor = _rbNodeColor(node); if (node->left_child == tree->nil) { @@ -441,11 +400,9 @@ _rbNodeRemove(PARCTreeRedBlack *tree, Node *node) tree->size--; // Fix the red-blackness - _rbNodeAssertTreeInvariants(tree); if (deleteNodeColor == BLACK) { _rbNodeFixDelete(tree, fixupNode); } - _rbNodeAssertTreeInvariants(tree); } @@ -480,7 +437,6 @@ parcTreeRedBlack_Destroy(PARCTreeRedBlack **treePointer) { assertNotNull(treePointer, "pointer to pointer to tree can't be null"); assertNotNull(*treePointer, "pointer to tree can't be null"); - _rbNodeAssertTreeInvariants(*treePointer); if ((*treePointer)->size > 0) { // If we have any elements in the tree, free them @@ -549,7 +505,6 @@ parcTreeRedBlack_Insert(PARCTreeRedBlack *tree, void *key, void *value) // We have a correct tree. But we need to regain the red-black property. _rbNodeFix(tree, newNode); - _rbNodeAssertTreeInvariants(tree); } // Return value @@ -557,7 +512,6 @@ void * parcTreeRedBlack_Get(PARCTreeRedBlack *tree, const void *key) { assertNotNull(tree, "Tree can't be NULL"); - _rbNodeAssertTreeInvariants(tree); Node *node = tree->root; @@ -583,7 +537,6 @@ parcTreeRedBlack_Remove(PARCTreeRedBlack *tree, const void *key) { assertNotNull(tree, "Tree can't be NULL"); assertNotNull(key, "Key can't be NULL"); - _rbNodeAssertTreeInvariants(tree); Node *node = tree->root; @@ -596,7 +549,6 @@ parcTreeRedBlack_Remove(PARCTreeRedBlack *tree, const void *key) tree->keyFree(&node->key); } parcMemory_Deallocate((void **) &node); - _rbNodeAssertTreeInvariants(tree); return value; } else { if (_rbNodeIsGreaterThan(tree, node, key)) { @@ -609,7 +561,6 @@ parcTreeRedBlack_Remove(PARCTreeRedBlack *tree, const void *key) // We didn't find the node - _rbNodeAssertTreeInvariants(tree); return NULL; } @@ -626,7 +577,6 @@ parcTreeRedBlack_RemoveAndDestroy(PARCTreeRedBlack *tree, const void *key) if (_rbNodeIsEqual(tree, node, key)) { _rbNodeRemove(tree, node); _rbNodeFree(tree, node); - _rbNodeAssertTreeInvariants(tree); return; } else { if (_rbNodeIsGreaterThan(tree, node, key)) { @@ -636,14 +586,12 @@ parcTreeRedBlack_RemoveAndDestroy(PARCTreeRedBlack *tree, const void *key) } } } - _rbNodeAssertTreeInvariants(tree); } void * parcTreeRedBlack_LastKey(const PARCTreeRedBlack *tree) { assertNotNull(tree, "Tree can't be NULL"); - _rbNodeAssertTreeInvariants(tree); Node *node = tree->root; if (tree->size == 0) { @@ -663,7 +611,6 @@ void * parcTreeRedBlack_FirstKey(const PARCTreeRedBlack *tree) { assertNotNull(tree, "Tree can't be NULL"); - _rbNodeAssertTreeInvariants(tree); Node *node = tree->root; @@ -684,7 +631,6 @@ size_t parcTreeRedBlack_Size(const PARCTreeRedBlack *tree) { assertNotNull(tree, "Tree can't be NULL"); - _rbNodeAssertTreeInvariants(tree); return tree->size; } @@ -700,7 +646,6 @@ PARCArrayList * parcTreeRedBlack_Keys(const PARCTreeRedBlack *tree) { assertNotNull(tree, "Tree can't be NULL"); - _rbNodeAssertTreeInvariants(tree); PARCArrayList *keys = parcArrayList_Create(NULL); @@ -721,7 +666,6 @@ PARCArrayList * parcTreeRedBlack_Values(const PARCTreeRedBlack *tree) { assertNotNull(tree, "Tree can't be NULL"); - _rbNodeAssertTreeInvariants(tree); PARCArrayList *values = parcArrayList_Create(NULL); @@ -734,8 +678,6 @@ parcTreeRedBlack_Values(const PARCTreeRedBlack *tree) int parcTreeRedBlack_Equals(const PARCTreeRedBlack *tree1, const PARCTreeRedBlack *tree2) { - _rbNodeAssertTreeInvariants(tree1); - _rbNodeAssertTreeInvariants(tree2); assertNotNull(tree1, "Tree can't be NULL"); assertNotNull(tree2, "Tree can't be NULL"); @@ -794,7 +736,6 @@ parcTreeRedBlack_Equals(const PARCTreeRedBlack *tree1, const PARCTreeRedBlack *t PARCTreeRedBlack * parcTreeRedBlack_Copy(const PARCTreeRedBlack *source_tree) { - _rbNodeAssertTreeInvariants(source_tree); assertNotNull(source_tree, "Tree can't be NULL"); void *key_source; diff --git a/libparc/parc/algol/test/test_parc_TreeRedBlack.c b/libparc/parc/algol/test/test_parc_TreeRedBlack.c index cf2f19ca..7fb1828a 100755 --- a/libparc/parc/algol/test/test_parc_TreeRedBlack.c +++ b/libparc/parc/algol/test/test_parc_TreeRedBlack.c @@ -248,7 +248,6 @@ rbCheckTree(const PARCTreeRedBlack *tree) { assertNotNull(tree, "Tree can't be NULL"); //printf("--- TREE ---\n"); - _rbNodeAssertTreeInvariants(tree); if (tree->size > 0) { //_rbNodeRecursiveRun((PARCTreeRedBlack *)tree,tree->root,rbCheckNode,(void *)tree); recursiveCheckBlackDepth(tree, tree->root); -- cgit 1.2.3-korg