7
\$\begingroup\$

As an exercise to learn Rust I've decided to write a Bit Vector library, furthermore I also intend to use it later because my version can share slices of the bit vector between threads whereas the existing bit_vec library cannot do that and development does not seem to be active anymore.

The library has the following functionality:

  • Create a bit vector backed by a storage such as u8, u16, u32, u64 or usize.
  • Set a bit in the bit vector.
  • Get a bit from the bit vector.
  • Split the bit vector into either immutable or mutable bit slices.
  • Retrieve an iterator over the bit vector or bit slices.

I have tried to mimic Vec<T> as much as possible, it for example has a vec.split_at() resp vec.split_at_mut() method that return slices ([T]) to the original vector, the following types are available in this library:

  • BitStorage: A trait with implementation that specifies which types are eligible for storing the bits, existing types that fit this definition are u8, u16, u32, u64 and usize, but an user could also define their own types.
  • BitVector: The struct that represents the bit vector.
  • BitSlice: The struct that represents the immutable bit slice.
  • BitSliceMut: The struct that represents the mutable bit slice.

Below is the code to be reviewed, all code including unit tests can be found on my GitHub project page and I'd especially like advice on reducing code duplication.

The main lib.rs file:

extern crate num;

macro_rules! bool_ref {
    ($cond:expr) => (if $cond { &TRUE } else { &FALSE })
}

mod bit_storage;
mod bit_vector;
mod bit_slice;
mod bit_slice_mut;

pub use bit_storage::BitStorage;
pub use bit_vector::BitVector;
pub use bit_slice::BitSlice;
pub use bit_slice_mut::BitSliceMut;

static TRUE: bool = true;
static FALSE: bool = false;

The bit_storage.rs file:

use std::mem;
use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Not,Shl,ShlAssign,Shr,ShrAssign};
use num;
use num::{One,Zero,Unsigned,NumCast,Bounded};

pub trait BitStorage: Sized +
    BitAnd<Self, Output = Self> +
    BitAndAssign<Self> +
    BitOr<Self, Output = Self> +
    BitOrAssign<Self> +
    BitXor<Self, Output = Self> +
    BitXorAssign<Self> +
    Not<Output = Self> +
    Shl<Self, Output = Self> +
    ShlAssign<Self> +
    Shr<Self, Output = Self> +
    ShrAssign<Self> +
    Eq + Zero + One + Unsigned + NumCast + Bounded + Copy {
        fn storage_size() -> usize;

        fn set(storage: &mut Self, storage_index: Self, value: bool);

        fn get(storage: &Self, storage_index: Self) -> bool;

        fn compute_data_index(index: usize) -> usize;

        fn compute_remainder(index: usize) -> Self;

        fn compute_data_index_and_remainder(index: usize) -> (usize, Self);
}

impl<S> BitStorage for S where S: Sized +
    BitAnd<S, Output = S> +
    BitAndAssign<S> +
    BitOr<S, Output = S> +
    BitOrAssign<S> +
    BitXor<S, Output = S> +
    BitXorAssign<S> +
    Not<Output = S> +
    Shl<S, Output = S> +
    ShlAssign<S> +
    Shr<S, Output = S> +
    ShrAssign<S> +
    Eq + Zero + One + Unsigned + NumCast + Bounded + Copy {
        #[inline]
        fn storage_size() -> usize {
            mem::size_of::<S>() * 8
        }

        #[inline]
        fn set(storage: &mut S, storage_index: S, value: bool) {
            if value {
                *storage |= S::one() << storage_index;
            }
            else {
                *storage &= !(S::one() << storage_index);
            }
        }

        #[inline]
        fn get(storage: &S, storage_index: S) -> bool {
            (*storage & (S::one() << storage_index)) != S::zero()
        }

        #[inline]
        fn compute_data_index(index: usize) -> usize {
            index / S::storage_size()
        }

        #[inline]
        fn compute_remainder(index: usize) -> S {
            let remainder = index % S::storage_size();
            // we know that remainder is always smaller or equal to the size that S can hold
            // for example if S = u8 then remainder <= 2^8 - 1
            let remainder: S = num::cast(remainder).unwrap();
            remainder
        }

        #[inline]
        fn compute_data_index_and_remainder(index: usize) -> (usize, S) {
            (S::compute_data_index(index), S::compute_remainder(index))
        }
}

