Связанный список в выделенном пространстве?
Я надеюсь, что этот вопрос будет не слишком веским для обсуждения, а для четкого ответа.
Я изучил C в университете и только начал писать свою первую полезную программу (то есть без спецификации). Я просто наткнулся на проблему, которой я до сих пор не занимался, и я думаю, что они не упоминали об этом в лекции:
Когда я выделяю память, которая может быть изменена, я не должен хранить указатели на адреса этого выделенного пространства. Потому что, когда я перераспределяю, пространство может быть перемещено в другое место, что делает каждый указатель на этот регион бесполезным. Это приводит меня к выводу, что я не могу хранить связанный список внутри пространства, так как каждый элемент «живет» где-то в этом пространстве, поскольку перераспределение может сделать недействительными все указатели «next» и «prev».
Это проблема, с которой я никогда не сталкивался, поэтому я хотел спросить вас, есть ли какое-то решение для этого. В частности: у меня есть область общей памяти, и я хочу сохранить в ней все свои данные, чтобы разные процессы могли работать с ней. Поскольку данные (строки) будут часто добавляться и удаляться и должны быть в определенном порядке, я подумал, что лучше всего использовать связанный список. Теперь я понял, что не могу сделать это таким образом. Или я просто слишком слеп, чтобы увидеть очевидное решение? Как бы вы пошли об этом? (Я не хочу хранить все это в файле, оно должно оставаться в (основной) памяти)
Спасибо и всего наилучшего,
Фил
Решение
Это Можно быть сделано за счет простоты и, следовательно, производительности. Вместо того, чтобы хранить указатели в общей памяти, вы должны хранить смещения от начала региона вместо. Затем, когда вы хотите «разыменовать» один из них, вы добавляете смещение к указателю на общую область.
Чтобы избежать ошибок, я бы сделал специальный тип для этого, в зависимости от фактический язык, который вы используете
С
//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;
Другие решения
Другой метод, который очень похож на метод смещения, предложенный Mooing Duck, — это массив и индексы массива.
Если каждый элемент списка имеет одинаковый размер, объявите указатель на массив этих элементов списка. Установите этот указатель на начало области памяти. Хранить смещения массива вместо указателей для предыдущего и следующего узлов. Теперь компилятор позаботится о добавлении смещений для вас.