How to implement a custom slice for a Bitvector

user_2611436 0
Viewed 366

I'm implementing a Bitvector. My question is - How do I implement the slice functionality? Here is my code (things I've tried follow after the code):

use core::ops::Range;
use std::ops::Index;

pub struct Bitvec {
    vec: Vec<u8>,
}

impl Bitvec {
    pub fn new(capacity: usize) -> Bitvec {
        Bitvec {
            vec: Vec::with_capacity(capacity),
        }
    }

    pub fn bit_at(&self, index: usize) -> bool {
        let mask = 2u8.pow(7 - (index % 8) as u32);
        self.vec.get(index / 8).unwrap() & mask == mask
    }

    pub fn push(&mut self, val: u8) {
        self.vec.push(val);
    }
}

impl Index<usize> for Bitvec {
    type Output = bool;
    fn index(&self, index: usize) -> &Self::Output {
        match self.bit_at(index) {
            true => &true,
            false => &false,
        }
    }
}

impl Index<Range<usize> for Bitvec {
    type Output = ??;
    fn index(&self, index: Range<usize>) -> &Self::Output {
        //What should go here?
    }
}

fn main() {
    let mut bv = Bitvec::new(20);
    bv.push(0b1011_0011);
    assert_eq!(bv.bit_at(0), true);
    assert_eq!(bv.bit_at(1), false);

    assert_eq!(bv[0], true);
    assert_eq!(bv[1], false);

    let slice = bv[2..4]; //should return a slice that represents the two bits of [11]
}

What should the impl of Index<Range> for Bitvec return?

Things I've tried:

  • Creating a struct BitSlice that holds a start and an end and returning that. I end up fighting with the borrow checker with lifetimes since I need to have the BitSlice hold a reference to the Bitvec. Also can't return an &BitSlice from the index(...) function.

  • Having the Bitvec own a BitSlice but that runs into similar issues where the BitSlice and the Bitvec refer to each other

  • Having the Bitvec own an Option but also run into issues with lifetimes.

rust slice data-structures boolean
1 Answers

Slice types like &str or &[u8] are fat pointers, containing a pointer to some data and a length. The type &[T] is syntactic sugar for a struct resembling this:

struct Slice<'a, T> {
    data: *const T,
    len: usize,
    _lifetime: PhantomData<&'a T>,
}

The caveat is that the ABI is unstable, so you can't make any assumptions about the order of those fields.

A pointer is always to a byte, not a bit, so a fat pointer to a BitVec slice would also need to contain a bit offset for where the slice begins within the first byte:

pub struct BitSlice<'a> {
    offset: u8,
    len: usize,
    ptr: *const u8,
    _lifetime: PhantomData<&'a u8>,
}

You can construct one of these, but the Index::index trait method returns &Self::Output. There is no way to transmute a BitSlice<'a> into a &'a [T].

It might be possible to shoe-horn the length and offset into a single usize and be extremely careful about how that is accessed. Here's a semi-complete sketch, but there are likely soundness holes in that implementation. Certainly, if you are a Rust beginner, you should not be attempting it!

user_4937290
Related