The bit_vector.rs file:

use num;

use std::ops::Index;

use BitStorage;
use BitSlice;
use BitSliceMut;

use TRUE;
use FALSE;

pub struct BitVector<S: BitStorage> {
    data: Vec<S>,
    capacity: usize
}

impl<S: BitStorage> BitVector<S> {
    pub fn with_capacity(capacity: usize, default: bool) -> BitVector<S> {
        let len = (capacity / S::storage_size()) + 1;
        let default = if default { S::max_value() } else { S::zero() };
        BitVector { 
            data: vec![default; len],
            capacity: capacity
        }
    }

    pub fn get(&self, index: usize) -> Option<bool> {
        match self.index_in_bounds(index) {
            true => Some(self.get_unchecked(index)),
            false => None
        }
    }

    pub fn set(&mut self, index: usize, value: bool) {
        self.panic_index_bounds(index);
        let (data_index, remainder) = S::compute_data_index_and_remainder(index);
        S::set(&mut self.data[data_index], remainder, value);
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }

    pub fn split_at(&self, index: usize) -> (BitSlice<S>, BitSlice<S>) {
        self.panic_index_not_on_storage_bound(index);
        let data_index = S::compute_data_index(index);
        let (capacity_left, capacity_right) = self.compute_capacities(index);
        let (data_left, data_right) = self.data.split_at(data_index);

        unsafe {
            let left = BitSlice::from_pointer(data_left.as_ptr(), capacity_left);
            let right = BitSlice::from_pointer(data_right.as_ptr(), capacity_right);
            (left, right)
        }
    }

    pub fn split_at_mut(&mut self, index: usize) -> (BitSliceMut<S>, BitSliceMut<S>) {
        self.panic_index_not_on_storage_bound(index);
        let data_index = S::compute_data_index(index);
        let (capacity_left, capacity_right) = self.compute_capacities(index);
        let (data_left, data_right) = self.data.split_at_mut(data_index);

        unsafe {
            let left = BitSliceMut::from_pointer(data_left.as_mut_ptr(), capacity_left);
            let right = BitSliceMut::from_pointer(data_right.as_mut_ptr(), capacity_right);
            (left, right)
        }
    }

    pub fn iter(&self) -> Iter<S> {
        Iter {
            data: &self.data,
            capacity: self.capacity,
            data_index_counter: 0,
            remainder_counter: 0
        }
    }

    #[inline]
    fn get_unchecked(&self, index: usize) -> bool {
        let (data_index, remainder) = S::compute_data_index_and_remainder(index);
        self.get_unchecked_by_data_index_and_remainder(data_index, remainder)
    }

    #[inline]
    fn get_unchecked_by_data_index_and_remainder(&self, data_index: usize, remainder: S) -> bool {
        S::get(&self.data[data_index], remainder)
    }

    #[inline]
    fn compute_capacities(&self, index_to_split: usize) -> (usize, usize) {
        (index_to_split, self.capacity - index_to_split)
    }

    #[inline]
    fn index_in_bounds(&self, index: usize) -> bool {
        index < self.capacity
    }

    #[inline]
    fn panic_index_bounds(&self, index: usize) {
        if !self.index_in_bounds(index) {
            panic!("Index out of bounds. Length = {}, Index = {}", self.capacity, index);
        }
    }

    #[inline]
    fn panic_index_not_on_storage_bound(&self, index: usize) {
        if index % S::storage_size() != 0 {
            panic!("Index not on storage bound. Storage size = {}, Index = {}", S::storage_size(), index);
        }
    }
}

impl<S: BitStorage> Index<usize> for BitVector<S> {
    type Output = bool;

    fn index(&self, index: usize) -> &bool {
        self.panic_index_bounds(index);
        bool_ref!(self.get_unchecked(index))
    }
}

