This may be a really simple question, but I could not find an answer any place on the internet. I am working on a linked list implementation in C, and am checking the memory usage and de-allocation with valgrind. I have created the following implementation which works properly. The only place that malloc is called is in the push_int_list function, which allows a user to create and insert a struct to any index in the linked list. Yes, I know that it is not a true index like an array, but i am using the same lingo to describe the location of a data point. Furthermore, the push_int_list function will will iterate from the head or tail of the linked list depending on where the struct is to be inserted.
The implementation shown below works correctly; however, when I check the memory allocation and de-allocation with valgrind, it shows that I execute 6 allocs, and 6 frees. As you can see, I only call the push_int_list function 5 times, and therefore should only be executing 5 allocs and 5 frees. If I change the number of push statements, the number of allocs and frees in valgrind is always one more than I actually execute. Why does valgrind always show one more malloc than I actually execute.
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
// --------------------------------------------------------------------------------
// Linked list Struct to containt data
typedef struct int_list
{
int data;
struct int_list *next;
struct int_list *previous;
} int_list;
// --------------------------------------------------------------------------------
// Struct to track linked list data
typedef struct
{
size_t active_length;
struct int_list *head;
struct int_list *tail;
} Int;
// --------------------------------------------------------------------------------
// Basic initialization of data tracking struct
void init_int_list(Int *list) {
list->active_length = 0;
list->head = NULL;
list->tail = NULL;
}
// --------------------------------------------------------------------------------
// Function that allows user to push a struct to any indice
int push_int_list(Int *list, int data, size_t index) {
if (index < 0 || index > list->active_length) {
fprintf(stderr, "INdex out of range\n");
return -1;
}
struct int_list *dat = malloc(sizeof(int_list));
if (!dat) {
fprintf(stderr, "malloc failed in file %s at line %d\n", __FILE__, __LINE__);
return -1;
}
if (list->active_length == 0) {
// populate struct
dat->data = data;
dat->previous = NULL;
dat->next = NULL;
// Update linked list tracking struct
list->head = dat;
list->tail = dat;
list->active_length += 1;
}
else if (index == 0 && list->active_length > 0) {
// populate struct
dat->previous = NULL;
dat->next = list->head;
dat->data = data;
// Update data in the struct occupying hte next index
(list->head)->previous = dat;
// Update linked list tracking struct
list->head = dat;
list->active_length += 1;
}
else if (list->active_length > 0 && index == list->active_length) {
// populate struct
dat->data = data;
dat->next = NULL;
dat->previous = list->tail;
// Update struct occupying previous index
(list->tail)->next = dat;
// Update linked list tracking struct
list->tail = dat;
list->active_length += 1;
}
// The next two if statements are mean to reduce the iteration time by half
// if the index to be inserted is between 0 and active_length
else if (index < list->active_length / 2) {
struct int_list *current = list->head;
struct int_list *previous = NULL;
for (size_t i = 0; i < index; i++) {
previous = current;
current = current->next;
}
// populate struct
dat->data = data;
dat->next = current;
dat->previous = previous;
// Update previous and next struct
previous->next = dat;
current->previous = dat;
// Update linked list tracking struct
list->active_length += 1;
}
else {
struct int_list *current = list->tail;
struct int_list *next = NULL;
for (size_t i = list->active_length; i > index; i--) {
next = current;
current = current->previous;
}
// Update struct
dat->data = data;
dat->next = next;
dat->previous = current;
// Update previous and next struct
next->previous = dat;
current->next = dat;
// Update linked list tracking struct
list->active_length += 1;
}
return 1;
}
void free_int_list(Int *list) {
if (list->active_length > 0) {
struct int_list *tmp = NULL;
struct int_list *head = list->head;
while (head->next != NULL) {
tmp = head;
head = tmp->next;
free(tmp);
}
free(head);
}
}
// Begin code
int main() {
Int list;
init_int_list(&list);
push_int_list(&list, 1, 0);
push_int_list(&list, 2, 1);
push_int_list(&list, 3, 2);
push_int_list(&list, 4, 3);
push_int_list(&list, 8, 0);
// Print linked list
struct int_list *current = list.head;
for (size_t i = 0; i < list.active_length; i++) {
printf("%d\n", current->data);
current = current->next;
}
free_int_list(&list);
return 0;
}
valgrind information shown below
==10074== Memcheck, a memory error detector
==10074== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==10074== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==10074== Command: ./test
==10074==
8
1
2
3
4
==10074==
==10074== HEAP SUMMARY:
==10074== in use at exit: 0 bytes in 0 blocks
==10074== total heap usage: 6 allocs, 6 frees, 1,144 bytes allocated
==10074==
==10074== All heap blocks were freed -- no leaks are possible
==10074==
==10074== For lists of detected and suppressed errors, rerun with: -s
==10074== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
I have wondered if it is tracking the instantiation of the Int struct as a malloc, but this is created in stack memory as a static allocation, so I cant see why this would be tracked as a malloc in valgrind!
