Using free() on a pointer within a struct frees memory for the entire struct

Question

I have two structs within my program. The first one, huffchar is below, and just shows the general structure (mostly irrelevant to the question), but the second one, huffcoder is the one that I'm having an issue with:

struct huffchar {   
    int freq;   
    int is_compound;   
    int seqno;   
    union {
        struct {
        struct huffchar * left;
        struct huffchar * right;
        } compound;
        unsigned char c;   
    } u; 
};


struct huffcoder {   
    int freqs[NUM_CHARS];
    int code_lengths[NUM_CHARS];
    unsigned long long codes[NUM_CHARS];
    struct huffchar * tree;
    int sizeOfTree; 
};

When I initialize a huffcoder in my program, I malloc ourHuffCoder the size of a huffcoder, and then malloc memory for X many elements to the struct huffchar * tree:

struct huffcoder * ourHuffChar = malloc(sizeof(struct huffcoder));

ourHuffChar -> tree = malloc(sizeof(struct huffchar)*NUM_CHARS);

However, I will need to make this tree larger at a later point, and do not know how many elements will be on this tree at the end. In other words, every time I add an element, I will create a new tree with realloc() that is one element larger, then set the pointer for tree within the huffcoder to this new updatedTree.

The follow lines of code are intended to achieve this:

    struct huffchar * updatedTree = realloc(ourHuffCoder -> tree, (ourHuffCoder->sizeOfTree+1)*sizeof(struct huffchar));
    free(ourHuffCoder -> tree);
    ourHuffCoder -> tree = updatedTree;

Note that I use the line free(ourHuffCoder -> tree) to free the memory that has been previously allocated to the tree, before updating the tree pointer to updatedTree. However, when I reach the free(ourHuffCoder -> tree) line, memory allocated to the entirety of the HuffCoder pointer ourHuffCoder is freed instead of just the memory allocated to the tree.

Here is my variables window before running the free(ourHuffCoder->tree) line:

And here is after running the free(ourHuffCoder->tree) line:

I have also tried creating an entirely new pointer huffchar * ourTree = ourHuffCoder -> tree and use this variable for the free() method instead, but I get the same result.

Just to test my code, I modified the above code to remove the free() line,

    struct huffchar * updatedTree = realloc(ourHuffCoder -> tree, (ourHuffCoder->sizeOfTree+1)*sizeof(struct huffchar));
    ourHuffCoder -> tree = updatedTree;

This is obviously not what I should be doing because I will run out of memory quickly, but I wanted to see if the pointer to tree within huffcoder would be updated to point to updatedTree, which is has:

Before ourHuffCoder -> tree = updatedTree;

After ourHuffCoder -> tree = updatedTree;

My question is, why is the memory allocated to the entirety of the huffcoder struct being freed, instead of just the memory to the tree? How do I solve this? Is there a better way of increasing the memory allocated to the tree?

Answer 1

The mistake I see is that realloc is already a combination of malloc and free. The free call here is unnecessary and wrong:

struct huffchar * updatedTree = realloc(ourHuffCoder -> tree, (ourHuffCoder->sizeOfTree+1)*sizeof(struct huffchar));
free(ourHuffCoder -> tree);
ourHuffCoder -> tree = updatedTree;

That is to say, when we call realloc(ptr), ptr is deallocated and a new pointer is returned. The allocator can sometimes optimize the process by resizing the old object in place.

There is no need to free ptr, and we must not do so, in fact.

If we didn't care about the optimization, we could almost write realloc like this:

#include <string.h>
#include <stdlib.h>
#define min(a, b) ((a) < (b) : (a) : (b))

void *our_realloc(void *oldptr, size_t newsize)
{
   if (newsize == 0) {
      free(oldptr);
      return 0;
   } else {
      void *newptr = malloc(newsize);
      if (oldptr) {
         size_t oldsize = __obtain_old_size_in_nonportable_way(oldptr);
         memcpy(newptr, oldptr, min(oldsize, newsize));
         free(oldptr); // !!!!
      }
      return newptr;
   }
}

Even in cases when realloc returns the "same" pointer, the program cannot easily tell. The old pointer has become invalid, so any use of it is undefined behavior:

newptr = realloc(oldptr, size);

if (newptr == oldptr) {  // did it really move?

The use of oldptr here is technically undefined behavior. We never hold the two pointers simultaneously; we have traded one for the other and the transaction took place inside the realloc blackbox.

We can capture a printed image:

char oldptr_txt[64], newptr_txt[64];
snprintf(oldptr_txt, sizeof oldptr_txt, "%p", (void *) oldptr);
newptr = realloc(oldptr, size);
snprintf(newptr_txt, sizeof newptr_txt, "%p", (void *) newptr);

if (strcmp(oldptr_txt, newptr_txt) == 0) {
  // almost certainly stayed in place
} else {
  // almost certainly moved
}