OLD | NEW |
---|---|
(Empty) | |
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 | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 part of dart.collection; | |
6 | |
7 class _DeadEntry { | |
8 const _DeadEntry(); | |
9 } | |
10 | |
11 class _NullKey { | |
12 const _NullKey(); | |
13 int get hashCode => null.hashCode; | |
14 } | |
15 | |
16 const _TOMBSTONE = const _DeadEntry(); | |
17 const _NULL = const _NullKey(); | |
18 | |
19 class _HashTable<K> { | |
20 /** | |
21 * Table of entries with [_entrySize] slots per entry. | |
22 * | |
23 * Capacity in entries must be factor of two. | |
24 */ | |
25 List _table; | |
26 /** Current capacity. Always equal to [:_table.length ~/ _entrySize:]. */ | |
27 int _capacity; | |
28 /** Count of occupied entries, including deleted ones. */ | |
29 int _entryCount = 0; | |
30 /** Count of deleted entries. */ | |
31 int _deletedCount = 0; | |
32 /** Counter incremented when table is modified. */ | |
33 int _modificationCount = 0; | |
34 /** If set, used as the source object for [ConcurrentModificationError]s. */ | |
35 Object _container; | |
36 | |
37 _HashTable(int initialCapacity) : _capacity = initialCapacity { | |
38 _table = _createTable(initialCapacity); | |
39 } | |
40 | |
41 /** Reads key from table. Converts _NULL marker to null. */ | |
42 Object _key(offset) { | |
43 assert(!_isFree(_table[offset])); | |
44 Object key = _table[offset]; | |
45 if (!identical(key, _NULL)) return key; | |
46 return null; | |
47 } | |
48 | |
49 /** Writes key to table. Converts null to _NULL marker. */ | |
50 void _setKey(int offset, Object key) { | |
51 if (key == null) key = _NULL; | |
52 _table[offset] = key; | |
53 } | |
54 | |
55 int get _elementCount => _entryCount - _deletedCount; | |
56 | |
57 /** Size of each entry. */ | |
58 int get _entrySize => 1; | |
59 | |
60 void _checkModification(int expectedModificationCount) { | |
61 if (_modificationCount != expectedModificationCount) { | |
62 throw new ConcurrentModificationError(_container); | |
63 } | |
64 } | |
65 | |
66 void _recordModification() { | |
67 // Value cycles after 2^30 modifications. If you keep hold of an | |
68 // iterator for that long, you might miss a modification detection, | |
69 // and iteration can go sour. Don't do that. | |
70 _modificationCount = (_modificationCount + 1) & (0x3FFFFFFF); | |
71 } | |
72 | |
73 /** | |
74 * Create an empty table. | |
75 */ | |
76 List _createTable(int capacity) { | |
77 List table = new List.fixedLength(capacity * _entrySize); | |
78 return table; | |
79 } | |
80 | |
81 /** First table probe. */ | |
82 int _firstProbe(int hashCode, int capacity) { | |
83 return hashCode & (capacity - 1); | |
84 } | |
85 | |
86 /** Following table probes. */ | |
87 int _nextProbe(int previousIndex, int probeCount, int capacity) { | |
floitsch
2013/02/13 15:54:06
Add comment that this will hit every index eventua
Lasse Reichstein Nielsen
2013/02/14 10:18:12
Done.
| |
88 return (previousIndex + probeCount) & (capacity - 1); | |
89 } | |
90 | |
91 /** Whether an object is a free-marker (either tombstone or free). */ | |
92 bool _isFree(Object marker) => | |
93 marker == null || identical(marker, _TOMBSTONE); | |
94 | |
95 /** | |
96 * Look up the offset for an object in the table. | |
97 * | |
98 * Finds the offset of the object in the table, if it is there, | |
99 * or the first free offset for its hashCode. | |
100 */ | |
101 int _probeForAdd(int hashCode, Object object) { | |
102 int entrySize = _entrySize; | |
103 int index = _firstProbe(hashCode, _capacity); | |
104 int firstTombstone = -1; | |
105 int probeCount = 0; | |
106 while (true) { | |
107 int offset = index * entrySize; | |
108 Object entry = _table[offset]; | |
109 if (identical(entry, _TOMBSTONE)) { | |
110 if (firstTombstone < 0) firstTombstone = offset; | |
111 } else if (entry == null) { | |
112 if (firstTombstone < 0) return offset; | |
113 return firstTombstone; | |
114 } else if (identical(_NULL, entry) ? _equals(null, object) | |
115 : _equals(entry, object)) { | |
116 return offset; | |
117 } | |
118 // The _nextProbe is designed so that it hits | |
119 // every index eventually. | |
120 index = _nextProbe(index, ++probeCount, _capacity); | |
121 } | |
122 } | |
123 | |
124 /** | |
125 * Look up the offset for an object in the table. | |
126 * | |
127 * If the object is in the table, its offset is returned. | |
128 * | |
129 * If the object is not in the table, Otherwise a negative value is returned. | |
130 */ | |
131 int _probeForLookup(int hashCode, Object object) { | |
132 int entrySize = _entrySize; | |
133 int index = _firstProbe(hashCode, _capacity); | |
134 int probeCount = 0; | |
135 while (true) { | |
136 int offset = index * entrySize; | |
137 Object entry = _table[offset]; | |
138 if (entry == null) { | |
139 return -1; | |
140 } else if (identical(_NULL, entry) ? _equals(null, object) | |
141 : _equals(entry, object)) { | |
142 // If entry is _TOMBSTONE, it matches nothing. | |
floitsch
2013/02/13 15:54:06
I would prefer if "_TOMBSTONE" didn't escape to "_
Lasse Reichstein Nielsen
2013/02/14 10:18:12
Good argument, done.
| |
143 // Consider special casing it to make 'equals' calls monomorphic. | |
144 return offset; | |
145 } | |
146 // The _nextProbe is designed so that it hits | |
147 // every index eventually. | |
148 index = _nextProbe(index, ++probeCount, _capacity); | |
149 } | |
150 } | |
151 | |
152 // Override the following two to change equality/hashCode computations | |
153 | |
154 /** | |
155 * Compare two object for equality. | |
156 * | |
157 * The first object is the one already in the table, | |
158 * and the second is the one being searched for. | |
159 */ | |
160 bool _equals(Object element, Object other) { | |
161 return element == other; | |
162 } | |
163 | |
164 /** | |
165 * Compute hash-code for an object. | |
166 */ | |
167 int _hashCodeOf(Object object) => object.hashCode; | |
168 | |
169 /** | |
170 * Ensure that the table isn't too full for its own good. | |
171 * | |
172 * Call this after adding an element. | |
173 */ | |
174 int _checkCapacity() { | |
175 // Compute everything in multiples of entrySize to avoid division. | |
176 int freeCount = _capacity - _entryCount; | |
177 if (freeCount * 4 < _capacity || | |
178 freeCount < _deletedCount) { | |
179 // Less than 25% free or more deleted entries than free entries. | |
180 _grow(_entryCount - _deletedCount); | |
181 } | |
182 } | |
183 | |
184 void _grow(int contentCount) { | |
185 int capacity = _capacity; | |
186 // Don't grow to less than twice the needed capacity. | |
187 int minCapacity = contentCount * 2; | |
188 while (capacity < minCapacity) { | |
189 capacity *= 2; | |
190 } | |
191 // Reset to another table and add all existing elements. | |
192 List oldTable = _table; | |
193 _table = _createTable(capacity); | |
194 _capacity = capacity; | |
195 _entryCount = 0; | |
196 _deletedCount = 0; | |
197 _addAllEntries(oldTable); | |
198 _recordModification(); | |
199 } | |
200 | |
201 /** | |
202 * Copies all non-free entries from the old table to the new empty table. | |
203 */ | |
204 void _addAllEntries(List oldTable) { | |
205 for (int i = 0; i < oldTable.length; i += _entrySize) { | |
206 Object object = oldTable[i]; | |
207 if (!_isFree(object)) { | |
208 int toOffset = _put(object); | |
209 _copyEntry(oldTable, i, toOffset); | |
210 } | |
211 } | |
212 } | |
213 | |
214 /** | |
215 * Copies everything but the key element from one entry to another. | |
216 * | |
217 * Called while growing the base array. | |
218 * | |
219 * Override this if any non-key fields need copying. | |
220 */ | |
221 void _copyEntry(List fromTable, int fromOffset, int toOffset) {} | |
222 | |
223 // The following three methods are for simple get/set/remove operations. | |
224 // They only affect the key of an entry. The remaining fields must be | |
225 // filled by the caller. | |
226 | |
227 /** | |
228 * Returns the offset of a key in [_table], or negative if it's not there. | |
229 */ | |
230 int _get(K key) { | |
231 return _probeForLookup(_hashCodeOf(key), key); | |
232 } | |
233 | |
234 /** | |
235 * Puts the key into the table and returns its offset into [_table]. | |
236 * | |
237 * If [_entrySize] is greater than 1, the caller should fill the | |
238 * remaining fields. | |
239 * | |
240 * Remember to call [_checkCapacity] after using this method. | |
241 */ | |
242 int _put(K key) { | |
243 int offset = _probeForAdd(_hashCodeOf(key), key); | |
244 Object oldEntry = _table[offset]; | |
245 if (oldEntry == null) { | |
246 _entryCount++; | |
247 } else if (identical(oldEntry, _TOMBSTONE)) { | |
248 _deletedCount--; | |
249 } else { | |
250 return offset; | |
251 } | |
252 _setKey(offset, key); | |
253 _recordModification(); | |
254 return offset; | |
255 } | |
256 | |
257 /** | |
258 * Removes a key from the table and returns its offset into [_table]. | |
259 * | |
260 * Returns null if the key was not in the table. | |
261 * If [_entrySize] is greater than 1, the caller should clean up the | |
262 * remaining fields. | |
263 */ | |
264 int _remove(K key) { | |
265 int offset = _probeForLookup(_hashCodeOf(key), key); | |
266 if (offset >= 0) { | |
267 _deleteEntry(offset); | |
268 } | |
269 return offset; | |
270 } | |
271 | |
272 /** Clears the table completely, leaving it empty. */ | |
273 void _clear() { | |
floitsch
2013/02/13 15:54:06
Should we also shrink the table?
Lasse Reichstein Nielsen
2013/02/14 10:18:12
Let's not do that now. If you reuse a set that gre
| |
274 if (_elementCount == 0) return; | |
275 for (int i = 0; i < _table.length; i++) { | |
276 _table[i] = null; | |
277 } | |
278 _entryCount = _deletedCount = 0; | |
279 _recordModification(); | |
280 } | |
281 | |
282 /** Clears an entry in the table. */ | |
283 void _deleteEntry(int offset) { | |
284 assert(!_isFree(_table[offset])); | |
285 _setKey(offset, _TOMBSTONE); | |
286 _deletedCount++; | |
287 _recordModification(); | |
288 } | |
289 } | |
290 | |
291 /** | |
292 * Generic iterable based on a [_HashTable]. | |
293 */ | |
294 abstract class _HashTableIterable<E> extends Iterable<E> { | |
295 final _HashTable _hashTable; | |
296 _HashTableIterable(this._hashTable); | |
297 | |
298 Iterator<E> get iterator; | |
299 | |
300 /** | |
301 * Return the iterated value for a given entry. | |
302 */ | |
303 E _valueAt(int offset, Object key); | |
304 | |
305 int get length => _hashTable._elementCount; | |
306 | |
307 /** | |
308 * Iterates over non-free entries of the table. | |
309 * | |
310 * I | |
311 */ | |
312 void forEach(void action(E element)) { | |
313 int entrySize = _hashTable._entrySize; | |
314 List table = _hashTable._table; | |
315 int modificationCount = _hashTable._modificationCount; | |
316 for (int offset = 0; offset < table.length; offset += entrySize) { | |
317 Object entry = table[offset]; | |
318 if (!_hashTable._isFree(entry)) { | |
319 E value = _valueAt(offset, entry); | |
320 action(value); | |
321 } | |
322 _hashTable._checkModification(modificationCount); | |
323 } | |
324 } | |
325 | |
326 bool get isEmpty => _hashTable._elementCount == 0; | |
327 | |
328 E get single { | |
floitsch
2013/02/13 15:54:06
Why this special case? You still allocate an itera
Lasse Reichstein Nielsen
2013/02/14 10:18:12
True. It changes the behavior so you only need to
| |
329 if (_hashTable._elementCount > 1) { | |
330 throw new StateError("More than one element"); | |
331 } | |
332 return first; | |
333 } | |
334 } | |
335 | |
336 abstract class _HashTableIterator<E> implements Iterator<E> { | |
337 final _HashTable _hashTable; | |
338 final int _modificationCount; | |
339 /** Location right after last found element. */ | |
340 int _offset = 0; | |
341 E _current = null; | |
342 | |
343 _HashTableIterator(_HashTable hashTable) | |
344 : _hashTable = hashTable, | |
345 _modificationCount = hashTable._modificationCount; | |
346 | |
347 bool moveNext() { | |
348 _hashTable._checkModification(_modificationCount); | |
349 | |
350 List table = _hashTable._table; | |
351 int entrySize = _hashTable._entrySize; | |
352 | |
353 while (_offset < table.length) { | |
354 int currentOffset = _offset; | |
355 Object entry = table[currentOffset]; | |
356 _offset = currentOffset + entrySize; | |
357 if (!_hashTable._isFree(entry)) { | |
358 _current = _valueAt(currentOffset, entry); | |
359 return true; | |
360 } | |
361 } | |
362 _current = null; | |
363 return false; | |
364 } | |
365 | |
366 E get current => _current; | |
367 | |
368 E _valueAt(int offset, Object key); | |
369 } | |
370 | |
371 class _HashTableKeyIterable<K> extends _HashTableIterable<K> { | |
372 _HashTableKeyIterable(_HashTable<K> hashTable) : super(hashTable); | |
373 | |
374 Iterator<K> get iterator => new _HashTableKeyIterator<K>(_hashTable); | |
375 | |
376 K _valueAt(int offset, Object key) { | |
377 if (identical(key, _NULL)) return null; | |
378 return key; | |
379 } | |
380 | |
381 bool contains(Object value) => _hashTable._get(value) >= 0; | |
382 } | |
383 | |
384 class _HashTableKeyIterator<K> extends _HashTableIterator<K> { | |
385 _HashTableKeyIterator(_HashTable hashTable) : super(hashTable); | |
386 | |
387 K _valueAt(int offset, Object key) { | |
388 if (identical(key, _NULL)) return null; | |
389 return key; | |
390 } | |
391 } | |
392 | |
393 class _HashTableValueIterable<V> extends _HashTableIterable<V> { | |
394 final int _entryIndex; | |
395 | |
396 _HashTableValueIterable(_HashTable hashTable, this._entryIndex) | |
397 : super(hashTable); | |
398 | |
399 Iterator<V> get iterator { | |
400 return new _HashTableValueIterator<V>(_hashTable, _entryIndex); | |
401 } | |
402 | |
403 V _valueAt(int offset, Object key) => _hashTable._table[offset + _entryIndex]; | |
404 } | |
405 | |
406 class _HashTableValueIterator<V> extends _HashTableIterator<V> { | |
407 final int _entryIndex; | |
408 | |
409 _HashTableValueIterator(_HashTable hashTable, this._entryIndex) | |
410 : super(hashTable); | |
411 | |
412 V _valueAt(int offset, Object key) => _hashTable._table[offset + _entryIndex]; | |
413 } | |
OLD | NEW |