Thursday, September 8, 2016

Free memory allocated in a Binary Search Tree

A lot of times I have seen codes which are not written keeping memory in mind. A great example is dynamically allocating memory for data structure demonstration on many coding websites. Though they are not meant to demonstrate efficient use of memory, it doesn't take much effort to write codes which actually free the memory. For example, if you have a look on this code, which finds the inorder predecessor and successor of a key in a Binary Search Tree, you see that the call to 'free_all()' frees the memory allocated to demonstrate the actual problem at hand. The function has just two lines of recursive calls along with free() and an exit criteria, hence it doesn't take much effort to write such functions.

A valgrind analysis of the code without the call to 'free_all()' throws the following:

gcc -Wall inorder_successor_predecessor.c && valgrind --leak-check=yes ./a.out
.
.
20 30 40 50 60 70 80
The BST is created, enter the key for inorder successor and inorder predecessor: 30
The predecessor is: 20
The successor is: 40
.
.
84 (12 direct, 72 indirect) bytes in 1 blocks are definitely lost in loss record 7 of 7
.
.
LEAK SUMMARY:
   definitely lost: 12 bytes in 1 blocks
   indirectly lost: 72 bytes in 6 blocks
     possibly lost: 0 bytes in 0 blocks
   still reachable: 0 bytes in 0 blocks
        suppressed: 0 bytes in 0 blocks

For counts of detected and suppressed errors, rerun with: -v
ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)


Whereas, a valgrind analysis of the code with the call to 'free_all()' throws the following:

HEAP SUMMARY:
    in use at exit: 0 bytes in 0 blocks
  total heap usage: 9 allocs, 9 frees, 108 bytes allocated

All heap blocks were freed -- no leaks are possible

For counts of detected and suppressed errors, rerun with: -v
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)


Therefore, sometimes few lines can actually save a lot of memory.