I am working on a program that uses a linked list implemented as
typedef struct Node{
char* word;
int freq;
struct Node *next;
}Node;
typedef struct {
Node* head;
}LL;
and have functions
void add_Node(LL* list, char* word, int freq){
Node* newNode = (Node*)malloc(sizeof(Node));
if(newNode == NULL){
fprintf(stderr, "not able to create node\n");
return;
}
newNode->word = strdup(word);
if(newNode->word == NULL){
fprintf(stderr, "can't allocate mem for word\n");
free(newNode);
return;
}
newNode -> freq = freq;
newNode->next = NULL;
if(list->head == NULL){
list -> head = newNode;
}
else{
Node* current = list->head;
while(current->next != NULL){
current = current->next;
}
current->next = newNode;
}
//return newNode;
}
void addFreq(LL* list, char* word){
if(word == NULL){
return;
}
Node* current = list->head;
while(current != NULL){
if(strcmp(current->word, word) == 0){
current->freq++;
return;
}
current = current->next;
}
add_Node(list, word, 1);
}
void destroyLL(LL* list){
if(list == NULL){
return;
}
Node* current = list->head;
Node* next;
while (current != NULL){
next = current ->next;
free(current->word);
free(current);
current = next;
}
list->head = NULL;
free(list);
} //clears the linked list so it can be used again
Im my main function I have nested while loops that parse a file with a word on each line and store a word of specific length in the linked list, as such:
//assume all needed header files are included
int main(int argc, char *argv[]){
LL* list = (LL*)malloc(sizeof(LL));
//list->head = NULL;
//file meant to be parsed opened using fopen(/*name*/, "r"), nothing went wrong here
input = fopen(argv[1], "r"); //file for the inputs
char target[100];
int length;
int target_freq;
while(fgets(target, sizeof(target), input) != NULL){ //gets inputs from input file
if(sscanf(target, "%d %d", &length, &target_freq)==2){
char word[100];
while(fgets(word, sizeof(word), shake_txt) != NULL){ //parses the file of words
if(strlen(word) == length+1){
addFreq(list, word); //adds 1 to the freq field of the node, if it does not exist, add the node
}
}
sortLL(list);
printf("%s", findWord(list, target_freq));
}
destroyLL(list);
LL* list = (LL*)realloc(list,sizeof(LL));
}
//assume files are properly closed
}
After I run the program only the first iteration of the while loop runs, followed by the error message
Bard: malloc.c:2868: mremap_chunk: Assertion `((size + offset) & (GLRO (dl_pagesize) - 1)) == 0' failed.
Aborted (core dumped)
Anyone knows how to fix? Thanks in advance.
I tried replacing the destroyLL(list); with clearLL(list);, but I got the message
realloc(): invalid old size
Aborted (core dumped
here is clearLL
void clearLL(LL* list){
if(list == NULL || list -> head == NULL){
return;
}
Node* current = list->head;
Node* next;
while(current != NULL){
next = current->next;
free(current->word);
free(current);
current = next;
}
list->head = NULL;
}
Edit: After following Paddy's suggestions, my destroy function now looks like
void destroyLL(LL* list){
clearLL(list);
free(list);
}
and I have uncommented the list->head = NULL; line.
now my main function looks like
int main(int argc, char *argv[]){
LL* list = (LL*)malloc(sizeof(LL));
list->head = NULL;
//file meant to be parsed opened using fopen(/*name*/, "r"), nothing went wrong here
input = fopen(argv[1], "r"); //file for the inputs
char target[100];
int length;
int target_freq;
while(fgets(target, sizeof(target), input) != NULL){ //gets inputs from input file
if(sscanf(target, "%d %d", &length, &target_freq)==2){
char word[100];
while(fgets(word, sizeof(word), shake_txt) != NULL){ //parses the file of words
if(strlen(word) == length+1){
addFreq(list, word); //adds 1 to the freq field of the node, if it does not exist, add the node
}
}
sortLL(list);
printf("%s", findWord(list, target_freq));
}
destroyLL(list);
list = (LL*)malloc(sizeof(LL));
}
//assume files are properly closed
}
After compiling and running, I got the error Segmentation fault (core dumped) after the first iteration of the while loop running(it printed an output). Runninf valgrind with --leak-check=full gave me
==647== Memcheck, a memory error detector
==647== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==647== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==647== Command: ./Bard simple-input.txt
==647==
father
==647== Conditional jump or move depends on uninitialised value(s)
==647== at 0x108DED: sortLL (in /home/codio/workspace/Bard/Bard)
==647== by 0x109025: main (in /home/codio/workspace/Bard/Bard)
==647==
==647== Conditional jump or move depends on uninitialised value(s)
==647== at 0x108E55: findWord (in /home/codio/workspace/Bard/Bard)
==647== by 0x10903C: main (in /home/codio/workspace/Bard/Bard)
==647==
==647== Conditional jump or move depends on uninitialised value(s)
==647== at 0x108E7B: clearLL (in /home/codio/workspace/Bard/Bard)
==647== by 0x108EE7: destroyLL (in /home/codio/workspace/Bard/Bard)
==647== by 0x10905F: main (in /home/codio/workspace/Bard/Bard)
==647==
(null)(null)(null)(null)(null)==647==
==647== HEAP SUMMARY:
==647== in use at exit: 8 bytes in 1 blocks
==647== total heap usage: 9,706 allocs, 9,705 frees, 165,480 bytes allocated
==647==
==647== 8 bytes in 1 blocks are definitely lost in loss record 1 of 1
==647== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==647== by 0x109069: main (in /home/codio/workspace/Bard/Bard)
==647==
==647== LEAK SUMMARY:
==647== definitely lost: 8 bytes in 1 blocks
==647== indirectly lost: 0 bytes in 0 blocks
==647== possibly lost: 0 bytes in 0 blocks
==647== still reachable: 0 bytes in 0 blocks
==647== suppressed: 0 bytes in 0 blocks
==647==
==647== For counts of detected and suppressed errors, rerun with: -v
==647== Use --track-origins=yes to see where uninitialised values come from
==647== ERROR SUMMARY: 16 errors from 4 contexts (suppressed: 0 from 0)
Edit 2:
for those interested, here is findWord
char* findWord(LL* list, int freqRank){
Node* current = list->head;
int count = 0;
while(current != NULL){
if(count == freqRank){
return current->word;
}
count++;
current = current->next;
}
return NULL;
}
and sortLL, which uses merge sort:
Node* merge(Node* left, Node* right){
Node* result = NULL;
if(left == NULL){
return right;
}
if(right == NULL){
return left;
}
if(compareNode(left, right) <= 0){
result = left;
result->next = merge(left->next, right);
}
else{
result = right;
result->next = merge(left, right->next);
}
return result;
}
void mergeSort(Node** headRef){
Node* head = *headRef;
Node* right;
Node* left;
if (head == NULL || head->next == NULL){
return;
}
Node* slow = head;
Node* fast = head->next;
while(fast != NULL){
fast = fast->next;
if(fast != NULL){
slow = slow->next;
fast = fast->next;
}
}
left = head;
right = slow->next;
slow->next = NULL;
mergeSort(&left);
mergeSort(&right);
*headRef = merge(left, right);
}
void sortLL(LL* list){
if(list == NULL || list->head ==NULL || list->head->next ==NULL){
return;
}
mergeSort(&(list->head));
}
Edit 3: Following @Paddy's suggestion, not my main looks like:
//assume all needed header files are included
int main(int argc, char *argv[]){
LL* list = (LL*)malloc(sizeof(LL));
//list->head = NULL;
//file meant to be parsed opened using fopen(/*name*/, "r"), nothing went wrong here
input = fopen(argv[1], "r"); //file for the inputs
char target[100];
int length;
int target_freq;
while(fgets(target, sizeof(target), input) != NULL){ //gets inputs from input file
if(sscanf(target, "%d %d", &length, &target_freq)==2){
char word[100];
while(fgets(word, sizeof(word), shake_txt) != NULL){ //parses the file of words
if(strlen(word) == length+1){
addFreq(list, word); //adds 1 to the freq field of the node, if it does not exist, add the node
}
}
sortLL(list);
printf("%s", findWord(list, target_freq));
}
clearLL(list);
}
//assume files are properly closed
}
It outputs
father // <--the first output
(null)(null)(null)(null)(null) // <--the remaining outputs from the remaining inputs
Here is what I got from valgrind:
==686== Memcheck, a memory error detector
==686== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==686== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==686== Command: ./Bard simple-input.txt
==686==
father
(null)(null)(null)(null)(null)==686==
==686== HEAP SUMMARY:
==686== in use at exit: 8 bytes in 1 blocks
==686== total heap usage: 9,700 allocs, 9,699 frees, 165,432 bytes allocated
==686==
==686== 8 bytes in 1 blocks are definitely lost in loss record 1 of 1
==686== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==686== by 0x108F27: main (in /home/codio/workspace/Bard/Bard)
==686==
==686== LEAK SUMMARY:
==686== definitely lost: 8 bytes in 1 blocks
==686== indirectly lost: 0 bytes in 0 blocks
==686== possibly lost: 0 bytes in 0 blocks
==686== still reachable: 0 bytes in 0 blocks
==686== suppressed: 0 bytes in 0 blocks
==686==
==686== For counts of detected and suppressed errors, rerun with: -v
==686== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0
Edit 4: The reason why it was printing null was because for some reason nothing was added to the linked list on the second iteration and later. Anyone got any suggestions?
At the top of main, you allocate a new list but do not initialize it:
LL* list = (LL*)malloc(sizeof(LL));
//list->head = NULL;
For unknown reasons, you commented-out the initialization. As a result, the value of head is indeterminate and your program has undefined behavior.
To fix that, uncomment the offending line:
list->head = NULL;
Later, when you attempt to destroy your list and allocate a new one, you're trying to realloc a dangling pointer.
destroyLL(list);
LL* list = (LL*)realloc(list,sizeof(LL));
Except it's not a dangling pointer -- it's an uninitialized pointer because here a new local variable named list is being defined.
Changing this to malloc as you attempted still doesn't fix the issue because the list variable belonging to the larger scope of main is hidden by this local variable.
// Wrong:
destroyLL(list);
LL* list = (LL*)malloc(sizeof(LL)); // <-- Not the 'list' variable you think it is
The above allocates memory to the while-loop's 'list' variable, and then immediately leaks it when that variable goes out of scope. The original list variable remains unchanged.
This would technically work:
// Ugly:
destroyLL(list);
list = (LL*)malloc(sizeof(LL));
list->head = NULL;
But that's unnecessary, and it also assumes allocation succeeded. In fact, there's no need to free list and allocate another at all. Doing this would be considered bad practice.
You can instead just "clear" your list, by replacing these lines with:
clearLL(list);
Side-note 1: Since the clearLL function has a lot in common with destroyLL, you can re-use code by defining destroyLL as:
void destroyLL(LL* list){
clearLL(list);
free(list);
}
Side-note 2: You have all these functions to manipulate your list, but you require the list itself be created manually. This is not good practice. You should consider symmetry of an interface. You already have a destroyLL function, so you ought to have a matching createLL function:
LL* createLL(){
LL* list = malloc(sizeof(LL));
if (list) list->head = NULL;
return list;
}
Doing this makes for cleaner code, and also avoids mistakes (like forgetting to initialize head). It also allows for future changes to your implementation without requiring changes to all the code that uses it.