I'm writing a stack that's a linked list of data (void type). The data I am testing, is
struct my_data {
int val;
char name[60];
};
struct my_stack_node {
void *data;
struct my_stack_node *next;
};
struct my_stack {
int size;
struct my_stack_node *first;
};
the data used to be pushed, is initialized like this:
s1 = my_stack_init(sizeof(struct my_data));
if (!s1) {
puts("Error in my_stack_init()");
exit(1);
}
printf("\ns1 initialized, size of data: %lu\n", sizeof(struct my_data));
for (int i = 0; i < NODES; i++) {
data = malloc(sizeof(struct my_data)); // We must allocate static memory
data->val = i;
sprintf(data->name, "Value %d", i);
if (my_stack_push(s1, data)) {
puts("Error in my_stack_push()");
exit(1);
}
} //s1 is the stack we are using here
And pushing them by my_stack_push(s2, data); stack and the data as the arguments.
My push function is this one:
int my_stack_push(struct my_stack *stack, void *data){
if(stack == NULL && sizeof(data)> 0){
printf("Null Stack or data size error.\n");
//la pila debe existir
return -1;
}
else {
struct my_stack_node *nodeToPush = malloc(sizeof(struct my_stack_node));
nodeToPush -> data = data;
if(stack -> first == NULL) {
nodeToPush -> next = NULL;
stack -> first = nodeToPush;
}
else {
nodeToPush -> next = stack -> first;
stack -> first = nodeToPush;
}
}
return 0;
}
And my pop function is this one
void *my_stack_pop(struct my_stack *stack){
struct my_stack_node *node = stack->first;
if(stack->first == NULL){
return 0;
}
stack->first = node->next;
void *ret = node->data;
free(node);
return ret;
}
But in my main, when I pop them and try to compare them, I get a segmentation fault:
while ((data1 = my_stack_pop(s1))) {
data2 = my_stack_pop(fs1);
printf("Node of s1: (%d, %s)\t", data1->val, data1->name);
printf("Node of fs1: (%d, %s)\n", data2->val, data2->name);
if (!data2 || data1->val != data2->val || my_strcmp(data1->name, data2->name)) {
printf("Data in s1 and fs1 are not the same.\n (data1->val: %d <> data2->val: %d) o (data1->name: %s <> data2->name: "
"%s)\n",
data1->val, data2->val, data1->name, data2->name);
exit(1);
}
size1 = sizeof(*data1);
size2 = sizeof(*data2);
free(data1);
free(data2);
}
printf("size of data from s1: %d\t", size1);
printf("size of data from fs1: %d\n", size2);
(the 2 stacks are a copy of each other so what I inputed, should be the same I read). When I return the whole node in the pop function (not the data, but the whole my_stack_node), everything is right.. but wrong:
Comparing the data...
Node of s1: (0, Value 0) //good one Node of fs1: (0, Value 0) 8 8
Node of s1: (-1203217792, NV) //here it begins to go all wrong Node of fs1: (-1203217792, NV) 8 8
Node of s1: (-1203217792, NV) Node of fs1: (-1203217792, NV) 8 8
Node of s1: (-1203217792, NV) Node of fs1: (-1203217792, NV) 8 8
Node of s1: (0, ) Node of fs1: (0, ) double free or corruption (fasttop) Aborted (core dumped)
Size is the same as the data inputed, but the value and name are bad (even in the non copied stack), which is supposed to be:
New node in s1: (0, Value 0)
New node in s1: (1, Value 1)
New node in s1: (2, Value 2)
New node in s1: (3, Value 3)
New node in s1: (4, Value 4)
New node in s1: (5, Value 5)
New node in s1: (6, Value 6)
New node in s1: (7, Value 7)
New node in s1: (8, Value 8)
New node in s1: (9, Value 9)
But when I return (on my stack pop) the data itself like in the code, I get core dumped in the print of the test.(data that has 8 bytes of length, like the one input).
When I return the node (size = 64) it prints correctly wrong data, but when I return the data(size = 8 (like the one pushed)), it core faults.
If I push the same data and read the same data (as it shown when I return node because even when weird output, are the same), why do I get a core segmentation fault when I return the data that's supposed to print like the example above?
It looks that it only happens when I read the data2, and not data1. This is the code I use to write and read the file :
Write:
int my_stack_write(struct my_stack *stack, char *filename){
int count = 0;
struct my_stack_node *aux =malloc(sizeof(struct my_stack_node));
FILE *file = fopen(filename, "wb");
if(stack->first != NULL){
aux = stack->first;
count++;
while(aux->next != NULL){
printf("New node in s1: (%p)\n", aux->data);
fwrite(aux ,sizeof(struct my_stack_node), 1, file);
aux = aux->next;
count++;
}
printf("New node in s1: (%p)\n", aux->data);
fwrite(aux ,sizeof(struct my_stack_node), 1, file);
}
fclose(file);
return count;
}
Read:
struct my_stack *my_stack_read(char *filename){
struct my_stack *stackRead = my_stack_init(sizeof(struct my_stack_node));
struct my_stack_node *stackNode = malloc(sizeof(struct my_stack_node));
FILE *file = fopen(filename, "rb");
if(!file){
puts("Impossible obrir el fitxer");
return NULL;
}else{
while(fread(stackNode, sizeof(struct my_stack_node), 1, file)){
printf("New node in fs1: (%p)\n", stackNode->data);
stackNode = (struct my_stack_node*) stackNode;
my_stack_push(stackRead, stackNode->data);
}
fclose(file);
struct my_stack *InvertedStack = my_stack_init(sizeof(struct my_stack_node));
struct my_stack_node *aux = malloc(sizeof(struct my_stack_node));
while(my_stack_len(stackRead) !=0){
printf("Inverting the stack\n");
aux = my_stack_pop(stackRead);
my_stack_push(InvertedStack, aux);
}
return InvertedStack;
}
}
Thank you to anyone that helps.
MCVE of the program, so people can check the whole code and help better:
test2.c:
my_lib.c: https://codeshare.io/G7L8Ab
my_lib.h:
With this, you should have a broader view and an executable once compiled on what's happening to me.
Designing good, reliable and consistent API and libraries is a very hard job, especially in programming languages in which creating interfaces is somewhat harder then in object oriented languages.
I mean to be really nice, but the code you posted has memory leaks, unhandled errors, undefined behavior and bad design. The sizeof operator is misused. I can only guess you fail to understand how the memory allocation really works and the concept of a pointer and general void*
pointer.
Well, let's go.
So the reasons the code will seg fault is:
malloc
ated, but is subsequently free
d some lines later:for (int i = 0; i < NODES; i++) {
struct ... * data = malloc(sizeof(struct my_data));
my_stack_push(s1, data); // pushes the data pointer to the stack
void *data1 = my_stack_pop(s1); // pops the data pointer to the stack
...
assert(data1 == data); // data and data1 are the same
free(data1); // and data get's freed
// the memory behind both data and data1 is freed in this point
// thus the pointer s1.first->node->data is invalid
// as the code runs in loop, effectively all the data in this stack are invalid
}
main()
in the while loop. Both s1
and fs1
are obtained from calling my_stack_read
on the same file - thus logically they should contain the same values. As they store the same values, stored pointers to data are the same, thus freeing the pointer will also free and invalidate the second pointer in the second list. Double free is undefined behavior and I guess should result in something similar to segmentation fault on normal systems.while ((data1 = my_stack_pop(s1))) {
data2 = my_stack_pop(fs1);
...
assert(data1 == data2); // same pointers
free(data1);
free(data2); // double free corruption - seg fault
}
After fixing the errors the code will run and print "All tests passed", live version available here. Anyway below are some notes:
my_stack_init
:struct my_stack *my_stack_init(int size){
struct my_stack *stack = malloc(sizeof(struct my_stack_node) * size);
...
stack
now points to size
count of sizeof(struct my_stack_node)
bytes of memory. You need only a single my_stack_node structure. Also, sizeof
returns size_t
. A better version would be:
struct my_stack *my_stack_init(size_t size){
struct my_stack *stack = malloc(sizeof(struct my_stack_node));
...
my_stack_read
leaks memory:struct my_stack_node *aux = malloc(sizeof(struct my_stack_node));
...
aux = my_stack_pop(stackRead);
Indentation in the code you posted is a bit off. Try to keep one indentation style, I could advertise the good old' Linux kernel coding style but you can use anything but be consistent. Also your code could use some restructuring - limiting the scope of variables or like removing else
after return NULL
may increase readability.
sizeof
returns size_t
. The proper way to print size_t
is to use "%zu"
printf modifier. You can print pointers by casting to void*
and using "%p"
printf modifier.
Generally, this is really good work, but you need to understand that pointers point to data and are data themselves (as they have value). Currently your implementation stores only pointers to the data, thus client code is responsible for freeing the pointers. It's easy to trap yourself in confusion in such implementation. One could rewrite your stack implementation to allocate memory for the node and for the data itself, thus freeing the need for client code to handle the memory in any special manner. It could look like:
int my_stack_push(struct my_stack *stack, void *data) {
...
// allocate memory for new link in the list
struct my_stack_node *nodeToPush = malloc(sizeof(struct my_stack_node));
if (nodeToPush == NULL) abort();
// allocate memory for data itself
nodeToPush->data = malloc(stack->size);
if (nodeToPush->data == NULL) abort();
// memory copy the data into the pointer
memcpy(nodeToPush->data, data, stack->size);
..
In such implementation the stack is responsible in freeing the pointer and stores only copies of the data. Thus all the handles need to be rewritten to support that. The size of the data is available via stack->size
and initialized in my_stack_init
with the argument.
stackNode->next
is indeed not used in my_stack_read
, because it's value has been freed already before. I fail to see why do you even write the value of stackNode->next
to the file if you never use it.So we can store the data itself in the file:
int my_stack_write(struct my_stack *stack, char *filename){
...
node = stack->first;
void *data = node->data;
// write the data behind the node to the file
if (fwrite(data, stack->size, 1, file) != 1) {
return -100;
}
}
In a similar way we could rewrite my_stack_read
:
struct my_stack *my_stack_read(char *filename, size_t size) {
...
struct my_stack *stack = stack_init(size);
...
void *newdata = malloc(stack->size);
while (fread(newdata, stack->size, 1, file)) {
my_stack_push(stack, newdata);
}
free(newdata); // as in my proposed implementation my_stack stores copy
// of the memory behind the pointers, we can safely manage own memory
// by freeing the pointer
}