/* * 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"); 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); }