C efficient way to manage function temporary dynamic memory

Question

I'm making an Nondeterministic Finite Automata (NFA). An NFA has a set of states, I need four array with the same size(number of states in the NFA) to record temporary information about states during the simulation of the NFA.

However, different NFAs has different number of states, thus the size of arrays varies with different NFAs.

Using C I have come up with three ways to deal with the memory allocation:

1. Use a very big fix-sized array.

2. malloc memroy dynamically every time the function is called, and before the function finishes, free the allocated memory

3. Use malloc but not allocate memory on every function call, use four static pointer variables, and one static int arraySize to record allocated array size, for the first time when the function is called, allocate arrays of size NFA->numStates and assign to each of the static pointers, assign NFA->numStates to static int arraySize; for the second time, if NFA->numStates is less than or equal to arraySize, no memory allocation; if NFA->numStates is greater than arraySize, free previous memory and realloc arrays of size NFA->numStates.

Method 1 uses fix-sized array, which means when the input NFA->numStates is greater than the hard-coded array size, the function will not work.

Method 2 is adaptable, but need to allocate memory every time the function is called, not so efficient ?

Method 3 is adaptable too, but is complicated, and is not thread safe ?

Suggestions or other alternatives ?

Answer 1

How about option 2 but with alloca(), i.e. allocate on the stack? It's much (much) faster than malloc(), and automatically de-allocates when you leave the scope which sounds like what you want.

Of course, it's not standard or portable, so it might not be applicable for you.

Failing that, a big fixed-size array seems easy enough and doesn't use more memory.

Answer 2

Variable-Length Arrays (VLAs) have been available since C99. I'd be impressed if you are still working with an implementation that does not support such a thing. VLAs work like regular arrays, except that the size you use to declare them is determined at runtime. That seems to be what you're looking for.

Answer 3

As you are dealing with arrays of arbitrary size I suggest you to implement simple linked list structure that at initialization will hold an array of predefined size and can be extended to hold additional chunks of memory. This will be an abstraction over contiguous memory space. You just need to store the current size of this structure in parent container.

#include <stddef.h>

struct contmem
{
        size_t size;
        struct memchunk
        {
                void *data;
                struct memchunk *next, *prev;
        } head;
}

So, you can extend this structure when you have to and store information by iterating over elements of linked list. This is similar to what happens inside lists from standard C++ library and differs from straight memory reallocation.