Changeset - 3740bd8ebfdd
[Not reviewed]
0 1 0
Christopher Esterhuyse - 5 years ago 2020-02-14 11:46:13
christopher.esterhuyse@gmail.com
trying out a matrix representation for components
1 file changed with 1 insertions and 43 deletions:
0 comments (0 inline, 0 general)
src/runtime/ecs.rs
Show inline comments
 
@@ -30,226 +30,184 @@ impl BitSet {
 
                self.0.push(!0u32);
 
            } else {
 
                if end > 0 {
 
                    // #end ones, with a (32-end) prefix of zeroes
 
                    self.0.push(!0u32 >> (32 - end));
 
                }
 
                return;
 
            }
 
        }
 
    }
 
    #[inline(always)]
 
    fn index_decomposed(index: usize) -> [usize; 2] {
 
        // [chunk_index, chunk_bit]
 
        [index / 32, index % 32]
 
    }
 
    fn test(&self, at: usize) -> bool {
 
        let [chunk_index, chunk_bit] = Self::index_decomposed(at);
 
        match self.0.get(chunk_index) {
 
            None => false,
 
            Some(&chunk) => (chunk & (1 << chunk_bit)) != 0,
 
        }
 
    }
 
    fn set(&mut self, at: usize) {
 
        let [chunk_index, chunk_bit] = Self::index_decomposed(at);
 
        if chunk_index >= self.0.len() {
 
            self.0.resize(chunk_index + 1, 0u32);
 
        }
 
        let chunk = unsafe {
 
            // SAFE! previous line ensures sufficient size
 
            self.0.get_unchecked_mut(chunk_index)
 
        };
 
        *chunk |= 1 << chunk_bit;
 
    }
 
    fn unset(&mut self, at: usize) {
 
        let [chunk_index, chunk_bit] = Self::index_decomposed(at);
 
        if chunk_index < self.0.len() {
 
            let chunk = unsafe {
 
                // SAFE! previous line ensures sufficient size
 
                self.0.get_unchecked_mut(chunk_index)
 
            };
 
            *chunk &= !(1 << chunk_bit);
 
            while let Some(0u32) = self.0.iter().copied().last() {
 
                self.0.pop();
 
            }
 
        }
 
    }
 
}
 

	
 
#[derive(Debug, Default)]
 
struct BitMasks(HashMap<(ChannelId, bool), BitSet>);
 

	
 
struct BitChunkIter<I: Iterator<Item = u32>> {
 
    chunk_iter: I,
 
    next_bit_index: usize,
 
    cached: Option<u32>, // None <=> iterator is done
 
}
 

	
 
impl<I: Iterator<Item = u32>> BitChunkIter<I> {
 
    fn new(mut chunk_iter: I) -> Self {
 
        let cached = chunk_iter.next();
 
        Self { chunk_iter, next_bit_index: 0, cached }
 
    }
 
}
 
impl<I: Iterator<Item = u32>> Iterator for BitChunkIter<I> {
 
    type Item = usize;
 
    fn next(&mut self) -> Option<Self::Item> {
 
        loop {
 
            println!("LOOP");
 
            // get cached chunk. If none exists, iterator is done.
 
            let mut chunk = self.cached?;
 
            if chunk == 0 {
 
                // self.next_bit_index jumps to next multiple of 32
 
                self.next_bit_index = (self.next_bit_index + 32) & !(32 - 1);
 
                self.cached = self.chunk_iter.next();
 
                continue;
 
            }
 
            // this chunk encodes 1+ Items to yield
 
            // shift the contents of chunk until the least significant bit is 1
 

	
 
            #[inline(always)]
 
            fn shifty(chunk: &mut u32, shift_by: usize, next_bit_index: &mut usize) {
 
                if *chunk & ((1 << shift_by) - 1) == 0 {
 
                    *next_bit_index += shift_by;
 
                    *chunk >>= shift_by;
 
                }
 
                println!("{:#032b}", *chunk);
 
            }
 
            shifty(&mut chunk, 16, &mut self.next_bit_index);
 
            shifty(&mut chunk, 08, &mut self.next_bit_index);
 
            shifty(&mut chunk, 04, &mut self.next_bit_index);
 
            shifty(&mut chunk, 02, &mut self.next_bit_index);
 
            shifty(&mut chunk, 01, &mut self.next_bit_index);
 
            // assert(chunk & 1 == 1)
 

	
 
            self.next_bit_index += 1;
 
            self.cached = Some(chunk >> 1);
 
            if chunk > 0 {
 
                return Some(self.next_bit_index - 1);
 
            }
 
        }
 
    }
 
}
 

	
 
/// Returns an iterator over chunks of bits where ALL of the given
 
/// bitsets have 1.
 
struct AndChunkIter<'a> {
 
    // this value is not overwritten during iteration
 
    // invariant: !sets.is_empty()
 
    sets: &'a [&'a [u32]],
 

	
 
    next_chunk_index: usize,
 
}
 
