Mixing
Invalid read even though object exists
I am trying to implement a self-balancing binary search tree. When I try to get the height of the right branch, it works until I reach this point. Then I get a segmentation fault error and valgrind says there was an invalid read of size 8. The odd thing is when I look at the tree when this error occurs, the right branch isn't null. Is there some check that I am forgetting to do that is causing this error?
Lines where error is thrown:
int rightChildHeight = 0;
if (n->right != NULL)
rightChildHeight = n->right->getHeight();
getHeight():
int Node::getHeight()
{
// No kids => 2
if (!left && !right)
return 1;
// 1 kid => height of kid +1
else if (!left && right)
return right->getHeight() + 1;
else if (left && !right)
return left->getHeight() + 1;
// 2 kids => height of taller kid +1
else
return max(left->getHeight(), right->getHeight()) + 1;
}
Tree when the error occurs:
c++ c++11 binary-search-tree avl-tree
asked Nov 21 '18 at 6:24
Blake MorganBlake Morgan
4971520
add a comment |
I am trying to implement a self-balancing binary search tree. When I try to get the height of the right branch, it works until I reach this point. Then I get a segmentation fault error and valgrind says there was an invalid read of size 8. The odd thing is when I look at the tree when this error occurs, the right branch isn't null. Is there some check that I am forgetting to do that is causing this error?
Lines where error is thrown:
int rightChildHeight = 0;
if (n->right != NULL)
rightChildHeight = n->right->getHeight();
getHeight():
int Node::getHeight()
{
// No kids => 2
if (!left && !right)
return 1;
// 1 kid => height of kid +1
else if (!left && right)
return right->getHeight() + 1;
else if (left && !right)
return left->getHeight() + 1;
// 2 kids => height of taller kid +1
else
return max(left->getHeight(), right->getHeight()) + 1;
}
Tree when the error occurs:
c++ c++11 binary-search-tree avl-tree
asked Nov 21 '18 at 6:24
Blake MorganBlake Morgan
4971520
1
"the right branch isn't null" - Doesn't mean it holds a valid address either. You have bug somewhere in the tree's initialization/rotation/insertion/deletion. We can't find it for you psychically.
– StoryTeller
Nov 21 '18 at 6:37
1
Most likely,rightis a "dangling pointer" (i.e. it is non-null but it is not pointing at a valid object -- this typically happens if the object it was pointing at was deleted, but the pointer was not modified, so it remains pointing at the memory location where the object previously existed. Dereferencing a dangling pointer is an error and invokes undefined behavior)
– Jeremy Friesner
Nov 21 '18 at 6:37
Pointer n is not pointing to a valid address.
– tunglt
Nov 21 '18 at 6:44
@TungLeThanh But if I point to n->left I get no error. Does that mean n->right isn't pointing to a valid address?
– Blake Morgan
Nov 21 '18 at 6:45
@BlakeMorgan: if your program working memory space is trully at 0x5555555xxxxx, n is valid, sorry for that. I see Valgrin ou debug program fills out unused/uninitialized memory with 0x55 sometime.
– tunglt
Nov 21 '18 at 7:02
add a comment |
I am trying to implement a self-balancing binary search tree. When I try to get the height of the right branch, it works until I reach this point. Then I get a segmentation fault error and valgrind says there was an invalid read of size 8. The odd thing is when I look at the tree when this error occurs, the right branch isn't null. Is there some check that I am forgetting to do that is causing this error?
Lines where error is thrown:
int rightChildHeight = 0;
if (n->right != NULL)
rightChildHeight = n->right->getHeight();
getHeight():
int Node::getHeight()
{
// No kids => 2
if (!left && !right)
return 1;
// 1 kid => height of kid +1
else if (!left && right)
return right->getHeight() + 1;
else if (left && !right)
return left->getHeight() + 1;
// 2 kids => height of taller kid +1
else
return max(left->getHeight(), right->getHeight()) + 1;
}
Tree when the error occurs:
c++ c++11 binary-search-tree avl-tree
asked Nov 21 '18 at 6:24
Blake MorganBlake Morgan
4971520
I am trying to implement a self-balancing binary search tree. When I try to get the height of the right branch, it works until I reach this point. Then I get a segmentation fault error and valgrind says there was an invalid read of size 8. The odd thing is when I look at the tree when this error occurs, the right branch isn't null. Is there some check that I am forgetting to do that is causing this error?
Lines where error is thrown:
int rightChildHeight = 0;
if (n->right != NULL)
rightChildHeight = n->right->getHeight();
getHeight():
int Node::getHeight()
{
// No kids => 2
if (!left && !right)
return 1;
// 1 kid => height of kid +1
else if (!left && right)
return right->getHeight() + 1;
else if (left && !right)
return left->getHeight() + 1;
// 2 kids => height of taller kid +1
else
return max(left->getHeight(), right->getHeight()) + 1;
}
Tree when the error occurs:
c++ c++11 binary-search-tree avl-tree
c++ c++11 binary-search-tree avl-tree
asked Nov 21 '18 at 6:24
Blake MorganBlake Morgan
4971520
asked Nov 21 '18 at 6:24
Blake MorganBlake Morgan
4971520
edited Nov 21 '18 at 6:35
Blake Morgan
asked Nov 21 '18 at 6:24
Blake MorganBlake Morgan
4971520
asked Nov 21 '18 at 6:24
Blake MorganBlake Morgan
4971520
asked Nov 21 '18 at 6:24
Blake MorganBlake Morgan
4971520
4971520
1
"the right branch isn't null" - Doesn't mean it holds a valid address either. You have bug somewhere in the tree's initialization/rotation/insertion/deletion. We can't find it for you psychically.
– StoryTeller
Nov 21 '18 at 6:37
1
Most likely,rightis a "dangling pointer" (i.e. it is non-null but it is not pointing at a valid object -- this typically happens if the object it was pointing at was deleted, but the pointer was not modified, so it remains pointing at the memory location where the object previously existed. Dereferencing a dangling pointer is an error and invokes undefined behavior)
– Jeremy Friesner
Nov 21 '18 at 6:37
Pointer n is not pointing to a valid address.
– tunglt
Nov 21 '18 at 6:44
@TungLeThanh But if I point to n->left I get no error. Does that mean n->right isn't pointing to a valid address?
– Blake Morgan
Nov 21 '18 at 6:45
@BlakeMorgan: if your program working memory space is trully at 0x5555555xxxxx, n is valid, sorry for that. I see Valgrin ou debug program fills out unused/uninitialized memory with 0x55 sometime.
– tunglt
Nov 21 '18 at 7:02
add a comment |
1
"the right branch isn't null" - Doesn't mean it holds a valid address either. You have bug somewhere in the tree's initialization/rotation/insertion/deletion. We can't find it for you psychically.
– StoryTeller
Nov 21 '18 at 6:37
1
Most likely,rightis a "dangling pointer" (i.e. it is non-null but it is not pointing at a valid object -- this typically happens if the object it was pointing at was deleted, but the pointer was not modified, so it remains pointing at the memory location where the object previously existed. Dereferencing a dangling pointer is an error and invokes undefined behavior)
– Jeremy Friesner
Nov 21 '18 at 6:37
Pointer n is not pointing to a valid address.
– tunglt
Nov 21 '18 at 6:44
@TungLeThanh But if I point to n->left I get no error. Does that mean n->right isn't pointing to a valid address?
– Blake Morgan
Nov 21 '18 at 6:45
@BlakeMorgan: if your program working memory space is trully at 0x5555555xxxxx, n is valid, sorry for that. I see Valgrin ou debug program fills out unused/uninitialized memory with 0x55 sometime.
– tunglt
Nov 21 '18 at 7:02
1
1
"the right branch isn't null" - Doesn't mean it holds a valid address either. You have bug somewhere in the tree's initialization/rotation/insertion/deletion. We can't find it for you psychically.
– StoryTeller
Nov 21 '18 at 6:37
"the right branch isn't null" - Doesn't mean it holds a valid address either. You have bug somewhere in the tree's initialization/rotation/insertion/deletion. We can't find it for you psychically.
– StoryTeller
Nov 21 '18 at 6:37
1
1
Most likely,
right is a "dangling pointer" (i.e. it is non-null but it is not pointing at a valid object -- this typically happens if the object it was pointing at was deleted, but the pointer was not modified, so it remains pointing at the memory location where the object previously existed. Dereferencing a dangling pointer is an error and invokes undefined behavior)– Jeremy Friesner
Nov 21 '18 at 6:37
Most likely,
right is a "dangling pointer" (i.e. it is non-null but it is not pointing at a valid object -- this typically happens if the object it was pointing at was deleted, but the pointer was not modified, so it remains pointing at the memory location where the object previously existed. Dereferencing a dangling pointer is an error and invokes undefined behavior)– Jeremy Friesner
Nov 21 '18 at 6:37
Pointer n is not pointing to a valid address.
– tunglt
Nov 21 '18 at 6:44
Pointer n is not pointing to a valid address.
– tunglt
Nov 21 '18 at 6:44
@TungLeThanh But if I point to n->left I get no error. Does that mean n->right isn't pointing to a valid address?
– Blake Morgan
Nov 21 '18 at 6:45
@TungLeThanh But if I point to n->left I get no error. Does that mean n->right isn't pointing to a valid address?
– Blake Morgan
Nov 21 '18 at 6:45
@BlakeMorgan: if your program working memory space is trully at 0x5555555xxxxx, n is valid, sorry for that. I see Valgrin ou debug program fills out unused/uninitialized memory with 0x55 sometime.
– tunglt
Nov 21 '18 at 7:02
@BlakeMorgan: if your program working memory space is trully at 0x5555555xxxxx, n is valid, sorry for that. I see Valgrin ou debug program fills out unused/uninitialized memory with 0x55 sometime.
– tunglt
Nov 21 '18 at 7:02
add a comment |
1 Answer
1
active
oldest
votes
Check if you are initiating the left and right pointers as nullptr. Probably you are not and it's getting random data from that memory location, making the pointer exist but it's not pointing to an object with a right property. Also if you delete any node before that show us the delete method and the insert method. There might be a problem in one of those functions.
Also you should try to be consistent with your code, first you check for nullability like this if (n->right != NULL) and after like this if (!left && !right) to be honest I prefer the second way, it's cleaner.
answered Nov 29 '18 at 15:58
Andre SilvaAndre Silva
1014
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53406331%2finvalid-read-even-though-object-exists%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Check if you are initiating the left and right pointers as nullptr. Probably you are not and it's getting random data from that memory location, making the pointer exist but it's not pointing to an object with a right property. Also if you delete any node before that show us the delete method and the insert method. There might be a problem in one of those functions.
Also you should try to be consistent with your code, first you check for nullability like this if (n->right != NULL) and after like this if (!left && !right) to be honest I prefer the second way, it's cleaner.
answered Nov 29 '18 at 15:58
Andre SilvaAndre Silva
1014
add a comment |
Check if you are initiating the left and right pointers as nullptr. Probably you are not and it's getting random data from that memory location, making the pointer exist but it's not pointing to an object with a right property. Also if you delete any node before that show us the delete method and the insert method. There might be a problem in one of those functions.
Also you should try to be consistent with your code, first you check for nullability like this if (n->right != NULL) and after like this if (!left && !right) to be honest I prefer the second way, it's cleaner.
answered Nov 29 '18 at 15:58
Andre SilvaAndre Silva
1014
add a comment |
Check if you are initiating the left and right pointers as nullptr. Probably you are not and it's getting random data from that memory location, making the pointer exist but it's not pointing to an object with a right property. Also if you delete any node before that show us the delete method and the insert method. There might be a problem in one of those functions.
Also you should try to be consistent with your code, first you check for nullability like this if (n->right != NULL) and after like this if (!left && !right) to be honest I prefer the second way, it's cleaner.
answered Nov 29 '18 at 15:58
Andre SilvaAndre Silva
1014
Check if you are initiating the left and right pointers as nullptr. Probably you are not and it's getting random data from that memory location, making the pointer exist but it's not pointing to an object with a right property. Also if you delete any node before that show us the delete method and the insert method. There might be a problem in one of those functions.
Also you should try to be consistent with your code, first you check for nullability like this if (n->right != NULL) and after like this if (!left && !right) to be honest I prefer the second way, it's cleaner.
answered Nov 29 '18 at 15:58
Andre SilvaAndre Silva
1014
edited Nov 29 '18 at 16:05
answered Nov 29 '18 at 15:58
Andre SilvaAndre Silva
1014
answered Nov 29 '18 at 15:58
Andre SilvaAndre Silva
1014
answered Nov 29 '18 at 15:58
Andre SilvaAndre Silva
1014
1014
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53406331%2finvalid-read-even-though-object-exists%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
"the right branch isn't null" - Doesn't mean it holds a valid address either. You have bug somewhere in the tree's initialization/rotation/insertion/deletion. We can't find it for you psychically.
– StoryTeller
Nov 21 '18 at 6:37
1
Most likely,
rightis a "dangling pointer" (i.e. it is non-null but it is not pointing at a valid object -- this typically happens if the object it was pointing at was deleted, but the pointer was not modified, so it remains pointing at the memory location where the object previously existed. Dereferencing a dangling pointer is an error and invokes undefined behavior)– Jeremy Friesner
Nov 21 '18 at 6:37
Pointer n is not pointing to a valid address.
– tunglt
Nov 21 '18 at 6:44
@TungLeThanh But if I point to n->left I get no error. Does that mean n->right isn't pointing to a valid address?
– Blake Morgan
Nov 21 '18 at 6:45
@BlakeMorgan: if your program working memory space is trully at 0x5555555xxxxx, n is valid, sorry for that. I see Valgrin ou debug program fills out unused/uninitialized memory with 0x55 sometime.
– tunglt
Nov 21 '18 at 7:02