| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2012, 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 // Hash map implementation with open addressing and quadratic probing. | |
| 6 class HashMapImplementation<K extends Hashable, V> implements HashMap<K, V> { | |
| 7 | |
| 8 // The [_keys] list contains the keys inserted in the map. | |
| 9 // The [_keys] list must be a raw list because it | |
| 10 // will contain both elements of type K, and the [_DELETED_KEY] of type | |
| 11 // [_DeletedKeySentinel]. | |
| 12 // The alternative of declaring the [_keys] list as of type Object | |
| 13 // does not work, because the HashSetIterator constructor would fail: | |
| 14 // HashSetIterator(HashSet<E> set) | |
| 15 // : _nextValidIndex = -1, | |
| 16 // _entries = set_._backingMap._keys { | |
| 17 // _advance(); | |
| 18 // } | |
| 19 // With K being type int, for example, it would fail because | |
| 20 // List<Object> is not assignable to type List<int> of entries. | |
| 21 List _keys; | |
| 22 | |
| 23 // The values inserted in the map. For a filled entry index in this | |
| 24 // list, there is always the corresponding key in the [keys_] list | |
| 25 // at the same entry index. | |
| 26 List<V> _values; | |
| 27 | |
| 28 // The load limit is the number of entries we allow until we double | |
| 29 // the size of the lists. | |
| 30 int _loadLimit; | |
| 31 | |
| 32 // The current number of entries in the map. Will never be greater | |
| 33 // than [_loadLimit]. | |
| 34 int _numberOfEntries; | |
| 35 | |
| 36 // The current number of deleted entries in the map. | |
| 37 int _numberOfDeleted; | |
| 38 | |
| 39 // The sentinel when a key is deleted from the map. | |
| 40 static final _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel(); | |
| 41 | |
| 42 // The initial capacity of a hash map. | |
| 43 static final int _INITIAL_CAPACITY = 8; // must be power of 2 | |
| 44 | |
| 45 HashMapImplementation() { | |
| 46 _numberOfEntries = 0; | |
| 47 _numberOfDeleted = 0; | |
| 48 _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY); | |
| 49 _keys = new List(_INITIAL_CAPACITY); | |
| 50 _values = new List<V>(_INITIAL_CAPACITY); | |
| 51 } | |
| 52 | |
| 53 factory HashMapImplementation.from(Map<K, V> other) { | |
| 54 Map<K, V> result = new HashMapImplementation<K, V>(); | |
| 55 other.forEach((K key, V value) { result[key] = value; }); | |
| 56 return result; | |
| 57 } | |
| 58 | |
| 59 static int _computeLoadLimit(int capacity) { | |
| 60 return (capacity * 3) ~/ 4; | |
| 61 } | |
| 62 | |
| 63 static int _firstProbe(int hashCode, int length) { | |
| 64 return hashCode & (length - 1); | |
| 65 } | |
| 66 | |
| 67 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { | |
| 68 return (currentProbe + numberOfProbes) & (length - 1); | |
| 69 } | |
| 70 | |
| 71 int _probeForAdding(K key) { | |
| 72 int hash = _firstProbe(key.hashCode(), _keys.length); | |
| 73 int numberOfProbes = 1; | |
| 74 int initialHash = hash; | |
| 75 // insertionIndex points to a slot where a key was deleted. | |
| 76 int insertionIndex = -1; | |
| 77 while (true) { | |
| 78 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | |
| 79 Object existingKey = _keys[hash]; | |
| 80 if (existingKey === null) { | |
| 81 // We are sure the key is not already in the set. | |
| 82 // If the current slot is empty and we didn't find any | |
| 83 // insertion slot before, return this slot. | |
| 84 if (insertionIndex < 0) return hash; | |
| 85 // If we did find an insertion slot before, return it. | |
| 86 return insertionIndex; | |
| 87 } else if (existingKey == key) { | |
| 88 // The key is already in the map. Return its slot. | |
| 89 return hash; | |
| 90 } else if ((insertionIndex < 0) && (_DELETED_KEY === existingKey)) { | |
| 91 // The slot contains a deleted element. Because previous calls to this | |
| 92 // method may not have had this slot deleted, we must continue iterate | |
| 93 // to find if there is a slot with the given key. | |
| 94 insertionIndex = hash; | |
| 95 } | |
| 96 | |
| 97 // We did not find an insertion slot. Look at the next one. | |
| 98 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | |
| 99 // _ensureCapacity has guaranteed the following cannot happen. | |
| 100 // assert(hash != initialHash); | |
| 101 } | |
| 102 } | |
| 103 | |
| 104 int _probeForLookup(K key) { | |
| 105 int hash = _firstProbe(key.hashCode(), _keys.length); | |
| 106 int numberOfProbes = 1; | |
| 107 int initialHash = hash; | |
| 108 while (true) { | |
| 109 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | |
| 110 Object existingKey = _keys[hash]; | |
| 111 // If the slot does not contain anything (in particular, it does not | |
| 112 // contain a deleted key), we know the key is not in the map. | |
| 113 if (existingKey === null) return -1; | |
| 114 // The key is in the map, return its index. | |
| 115 if (existingKey == key) return hash; | |
| 116 // Go to the next probe. | |
| 117 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | |
| 118 // _ensureCapacity has guaranteed the following cannot happen. | |
| 119 // assert(hash != initialHash); | |
| 120 } | |
| 121 } | |
| 122 | |
| 123 void _ensureCapacity() { | |
| 124 int newNumberOfEntries = _numberOfEntries + 1; | |
| 125 // Test if adding an element will reach the load limit. | |
| 126 if (newNumberOfEntries >= _loadLimit) { | |
| 127 _grow(_keys.length * 2); | |
| 128 return; | |
| 129 } | |
| 130 | |
| 131 // Make sure that we don't have poor performance when a map | |
| 132 // contains lots of deleted entries: we _grow if | |
| 133 // there are more deleted entried than free entries. | |
| 134 int capacity = _keys.length; | |
| 135 int numberOfFreeOrDeleted = capacity - newNumberOfEntries; | |
| 136 int numberOfFree = numberOfFreeOrDeleted - _numberOfDeleted; | |
| 137 // assert(numberOfFree > 0); | |
| 138 if (_numberOfDeleted > numberOfFree) { | |
| 139 _grow(_keys.length); | |
| 140 } | |
| 141 } | |
| 142 | |
| 143 static bool _isPowerOfTwo(int x) { | |
| 144 return ((x & (x - 1)) == 0); | |
| 145 } | |
| 146 | |
| 147 void _grow(int newCapacity) { | |
| 148 assert(_isPowerOfTwo(newCapacity)); | |
| 149 int capacity = _keys.length; | |
| 150 _loadLimit = _computeLoadLimit(newCapacity); | |
| 151 List oldKeys = _keys; | |
| 152 List<V> oldValues = _values; | |
| 153 _keys = new List(newCapacity); | |
| 154 _values = new List<V>(newCapacity); | |
| 155 for (int i = 0; i < capacity; i++) { | |
| 156 // [key] can be either of type [K] or [_DeletedKeySentinel]. | |
| 157 Object key = oldKeys[i]; | |
| 158 // If there is no key, we don't need to deal with the current slot. | |
| 159 if (key === null || key === _DELETED_KEY) { | |
| 160 continue; | |
| 161 } | |
| 162 V value = oldValues[i]; | |
| 163 // Insert the {key, value} pair in their new slot. | |
| 164 int newIndex = _probeForAdding(key); | |
| 165 _keys[newIndex] = key; | |
| 166 _values[newIndex] = value; | |
| 167 } | |
| 168 _numberOfDeleted = 0; | |
| 169 } | |
| 170 | |
| 171 void clear() { | |
| 172 _numberOfEntries = 0; | |
| 173 _numberOfDeleted = 0; | |
| 174 int length = _keys.length; | |
| 175 for (int i = 0; i < length; i++) { | |
| 176 _keys[i] = null; | |
| 177 _values[i] = null; | |
| 178 } | |
| 179 } | |
| 180 | |
| 181 void operator []=(K key, V value) { | |
| 182 _ensureCapacity(); | |
| 183 int index = _probeForAdding(key); | |
| 184 if ((_keys[index] === null) || (_keys[index] === _DELETED_KEY)) { | |
| 185 _numberOfEntries++; | |
| 186 } | |
| 187 _keys[index] = key; | |
| 188 _values[index] = value; | |
| 189 } | |
| 190 | |
| 191 V operator [](K key) { | |
| 192 int index = _probeForLookup(key); | |
| 193 if (index < 0) return null; | |
| 194 return _values[index]; | |
| 195 } | |
| 196 | |
| 197 V putIfAbsent(K key, V ifAbsent()) { | |
| 198 int index = _probeForLookup(key); | |
| 199 if (index >=0) return _values[index]; | |
| 200 | |
| 201 V value = ifAbsent(); | |
| 202 this[key] = value; | |
| 203 return value; | |
| 204 } | |
| 205 | |
| 206 V remove(K key) { | |
| 207 int index = _probeForLookup(key); | |
| 208 if (index >= 0) { | |
| 209 _numberOfEntries--; | |
| 210 V value = _values[index]; | |
| 211 _values[index] = null; | |
| 212 // Set the key to the sentinel to not break the probing chain. | |
| 213 _keys[index] = _DELETED_KEY; | |
| 214 _numberOfDeleted++; | |
| 215 return value; | |
| 216 } | |
| 217 return null; | |
| 218 } | |
| 219 | |
| 220 bool isEmpty() { | |
| 221 return _numberOfEntries == 0; | |
| 222 } | |
| 223 | |
| 224 int get length() { | |
| 225 return _numberOfEntries; | |
| 226 } | |
| 227 | |
| 228 void forEach(void f(K key, V value)) { | |
| 229 int length = _keys.length; | |
| 230 for (int i = 0; i < length; i++) { | |
| 231 var key = _keys[i]; | |
| 232 if ((key !== null) && (key !== _DELETED_KEY)) { | |
| 233 f(key, _values[i]); | |
| 234 } | |
| 235 } | |
| 236 } | |
| 237 | |
| 238 | |
| 239 Collection<K> getKeys() { | |
| 240 List<K> list = new List<K>(length); | |
| 241 int i = 0; | |
| 242 forEach(void _(K key, V value) { | |
| 243 list[i++] = key; | |
| 244 }); | |
| 245 return list; | |
| 246 } | |
| 247 | |
| 248 Collection<V> getValues() { | |
| 249 List<V> list = new List<V>(length); | |
| 250 int i = 0; | |
| 251 forEach(void _(K key, V value) { | |
| 252 list[i++] = value; | |
| 253 }); | |
| 254 return list; | |
| 255 } | |
| 256 | |
| 257 bool containsKey(K key) { | |
| 258 return (_probeForLookup(key) != -1); | |
| 259 } | |
| 260 | |
| 261 bool containsValue(V value) { | |
| 262 int length = _values.length; | |
| 263 for (int i = 0; i < length; i++) { | |
| 264 var key = _keys[i]; | |
| 265 if ((key !== null) && (key !== _DELETED_KEY)) { | |
| 266 if (_values[i] == value) return true; | |
| 267 } | |
| 268 } | |
| 269 return false; | |
| 270 } | |
| 271 | |
| 272 String toString() { | |
| 273 return Maps.mapToString(this); | |
| 274 } | |
| 275 } | |
| 276 | |
| 277 class HashSetImplementation<E extends Hashable> implements HashSet<E> { | |
| 278 | |
| 279 HashSetImplementation() { | |
| 280 _backingMap = new HashMapImplementation<E, E>(); | |
| 281 } | |
| 282 | |
| 283 factory HashSetImplementation.from(Iterable<E> other) { | |
| 284 Set<E> set = new HashSetImplementation<E>(); | |
| 285 for (final e in other) { | |
| 286 set.add(e); | |
| 287 } | |
| 288 return set; | |
| 289 } | |
| 290 | |
| 291 void clear() { | |
| 292 _backingMap.clear(); | |
| 293 } | |
| 294 | |
| 295 void add(E value) { | |
| 296 _backingMap[value] = value; | |
| 297 } | |
| 298 | |
| 299 bool contains(E value) { | |
| 300 return _backingMap.containsKey(value); | |
| 301 } | |
| 302 | |
| 303 bool remove(E value) { | |
| 304 if (!_backingMap.containsKey(value)) return false; | |
| 305 _backingMap.remove(value); | |
| 306 return true; | |
| 307 } | |
| 308 | |
| 309 void addAll(Collection<E> collection) { | |
| 310 collection.forEach(void _(E value) { | |
| 311 add(value); | |
| 312 }); | |
| 313 } | |
| 314 | |
| 315 Set<E> intersection(Collection<E> collection) { | |
| 316 Set<E> result = new Set<E>(); | |
| 317 collection.forEach(void _(E value) { | |
| 318 if (contains(value)) result.add(value); | |
| 319 }); | |
| 320 return result; | |
| 321 } | |
| 322 | |
| 323 bool isSubsetOf(Collection<E> other) { | |
| 324 return new Set<E>.from(other).containsAll(this); | |
| 325 } | |
| 326 | |
| 327 void removeAll(Collection<E> collection) { | |
| 328 collection.forEach(void _(E value) { | |
| 329 remove(value); | |
| 330 }); | |
| 331 } | |
| 332 | |
| 333 bool containsAll(Collection<E> collection) { | |
| 334 return collection.every(bool _(E value) { | |
| 335 return contains(value); | |
| 336 }); | |
| 337 } | |
| 338 | |
| 339 void forEach(void f(E element)) { | |
| 340 _backingMap.forEach(void _(E key, E value) { | |
| 341 f(key); | |
| 342 }); | |
| 343 } | |
| 344 | |
| 345 Set map(f(E element)) { | |
| 346 Set result = new Set(); | |
| 347 _backingMap.forEach(void _(E key, E value) { | |
| 348 result.add(f(key)); | |
| 349 }); | |
| 350 return result; | |
| 351 } | |
| 352 | |
| 353 Dynamic reduce(Dynamic initialValue, | |
| 354 Dynamic combine(Dynamic previousValue, E element)) { | |
| 355 return Collections.reduce(this, initialValue, combine); | |
| 356 } | |
| 357 | |
| 358 Set<E> filter(bool f(E element)) { | |
| 359 Set<E> result = new Set<E>(); | |
| 360 _backingMap.forEach(void _(E key, E value) { | |
| 361 if (f(key)) result.add(key); | |
| 362 }); | |
| 363 return result; | |
| 364 } | |
| 365 | |
| 366 bool every(bool f(E element)) { | |
| 367 Collection<E> keys = _backingMap.getKeys(); | |
| 368 return keys.every(f); | |
| 369 } | |
| 370 | |
| 371 bool some(bool f(E element)) { | |
| 372 Collection<E> keys = _backingMap.getKeys(); | |
| 373 return keys.some(f); | |
| 374 } | |
| 375 | |
| 376 bool isEmpty() { | |
| 377 return _backingMap.isEmpty(); | |
| 378 } | |
| 379 | |
| 380 int get length() { | |
| 381 return _backingMap.length; | |
| 382 } | |
| 383 | |
| 384 Iterator<E> iterator() { | |
| 385 return new HashSetIterator<E>(this); | |
| 386 } | |
| 387 | |
| 388 String toString() { | |
| 389 return Collections.collectionToString(this); | |
| 390 } | |
| 391 | |
| 392 // The map backing this set. The associations in this map are all | |
| 393 // of the form element -> element. If a value is not in the map, | |
| 394 // then it is not in the set. | |
| 395 HashMapImplementation<E, E> _backingMap; | |
| 396 } | |
| 397 | |
| 398 class HashSetIterator<E> implements Iterator<E> { | |
| 399 | |
| 400 // TODO(4504458): Replace set_ with set. | |
| 401 HashSetIterator(HashSetImplementation<E> set_) | |
| 402 : _nextValidIndex = -1, | |
| 403 _entries = set_._backingMap._keys { | |
| 404 _advance(); | |
| 405 } | |
| 406 | |
| 407 bool hasNext() { | |
| 408 if (_nextValidIndex >= _entries.length) return false; | |
| 409 if (_entries[_nextValidIndex] === HashMapImplementation._DELETED_KEY) { | |
| 410 // This happens in case the set was modified in the meantime. | |
| 411 // A modification on the set may make this iterator misbehave, | |
| 412 // but we should never return the sentinel. | |
| 413 _advance(); | |
| 414 } | |
| 415 return _nextValidIndex < _entries.length; | |
| 416 } | |
| 417 | |
| 418 E next() { | |
| 419 if (!hasNext()) { | |
| 420 throw const NoMoreElementsException(); | |
| 421 } | |
| 422 E res = _entries[_nextValidIndex]; | |
| 423 _advance(); | |
| 424 return res; | |
| 425 } | |
| 426 | |
| 427 void _advance() { | |
| 428 int length = _entries.length; | |
| 429 var entry; | |
| 430 final deletedKey = HashMapImplementation._DELETED_KEY; | |
| 431 do { | |
| 432 if (++_nextValidIndex >= length) break; | |
| 433 entry = _entries[_nextValidIndex]; | |
| 434 } while ((entry === null) || (entry === deletedKey)); | |
| 435 } | |
| 436 | |
| 437 // The entries in the set. May contain null or the sentinel value. | |
| 438 List<E> _entries; | |
| 439 | |
| 440 // The next valid index in [_entries] or the length of [entries_]. | |
| 441 // If it is the length of [_entries], calling [hasNext] on the | |
| 442 // iterator will return false. | |
| 443 int _nextValidIndex; | |
| 444 } | |
| 445 | |
| 446 /** | |
| 447 * A singleton sentinel used to represent when a key is deleted from the map. | |
| 448 * We can't use [: const Object() :] as a sentinel because it would end up | |
| 449 * canonicalized and then we cannot distinguish the deleted key from the | |
| 450 * canonicalized [: Object() :]. | |
| 451 */ | |
| 452 class _DeletedKeySentinel { | |
| 453 const _DeletedKeySentinel(); | |
| 454 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 10890030:
Move core and coreimpl from corelib/ to lib/core and lib/coreimpl. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart