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.