CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 13 of 13
  1. #1
    Join Date
    Jan 2012
    Location
    United States
    Posts
    12

    Question 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:
    voidpBuffer 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
    {
        
    NodepNode;
        
    size_t nodeSize;
        
    NodeHeaderpNext;

    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.
    Last edited by JaySoyer; February 4th, 2012 at 01:28 PM.

  2. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    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?

  3. #3
    Join Date
    Jan 2012
    Location
    United States
    Posts
    12

    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.

  4. #4
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: C - Realloc, Linked Lists, and pointers

    Quote Originally Posted by JaySoyer View Post
    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.

  5. #5
    Join Date
    Apr 1999
    Posts
    27,449

    Re: C - Realloc, Linked Lists, and pointers

    Quote Originally Posted by JaySoyer View Post
    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:
    Code:
    sizeof(Node)
    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

  6. #6
    Join Date
    Jan 2012
    Location
    United States
    Posts
    12

    Exclamation 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.
    Last edited by JaySoyer; February 4th, 2012 at 05:39 PM.

  7. #7
    Join Date
    Apr 1999
    Posts
    27,449

    Re: C - Realloc, Linked Lists, and pointers

    Quote Originally Posted by JaySoyer View Post
    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.
    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.
    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
    Last edited by Paul McKenzie; February 4th, 2012 at 06:31 PM.

  8. #8
    Join Date
    Jan 2012
    Location
    United States
    Posts
    12

    Unhappy 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.
    Last edited by JaySoyer; February 4th, 2012 at 07:21 PM.

  9. #9
    Join Date
    Apr 1999
    Posts
    27,449

    Re: C - Realloc, Linked Lists, and pointers

    Quote Originally Posted by JaySoyer View Post
    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

  10. #10
    Join Date
    Jan 2012
    Location
    United States
    Posts
    12

    Post 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:
    voidmBuffer malloc(size);    //Start of the memory buffer
    voidmBuffFree 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
    NodeHeaderpHeader = (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 chartext)   {
       
    size_tpOffset = (size_t*) mBuffFree;
       
    charpText = (char*) (pOffset 1);
       *
    pOffset strlen(text);
       
    memcpy(pTexttext, *pOffset); 
       
    mBuffFree pText + *pOffset;     //Move buffer passed char array to next free location

    Finally Nodeheader would be defined as:
    PHP Code:
    struct NodeHeader  {
      
    voidnode;
      
    size_t size;
      
    NodeHeadernext;
    }; 
    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.

  11. #11
    Join Date
    Apr 1999
    Posts
    27,449

    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

  12. #12
    Join Date
    Oct 2008
    Posts
    1,456

    Re: C - Realloc, Linked Lists, and pointers

    Quote Originally Posted by JaySoyer View Post
    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 ...

  13. #13
    Join Date
    Jan 2012
    Location
    United States
    Posts
    12

    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured