BST table implementation segfault (C)
-2
I've been trying to implement an associative array (int -> int) in C using binary search trees. However, my current implementation reliably produces a segfault, and I'm not quite sure why. I apologize if the problem is something very simple I just overlooked.
Code:
#include <stdlib.h>
#include <stdio.h>
struct tree {
int key;
int value;
struct tree *a;
struct tree *b;
};
int summon (struct tree *t, int key) {
if (t == NULL) {
fprintf(stderr, "%s", "Key not in tree");
exit(-1);
} else {
if (t -> key < key)
return summon(t -> a, key);
else if (t -> key > key)
return summon(t -> b, key);
else
return t -> value;
}
}
struct tree _make (int key, int value) {
struct tree ret;
ret.key = key;
ret.value = value;
ret.a = ret.b = NULL;
return ret;
}
void cast (struct tree *t, int key, int value) {
if (key == t -> key) {
t -> value = value;
} else if (key > t -> key) {
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
} else {
cast(t -> a, key, value);
}
} else {
if (t -> b == NULL) {
struct tree n = _make(key, value);
t -> b = &n;
} else {
cast(t -> b, key, value);
}
}
}
int main (int argc, char **argv) {
struct tree h = _make(5, 2);
cast(&h, 16, 43);
printf("%d", summon(&h, 16));
return 0;
}
I'm using gcc on Ubuntu; gdb is not being helpful.
c segmentation-fault associative-array
asked Nov 24 '18 at 20:56
user124user124
1097
|
show 2 more comments
-2
I've been trying to implement an associative array (int -> int) in C using binary search trees. However, my current implementation reliably produces a segfault, and I'm not quite sure why. I apologize if the problem is something very simple I just overlooked.
Code:
#include <stdlib.h>
#include <stdio.h>
struct tree {
int key;
int value;
struct tree *a;
struct tree *b;
};
int summon (struct tree *t, int key) {
if (t == NULL) {
fprintf(stderr, "%s", "Key not in tree");
exit(-1);
} else {
if (t -> key < key)
return summon(t -> a, key);
else if (t -> key > key)
return summon(t -> b, key);
else
return t -> value;
}
}
struct tree _make (int key, int value) {
struct tree ret;
ret.key = key;
ret.value = value;
ret.a = ret.b = NULL;
return ret;
}
void cast (struct tree *t, int key, int value) {
if (key == t -> key) {
t -> value = value;
} else if (key > t -> key) {
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
} else {
cast(t -> a, key, value);
}
} else {
if (t -> b == NULL) {
struct tree n = _make(key, value);
t -> b = &n;
} else {
cast(t -> b, key, value);
}
}
}
int main (int argc, char **argv) {
struct tree h = _make(5, 2);
cast(&h, 16, 43);
printf("%d", summon(&h, 16));
return 0;
}
I'm using gcc on Ubuntu; gdb is not being helpful.
c segmentation-fault associative-array
asked Nov 24 '18 at 20:56
user124user124
1097
3
in the function _make, you try to return a structure, which is hold on stack.
– Tom Kuschel
Nov 24 '18 at 21:03
@TomKuschel that's valid... it is incastwhere it goes wrong.
– Antti Haapala
Nov 25 '18 at 4:29
for ease of readability and understanding: 1) variable names, field names, parameter names should indicatecontentorusagenames likeaandbare meaningless even in the current context
– user3629249
Nov 25 '18 at 5:54
the function:cast()is recursive, but nothing in the passed parameters is being modified before the function calls itself. This is not a valid way to implement recursion
– user3629249
Nov 25 '18 at 5:58
regarding:int main (int argc, char **argv) {When the parameters tomain()are not used, then the signature:int main( void )should be used
– user3629249
Nov 25 '18 at 6:00
|
show 2 more comments
-2
-2
-2
I've been trying to implement an associative array (int -> int) in C using binary search trees. However, my current implementation reliably produces a segfault, and I'm not quite sure why. I apologize if the problem is something very simple I just overlooked.
Code:
#include <stdlib.h>
#include <stdio.h>
struct tree {
int key;
int value;
struct tree *a;
struct tree *b;
};
int summon (struct tree *t, int key) {
if (t == NULL) {
fprintf(stderr, "%s", "Key not in tree");
exit(-1);
} else {
if (t -> key < key)
return summon(t -> a, key);
else if (t -> key > key)
return summon(t -> b, key);
else
return t -> value;
}
}
struct tree _make (int key, int value) {
struct tree ret;
ret.key = key;
ret.value = value;
ret.a = ret.b = NULL;
return ret;
}
void cast (struct tree *t, int key, int value) {
if (key == t -> key) {
t -> value = value;
} else if (key > t -> key) {
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
} else {
cast(t -> a, key, value);
}
} else {
if (t -> b == NULL) {
struct tree n = _make(key, value);
t -> b = &n;
} else {
cast(t -> b, key, value);
}
}
}
int main (int argc, char **argv) {
struct tree h = _make(5, 2);
cast(&h, 16, 43);
printf("%d", summon(&h, 16));
return 0;
}
I'm using gcc on Ubuntu; gdb is not being helpful.
c segmentation-fault associative-array
asked Nov 24 '18 at 20:56
user124user124
1097
I've been trying to implement an associative array (int -> int) in C using binary search trees. However, my current implementation reliably produces a segfault, and I'm not quite sure why. I apologize if the problem is something very simple I just overlooked.
Code:
#include <stdlib.h>
#include <stdio.h>
struct tree {
int key;
int value;
struct tree *a;
struct tree *b;
};
int summon (struct tree *t, int key) {
if (t == NULL) {
fprintf(stderr, "%s", "Key not in tree");
exit(-1);
} else {
if (t -> key < key)
return summon(t -> a, key);
else if (t -> key > key)
return summon(t -> b, key);
else
return t -> value;
}
}
struct tree _make (int key, int value) {
struct tree ret;
ret.key = key;
ret.value = value;
ret.a = ret.b = NULL;
return ret;
}
void cast (struct tree *t, int key, int value) {
if (key == t -> key) {
t -> value = value;
} else if (key > t -> key) {
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
} else {
cast(t -> a, key, value);
}
} else {
if (t -> b == NULL) {
struct tree n = _make(key, value);
t -> b = &n;
} else {
cast(t -> b, key, value);
}
}
}
int main (int argc, char **argv) {
struct tree h = _make(5, 2);
cast(&h, 16, 43);
printf("%d", summon(&h, 16));
return 0;
}
I'm using gcc on Ubuntu; gdb is not being helpful.
c segmentation-fault associative-array
c segmentation-fault associative-array
asked Nov 24 '18 at 20:56
user124user124
1097
asked Nov 24 '18 at 20:56
user124user124
1097
asked Nov 24 '18 at 20:56
user124user124
1097
asked Nov 24 '18 at 20:56
user124user124
1097
asked Nov 24 '18 at 20:56
user124user124
1097
1097
3
in the function _make, you try to return a structure, which is hold on stack.
– Tom Kuschel
Nov 24 '18 at 21:03
@TomKuschel that's valid... it is incastwhere it goes wrong.
– Antti Haapala
Nov 25 '18 at 4:29
for ease of readability and understanding: 1) variable names, field names, parameter names should indicatecontentorusagenames likeaandbare meaningless even in the current context
– user3629249
Nov 25 '18 at 5:54
the function:cast()is recursive, but nothing in the passed parameters is being modified before the function calls itself. This is not a valid way to implement recursion
– user3629249
Nov 25 '18 at 5:58
regarding:int main (int argc, char **argv) {When the parameters tomain()are not used, then the signature:int main( void )should be used
– user3629249
Nov 25 '18 at 6:00
|
show 2 more comments
3
in the function _make, you try to return a structure, which is hold on stack.
– Tom Kuschel
Nov 24 '18 at 21:03
@TomKuschel that's valid... it is incastwhere it goes wrong.
– Antti Haapala
Nov 25 '18 at 4:29
for ease of readability and understanding: 1) variable names, field names, parameter names should indicatecontentorusagenames likeaandbare meaningless even in the current context
– user3629249
Nov 25 '18 at 5:54
the function:cast()is recursive, but nothing in the passed parameters is being modified before the function calls itself. This is not a valid way to implement recursion
– user3629249
Nov 25 '18 at 5:58
regarding:int main (int argc, char **argv) {When the parameters tomain()are not used, then the signature:int main( void )should be used
– user3629249
Nov 25 '18 at 6:00
3
3
in the function _make, you try to return a structure, which is hold on stack.
– Tom Kuschel
Nov 24 '18 at 21:03
in the function _make, you try to return a structure, which is hold on stack.
– Tom Kuschel
Nov 24 '18 at 21:03
@TomKuschel that's valid... it is in
cast where it goes wrong.– Antti Haapala
Nov 25 '18 at 4:29
@TomKuschel that's valid... it is in
cast where it goes wrong.– Antti Haapala
Nov 25 '18 at 4:29
for ease of readability and understanding: 1) variable names, field names, parameter names should indicate
content or usage names like a and b are meaningless even in the current context– user3629249
Nov 25 '18 at 5:54
for ease of readability and understanding: 1) variable names, field names, parameter names should indicate
content or usage names like a and b are meaningless even in the current context– user3629249
Nov 25 '18 at 5:54
the function:
cast() is recursive, but nothing in the passed parameters is being modified before the function calls itself. This is not a valid way to implement recursion– user3629249
Nov 25 '18 at 5:58
the function:
cast() is recursive, but nothing in the passed parameters is being modified before the function calls itself. This is not a valid way to implement recursion– user3629249
Nov 25 '18 at 5:58
regarding:
int main (int argc, char **argv) { When the parameters to main() are not used, then the signature: int main( void ) should be used– user3629249
Nov 25 '18 at 6:00
regarding:
int main (int argc, char **argv) { When the parameters to main() are not used, then the signature: int main( void ) should be used– user3629249
Nov 25 '18 at 6:00
|
show 2 more comments
1 Answer
1
active
oldest
votes
0
In this, for example,
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
}
you're storing a pointer to a variable with automatic storage duration into t->a. However the lifetime of n ends at the }, and t->a becomes a dangling pointer; use of such pointer in any context causes undefined behaviour.
You need to use dynamic memory allocation (malloc et al) for this task.
answered Nov 25 '18 at 4:45
Antti HaapalaAntti Haapala
82.1k16153195
Thank you! The dangling pointer makes sense (especially considering the undefined behavior - the code occasionally ran completely fine). Usingcallocinstead of the dangling pointer, I was able to make the code work.
– user124
Nov 25 '18 at 14:12
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
});
}
});
draft saved
draft discarded
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%2f53462290%2fbst-table-implementation-segfault-c%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
0
In this, for example,
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
}
you're storing a pointer to a variable with automatic storage duration into t->a. However the lifetime of n ends at the }, and t->a becomes a dangling pointer; use of such pointer in any context causes undefined behaviour.
You need to use dynamic memory allocation (malloc et al) for this task.
answered Nov 25 '18 at 4:45
Antti HaapalaAntti Haapala
82.1k16153195
Thank you! The dangling pointer makes sense (especially considering the undefined behavior - the code occasionally ran completely fine). Usingcallocinstead of the dangling pointer, I was able to make the code work.
– user124
Nov 25 '18 at 14:12
add a comment |
0
In this, for example,
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
}
you're storing a pointer to a variable with automatic storage duration into t->a. However the lifetime of n ends at the }, and t->a becomes a dangling pointer; use of such pointer in any context causes undefined behaviour.
You need to use dynamic memory allocation (malloc et al) for this task.
answered Nov 25 '18 at 4:45
Antti HaapalaAntti Haapala
82.1k16153195
Thank you! The dangling pointer makes sense (especially considering the undefined behavior - the code occasionally ran completely fine). Usingcallocinstead of the dangling pointer, I was able to make the code work.
– user124
Nov 25 '18 at 14:12
add a comment |
0
0
0
In this, for example,
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
}
you're storing a pointer to a variable with automatic storage duration into t->a. However the lifetime of n ends at the }, and t->a becomes a dangling pointer; use of such pointer in any context causes undefined behaviour.
You need to use dynamic memory allocation (malloc et al) for this task.
answered Nov 25 '18 at 4:45
Antti HaapalaAntti Haapala
82.1k16153195
In this, for example,
if (t -> a == NULL) {
struct tree n = _make(key, value);
t -> a = &n;
}
you're storing a pointer to a variable with automatic storage duration into t->a. However the lifetime of n ends at the }, and t->a becomes a dangling pointer; use of such pointer in any context causes undefined behaviour.
You need to use dynamic memory allocation (malloc et al) for this task.
answered Nov 25 '18 at 4:45
Antti HaapalaAntti Haapala
82.1k16153195
answered Nov 25 '18 at 4:45
Antti HaapalaAntti Haapala
82.1k16153195
answered Nov 25 '18 at 4:45
Antti HaapalaAntti Haapala
82.1k16153195
answered Nov 25 '18 at 4:45
Antti HaapalaAntti Haapala
82.1k16153195
82.1k16153195
Thank you! The dangling pointer makes sense (especially considering the undefined behavior - the code occasionally ran completely fine). Usingcallocinstead of the dangling pointer, I was able to make the code work.
– user124
Nov 25 '18 at 14:12
add a comment |
Thank you! The dangling pointer makes sense (especially considering the undefined behavior - the code occasionally ran completely fine). Usingcallocinstead of the dangling pointer, I was able to make the code work.
– user124
Nov 25 '18 at 14:12
Thank you! The dangling pointer makes sense (especially considering the undefined behavior - the code occasionally ran completely fine). Using
calloc instead of the dangling pointer, I was able to make the code work.– user124
Nov 25 '18 at 14:12
Thank you! The dangling pointer makes sense (especially considering the undefined behavior - the code occasionally ran completely fine). Using
calloc instead of the dangling pointer, I was able to make the code work.– user124
Nov 25 '18 at 14:12
add a comment |
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f53462290%2fbst-table-implementation-segfault-c%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
3
in the function _make, you try to return a structure, which is hold on stack.
– Tom Kuschel
Nov 24 '18 at 21:03
@TomKuschel that's valid... it is in
castwhere it goes wrong.– Antti Haapala
Nov 25 '18 at 4:29
for ease of readability and understanding: 1) variable names, field names, parameter names should indicate
contentorusagenames likeaandbare meaningless even in the current context– user3629249
Nov 25 '18 at 5:54
the function:
cast()is recursive, but nothing in the passed parameters is being modified before the function calls itself. This is not a valid way to implement recursion– user3629249
Nov 25 '18 at 5:58
regarding:
int main (int argc, char **argv) {When the parameters tomain()are not used, then the signature:int main( void )should be used– user3629249
Nov 25 '18 at 6:00