Leaked Memory while creating bst, Parsing assistance needed

Question

Node *addToTree(Node *head, Node *newNode) {
    if (head == NULL) {
        head = newNode;
    } else {
        if (newNode->price < head->price) {
            head->left = addToTree(head->left, newNode);
        } else
        if (newNode->price > head->price) {
            head->right = addToTree(head->right, newNode);
        } else
        if (newNode->price == head->price) {
            free(newNode);
        }
    }
    return head;
}

Node *getCars(char *name) {
    FILE *fp;
    if ((fp = fopen(name, "r")) == NULL) {
        return NULL;
    } else {
        Node *head = NULL;
        Node *tmp;
        char delim[2] = "|";
        char car[MAXLINELENGTH] = {0};
        char *token = NULL;
        int ch;
        while (!feof(fp)) {
            tmp = malloc(sizeof(Node));
            tmp->left = tmp->right = NULL;
            fgets(car, MAXLINELENGTH, fp);
            token = strtok(car, delim);
            while (token != NULL) {
                if (strcmp(token, "model") == 0) {
                    token = strtok(NULL, delim);
                    strcpy(tmp->model, token);
                } else
                if (strcmp(token, "make") == 0) {
                    token = strtok(NULL, delim);    
                    strcpy(tmp->make, token);
                } else
                if (strcmp(token, "price") == 0) {
                    token = strtok(NULL, delim);                
                    tmp->price = atoi(token);
                } else
                if (strcmp(token, "year") == 0) {
                    token = strtok(NULL, delim);                
                    tmp->year = atoi(token);
                } else
                if (strcmp(token, "color") == 0) {
                    token = strtok(NULL, delim);    
                    strcpy(tmp->color, token);
                } else
                if (strcmp(token, "type") == 0) {
                    token = strtok(NULL, delim);
                    if (token == NULL) {
                        break;
                    }   
                    strcpy(tmp->type, token);
                } else
                if (strcmp(token, "mileage") == 0) {
                    token = strtok(NULL, delim);    
                    tmp->mileage = atoi(token);
                }
                token = strtok(NULL, delim);
            }
            if (check("makes.txt", tmp->make) != 1) {
                continue;
            } else
            if (check("colors.txt", tmp->color) != 1) {
                continue;
            } else
            if (check("types.txt", tmp->type) != 1) {
                continue;
            } else {
                head = addToTree(head, tmp);
            }
        }
        free(tmp);
        fclose(fp);
        return head;
    }
}

So for a homework assignment I'm supposed to parse through an input file with around 10000 cars information being make, model, color, type, price, mileage, and year and input them into a BST based on their price, when I run the code it says I have 274 bytes lost at the line where I malloc the tmp pointer. I was just wondering what the solution to this is, and also I could really any advice/help on parsing cause to me my getCars function is ugly, and it also takes around 15 seconds to run, any help is greatly appreciated!

change `while (!feof(fp)) {` to `while(fgets(car, MAXLINELENGTH, fp)){` and delete `free(tmp);` — BLUEPIXY, Nov 16 '16 at 00:16
@BLUEPIXY would you also happen to know why im getting "conditional jump depends on uninitialized value" errors in valgrind as well? or would you have to see more code? — Caleb lee, Nov 16 '16 at 00:21
Add error message and corresponding source part.(Not for me) — BLUEPIXY, Nov 16 '16 at 00:33
`check("makes.txt", tmp->make)` : Change it so that it does not read from the file every time. — BLUEPIXY, Nov 16 '16 at 00:43
It takes time to read the file every time for _10000 cars_ . e.g. First read once to create a sorted table. then Do binary-search for check. — BLUEPIXY, Nov 16 '16 at 01:11
Do you mean make a table for the makesfile or can you explain a little more? — Caleb lee, Nov 16 '16 at 01:26
Please respect the parameters of the site: don't put multiple different questions in the same post. [ask]. Open ended questions of the form "please debug my code for me" are not likely to help future visitors. — rici, Nov 16 '16 at 19:45

score 0 · Answer 1 · edited May 23 '17 at 10:30

There are multiple problems in your code:

