I've been working on a generic linked list in C that can accept multiple data types. When testing my linked list search function, I noticed a weird valgrind uninitialized error that I cannot figure out. For some reason, if I initialize the linked list by appending an integer first, then a double, and then search for any double (existing in the LL or not), I get the following error:
==64398== Conditional jump or move depends on uninitialised value(s) ==64398== at 0x1099C0: ll_contains (gll.c:301) ==64398== by 0x1092E8: contains_tests (gll_tests.c:17) ==64398== by 0x10934C: main (gll_tests.c:24) ==64398== ==64398== HEAP SUMMARY: ==64398== in use at exit: 0 bytes in 0 blocks ==64398== total heap usage: 6 allocs, 6 frees, 1,124 bytes allocated ==64398== ==64398== All heap blocks were freed -- no leaks are possible ==64398== ==64398== For lists of detected and suppressed errors, rerun with: -s ==64398== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
However, if I first add the double, and then the integer, and then search, everything is fine. Here is how the error is being produced (the order of lines 4 and 5):
struct LL* test_ll = ll_init();
int int_val = 69;
double double_val = 69.69;
ll_add_end(test_ll, &int_val, INT); /* This order causes the error! */
ll_add_end(test_ll, &double_val, DOUBLE);
assert(ll_contains(test_ll, &double_val, DOUBLE) == true);
struct LL* test_ll = ll_init();
int int_val = 69;
double double_val = 69.69;
ll_add_end(test_ll, &double_val, DOUBLE); /* This order causes no errors! */
ll_add_end(test_ll, &int_val, INT);
assert(ll_contains(test_ll, &double_val, DOUBLE) == true);
Here are the relevant functions:
This is how a Node is created:
struct Node* _create_node(void* data, enum ListType type)
{
int data_size;
struct Node* to_add = (struct Node*)malloc(sizeof(struct Node));
to_add->type = type;
to_add->next = NULL;
to_add->prev = NULL;
/* allocate memory for node's data */
switch (type)
{
case INT:
to_add->data = malloc(sizeof(int));
data_size = sizeof(int);
break;
case DOUBLE:
to_add->data = malloc(sizeof(double));
data_size = sizeof(double);
break;
case CHAR:
to_add->data = malloc(sizeof(char));
data_size = sizeof(char);
break;
case STRING:
data_size = strlen((const char*)data) + 1;
to_add->data = malloc(sizeof(char) * data_size);
break;
default:
return false;
}
/* copy data by byte into newly allocated memory */
int i;
for (i = 0; i < data_size; i++)
{
*(char*)(to_add->data + i) = *(char*)(data + i);
}
return to_add;
}
This is how a node is appended to a linked list:
bool ll_add_end(struct LL* list, void* data, enum ListType type)
{
struct Node* to_add = _create_node(data, type);
to_add->prev = list->tail;
if (list->tail)
{
list->tail->next = to_add;
}
list->tail = to_add;
list->head = (list->count == 0) ? to_add : list->head;
list->count++;
return true;
}
This is the faulty contains function. The error always happens at the indicated line:
bool ll_contains(struct LL* list, void* data, enum ListType type)
{
struct Node* current = list->head;
switch (type)
{
case INT:
while (current != NULL)
{
if (*((int*)current->data) == *((int*)data))
{
return true;
}
current = current->next;
}
break;
case DOUBLE:
while (current != NULL)
{
if (*((double*)current->data) == *((double*)data)) /* ERROR HERE */
{
return true;
}
current = current->next;
}
break;
case CHAR:
while (current != NULL)
{
if (*((char*)current->data) == *((char*)data))
{
return true;
}
current = current->next;
}
break;
case STRING:
while (current != NULL)
{
if (strcmp((char*)current->data, (char*)data) == 0)
{
return true;
}
current = current->next;
}
break;
default:
return false;
}
return false;
}
After testing, I have determined that the error is being caused from trying to access current->data, but ONLY in the case of DOUBLE, and then, ONLY if an integer was added to the linked list first. I have tried using calloc instead of malloc in the create_node function, but the error persists. I haven't been able to make any progress figuring out what is causing this behavior for a long time now, and therefore have decided to ask for help. Thanks in advance.
The problem is that you have a mixed type list but ll_contains forces comparisons of one fixed type.
So what is happening is that when you execute in this order
ll_add_end(test_ll, &double_val, DOUBLE); /* This order causes no errors! */
ll_add_end(test_ll, &int_val, INT);
assert(ll_contains(test_ll, &double_val, DOUBLE) == true);
the double value is first in the list, so it returns before comparing with the int.
When the order is reversed
ll_add_end(test_ll, &int_val, INT); /* This order causes the error! */
ll_add_end(test_ll, &double_val, DOUBLE);
assert(ll_contains(test_ll, &double_val, DOUBLE) == true);
you first have the int then the double. So you force a comparison between an int and a double
if (*((double*)current->data) == *((double*)data)) /* ERROR HERE */
but current->data is really a pointer to int. When you malloced it, you probably got back more than just 4 bytes - iirc it will be something like 24 bytes. Hence when you do this comparison bytes after the 4th one are uninitialized.
In your comparison function, you need to check the type before casting and checking the data.
while (current != NULL)
{
if (current->type) == type)
switch (type)
{
case INT:
if (*((int*)current->data) == *((int*)data))
{
return true;
}
break;
// etc.
}
current = current->next;
}