OLD | NEW |
1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import 'dart:typed_data'; | 5 import 'dart:typed_data'; |
| 6 import 'dart:_internal' as internal; |
6 | 7 |
7 // Hash table with open addressing that separates the index from keys/values. | 8 // Hash table with open addressing that separates the index from keys/values. |
8 abstract class _HashBase { | 9 abstract class _HashBase { |
9 // Each occupied entry in _index is a fixed-size integer that encodes a pair: | 10 // Each occupied entry in _index is a fixed-size integer that encodes a pair: |
10 // [ hash pattern for key | index of entry in _data ] | 11 // [ hash pattern for key | index of entry in _data ] |
11 // The hash pattern is based on hashCode, but is guaranteed to be non-zero. | 12 // The hash pattern is based on hashCode, but is guaranteed to be non-zero. |
12 // The length of _index is always a power of two, and there is always at | 13 // The length of _index is always a power of two, and there is always at |
13 // least one unoccupied entry. | 14 // least one unoccupied entry. |
14 Uint32List _index; | 15 Uint32List _index; |
15 | 16 |
16 // The number of bits used for each component is determined by table size. | 17 // The number of bits used for each component is determined by table size. |
17 // The length of _index is twice the number of entries in _data, and both | 18 // The length of _index is twice the number of entries in _data, and both |
18 // are doubled when _data is full. Thus, _index will have a max load factor | 19 // are doubled when _data is full. Thus, _index will have a max load factor |
19 // of 1/2, which enables one more bit to be used for the hash. | 20 // of 1/2, which enables one more bit to be used for the hash. |
20 // TODO(koda): Consider growing _data by factor sqrt(2), twice as often. | 21 // TODO(koda): Consider growing _data by factor sqrt(2), twice as often. |
21 static const int _INITIAL_INDEX_BITS = 3; | 22 static const int _INITIAL_INDEX_BITS = 3; |
22 static const int _INITIAL_INDEX_SIZE = 1 << (_INITIAL_INDEX_BITS + 1); | 23 static const int _INITIAL_INDEX_SIZE = 1 << (_INITIAL_INDEX_BITS + 1); |
23 | 24 |
24 // Unused and deleted entries are marked by 0 and 1, respectively. | 25 // Unused and deleted entries are marked by 0 and 1, respectively. |
25 static const int _UNUSED_PAIR = 0; | 26 static const int _UNUSED_PAIR = 0; |
26 static const int _DELETED_PAIR = 1; | 27 static const int _DELETED_PAIR = 1; |
27 | 28 |
28 // Cached in-place mask for the hash pattern component. On 32-bit, the top | 29 // Cached in-place mask for the hash pattern component. On 32-bit, the top |
29 // bits are wasted to avoid Mint allocation. | 30 // bits are wasted to avoid Mint allocation. |
30 // TODO(koda): Reclaim the bits by making the compiler treat hash patterns | 31 // TODO(koda): Reclaim the bits by making the compiler treat hash patterns |
31 // as unsigned words. | 32 // as unsigned words. |
32 int _hashMask = int.is64Bit() ? | 33 int _hashMask = internal.is64Bit ? |
33 (1 << (32 - _INITIAL_INDEX_BITS)) - 1 : | 34 (1 << (32 - _INITIAL_INDEX_BITS)) - 1 : |
34 (1 << (30 - _INITIAL_INDEX_BITS)) - 1; | 35 (1 << (30 - _INITIAL_INDEX_BITS)) - 1; |
35 | 36 |
36 static int _hashPattern(int fullHash, int hashMask, int size) { | 37 static int _hashPattern(int fullHash, int hashMask, int size) { |
37 final int maskedHash = fullHash & hashMask; | 38 final int maskedHash = fullHash & hashMask; |
38 // TODO(koda): Consider keeping bit length and use left shift. | 39 // TODO(koda): Consider keeping bit length and use left shift. |
39 return (maskedHash == 0) ? (size >> 1) : maskedHash * (size >> 1); | 40 return (maskedHash == 0) ? (size >> 1) : maskedHash * (size >> 1); |
40 } | 41 } |
41 | 42 |
42 // Linear probing. | 43 // Linear probing. |
(...skipping 483 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
526 E lookup(Object o) => _validKey(o) ? super.lookup(o) : null; | 527 E lookup(Object o) => _validKey(o) ? super.lookup(o) : null; |
527 bool remove(Object o) => _validKey(o) ? super.remove(o) : false; | 528 bool remove(Object o) => _validKey(o) ? super.remove(o) : false; |
528 | 529 |
529 _CompactLinkedCustomHashSet(this._equality, this._hasher, validKey) | 530 _CompactLinkedCustomHashSet(this._equality, this._hasher, validKey) |
530 : _validKey = (validKey != null) ? validKey : new _TypeTest<E>().test; | 531 : _validKey = (validKey != null) ? validKey : new _TypeTest<E>().test; |
531 | 532 |
532 Set<E> toSet() => | 533 Set<E> toSet() => |
533 new _CompactLinkedCustomHashSet<E>(_equality, _hasher, _validKey) | 534 new _CompactLinkedCustomHashSet<E>(_equality, _hasher, _validKey) |
534 ..addAll(this); | 535 ..addAll(this); |
535 } | 536 } |
OLD | NEW |