0

I'm starting to learn C coming from a Java background. My first toy program is a binary search tree. I have implemented add, find, min, max, depthfirst and delete. My question stems from the delete method.

In order to debug I print the tree ( depth first ) to the console, then I remove nodes using delete and print the bst again. If it were Java I'd call it a day and move on but I'm worried that somewhere I forgot to free some memory ( or thought I did but free'd the wrong pointer or something ).

As a novice C programmer what is the best way to detect these sorts of memory leaks? I'm using CLion as my IDE if there are tools I should be using in the IDE but I would prefer some tricks that aren't IDE dependant.

gsamaras
  • 71,951
  • 46
  • 188
  • 305
LiamRyan
  • 1,892
  • 4
  • 32
  • 61
  • 5
    You could try using valgrind. – EOF Nov 22 '16 at 22:03
  • 1
    Simple: Any time you call `malloc` (or a related function), prove that every execution path from there on ends in a `free`. – Kerrek SB Nov 22 '16 at 22:05
  • You could use valgrind and if you want more precision you have the option --leak-check=full. – Thomas Blanquet Nov 22 '16 at 22:05
  • @KerrekSB Thanks but if I could do that I'd be most of the way to mastering C :) My worry is freeing the wrong pointer or maybe freeing a double pointer without de-referencing it or – LiamRyan Nov 22 '16 at 22:07
  • @KerrekSB, proving that all code paths do free is not 'Simple'. If it were then there would be no leaks. For a start compile/ link toolchains would do it by default – pm100 Nov 22 '16 at 22:10
  • @pm100: Whether and how simple it is depends largely on how you design your code, doesn't it? Knowing that you *need* to be able to reason about resources may guide your design. – Kerrek SB Nov 22 '16 at 22:17
  • @pm100: To further the point: suppose Valgrind tells you that you have a leak, which comes from things put into a collection. Now you insert `free` calls, but it turns out that some of the pointers actually point to static or automatic variables, and boom. Sometimes finding a leak after a poor design has been built is too late to save your program, and you need to redesign. So it's worth keeping the principles in mind right from the start. – Kerrek SB Nov 22 '16 at 22:19
  • It's probably useful to think of allocations in terms of, who owns them. Owner must never lose a pointer to allocated memory, unless it either frees it, or passes ownership to something else. Document this clearly with comments, like "This function removes item from the tree, and returns pointer to it. Caller gets ownership of the allocation." And only owner is allowed to `free` an allocation. – hyde Nov 22 '16 at 22:35

1 Answers1

3

I understand your concern, I remember an undergrad project that executed just fine in my home desktop, but was producing a memory leak in the TA's laptop. I couldn't even imagine at that point...

So after that I started to use Valgrind to check for memory leaks. If Valgrind said that we were cool, I would say we're cool and call it a day!

Pro tip: How do I use valgrind to find memory leaks?

Community
  • 1
  • 1
gsamaras
  • 71,951
  • 46
  • 188
  • 305