Linked list in allocated space?

Question

I hope that this question will not be too weighted in the discussion, but in a clear answer.

I studied C at university and just started writing my first useful program (no spec). I just stumbled upon a problem that I still have not dealt with, and I think they did not mention this in the lecture:

When I allocate memory that can be modified, I should not store pointers to the addresses of this allocated space. Because when I redistribute, the space can be moved to another place, which makes each pointer to this region useless. This leads me to the conclusion that I cannot store a linked list inside a space, and each element lives somewhere in this space, since redistribution can invalidate all the next and prev pointers.

This is a problem that I have never encountered, so I wanted to ask you if there is any solution for this. In particular: I have a shared memory area and you want to save all my data in it so that different processes can work on it. Since data (rows) will be added and deleted frequently and should be in a specific order, I thought a linked list would be a better way. Now I realized that I can’t do this. Or am I too blind to see the obvious solution? How would you do that? (I do not want to store everything in a file, it should remain in the (main) memory)

thanks and best regards, phil

Answer 1

, , . , , . , "" , .

, , ,

 //seriously, this is one situation where I would find a global justified
 region_ptr region;

 //store these instead of pointers inside the memory region
 struct node_offset {ptrdiff_t offset};

 //used to get a temporary pointer from an offset in a region
 //the pointer is invalidated when the memory is reallocated
 //the pointer cannot be stored in the region
 node* get_node_ptr(node_offset offset) 
 {return (node*)((char*)region+offset.offset);}

 //used to get an offset from a pointer in a region
 //store offsets in the region, not pointers
 node_offset set_node_ptr(region* r, node* offset) 
 {node_offset o = {(char*)offset.offset-(char*)region}; return o;}

C++

 //seriously, this is one situation where I would find a global justified
 region_ptr region;

 //store these in the memory region
 //but you can pretend they're actual pointers
 template<class T>
 struct offset_ptr { 
     offset_ptr() : offset(0) {}

     T* get() const {return (T*)((char*)region + offset);}
     void set(T* ptr) {offset = (char*)ptr - (char*)region;}

     offset_ptr(T* ptr) {set(ptr);}
     offset_ptr& operator=(T* ptr) {set(ptr); return *this;}
     operator T*() const {return get();}
     T* operator->() const {return get();}
     T& operator*() const {return *get();}

 private:
     ptrdiff_t offset;
 };

 template<class T>
 struct offset_delete {
     typedef offset_ptr<T> pointer;
     void operator()(offset_ptr<T> ptr) const {ptr->~T();}
 };
 //std::unique_ptr<node, offset_delete<node>> node_ptr;

Answer 2

, , Mooing Duck, .

, . . prev . .