Thread: Is this small function an example of memory leakage?

Hello all

A background to the function that is suspected of leaking memory. We pass to it a header to a linearly linked list which is unordered and we want to order it from decreasing to increasing order. The actual insertion sorting of the list is done by "SortedInsert" of which we dont have to go into detail for the purpose of the question.

Code:

void InsertSort(struct node** headRef) {
struct node* result = NULL; // build the answer here
struct node* current = *headRef; // iterate over the original list
struct node* next;
while (current! = NULL) {
next = current->next; // tricky - note the next pointer before we change it
SortedInsert(&result, current);
current = next;
}
*headRef = result;
}

Basically the function creates an empty list and copies to it each node one by one from the old list (which is the argument in the function). Don't get confused by the ** in the argument. Its there because headRef is a reference pointer i.e. it points to a head pointer from the caller function so that when we change the linked list in this function, it chages the callers list aswell and not merely its copy.

The crux is the very last statement: headRef is now told to point to the new linked list. When we do this, we lose reference to the head of the old list and thus, without freeing it, it will "linger" in memory without a reference to its head. I suspect that its bad practice, rather, I would add a function DeleteList (*headRef) THEN add the statement *headRef = result; The delete list would typically iterate down the list freeing each node as it passes through.

Take in mind that the linked list is in the heap not the stack and so after this functions life, the memory will still exist unreferenced.

Yeah sorry about that I realised that was in the book reviews forum

Originally Posted by claudiu

You are not visibly allocating memory in that function so it's pretty hard to tell. Post your entire code. Alternatively install Valgrind and run your program using ./valgrind myprog. It will tell you if you are leaking anywhere.

Not that I think it would help understanding the problem but heres the entire code:

Code:

# include <stdio.h>
# include <assert.h>
# include <stdlib.h>

struct node {
int data;
struct node* next;
};

void PrintLinkedList (struct node* head) {
 if (head == NULL) {
printf("Null List");
return;
}
while (head -> next != NULL) {
  printf("%d ", head -> data);
  head = head -> next;
 }
  printf("%d", head -> data);
  return;
}

struct node* BuildOneTwoThree() {
struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;
head = malloc (sizeof(struct node));
second = malloc (sizeof(struct node));
third = malloc (sizeof(struct node));
head -> data = 3;
head -> next = second;
second -> data = 2;
second -> next = third;
third -> data = 1;
third -> next = NULL;
return (head);
}

void Push (struct node** headref, int data) {
struct node* first = malloc (sizeof(struct node));
first -> data = data;
first -> next = *headref;
*headref = first;
}

void DeleteList (struct node** headRef) {
struct node* current  = *headRef;
struct node* ahead;
while (current != NULL) {
	ahead = current -> next;
	free (current);
	current = ahead;
        }
*headRef = NULL;
}

void SortedInsert (struct node** headRef, struct node* 

newNode) {
struct node* current = *headRef;
if(*headRef == NULL || newNode -> data <= (*headRef) -> 

data) {
newNode -> next = *headRef;
*headRef = newNode;
return;
}
while (current -> next != NULL && newNode -> data > 

(current -> next) -> data)
current = current -> next;
newNode -> next = current -> next;              //WATCH THE ORDER HERE!
current -> next = newNode;                          

//WATCH THE ORDER HERE!
return;
}

void InsertSort (struct node** headRef) {
struct node* newlist = NULL;
struct node* current = *headRef;
while (current != NULL) {
 SortedInsert (&newlist, current);
 current = current -> next;
 }
SortedInsert (newlist, current);
DeleteList (*headRef);
*headRef = newlist;
return;
}

int main() {
struct node* head = BuildOneTwoThree();
SortedInsert(&head,anode);
PrintLinkedList (head);
getchar();
}

I have not run the entire consolidated code yet so there may be errors.

Yes I understand all of that 100%, the code does work individually but I didnt compile the final draft. But the question still remains: Does the function exercise a bad practice i.e. transferring info to a new list without deleting freeing the old nodes. Not that it has anything to do with the question at hand but I will compile this thing when I get home to a compiler. Watch this space.

I get you, and its exactly the fear of "before you lose all pointers to that part of memory" that I believe the function does for in the last step we make it point to a new linked list without freeing the old list. I made a memory diagram showing what I think the function does wrong.



So to answer your question on whats bothering me. The code extract is from a reputable tutorial from an author who warns against the very leakage that I suspect was overlooked. There may be "something im not seeing" as im not an expert on memory allocation. I think im overlooking the fact that the old list somehow automatically de-allocates after the function life ends which I cant see happening as it exists [sic!] in the heap.

Also your iteration over the list is unnecessarily mental. You don't need both current and next if you write the loop properly. You are not changing either of them (presumably) in SortedInsert.

I think youre right, I think the reason for next was to make sure the iteration carries on right up until NULL is encountered. I re did the code to ignore the next variable AND I included the delete list function so that my suspected leak doesnt occur.

Code:

void InsertSort (struct node** headRef) {
struct node* newlist = NULL;
struct node* current = *headRef;
while (current != NULL) {
SortedInsert (&newlist, current);
current = current -> next;
}
SortedInsert (&newlist, current);
DeleteList (*headRef);
*headRef = newlist;
return;
}

Any other opinions on this?