C - Array of Strings & Mysterious Valgrind Error

Question

I'm trying to allocate a two-dimensional array of strings, where the last member is always a NULL pointer, i.e. an empty array consists of a single NULL pointer. I keep getting Valgrind errors but I have no idea why.

/*Initializes the string array to contain the initial
 * NULL pointer, but nothing else.
 * Returns: pointer to the array of strings that has one element
 *      (that contains NULL)
 */
char **init_array(void)
{
    char **array = malloc(sizeof(char *));
    array[0] = NULL;
    return array;
}
/* Releases the memory used by the strings.
 */
void free_strings(char **array)
{
    int i = 0;
    while(array[i] != NULL){
        free(array[i]);
        i++;
    }
    //free(array[i]);
    free(array);

}

/* Add <string> to the end of array <array>.
 * Returns: pointer to the array after the string has been added.
 */
char **add_string(char **array, const char *string)
{
    int i = 0;
    while(array[i] != NULL){
        i++;
    }
    array = realloc(array, (i+1) * sizeof(char *));
    char *a = malloc(strlen(string)+1);
    array[i] = malloc(strlen(string)+1);
    strcpy(a, string);
    strcpy(array[i], a);
    free(a);
    return array;
}

Here's the Valgrind error:

==375== Invalid read of size 8 ==375==    at 0x402FCE: add_string (strarray.c:40) ==375==    by 0x401855: test_add_string (test_source.c:58) ==375==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==375==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==375==    by 0x40256A: main (test_source.c:194) ==375==  Address 0x518df08 is 0 bytes after a block of size 8 alloc'd ==375==    at 0x4C245E2: realloc (vg_replace_malloc.c:525) ==375==    by 0x402FF4: add_string (strarray.c:43) ==375==    by 0x401855: test_add_string (test_source.c:58) ==375==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==375==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==375==    by 0x40256A: main (test_source.c:194) ==375==  ==375== Invalid read of size 8 ==375==    at 0x4018F7: test_add_string (test_source.c:70) ==375==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==375==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==375==    by 0x40256A: main (test_source.c:194) ==375==  Address 0x518e308 is 0 bytes after a block of size 40 alloc'd ==375==    at 0x4C245E2: realloc (vg_replace_malloc.c:525) ==375==    by 0x402FF4: add_string (strarray.c:43) ==375==    by 0x401855: test_add_string (test_source.c:58) ==375==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==375==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==375==    by 0x40256A: main (test_source.c:194) ==375==  ==375== Invalid read of size 8 ==375==    at 0x402F8D: free_strings (strarray.c:25) ==375==    by 0x401AA6: test_add_string (test_source.c:91) ==375==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==375==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==375==    by 0x40256A: main (test_source.c:194) ==375==  Address 0x518e308 is 0 bytes after a block of size 40 alloc'd ==375==    at 0x4C245E2: realloc (vg_replace_malloc.c:525) ==375==    by 0x402FF4: add_string (strarray.c:43) ==375==    by 0x401855: test_add_string (test_source.c:58) ==375==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==375==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==375==    by 0x40256A: main (test_source.c:194) ==375==  ==376== Invalid read of size 8 ==376==    at 0x402FCE: add_string (strarray.c:40) ==376==    by 0x401DCD: test_make_lower (test_source.c:111) ==376==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==376==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==376==    by 0x40256A: main (test_source.c:194) ==376==  Address 0x518e6d8 is 0 bytes after a block of size 8 alloc'd ==376==    at 0x4C245E2: realloc (vg_replace_malloc.c:525) ==376==    by 0x402FF4: add_string (strarray.c:43) ==376==    by 0x401DCD: test_make_lower (test_source.c:111) ==376==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==376==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==376==    by 0x40256A: main (test_source.c:194) ==376==  ==376== Invalid read of size 8 ==376==    at 0x402F8D: free_strings (strarray.c:25) ==376==    by 0x401F5C: test_make_lower (test_source.c:130) ==376==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==376==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==376==    by 0x40256A: main (test_source.c:194) ==376==  Address 0x518e9d0 is 0 bytes after a block of size 32 alloc'd ==376==    at 0x4C245E2: realloc (vg_replace_malloc.c:525) ==376==    by 0x402FF4: add_string (strarray.c:43) ==376==    by 0x401DCD: test_make_lower (test_source.c:111) ==376==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==376==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==376==    by 0x40256A: main (test_source.c:194) ==376==  ==377== Invalid read of size 8 ==377==    at 0x402FCE: add_string (strarray.c:40) ==377==    by 0x4022DB: test_sort_strings (test_source.c:155) ==377==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==377==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==377==    by 0x40256A: main (test_source.c:194) ==377==  Address 0x518f3e8 is 0 bytes after a block of size 8 alloc'd ==377==    at 0x4C245E2: realloc (vg_replace_malloc.c:525) ==377==    by 0x402FF4: add_string (strarray.c:43) ==377==    by 0x4022DB: test_sort_strings (test_source.c:155) ==377==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==377==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==377==    by 0x40256A: main (test_source.c:194) ==377==  ==377== Invalid read of size 8 ==377==    at 0x402F8D: free_strings (strarray.c:25) ==377==    by 0x40246A: test_sort_strings (test_source.c:174) ==377==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==377==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==377==    by 0x40256A: main (test_source.c:194) ==377==  Address 0x518f6e0 is 0 bytes after a block of size 32 alloc'd ==377==    at 0x4C245E2: realloc (vg_replace_malloc.c:525) ==377==    by 0x402FF4: add_string (strarray.c:43) ==377==    by 0x4022DB: test_sort_strings (test_source.c:155) ==377==    by 0x405F90: srunner_run_all (in /tmc/test/test) ==377==    by 0x4028B2: tmc_run_tests (tmc-check.c:122) ==377==    by 0x40256A: main (test_source.c:194) ==377==

Answer 1

That's because you didn't add new NULL-terminator to the array add_string(). So subsequent calls of add_array() fail to find end of array without going out of bounds.

I think you need realloc with larger length:

array = realloc(array, (i + 2) * sizeof(char *));

And then save NULL-terminator to array[i + 1]:

array[i + 1] = NULL;

---

Why didn't you try using linked lists for that? I feel bad for realloc() per each add_string()

Answer 2

This function

char **add_string(char **array, const char *string)
{
    int i = 0;
    while(array[i] != NULL){
        i++;
    }
    array = realloc(array, (i+1) * sizeof(char *));
    char *a = malloc(strlen(string)+1);
    array[i] = malloc(strlen(string)+1);
    strcpy(a, string);
    strcpy(array[i], a);
    free(a);
    return array;
}

is wrong. It does not add a new slot into the array and you do not set the last element to NULL.

The valid function can look like

char **add_string( char **array, const char *string )
{
    int i = 0;

    while ( array[i++] != NULL );

    array = realloc( array, ( i + 1 ) * sizeof( char * ) );

    array[i] = NULL;

    array[i-1] = malloc( strlen( string ) + 1 );
    strcpy( array[i-1], string );

    return array;
}