diff options
Diffstat (limited to 'libparc/parc/algol/parc_TreeRedBlack.c')
| -rwxr-xr-x | libparc/parc/algol/parc_TreeRedBlack.c | 840 |
1 files changed, 840 insertions, 0 deletions
diff --git a/libparc/parc/algol/parc_TreeRedBlack.c b/libparc/parc/algol/parc_TreeRedBlack.c new file mode 100755 index 00000000..05480d67 --- /dev/null +++ b/libparc/parc/algol/parc_TreeRedBlack.c @@ -0,0 +1,840 @@ +/* + * 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 <config.h> + +#include <LongBow/runtime.h> + +#include <stdio.h> + +#include <parc/algol/parc_TreeRedBlack.h> + +#include <parc/algol/parc_Memory.h> + +#define RED 1 +#define BLACK 0 + +#define ASSERT_INVARIANTS + +struct redblack_node; +typedef struct redblack_node Node; + +struct redblack_node { + Node *left_child; + Node *right_child; + Node *parent; + void *key; + void *value; + int color; +}; + +struct parc_tree_redblack { + Node *root; + Node *nil; + int size; + PARCTreeRedBlack_KeyCompare *keyCompare; + PARCTreeRedBlack_KeyFree *keyFree; + PARCTreeRedBlack_KeyCopy *keyCopy; + PARCTreeRedBlack_ValueFree *valueFree; + PARCTreeRedBlack_ValueEquals *valueEquals; + PARCTreeRedBlack_ValueCopy *valueCopy; +}; + +typedef void (rbRecursiveFunc)(Node *node, void *data); + +static void +_rbNodeFree(PARCTreeRedBlack *tree, Node *node) +{ + if (tree->keyFree != NULL) { + tree->keyFree(&(node->key)); + } + if (tree->valueFree != NULL) { + tree->valueFree(&(node->value)); + } + parcMemory_Deallocate((void **) &node); +} + +static void +_rbNodeFreeRecursive(PARCTreeRedBlack *tree, Node *node) +{ + if (node->left_child != tree->nil) { + _rbNodeFreeRecursive(tree, node->left_child); + } + if (node->right_child != tree->nil) { + _rbNodeFreeRecursive(tree, node->right_child); + } + // We descended on both branches, now free myself. + _rbNodeFree(tree, node); + tree->size--; +} + +// Run a function on all nodes in the tree, in order +static void +_rbNodeRecursiveRun(PARCTreeRedBlack *tree, Node *node, rbRecursiveFunc *func, void *data) +{ + if (node->left_child != tree->nil) { + _rbNodeRecursiveRun(tree, node->left_child, func, data); + } + func(node, data); + if (node->right_child != tree->nil) { + _rbNodeRecursiveRun(tree, node->right_child, func, data); + } +} + +/** + * Create a node + * Set the parent and children to tree->nil. + * If we are creating the nil node this might leave garbage there (if not preset to NULL). + */ +static Node * +_rbNodeCreate(PARCTreeRedBlack *tree, int color) +{ + Node *node = parcMemory_AllocateAndClear(sizeof(Node)); + assertNotNull(node, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(Node)); + node->color = color; + node->left_child = tree->nil; + node->right_child = tree->nil; + node->parent = tree->nil; + return node; +} + +static void +_rbNodeSetColor(Node *node, uint8_t color) +{ + node->color = color; +} + +static int +_rbNodeColor(const Node *node) +{ + return node->color; +} + +static int +_rbNodeIsEqual(const PARCTreeRedBlack *tree, const Node *node, const void *key) +{ + return (tree->keyCompare(node->key, key) == 0); +} + +static int +_rbNodeIsGreaterThan(const PARCTreeRedBlack *tree, const Node *node, const void *key) +{ + return (tree->keyCompare(node->key, key) > 0); +} + +static void +_rbNodeUpdate(PARCTreeRedBlack *tree, Node *treeNode, Node *newNode) +{ + // Free old values + if (tree->keyFree != NULL) { + tree->keyFree(&(treeNode->key)); + } + if (tree->valueFree != NULL) { + tree->valueFree(&(treeNode->value)); + } + treeNode->key = newNode->key; + treeNode->value = newNode->value; + parcMemory_Deallocate((void **) &newNode); +} + +static void +_rbNodeRotateLeft(PARCTreeRedBlack *tree, Node *node) +{ + Node *subroot = node->right_child; + node->right_child = subroot->left_child; + if (node->right_child != tree->nil) { + node->right_child->parent = node; + } + + subroot->parent = node->parent; + if (tree->root == node) { + tree->root = subroot; + } else { + if (subroot->parent->left_child == node) { + // node was a left child + subroot->parent->left_child = subroot; + } else { + // node was a right child + subroot->parent->right_child = subroot; + } + } + + subroot->left_child = node; + node->parent = subroot; +} + +static void +_rbNodeRotateRight(PARCTreeRedBlack *tree, Node *node) +{ + Node *subroot = node->left_child; + node->left_child = subroot->right_child; + if (node->left_child != tree->nil) { + node->left_child->parent = node; + } + + subroot->parent = node->parent; + if (tree->root == node) { + tree->root = subroot; + } else { + if (subroot->parent->left_child == node) { + // node was a left child + subroot->parent->left_child = subroot; + } else { + // node was a right child + subroot->parent->right_child = subroot; + } + } + + subroot->right_child = node; + node->parent = subroot; +} + +static void +_rbNodeFix(PARCTreeRedBlack *tree, Node *startNode) +{ + Node *node = startNode; + Node *uncle; + while (_rbNodeColor(node->parent) == RED) { + if (node->parent->parent->left_child == node->parent) { + uncle = node->parent->parent->right_child; + if (_rbNodeColor(uncle) == RED) { + // My dad and uncle are red. Switch dad to black. + // Switch grandpa to red and start there. + _rbNodeSetColor(node->parent, BLACK); + _rbNodeSetColor(uncle, BLACK); + _rbNodeSetColor(node->parent->parent, RED); + node = node->parent->parent; + } else { + if (node->parent->right_child == node) { + node = node->parent; + _rbNodeRotateLeft(tree, node); + } + _rbNodeSetColor(node->parent, BLACK); + _rbNodeSetColor(node->parent->parent, RED); + _rbNodeRotateRight(tree, node->parent->parent); + } + } else { + uncle = node->parent->parent->left_child; + if (_rbNodeColor(uncle) == RED) { + // My dad and uncle are red. Switch dad to black. + // Switch grandpa to red and start there. + _rbNodeSetColor(node->parent, BLACK); + _rbNodeSetColor(uncle, BLACK); + _rbNodeSetColor(node->parent->parent, RED); + node = node->parent->parent; + } else { + if (node->parent->left_child == node) { + node = node->parent; + _rbNodeRotateRight(tree, node); + } + _rbNodeSetColor(node->parent, BLACK); + _rbNodeSetColor(node->parent->parent, RED); + _rbNodeRotateLeft(tree, node->parent->parent); + } + } + } + _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) { + _rbNodeSetColor(fixNode, BLACK); + _rbNodeSetColor(node->parent, RED); + _rbNodeRotateLeft(tree, node->parent); + fixNode = node->parent->right_child; + } + if ((_rbNodeColor(fixNode->left_child) == BLACK) && + (_rbNodeColor(fixNode->right_child) == BLACK)) { + _rbNodeSetColor(fixNode, RED); + node = node->parent; + } else { + if (_rbNodeColor(fixNode->right_child) == BLACK) { + _rbNodeSetColor(fixNode->left_child, BLACK); + _rbNodeSetColor(fixNode, RED); + _rbNodeRotateRight(tree, fixNode); + fixNode = node->parent->right_child; + } + _rbNodeSetColor(fixNode, _rbNodeColor(node->parent)); + _rbNodeSetColor(node->parent, BLACK); + _rbNodeSetColor(fixNode->right_child, BLACK); + _rbNodeRotateLeft(tree, node->parent); + node = tree->root; + } + } else { + fixNode = node->parent->left_child; + if (_rbNodeColor(fixNode) == RED) { + _rbNodeSetColor(fixNode, BLACK); + _rbNodeSetColor(node->parent, RED); + _rbNodeRotateRight(tree, node->parent); + fixNode = node->parent->left_child; + } + if ((_rbNodeColor(fixNode->left_child) == BLACK) && + (_rbNodeColor(fixNode->right_child) == BLACK)) { + _rbNodeSetColor(fixNode, RED); + node = node->parent; + } else { + if (_rbNodeColor(fixNode->left_child) == BLACK) { + _rbNodeSetColor(fixNode->right_child, BLACK); + _rbNodeSetColor(fixNode, RED); + _rbNodeRotateLeft(tree, fixNode); + fixNode = node->parent->left_child; + } + _rbNodeSetColor(fixNode, _rbNodeColor(node->parent)); + _rbNodeSetColor(node->parent, BLACK); + _rbNodeSetColor(fixNode->left_child, BLACK); + _rbNodeRotateRight(tree, node->parent); + node = tree->root; + } + } + } + + _rbNodeSetColor(node, BLACK); +} + +// Remove the node from the tree. +// The node must be part of a tree (with parents and children) +static void +_rbNodeRemove(PARCTreeRedBlack *tree, Node *node) +{ + _rbNodeAssertTreeInvariants(tree); + Node *fixupNode; + int deleteNodeColor = _rbNodeColor(node); + if (node->left_child == tree->nil) { + if (node->right_child == tree->nil) { + // ---- We have no children ---- + if (tree->root == node) { + tree->root = tree->nil; + } else { + if (node->parent->left_child == node) { + node->parent->left_child = tree->nil; + } else { + node->parent->right_child = tree->nil; + } + } + fixupNode = tree->nil; + fixupNode->parent = node->parent; + } else { + // ---- We only have right child, move up ---- + if (tree->root == node) { + tree->root = node->right_child; + } else { + if (node->parent->left_child == node) { + node->parent->left_child = node->right_child; + } else { + node->parent->right_child = node->right_child; + } + } + fixupNode = node->right_child; + node->right_child->parent = node->parent; + } + } else { + if (node->right_child == tree->nil) { + // ---- We only have left child, move up ---- + if (tree->root == node) { + tree->root = node->left_child; + } else { + if (node->parent->left_child == node) { + node->parent->left_child = node->left_child; + } else { + node->parent->right_child = node->left_child; + } + } + node->left_child->parent = node->parent; + fixupNode = node->left_child; + } else { + // ---- We have 2 children, move our successor to our location ---- + Node *successor = node->right_child; + while (successor->left_child != tree->nil) { + successor = successor->left_child; + } + deleteNodeColor = _rbNodeColor(successor); + + // Remove successor, it has no left child + if (successor == successor->parent->left_child) { + successor->parent->left_child = successor->right_child; + } else { + successor->parent->right_child = successor->right_child; + } + successor->right_child->parent = successor->parent; + + fixupNode = successor->right_child; + + if (node->parent == tree->nil) { + tree->root = successor; + } else if (node->parent->left_child == node) { + node->parent->left_child = successor; + } else { + node->parent->right_child = successor; + } + successor->parent = node->parent; + successor->left_child = node->left_child; + node->left_child->parent = successor; + successor->right_child = node->right_child; + node->right_child->parent = successor; + + _rbNodeSetColor(successor, _rbNodeColor(node)); + + if (successor->parent == tree->nil) { + tree->root = successor; + } + } + } + tree->size--; + + // Fix the red-blackness + _rbNodeAssertTreeInvariants(tree); + if (deleteNodeColor == BLACK) { + _rbNodeFixDelete(tree, fixupNode); + } + _rbNodeAssertTreeInvariants(tree); +} + + +PARCTreeRedBlack * +parcTreeRedBlack_Create(PARCTreeRedBlack_KeyCompare *keyCompare, + PARCTreeRedBlack_KeyFree *keyFree, + PARCTreeRedBlack_KeyCopy *keyCopy, + PARCTreeRedBlack_ValueEquals *valueEquals, + PARCTreeRedBlack_ValueFree *valueFree, + PARCTreeRedBlack_ValueCopy *valueCopy) +{ + assertNotNull(keyCompare, "We need a key compare function"); + PARCTreeRedBlack *tree = parcMemory_AllocateAndClear(sizeof(PARCTreeRedBlack)); + assertNotNull(tree, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(PARCTreeRedBlack)); + tree->nil = _rbNodeCreate(tree, BLACK); + tree->nil->left_child = tree->nil; + tree->nil->right_child = tree->nil; + tree->nil->parent = tree->nil; + tree->root = tree->nil; + tree->keyCompare = keyCompare; + tree->keyFree = keyFree; + tree->keyCopy = keyCopy; + tree->valueEquals = valueEquals; + tree->valueFree = valueFree; + tree->valueCopy = valueCopy; + tree->size = 0; + return tree; +} + +void +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 + _rbNodeFreeRecursive(*treePointer, (*treePointer)->root); + } + + // Free the nil element + parcMemory_Deallocate((void **) &((*treePointer)->nil)); + + parcMemory_Deallocate((void **) treePointer); + *treePointer = NULL; +} + +void +parcTreeRedBlack_Insert(PARCTreeRedBlack *tree, void *key, void *value) +{ + assertNotNull(tree, "Tree can't be NULL"); + assertNotNull(key, "Key can't be NULL"); + assertNotNull(value, "Value can't be NULL"); + + Node *newNode = _rbNodeCreate(tree, RED); + Node *parent = tree->nil; + Node *node; + + // Set the value for the created node + newNode->key = key; + newNode->value = value; + + // Start at the top + node = tree->root; + + // Let's get to the bottom of the tree to insert. + while (node != tree->nil) { + parent = node; + if (_rbNodeIsEqual(tree, node, key)) { + // We're trying to insert the same value + _rbNodeUpdate(tree, node, newNode); + return; + } else { + if (_rbNodeIsGreaterThan(tree, node, key)) { + // The key is smaller + node = node->left_child; + } else { + node = node->right_child; + } + } + } + + // We're at the bottom. + // node is nil (a leaf) + newNode->parent = parent; + if (parent == tree->nil) { + // nil is our parent, we are the root + tree->root = newNode; + } else { + if (_rbNodeIsGreaterThan(tree, parent, key)) { + parent->left_child = newNode; + } else { + parent->right_child = newNode; + } + } + + // We have inserted one node. + tree->size++; + + // We have a correct tree. But we need to regain the red-black property. + _rbNodeFix(tree, newNode); + + _rbNodeAssertTreeInvariants(tree); +} + +// Return value +void * +parcTreeRedBlack_Get(PARCTreeRedBlack *tree, const void *key) +{ + assertNotNull(tree, "Tree can't be NULL"); + _rbNodeAssertTreeInvariants(tree); + + Node *node = tree->root; + + // Let's get to the bottom of the tree to insert. + while (node != tree->nil) { + if (_rbNodeIsEqual(tree, node, key)) { + // We found the node, return + return node->value; + } else { + if (_rbNodeIsGreaterThan(tree, node, key)) { + node = node->left_child; + } else { + node = node->right_child; + } + } + } + return NULL; +} + +// Return value, remove from tree +void * +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; + + // Let's get to the bottom of the tree to insert. + while (node != tree->nil) { + if (_rbNodeIsEqual(tree, node, key)) { + _rbNodeRemove(tree, node); + void *value = node->value; + if (tree->keyFree != NULL) { + tree->keyFree(&node->key); + } + parcMemory_Deallocate((void **) &node); + _rbNodeAssertTreeInvariants(tree); + return value; + } else { + if (_rbNodeIsGreaterThan(tree, node, key)) { + node = node->left_child; + } else { + node = node->right_child; + } + } + } + + // We didn't find the node + + _rbNodeAssertTreeInvariants(tree); + return NULL; +} + +// remove from tree and destroy +void +parcTreeRedBlack_RemoveAndDestroy(PARCTreeRedBlack *tree, const void *key) +{ + assertNotNull(tree, "Tree can't be NULL"); + assertNotNull(key, "Key can't be NULL"); + + Node *node = tree->root; + // Let's get to the bottom of the tree to insert. + while (node != tree->nil) { + if (_rbNodeIsEqual(tree, node, key)) { + _rbNodeRemove(tree, node); + _rbNodeFree(tree, node); + _rbNodeAssertTreeInvariants(tree); + return; + } else { + if (_rbNodeIsGreaterThan(tree, node, key)) { + node = node->left_child; + } else { + node = node->right_child; + } + } + } + _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) { + // We don't have any entries + return NULL; + } + + // Let's get to the bottom right of the tree to find the largest + while (node->right_child != tree->nil) { + node = node->right_child; + } + + return node->key; +} + +void * +parcTreeRedBlack_FirstKey(const PARCTreeRedBlack *tree) +{ + assertNotNull(tree, "Tree can't be NULL"); + _rbNodeAssertTreeInvariants(tree); + Node *node = tree->root; + + + if (tree->size == 0) { + // We don't have any entries + return NULL; + } + + // Let's get to the bottom left of the tree to find the smallest + while (node->left_child != tree->nil) { + node = node->left_child; + } + + return node->key; +} + +size_t +parcTreeRedBlack_Size(const PARCTreeRedBlack *tree) +{ + assertNotNull(tree, "Tree can't be NULL"); + _rbNodeAssertTreeInvariants(tree); + + return tree->size; +} + +static void +_rbGetKeys(Node *node, void *data) +{ + PARCArrayList *list = (PARCArrayList *) data; + parcArrayList_Add(list, node->key); +} + +PARCArrayList * +parcTreeRedBlack_Keys(const PARCTreeRedBlack *tree) +{ + assertNotNull(tree, "Tree can't be NULL"); + _rbNodeAssertTreeInvariants(tree); + + PARCArrayList *keys = parcArrayList_Create(NULL); + + if (tree->size > 0) { + _rbNodeRecursiveRun((PARCTreeRedBlack *) tree, tree->root, _rbGetKeys, keys); + } + return keys; +} + +static void +_rbGetValues(Node *node, void *data) +{ + PARCArrayList *list = (PARCArrayList *) data; + parcArrayList_Add(list, node->value); +} + +PARCArrayList * +parcTreeRedBlack_Values(const PARCTreeRedBlack *tree) +{ + assertNotNull(tree, "Tree can't be NULL"); + _rbNodeAssertTreeInvariants(tree); + + PARCArrayList *values = parcArrayList_Create(NULL); + + if (tree->size > 0) { + _rbNodeRecursiveRun((PARCTreeRedBlack *) tree, tree->root, _rbGetValues, values); + } + return values; +} + +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"); + + int ret = 1; + + PARCArrayList *keys1 = parcTreeRedBlack_Keys(tree1); + PARCArrayList *keys2 = parcTreeRedBlack_Keys(tree2); + size_t length1 = parcArrayList_Size(keys1); + size_t length2 = parcArrayList_Size(keys2); + + if (length1 == length2) { + for (size_t i = 0; i < length1; i++) { + if (tree1->keyCompare(parcArrayList_Get(keys1, i), parcArrayList_Get(keys2, i)) != 0) { + ret = 0; + break; + } + } + if (ret != 0) { + PARCArrayList *values1 = parcTreeRedBlack_Values(tree1); + PARCArrayList *values2 = parcTreeRedBlack_Values(tree2); + size_t length1 = parcArrayList_Size(values1); + size_t length2 = parcArrayList_Size(values2); + if (length1 == length2) { + for (size_t i = 0; i < length1; i++) { + void *value1 = parcArrayList_Get(values1, i); + void *value2 = parcArrayList_Get(values2, i); + if (tree1->valueEquals != NULL) { + if (tree1->valueEquals(value1, value2) == 0) { + ret = 0; + break; + } + } else { + if (value1 != value2) { + ret = 0; + break; + } + } + } + } + parcArrayList_Destroy(&values1); + parcArrayList_Destroy(&values2); + } + } else { + ret = 0; + } + + parcArrayList_Destroy(&keys1); + parcArrayList_Destroy(&keys2); + return ret; +} + + +/* + * This is a simple implementation of Copy that goes through the list of keys and values. + */ +PARCTreeRedBlack * +parcTreeRedBlack_Copy(const PARCTreeRedBlack *source_tree) +{ + _rbNodeAssertTreeInvariants(source_tree); + assertNotNull(source_tree, "Tree can't be NULL"); + + void *key_source; + void *key_copy; + void *value_source; + void *value_copy; + + PARCTreeRedBlack *tree_copy = parcTreeRedBlack_Create(source_tree->keyCompare, + source_tree->keyFree, + source_tree->keyCopy, + source_tree->valueEquals, + source_tree->valueFree, + source_tree->valueCopy); + + PARCArrayList *keys = parcTreeRedBlack_Keys(source_tree); + PARCArrayList *values = parcTreeRedBlack_Values(source_tree); + + size_t total_keys = parcArrayList_Size(keys); + + for (size_t i = 0; i < total_keys; i++) { + key_source = parcArrayList_Get(keys, i); + value_source = parcArrayList_Get(values, i); + + if (source_tree->keyCopy != NULL) { + key_copy = source_tree->keyCopy(key_source); + } else { + key_copy = key_source; + } + + if (source_tree->valueCopy != NULL) { + value_copy = source_tree->valueCopy(value_source); + } else { + value_copy = value_source; + } + + parcTreeRedBlack_Insert(tree_copy, key_copy, value_copy); + } + + parcArrayList_Destroy(&keys); + parcArrayList_Destroy(&values); + + return tree_copy; +} |