1// Copyright 2014 The Flutter Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5/// A collection of key/value pairs which provides efficient retrieval of
6/// value by key.
7///
8/// This class implements a persistent map: extending this map with a new
9/// key/value pair does not modify an existing instance but instead creates a
10/// new instance.
11///
12/// Unlike [Map], this class does not support `null` as a key value and
13/// implements only a functionality needed for a specific use case at the
14/// core of the framework.
15///
16/// Underlying implementation uses a variation of *hash array mapped trie*
17/// data structure with compressed (bitmap indexed) nodes.
18///
19/// See also:
20///
21/// * [Bagwell, Phil. Ideal hash trees.](https://infoscience.epfl.ch/record/64398);
22/// * [Steindorfer, Michael J., and Jurgen J. Vinju. "Optimizing hash-array mapped tries for fast and lean immutable JVM collections."](https://dl.acm.org/doi/abs/10.1145/2814270.2814312);
23/// * [Clojure's `PersistentHashMap`](https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java).
24///
25class PersistentHashMap<K extends Object, V> {
26 /// Creates an empty hash map.
27 const PersistentHashMap.empty() : this._(null);
28
29 const PersistentHashMap._(this._root);
30
31 final _TrieNode? _root;
32
33 /// If this map does not already contain the given [key] to [value]
34 /// mapping then create a new version of the map which contains
35 /// all mappings from the current one plus the given [key] to [value]
36 /// mapping.
37 PersistentHashMap<K, V> put(K key, V value) {
38 final _TrieNode newRoot = (_root ?? _CompressedNode.empty).put(0, key, key.hashCode, value);
39 if (newRoot == _root) {
40 return this;
41 }
42 return PersistentHashMap<K, V>._(newRoot);
43 }
44
45 /// Returns value associated with the given [key] or `null` if [key]
46 /// is not in the map.
47 @pragma('dart2js:as:trust')
48 V? operator [](K key) {
49 // Unfortunately can not use unsafeCast(...) here because it leads
50 // to worse code generation on VM.
51 return _root?.get(0, key, key.hashCode) as V?;
52 }
53}
54
55/// Base class for nodes in a hash trie.
56///
57/// This trie is keyed by hash code bits using [hashBitsPerLevel] bits
58/// at each level.
59abstract class _TrieNode {
60 static const int hashBitsPerLevel = 5;
61 static const int hashBitsPerLevelMask = (1 << hashBitsPerLevel) - 1;
62
63 @pragma('dart2js:tryInline')
64 @pragma('vm:prefer-inline')
65 @pragma('wasm:prefer-inline')
66 static int trieIndex(int hash, int bitIndex) {
67 return (hash >>> bitIndex) & hashBitsPerLevelMask;
68 }
69
70 /// Insert [key] to [value] mapping into the trie using bits from [keyHash]
71 /// starting at [bitIndex].
72 _TrieNode put(int bitIndex, Object key, int keyHash, Object? value);
73
74 /// Lookup a value associated with the given [key] using bits from [keyHash]
75 /// starting at [bitIndex].
76 Object? get(int bitIndex, Object key, int keyHash);
77}
78
79/// A full (uncompressed) node in the trie.
80///
81/// It contains an array with `1<<_hashBitsPerLevel` elements which
82/// are references to deeper nodes.
83class _FullNode extends _TrieNode {
84 _FullNode(this.descendants);
85
86 static const int numElements = 1 << _TrieNode.hashBitsPerLevel;
87
88 // Caveat: this array is actually List<_TrieNode?> but typing it like that
89 // will introduce a type check when copying this array. For performance
90 // reasons we instead omit the type and use (implicit) casts when accessing
91 // it instead.
92 final List<Object?> descendants;
93
94 @override
95 _TrieNode put(int bitIndex, Object key, int keyHash, Object? value) {
96 final int index = _TrieNode.trieIndex(keyHash, bitIndex);
97 final _TrieNode node = _unsafeCast<_TrieNode?>(descendants[index]) ?? _CompressedNode.empty;
98 final _TrieNode newNode = node.put(bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash, value);
99 return identical(newNode, node) ? this : _FullNode(_copy(descendants)..[index] = newNode);
100 }
101
102 @override
103 Object? get(int bitIndex, Object key, int keyHash) {
104 final int index = _TrieNode.trieIndex(keyHash, bitIndex);
105
106 final _TrieNode? node = _unsafeCast<_TrieNode?>(descendants[index]);
107 return node?.get(bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash);
108 }
109}
110
111/// Compressed node in the trie.
112///
113/// Instead of storing the full array of outgoing edges this node uses a
114/// compressed representation:
115///
116/// * [_CompressedNode.occupiedIndices] has a bit set for indices which are
117/// occupied.
118/// * furthermore, each occupied index can either be a `(key, value)` pair
119/// representing an actual key/value mapping or a `(null, trieNode)` pair
120/// representing a descendant node.
121///
122/// Keys and values are stored together in a single array (instead of two
123/// parallel arrays) for performance reasons: this improves memory access
124/// locality and reduces memory usage (two arrays of length N take slightly
125/// more space than one array of length 2*N).
126class _CompressedNode extends _TrieNode {
127 _CompressedNode(this.occupiedIndices, this.keyValuePairs);
128 _CompressedNode._empty() : this(0, _emptyArray);
129
130 factory _CompressedNode.single(int bitIndex, int keyHash, _TrieNode node) {
131 final int bit = 1 << _TrieNode.trieIndex(keyHash, bitIndex);
132 // A single (null, node) pair.
133 final List<Object?> keyValuePairs = _makeArray(2)..[1] = node;
134 return _CompressedNode(bit, keyValuePairs);
135 }
136
137 static final _CompressedNode empty = _CompressedNode._empty();
138
139 // Caveat: do not replace with [] or const [] this will
140 // introduce polymorphism in the keyValuePairs field and significantly
141 // degrade performance on the VM because it will no longer be able to
142 // devirtualize method calls on keyValuePairs.
143 static final List<Object?> _emptyArray = _makeArray(0);
144
145 // This bitmap only uses 32bits due to [_TrieNode.hashBitsPerLevel] being `5`.
146 final int occupiedIndices;
147 final List<Object?> keyValuePairs;
148
149 @override
150 _TrieNode put(int bitIndex, Object key, int keyHash, Object? value) {
151 final int bit = 1 << _TrieNode.trieIndex(keyHash, bitIndex);
152 final int index = _compressedIndex(bit);
153
154 if ((occupiedIndices & bit) != 0) {
155 // Index is occupied.
156 final Object? keyOrNull = keyValuePairs[2 * index];
157 final Object? valueOrNode = keyValuePairs[2 * index + 1];
158
159 // Is this a (null, trieNode) pair?
160 if (identical(keyOrNull, null)) {
161 final _TrieNode newNode = _unsafeCast<_TrieNode>(
162 valueOrNode,
163 ).put(bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash, value);
164 if (newNode == valueOrNode) {
165 return this;
166 }
167 return _CompressedNode(occupiedIndices, _copy(keyValuePairs)..[2 * index + 1] = newNode);
168 }
169
170 if (key == keyOrNull) {
171 // Found key/value pair with a matching key. If values match
172 // then avoid doing anything otherwise copy and update.
173 return identical(value, valueOrNode)
174 ? this
175 : _CompressedNode(occupiedIndices, _copy(keyValuePairs)..[2 * index + 1] = value);
176 }
177
178 // Two different keys at the same index, resolve collision.
179 final _TrieNode newNode = _resolveCollision(
180 bitIndex + _TrieNode.hashBitsPerLevel,
181 keyOrNull,
182 valueOrNode,
183 key,
184 keyHash,
185 value,
186 );
187 return _CompressedNode(
188 occupiedIndices,
189 _copy(keyValuePairs)
190 ..[2 * index] = null
191 ..[2 * index + 1] = newNode,
192 );
193 } else {
194 // Adding new key/value mapping.
195 final int occupiedCount = _bitCount(occupiedIndices);
196 if (occupiedCount >= 16) {
197 // Too many occupied: inflate compressed node into full node and
198 // update descendant at the corresponding index.
199 return _inflate(bitIndex)
200 ..descendants[_TrieNode.trieIndex(keyHash, bitIndex)] = _CompressedNode.empty.put(
201 bitIndex + _TrieNode.hashBitsPerLevel,
202 key,
203 keyHash,
204 value,
205 );
206 } else {
207 // Grow keyValuePairs by inserting key/value pair at the given
208 // index.
209 final int prefixLength = 2 * index;
210 final int totalLength = 2 * occupiedCount;
211 final List<Object?> newKeyValuePairs = _makeArray(totalLength + 2);
212 for (int srcIndex = 0; srcIndex < prefixLength; srcIndex++) {
213 newKeyValuePairs[srcIndex] = keyValuePairs[srcIndex];
214 }
215 newKeyValuePairs[prefixLength] = key;
216 newKeyValuePairs[prefixLength + 1] = value;
217 for (
218 int srcIndex = prefixLength, dstIndex = prefixLength + 2;
219 srcIndex < totalLength;
220 srcIndex++, dstIndex++
221 ) {
222 newKeyValuePairs[dstIndex] = keyValuePairs[srcIndex];
223 }
224 return _CompressedNode(occupiedIndices | bit, newKeyValuePairs);
225 }
226 }
227 }
228
229 @override
230 Object? get(int bitIndex, Object key, int keyHash) {
231 final int bit = 1 << _TrieNode.trieIndex(keyHash, bitIndex);
232 if ((occupiedIndices & bit) == 0) {
233 return null;
234 }
235 final int index = _compressedIndex(bit);
236 final Object? keyOrNull = keyValuePairs[2 * index];
237 final Object? valueOrNode = keyValuePairs[2 * index + 1];
238 if (keyOrNull == null) {
239 final _TrieNode node = _unsafeCast<_TrieNode>(valueOrNode);
240 return node.get(bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash);
241 }
242 if (key == keyOrNull) {
243 return valueOrNode;
244 }
245 return null;
246 }
247
248 /// Convert this node into an equivalent [_FullNode].
249 _FullNode _inflate(int bitIndex) {
250 final List<Object?> nodes = _makeArray(_FullNode.numElements);
251 int srcIndex = 0;
252 for (int dstIndex = 0; dstIndex < _FullNode.numElements; dstIndex++) {
253 if (((occupiedIndices >>> dstIndex) & 1) != 0) {
254 final Object? keyOrNull = keyValuePairs[srcIndex];
255 if (keyOrNull == null) {
256 nodes[dstIndex] = keyValuePairs[srcIndex + 1];
257 } else {
258 nodes[dstIndex] = _CompressedNode.empty.put(
259 bitIndex + _TrieNode.hashBitsPerLevel,
260 keyOrNull,
261 keyValuePairs[srcIndex].hashCode,
262 keyValuePairs[srcIndex + 1],
263 );
264 }
265 srcIndex += 2;
266 }
267 }
268 return _FullNode(nodes);
269 }
270
271 @pragma('dart2js:tryInline')
272 @pragma('vm:prefer-inline')
273 @pragma('wasm:prefer-inline')
274 int _compressedIndex(int bit) {
275 return _bitCount(occupiedIndices & (bit - 1));
276 }
277
278 static _TrieNode _resolveCollision(
279 int bitIndex,
280 Object existingKey,
281 Object? existingValue,
282 Object key,
283 int keyHash,
284 Object? value,
285 ) {
286 final int existingKeyHash = existingKey.hashCode;
287 // Check if this is a full hash collision and use _HashCollisionNode
288 // in this case.
289 return (existingKeyHash == keyHash)
290 ? _HashCollisionNode.fromCollision(keyHash, existingKey, existingValue, key, value)
291 : _CompressedNode.empty
292 .put(bitIndex, existingKey, existingKeyHash, existingValue)
293 .put(bitIndex, key, keyHash, value);
294 }
295}
296
297/// Trie node representing a full hash collision.
298///
299/// Stores a list of key/value pairs (where all keys have the same hash code).
300class _HashCollisionNode extends _TrieNode {
301 _HashCollisionNode(this.hash, this.keyValuePairs);
302
303 factory _HashCollisionNode.fromCollision(
304 int keyHash,
305 Object keyA,
306 Object? valueA,
307 Object keyB,
308 Object? valueB,
309 ) {
310 final List<Object?> list = _makeArray(4);
311 list[0] = keyA;
312 list[1] = valueA;
313 list[2] = keyB;
314 list[3] = valueB;
315 return _HashCollisionNode(keyHash, list);
316 }
317
318 final int hash;
319 final List<Object?> keyValuePairs;
320
321 @override
322 _TrieNode put(int bitIndex, Object key, int keyHash, Object? val) {
323 // Is this another full hash collision?
324 if (keyHash == hash) {
325 final int index = _indexOf(key);
326 if (index != -1) {
327 return identical(keyValuePairs[index + 1], val)
328 ? this
329 : _HashCollisionNode(keyHash, _copy(keyValuePairs)..[index + 1] = val);
330 }
331 final int length = keyValuePairs.length;
332 final List<Object?> newArray = _makeArray(length + 2);
333 for (int i = 0; i < length; i++) {
334 newArray[i] = keyValuePairs[i];
335 }
336 newArray[length] = key;
337 newArray[length + 1] = val;
338 return _HashCollisionNode(keyHash, newArray);
339 }
340
341 // Not a full hash collision, need to introduce a _CompressedNode which
342 // uses previously unused bits.
343 return _CompressedNode.single(bitIndex, hash, this).put(bitIndex, key, keyHash, val);
344 }
345
346 @override
347 Object? get(int bitIndex, Object key, int keyHash) {
348 final int index = _indexOf(key);
349 return index < 0 ? null : keyValuePairs[index + 1];
350 }
351
352 int _indexOf(Object key) {
353 final int length = keyValuePairs.length;
354 for (int i = 0; i < length; i += 2) {
355 if (key == keyValuePairs[i]) {
356 return i;
357 }
358 }
359 return -1;
360 }
361}
362
363/// Returns number of bits set in a 32bit integer.
364///
365/// dart2js safe because we work with 32bit integers.
366@pragma('dart2js:tryInline')
367@pragma('vm:prefer-inline')
368@pragma('wasm:prefer-inline')
369int _bitCount(int n) {
370 assert((n & 0xFFFFFFFF) == n);
371 n = n - ((n >> 1) & 0x55555555);
372 n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
373 n = (n + (n >> 4)) & 0x0F0F0F0F;
374 n = n + (n >> 8);
375 n = n + (n >> 16);
376 return n & 0x0000003F;
377}
378
379/// Create a copy of the given array.
380///
381/// Caveat: do not replace with List.of or similar methods. They are
382/// considerably slower.
383@pragma('dart2js:tryInline')
384@pragma('vm:prefer-inline')
385@pragma('wasm:prefer-inline')
386List<Object?> _copy(List<Object?> array) {
387 final List<Object?> clone = _makeArray(array.length);
388 for (int j = 0; j < array.length; j++) {
389 clone[j] = array[j];
390 }
391 return clone;
392}
393
394/// Create a fixed-length array of the given length filled with `null`.
395///
396/// We are using fixed length arrays because they are smaller and
397/// faster to access on VM. Growable arrays are represented by 2 objects
398/// (growable array instance pointing to a fixed array instance) and
399/// consequently fixed length arrays are faster to allocated, require less
400/// memory and are faster to access (less indirections).
401@pragma('dart2js:tryInline')
402@pragma('vm:prefer-inline')
403@pragma('wasm:prefer-inline')
404List<Object?> _makeArray(int length) {
405 return List<Object?>.filled(length, null);
406}
407
408/// This helper method becomes an no-op when compiled with dart2js on
409/// with high level of optimizations enabled.
410@pragma('dart2js:as:trust')
411@pragma('dart2js:tryInline')
412@pragma('vm:prefer-inline')
413@pragma('wasm:prefer-inline')
414T _unsafeCast<T>(Object? o) {
415 return o as T;
416}
417

Provided by KDAB

Privacy Policy
Learn more about Flutter for embedded and desktop on industrialflutter.com