I have some sort of recursive function, but I need to parse a string, I don't know how long the string could it be. What si the appropiate way to allocate memory for that?
+1
A:
Either you need to have the size of the string passed in, so that you can allocate enough memory, or you have to put some reasonable limit on the maximum length of the string, say 1024 characters.
Dima
2009-09-03 18:23:11
Or you use the 3. option, allocate a reasonable size of memory and realloc() it as you need more. (mending the recursive function to either return the string directly or manipulate it via a passed in char **)
nos
2009-09-03 18:25:48
+6
A:
Use realloc() to increase string size when you exhaust the memory you've allocated so far.
Each realloc should at least double your string size--then the overall time spent on reallocation won't differ asymptotically, compared to a lucky allocation of the the string of necessary length at once.
Pavel Shved
2009-09-03 18:27:25
I agree, although there's nothing magic about doubling the size with each allocation. As long as you multiply by a constant factor greater than 1, you stay at O(n) rather than O(n^2). 2 is popular, but you'd get the same time complexity using 1.01. Just a much bigger constant factor.
Steve Jessop
2009-09-03 22:07:59
A:
If you can't find out the exact size (or getting it is too expensive), you should just assume some value. If you can estimate maximum size which the string will not exceed, you can just alloc a buffer of that size (and possibly realloc() it after filling the string in to avoid wasting space).
If you can't assume such maximum value, you should behave like Pavel suggests — assume some possible value, and then expand the area as the string arises.
Michał Górny
2009-09-03 18:29:41