netlistdb/
csr.rs

1//! Compressed sparse row (CSR) implementation.
2
3use ulib::UVec;
4
5/// A helper type for simple 1-layer CSR.
6#[derive(Debug, Default)]
7pub struct VecCSR {
8    /// flattened list start, analogous to `flat_net2pin_start`
9    pub start: UVec<usize>,
10    /// flattened list, analogous to `netpin`, indexed by [VecCSR::start]
11    pub items: UVec<usize>,
12}
13
14impl VecCSR {
15    /// build CSR from the mapping between items to set indices.
16    pub fn from(num_sets: usize, num_items: usize, inset: &[usize]) -> VecCSR {
17        assert_eq!(inset.len(), num_items);
18        let mut start: Vec<usize> = vec![0; num_sets + 1];
19        let mut items: Vec<usize> = vec![0; num_items];
20        for s in inset {
21            start[*s] += 1;
22        }
23        // todo: parallelizable
24        for i in 1..num_sets + 1 {
25            start[i] += start[i - 1];
26        }
27        assert_eq!(start[num_sets], num_items);
28        // todo: parallelizable
29        for i in (0..num_items).rev() {
30            let s = inset[i];
31            let pos = start[s] - 1;
32            start[s] -= 1;
33            items[pos] = i;
34        }
35        VecCSR {
36            start: start.into(),
37            items: items.into()
38        }
39    }
40
41    /// convenient method to get an iterator of set items.
42    #[inline]
43    pub fn iter_set(&self, set_id: usize)
44                    -> impl Iterator<Item = usize> + '_
45    {
46        let l = self.start[set_id];
47        let r = self.start[set_id + 1];
48        self.items[l..r].iter().copied()
49    }
50    
51    /// get size of a set
52    #[inline]
53    pub fn len(&self, set_id: usize) -> usize {
54        let l = self.start[set_id];
55        let r = self.start[set_id + 1];
56        r - l
57    }
58}
netlistdb/csr.rs

netlistdb/
csr.rs
