0
\$\begingroup\$
pub struct FreeList<T: Copy, I: Copy> {
    items: Vec<Node<T, I>>,
    free: I,
}

union Node<T: Copy, I: Copy> {
    used: T,
    free: I,
}

impl<T: Copy, I: ID> FreeList<T, I> {
    pub fn new() -> Self {
        Self { items: Vec::new(), free: I::none() }
    }

    pub unsafe fn insert(&mut self, x: T) -> I {
        if self.free.is_none() {
            let i = I::from_usize(self.items.len());
            self.items.push(Node { used: x });
            i
        } else {
            let i = self.free;
            let slot = self.items.get_unchecked_mut(i.into_usize());
            self.free = slot.free;
            *slot = Node { used: x };
            i
        }
    }

    pub unsafe fn remove(&mut self, i: I) -> T {
        let slot = self.items.get_unchecked_mut(i.into_usize());
        let data = slot.used;
        *slot = Node { free: self.free };
        self.free = i;
        data
    }

    pub unsafe fn get(&self, i: I) -> &T {
        &self.items.get_unchecked(i.into_usize()).used
    }

    pub unsafe fn get_mut(&mut self, i: I) -> &mut T {
        &mut self.items.get_unchecked_mut(i.into_usize()).used
    }
}



fn main() {}



pub trait ID: Copy {
    fn from_usize(u: usize) -> Self;
    fn into_usize(self) -> usize;
    fn none() -> Self;
    fn is_none(self) -> bool;
}

This is just a freelist. There's a lot of unsafety, though, so I wanted to make sure that I got it right. In particular:

  • is insert always safe?
  • is remove safe as long as there isn't a use-after-remove?
  • is the drop code correct?
\$\endgroup\$
  • \$\begingroup\$ What is a freelist? Is it a free list, a variation on a linked list? \$\endgroup\$ – Mast Jan 29 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.