Hey everyone.
So, my final project in C deals with generic Red Black tree data structure.
I have only one function to implement to finish this project but some bugs occur with him.
I think the problem is with the copy pointer, as it's passed as a pointer and not as a pointer to pointer, so if I am modifying it - it doesn't effect the "real one".
We mustn't change the signature of the functions and this is my problem.
Code:
/**
* Represents a vector. The double* should be dynamically allocated
*/
typedef struct Vector
{
int len;
double *vector;
} Vector;
/**
* copy pVector to pMaxVector if : 1. The norm of pVector is greater then the norm of pMaxVector.
* 2. pMaxVector == NULL.
* @param pVector pointer to Vector
* @param pMaxVector pointer to Vector
* @return 1 on success, 0 on failure (if pVector == NULL: failure).
*/
int copyIfNormIsLarger(const void *pVector, void *pMaxVector); // implement it in Structs.c
There is some functionality which depends on this function (when the current data in the tree is Vector) from above:
Code:
/*
* a node of the tree.
*/
typedef struct Node
{
struct Node *parent, *left, *right;
Color color;
void *data;
} Node;
/**
* represents the tree
*/
typedef struct RBTree
{
Node *root;
CompareFunc compFunc;
FreeFunc freeFunc;
int size;
} RBTree;
/**
* a function to apply on all tree items.
* @object: a pointer to an item of the tree.
* @args: pointer to other arguments for the function.
* @return: 0 on failure, other on success.
*/
typedef int (*forEachFunc)(const void *object, void *args);
/**
* Helper function to forEachRBTree which is in charge to recurse the BST in ascending order while activating each
* one of the nodes.
* @param tree: the tree with all the items.
* @param func: the function to activate on all items.
* @param args: more optional arguments to the function (may be null if the given function support it).
* @param indicator: if the func is failed - indicator will be assigned with -1 indicating failure.
* @return: 0 on failure, other on success.
*/
void forEachRBTreeHelper(Node *node, forEachFunc func, void *args, int* indicator)
{
if (node == NULL)
{
return;
}
/* first recur on left child */
forEachRBTreeHelper(node->left, func, args, indicator);
/* then activate the func on node */
if (node->data == NULL || func(node->data, args) == 0) {
*indicator = -1; // failed!
}
/* now recur on right child */
forEachRBTreeHelper(node->right, func, args, indicator);
}
int forEachRBTree(RBTree *tree, forEachFunc func, void *args) {
if (tree == NULL || func == NULL) {
return 0;
}
int indicator = 0;
forEachRBTreeHelper(tree->root, func, args, &indicator); // Recurse and activate func
if (indicator == -1) {
return 0;
}
return 1;
}
/**
* free all memory of the data structure using in-order recursion in order to not to cause memory leaks.
* @param node: the current node to free.
*/
void freeRBTreeHelper(Node* node) {
if (node == NULL) {
return;
}
freeRBTreeHelper(node->left);
if (node->right == NULL && node->left == NULL) {
free(node);
}
freeRBTreeHelper(node->right);
}
So, I have a bug in one of the functions: copyIfNormIsLarger (I have a nonsense implementation so I don't even attach it), forEachRBTree or in forEachRBTreeHelper.
Can someone help me with that?
Thanks in advance!