impl<'a, S: BitStorage + 'a> IntoIterator for &'a BitVector<S> {
    type Item = bool;
    type IntoIter = Iter<'a, S>;

    fn into_iter(self) -> Iter<'a, S> {
        self.iter()
    }
}

pub struct Iter<'a, S: BitStorage + 'a> {
    data: &'a Vec<S>,
    capacity: usize,
    data_index_counter: usize,
    remainder_counter: usize
}

impl<'a, S: BitStorage + 'a> Iterator for Iter<'a, S> {
    type Item = bool;

    fn next(&mut self) -> Option<bool> {
        let remainder: S = num::cast(self.remainder_counter).unwrap();
        let next = self.get_unchecked_by_data_index_and_remainder(self.data_index_counter, remainder);

        if self.calculate_index() == self.capacity {
            return None;
        }

        self.remainder_counter += 1;
        if self.remainder_counter == S::storage_size() {
            self.remainder_counter = 0;
            self.data_index_counter += 1;
        }

        Some(next)
    }
}

impl<'a, S: BitStorage + 'a> Iter<'a, S> {
    #[inline]
    fn get_unchecked_by_data_index_and_remainder(&self, data_index: usize, remainder: S) -> bool {
        S::get(&self.data[data_index], remainder)
    }

    #[inline]
    fn calculate_index(&self) -> usize {
        (self.data_index_counter * S::storage_size()) + self.remainder_counter
    }
}

The bit_slice.rs file:

use num;

use std::marker::PhantomData;
use std::ops::Index;

use BitStorage;

use TRUE;
use FALSE;

pub struct BitSlice<'a, S: BitStorage + 'a> {
    pointer: *const S,
    capacity: usize,
    phantom: PhantomData<&'a S>
}

unsafe impl<'a, S: BitStorage + 'a> Send for BitSlice<'a, S> {}
unsafe impl<'a, S: BitStorage + 'a> Sync for BitSlice<'a, S> {}

impl<'a, S: BitStorage + 'a> BitSlice<'a, S> {
    pub unsafe fn from_pointer(pointer: *const S, capacity: usize) -> BitSlice<'a, S> {
        BitSlice {
            pointer: pointer,
            capacity: capacity,
            phantom: PhantomData
        }
    }

    pub fn get(&self, index: usize) -> Option<bool> {
        match self.index_in_bounds(index) {
            true => Some(self.get_unchecked(index)),
            false => None
        }
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }

    pub fn split_at(&self, index: usize) -> (BitSlice<S>, BitSlice<S>) {
        self.panic_index_not_on_storage_bound(index);
        let data_index = S::compute_data_index(index);
        let (capacity_left, capacity_right) = self.compute_capacities(index);
        let (pointer_left, pointer_right) = self.compute_pointers(data_index);

        unsafe {
            let left = BitSlice::from_pointer(pointer_left, capacity_left);
            let right = BitSlice::from_pointer(pointer_right, capacity_right);
            (left, right)
        }
    }

    pub fn iter(&self) -> Iter<S> {
        Iter {
            pointer: self.pointer,
            capacity: self.capacity,
            data_index_counter: 0,
            remainder_counter: 0,
            phantom: PhantomData
        }
    }

    #[inline]
    fn get_unchecked(&self, index: usize) -> bool {
        let (data_index, remainder) = S::compute_data_index_and_remainder(index);
        self.get_unchecked_by_data_index_and_remainder(data_index, remainder)
    }

    #[inline]
    fn get_unchecked_by_data_index_and_remainder(&self, data_index: usize, remainder: S) -> bool {
        let element = unsafe { *self.pointer.offset(data_index as isize) };
        S::get(&element, remainder)
    }

    #[inline]
    fn compute_capacities(&self, index_to_split: usize) -> (usize, usize) {
        (index_to_split, self.capacity - index_to_split)
    }

    #[inline]
    fn compute_pointers(&self, data_index_to_split: usize) -> (*const S, *const S) {
        let pointer_left = self.pointer;
        let pointer_right = unsafe { self.pointer.offset(data_index_to_split as isize) };
        (pointer_left, pointer_right)
    }

    #[inline]
    fn index_in_bounds(&self, index: usize) -> bool {
        index < self.capacity
    }

    #[inline]
    fn panic_index_bounds(&self, index: usize) {
        if !self.index_in_bounds(index) {
            panic!("Index out of bounds. Length = {}, Index = {}", self.capacity, index);
        }
    }

    #[inline]
    fn panic_index_not_on_storage_bound(&self, index: usize) {
        if index % S::storage_size() != 0 {
            panic!("Index not on storage bound. Storage size = {}, Index = {}", S::storage_size(), index);
        }
    }
}

