Memory leak while using linked lists and hash arrays

Question

Whatever I do I cant tell why this is leaking memory. I am releasing all dynamically created memory, yet it says I have 406 leaks. Any hints would be great. I have spent a week trying to figure it out and used crtdbg (doesn't show any lines) and VLD and still no luck. sorry for the long code:

---------- Block 742 at 0x00F06D50: 56 bytes ----------
Call Stack:
c:\users\main\desktop\lab3123.c (113): lab3.exe!createNode + 0xA bytes
c:\users\main\desktop\lab3123.c (152): lab3.exe!addToArr + 0x9 bytes
c:\users\main\desktop\lab3123.c (66): lab3.exe!main + 0x10 bytes
f:\dd\vctools\crt_bld\self_x86\crt\src\crtexe.c (555): lab3.exe!__tmainCRTStartup + 0x19 bytes
f:\dd\vctools\crt_bld\self_x86\crt\src\crtexe.c (371): lab3.exe!mainCRTStartup
0x76713677 (File and line number not available): kernel32.dll!BaseThreadInitThunk + 0x12 bytes
0x775B9F42 (File and line number not available): ntdll.dll!RtlInitializeExceptionChain + 0x63 bytes
0x775B9F15 (File and line number not available): ntdll.dll!RtlInitializeExceptionChain + 0x36 bytes
Data:
74 65 63 68    6E 6F 6C 6F    67 79 00 CD    CD CD CD CD     technolo gy......
CD CD CD CD    CD CD CD CD    CD CD CD CD    CD CD CD CD     ........ ........
CD CD CD CD    CD CD CD CD    CD CD CD CD    CD CD CD CD     ........ ........
CD CD CD CD    01 00 00 00                                   ........ ........


---------- Block 746 at 0x00F06E20: 56 bytes ----------
Call Stack:
c:\users\main\desktop\lab3123.c (113): lab3.exe!createNode + 0xA bytes
c:\users\main\desktop\lab3123.c (152): lab3.exe!addToArr + 0x9 bytes
c:\users\main\desktop\lab3123.c (66): lab3.exe!main + 0x10 bytes
f:\dd\vctools\crt_bld\self_x86\crt\src\crtexe.c (555): lab3.exe!__tmainCRTStartup + 0x19 bytes
f:\dd\vctools\crt_bld\self_x86\crt\src\crtexe.c (371): lab3.exe!mainCRTStartup
0x76713677 (File and line number not available): kernel32.dll!BaseThreadInitThunk + 0x12 bytes
0x775B9F42 (File and line number not available): ntdll.dll!RtlInitializeExceptionChain + 0x63 bytes
0x775B9F15 (File and line number not available): ntdll.dll!RtlInitializeExceptionChain + 0x36 bytes
Data:
68 75 6D 61    6E 69 74 79    00 CD CD CD    CD CD CD CD     humanity ........
CD CD CD CD    CD CD CD CD    CD CD CD CD    CD CD CD CD     ........ ........
CD CD CD CD    CD CD CD CD    CD CD CD CD    CD CD CD CD     ........ ........
CD CD CD CD    01 00 00 00                                   ........ ........


Visual Leak Detector detected 406 memory leaks (26480 bytes).
Largest number used: 43684 bytes.
Total allocations: 57944 bytes. 
Visual Leak Detector is now exiting.
Press any key to continue . . .

WORDNEW* createNode(char *str)
{
    WORDNEW* w;

    if(!(w = (WORDNEW*)malloc(sizeof(WORDNEW))))
        printf("Memory Allocation Error"),
            exit(100);
    strcpy(w->str, str);
    w->count = 1;
    return w;
}

//addToArr: adds a word to the hash array or linked list if there is a collision
void addToArr( char *str, HASH_ARR_ELEM hashArr[]){
    int homeAddress = 0;
    int addResult = 0;
    int probe = 0;
    HASH_ARR_ELEM *ph;
    WORDNEW *w;
    WORDNEW *rWord;
    rWord = NULL;
    homeAddress = hashFunct(str);
    ph = &hashArr[homeAddress];

    if(ph->wordPtr == NULL){
        if(!(ph->wordPtr = (WORDNEW*)malloc(sizeof(WORDNEW))))
            printf("Memory Allocation Error"),
                exit(100);
        strcpy(ph->wordPtr->str, str);
        ph->wordPtr->count = 1;
    }else if(ph->wordPtr != NULL && ph->headPtr == NULL){
        if(!(strcmp(ph->wordPtr->str, str)))
            ph->wordPtr->count++;
        else {
            ph->headPtr = createList(cmpWord);
            w = createNode(str);
            addNode(ph->headPtr,w,&probe);
        }
    }else {
        w = createNode(str);
        if(!(strcmp(ph->wordPtr->str, str))){
            ph->wordPtr->count++;
            free(w);
        }else if(retrieveNode(ph->headPtr,w,&rWord,&probe) == 1){
            rWord->count++;
            free(w);
        }else
            addNode(ph->headPtr,w,&probe);
    } //end else


} // end addToArr

hears a tip. Get your program small enough so that you have no memory leaks, all the way to an empty main if need be. Then gradually add back in stuff you think shouldn't leak. Observe what causes the leak. — Doug T., May 07 '12 at 01:07
Another tip would be to post less code. I don't know how many people compile every piece of code from SO questions, but I try to review it instead. And shorter code is much easier and faster to review. — Alexey Frunze, May 07 '12 at 01:18
Cole yes I release it when the word exists in the home address of the hashed array, but add it to the linklist if there is a collision. I thought in the code when I destroyList it should release all data dynamically allocated in the linked list. — TheMadKoder, May 07 '12 at 01:26
Doug I took your advice and it seems the leak is in the addToArr(newWord, hashArr); call, but i cant pin down where — TheMadKoder, May 07 '12 at 01:29
[That's *really* a lot of code to wade through.](http://meta.stackexchange.com/a/129787/175248) As a general debugging tip, I would advise the same thing that @DougT. did: make your program small enough such that it doesn't have a leak. Alternatively, you could use a memory profiler like Valgrind. — Makoto, May 07 '12 at 01:42
You might find http://stackoverflow.com/questions/413477/is-there-a-good-valgrind-substitute-for-windows helpful — IanNorton, May 07 '12 at 08:36
You have to many special cases. In reality, there are only two cases: either the word exists, or it does not. Your program should reflect that logic. — wildplasser, May 07 '12 at 14:59
The code is still missing the definitions for HASH_ARR_ELEM (which appears to contain *two* pointers) and WORDNEW. — wildplasser, May 07 '12 at 15:10
IanNorton I use Visual Leak Detector, but thanks for the link. Very helpful — TheMadKoder, May 07 '12 at 23:33
wildplasser I re-edit the posting and removed the definitions, but they are there in the program. — TheMadKoder, May 07 '12 at 23:33

William Morris · Accepted Answer · 2012-05-07T12:44:11.747

From above, I gather you believe the error to be in addToArr. Here are some suggestions for finding the fault.

Delete tempWord. Only the str field is used and that is a copy of the str call parameter. So just use str wherever you have tempWord->str.
Then, if you have control over the code for addNode, do the necessary allocation in there.
Otherwise wrap the call to addNode in a function that allocates a WORDNEW structure, copies str into it and sets count to 1, and then passes this into addNode.

You might also:

rewrite the if-the-else chain by factoring out the repeated sections.
factor out the repeated hashArr[homeAddress]. using a pointer ph->:

HASH_ARR_ELEM *ph = &hashArr[homeAddress];

turn on compiler warnings to warn you about ambiguous 'else' clauses. Specifically you have:

 if (!strcmp...)){
      ...
 }else
 {
     ...
     if(addResult != 0)
         if(addResult == -1){
             printf("Memory Overflow adding node\n"),
             exit(120);
         }else{
             etc...
         }

EDIT 2 (after refactoring addToArr)

The function looks a lot better now although there are still some possible points of improvement and some error checks have disappeared. But if you still have a leak, then it is not in addToArr. What or who is telling you that there are 406 leaks?

Improvements now include:

the (ph->wordPtr != NULL) is unnecessary as you know ph->wordPtr == NULL from the condition above above.
the following bit is common to both the main else clauses and can be done just once:
```
if (!strcmp(ph->wordPtr->str, str))
     ph->wordPtr->count++;
```
use perror on failure instead of printf
add spaces between call parameters and around else and if
remove the cast of malloc return
remove brackets and add space: if(!(strcmp(...))) becomes if (!strcmp(...))
cmpWord is undefined.

Ok so here is what I did based on your suggestion, but still same thing. Please take a look at the code above(re-edited the original posting) — TheMadKoder, May 07 '12 at 03:21
William thanks for the hints. I really do appreciate it. Visual Leak Detector is the one telling me I have 406 leaks. — TheMadKoder, May 07 '12 at 23:29
I wonder what Visual Leak Detector considers a leak. Does it give any clues? Does the number of 'leaks' correspond in any way to the number of entries in the hash array? — William Morris, May 08 '12 at 02:51
The leaks it shows looks like the information that is stored in the linked list. I use the function destroyList() to free memory and destroy the list but it still shows as a leak. I have re-edited the original post above to show the memory leak. — TheMadKoder, May 08 '12 at 04:51
Could the leaks be in addNode and retrieveNode? Do you have the source code for those functions? — William Morris, May 08 '12 at 14:31

Memory leak while using linked lists and hash arrays

1 Answers1