Array of Structs memory realloc stderr

Question

I am trying to realloc an array of structs when it runs out of space as I'm putting elements into it but I keep receiving a realloc stderr. The array of struct will eventually have 235,000 elements in it. When I set the initial start size to 100,000 I receive the stderr when trying to realloc. If I se the initial start size to 300,000 it does not give the error because it never reaches the realloc statement.

#define _XOPEN_SOURCE
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>

#define BUFFERLEN 200
#define START_SIZE 100000
#define GROW 1000
#define TRUE 1
#define FALSE 0

typedef struct{
    char *forw;
    char *back;
} word;

typedef struct{
    char *entry;
} single_words;


FILE *words;
/*-------------Function Prototypes------------*/
void reverse(char* string, char* revstr, int len);
int search_struct(char* find, word* words, int length);
int compare(const void* eventa, const void* eventb);
int length(char* string);


int main(void)
{
    char *buffer;
    int letter_index[26];
    char alpha[] = "abcdefghijklmnopqrstuvwxyz";
    int i=0, found = FALSE, strlen=0, letter=0;
    word *word_storage;
    single_words *output_storage;
    int num_words = 0, size = 0;
    int num_output = 0, output_size = 0;

    /*buffer for the input strings of the words in the input file*/
    buffer = (char*) malloc (sizeof(char)*BUFFERLEN);
        if(!buffer){
            fprintf(stderr, "Error in buffer string mem alloc\n");
            exit(1);
        }   

    /*Initializing the array of structs to store the forward and reverse of each word*/
    word_storage = (word*) malloc (sizeof(word)*START_SIZE);
        if(!word_storage){
            fprintf(stderr, "Error in word_storage string mem alloc\n");
            exit(1);
        }
        size = START_SIZE;

    /*Initializing the array of structs for the output*/
    output_storage = (single_words*) malloc (sizeof(single_words)*START_SIZE);
        if(!output_storage){
            fprintf(stderr, "Error in output_storage mem alloc\n");
            exit(1);
        }
        output_size = START_SIZE;   

    /*Set the letter index 0(which is a) to the first character*/
    letter_index[0] = 0;

    words = fopen("words", "r");

    /*Read the words(forward and reverse) in from stdin into the word_storage*/
    while(fgets(buffer, BUFFERLEN, words) != NULL){
        buffer = strtok(buffer, "\n");
        strlen = length(buffer);
        if (num_words < size){
            /*Allocate memory for the forward and reverse strings*/
            word_storage[num_words].forw = (char *) malloc (sizeof(char) * strlen);
                if(!word_storage[num_words].forw){
                    free(word_storage[num_words].forw);
                    fprintf(stderr, "word_storage forward string malloc was unsuccessful");
                    exit(1);
                }
            word_storage[num_words].back = (char *) malloc (sizeof(char) * strlen);
                if(!word_storage[num_words].back){
                    free(word_storage[num_words].back);
                    fprintf(stderr, "word_storage forward string malloc was unsuccessful");
                    exit(1);;
                }               

            /*Store the forward and reverse in the strings*/
            strncpy(word_storage[num_words].forw, buffer, strlen);
            reverse(word_storage[num_words].forw, word_storage[num_words].back, strlen);
            printf("%d: %s %s\n", num_words, word_storage[num_words].forw, word_storage[num_words].back);

            /*Increment the letter if it changes*/
            if(word_storage[num_words].forw[0] != alpha[letter]){
                letter++;
                letter_index[letter] = num_words + 1;
            }
            num_words++;
        }
        else{
            /*Increase the size of word_storage*/
            word_storage = (word*) realloc (word_storage, sizeof(word) * size * GROW);
                if(!word_storage){
                    free(word_storage);
                    fprintf(stderr, "Error in word_storage realloc string mem realloc\n");
                    exit(1);
                }
            size = size * GROW;
        }       
    }


    return 0;
}

The realloc error occurs here:

word_storage = (word*) realloc (word_storage, sizeof(word) * size * GROW);
    if(!word_storage){
      free(word_storage);
      fprintf(stderr, "Error in word_storage realloc string mem realloc\n");
      exit(1);
     }
     size = size * GROW;

Answer 1

So, you initially set size to START_SIZE, which is 100,000. Then when you use that up, you try to allocate sizeof(word) * size * GROW bytes. sizeof(word) is presumably 16 bytes; we know that size is 100000, and GROW is 1000. So that works out to enough space for 100,000,000 entries, of which you say you will use 235,000. That seems like the allocation is a bit on the generous side.

The total space for 100,000,000 entries is 1,600,000,000 bytes. That seems like a lot, although these days many desktop machines could handle that. But it doesn't seem too surprising that realloc fails.

Perhaps you should make GROW something more reasonable, like 2.

By the way, once you've established that word_storage is NULL, there is no point in calling free(word_storage). It does no harm, since free(NULL) is a no-op, but it also does no good for the same reason.

Answer 2

You are multiplying the size by 1000 which is too much (highly exponential growth 1 -> 1000 -> 1000 000 -> 1000 000 000 ...), and you are not displaying the errno. I suggest instead

 size_t newsize = 3*size/2 + 1000;
 word_storage = realloc(word_storage, sizeof(word)*newsize);
 if (!word_storage) {
     fprintf(stderr, "Cannot grow storage to %ld size, %s\n",
                     (long) newsize, strerror(errno));
     exit (EXIT_FAILURE);
 }
 else size = newsize;

then if starting with an initial size of 1000, you are getting the much more reasonable progression 1000 -> 2500 -> 4750 -> 8125 -> 13187 -> 20780 ... and more importantly you are spending at most 50% of useless memory, not a factor of nearly 1000!