ktrs_cli/ktlint/reporter/
java_map.rs

1//! A `java.util.concurrent.ConcurrentHashMap<String, V>` (default capacity, single-threaded use) that
2//! iterates in the JVM's order: bins by index, nodes as `putVal`, `transfer` and tree bins leave them.
3//! The html reporter iterates its map, so its file order depends on this.
4
5const DEFAULT_CAPACITY: usize = 16;
6const TREEIFY_THRESHOLD: usize = 8;
7const UNTREEIFY_THRESHOLD: usize = 6;
8const MIN_TREEIFY_CAPACITY: usize = 64;
9const HASH_BITS: u32 = 0x7fff_ffff;
10
11struct Bin<V> {
12    nodes: Vec<(u32, String, V)>,
13    /// A `TreeBin`: new nodes are prepended to its `first` list.
14    tree: bool,
15}
16
17impl<V> Default for Bin<V> {
18    fn default() -> Self {
19        Bin { nodes: Vec::new(), tree: false }
20    }
21}
22
23pub struct JavaConcurrentHashMap<V> {
24    table: Vec<Bin<V>>,
25    size: usize,
26    size_ctl: usize,
27}
28
29impl<V> Default for JavaConcurrentHashMap<V> {
30    fn default() -> Self {
31        JavaConcurrentHashMap { table: Vec::new(), size: 0, size_ctl: 0 }
32    }
33}
34
35/// `String.hashCode()` over UTF-16 code units.
36pub fn java_string_hash(s: &str) -> i32 {
37    s.encode_utf16().fold(0i32, |h, c| h.wrapping_mul(31).wrapping_add(c as i32))
38}
39
40fn spread(h: i32) -> u32 {
41    let h = h as u32;
42    (h ^ (h >> 16)) & HASH_BITS
43}
44
45fn table_size_for(c: usize) -> usize {
46    c.max(1).next_power_of_two()
47}
48
49impl<V> JavaConcurrentHashMap<V> {
50    pub fn new() -> Self {
51        Self::default()
52    }
53
54    pub fn is_empty(&self) -> bool {
55        self.size == 0
56    }
57
58    pub fn len(&self) -> usize {
59        self.size
60    }
61
62    /// Kotlin's `getOrPut(key) { default() }` on a `ConcurrentMap` (`putIfAbsent` when missing).
63    pub fn get_or_put(&mut self, key: &str, default: impl FnOnce() -> V) -> &mut V {
64        let hash = spread(java_string_hash(key));
65        if let Some((bin, pos)) = self.find(hash, key) {
66            return &mut self.table[bin].nodes[pos].2;
67        }
68        self.put_val(hash, key.to_owned(), default());
69        let (bin, pos) = self.find(hash, key).expect("just inserted");
70        &mut self.table[bin].nodes[pos].2
71    }
72
73    fn find(&self, hash: u32, key: &str) -> Option<(usize, usize)> {
74        if self.table.is_empty() {
75            return None;
76        }
77        let i = hash as usize & (self.table.len() - 1);
78        self.table[i].nodes.iter().position(|(h, k, _)| *h == hash && k == key).map(|pos| (i, pos))
79    }
80
81    fn put_val(&mut self, hash: u32, key: String, value: V) {
82        if self.table.is_empty() {
83            self.table = (0..DEFAULT_CAPACITY).map(|_| Bin::default()).collect();
84            self.size_ctl = DEFAULT_CAPACITY - (DEFAULT_CAPACITY >> 2);
85        }
86        let n = self.table.len();
87        let i = hash as usize & (n - 1);
88        let bin = &mut self.table[i];
89        let bin_count = if bin.tree {
90            bin.nodes.insert(0, (hash, key, value));
91            2
92        } else {
93            let count = bin.nodes.len();
94            bin.nodes.push((hash, key, value));
95            count
96        };
97        if bin_count >= TREEIFY_THRESHOLD {
98            self.treeify_bin(i);
99        }
100        self.add_count();
101    }
102
103    fn treeify_bin(&mut self, index: usize) {
104        let n = self.table.len();
105        if n < MIN_TREEIFY_CAPACITY {
106            self.try_presize(n << 1);
107        } else {
108            self.table[index].tree = true;
109        }
110    }
111
112    fn try_presize(&mut self, size: usize) {
113        let c = table_size_for(size + (size >> 1) + 1);
114        while c > self.size_ctl {
115            self.transfer();
116        }
117    }
118
119    fn add_count(&mut self) {
120        self.size += 1;
121        while self.size >= self.size_ctl {
122            self.transfer();
123        }
124    }
125
126    fn transfer(&mut self) {
127        let n = self.table.len();
128        let mut next: Vec<Bin<V>> = (0..n << 1).map(|_| Bin::default()).collect();
129        for (i, bin) in std::mem::take(&mut self.table).into_iter().enumerate() {
130            if bin.nodes.is_empty() {
131                continue;
132            }
133            let (lo, hi) = if bin.tree { split_tree(bin.nodes, n) } else { split_list(bin.nodes, n) };
134            next[i] = lo;
135            next[i + n] = hi;
136        }
137        self.table = next;
138        self.size_ctl = (n << 1) - (n >> 1);
139    }
140}
141
142/// `transfer` of a list bin: the tail run with the same bit stays intact, the nodes before it are
143/// prepended one by one (so their order reverses).
144fn split_list<V>(nodes: Vec<(u32, String, V)>, n: usize) -> (Bin<V>, Bin<V>) {
145    let bit = |h: u32| h as usize & n;
146    let mut run_bit = bit(nodes[0].0);
147    let mut last_run = 0;
148    for (p, node) in nodes.iter().enumerate().skip(1) {
149        if bit(node.0) != run_bit {
150            run_bit = bit(node.0);
151            last_run = p;
152        }
153    }
154    let mut nodes = nodes;
155    let tail = nodes.split_off(last_run);
156    let (mut ln, mut hn) = if run_bit == 0 { (tail, Vec::new()) } else { (Vec::new(), tail) };
157    for node in nodes {
158        if bit(node.0) == 0 { ln.insert(0, node) } else { hn.insert(0, node) }
159    }
160    (Bin { nodes: ln, tree: false }, Bin { nodes: hn, tree: false })
161}
162
163/// `transfer` of a `TreeBin`: order kept; a half with at most `UNTREEIFY_THRESHOLD` nodes becomes a list.
164fn split_tree<V>(nodes: Vec<(u32, String, V)>, n: usize) -> (Bin<V>, Bin<V>) {
165    let (lo, hi): (Vec<_>, Vec<_>) = nodes.into_iter().partition(|node| node.0 as usize & n == 0);
166    let tree = |nodes: &Vec<(u32, String, V)>| nodes.len() > UNTREEIFY_THRESHOLD;
167    (Bin { tree: tree(&lo), nodes: lo }, Bin { tree: tree(&hi), nodes: hi })
168}
169
170impl<V> JavaConcurrentHashMap<V> {
171    /// `entries` / `forEach` order.
172    pub fn iter(&self) -> impl Iterator<Item = (&str, &V)> {
173        self.table.iter().flat_map(|bin| bin.nodes.iter().map(|(_, k, v)| (k.as_str(), v)))
174    }
175}
ktrs_cli/ktlint/reporter/java_map.rs

ktrs_cli/ktlint/reporter/
java_map.rs