impl<'a, S: BitStorage + 'a> Index<usize> for BitSlice<'a, S> {
    type Output = bool;

    fn index(&self, index: usize) -> &bool {
        self.panic_index_bounds(index);
        bool_ref!(self.get_unchecked(index))
    }
}

pub struct Iter<'a, S: BitStorage + 'a> {
    pointer: *const S,
    capacity: usize,
    data_index_counter: usize,
    remainder_counter: usize,
    phantom: PhantomData<&'a S>
}

unsafe impl<'a, S: BitStorage + 'a> Send for Iter<'a, S> {}
unsafe impl<'a, S: BitStorage + 'a> Sync for Iter<'a, S> {}

impl<'a, S: BitStorage + 'a> IntoIterator for &'a BitSlice<'a, S> {
    type Item = bool;
    type IntoIter = Iter<'a, S>;

    fn into_iter(self) -> Iter<'a, S> {
        self.iter()
    }
}

impl<'a, S: BitStorage + 'a> Iterator for Iter<'a, S> {
    type Item = bool;

    fn next(&mut self) -> Option<bool> {
        let remainder: S = num::cast(self.remainder_counter).unwrap();
        let next = self.get_unchecked_by_data_index_and_remainder(self.data_index_counter, remainder);

        if self.calculate_index() == self.capacity {
            return None;
        }

        self.remainder_counter += 1;
        if self.remainder_counter == S::storage_size() {
            self.remainder_counter = 0;
            self.data_index_counter += 1;
        }

        Some(next)
    }
}

impl<'a, S: BitStorage + 'a> Iter<'a, S> {
    #[inline]
    fn get_unchecked_by_data_index_and_remainder(&self, data_index: usize, remainder: S) -> bool {
        let element = unsafe { *self.pointer.offset(data_index as isize) };
        S::get(&element, remainder)
    }

    #[inline]
    fn calculate_index(&self) -> usize {
        (self.data_index_counter * S::storage_size()) + self.remainder_counter
    }
}

The bit_slice_mut.rs file:

use num;

use std::marker::PhantomData;
use std::ops::Index;

use BitStorage;
use BitSlice;

use TRUE;
use FALSE;

pub struct BitSliceMut<'a, S: BitStorage + 'a> {
    pointer: *mut S,
    capacity: usize,
    phantom: PhantomData<&'a S>
}

unsafe impl<'a, S: BitStorage + 'a> Send for BitSliceMut<'a, S> {}
unsafe impl<'a, S: BitStorage + 'a> Sync for BitSliceMut<'a, S> {}

