| 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 | 6 |
| 7 // Hash table with open addressing that separates the index from keys/values. | 7 // Hash table with open addressing that separates the index from keys/values. |
| 8 abstract class _HashBase { | 8 abstract class _HashBase { |
| 9 // Each occupied entry in _index is a fixed-size integer that encodes a pair: | 9 // Each occupied entry in _index is a fixed-size integer that encodes a pair: |
| 10 // [ hash pattern for key | index of entry in _data ] | 10 // [ hash pattern for key | index of entry in _data ] |
| (...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 78 assert(_HashBase._UNUSED_PAIR == 0); | 78 assert(_HashBase._UNUSED_PAIR == 0); |
| 79 _index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE); | 79 _index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE); |
| 80 _data = new List(_HashBase._INITIAL_INDEX_SIZE); | 80 _data = new List(_HashBase._INITIAL_INDEX_SIZE); |
| 81 } | 81 } |
| 82 | 82 |
| 83 int get length => (_usedData >> 1) - _deletedKeys; | 83 int get length => (_usedData >> 1) - _deletedKeys; |
| 84 bool get isEmpty => length == 0; | 84 bool get isEmpty => length == 0; |
| 85 bool get isNotEmpty => !isEmpty; | 85 bool get isNotEmpty => !isEmpty; |
| 86 | 86 |
| 87 void _rehash() { | 87 void _rehash() { |
| 88 if ((_deletedKeys << 1) > _usedData) { | 88 if ((_deletedKeys << 2) > _usedData) { |
| 89 // TODO(koda): Consider shrinking. | 89 // TODO(koda): Consider shrinking. |
| 90 // TODO(koda): Consider in-place compaction and more costly CME check. | 90 // TODO(koda): Consider in-place compaction and more costly CME check. |
| 91 _init(_index.length, _hashMask, _data, _usedData); | 91 _init(_index.length, _hashMask, _data, _usedData); |
| 92 } else { | 92 } else { |
| 93 // TODO(koda): Support 32->64 bit transition (and adjust _hashMask). | 93 // TODO(koda): Support 32->64 bit transition (and adjust _hashMask). |
| 94 _init(_index.length << 1, _hashMask >> 1, _data, _usedData); | 94 _init(_index.length << 1, _hashMask >> 1, _data, _usedData); |
| 95 } | 95 } |
| 96 } | 96 } |
| 97 | 97 |
| 98 void clear() { | 98 void clear() { |
| (...skipping 365 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 464 pair = _index[i]; | 464 pair = _index[i]; |
| 465 } | 465 } |
| 466 return false; | 466 return false; |
| 467 } | 467 } |
| 468 | 468 |
| 469 Iterator<K> get iterator => | 469 Iterator<K> get iterator => |
| 470 new _CompactIterator<K>(this, _data, _usedData, -1, 1); | 470 new _CompactIterator<K>(this, _data, _usedData, -1, 1); |
| 471 | 471 |
| 472 Set<K> toSet() => new Set<K>()..addAll(this); | 472 Set<K> toSet() => new Set<K>()..addAll(this); |
| 473 } | 473 } |
| OLD | NEW |