exc bad access C

Question

I am making a simple BST and, in the add_to_bst() function, it is throwing an error in the first line when referencing the object's value.

CODE

 typedef struct node {
    int value;
    struct node* leftChild;
    struct node* rightChild;
} BSTNode;

BSTNode *new_BSTNode(int val) {
    BSTNode *this = (BSTNode *) malloc(sizeof(BSTNode));
    this->value = val;
    this->leftChild = (BSTNode * ) malloc(sizeof(BSTNode));
    this->rightChild = (BSTNode * ) malloc(sizeof(BSTNode));
    this->leftChild = NULL;
    this->rightChild = NULL;
    return this;
}

typedef struct bst {
    BSTNode * root;
} BST;

BST *new_BST(int root_val) {
    BST *this = (BST *) malloc(sizeof(BST));
    this->root = (BST * ) malloc(sizeof(BSTNode));
    this->root->value = root_val;
//    this->root->value = (int *) malloc(sizeof(int));
    return this;
}


int node_get(BSTNode *n, int i) {
    if (n == NULL) return -1;
    if (i == n-> value) return 1;
    if (i > n-> value) return node_get(n->rightChild, i);
    else return node_get(n->leftChild, i);
}

int bst_get(BST *bst, int i) {
    return node_get(bst->root, i);
}

void add_to_bst_node(int i, BSTNode *to) {
    int n = to->value;                      // <--- ERR
    printf("\nBST VAL: %d", n);

    if (i > n) {
        if (to->rightChild == NULL)
            to->rightChild = new_BSTNode(i);
        else
            add_to_bst_node(i, to->rightChild);
    } else {
        if (to->leftChild == NULL)
            to->leftChild = new_BSTNode(i);
        else
            add_to_bst_node(i, to->leftChild);
    }


}


void add_to_bst(BST *tree, int i) {

    if (tree->root != NULL) {
        add_to_bst_node(i, tree->root);
    } else {
        tree->root = new_BSTNode(i);
    }
}


int main() {

    BST *bst = new_BST(10);
    add_to_bst(bst, 10);

}

RUN MSG:

0x7fa64fc00690
0x7fa64fc00640
First Val: 10

Process finished with exit code 11

BUILD ERR:

