Thread: printing tree trunk

  1. #16
    Registered User
    Join Date
    May 2019
    Posts
    153
    valgrind --leak-check=full ./myprogram

    Use that to get more information in future runs.

    There are ways, good ways and better ways to deal with this.

    On the way OUT of print_tree_and_trunk, check for p == null (this was in my earlier commentary).

    When p is null, the function is the top most call of the recursion (it's about to return to the caller and the leak is done).

    It is then, just before return, when you're done with the tmp_trunk, that you can delete the entire list and the tmp_trunk.

    That's not the better, maybe not even the good way, but it's a start.

    A good way is to more formally describe the ownership of tmp_trunk, so it is more obvious to you.

    Maybe starting a trunk first so there are no calls to print_tree_and_trunk where p is null, and let the caller deal with clearing up the trunk.

    A better way is to more formalize the entire concept such that calling code is not calling print_tree_and_trunk itself, but a "setup" function that deals with tmp_trunk ownership (and deletion), and let THAT call print_tree_and_trunk.
    Last edited by Niccolo; 1 Week Ago at 06:02 PM.

  2. #17
    Registered User
    Join Date
    Apr 2019
    Posts
    655
    --leak-check=full produces
    ==20358==
    ==20358== HEAP SUMMARY:
    ==20358== in use at exit: 512 bytes in 16 blocks
    ==20358== total heap usage: 36 allocs, 20 frees, 1,976 bytes allocated
    ==20358==
    ==20358== 32 bytes in 1 blocks are definitely lost in loss record 10 of 16
    ==20358== at 0x4C2FDFB: malloc (vg_replace_malloc.c:309)
    ==20358== by 0x108D5D: create_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D74: initalize_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E56: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108F4C: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D0C: print (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108945: main (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358==
    ==20358== 32 bytes in 1 blocks are definitely lost in loss record 11 of 16
    ==20358== at 0x4C2FDFB: malloc (vg_replace_malloc.c:309)
    ==20358== by 0x108D5D: create_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D74: initalize_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E56: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108F4C: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D0C: print (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108972: main (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358==
    ==20358== 32 bytes in 1 blocks are definitely lost in loss record 12 of 16
    ==20358== at 0x4C2FDFB: malloc (vg_replace_malloc.c:309)
    ==20358== by 0x108D5D: create_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D74: initalize_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E56: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108F4C: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108F4C: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D0C: print (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108972: main (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358==
    ==20358== 64 (32 direct, 32 indirect) bytes in 1 blocks are definitely lost in loss record 13 of 16
    ==20358== at 0x4C2FDFB: malloc (vg_replace_malloc.c:309)
    ==20358== by 0x108D5D: create_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D74: initalize_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E56: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108F4C: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D0C: print (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108972: main (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358==
    ==20358== 96 (32 direct, 64 indirect) bytes in 1 blocks are definitely lost in loss record 14 of 16
    ==20358== at 0x4C2FDFB: malloc (vg_replace_malloc.c:309)
    ==20358== by 0x108D5D: create_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D74: initalize_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E56: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D0C: print (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108972: main (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358==
    ==20358== 128 (32 direct, 96 indirect) bytes in 1 blocks are definitely lost in loss record 15 of 16
    ==20358== at 0x4C2FDFB: malloc (vg_replace_malloc.c:309)
    ==20358== by 0x108D5D: create_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D74: initalize_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E56: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D0C: print (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108945: main (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358==
    ==20358== 128 (32 direct, 96 indirect) bytes in 1 blocks are definitely lost in loss record 16 of 16
    ==20358== at 0x4C2FDFB: malloc (vg_replace_malloc.c:309)
    ==20358== by 0x108D5D: create_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D74: initalize_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E56: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108F4C: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108E76: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108F4C: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108F4C: print_tree_and_trunk (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108D0C: print (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358== by 0x108945: main (in /home/ben/Downloads/valgrind-3.15.0/trunk)
    ==20358==
    ==20358== LEAK SUMMARY:
    ==20358== definitely lost: 224 bytes in 7 blocks
    ==20358== indirectly lost: 288 bytes in 9 blocks
    ==20358== possibly lost: 0 bytes in 0 blocks
    ==20358== still reachable: 0 bytes in 0 blocks
    ==20358== suppressed: 0 bytes in 0 blocks
    ==20358==
    ==20358== For lists of detected and suppressed errors, rerun with: -s
    ==20358== ERROR SUMMARY: 7 errors from 7 contexts (suppressed: 0 from 0)

    [/code]
    im not sure where you mean i tried it on line 224 and it caused a segmentation fault.... if i do it below the second call to print tree and trunk inside if (!p) it only gets called twice.

  3. #18
    Registered User
    Join Date
    May 2019
    Posts
    153
    Ok, this is weird.

    I posted this earlier, but it evaporated.

    So, I posted it again, and now both appear. Not sure why.

    valgrind --leak-check=full ./myprogram

    Use that in the future (modified for your program obviously).

    Well, there are ways, good ways and better ways to think of this.

    First, it is at the end of print_tree_and_trunk that the moment occurs, but unfortunately that's a recursive function. You can "sense" when returning from the top most call (the one the caller makes) then p == null (I mentioned this in an earlier post).

    When p == null, this means you're about to return to the caller, and tmp_trunk still points to the top of that list. Delete it then.

    However, that's not a better way.

    This concept should be more formalized to get it really right.

    User code should not directly call the recursive function. It should call an interface function that sets up what is required, does the recursive call, then cleans up as required. This means this interface function would create the initial trunk (so that even the first recursive call doesn't see a null p), and can then deal with freeing that list and the trunk upon exit.


    EDIT:

    Ok, I can't really tell line numbers anymore...we may need a fresh post of the code.

    I can try it here and see what's up.


    EDIT 2:

    Oh, I get it now.

    There's more to it than I have posted.

    As it is, you actually can't free the trunks.

    Let me study this a little more.

    The problem, as I see it now, is that the new tmp_trunk is still used in upper level recursions, but some are being lost because they're a bunch of lists, not a full tree.

    Let me study.....back in a while.


    Dinner may interrupt.
    Last edited by Niccolo; 1 Week Ago at 06:26 PM.

  4. #19
    Registered User
    Join Date
    Apr 2019
    Posts
    655
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>
    #include <string.h>
    
    typedef struct Bin_Node
    {
        int data;
        struct Bin_Node *left;
        struct Bin_Node *right;
    }Bin_Node;
    
    typedef struct Bin_Tree
    {
        struct Bin_Node *root; //same as head node in a linked list
        int node_count;
    }Bin_Tree;
    
    typedef struct Trunk
    {
        struct Trunk *previous;
        char mystr[20];
    }Trunk;
    
    Bin_Tree *create_tree(void);
    Bin_Tree *initalize_tree(Bin_Tree *tree);
    Bin_Node *create_node(void);
    Bin_Node *initalize_node(Bin_Node *node, int data);
    bool insert_node(Bin_Node **root, Bin_Node *node);
    void print_tree(const Bin_Node *root);
    void destroy_tree(Bin_Node *root);
    void insert(Bin_Tree *tree, int node_data);
    void print(const Bin_Tree *tree);
    void destroy(Bin_Tree *tree);
    
    // functions created to use c++ code
    Trunk *create_trunk(void);
    Trunk *initalize_trunk(Trunk *p, char strpassed[]);
    void insert_trunk(Bin_Tree *tree);
    
    // copied from c++ code
    void show_trunks(Trunk *p);
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft);
    
    int main()
    {                   //10,6,,3,9,2,3,13,54,20,43
        int i, nums[] = {10, 6, 3, 9, 2, 3, 13, 54, 20, 43};
        Bin_Tree *tree, *tree_trunk;
    
        tree = create_tree();
        for (i = 0; i < 10; i++)
        {
            insert(tree, nums[i]);
        }
        print(tree);
        destroy(tree);
        tree_trunk = create_tree();
        insert_trunk(tree_trunk);
        print(tree_trunk);
        destroy(tree_trunk);
        free(tree);
        free(tree_trunk);
    
        return 0;
    }
    
    Bin_Tree *create_tree(void)
    {
        Bin_Tree *tmp_tree = malloc(sizeof(Bin_Tree));
    
        assert(tmp_tree != NULL);
        tmp_tree = initalize_tree(tmp_tree);
        return tmp_tree;
    }
    
    Bin_Tree *initalize_tree(Bin_Tree *tree)
    {
        tree->node_count = 0;
        tree->root = NULL;
    
        return tree;
    }
    
    Bin_Node *create_node(void)
    {
        return malloc(sizeof(Bin_Node));
    }
    
    Bin_Node *initalize_node(Bin_Node *node, int data)
    {
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    
        return node;
    }
    
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        if (!*root) //parent node has no children??
        {
            *root = node;
            return true;
        }
        else
        {
            if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
            {
                return insert_node(&(*root)->right, node);
            }
            else if ((*root)->data != node->data)
            {
                return insert_node(&(*root)->left, node);
            }
        }
        return false; // the node already existed
    }
    
    void print_tree(const Bin_Node *root)
    {
        if (!root)
        {
            return;
        }
    
        if (root->left) //parent node has a child to the left
        {
            print_tree(root->left);
            printf("searching left child of %d\n", root->data);
        }
    
        printf("node data = %d\n", root->data);
    
        if (root->right) //parent node has a child to the right
        {
            print_tree(root->right);
            printf("searching right child of %d\n", root->data);
        }
    }
    
    void destroy_tree(Bin_Node *root)
    {
        if (root) //parent has children
        {
            destroy_tree(root->left);
            destroy_tree(root->right);
            free(root);
            printf("node deleated\n");
        }
    }
    
    void insert(Bin_Tree *tree, int node_data)
    {
        Bin_Node *root = tree->root, *node;
    
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, node_data);
    
    
        if (!insert_node(&root, node)) //node already exists
        {
            free(node);
            fprintf(stderr, "value already exists\n");
        }
        else
        {
            if (!tree->root)
            {
                tree->root = node;
            }
            tree->node_count++;
        }
    
    }
    
    void print(const Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        //print_tree(root);
        print_tree_and_trunk(root, NULL, false);
        printf("\nthere are %d nodes in the tree\n\n", tree->node_count);
    }
    
    void destroy(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        destroy_tree(root);
    }
    
    // functions created to use c++ code
    Trunk *create_trunk(void)
    {
        return malloc(sizeof(Trunk));
    }
    
    Trunk *initalize_trunk(Trunk *p, char strpassed[])
    {
        Trunk *tmp_trunk = create_trunk();
    
        assert(tmp_trunk != NULL);
        tmp_trunk->previous = p;
        strcpy(tmp_trunk->mystr, strpassed);
        return tmp_trunk;
    }
    
    // functions copied from c++ code
    void show_trunks(Trunk *p)
    {
        if (!p)
        {
            return;
        }
    
        show_trunks(p->previous);
        printf("%s", p->mystr);
    }
    
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft)
    {
        if (!root)
        {
            //printf("free memory here?\n");
            //free(p);
            return;
        }
    
        char prev_str[] = "    ";
        Trunk *tmp_trunk = initalize_trunk(p, prev_str); //this line added instead of new Trunk(prev, prev_str);
    
        print_tree_and_trunk(root->left, tmp_trunk, true);
    
        if (!p)
        {
            strcpy(tmp_trunk->mystr, "---");
        }
        else if (isleft)
        {
            strcpy(tmp_trunk->mystr, ".---");
            strcpy(prev_str, "   |");
        }
        else
        {
            strcpy(tmp_trunk->mystr, "`---");
            strcpy(p->mystr, prev_str);
        }
    
        show_trunks(tmp_trunk);
        printf("%d\n", root->data);
    
        if (p)
        {
            strcpy(p->mystr, prev_str);
        }
    
        strcpy(tmp_trunk->mystr, "   |");
        print_tree_and_trunk(root->right, tmp_trunk, false);
    
        if (!p)
        {
            free(tmp_trunk);
            printf("free p\n");
        }
    }
    
    void insert_trunk(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        root = create_node();
        assert(root != NULL);
        root = initalize_node(root, 1);
        tree->root = root;
        root->left = create_node();
        assert(root->left != NULL);
        root->left = initalize_node(root->left, 2);
        root->right = create_node();
        assert(root->right != NULL);
        root->right = initalize_node(root->right, 3);
        root->left->left = create_node();
        assert(root->left->left != NULL);
        root->left->left = initalize_node(root->left->left, 4);
        root->left->right = create_node();
        assert(root->left->right != NULL);
        root->left->right = initalize_node(root->left->right, 5);
        root->right->left = create_node();
        assert(root->right->left != NULL);
        root->right->left = initalize_node(root->right->left, 6);
        root->right->right = create_node();
        assert(root->right->right != NULL);
        root->right->right = initalize_node(root->right->right, 7);
    }
    here is the code as it stands
    coop

    ps. im off to bed now as its 1,30 so no rush

  5. #20
    Registered User
    Join Date
    May 2019
    Posts
    153
    Ok, dinner done, you're asleep, but this turns out to be quite simple.

    Nothing more than if ( tmp_trunk ) free ( tmp_trunk ); at the end of print_tree_and_trunk. It must be at the end - the very last line of that function, an no consideration for the value of p. I was misunderstanding what I read. The trunk is, essentially, inverted from the tree. While the tree descends, the trunk is built so that the list it forms points backwards toward the call that produced it. As a result, the list doesn't need to be cleared. In fact, it must remain for the calling code to use.

    Trunk is a reverse stack, created in the exact fashion as the stack which is generated by the recursions. All that must be done is to pop off the top of the stack as the function concludes, which is to say merely delete the tmp_trunk that recursive call created.

    I tried a loop of 500 random integers - it printed a good looking tree, with no leaks in my debug session.

  6. #21
    Registered User
    Join Date
    Apr 2019
    Posts
    655
    thanks that worked a treat trust me to try every combo than the right one lol
    coop

  7. #22
    Registered User
    Join Date
    May 2019
    Posts
    153
    Oh, I've never done that


    ...and a bit of an embarrassment for me since I suggested that link to that source, and the bug WAS IN THEIR CODE!

    It works, but it leaks as they posted it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Printing a Binary Tree:
    By jocdrew21 in forum C++ Programming
    Replies: 5
    Last Post: 02-01-2014, 10:06 PM
  2. need help with printing out a tree
    By winggx in forum C Programming
    Replies: 7
    Last Post: 03-03-2010, 01:42 AM
  3. Binary Tree Printing
    By ss3x in forum C++ Programming
    Replies: 0
    Last Post: 02-26-2002, 12:25 AM
  4. FAQ Printing a binary tree?? (C)
    By Unregistered in forum FAQ Board
    Replies: 5
    Last Post: 10-31-2001, 07:35 PM
  5. Printing a binary tree??
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-31-2001, 07:35 PM

Tags for this Thread