Is this small function an example of memory leakage?

This is a discussion on Is this small function an example of memory leakage? within the C Programming forums, part of the General Programming Boards category; Hello all A background to the function that is suspected of leaking memory. We pass to it a header to ...

  1. #1
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181

    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.

  2. #2
    &TH of undefined behavior Fordy's Avatar
    Join Date
    Aug 2001
    Posts
    5,789
    I deleted the other thread as it was a cross-post and against forum rules.

    If you have one question, make one post

  3. #3
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    Yeah sorry about that I realised that was in the book reviews forum

  4. #4
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  6. #6
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    Quote Originally Posted by claudiu View Post
    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.

  7. #7
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    I suggest you get it to compile first and worry about memory leaks later. Also I suggest indenting your space a bit better it is hard to read as it is. Space things out a bit. particularly in the SortedInsert() function.

    The process of building this is not barf three tons of code, get it to work, it's write 5 lines, compile, write another 5, compile, etc. After each function is done TEST IT!
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  8. #8
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    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.

  9. #9
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Not necessarily. If you maintain a pointer to the head of the old list you can free it later. The idea is that you must free everything you malloc before you lose all pointers to that part of memory. But when you decide to do it is entirely up to you and/or your requirements. You already seem to understand that pretty well though, so I am not sure what is bothering you.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  10. #10
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    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.

    Name:  Memory Diagram of possible leak.JPG
Views: 155
Size:  40.6 KB

    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.

  11. #11
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    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;
    }

  12. #12
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Note that you can also do the following:

    Before changing *headRef save it in some other pointer, and return that from your insert function. That way, you still know what it is in the caller.

    EDIT: This being if you don't necessarily want to delete it immediately.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  13. #13
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    Any other opinions on this?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How can detect memory leakage?
    By pronetin in forum C Programming
    Replies: 9
    Last Post: 10-07-2010, 07:37 AM
  2. Does this code has memory leakage?
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 04-08-2008, 09:13 PM
  3. Question about the Basics of Memory Leakage
    By Shamino in forum C++ Programming
    Replies: 12
    Last Post: 09-26-2005, 10:42 AM
  4. memory leakage?
    By xagiber in forum C++ Programming
    Replies: 1
    Last Post: 02-04-2002, 02:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21