impl<'a, S: BitStorage + 'a> BitSliceMut<'a, S> {
    pub unsafe fn from_pointer(pointer: *mut S, capacity: usize) -> BitSliceMut<'a, S> {
        BitSliceMut {
            pointer: pointer,
            capacity: capacity,
            phantom: PhantomData
        }
    }

    pub fn get(&self, index: usize) -> Option<bool> {
        match self.index_in_bounds(index) {
            true => Some(self.get_unchecked(index)),
            false => None
        }
    }

    pub fn set(&mut self, index: usize, value: bool) {
        self.panic_index_bounds(index);
        let (data_index, remainder) = S::compute_data_index_and_remainder(index);
        unsafe {
            let element_pointer = self.pointer.offset(data_index as isize);
            S::set(&mut *element_pointer, remainder, value);
        }
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }

    pub fn split_at(&self, index: usize) -> (BitSlice<S>, BitSlice<S>) {
        self.panic_index_not_on_storage_bound(index);
        let data_index = S::compute_data_index(index);
        let (capacity_left, capacity_right) = self.compute_capacities(index);
        let (pointer_left, pointer_right) = self.compute_pointers(data_index);

        unsafe {
            let left = BitSlice::from_pointer(pointer_left, capacity_left);
            let right = BitSlice::from_pointer(pointer_right, capacity_right);
            (left, right)
        }
    }

    pub fn split_at_mut(&mut self, index: usize) -> (BitSliceMut<S>, BitSliceMut<S>) {
        self.panic_index_not_on_storage_bound(index);
        let data_index = S::compute_data_index(index);
        let (capacity_left, capacity_right) = self.compute_capacities(index);
        let (pointer_left, pointer_right) = self.compute_mut_pointers(data_index);

        unsafe {
            let left = BitSliceMut::from_pointer(pointer_left, capacity_left);
            let right = BitSliceMut::from_pointer(pointer_right, capacity_right);
            (left, right)
        }
    }

    pub fn iter(&self) -> Iter<S> {
        Iter {
            pointer: self.pointer,
            capacity: self.capacity,
            data_index_counter: 0,
            remainder_counter: 0,
            phantom: PhantomData
        }
    }

    #[inline]
    fn get_unchecked(&self, index: usize) -> bool {
        let (data_index, remainder) = S::compute_data_index_and_remainder(index);
        self.get_unchecked_by_data_index_and_remainder(data_index, remainder)
    }

    #[inline]
    fn get_unchecked_by_data_index_and_remainder(&self, data_index: usize, remainder: S) -> bool {
        let element = unsafe { *self.pointer.offset(data_index as isize) };
        S::get(&element, remainder)
    }

    #[inline]
    fn compute_capacities(&self, index_to_split: usize) -> (usize, usize) {
        (index_to_split, self.capacity - index_to_split)
    }

    #[inline]
    fn compute_pointers(&self, data_index_to_split: usize) -> (*const S, *const S) {
        let pointer_left = self.pointer;
        let pointer_right = unsafe { self.pointer.offset(data_index_to_split as isize) };
        (pointer_left, pointer_right)
    }

    #[inline]
    fn compute_mut_pointers(&self, data_index_to_split: usize) -> (*mut S, *mut S) {
        let (pointer_left, pointer_right) = self.compute_pointers(data_index_to_split);
        (pointer_left as *mut _, pointer_right as *mut _)
    }


    #[inline]
    fn index_in_bounds(&self, index: usize) -> bool {
        index < self.capacity
    }

    #[inline]
    fn panic_index_bounds(&self, index: usize) {
        if !self.index_in_bounds(index) {
            panic!("Index out of bounds. Length = {}, Index = {}", self.capacity, index);
        }
    }

    #[inline]
    fn panic_index_not_on_storage_bound(&self, index: usize) {
        if index % S::storage_size() != 0 {
            panic!("Index not on storage bound. Storage size = {}, Index = {}", S::storage_size(), index);
        }
    }
}

impl<'a, S: BitStorage + 'a> Index<usize> for BitSliceMut<'a, S> {
    type Output = bool;

    fn index(&self, index: usize) -> &bool {
        self.panic_index_bounds(index);
        bool_ref!(self.get_unchecked(index))
    }
}

pub struct Iter<'a, S: BitStorage + 'a> {
    pointer: *mut S,
    capacity: usize,
    data_index_counter: usize,
    remainder_counter: usize,
    phantom: PhantomData<&'a S>
}

unsafe impl<'a, S: BitStorage + 'a> Send for Iter<'a, S> {}
unsafe impl<'a, S: BitStorage + 'a> Sync for Iter<'a, S> {}

impl<'a, S: BitStorage + 'a> IntoIterator for &'a BitSliceMut<'a, S> {
    type Item = bool;
    type IntoIter = Iter<'a, S>;

