0

So i am trying to finish up a project and i am stuck. I have made almost everything and from my perspective the function i have made should be working fine but it does not. First of all i am reading IPs from a file in a decimal form and making them in a binary form based on the slash for different prefixes. For example if I read 8.0.0.0/8 means that i have to insert in my tree 00001000.

After that the user gives me an IP and then I have to search the tree one by one the leaves to match if I have to go left, that means 0, or if i have to go right, that means 1. And that's where I am stuck because I have made a print/traverse method that starts alright but breaks without letting me understand why. I am 99% sure that my insert method is correct because i have tested it with many debugging printfs so i am providing the structure of the struct I am using and the code of the print & insert functions.

typedef struct TREE{
    int data;
    struct TREE* left;
    struct TREE* right;
}TREE;

TREE* insert(TREE* root, int level, int tmpData[], int *slash) {
    
    TREE *tmp = root;
    TREE *newNode = NULL;
    int i;
    for(i = 0; i < slash[4]; i++) {

        if(tmpData[i] == 0) {
            //printf("We go LEFT.\n");
            printf("0");
            if(tmp -> left == NULL) {
                newNode = (TREE*)malloc(sizeof(TREE));
                if (newNode == NULL) {
                    printf("\033[0;31mFailed to allocate memory for a node.\033[0m\n");
                    exit(1);
                }
                newNode -> data = tmpData[i];
                newNode -> left = NULL;
                newNode -> right = NULL;
                tmp -> left = newNode;
            }
            tmp = tmp -> left;
        } else if(tmpData[i] == 1) {
            //printf("We go RIGHT.\n");
            printf("1");
            if(tmp -> left == NULL) {
                newNode = (TREE*)malloc(sizeof(TREE));
                if (newNode == NULL) {
                    printf("\033[0;31mFailed to allocate memory for a node.\033[0m\n");
                    exit(1);
                }
                newNode -> data = tmpData[i];
                newNode -> left = NULL;
                newNode -> right = NULL;
                tmp -> right = newNode;
            }
            tmp = tmp -> right;
        }
    }
}

void print(TREE* root, int max[], int tmpData[], int slash, int level){
    
    int i = 0;
    TREE *tmp = root;
    
    if (tmpData[0] == 0 && root -> left != NULL){
        tmp = root -> left;
    }
    else if (tmpData[0] == 1 && root -> right != NULL){
        tmp = root -> right;
    }
    else {
        return;
    }
    
    while(i != binarySIZE){
        if (tmp == NULL){
            printf("We BREAK.\n");
            break;
        }
        
        printf("\n%d\n", tmp -> data);
        if (tmpData[i] == 0){
            printf("We go LEFT.\n");
            max[i] = tmp -> data;
            printf("%d\n", tmp -> data);
            tmp = tmp -> left;
        }
        else if (tmpData[i] == 1){
            printf("We go RIGHT.\n");
            max[i] = tmp -> data;
            printf("%d\n", tmp -> data);
            tmp = tmp -> right;
        }
        i++;
    }
}

Also i am initiating the tree with a root number 32 and the two pointer to NULL

root = (TREE*)malloc(sizeof(TREE));
root->data = 32;
root->left = NULL;
root->right = NULL;

And because of this initiation i have to use this perimeters at the start of the print so it does not check the root number 32.

if (tmpData[0] == 0 && root -> left != NULL){
    tmp = root -> left;
}
else if (tmpData[0] == 1 && root -> right != NULL){
    tmp = root -> right;
}
else {
    return;
}

Any help is really appreciated.

Kamora
  • 83
  • 7
  • Using only `printf` for debugging may not be sufficient. Have you tried running your code line by line in a [debugger](https://stackoverflow.com/q/25385173/12149471) while monitoring the values of all variables, in order to determine at which point your program stops behaving as intended? – Andreas Wenzel Jan 05 '21 at 17:17
  • Is my understanding correct that each node (more accurately, each edge) represents a single *bit* in subnet mask ? Just curious. – WhozCraig Jan 05 '21 at 17:34
  • @AndreasWenzel Yes, i have tried running it throw a debugger and it seems that the tree is generated correctly. – Kamora Jan 05 '21 at 17:46
  • @WhozCraig That is correct. – Kamora Jan 05 '21 at 17:46
  • And when you say you expect to see the "break" call, but don't, do you mean it just sits in a loop and spins forever (which should be easily detected in a debugger) or that it "finishes" but you never got your "break" ? Understand the latter is conditional on `(i != binarySIZE)` remaining *true*, but left with nowhere to go (i.e. the next leg child pointer led to null). if `i == binarySize` then it will break the loop with no announcement. a proper [mcve] is *really* needed for this. – WhozCraig Jan 05 '21 at 17:56
  • @WhozCraig actually the problem is that i see the break point but in situations where it should just continue searching. For example lets say i only read 135.0.0.0/8 where the saved prefix is 10000111 and the user wants to search 135.156.34.28 the program has to search the tree until it has nothing to match. In this example it must match only the first 8 bits (10000111) but instead of that it starts with 1 and then it breaks. – Kamora Jan 05 '21 at 18:36
  • You test for `tmp -> left == NULL` in both branches. In the `else` you should test for `tmp->right`. Is it a copy-paste typo or the actual code? – user58697 Jan 05 '21 at 19:56
  • @user58697 Dude you are absolutely right and i missed it... Thank you so much for your help! – Kamora Jan 05 '21 at 21:39

0 Answers0