Dynamic memory allocation question.

[peripatein]

Hi,
Suppose I wished to reallocate memory (resize) an array of pointers. Why does the following not work?(The program runs, yet yields a faulty segmentation error message.
Why?):

char **ptrarr = (char**) malloc(sizeof(char*))

 ptrarr = (char**) realloc(ptrarr, (capacity) * sizeof(char*));

[laserlight]

Post the smallest and simplest compilable program that demonstrates the problem.

[Jimmy]

Laserlight has a better answer than mine! :-)

Also, read the documentation on realloc, you are using it wrong. You should save the value returned from realloc in a temporary variable until you know the call was successful.

[peripatein]

It's supposed to be an array of pointers, where each cell points to a sentence in a string. I am using it in a loop which determines how many sentences are in that string. Each time the sentence counter is incremented, I would like my array incremented as well by 1. Capacity, in my code, is the sentence counter.
Why would it give such message? What am I doing wrong?

[peripatein]

But is that what's preventing it from working? Even if I first verify that the returned value is not NULL, it still gives the above mentioned message.

[laserlight]

It's supposed to be an array of pointers, where each cell points to a sentence in a string. I am using it in a loop which determines how many sentences are in that string. Each time the sentence counter is incremented, I would like my array incremented as well by 1. Capacity, in my code, is the sentence counter.

Don't just tell, show us. Post the code. It is supposed to be an array of pointers, but maybe it isn't. Maybe it is not the case that "each cell points to a sentence in a string". Maybe your loop is wrong. Maybe your capacity is negative at some point. Maybe, maybe, maybe.

By the way, re-allocating each time the sentence counter is incremented is likely to be a poor strategy in the long run. A better general purpose strategy would be to expand by a factor, e.g., double the capacity.

Incidentally, for the code that you did show, I can say:

• Use sizeof(*ptrarr) instead of sizeof(char*)
• Unless you need this to be compilable as C++, do not cast the return value of malloc.
• When using realloc, use a different pointer to store the result, in case realloc returns a null pointer.

[Jimmy]

It's supposed to be an array of pointers, where each cell points to a sentence in a string. I am using it in a loop which determines how many sentences are in that string. Each time the sentence counter is incremented, I would like my array incremented as well by 1. Capacity, in my code, is the sentence counter.
Why would it give such message? What am I doing wrong?

I know why. It is easy. You are doing something wrong.

That is about all I can say as I haven't seen the code you have written.

On another note, if you show us your code, be sure to enable all warnings in your compiler and make sure it compiles without warnings before posting.

[migf1]

