Freeing an array of dynamically allocated pointers

Question

I'm studying for an exam, and I have a question about a sample question that I was provided:

Implement the function free_array with prototype void free_array(void *a[], int length). The purpose of the function is to free the dynamically allocated memory associated with each array element in the first parameter passed to the function. The function must handle the scenario in which two or more array entries point to the same memory (only one free can be applied to a single memory location).

My first thought was to set each freed index to NULL because calling free() on NULL is harmless. So I did the following:

void free_array(void *a[], int length) { 
   int i;
   for (i = 0; i < length; i++) {
      free(a[i]);
      a[i] = NULL;
   }
}

The solution provided is pretty different than mine, and I don't fully understand what they're doing. Here's what I'm given as the answer:

void free_array(void *a[], int length) { 
    int i, j;
    for (i = 0; i < length; i++) {
        if (a[i] != NULL) {
            free(a[i]);
            for (j = i + 1; j < length; j++) {
                if (a[j] == a[i]) {
                    a[j] = NULL;
                }
            }
        }
    }
}

I'm really confused about what's going on here. It seems like they're freeing each entry and marking the ones with the same content to NULL. However, I thought that we aren't supposed to re-access freed memory? Also, would my way still work?

It looks like the array could have multiple entries pointing to the same memory. It's an error to free the same memory multiple times, so for each entry, you have to check to see if other entries point to the same block, and clear those out too. — Thomas Jager, Jul 22 '19 at 19:29
Your way doesn't work at all. It doesn't even attempt to handle the case of multiple pointers to the same location. The provided solution has undefined behavior, but not because it's accessing freed memory. — melpomene, Jul 22 '19 at 19:30
I thought that if I were to set a[i] to NULL, every pointer pointing to the same address as a[i] will also equal NULL. Is this incorrect? — , Jul 22 '19 at 19:34
@redblacktrees Yes, that's incorrect. Setting one variable doesn't affect other variables, no matter if they're pointers. — melpomene, Jul 22 '19 at 19:35
Okay. Also, is it valid to access the a[i], even after it's been freed? (they are doing the comparison a[i] == a[j], after the free() call. Or, would it be better to intialize a temp variable with the contents of a[i] prior to freeing a[i]? — , Jul 22 '19 at 19:36
@redblacktrees It is **not** valid. The call to `free` should happen *after* the inner loop. — dbush, Jul 22 '19 at 19:38
That's not valid and is the reason why their solution has undefined behavior. However, the code is not accessing freed memory. It's just that after `free(x)` the value `x` becomes indeterminate, so you're not allowed to even inspect it. — melpomene, Jul 22 '19 at 19:38
Would their function still work if there are two entries of, say, "5," but they are stored in different locations in memory? It seems to me that it wouldn't. We'd mark both 5's as NULL, and we'd only call "free" on the first one. EDIT: Never mind - I think it will work because a[i] == a[j] is comparing memory addresses. — , Jul 22 '19 at 19:41
`a[i]` and `a[j]` are memory locations (pointers). The code doesn't look at the values stored in memory, it's just comparing memory addresses. — melpomene, Jul 22 '19 at 19:43
"if I were to set a[i] to NULL, every pointer pointing to the same address as a[i] will also equal NULL.". By the same vein, if you remove a contact from your phone, all contacts of that person get immediately removed from every other phone in the universe. — n. m. could be an AI, Jul 22 '19 at 19:48
@redblacktrees The reason you can't do the comparison after calling `free()` is because of [**6.2.4 Storage durations of objects**, paragraph 2 of the C standard:](https://port70.net/~nsz/c/c11/n1570.html#6.2.4p2): "The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime." [POSIX also states](https://pubs.opengroup.org/onlinepubs/9699919799/functions/free.html#tag_16_165_03): "Any use of a pointer that refers to freed space results in undefined behavior." That rule is abused often. — Andrew Henle, Jul 22 '19 at 19:50
(cont) Most widely-used systems today just leave the old value in the pointer, and don't implement pointer constructs such as [trap values](https://stackoverflow.com/questions/6725809/trap-representation). — Andrew Henle, Jul 22 '19 at 19:52
In the given answer, I believe that `free(a[j]);` should be called instead of `a[j] = NULL;`, and `free(a[i]);` should be moved to directly after the second for loop. — ejderuby, Jul 22 '19 at 20:16

score 2 · Answer 1 · answered Jul 22 '19 at 21:21

The intent of the code is that multiple positions in the array can point to the same element but must be freed only once. The inner loop would set the yet unprocessed pointers pointing to the same memory block to point to null instead so that they would not be attempted to be freed twice.

However, there is a serious problem with the implementation: the C standard says that after free(x) the value of x becomes indeterminate. And indeterminate means that the value could be anything at any instance that you inspect the variable. Thus it is legal for a C compiler to assume that the pointer does not match the pointer of any valid pointer and optimize the "almost correct"

void free_array(void *a[], int length) {
   int i, j;
   for (i = 0; i < length; i++) {
      if (a[i] != NULL) {
          free(a[i]);
          for (j = i + 1; j < length; j++) {
              if (a[j] == a[i]) {
                  a[j] = NULL;
              }
           }
     }
}

to

void free_array(void *a[], int length) {
    int i, j;
    for (i = 0; i < length; i++) {
        if (a[i] != NULL) {
            free(a[i]);
            for (j = i + 1; j < length; j++) {
                if (false) {
                }
            }
        }
    }
}

to

void free_array(void *a[], int length) {
    int i, j;
    for (i = 0; i < length; i++) {
        if (a[i] != NULL) {
            free(a[i]);
        }
    }
}

Correct solution must do the pointer comparisons before calling free:

void free_array(void *a[], int length) {
    int i, j;
    for (i = 0; i < length; i++) {
        if (a[i] != NULL) {
            for (j = i + 1; j < length; j++) {
                if (a[j] == a[i]) {
                    a[j] = NULL;
                }
            }
            free(a[i]);
        }
    }
}

Thanks for the effort. [**6.2.4 Storage durations of objects**, paragraph 2](https://port70.net/~nsz/c/c11/n1570.html#6.2.4p2): "... The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime." — Andrew Henle, Jul 22 '19 at 21:26

score 1 · Accepted Answer · answered Jul 22 '19 at 19:54

E.g.

Say you have an array of strings

char* ar[5];

you allocate some strings and let 0 and 4 index point to the same allocated string

ar[0] = ar[4] = strdup("mycommonstring");
ar[1] = strdup("hello");
ar[2] = strdup("world");
ar[3] = strdup("!");

With you answer you will free what ar[0] points to first, unfortunately ar[4] is still pointing to the same memory location, but when free(ar[0]) is called, the memory location it points to is invalid. When free is later called on ar[4], it will cause an error.

The given example makes sure that all pointers that point to the same location will be set to NULL to avoid that an invalid address is passed to the free function. So no, the memory location is not accessed again, only the pointer to the memory location

Freeing an array of dynamically allocated pointers

2 Answers2