C dynamic string length

Question

There are different ways of creating dynamic strings in C (with length that constantly changes). After some google search, the main way of doing this is to use realloc().

A way I implemented this is using linked lists with 32 bytes chunks for each node.

I was wondering if there are better ways of tackling this apart from using realloc() and linked lists, and what the cons and pros for each method are.

EDIT The reason I am doing this is because I'm receiving dynamic data from a socket recv(), and was looking for a flexible way of storing it, without allocating huge amounts of data that aren't needed.

Answer 1

You can realloc to different predefined sizes. For example, when the buffer is full, double its size.

Using a linked list is a good idea, but the data is not continuous (you can't pass the whole structure to printf, for example) and indexing takes more calculations (O(N)). A major advantage is that appending strings (at either end) is O(1).

Answer 2

I think you're looking for Scatter-Gather I/O, the function you'd be looking for would be readv().

Answer 3

If you do use realloc(), don't add a constant amount of space on every realloc, because then the cost of producing a string of length n will be an O(n^2) (realloc will probably allocate a new region and copy the data there, i.e. its complexity is not constant but O(n)). The easiest way to do it is to double the size of the buffer on every realloc, then the amortized cost will still be O(n).

Answer 4

Using 32 byte chunks means that the ratio between data and overhead is terrible - you have your pointer in the linked list and at least (probably much more) the same again from the memory allocator. I would strongly suggest allocating a much larger chunk of memory and grow it exponentially to fit and see if this causes problems. Only if you encounter problems would I go the linked list route.