Here's a small but complete program that does almost what you are asking for. It's working with arrays of integers instead of cstrings, completely dynamically. It should be fairly easy to change it for cstrings (I've included comments).

Actually it is easier when working with cstrings, since you don't have to NUL terminate the columns. Most probably you won't need to tokenize each input line, but store it as a whole instead, after s_get()'ing it....

Most of the action takes place inside the function arr_new()...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAXINPUT    (255+1)
#define STOP_INPUT    "stop"

/* -----------------------------------------------
 * Get a string from stdin, drop the '\n' and return its length.
 */
int s_get( char *s, int size )
{
    int i, c;

    if ( !s )
        return -1;

    for (i=0; i < size-1 && EOF != (c = getchar()) && c != '\n'; i++ )
        *s++ = c;
    *s = '\0';

    return i;
}

/* -----------------------------------------------
 * Set the first nrows of arr to NULL.
 */
void arr_invalidate_rows( int **arr, int nrows )
{
    int i;

    if ( !arr )
        return;

    for (i=0; i < nrows; i++)
        arr[i] = NULL;
}

/* -----------------------------------------------
 * Print the contents of arr.
 * Rows are expected to be NULL terminated,
 * while cols are expected to be INT_MAX terminated.
 */
void arr_print( int **arr, const char *title )
{
    int i,j;

    if ( title ) {
        printf( "%s", title );
        fflush( stdout );
    }

    if ( !arr ) {
        puts( "<NULL>" );
        return;
    }

    for (i=0; NULL != arr[i]; i++)
    {
        for (j=0; INT_MAX != arr[i][j]; j++) {
            printf( "%d ", arr[i][j] );
            fflush(stdout);
        }
        putchar( '\n' );
    }
    putchar( '\n' );
}

/* -----------------------------------------------
 * Free memory reserved for arr.
 * Rows are expected to be NULL terminated.
 */
void arr_free( int ***arr )
{
    int i;

    if ( !arr )
        return;

    for (i=0; (*arr)[i]; i++)
        free( (*arr)[i] );
    free( *arr );

    *arr = NULL;
}

/* -----------------------------------------------
 * Return a newly created arr, according to user input.
 * nrows passes to the caller the total number of rows
 * created, excluding the NULL terminating one.
 */
int **arr_new( int *nrows, const char *prompt )
{
    const int AHEAD = 16;        /* alloc ahead buffer, in elements */

    int    **ret = NULL, **try = NULL;
    int    *tryCols = NULL;

    int    i=0, j=0;
    char    *delims    = "\t\n ";
    int    ncols = 0;
    char    input[MAXINPUT] = {'\0'};

    if ( !nrows )
        goto fail;

    if ( prompt ) {
        printf( "%s", prompt );
        fflush( stdout );
    }

    /* create alloc-ahead buffer for rows */
    *nrows = AHEAD;
    ret = malloc( *nrows * sizeof(int *) );
    if ( NULL == ret )
        goto fail;
    arr_invalidate_rows( ret, *nrows );    /* make them all NULL */

    /*
     * read input lines (rows) from stdin
     * tokenize each line to integers (cols)
     * and store each integer into each curent row as a new col
     */
    for (i=0; s_get(input, MAXINPUT) > 0; i++ )
    {
        char *cp = NULL;        /* string token */

        /* stop when user types the STOP_INPUT string */
        if ( 0 == strcmp(input, STOP_INPUT) )
            break;

        /* need more mem for rows? */
        if ( i == *nrows-1 )
        {
            /* double their allocated size */
            try = realloc(ret, 2 * (*nrows) * sizeof(int *) );
            if ( NULL == try )
                goto fail;
            arr_invalidate_rows( &try[i], *nrows );
            ret = try;

            (*nrows) += (*nrows);    /* remember new count of rows */
        }

        /* create alloc-ahead buffer for cols in current row */
        ncols = AHEAD;
        ret[i] = calloc(ncols, sizeof(int) );
        if ( NULL == ret[i] )
            goto fail;

        /* tokenize input line into integers & store them as cols at current row */
        j = 0;
        for (cp = strtok(input,delims); cp; cp = strtok(NULL,delims) )
        {
            /* need more mem for cols in current row ? */
            if ( j == ncols-1 )
            {
                /* double their allocated size */
                tryCols = realloc(ret[i], 2 * ncols * sizeof(int) );
                if ( NULL == try )
                    goto fail;
                ret[i] = tryCols;

                ncols += ncols;    /* remember new count of cols */
            }

            /* convert string token to integer & store it */
            if ( 1 != sscanf(cp, "%d", &ret[i][j]) )
                goto fail;
            /* INT_MAX is allowed, but no further inputting for this row */
            if ( INT_MAX == ret[i][j] )
                break;
            j++;            /* current col */
        }
        ret[i][j++] = INT_MAX;        /* add terminating value */

        /* free any extra cols from memory for this row */
        tryCols = realloc(ret[i], j * sizeof(int) );
        if ( NULL == tryCols )
            goto fail;
        ret[i] = tryCols;

        ncols = j-1;            /* exclude terminating value */
    }
    ret[i++] = NULL;            /* NULL termninate rows */

    /* free any extra rows from memory */
    try = realloc( ret, i * sizeof(int *) );
    if ( NULL == try )
        goto fail;
    ret = try;

    *nrows = i-1;                /* exclude NULL terminating row */

    return ret;

fail:
    puts( "*** failure to make a new arr... " );
    if ( ret )
        arr_free( &ret );
    return NULL;
}

/* -----------------------------------------------
 * Entry point of the program
 */
int main( void )
{
    int **arr1 = NULL, **arr2 = NULL;
    int nrows1 = 0, nrows2 = 0;

    arr1 = arr_new( &nrows1, "ENTER CONTENTS OF ARR1:\n" );
    if ( NULL == arr1 )
        goto fail;

    arr2 = arr_new( &nrows2, "ENTER CONTENTS OF ARR2:\n" );
    if ( NULL == arr2 )
        goto fail;

    arr_print( arr1, "ARR1 CONTENTS:\n" );
    arr_print( arr2, "ARR2 CONTENTS:\n" );

    arr_free( &arr1 );
    arr_free( &arr2 );

    exit(0);

fail:
    puts( "aborting program... " );
    if ( arr1 )
        arr_free( &arr1 );
    if ( arr2 )
        arr_free( &arr2 );

    exit(1);

}

And here is some sample input & output...

ENTER CONTENTS OF ARR1:
1 3 4
0 2
1 3
0 2 4
0 3
stop
ENTER CONTENTS OF ARR2:
5 5 7
5 7
7 6
5 6 6
7 6
stop
ARR1 CONTENTS:
1 3 4
0 2
1 3
0 2 4
0 3

ARR2 CONTENTS:
5 5 7
5 7
7 6
5 6 6
7 6

s_get() requires a pre-allocated buffer of fixed maximum size. If you want it to be dynamically allocated, you may give a try to this function instead (don't forget to free() the returned cstring after done using it).

[Nominal Animal]

Perhaps a small exploration on how dynamic memory management is properly done is in order?

In C, dynamically allocated arrays are referenced using a pointer (to its first element). The C library knows internally how much memory was allocated, but it never divulges that information. Therefore, we need to keep track of the size used and size allocated for the array. Allocation/reallocation size is the only one that is counted in chars: for the sizes, we can use the number of elements used and available.

While the allocation/deallocation routines in C are quite fast, they do cause a slowdown if you have to call them for every single new element you wish to add. That is why it is better to allocate more than you need right now. The balance between number of reallocations and the extra memory allocated depends entirely on the circumstances, and there is no golden rule. (It's not that rare to fine-tune that after the application sees some real-world use cases.

Consider, for example, a small snippet that reads floating-point values from standard input, and adds them into a dynamically allocated array, until it encounters an error (not a valid number in input) or end-of-input:

    size_t  numbers_allocated = 0;
    size_t  numbers_count = 0;
    double *numbers_array = NULL;

    double  number;

    while (fscanf(stdin, "%lf", &number) == 1) {

        /* Grow numbers array if necessary. */
        if (numbers_count >= numbers_allocated) {
            double *temp;

            /* Easiest possible policy: Allocate fixed number of extra elements. */
            numbers_allocated = numbers_count + 16; /* Current + 15 more for future */
            temp = realloc(numbers_array, numbers_allocated * sizeof *numbers_array);
            if (!temp) {
                /* Reallocation failed: not enough memory.
                 * Note: numbers_array is still intact.
                 * We exit(1) after printing an out of memory error. */
                fprintf(stderr, "Out of memory: cannot grow numbers_array.\n");
                free(numbers_array);
                exit(1);
            }

            /* Reallocation was successful. The old pointer is now defunct,
             * and we must switch to using the one realloc() gave us. */
            numbers_array = temp;
        }

        /* Add new number to the array. */
        numbers_array[numbers_count++] = number;
    }

    if (ferror(stdin) || !feof(stdin))
        fprintf(stderr, "Standard input contained a non-numeric value!\n");
    else
        fprintf(stderr, "All standard input read successfully.\n");

    /*
     * TODO: Do something with the array
    */

    /* After the numbers are no longer needed, do: */
    free(numbers_array);
    numbers_array = NULL;
    numbers_count = 0;
    numbers_allocated = 0;

Some frequently asked questions:

1. Why do you explicitly initialize the pointer to NULL, and the sizes to zero?
   For simplicity and ease of use. realloc(NULL,size) is exactly the same as malloc(size), and free(NULL) is a no-op.
   
2. Why do you explicitly clear the pointer to NUL and the sizes to zero after the free() call?
   It is cheap (clearing three variables takes almost no CPU time at all).
   It makes debugging easier, because catching a NULL pointer dereference is much easier than noticing that you're using a pointer that has already been free()d.
   It makes it easier to catch memory leaks. (Add a breakpoint just before a function exits. If the context has non-NULL pointer variables, you've forgotten to release some dynamically allocated memory. This is especially useful when writing libraries.)
   
3. What does that sizeof *numbers_array mean?
   It literally means the size of the element that numbers_array points to.
   While the sizes are in numbers of elements, malloc() and realloc() take the size in bytes (chars). This is the recommended way to refer to the size of each element in the array, because it keeps working even if you change the type of the array elements.
   
4. What's with the temporary pointer variable temp?
   If a realloc() call fails, the original data still exists and is accessible at the old pointer.
   Many programmers take advantage of the fact that when a program exits, all dynamically allocated memory is automatically released. (Well, certain shared memory types do not, but you need to allocate those using special function calls anyway.) This means that doing free() just before exit() (or return from main() is never necessary.
   However, if you are writing reusable code, or library code, you cannot just assume that. The actual program might find the error completely okay, and do something else instead -- we call these programs nice and robust!
   Not leaking memory is therefore very important in the long run. It does not matter for test programs or programming exercises, but it does in real life.
   
5. Error checking?
   The scanf() family of functions return the number of successful conversions, or -1 if an error occurs (invalid input, read error, so on).
   After an I/O call fails, we can check ferror() and/or feof() to see if the failure was caused by a read error, or if there simply was no more input.
   Make sure you understand that logic: these two functions do not "test the input stream". They only tell you why a previous I/O call on that stream failed.
   
6. I used the above code, but if I supply no input, I get Segmentation Fault. Why?
   The above snippet allocates memory only when it is needed. (And then it allocates for 15 extra numbers.)
   This means that if the very first fscanf() call fails, i.e. there is no valid numbers in the standard input, the numbers_array will stay NULL.
   In other words, you forgot to check that numbers_count > 0, and just tried to access the array elements anyway. There aren't any, as numbers_count would tell you, so it is perfectly normal for numbers_array to be NULL.

I hope you find this illuminating.

[migf1]

Pretty nice post!

Just a note though, I'm not 100% sure but I think realloc(NULL,...) acting like malloc() was standardized in C99. I think C89/90 doesn't guarantee it (it is worth looking it up if you are working with a pre C99 compiler).

[laserlight]

Nominal Animal: instead of only posting all that here where it will probably get lost after some time, consider submitting it to the webmaster as a tutorial or FAQ entry.

Just a note though, I'm not 100% sure but I think realloc(NULL,...) acting like malloc() was standardized in C99. I think C89/90 doesn't guarantee it (it is worth looking it up if you are working with a pre C99 compiler).

No, it was standardised in C89/C90.

[grumpy]

It was also informally specified in K&R C.

[Nominal Animal]

Nominal Animal: instead of only posting all that here where it will probably get lost after some time, consider submitting it to the webmaster as a tutorial or FAQ entry.

I think it'd benefit from a bit of finessing first (wording and comments in the code at least); any volunteers?

Feel free to edit and/or submit it. No attribution necessary.

[Mr.Lnx]

@Nominal Animal why you are using "scanf returns the number of succesful conversions" ?

Except you are assuming that is equal with "scanf returns the number of succesful assignments".

[Nominal Animal]

@Nominal Animal why you are using "scanf returns the number of succesful conversions" ?

Except you are assuming that is equal with "scanf returns the number of succesful assignments".

Because %n (the number of characters consumed thus far by the function) may or may not be included in the count, and it is an assignment. (The text of the standard and the corrigendum seem to contradict each other.)

I thought "conversion" would be better than "assignment", since %n assignment may not be counted, and all the other the assignments that are counted, look like conversions to the programmer. (Except that strings and patterns are just copied, not really converted..)

Individual characters and suppressed assignments (%*) are not counted in the results either. (A C library is free to just verify that the pattern consumed matches the input specified, it does not absolutely have to do a conversion. I think to a programmer, that is more like matching, not conversion.)

English is not my native language, so if there is a language issue, could some of the native English speakers pipe up? Check the scanf() man page from the Linux man-pages project; it describes not only the Linux implementation, but the differences it has to other implementations and the relevant standards, too. I don't personally have an opinion on what terms are best used -- the man page uses "matched and assigned" -- but clarity on this should help programmers understand the function family better.

I've personally seen enough code that ignores the return values from the scanf() family of function calls.

There are only two situations where ignoring the return value is okay:

1. You consume optional input that does not have any assignments.
   For example, you might use

    (void)fscanf(stream, "%*[,:;]")

   to consume any commas, semicolons, or colons in input, between things you are interested in.
2. You use %n, and preset the values to -1.
   For example, you might want to use

       int start = -1, length = -1;
       (void)sscanf(string, "rgb: %n%*[-0-9A-Za-z]%n", &start, &length);
       if (length > start) {
           /* Okay, you have a colorspec at string[start..length-1]. */
       }

   to parse a colorspec from a string. The length variable tells how much of the string was consumed, and start where the interesting part was.

Every other case of ignoring the return value leads to bugs or undefined behaviour, as far as I can tell.

(I know there are those here who wish to nitpick that claim. Sure, you can assign default values and just not care whether the input is correct or not, but think about how that looks like to the end user: they cannot tell whether their input was acceptable or not: the program just chugs forwards with who knows what input. I don't accept that kind of behaviour from my own programs.)