Copying data between linked list nodes

Question

I'm writing a virtual machine and currently working on its memory which is implemented using a linked list. I have implemented malloc which adds a new node to the list, free which marks a node to be reused by malloc and now I am working on realloc. The problem i have is that I cannot copy data between two nodes of the linked list due to there being two mutable references, here is a minimum example:

use std::collections::LinkedList;

struct MemoryBlock {
    address: u64,
    size: u64,
    data: Vec<u8>
}

struct Memory {
    blocks: LinkedList<MemoryBlock>,
}

impl Memory {
    fn malloc(&mut self, alloc_size: u64) -> u64 {
        self.blocks.push_back(MemoryBlock {
            address: 1,
            size: alloc_size,
            data: vec![0x00]
        });
        
        1
    }

    fn realloc(&mut self, address: u64, new_size: u64) -> u64 {
        let new_address = self.malloc(new_size);
        
        let mut old_block = self.blocks.iter_mut().find(|b| b.address == address).unwrap();
        let mut new_block = self.blocks.iter_mut().find(|b| b.address == new_address).unwrap();
        
        new_block.data[0] = old_block.data[0];
        
        new_address
    }
}

fn main() {
    let mut memory = Memory {
        blocks: LinkedList::new()
    };
    
    memory.blocks.push_back(MemoryBlock {
        address: 0,
        size: 1,
        data: vec![0x00]
    });
    
    memory.realloc(0, 2);
}

I have tried to make 'old_block' immutable but then I cannot have one mutable and one immutable borrow at the same time. Is there any way to structure my code differently or any other method (other than unsafe) to get it to work? I know I can use a vector and then use slices as a 'hack' to get it done but I would prefer to use a linked list if possible.

I think you are attempting to set new_block to the old_block without copying, hence the compiler is complaining, as you are still holding references to the same linked list. You need to use .clone() to properly copy the value before taking a second reference (and esnure MemoryBlock derives Clone) or use drain_filter to remove the block before reassigning it (probably not what you want). Something like let old_block = self.blocks.iter().find(|b| b.address == address).unwrap().clone(); should do the trick, assuming #[derive(Clone)] on MemoryBlock — somnium
– somnium, Commented Apr 20, 2022 at 15:15
@somnium Wouldn't that also clone the 'data' vector? This vector will go up to a gigabyte in size so i assume it could cause some memory issues — Daniel Nowak
– Daniel Nowak, Commented Apr 20, 2022 at 15:35

Dogbert · Accepted Answer · 2022-04-20 15:58:03Z

2

You can restructure the code so that the Rust compiler knows that old_block and new_block point to different locations. This will also be more efficient as the LinkedList is only traversed once.

fn realloc(&mut self, address: u64, new_size: u64) -> u64 {
    let new_address = self.malloc(new_size);

    let mut old_block = None;
    let mut new_block = None;

    for block in &mut self.blocks {
        if block.address == address {
            old_block = Some(block);
        } else if block.address == new_address {
            new_block = Some(block);
        }
    }

    new_block.unwrap().data[0] = old_block.unwrap().data[0];

    new_address
}

Playground

answered Apr 20, 2022 at 15:58

Dogbert

224k43 gold badges419 silver badges416 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Daniel Nowak Over a year ago

That's exactly what i needed!

Collectives™ on Stack Overflow

Copying data between linked list nodes

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related