C - Realloc, Linked Lists, and pointers
So I'm creating a simple memory buffer in C. Lets say I create the buffer of memory:
PHP Code:
void* pBuffer = malloc(1024);
This buffer will be used to hold a bunch of structs.
PHP Code:
struct Node
{
...Bunch of PODs
}
And of course each Node will have a header struct in order to link everything in the buffer.
PHP Code:
struct NodeHeader
{
Node* pNode;
size_t nodeSize;
NodeHeader* pNext;
}
When I run out of free buffer space, I'll call realloc on pBuffer to make the buffer larger. Now I know its best to assume it'll always assign a whole new block of memory and copy everything over. Which will make any pointer, pointing into the original buffer location unsafe. But what about pointers within in the buffer? Will I need to manually go back through and reassign all my struct NodeHeader pointers? Or will what they are pointing to also be updated in the realloc?
Keep in mind, its paramount that I always have everything stored in continuous segment of memory. So just doing another malloc and linking the two blocks of memory together isn't an option.
Thanx in advance.
Re: C - Realloc, Linked Lists, and pointers
The internal pointers would likely change, but I don't understand why you need them. You're kind of combining an array and a list. If everything is contiguous why do you need pointers to the next node? Why not just use an array?
Re: C - Realloc, Linked Lists, and pointers
Oh, forgot to mention that each Node struct would be variable in size so an array is out of the question.
Re: C - Realloc, Linked Lists, and pointers
Quote:
Originally Posted by
JaySoyer
Oh, forgot to mention that each Node struct would be variable in size so an array is out of the question.
Not if it's an array of pointers. The concept of a container that stores objects contiguously and each node has a pointer to the next node seems redundant and a bit confused to me.
Re: C - Realloc, Linked Lists, and pointers
Quote:
Originally Posted by
JaySoyer
Oh, forgot to mention that each Node struct would be variable in size
How? There is no way to change the size of a type at runtime.
The Node has a size that's fixed, and that size is:
The "Bunch of PODS" you have in your original post means nothing. There is a fixed size, and that is what you see above.
Regards,
Paul McKenzie
Re: C - Realloc, Linked Lists, and pointers
Ok, I'm being critique in something I was just trying to dumb down for the purpose of my REAL question. Which was what happens to the internal pointers and not am I programming this correctly. Perhaps my choice for "setting the scene" was too simplistic.
To clear up, I'm not truly storing a struct but a collection of variable sized character arrays. And not the pointers either. I need to store the actual guts of it. A collection of these arrays constitutes a "logical node" sort of speak. Throughout this buffer, I'm storing several different "logical nodes", each with its own node header.
The above sounds more complex then what was needed to say and I left it out because it will not affect the answer of my original question.
Re: C - Realloc, Linked Lists, and pointers
Quote:
Originally Posted by
JaySoyer
To clear up, I'm not truly storing a struct but a collection of variable sized character arrays.
That doesn't change what I stated.
It is not possible to declare a struct A with "variable size" arrays, and have the sizeof(A) change. So what you're asking for is impossible. Why not post a real struct with real definitions, and you will see you cannot change the sizeof(A)?
Somehow you have to implement these variable size arrays. The way you do that is with malloc(), realloc(), calloc(), and the heap. You have no choice but to use pointers since these are the types that are returned by these functions. Also a pointer is not data. All a pointer does is point to your data. If your data is on the heap in contiguous memory, then you point to this data using pointers.
As to your question about pointers becoming invalid -- the answer is simple.
If you have a pointer value returned by malloc(), and then you call free() on that same value, the memory that was allocated now becomes deallocated and "invalid". That's it -- nothing else. So if you had pointers internally that were created by malloc() but you never free() them, then those pointer values are still valid.
What is *not* valid is if you had declared pointers and pointed them into this pool of memory and then you deallocated the pool. Then of course, those pointers are pointing into garbage -- you need to reseat those pointers to point to the valid memory.
Quote:
A collection of these arrays constitutes a "logical node" sort of speak. Throughout this buffer, I'm storing several different "logical nodes", each with its own node header.
It isn't clear why a linked list is not satisfactory in this case.
Quote:
Keep in mind, its paramount that I always have everything stored in continuous segment of memory. So just doing another malloc and linking the two blocks of memory together isn't an option.
Please explain the reason for this requirement.
Basically, what you want is one memory pool big enough to hold everything, and you need to write all of the memory management code if you have user pointers pointing to the pool (the reseating of the pointers if the memory becomes invalidated).
Regards,
Paul McKenzie
Re: C - Realloc, Linked Lists, and pointers
We seem to be having a communication problem.
Quote:
Originally Posted by Paul McKenzie
It is not possible to declare a struct A with "variable size" arrays, and have the sizeof(A) change.
I know that. You're referring to a reply in which, I still didn't feel like explaining why I wasn't actually using structs. The given question was easier to understand if it was just a struct. I didn't want this to be some drawn out thing on what and why I'm doing everything.
Quote:
Originally Posted by Paul McKenzie
Somehow you have to implement these variable size arrays. The way you do that is with malloc(), realloc(), calloc(), and the heap. You have no choice but to use pointers since these are the types that are returned by these functions.
Ugh, must I explain the entire purpose of what I'm coding. No I am not implementing these arrays. I'm writing an API which accepts character arrays from whomever. So I have no control of the original memory allocation. If the array points to "Hello", I need to store those actual 5 characters and not the pointer.
Quote:
Originally Posted by Paul McKenzie
It isn't clear why a linked list is not satisfactory in this case.
I never said I wasn't using one. All the nodes have a header. All the headers link together through pointers. Its a singly linked list. This is where my question comes from. Since those pointers are stored within the allocated memory, will they continue to point to the correct location within that memory chunk after a realloc.
Quote:
Originally Posted by Paul McKenzie
I gave the answer. There is no such thing as changing the sizeof() a struct or any type at runtime. All sizes are fixed.
No, you gave an answer to a question that I never asked.
Quote:
Originally Posted by Paul McKenzie
Please explain the reason for this requirement.
Not quite sure. I'll be applying wrapper functions which redirect memory allocations to a file. Keeping everything one giant, non-fragmented block was a requirement of those wrappers. Seeing that I've never dealt with memory-mapped files, I couldn't tell you why that is.
Quote:
Originally Posted by Paul McKenzie
if you have user pointers pointing to the pool (the reseating of the pointers if the memory becomes invalidated).
Yes I know. That's why I don't have or allow user pointers and why I'm curious about the pointers stored within the allocated memory.
Re: C - Realloc, Linked Lists, and pointers
Quote:
Originally Posted by
JaySoyer
Yes I know. That's why I don't have or allow user pointers and why I'm curious about the pointers stored within the allocated memory.
Allocated memory is allocated memory. You deallocate it, that data that resided there cannot be retrieved without invoking undefined behaviour.
But what do you really mean by "pointers stored within allocated memory"? You call malloc() and an address is returned by the heap manager. That address is valid up until you call free(). Where and how is this pointer now "stored in allocated memory"?
Take scenario 2: You declare a pointer. So where is this pointer stored? It's usually on the stack or in whatever block designated by the linker to store global and static data. So again, how is this pointer moved from where it was declared into your allocated memory?
Regards,
Paul McKenzie
Re: C - Realloc, Linked Lists, and pointers
Quote:
Originally Posted by Paul McKenzie
But what do you really mean by "pointers stored within allocated memory"? You call malloc() and an address is returned by the heap manager. That address is valid up until you call free(). Where and how is this pointer now "stored in allocated memory"?
Bare with me. Say I do this initially. Variables have global scope.
PHP Code:
void* mBuffer = malloc(size); //Start of the memory buffer
void* mBuffFree = mBuffer; //Points to next available free memory block
Then later on I do the following in a function called WriteNodeHead() to add a new node. Lets assume this function accepts a bunch of const char* text1, const char* text2, ....etc.
PHP Code:
//Setting up the node header
NodeHeader* pHeader = (NodeHeader*) mBuffFree;
mBuffFree = pHeader + 1;
pHeader->node = mBuffFree;
pHeader->size = nodeSize; //Lets say I calculated nodeSize already
WriteTextIntoMemory(text1);
WriteTextIntoMemory(text2);
...etc.
//Linking with where the next node header will be. This is what
//I mean by a pointer stored within the allocated memory.
pheader->next = (NodeHeader*) mBuffFree;
The node writing function.
PHP Code:
WriteTextIntoMemory (const char* text) {
size_t* pOffset = (size_t*) mBuffFree;
char* pText = (char*) (pOffset + 1);
*pOffset = strlen(text);
memcpy(pText, text, *pOffset);
mBuffFree = pText + *pOffset; //Move buffer passed char array to next free location
}
Finally Nodeheader would be defined as:
PHP Code:
struct NodeHeader {
void* node;
size_t size;
NodeHeader* next;
};
Lets say I call WriteNodeHead() several times so i end up with a chain of linked heads/nodes. You can see I have locations within the allocated memory which point to other locations within the memory. I call it pointers stored within the allocated memory. Not sure what else to call them.
Re: C - Realloc, Linked Lists, and pointers
Here is what this all boils down to:
Take the case of free().
Code:
void* mBuffer = malloc(size); //Start of the memory buffer
void* mBuffFree = mBuffer; //Points to next available free memory block
//...
free(mBuffer);
All that work you did in the //... now becomes invalidated once free() is called. Any strings written there are gone (maybe not physically, but logically those strings no longer exist).
Take case 2, calling realloc()
Code:
void* mBuffer = malloc(size); //Start of the memory buffer
void* mBuffFree = mBuffer; //Points to next available free memory block
//...
mBuffer = realloc(/* whatever */);
The data that is between mBuffer and mBuffer + size is still valid, even if mBuffer changes address
However, if you have pointers pointing to the data within mBuffer and mBuffer+size -- then those pointers may now point to garbage after the realloc() call, depending on whether there was enough contiguous memory at the tail end of the original allocated block. So you can't count on realloc() returning the same pointer and just expanding the memory area.
Regards,
Paul McKenzie
Re: C - Realloc, Linked Lists, and pointers
Quote:
Originally Posted by
JaySoyer
PHP Code:
pheader->next = (NodeHeader*) mBuffFree;
note that this won't work in general if you ignore NodeHeader memory alignment requirements ...
regarding the memory grow issue, a guy in the winapi subforum had similar requirements sometime ago, take a look here. As you can see, the C winapi "solution" to this problem is just to return an error code notifying the user that the buffer is too small, hence asking him to repeat the operation from the start. This has the advantage of giving the user total freedom on choosing how to allocate the memory buffer.
That said, your use case seems different as your users are required to use malloc for their buffers ( you couldn't even talk of using realloc otherwise ) ... which makes this design awkward to say the least ...
Re: C - Realloc, Linked Lists, and pointers
Thanx for all the help guys. I went ahead and just did another malloc and then memcpy everything over and free the old memory block. However this still failed as those addresses which were pointers and memcopied over still pointed to the old (freed) memory. Not sure why I didn't realize this before but that's probably exactly what realloc would have done if not enough continuous mem was available. Solution was to store offsets instead of pointers. That way in a realloc, or even a memcpy, the linking of my nodes is maintained.