while (!feof(fp)) is always wrong. Read this: Why is “while ( !feof (file) )” always wrong?
You should check for missing values for all properties.
You do not free the node when you fail to match the make, color or type.
You should not free tmp after the parsing loop: it may have been inserted into the BST and it may even be uninitialized if the file is empty.
It is surprising that you do not insert the car into the BST it another car has the same price... you should probably check for duplicates more accurately.

Here is an improved version:

Node *addToTree(Node *head, Node *newNode) {
    if (head == NULL) {
        head = newNode;
    } else {
        if (newNode->price < head->price) {
            head->left = addToTree(head->left, newNode);
        } else
        if (newNode->price > head->price) {
            head->right = addToTree(head->right, newNode);
        } else
        if (newNode->price == head->price) {
            free(newNode);
        }
    }
    return head;
}

Node *getCars(const char *name) {
    FILE *fp;
    if ((fp = fopen(name, "r")) == NULL) {
        return NULL;
    } else {
        Node *head = NULL;
        char delim[] = "|";
        char car[MAXLINELENGTH];

        while (fgets(car, sizeof car, fp)) {
            Node *tmp = malloc(sizeof(Node));
            /* initialize all members */
            tmp->left = tmp->right = NULL;
            tmp->model[0] = tmp->make[0] = tmp->color[0] = tmp->type[0] = '\0';
            tmp->price = tmp->year = tmp->mileage = 0; 
            char *token = token = strtok(car, delim);
            while (token != NULL) {
                if (strcmp(token, "model") == 0) {
                    token = strtok(NULL, delim);
                    if (token == NULL) break;
                    strcpy(tmp->model, token);
                } else
                if (strcmp(token, "make") == 0) {
                    token = strtok(NULL, delim);    
                    if (token == NULL) break;
                    strcpy(tmp->make, token);
                } else
                if (strcmp(token, "price") == 0) {
                    token = strtok(NULL, delim);                
                    if (token == NULL) break;
                    tmp->price = atoi(token);
                } else
                if (strcmp(token, "year") == 0) {
                    token = strtok(NULL, delim);                
                    if (token == NULL) break;
                    tmp->year = atoi(token);
                } else
                if (strcmp(token, "color") == 0) {
                    token = strtok(NULL, delim);    
                    if (token == NULL) break;
                    strcpy(tmp->color, token);
                } else
                if (strcmp(token, "type") == 0) {
                    token = strtok(NULL, delim);
                    if (token == NULL) break;
                    strcpy(tmp->type, token);
                } else
                if (strcmp(token, "mileage") == 0) {
                    token = strtok(NULL, delim);    
                    if (token == NULL) break;
                    tmp->mileage = atoi(token);
                }
                token = strtok(NULL, delim);
            }
            if (check("makes.txt", tmp->make) != 1
            ||  check("colors.txt", tmp->color) != 1
            ||  check("types.txt", tmp->type) != 1) {
                /* unrecognized make, type or color: discard entry */
                free(tmp);
            } else {
                head = addToTree(head, tmp);
            }
        }
        fclose(fp);
        return head;
    }
}

Holy cow thank you so much, this is amazing. If i remove the part where I free the node if the prices are the same would I have leaked memory? — Caleb lee, Nov 16 '16 at 00:57
Also, I can't use calloc because we haven't learned that yet in my computer science class, is it possible to use the original malloc call to tmp? — Caleb lee, Nov 16 '16 at 01:04
In `addToTree`, you must either insert the node into the tree or free it, so you currently do not leak memory there, I'm just wondering if you should discard cars that have the same price or if they should also have the same make, type and color too. I updated the code to not use `calloc()`: you must initialize the node completely then. — chqrlie, Nov 16 '16 at 06:16
Thank you, this solves another error with uninitialized errors in valgrind, I removed the if statement checking if the prices are the same and it seems to work the same and not cause any errors — Caleb lee, Nov 17 '16 at 00:08
@Caleblee: if you remove the `free()` statement when prices are equal, you should decide how do handle identical prices: do you put duplicates into the left branch or the right branch? Adjust the `<` or `>` comparison operators according to your choice. — chqrlie, Nov 17 '16 at 00:16

Leaked Memory while creating bst, Parsing assistance needed

1 Answers1