cranelift_codegen_meta/
unique_table.rs

1//! An index-accessed table implementation that avoids duplicate entries.
2use std::collections::HashMap;
3use std::hash::Hash;
4use std::slice;
5
6/// Collect items into the `table` list, removing duplicates.
7pub(crate) struct UniqueTable<'entries, T: Eq + Hash> {
8    table: Vec<&'entries T>,
9    map: HashMap<&'entries T, usize>,
10}
11
12impl<'entries, T: Eq + Hash> UniqueTable<'entries, T> {
13    pub fn new() -> Self {
14        Self {
15            table: Vec::new(),
16            map: HashMap::new(),
17        }
18    }
19
20    pub fn add(&mut self, entry: &'entries T) -> usize {
21        match self.map.get(&entry) {
22            None => {
23                let i = self.table.len();
24                self.table.push(entry);
25                self.map.insert(entry, i);
26                i
27            }
28            Some(&i) => i,
29        }
30    }
31
32    pub fn len(&self) -> usize {
33        self.table.len()
34    }
35    pub fn iter(&self) -> slice::Iter<&'entries T> {
36        self.table.iter()
37    }
38}
39
40/// A table of sequences which tries to avoid common subsequences.
41pub(crate) struct UniqueSeqTable<T: PartialEq + Clone> {
42    table: Vec<T>,
43}
44
45impl<T: PartialEq + Clone> UniqueSeqTable<T> {
46    pub fn new() -> Self {
47        Self { table: Vec::new() }
48    }
49    pub fn add(&mut self, values: &[T]) -> usize {
50        if values.is_empty() {
51            return 0;
52        }
53        if let Some(offset) = find_subsequence(values, &self.table) {
54            offset
55        } else {
56            let table_len = self.table.len();
57
58            // Try to put in common the last elements of the table if they're a prefix of the new
59            // sequence.
60            //
61            // We know there wasn't a full match, so the best prefix we can hope to find contains
62            // all the values but the last one.
63            let mut start_from = usize::min(table_len, values.len() - 1);
64            while start_from != 0 {
65                // Loop invariant: start_from <= table_len, so table_len - start_from >= 0.
66                if values[0..start_from] == self.table[table_len - start_from..table_len] {
67                    break;
68                }
69                start_from -= 1;
70            }
71
72            self.table
73                .extend(values[start_from..values.len()].iter().cloned());
74            table_len - start_from
75        }
76    }
77    pub fn len(&self) -> usize {
78        self.table.len()
79    }
80    pub fn iter(&self) -> slice::Iter<T> {
81        self.table.iter()
82    }
83}
84
85/// Try to find the subsequence `sub` in the `whole` sequence. Returns None if
86/// it's not been found, or Some(index) if it has been. Naive implementation
87/// until proven we need something better.
88fn find_subsequence<T: PartialEq>(sub: &[T], whole: &[T]) -> Option<usize> {
89    assert!(!sub.is_empty());
90    // We want i + sub.len() <= whole.len(), i.e. i < whole.len() + 1 - sub.len().
91    if whole.len() < sub.len() {
92        return None;
93    }
94    let max = whole.len() - sub.len();
95    for i in 0..=max {
96        if whole[i..i + sub.len()] == sub[..] {
97            return Some(i);
98        }
99    }
100    None
101}
102
103#[test]
104fn test_find_subsequence() {
105    assert_eq!(find_subsequence(&vec![1], &vec![4]), None);
106    assert_eq!(find_subsequence(&vec![1], &vec![1]), Some(0));
107    assert_eq!(find_subsequence(&vec![1, 2], &vec![1]), None);
108    assert_eq!(find_subsequence(&vec![1, 2], &vec![1, 2]), Some(0));
109    assert_eq!(find_subsequence(&vec![1, 2], &vec![1, 3]), None);
110    assert_eq!(find_subsequence(&vec![1, 2], &vec![0, 1, 2]), Some(1));
111    assert_eq!(find_subsequence(&vec![1, 2], &vec![0, 1, 3, 1]), None);
112    assert_eq!(find_subsequence(&vec![1, 2], &vec![0, 1, 3, 1, 2]), Some(3));
113    assert_eq!(
114        find_subsequence(&vec![1, 1, 3], &vec![1, 1, 1, 3, 3]),
115        Some(1)
116    );
117}
118
119#[test]
120fn test_optimal_add() {
121    let mut seq_table = UniqueSeqTable::new();
122    // [0, 1, 2, 3]
123    assert_eq!(seq_table.add(&vec![0, 1, 2, 3]), 0);
124    assert_eq!(seq_table.add(&vec![0, 1, 2, 3]), 0);
125    assert_eq!(seq_table.add(&vec![1, 2, 3]), 1);
126    assert_eq!(seq_table.add(&vec![2, 3]), 2);
127    assert_eq!(seq_table.len(), 4);
128    // [0, 1, 2, 3, 4]
129    assert_eq!(seq_table.add(&vec![2, 3, 4]), 2);
130    assert_eq!(seq_table.len(), 5);
131    // [0, 1, 2, 3, 4, 6, 5, 7]
132    assert_eq!(seq_table.add(&vec![4, 6, 5, 7]), 4);
133    assert_eq!(seq_table.len(), 8);
134    // [0, 1, 2, 3, 4, 6, 5, 7, 8, 2, 3, 4]
135    assert_eq!(seq_table.add(&vec![8, 2, 3, 4]), 8);
136    assert_eq!(seq_table.add(&vec![8]), 8);
137    assert_eq!(seq_table.len(), 12);
138}
cranelift_codegen_meta/unique_table.rs

cranelift_codegen_meta/
unique_table.rs