`tree -> root -> value != NULL` Why are you comparing an `int` to `NULL`? — Osiris, Jan 22 '19 at 00:21
Note that the dot `.` and arrow `->` operators bind very tightly indeed and should not be written with spaces around them. — Jonathan Leffler, Jan 22 '19 at 00:43
Yes @JonathanLeffler and I eliminated the surrounding spaces, but it had no effect on the execution of the program. — Ryan Cocuzzo, Jan 22 '19 at 00:50
Sorry — I should have made it clear; the spacing around the dot and arrow operators is a cosmetic issue, not a functional one. The compiler doesn't care; people reading your code do. — Jonathan Leffler, Jan 22 '19 at 00:51
You fixed it in `new_BSTNode` (should be `this->leftChild = NULL;` though) but in `new_BST` it is still uninitialized. I would suggest to call `new_BSTNode` from `new_BST`. — Osiris, Jan 22 '19 at 00:57
@Osiris Is an initialization to null necessary? I updated the cost above to include one, as per your comment, but it didn't seem to make a difference with the error. Additionally, as for the spacing question, is it not better practice to incorporate spacing when possible? I have always known that to be more legible. — Ryan Cocuzzo, Jan 22 '19 at 01:08
[don't cast malloc](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — Barmar, Jan 22 '19 at 01:09
@RyanCocuzzo It's good to use spacing around arithmetic operators. But it's not idiomatic to use it for structural operators like `.`, `->`, `[]`, and `()`. — Barmar, Jan 22 '19 at 01:10
I don't know which (if any) of these issues is the crucial one, but: (1) your `new_BSTNode()` function should contain just one memory allocation (the left and right children nodes should be initialized to NULL); the `new_BST()` function should use the `new_BSTNode()` function to allocate the `BSTNode`; (3) for debugging work, make sure your `printf()` format strings end with a newline as otherwise, the debugging output may not appear at all. — Jonathan Leffler, Jan 22 '19 at 01:11
@JonathanLeffler This solved it. I noted the line above that was the issue under "Solution" — Ryan Cocuzzo, Jan 22 '19 at 01:25
Please do not change the code after you've received answers — or, add the new code as an amendment, but leave 'the original' code unchanged. While there are no answers, you can make changes (but try to avoid needing to them). Once there are answers, you are more limited; changes you make must not invalidate the answers. Revision 2 assigned to `root->leftChild = (BSTNode *)malloc(sizeof(BSTNode));` twice in a row, for example, instead of `leftChild` and `rightChild`. Revised 5 code leaks the results of the two `malloc()` calls for the children; you should delete `malloc()` and assign `NULL`. — Jonathan Leffler, Jan 22 '19 at 01:32

score 1 · Answer 1 · answered Jan 22 '19 at 00:57

1

BSTNode *new_BSTNode(int val) {
    BSTNode *this = (BSTNode *) malloc(sizeof(BSTNode));
    this -> value = val;
    this -> leftChild = (BSTNode * ) malloc(sizeof(BSTNode));
    this -> leftChild = (BSTNode * ) malloc(sizeof(BSTNode));
    return this;
}

This leaves this->rightChild uninitialized and leaves this->leftChild pointing to uninitialized garbage. Neither of these issues is fixed in the code that calls new_BSTnode.

void add_to_bst_node(int i, BSTNode *to) {
    int n = to -> value;             // <------ ERROR

Not surprising, since to comes from leftChild and rightChild, both of which are broken by the logic of new_BSTNode.

Also:

BST *new_BST(int root_val) {
    BST *this = (BST *) malloc(sizeof(BST));
    this -> root = (BST * ) malloc(sizeof(BSTNode));
    this -> root -> value = root_val;
//    this -> root -> value = (int *) malloc(sizeof(int));
    return this;
}

This doesn't set this->root->leftChild or this->root->rightChild either, so again, they're garbage that gets passed to add_to_bst_node as to.

answered Jan 22 '19 at 00:57

David Schwartz

179,497
17
214
278

I changed the second reference to `this->rightChild`, and added in, from another comment and the second part of your own, added in an initialization of both children to NULL (which seems like a redundancy). The error still looks to be the same. The code is updated above. – Ryan Cocuzzo Jan 22 '19 at 01:06
A "Bad Access" causing a General Protection Fault simply means you are attempting to access memory outside the valid range for your executable. 99.9% of the time, the cause is attempting to use a pointer holding an invalid or uninitialized value. Each place in your code where you use a pointer, you must insure it holds a valid address. There may be more instances in your code where you have problems. See also: [Do I cast the result of malloc?](http://stackoverflow.com/q/605845/995714) – David C. Rankin Jan 22 '19 at 01:41
@RyanCocuzzo Except now `new_BST` sets `root` to point to a node whose `leftChild` and `rightChild` are garbage. And you are right, the calls to `malloc` can go away since you throw the value away. – David Schwartz Jan 22 '19 at 01:51

score 0 · Answer 2 · answered Jan 22 '19 at 01:28

The creation of the new node, and insertion into the tree seems incorrect.

A new node should not allocate space for the left and right subtrees. Since new nodes are always added to the extremities, they never have subtrees when new anyway.

BSTNode *new_BSTNode( int val )
{
    BSTNode *this = ( BSTNode * ) malloc( sizeof( BSTNode ) );
    if ( this != NULL )
    {
        this->value      = val;
        this->leftChild  = NULL;
        this->rightChild = NULL;
    }
    return this;
}

Using a recursive algorithm when inserting new data allows the code to "walk" the tree, finding the correct place for insertion.

void add_to_bst_node( int value, BSTNode *to )
{
    if (to != NULL)
    {
        if (value > to->value)
        {
            // Add to child-right subtree
            if (to->rightChild == NULL)
            {
                // right-tree is empty, create it
                to->rightChild = new_BSTNode( value );
            }
            else
            {
                // add it somewhere on the right-side (recursively)
                add_to_bst_node( value, to->rightChild );
            }
        }
        else // if (i <= to->value)
        {
            // Add to child-left subtree
            if (to->leftChild == NULL)
            {
                // left-tree is empty, create it
                to->leftChild = new_BSTNode( value );
            }
            else
            {
                // add it somewhere on the right-side (recursively)
                add_to_bst_node( value, to->leftChild );
            }
        }
    }
}

A tree is just a node. Making a separate structure for a "tree" is just extra work.

typedef BSTNode BST;

So the creation of a tree, is just the creation of a node:

BST *new_BST( int value )
{
    return new_BSTNode( value );
}

score 0 · Answer 3 · answered Jan 22 '19 at 01:45

The branch in add_to_BST() always chooses the tree->root != NULL if it was initialised error-free. Then the add_to_BST_node() dereferences garbage, (as the other answers have pointed out); here is a graphical representation of the memory allocating functions,

And,

I recommend thinking about what the states are in ones system and drawing them out first so one doesn't fall into an invalid state. Also, if one is doing a constructor, it's a good idea to initialise the entire structure.

exc bad access C

CODE

RUN MSG:

BUILD ERR:

3 Answers3