Determining realloc() behaviour before calling it

Question

As I understand it, when asked to reserve a larger block of memory, the realloc() function will do one of three different things:

if free contiguous block exists
    grow current block
else if sufficient memory
    allocate new memory
    copy old memory to new
    free old memory
else
    return null

Growing the current block is a very cheap operation, so this is behavior I'd like to take advantage of. However, if I'm reallocating memory because I want to (for example) insert a char at the start of an existing string, I don't want realloc() to copy the memory. I'll end up copying the entire string with realloc(), then copying it again manually to free up the first array element.

Is it possible to determine what realloc() will do? If so, is it possible to achieve in a cross-platform way?

Answer 1

I don't think it's possible in cross platform way. Here is the code for ulibc implementation that might give you a clue how to do itin platform dependent way, actually it's better to find glibc source but this one was on top of google search :)

Answer 2

A better approach is to use a linked list. Have each of your data objects allocated on a page, and allocate another page and have a link to it, either from the previous page or from an index page. This way you know when the next alloc fails, and you never need to copy memory.

Answer 3

Why not keep some empty buffer space in the left of the string, like so:

char* buf = malloc(1024);
char* start = buf + 1024 - 3;
start[0]='t';
start[1]='o';
start[2]='\0';

To add "on" to the beginning of your string to make it "onto\0":

start-=2;
if(start < buf) 
  DO_MEMORY_STUFF(start, buf);//time to reallocate!
start[0]='o';
start[1]='n';

This way, you won't have to keep copying your buffer every single time you want to do an insertion at the beginning.

If you have to do insertions at both the beginning and end, just have some space allocated at both ends; insertions in the middle will still need you to shuffle elements around, obviously.

Answer 4

Would storing your string backwards help?

Otherwise... just malloc() more space than you need, and when you run out of room, copy to a new buffer. A simple technique is to double the space each time; this works pretty well because the larger the string (i.e. the more time copying to a new buffer will takes) the less often it needs to occur.

Using this method you can also right-justify your string in the buffer, so it's easy to add characters to the start.

Answer 5

No - and if you think about it, it can't work. Between you checking what it's going to do and actually doing it, another process could allocate memory. In a multi-threaded application this can't work. Between you checking what it's going to do and actually doing it, another thread could allocate memory.

If you're worried about this sort of thing, it might be time to look at the data structures you're using to see if you can fix the problem there. Depending on how these strings are constructed, you can do so quite efficiently with a well designed buffer.

Answer 6

As noted in the comments, case 3 in the question (no memory) is wrong; realloc() will return NULL if there is no memory available [question now fixed].

Steve McConnell in 'Code Complete' points out that if you save the return value from realloc() in the only copy of the original pointer when realloc() fails, you've just leaked memory. That is:

void *ptr = malloc(1024);
...
if ((ptr = realloc(ptr, 2048)) == 0)
{
    /* Oops - cannot free original memory allocation any more! */
}

Different implementations of realloc() will behave differently. The only safe thing to assume is that the data will always be moved - that you will always get a new address when you realloc() memory.

As someone else pointed out, if you are concerned about this, maybe it is time to look at your algorithms.

Answer 7

If obstacks are a good match for your memory allocation needs, you can use their fast growing functionality. Obstacks are a feature of glibc, but they are also available in the libiberty library, which is fairly portable.

Answer 8

realloc()'s behavior is likely dependent on its specific implementation. And basing your code on that would be a terrible hack which, to say the least, violates encapsulation.

A better solution for your specific example is:

1. Find the size of the current buffer
   • Allocate a new buffer (with malloc()), greater than the previous one
   • Copy the prefix you want to the new buffer
   • Copy the string in the previous buffer to the new buffer, starting after the prefix
   • Release the previous buffer