Huh, I didn't consider the possibility of pre-allocating space for the entire state list. That's a cute trick, making it less memory efficient in the average case (though more efficient CPU-wise by avoiding malloc) but also addressing my exact concern. Nice.
edit: I guess I should have just looked that up sooner. Sorry for any hassle or aggravations.
Interesting. I had never even considered not pre-allocating space for it... :-)
In a "real" implementation, you also need space to store sub-capture locations. You get to reuse this space on each execution of the regex, so it's a really nice win.
There are also certain crazy people in this world who have encoded the NFA algorithm into a code generation tool, which enables it to run completely malloc-free and entirely on the stack. :-)
edit: I guess I should have just looked that up sooner. Sorry for any hassle or aggravations.