BitSet with up to 32 dynamic 128bit chunks. Can store values 0..4096. Sparse memory representation.

dynamic_bitset_128.rs

#![feature(i128_type)]

struct BitSet {
    offsets: u32,
    chunks: Vec<u128>,
}

impl BitSet {
    fn new() -> Self {
        Self {
            offsets: 0,
            chunks: Vec::new(),
        }
    }
    
    fn insert(&mut self, val: u32) {
        let index = (val / 128) as usize;
        let exists_chunk = (self.offsets & 1 << index) > 0;
        let c = 1 << val % 128;
        if !exists_chunk {
            println!("Chunk {} does not exist, creating...", index);
            let index = self.chunk_index(val / 128);
            self.chunks.insert(index, c);
            self.offsets |= 1 << val / 128;
        } else {
            let index = self.chunk_index(val / 128);
            unsafe {
                *self.chunks.get_unchecked_mut(index) |= c;
            }
        }
    }
    
    fn contains(&self, val: u32) -> bool {
        let index = (val / 128) as usize;
        let exists_chunk = (self.offsets & 1 << index) > 0;
        if exists_chunk {
            let index = self.chunk_index(val / 128);
            unsafe {
                self.chunks.get_unchecked(index) & (1 << val % 128) > 0
            }
        } else {
            false
        }
    }
    
    fn chunk_index(&self, bit_pos: u32) -> usize {
        let mut count = 0;
        for i in 0..bit_pos {
            if self.offsets & (1 << i) > 0 {
                count += 1;
            }
        }
        count
    }
}

fn main() {
    let mut set = BitSet::new();
    
    println!("1234:");
    println!("{}", set.contains(1234));
    set.insert(1234);
    println!("{}", set.contains(1234));
    set.insert(1234);
    
    println!("\n4000:");
    println!("{}", set.contains(4000));
    set.insert(4000);
    println!("{}", set.contains(4000));
    
    println!("\n2:");
    println!("{}", set.contains(2));
    set.insert(2);
    println!("{}", set.contains(2));
    
    println!("\n95:");
    println!("{}", set.contains(95));
    set.insert(95);
    println!("{}", set.contains(95));
}