OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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 part of dart.collection; | 5 patch class HashMap<K, V> { |
| 6 final _HashMapTable<K, V> _hashTable = new _HashMapTable<K, V>(); |
6 | 7 |
7 class _HashMapTable<K, V> extends _HashTable<K> { | 8 /* patch */ HashMap() { |
8 static const int _INITIAL_CAPACITY = 8; | |
9 static const int _VALUE_INDEX = 1; | |
10 | |
11 _HashMapTable() : super(_INITIAL_CAPACITY); | |
12 | |
13 int get _entrySize => 2; | |
14 | |
15 V _value(int offset) => _table[offset + _VALUE_INDEX]; | |
16 void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; } | |
17 | |
18 _copyEntry(List fromTable, int fromOffset, int toOffset) { | |
19 _table[toOffset + _VALUE_INDEX] = fromTable[fromOffset + _VALUE_INDEX]; | |
20 } | |
21 } | |
22 | |
23 class HashMap<K, V> implements Map<K, V> { | |
24 final _HashMapTable<K, V> _hashTable; | |
25 | |
26 HashMap() : _hashTable = new _HashMapTable<K, V>() { | |
27 _hashTable._container = this; | 9 _hashTable._container = this; |
28 } | 10 } |
29 | 11 |
30 factory HashMap.from(Map<K, V> other) { | |
31 return new HashMap<K, V>()..addAll(other); | |
32 } | |
33 | 12 |
34 bool containsKey(K key) { | 13 /* patch */ bool containsKey(K key) { |
35 return _hashTable._get(key) >= 0; | 14 return _hashTable._get(key) >= 0; |
36 } | 15 } |
37 | 16 |
38 bool containsValue(V value) { | 17 /* patch */ bool containsValue(V value) { |
39 List table = _hashTable._table; | 18 List table = _hashTable._table; |
40 int entrySize = _hashTable._entrySize; | 19 int entrySize = _hashTable._entrySize; |
41 for (int offset = 0; offset < table.length; offset += entrySize) { | 20 for (int offset = 0; offset < table.length; offset += entrySize) { |
42 if (!_hashTable._isFree(table[offset]) && | 21 if (!_hashTable._isFree(table[offset]) && |
43 _hashTable._value(offset) == value) { | 22 _hashTable._value(offset) == value) { |
44 return true; | 23 return true; |
45 } | 24 } |
46 } | 25 } |
47 return false; | 26 return false; |
48 } | 27 } |
49 | 28 |
50 void addAll(Map<K, V> other) { | 29 /* patch */ void addAll(Map<K, V> other) { |
51 other.forEach((K key, V value) { | 30 other.forEach((K key, V value) { |
52 int offset = _hashTable._put(key); | 31 int offset = _hashTable._put(key); |
53 _hashTable._setValue(offset, value); | 32 _hashTable._setValue(offset, value); |
54 _hashTable._checkCapacity(); | 33 _hashTable._checkCapacity(); |
55 }); | 34 }); |
56 } | 35 } |
57 | 36 |
58 V operator [](K key) { | 37 /* patch */ V operator [](K key) { |
59 int offset = _hashTable._get(key); | 38 int offset = _hashTable._get(key); |
60 if (offset >= 0) return _hashTable._value(offset); | 39 if (offset >= 0) return _hashTable._value(offset); |
61 return null; | 40 return null; |
62 } | 41 } |
63 | 42 |
64 void operator []=(K key, V value) { | 43 /* patch */ void operator []=(K key, V value) { |
65 int offset = _hashTable._put(key); | 44 int offset = _hashTable._put(key); |
66 _hashTable._setValue(offset, value); | 45 _hashTable._setValue(offset, value); |
67 _hashTable._checkCapacity(); | 46 _hashTable._checkCapacity(); |
68 } | 47 } |
69 | 48 |
70 V putIfAbsent(K key, V ifAbsent()) { | 49 /* patch */ V putIfAbsent(K key, V ifAbsent()) { |
71 int offset = _hashTable._probeForAdd(_hashTable._hashCodeOf(key), key); | 50 int offset = _hashTable._probeForAdd(_hashTable._hashCodeOf(key), key); |
72 Object entry = _hashTable._table[offset]; | 51 Object entry = _hashTable._table[offset]; |
73 if (!_hashTable._isFree(entry)) { | 52 if (!_hashTable._isFree(entry)) { |
74 return _hashTable._value(offset); | 53 return _hashTable._value(offset); |
75 } | 54 } |
76 int modificationCount = _hashTable._modificationCount; | 55 int modificationCount = _hashTable._modificationCount; |
77 V value = ifAbsent(); | 56 V value = ifAbsent(); |
78 if (modificationCount == _hashTable._modificationCount) { | 57 if (modificationCount == _hashTable._modificationCount) { |
79 _hashTable._setKey(offset, key); | 58 _hashTable._setKey(offset, key); |
80 _hashTable._setValue(offset, value); | 59 _hashTable._setValue(offset, value); |
81 if (entry == null) { | 60 if (entry == null) { |
82 _hashTable._entryCount++; | 61 _hashTable._entryCount++; |
83 _hashTable._checkCapacity(); | 62 _hashTable._checkCapacity(); |
84 } else { | 63 } else { |
85 assert(identical(entry, _TOMBSTONE)); | 64 assert(identical(entry, _TOMBSTONE)); |
86 _hashTable._deletedCount--; | 65 _hashTable._deletedCount--; |
87 } | 66 } |
88 _hashTable._recordModification(); | 67 _hashTable._recordModification(); |
89 } else { | 68 } else { |
90 // The table might have changed, so we can't trust [offset] any more. | 69 // The table might have changed, so we can't trust [offset] any more. |
91 // Do another lookup before setting the value. | 70 // Do another lookup before setting the value. |
92 offset = _hashTable._put(key); | 71 offset = _hashTable._put(key); |
93 _hashTable._setValue(offset, value); | 72 _hashTable._setValue(offset, value); |
94 _hashTable._checkCapacity(); | 73 _hashTable._checkCapacity(); |
95 } | 74 } |
96 return value; | 75 return value; |
97 } | 76 } |
98 | 77 |
99 V remove(K key) { | 78 /* patch */ V remove(K key) { |
100 int offset = _hashTable._remove(key); | 79 int offset = _hashTable._remove(key); |
101 if (offset < 0) return null; | 80 if (offset < 0) return null; |
102 V oldValue = _hashTable._value(offset); | 81 V oldValue = _hashTable._value(offset); |
103 _hashTable._setValue(offset, null); | 82 _hashTable._setValue(offset, null); |
104 _hashTable._checkCapacity(); | 83 _hashTable._checkCapacity(); |
105 return oldValue; | 84 return oldValue; |
106 } | 85 } |
107 | 86 |
108 void clear() { | 87 /* patch */ void clear() { |
109 _hashTable._clear(); | 88 _hashTable._clear(); |
110 } | 89 } |
111 | 90 |
112 void forEach(void action (K key, V value)) { | 91 /* patch */ void forEach(void action(K key, V value)) { |
113 int modificationCount = _hashTable._modificationCount; | 92 int modificationCount = _hashTable._modificationCount; |
114 List table = _hashTable._table; | 93 List table = _hashTable._table; |
115 int entrySize = _hashTable._entrySize; | 94 int entrySize = _hashTable._entrySize; |
116 for (int offset = 0; offset < table.length; offset += entrySize) { | 95 for (int offset = 0; offset < table.length; offset += entrySize) { |
117 Object entry = table[offset]; | 96 Object entry = table[offset]; |
118 if (!_hashTable._isFree(entry)) { | 97 if (!_hashTable._isFree(entry)) { |
119 K key = entry; | 98 K key = entry; |
120 V value = _hashTable._value(offset); | 99 V value = _hashTable._value(offset); |
121 action(key, value); | 100 action(key, value); |
122 _hashTable._checkModification(modificationCount); | 101 _hashTable._checkModification(modificationCount); |
123 } | 102 } |
124 } | 103 } |
125 } | 104 } |
126 | 105 |
127 Iterable<K> get keys => new _HashTableKeyIterable<K>(_hashTable); | 106 /* patch */ Iterable<K> get keys => new _HashTableKeyIterable<K>(_hashTable); |
128 Iterable<V> get values => | 107 /* patch */ Iterable<V> get values => |
129 new _HashTableValueIterable<V>(_hashTable, _HashMapTable._VALUE_INDEX); | 108 new _HashTableValueIterable<V>(_hashTable, _HashMapTable._VALUE_INDEX); |
130 | 109 |
131 int get length => _hashTable._elementCount; | 110 /* patch */ int get length => _hashTable._elementCount; |
132 | 111 |
133 bool get isEmpty => _hashTable._elementCount == 0; | 112 /* patch */ bool get isEmpty => _hashTable._elementCount == 0; |
134 | |
135 String toString() => Maps.mapToString(this); | |
136 } | 113 } |
OLD | NEW |