void _tree_init(Tree* tree, size_t dataSize)
{
- tree->root = NULL;
- tree->dataSize = dataSize;
- tree->size = 0;
+ tree->root = NULL;
+ tree->dataSize = dataSize;
+ tree->size = 0;
}
Tree* _tree_new(size_t dataSize)
{
- Tree* tree = (Tree*) safe_malloc(sizeof (Tree));
- _tree_init(tree, dataSize);
- return tree;
+ Tree* tree = (Tree*) safe_malloc(sizeof (Tree));
+ _tree_init(tree, dataSize);
+ return tree;
}
Tree* tree_copy(Tree* tree)
{
- Tree* treeCopy = _tree_new(tree->dataSize);
- if (tree->root == NULL)
- return treeCopy;
- _tree_set_root(treeCopy, tree->root->data);
+ Tree* treeCopy = _tree_new(tree->dataSize);
+ if (tree->root == NULL)
+ return treeCopy;
+ _tree_set_root(treeCopy, tree->root->data);
- // Now parallel run on both trees (manual breadth-first walk)
- TreeNode* treeNode = tree->root;
- TreeNode* treeNodeCopy = treeCopy->root;
- while (treeNode != NULL)
- {
- // process current children
- TreeNode* child = treeNode->firstChild;
- while (child != NULL)
- {
- _tree_add_child(treeCopy, treeNodeCopy, child->data);
- child = child->next;
- }
+ // Now parallel run on both trees (manual breadth-first walk)
+ TreeNode* treeNode = tree->root;
+ TreeNode* treeNodeCopy = treeCopy->root;
+ while (treeNode != NULL)
+ {
+ // process current children
+ TreeNode* child = treeNode->firstChild;
+ while (child != NULL)
+ {
+ _tree_add_child(treeCopy, treeNodeCopy, child->data);
+ child = child->next;
+ }
- // try to go to next sibling (NOTE: already added as child of parent)
- if (treeNode->next != NULL)
- {
- treeNode = treeNode->next;
- treeNodeCopy = treeNodeCopy->next;
- continue;
- }
+ // try to go to next sibling (NOTE: already added as child of parent)
+ if (treeNode->next != NULL)
+ {
+ treeNode = treeNode->next;
+ treeNodeCopy = treeNodeCopy->next;
+ continue;
+ }
- // try to go to next "cousin" on same level
- if (treeNode->parent != NULL && treeNode->parent->next != NULL)
- {
- TreeNode* treeNodeParent = treeNode->parent->next;
- TreeNode* treeNodeParentCopy = treeNodeCopy->parent->next;
- while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
- {
- treeNodeParent = treeNodeParent->next;
- treeNodeParentCopy = treeNodeParentCopy->next;
- }
- if (treeNodeParent != NULL)
- {
- treeNode = treeNodeParent->firstChild;
- treeNodeCopy = treeNodeParentCopy->firstChild;
- continue;
- }
- }
+ // try to go to next "cousin" on same level
+ if (treeNode->parent != NULL && treeNode->parent->next != NULL)
+ {
+ TreeNode* treeNodeParent = treeNode->parent->next;
+ TreeNode* treeNodeParentCopy = treeNodeCopy->parent->next;
+ while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
+ {
+ treeNodeParent = treeNodeParent->next;
+ treeNodeParentCopy = treeNodeParentCopy->next;
+ }
+ if (treeNodeParent != NULL)
+ {
+ treeNode = treeNodeParent->firstChild;
+ treeNodeCopy = treeNodeParentCopy->firstChild;
+ continue;
+ }
+ }
- // try to go to next level, and move treeNodeCopy accordingly
- while (treeNode->prev != NULL)
- {
- treeNode = treeNode->prev;
- treeNodeCopy = treeNodeCopy->prev;
- }
- while (treeNode != NULL && tree_is_leaf(treeNode))
- {
- treeNode = treeNode->next;
- treeNodeCopy = treeNodeCopy->next;
- }
- if (treeNode != NULL)
- {
- treeNode = treeNode->firstChild;
- treeNodeCopy = treeNodeCopy->firstChild;
- }
- }
- return treeCopy;
+ // try to go to next level, and move treeNodeCopy accordingly
+ while (treeNode->prev != NULL)
+ {
+ treeNode = treeNode->prev;
+ treeNodeCopy = treeNodeCopy->prev;
+ }
+ while (treeNode != NULL && tree_is_leaf(treeNode))
+ {
+ treeNode = treeNode->next;
+ treeNodeCopy = treeNodeCopy->next;
+ }
+ if (treeNode != NULL)
+ {
+ treeNode = treeNode->firstChild;
+ treeNodeCopy = treeNodeCopy->firstChild;
+ }
+ }
+ return treeCopy;
}
bool tree_empty(Tree* tree)
{
- return (tree->root == NULL);
+ return (tree->root == NULL);
}
UInt tree_size(Tree* tree)
{
- return tree->size;
+ return tree->size;
}
UInt _tree_height_rekursiv(TreeNode* treeNode)
{
- if (tree_is_leaf(treeNode))
- return 1;
- TreeNode* child = treeNode->firstChild;
- UInt maxHeightChild = 0;
- while (child != NULL)
- {
- UInt heightChild = _tree_height_rekursiv(child);
- if (heightChild > maxHeightChild)
- maxHeightChild = heightChild;
- child = child->next;
- }
- return 1 + maxHeightChild;
+ if (tree_is_leaf(treeNode))
+ return 1;
+ TreeNode* child = treeNode->firstChild;
+ UInt maxHeightChild = 0;
+ while (child != NULL)
+ {
+ UInt heightChild = _tree_height_rekursiv(child);
+ if (heightChild > maxHeightChild)
+ maxHeightChild = heightChild;
+ child = child->next;
+ }
+ return 1 + maxHeightChild;
}
UInt tree_height(Tree* tree)
{
- if (tree_empty(tree))
- return 0;
- return _tree_height_rekursiv(tree->root);
+ if (tree_empty(tree))
+ return 0;
+ return _tree_height_rekursiv(tree->root);
}
bool tree_is_leaf(TreeNode* treeNode)
{
- return (treeNode->firstChild == NULL);
+ return (treeNode->firstChild == NULL);
}
void _tree_set_root(Tree* tree, void* data)
{
- tree->root = (TreeNode*) safe_malloc(sizeof (TreeNode));
- tree->root->data = safe_malloc(tree->dataSize);
- memcpy(tree->root->data, data, tree->dataSize);
- tree->root->parent = NULL;
- tree->root->firstChild = NULL;
- tree->root->lastChild = NULL;
- tree->root->prev = NULL;
- tree->root->next = NULL;
- tree->size = 1;
+ tree->root = (TreeNode*) safe_malloc(sizeof (TreeNode));
+ tree->root->data = safe_malloc(tree->dataSize);
+ memcpy(tree->root->data, data, tree->dataSize);
+ tree->root->parent = NULL;
+ tree->root->firstChild = NULL;
+ tree->root->lastChild = NULL;
+ tree->root->prev = NULL;
+ tree->root->next = NULL;
+ tree->size = 1;
}
void* _tree_get(TreeNode* treeNode)
{
- return treeNode->data;
+ return treeNode->data;
}
void _tree_set(Tree* tree, TreeNode* treeNode, void* data)
{
- memcpy(treeNode->data, data, tree->dataSize);
+ memcpy(treeNode->data, data, tree->dataSize);
}
void _tree_add_child(Tree* tree, TreeNode* treeNode, void* data)
{
- TreeNode* newChildNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
- newChildNode->data = safe_malloc(tree->dataSize);
- memcpy(newChildNode->data, data, tree->dataSize);
- newChildNode->next = NULL;
- if (treeNode->lastChild != NULL)
- treeNode->lastChild->next = newChildNode;
- newChildNode->prev = treeNode->lastChild;
- treeNode->lastChild = newChildNode;
- if (treeNode->firstChild == NULL)
- treeNode->firstChild = newChildNode;
- newChildNode->parent = treeNode;
- newChildNode->firstChild = NULL;
- newChildNode->lastChild = NULL;
- tree->size++;
+ TreeNode* newChildNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
+ newChildNode->data = safe_malloc(tree->dataSize);
+ memcpy(newChildNode->data, data, tree->dataSize);
+ newChildNode->next = NULL;
+ if (treeNode->lastChild != NULL)
+ treeNode->lastChild->next = newChildNode;
+ newChildNode->prev = treeNode->lastChild;
+ treeNode->lastChild = newChildNode;
+ if (treeNode->firstChild == NULL)
+ treeNode->firstChild = newChildNode;
+ newChildNode->parent = treeNode;
+ newChildNode->firstChild = NULL;
+ newChildNode->lastChild = NULL;
+ tree->size++;
}
void _tree_add_sibling(Tree* tree, TreeNode* treeNode, void* data)
{
- TreeNode* newSiblingNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
- newSiblingNode->data = safe_malloc(tree->dataSize);
- memcpy(newSiblingNode->data, data, tree->dataSize);
- newSiblingNode->next = treeNode->next;
- if (treeNode->next != NULL)
- treeNode->next->prev = newSiblingNode;
- newSiblingNode->prev = treeNode;
- treeNode->next = newSiblingNode;
- newSiblingNode->parent = treeNode->parent;
- newSiblingNode->firstChild = NULL;
- newSiblingNode->lastChild = NULL;
- tree->size++;
+ TreeNode* newSiblingNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
+ newSiblingNode->data = safe_malloc(tree->dataSize);
+ memcpy(newSiblingNode->data, data, tree->dataSize);
+ newSiblingNode->next = treeNode->next;
+ if (treeNode->next != NULL)
+ treeNode->next->prev = newSiblingNode;
+ newSiblingNode->prev = treeNode;
+ treeNode->next = newSiblingNode;
+ newSiblingNode->parent = treeNode->parent;
+ newSiblingNode->firstChild = NULL;
+ newSiblingNode->lastChild = NULL;
+ tree->size++;
}
void _tree_remove_rekursiv(Tree* tree, TreeNode* treeNode)
{
- TreeNode* child = treeNode->firstChild;
- while (child != NULL)
- {
- TreeNode* nextChild = child->next;
- _tree_remove_rekursiv(tree, child);
- child = nextChild;
- }
- safe_free(treeNode->data);
- safe_free(treeNode);
- tree->size--;
+ TreeNode* child = treeNode->firstChild;
+ while (child != NULL)
+ {
+ TreeNode* nextChild = child->next;
+ _tree_remove_rekursiv(tree, child);
+ child = nextChild;
+ }
+ safe_free(treeNode->data);
+ safe_free(treeNode);
+ tree->size--;
}
void tree_remove(Tree* tree, TreeNode* treeNode)
{
- if (treeNode->parent != NULL)
- {
- if (treeNode->prev == NULL)
- treeNode->parent->firstChild = treeNode->next;
- if (treeNode->next == NULL)
- treeNode->parent->lastChild = treeNode->prev;
- }
- if (treeNode->next != NULL)
- treeNode->next->prev = treeNode->prev;
- if (treeNode->prev != NULL)
- treeNode->prev->next = treeNode->next;
- _tree_remove_rekursiv(tree, treeNode);
+ if (treeNode->parent != NULL)
+ {
+ if (treeNode->prev == NULL)
+ treeNode->parent->firstChild = treeNode->next;
+ if (treeNode->next == NULL)
+ treeNode->parent->lastChild = treeNode->prev;
+ }
+ if (treeNode->next != NULL)
+ treeNode->next->prev = treeNode->prev;
+ if (treeNode->prev != NULL)
+ treeNode->prev->next = treeNode->next;
+ _tree_remove_rekursiv(tree, treeNode);
}
void tree_rm_childs(Tree* tree, TreeNode* treeNode)
{
- TreeNode* child = treeNode->firstChild;
- while (child != NULL)
- {
- TreeNode* nextChild = child->next;
- _tree_remove_rekursiv(tree, child);
- child = nextChild;
- }
- treeNode->firstChild = NULL;
- treeNode->lastChild = NULL;
+ TreeNode* child = treeNode->firstChild;
+ while (child != NULL)
+ {
+ TreeNode* nextChild = child->next;
+ _tree_remove_rekursiv(tree, child);
+ child = nextChild;
+ }
+ treeNode->firstChild = NULL;
+ treeNode->lastChild = NULL;
}
void tree_clear(Tree* tree)
{
- if (tree->root != NULL)
- _tree_remove_rekursiv(tree, tree->root);
- _tree_init(tree, tree->dataSize);
+ if (tree->root != NULL)
+ _tree_remove_rekursiv(tree, tree->root);
+ _tree_init(tree, tree->dataSize);
}
void tree_destroy(Tree* tree)
{
- if (tree->root != NULL)
- tree_clear(tree);
- safe_free(tree);
+ if (tree->root != NULL)
+ tree_clear(tree);
+ safe_free(tree);
}
////////////////////
TreeIterator* tree_get_iterator(Tree* tree, TreeIteratorMode mode)
{
- TreeIterator* treeI = (TreeIterator*) safe_malloc(sizeof (TreeIterator));
- treeI->tree = tree;
- treeI->mode = mode;
- treeI_reset(treeI);
- return treeI;
+ TreeIterator* treeI = (TreeIterator*) safe_malloc(sizeof (TreeIterator));
+ treeI->tree = tree;
+ treeI->mode = mode;
+ treeI_reset(treeI);
+ return treeI;
}
void treeI_reset(TreeIterator* treeI)
{
- treeI->current = treeI->tree->root;
+ treeI->current = treeI->tree->root;
}
bool treeI_has_data(TreeIterator* treeI)
{
- return (treeI->current != NULL);
+ return (treeI->current != NULL);
}
TreeNode* treeI_get_raw(TreeIterator* treeI)
{
- return treeI->current;
+ return treeI->current;
}
void treeI_move_next(TreeIterator* treeI)
{
- TreeIteratorMode mode = treeI->mode;
- switch (mode)
- {
- case IN_DEPTH:
- if (!tree_is_leaf(treeI->current))
- {
- // easy case: just descend deeper in the tree
- treeI->current = treeI->current->firstChild;
- return;
- }
- // leaf: while no next sibling is available, move up
- while (treeI->current != NULL && treeI->current->next == NULL)
- treeI->current = treeI->current->parent;
- if (treeI->current != NULL)
- // run goes on from next sibling
- treeI->current = treeI->current->next;
- break;
- case IN_BREADTH:
- if (treeI->current->next != NULL)
- {
- // easy case : just move to the next sibling
- treeI->current = treeI->current->next;
- return;
- }
- // try to go to next "cousin" on same level
- if (treeI->current->parent != NULL && treeI->current->parent->next != NULL)
- {
- TreeNode* treeNodeParent = treeI->current->parent->next;
- while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
- treeNodeParent = treeNodeParent->next;
- if (treeNodeParent != NULL)
- {
- treeI->current = treeNodeParent->firstChild;
- return;
- }
- }
- // try to go to next level
- while (treeI->current->prev != NULL)
- treeI->current = treeI->current->prev;
- while (treeI->current != NULL && tree_is_leaf(treeI->current))
- treeI->current = treeI->current->next;
- if (treeI->current != NULL)
- treeI->current = treeI->current->firstChild;
- break;
- }
+ TreeIteratorMode mode = treeI->mode;
+ switch (mode)
+ {
+ case IN_DEPTH:
+ if (!tree_is_leaf(treeI->current))
+ {
+ // easy case: just descend deeper in the tree
+ treeI->current = treeI->current->firstChild;
+ return;
+ }
+ // leaf: while no next sibling is available, move up
+ while (treeI->current != NULL && treeI->current->next == NULL)
+ treeI->current = treeI->current->parent;
+ if (treeI->current != NULL)
+ // run goes on from next sibling
+ treeI->current = treeI->current->next;
+ break;
+ case IN_BREADTH:
+ if (treeI->current->next != NULL)
+ {
+ // easy case : just move to the next sibling
+ treeI->current = treeI->current->next;
+ return;
+ }
+ // try to go to next "cousin" on same level
+ if (treeI->current->parent != NULL && treeI->current->parent->next != NULL)
+ {
+ TreeNode* treeNodeParent = treeI->current->parent->next;
+ while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
+ treeNodeParent = treeNodeParent->next;
+ if (treeNodeParent != NULL)
+ {
+ treeI->current = treeNodeParent->firstChild;
+ return;
+ }
+ }
+ // try to go to next level
+ while (treeI->current->prev != NULL)
+ treeI->current = treeI->current->prev;
+ while (treeI->current != NULL && tree_is_leaf(treeI->current))
+ treeI->current = treeI->current->next;
+ if (treeI->current != NULL)
+ treeI->current = treeI->current->firstChild;
+ break;
+ }
}
void treeI_destroy(TreeIterator* treeI)
{
- safe_free(treeI);
+ safe_free(treeI);
}
projects / cgds.git / blobdiff