Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(452)

Side by Side Diff: runtime/lib/compact_hash.dart

Issue 1105453003: Remove public int.is64Bit. (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 5 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « no previous file | runtime/lib/growable_array.cc » ('j') | runtime/lib/object.cc » ('J')
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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 }
OLDNEW
« no previous file with comments | « no previous file | runtime/lib/growable_array.cc » ('j') | runtime/lib/object.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698