    fn into_iter(self) -> Iter<'a, S> {
        self.iter()
    }
}

impl<'a, S: BitStorage + 'a> Iterator for Iter<'a, S> {
    type Item = bool;

    fn next(&mut self) -> Option<bool> {
        let remainder: S = num::cast(self.remainder_counter).unwrap();
        let next = self.get_unchecked_by_data_index_and_remainder(self.data_index_counter, remainder);

        if self.calculate_index() == self.capacity {
            return None;
        }

        self.remainder_counter += 1;
        if self.remainder_counter == S::storage_size() {
            self.remainder_counter = 0;
            self.data_index_counter += 1;
        }

        Some(next)
    }
}

impl<'a, S: BitStorage + 'a> Iter<'a, S> {
    #[inline]
    fn get_unchecked_by_data_index_and_remainder(&self, data_index: usize, remainder: S) -> bool {
        let element = unsafe { *self.pointer.offset(data_index as isize) };
        S::get(&element, remainder)
    }

    #[inline]
    fn calculate_index(&self) -> usize {
        (self.data_index_counter * S::storage_size()) + self.remainder_counter
    }
}
\$\endgroup\$
4
\$\begingroup\$

There are some correctness issues with this code that need to be addressed immediately.

  1. There is no need to use pointers for the BitSlice(Mut). These should happily accept regular slices as the backing storage.

  2. Check if you are going to go off the end of the vector before doing it! The code for the slice iterators currently looks like this:

    let next = self.get_unchecked_by_data_index_and_remainder(self.data_index_counter, remainder);
    if self.calculate_index() == self.capacity { return None; }
    

    but it should be

    if self.calculate_index() == self.capacity { return None; }
    let next = self.get_unchecked_by_data_index_and_remainder(self.data_index_counter, remainder);
    

    This was hidden from you due to the use of pointers.

  3. I do not believe that it the Send / Sync implementations are correct. I did not test, but I believe that you could drop the underlying BitVec, leaving the pointers dangling. You shouldn't need these after switching to slices, anyway.

You should become familiar with tools like Valgrind if you want to do pointer-level work. Additionally, tools like quickcheck may help you explore a larger space of inputs with which to trigger bad behavior.


Here's the stylistic things I saw before the correctness ones above:

  1. Use &self or &mut self if the first argument is a &Self, specifically on the traits. You can still call it with the long form of Universal Function Call Syntax (UFCS), but this also allows method syntax:

    // definition
    fn set(&mut self, storage_index: Self, value: bool);
    fn get(&self, storage_index: Self) -> bool;
    
    // call site
    self.data[data_index].get(remainder)
    
  2. Why increment the capacity by 1 at creation time? Feels like it's supposed to be rounding up? If so, it should be either documented by a comment or a well-named method. Consider using floats and ceiling to get an accurate value, instead of adding overhead when the value fits perfectly.

  3. When I got to split_at, my first thought was "What about splitting at a section inside a byte?". This leads to my next point...

  4. You have to have documentation for public functions that do non-obvious things. Method names and types serve as a good base level of documentation, but they aren't sufficient. Panic conditions should especially be documented!

  5. You should include the conditions that make unsafe code not unsafe inside the unsafe block. This helps future programmers understand the preconditions and prevents them from being split up.

  6. The "unchecked" methods call the underlying slice / vectors Idx operation, which panics on out of bounds. It's likely you should be calling the underlying "unchecked" methods.

  7. I would then expect the "unchecked" methods to be unsafe as you could easily walk off the array and into undefined memory.

  8. Marking non-public functions inline probably has no effect. inline means to include a raw form of the code in the compiled library so that downstream consumers can choose to inline it. If it's private, nothing downstream can use it. Note that inline != inline(always).

  9. The iterators could be built on top of the slice / Vec iterator instead of reindexing into them each time.

  10. "Capacity" is a strange name. The capacity is how many values a vector could hold, size is how many it is holding. If I use 1 bit in a u64, the capacity should be 64 and the size should be 1.

At this point, I saw the correctness issues and stopped looking at idiomatic issues.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.