impl<'a> AndChunkIter<'a> {
 
    fn new(sets: &'a [&'a [u32]]) -> Self {
 
        let sets = if sets.is_empty() { &[&[] as &[_]] } else { sets };
 
        Self { sets, next_chunk_index: 0 }
 
    }
 
}
 
impl Iterator for AndChunkIter<'_> {
 
    type Item = u32;
 
    fn next(&mut self) -> Option<u32> {
 
        let old_chunk_index = self.next_chunk_index;
 
        self.next_chunk_index += 1;
 
        self.sets.iter().fold(Some(!0u32), move |a, b| {
 
            let a = a?;
 
            let b = *b.get(old_chunk_index)?;
 
            Some(a & b)
 
        })
 
    }
 
}
 

	
 
/// Returns an iterator over chunks for bits in range 0..bits_to_go but skipping
 
/// indices for which ANY of the given bitsets has a 1
 
struct NoneChunkIter<'a> {
 
    // this value is not overwritten during iteration
 
    // invariant: !sets.is_empty()
 
    sets: &'a [&'a [u32]],
 
    next_chunk_index: usize,
 
    bits_to_go: usize,
 
}
 
impl<'a> NoneChunkIter<'a> {
 
    /// a set of bitsets. the u32s of each are in ascending order of significant digits
 
    /// i.e., &[0,1] means {1<<32, 0} while &[0,1] is identical to &[1] and means {1}.
 
    fn new(sets: &'a [&'a [u32]], max_bit: usize) -> Self {
 
        let sets = if sets.is_empty() { &[&[] as &[_]] } else { sets };
 
        Self { sets, next_chunk_index: 0, bits_to_go: max_bit }
 
    }
 
}
 
impl Iterator for NoneChunkIter<'_> {
 
    type Item = u32;
 
    fn next(&mut self) -> Option<u32> {
 
        let neutral = match self.bits_to_go {
 
            0 => None,
 
            x @ 1..=31 => Some(!0u32 >> (32 - x)),
 
            _ => Some(!0u32),
 
        };
 
        self.bits_to_go = self.bits_to_go.saturating_sub(32);
 

	
 
        let old_chunk_index = self.next_chunk_index;
 
        self.next_chunk_index += 1;
 

	
 
        self.sets.iter().fold(neutral, move |a, b| {
 
            let a = a?;
 
            let b = *b.get(old_chunk_index)?;
 
            Some(a & !b)
 
        })
 
    }
 
}
 

	
 
#[test]
 
fn test_bit_iter() {
 
    static SETS: &[&[u32]] = &[
 
        //
 
        &[0b101001, 0b101001],
 
        &[0b100001, 0b101001],
 
    ];
 
    let _ = BitChunkIter::new(AndChunkIter::new(SETS));
 
    let iter = BitChunkIter::new(NoneChunkIter::new(SETS, 9));
 
    let iter = BitChunkIter::new(AndChunkIter::new(SETS));
 
    let indices = iter.collect::<Vec<_>>();
 
    println!("indices {:?}", indices);
 
}
 

	
 
enum Entity {
 
    Payload(Payload),
 
    Machine { state: ProtocolS, component_index: usize },
 
}
 

	
 
struct PortKey(usize);
 
struct EntiKey(usize);
 
struct CompKey(usize);
 

	
 
struct ComponentInfo {
 
    port_keyset: HashSet<PortKey>,
 
    protocol: Arc<Protocol>,
 
}
 
#[derive(Default)]
 
struct Connection {
 
    ecs: Ecs,
 
    round_solution: Vec<(ChannelId, bool)>, // encodes an ASSIGNMENT
 
    ekey_channel_ids: Vec<ChannelId>,       // all channel Ids for local keys
 
    component_info: Vec<ComponentInfo>,
 
    endpoint_exts: Vec<EndpointExt>,
 
}
 

	
 
/// Invariant: every component is either:
 
///        in to_run = (to_run_r U to_run_w)
 
///     or in ONE of the ekeys (which means it is blocked by a get on that ekey)
 
///     or in sync_ended (because they reached the end of their sync block)
 
///     or in inconsistent (because they are inconsistent)
 
#[derive(Default)]
 
struct Ecs {
 
    entities: Vec<Entity>, // machines + payloads
 
    assignments: HashMap<(ChannelId, bool), BitSet>,
 
    payloads: BitSet,
 
    ekeys: HashMap<usize, BitSet>,
 
    inconsistent: BitSet,
 
    sync_ended: BitSet,
 
    to_run_r: BitSet, // read from and drained while...
 
    to_run_w: BitSet, // .. written to and populated. }
 
}
 
impl Debug for Ecs {
 
    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
 
        let elen = self.entities.len();
 

	
 
        write!(f, "{:<30}", "payloads")?;
 
        print_flag_bits(f, &self.payloads, elen)?;
0 comments (0 inline, 0 general)