| 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 /** | |
| 6 * Classes and utilities that supplement the collection support in dart:core. | |
| 7 */ | |
| 8 library dart.collection; | |
| 9 | |
| 10 import 'dart:_internal'; | |
| 11 import 'dart:math' show Random; | |
| 12 import 'dart:_foreign_helper' show JS; | |
| 13 import 'dart:_js_helper' show | |
| 14 fillLiteralMap, InternalMap, NoInline, NoThrows, patch; // Used by ListMixi
n.shuffle. | |
| 15 | |
| 16 part 'collections.dart'; | |
| 17 part 'hash_map.dart'; | |
| 18 part 'hash_set.dart'; | |
| 19 part 'iterable.dart'; | |
| 20 part 'iterator.dart'; | |
| 21 part 'linked_hash_map.dart'; | |
| 22 part 'linked_hash_set.dart'; | |
| 23 part 'linked_list.dart'; | |
| 24 part 'list.dart'; | |
| 25 part 'maps.dart'; | |
| 26 part 'queue.dart'; | |
| 27 part 'set.dart'; | |
| 28 part 'splay_tree.dart'; | |
| 29 | |
| 30 class _HashMap<K, V> implements HashMap<K, V> { | |
| 31 int _length = 0; | |
| 32 | |
| 33 // The hash map contents are divided into three parts: one part for | |
| 34 // string keys, one for numeric keys, and one for the rest. String | |
| 35 // and numeric keys map directly to their values, but the rest of | |
| 36 // the entries are stored in bucket lists of the form: | |
| 37 // | |
| 38 // [key-0, value-0, key-1, value-1, ...] | |
| 39 // | |
| 40 // where all keys in the same bucket share the same hash code. | |
| 41 var _strings; | |
| 42 var _nums; | |
| 43 var _rest; | |
| 44 | |
| 45 // When iterating over the hash map, it is very convenient to have a | |
| 46 // list of all the keys. We cache that on the instance and clear the | |
| 47 // the cache whenever the key set changes. This is also used to | |
| 48 // guard against concurrent modifications. | |
| 49 List _keys; | |
| 50 | |
| 51 _HashMap(); | |
| 52 | |
| 53 | |
| 54 int get length => _length; | |
| 55 bool get isEmpty => _length == 0; | |
| 56 bool get isNotEmpty => !isEmpty; | |
| 57 | |
| 58 Iterable<K> get keys { | |
| 59 return new HashMapKeyIterable<K>(this); | |
| 60 } | |
| 61 | |
| 62 Iterable<V> get values { | |
| 63 return new MappedIterable<K, V>(keys, (each) => this[each]); | |
| 64 } | |
| 65 | |
| 66 bool containsKey(Object key) { | |
| 67 if (_isStringKey(key)) { | |
| 68 var strings = _strings; | |
| 69 return (strings == null) ? false : _hasTableEntry(strings, key); | |
| 70 } else if (_isNumericKey(key)) { | |
| 71 var nums = _nums; | |
| 72 return (nums == null) ? false : _hasTableEntry(nums, key); | |
| 73 } else { | |
| 74 return _containsKey(key); | |
| 75 } | |
| 76 } | |
| 77 | |
| 78 bool _containsKey(Object key) { | |
| 79 var rest = _rest; | |
| 80 if (rest == null) return false; | |
| 81 var bucket = _getBucket(rest, key); | |
| 82 return _findBucketIndex(bucket, key) >= 0; | |
| 83 } | |
| 84 | |
| 85 bool containsValue(Object value) { | |
| 86 return _computeKeys().any((each) => this[each] == value); | |
| 87 } | |
| 88 | |
| 89 void addAll(Map<K, V> other) { | |
| 90 other.forEach((K key, V value) { | |
| 91 this[key] = value; | |
| 92 }); | |
| 93 } | |
| 94 | |
| 95 V operator[](Object key) { | |
| 96 if (_isStringKey(key)) { | |
| 97 var strings = _strings; | |
| 98 return (strings == null) ? null : _getTableEntry(strings, key); | |
| 99 } else if (_isNumericKey(key)) { | |
| 100 var nums = _nums; | |
| 101 return (nums == null) ? null : _getTableEntry(nums, key); | |
| 102 } else { | |
| 103 return _get(key); | |
| 104 } | |
| 105 } | |
| 106 | |
| 107 V _get(Object key) { | |
| 108 var rest = _rest; | |
| 109 if (rest == null) return null; | |
| 110 var bucket = _getBucket(rest, key); | |
| 111 int index = _findBucketIndex(bucket, key); | |
| 112 return (index < 0) ? null : JS('var', '#[#]', bucket, index + 1); | |
| 113 } | |
| 114 | |
| 115 void operator[]=(K key, V value) { | |
| 116 if (_isStringKey(key)) { | |
| 117 var strings = _strings; | |
| 118 if (strings == null) _strings = strings = _newHashTable(); | |
| 119 _addHashTableEntry(strings, key, value); | |
| 120 } else if (_isNumericKey(key)) { | |
| 121 var nums = _nums; | |
| 122 if (nums == null) _nums = nums = _newHashTable(); | |
| 123 _addHashTableEntry(nums, key, value); | |
| 124 } else { | |
| 125 _set(key, value); | |
| 126 } | |
| 127 } | |
| 128 | |
| 129 void _set(K key, V value) { | |
| 130 var rest = _rest; | |
| 131 if (rest == null) _rest = rest = _newHashTable(); | |
| 132 var hash = _computeHashCode(key); | |
| 133 var bucket = JS('var', '#[#]', rest, hash); | |
| 134 if (bucket == null) { | |
| 135 _setTableEntry(rest, hash, JS('var', '[#, #]', key, value)); | |
| 136 _length++; | |
| 137 _keys = null; | |
| 138 } else { | |
| 139 int index = _findBucketIndex(bucket, key); | |
| 140 if (index >= 0) { | |
| 141 JS('void', '#[#] = #', bucket, index + 1, value); | |
| 142 } else { | |
| 143 JS('void', '#.push(#, #)', bucket, key, value); | |
| 144 _length++; | |
| 145 _keys = null; | |
| 146 } | |
| 147 } | |
| 148 } | |
| 149 | |
| 150 V putIfAbsent(K key, V ifAbsent()) { | |
| 151 if (containsKey(key)) return this[key]; | |
| 152 V value = ifAbsent(); | |
| 153 this[key] = value; | |
| 154 return value; | |
| 155 } | |
| 156 | |
| 157 V remove(Object key) { | |
| 158 if (_isStringKey(key)) { | |
| 159 return _removeHashTableEntry(_strings, key); | |
| 160 } else if (_isNumericKey(key)) { | |
| 161 return _removeHashTableEntry(_nums, key); | |
| 162 } else { | |
| 163 return _remove(key); | |
| 164 } | |
| 165 } | |
| 166 | |
| 167 V _remove(Object key) { | |
| 168 var rest = _rest; | |
| 169 if (rest == null) return null; | |
| 170 var bucket = _getBucket(rest, key); | |
| 171 int index = _findBucketIndex(bucket, key); | |
| 172 if (index < 0) return null; | |
| 173 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 174 // the length reaches zero. | |
| 175 _length--; | |
| 176 _keys = null; | |
| 177 // Use splice to remove the two [key, value] elements at the | |
| 178 // index and return the value. | |
| 179 return JS('var', '#.splice(#, 2)[1]', bucket, index); | |
| 180 } | |
| 181 | |
| 182 void clear() { | |
| 183 if (_length > 0) { | |
| 184 _strings = _nums = _rest = _keys = null; | |
| 185 _length = 0; | |
| 186 } | |
| 187 } | |
| 188 | |
| 189 void forEach(void action(K key, V value)) { | |
| 190 List keys = _computeKeys(); | |
| 191 for (int i = 0, length = keys.length; i < length; i++) { | |
| 192 var key = JS('var', '#[#]', keys, i); | |
| 193 action(key, this[key]); | |
| 194 if (JS('bool', '# !== #', keys, _keys)) { | |
| 195 throw new ConcurrentModificationError(this); | |
| 196 } | |
| 197 } | |
| 198 } | |
| 199 | |
| 200 List _computeKeys() { | |
| 201 if (_keys != null) return _keys; | |
| 202 List result = new List(_length); | |
| 203 int index = 0; | |
| 204 | |
| 205 // Add all string keys to the list. | |
| 206 var strings = _strings; | |
| 207 if (strings != null) { | |
| 208 var names = JS('var', 'Object.getOwnPropertyNames(#)', strings); | |
| 209 int entries = JS('int', '#.length', names); | |
| 210 for (int i = 0; i < entries; i++) { | |
| 211 String key = JS('String', '#[#]', names, i); | |
| 212 JS('void', '#[#] = #', result, index, key); | |
| 213 index++; | |
| 214 } | |
| 215 } | |
| 216 | |
| 217 // Add all numeric keys to the list. | |
| 218 var nums = _nums; | |
| 219 if (nums != null) { | |
| 220 var names = JS('var', 'Object.getOwnPropertyNames(#)', nums); | |
| 221 int entries = JS('int', '#.length', names); | |
| 222 for (int i = 0; i < entries; i++) { | |
| 223 // Object.getOwnPropertyNames returns a list of strings, so we | |
| 224 // have to convert the keys back to numbers (+). | |
| 225 num key = JS('num', '+#[#]', names, i); | |
| 226 JS('void', '#[#] = #', result, index, key); | |
| 227 index++; | |
| 228 } | |
| 229 } | |
| 230 | |
| 231 // Add all the remaining keys to the list. | |
| 232 var rest = _rest; | |
| 233 if (rest != null) { | |
| 234 var names = JS('var', 'Object.getOwnPropertyNames(#)', rest); | |
| 235 int entries = JS('int', '#.length', names); | |
| 236 for (int i = 0; i < entries; i++) { | |
| 237 var key = JS('String', '#[#]', names, i); | |
| 238 var bucket = JS('var', '#[#]', rest, key); | |
| 239 int length = JS('int', '#.length', bucket); | |
| 240 for (int i = 0; i < length; i += 2) { | |
| 241 var key = JS('var', '#[#]', bucket, i); | |
| 242 JS('void', '#[#] = #', result, index, key); | |
| 243 index++; | |
| 244 } | |
| 245 } | |
| 246 } | |
| 247 assert(index == _length); | |
| 248 return _keys = result; | |
| 249 } | |
| 250 | |
| 251 void _addHashTableEntry(var table, K key, V value) { | |
| 252 if (!_hasTableEntry(table, key)) { | |
| 253 _length++; | |
| 254 _keys = null; | |
| 255 } | |
| 256 _setTableEntry(table, key, value); | |
| 257 } | |
| 258 | |
| 259 V _removeHashTableEntry(var table, Object key) { | |
| 260 if (table != null && _hasTableEntry(table, key)) { | |
| 261 V value = _getTableEntry(table, key); | |
| 262 _deleteTableEntry(table, key); | |
| 263 _length--; | |
| 264 _keys = null; | |
| 265 return value; | |
| 266 } else { | |
| 267 return null; | |
| 268 } | |
| 269 } | |
| 270 | |
| 271 static bool _isStringKey(var key) { | |
| 272 return key is String && key != '__proto__'; | |
| 273 } | |
| 274 | |
| 275 static bool _isNumericKey(var key) { | |
| 276 // Only treat unsigned 30-bit integers as numeric keys. This way, | |
| 277 // we avoid converting them to strings when we use them as keys in | |
| 278 // the JavaScript hash table object. | |
| 279 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); | |
| 280 } | |
| 281 | |
| 282 int _computeHashCode(var key) { | |
| 283 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 284 // issues with problematic keys like '__proto__'. Another option | |
| 285 // would be to throw an exception if the hash code isn't a number. | |
| 286 return JS('int', '# & 0x3ffffff', key.hashCode); | |
| 287 } | |
| 288 | |
| 289 static bool _hasTableEntry(var table, var key) { | |
| 290 var entry = JS('var', '#[#]', table, key); | |
| 291 // We take care to only store non-null entries in the table, so we | |
| 292 // can check if the table has an entry for the given key with a | |
| 293 // simple null check. | |
| 294 return entry != null; | |
| 295 } | |
| 296 | |
| 297 static _getTableEntry(var table, var key) { | |
| 298 var entry = JS('var', '#[#]', table, key); | |
| 299 // We store the table itself as the entry to signal that it really | |
| 300 // is a null value, so we have to map back to null here. | |
| 301 return JS('bool', '# === #', entry, table) ? null : entry; | |
| 302 } | |
| 303 | |
| 304 static void _setTableEntry(var table, var key, var value) { | |
| 305 // We only store non-null entries in the table, so we have to | |
| 306 // change null values to refer to the table itself. Such values | |
| 307 // will be recognized and mapped back to null on access. | |
| 308 if (value == null) { | |
| 309 // Do not update [value] with [table], otherwise our | |
| 310 // optimizations could be confused by this opaque object being | |
| 311 // now used for more things than storing and fetching from it. | |
| 312 JS('void', '#[#] = #', table, key, table); | |
| 313 } else { | |
| 314 JS('void', '#[#] = #', table, key, value); | |
| 315 } | |
| 316 } | |
| 317 | |
| 318 static void _deleteTableEntry(var table, var key) { | |
| 319 JS('void', 'delete #[#]', table, key); | |
| 320 } | |
| 321 | |
| 322 List _getBucket(var table, var key) { | |
| 323 var hash = _computeHashCode(key); | |
| 324 return JS('var', '#[#]', table, hash); | |
| 325 } | |
| 326 | |
| 327 int _findBucketIndex(var bucket, var key) { | |
| 328 if (bucket == null) return -1; | |
| 329 int length = JS('int', '#.length', bucket); | |
| 330 for (int i = 0; i < length; i += 2) { | |
| 331 if (JS('var', '#[#]', bucket, i) == key) return i; | |
| 332 } | |
| 333 return -1; | |
| 334 } | |
| 335 | |
| 336 static _newHashTable() { | |
| 337 // Create a new JavaScript object to be used as a hash table. Use | |
| 338 // Object.create to avoid the properties on Object.prototype | |
| 339 // showing up as entries. | |
| 340 var table = JS('var', 'Object.create(null)'); | |
| 341 // Attempt to force the hash table into 'dictionary' mode by | |
| 342 // adding a property to it and deleting it again. | |
| 343 var temporaryKey = '<non-identifier-key>'; | |
| 344 _setTableEntry(table, temporaryKey, table); | |
| 345 _deleteTableEntry(table, temporaryKey); | |
| 346 return table; | |
| 347 } | |
| 348 } | |
| 349 class _IdentityHashMap<K, V> extends _HashMap<K, V> { | |
| 350 int _computeHashCode(var key) { | |
| 351 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 352 // issues with problematic keys like '__proto__'. Another option | |
| 353 // would be to throw an exception if the hash code isn't a number. | |
| 354 return JS('int', '# & 0x3ffffff', identityHashCode(key)); | |
| 355 } | |
| 356 | |
| 357 int _findBucketIndex(var bucket, var key) { | |
| 358 if (bucket == null) return -1; | |
| 359 int length = JS('int', '#.length', bucket); | |
| 360 for (int i = 0; i < length; i += 2) { | |
| 361 if (identical(JS('var', '#[#]', bucket, i), key)) return i; | |
| 362 } | |
| 363 return -1; | |
| 364 } | |
| 365 } | |
| 366 class _CustomHashMap<K, V> extends _HashMap<K, V> { | |
| 367 final _Equality<K> _equals; | |
| 368 final _Hasher<K> _hashCode; | |
| 369 final _Predicate<Object> _validKey; | |
| 370 _CustomHashMap(this._equals, this._hashCode, | |
| 371 bool validKey(Object potentialKey)) | |
| 372 : _validKey = (validKey != null) ? validKey : ((v) => v is K); | |
| 373 | |
| 374 V operator[](Object key) { | |
| 375 if (!_validKey(key)) return null; | |
| 376 return super._get(key); | |
| 377 } | |
| 378 | |
| 379 void operator[]=(K key, V value) { | |
| 380 super._set(key, value); | |
| 381 } | |
| 382 | |
| 383 bool containsKey(Object key) { | |
| 384 if (!_validKey(key)) return false; | |
| 385 return super._containsKey(key); | |
| 386 } | |
| 387 | |
| 388 V remove(Object key) { | |
| 389 if (!_validKey(key)) return null; | |
| 390 return super._remove(key); | |
| 391 } | |
| 392 | |
| 393 int _computeHashCode(var key) { | |
| 394 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 395 // issues with problematic keys like '__proto__'. Another option | |
| 396 // would be to throw an exception if the hash code isn't a number. | |
| 397 return JS('int', '# & 0x3ffffff', _hashCode(key)); | |
| 398 } | |
| 399 | |
| 400 int _findBucketIndex(var bucket, var key) { | |
| 401 if (bucket == null) return -1; | |
| 402 int length = JS('int', '#.length', bucket); | |
| 403 for (int i = 0; i < length; i += 2) { | |
| 404 if (_equals(JS('var', '#[#]', bucket, i), key)) return i; | |
| 405 } | |
| 406 return -1; | |
| 407 } | |
| 408 | |
| 409 String toString() => Maps.mapToString(this); | |
| 410 } | |
| 411 class HashMapKeyIterable<E> extends IterableBase<E> | |
| 412 implements EfficientLength { | |
| 413 final _map; | |
| 414 HashMapKeyIterable(this._map); | |
| 415 | |
| 416 int get length => _map._length; | |
| 417 bool get isEmpty => _map._length == 0; | |
| 418 | |
| 419 Iterator<E> get iterator { | |
| 420 return new HashMapKeyIterator<E>(_map, _map._computeKeys()); | |
| 421 } | |
| 422 | |
| 423 bool contains(Object element) { | |
| 424 return _map.containsKey(element); | |
| 425 } | |
| 426 | |
| 427 void forEach(void f(E element)) { | |
| 428 List keys = _map._computeKeys(); | |
| 429 for (int i = 0, length = JS('int', '#.length', keys); i < length; i++) { | |
| 430 f(JS('var', '#[#]', keys, i)); | |
| 431 if (JS('bool', '# !== #', keys, _map._keys)) { | |
| 432 throw new ConcurrentModificationError(_map); | |
| 433 } | |
| 434 } | |
| 435 } | |
| 436 } | |
| 437 class HashMapKeyIterator<E> implements Iterator<E> { | |
| 438 final _map; | |
| 439 final List _keys; | |
| 440 int _offset = 0; | |
| 441 E _current; | |
| 442 | |
| 443 HashMapKeyIterator(this._map, this._keys); | |
| 444 | |
| 445 E get current => _current; | |
| 446 | |
| 447 bool moveNext() { | |
| 448 var keys = _keys; | |
| 449 int offset = _offset; | |
| 450 if (JS('bool', '# !== #', keys, _map._keys)) { | |
| 451 throw new ConcurrentModificationError(_map); | |
| 452 } else if (offset >= JS('int', '#.length', keys)) { | |
| 453 _current = null; | |
| 454 return false; | |
| 455 } else { | |
| 456 _current = JS('var', '#[#]', keys, offset); | |
| 457 // TODO(kasperl): For now, we have to tell the type inferrer to | |
| 458 // treat the result of doing offset + 1 as an int. Otherwise, we | |
| 459 // get unnecessary bailout code. | |
| 460 _offset = JS('int', '#', offset + 1); | |
| 461 return true; | |
| 462 } | |
| 463 } | |
| 464 } | |
| 465 class _LinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap { | |
| 466 int _length = 0; | |
| 467 | |
| 468 // The hash map contents are divided into three parts: one part for | |
| 469 // string keys, one for numeric keys, and one for the rest. String | |
| 470 // and numeric keys map directly to their linked cells, but the rest | |
| 471 // of the entries are stored in bucket lists of the form: | |
| 472 // | |
| 473 // [cell-0, cell-1, ...] | |
| 474 // | |
| 475 // where all keys in the same bucket share the same hash code. | |
| 476 var _strings; | |
| 477 var _nums; | |
| 478 var _rest; | |
| 479 | |
| 480 // The keys and values are stored in cells that are linked together | |
| 481 // to form a double linked list. | |
| 482 LinkedHashMapCell _first; | |
| 483 LinkedHashMapCell _last; | |
| 484 | |
| 485 // We track the number of modifications done to the key set of the | |
| 486 // hash map to be able to throw when the map is modified while being | |
| 487 // iterated over. | |
| 488 int _modifications = 0; | |
| 489 | |
| 490 _LinkedHashMap(); | |
| 491 | |
| 492 | |
| 493 int get length => _length; | |
| 494 bool get isEmpty => _length == 0; | |
| 495 bool get isNotEmpty => !isEmpty; | |
| 496 | |
| 497 Iterable<K> get keys { | |
| 498 return new LinkedHashMapKeyIterable<K>(this); | |
| 499 } | |
| 500 | |
| 501 Iterable<V> get values { | |
| 502 return new MappedIterable<K, V>(keys, (each) => this[each]); | |
| 503 } | |
| 504 | |
| 505 bool containsKey(Object key) { | |
| 506 if (_isStringKey(key)) { | |
| 507 var strings = _strings; | |
| 508 if (strings == null) return false; | |
| 509 LinkedHashMapCell cell = _getTableEntry(strings, key); | |
| 510 return cell != null; | |
| 511 } else if (_isNumericKey(key)) { | |
| 512 var nums = _nums; | |
| 513 if (nums == null) return false; | |
| 514 LinkedHashMapCell cell = _getTableEntry(nums, key); | |
| 515 return cell != null; | |
| 516 } else { | |
| 517 return _containsKey(key); | |
| 518 } | |
| 519 } | |
| 520 | |
| 521 bool _containsKey(Object key) { | |
| 522 var rest = _rest; | |
| 523 if (rest == null) return false; | |
| 524 var bucket = _getBucket(rest, key); | |
| 525 return _findBucketIndex(bucket, key) >= 0; | |
| 526 } | |
| 527 | |
| 528 bool containsValue(Object value) { | |
| 529 return keys.any((each) => this[each] == value); | |
| 530 } | |
| 531 | |
| 532 void addAll(Map<K, V> other) { | |
| 533 other.forEach((K key, V value) { | |
| 534 this[key] = value; | |
| 535 }); | |
| 536 } | |
| 537 | |
| 538 V operator[](Object key) { | |
| 539 if (_isStringKey(key)) { | |
| 540 var strings = _strings; | |
| 541 if (strings == null) return null; | |
| 542 LinkedHashMapCell cell = _getTableEntry(strings, key); | |
| 543 return (cell == null) ? null : cell._value; | |
| 544 } else if (_isNumericKey(key)) { | |
| 545 var nums = _nums; | |
| 546 if (nums == null) return null; | |
| 547 LinkedHashMapCell cell = _getTableEntry(nums, key); | |
| 548 return (cell == null) ? null : cell._value; | |
| 549 } else { | |
| 550 return _get(key); | |
| 551 } | |
| 552 } | |
| 553 | |
| 554 V _get(Object key) { | |
| 555 var rest = _rest; | |
| 556 if (rest == null) return null; | |
| 557 var bucket = _getBucket(rest, key); | |
| 558 int index = _findBucketIndex(bucket, key); | |
| 559 if (index < 0) return null; | |
| 560 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | |
| 561 return cell._value; | |
| 562 } | |
| 563 | |
| 564 void operator[]=(K key, V value) { | |
| 565 if (_isStringKey(key)) { | |
| 566 var strings = _strings; | |
| 567 if (strings == null) _strings = strings = _newHashTable(); | |
| 568 _addHashTableEntry(strings, key, value); | |
| 569 } else if (_isNumericKey(key)) { | |
| 570 var nums = _nums; | |
| 571 if (nums == null) _nums = nums = _newHashTable(); | |
| 572 _addHashTableEntry(nums, key, value); | |
| 573 } else { | |
| 574 _set(key, value); | |
| 575 } | |
| 576 } | |
| 577 | |
| 578 void _set(K key, V value) { | |
| 579 var rest = _rest; | |
| 580 if (rest == null) _rest = rest = _newHashTable(); | |
| 581 var hash = _computeHashCode(key); | |
| 582 var bucket = JS('var', '#[#]', rest, hash); | |
| 583 if (bucket == null) { | |
| 584 LinkedHashMapCell cell = _newLinkedCell(key, value); | |
| 585 _setTableEntry(rest, hash, JS('var', '[#]', cell)); | |
| 586 } else { | |
| 587 int index = _findBucketIndex(bucket, key); | |
| 588 if (index >= 0) { | |
| 589 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | |
| 590 cell._value = value; | |
| 591 } else { | |
| 592 LinkedHashMapCell cell = _newLinkedCell(key, value); | |
| 593 JS('void', '#.push(#)', bucket, cell); | |
| 594 } | |
| 595 } | |
| 596 } | |
| 597 | |
| 598 V putIfAbsent(K key, V ifAbsent()) { | |
| 599 if (containsKey(key)) return this[key]; | |
| 600 V value = ifAbsent(); | |
| 601 this[key] = value; | |
| 602 return value; | |
| 603 } | |
| 604 | |
| 605 V remove(Object key) { | |
| 606 if (_isStringKey(key)) { | |
| 607 return _removeHashTableEntry(_strings, key); | |
| 608 } else if (_isNumericKey(key)) { | |
| 609 return _removeHashTableEntry(_nums, key); | |
| 610 } else { | |
| 611 return _remove(key); | |
| 612 } | |
| 613 } | |
| 614 | |
| 615 V _remove(Object key) { | |
| 616 var rest = _rest; | |
| 617 if (rest == null) return null; | |
| 618 var bucket = _getBucket(rest, key); | |
| 619 int index = _findBucketIndex(bucket, key); | |
| 620 if (index < 0) return null; | |
| 621 // Use splice to remove the [cell] element at the index and | |
| 622 // unlink the cell before returning its value. | |
| 623 LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); | |
| 624 _unlinkCell(cell); | |
| 625 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 626 // the length reaches zero. | |
| 627 return cell._value; | |
| 628 } | |
| 629 | |
| 630 void clear() { | |
| 631 if (_length > 0) { | |
| 632 _strings = _nums = _rest = _first = _last = null; | |
| 633 _length = 0; | |
| 634 _modified(); | |
| 635 } | |
| 636 } | |
| 637 | |
| 638 void forEach(void action(K key, V value)) { | |
| 639 LinkedHashMapCell cell = _first; | |
| 640 int modifications = _modifications; | |
| 641 while (cell != null) { | |
| 642 action(cell._key, cell._value); | |
| 643 if (modifications != _modifications) { | |
| 644 throw new ConcurrentModificationError(this); | |
| 645 } | |
| 646 cell = cell._next; | |
| 647 } | |
| 648 } | |
| 649 | |
| 650 void _addHashTableEntry(var table, K key, V value) { | |
| 651 LinkedHashMapCell cell = _getTableEntry(table, key); | |
| 652 if (cell == null) { | |
| 653 _setTableEntry(table, key, _newLinkedCell(key, value)); | |
| 654 } else { | |
| 655 cell._value = value; | |
| 656 } | |
| 657 } | |
| 658 | |
| 659 V _removeHashTableEntry(var table, Object key) { | |
| 660 if (table == null) return null; | |
| 661 LinkedHashMapCell cell = _getTableEntry(table, key); | |
| 662 if (cell == null) return null; | |
| 663 _unlinkCell(cell); | |
| 664 _deleteTableEntry(table, key); | |
| 665 return cell._value; | |
| 666 } | |
| 667 | |
| 668 void _modified() { | |
| 669 // Value cycles after 2^30 modifications. If you keep hold of an | |
| 670 // iterator for that long, you might miss a modification | |
| 671 // detection, and iteration can go sour. Don't do that. | |
| 672 _modifications = (_modifications + 1) & 0x3ffffff; | |
| 673 } | |
| 674 | |
| 675 // Create a new cell and link it in as the last one in the list. | |
| 676 LinkedHashMapCell _newLinkedCell(K key, V value) { | |
| 677 LinkedHashMapCell cell = new LinkedHashMapCell(key, value); | |
| 678 if (_first == null) { | |
| 679 _first = _last = cell; | |
| 680 } else { | |
| 681 LinkedHashMapCell last = _last; | |
| 682 cell._previous = last; | |
| 683 _last = last._next = cell; | |
| 684 } | |
| 685 _length++; | |
| 686 _modified(); | |
| 687 return cell; | |
| 688 } | |
| 689 | |
| 690 // Unlink the given cell from the linked list of cells. | |
| 691 void _unlinkCell(LinkedHashMapCell cell) { | |
| 692 LinkedHashMapCell previous = cell._previous; | |
| 693 LinkedHashMapCell next = cell._next; | |
| 694 if (previous == null) { | |
| 695 assert(cell == _first); | |
| 696 _first = next; | |
| 697 } else { | |
| 698 previous._next = next; | |
| 699 } | |
| 700 if (next == null) { | |
| 701 assert(cell == _last); | |
| 702 _last = previous; | |
| 703 } else { | |
| 704 next._previous = previous; | |
| 705 } | |
| 706 _length--; | |
| 707 _modified(); | |
| 708 } | |
| 709 | |
| 710 static bool _isStringKey(var key) { | |
| 711 return key is String && key != '__proto__'; | |
| 712 } | |
| 713 | |
| 714 static bool _isNumericKey(var key) { | |
| 715 // Only treat unsigned 30-bit integers as numeric keys. This way, | |
| 716 // we avoid converting them to strings when we use them as keys in | |
| 717 // the JavaScript hash table object. | |
| 718 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); | |
| 719 } | |
| 720 | |
| 721 int _computeHashCode(var key) { | |
| 722 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 723 // issues with problematic keys like '__proto__'. Another option | |
| 724 // would be to throw an exception if the hash code isn't a number. | |
| 725 return JS('int', '# & 0x3ffffff', key.hashCode); | |
| 726 } | |
| 727 | |
| 728 static _getTableEntry(var table, var key) { | |
| 729 return JS('var', '#[#]', table, key); | |
| 730 } | |
| 731 | |
| 732 static void _setTableEntry(var table, var key, var value) { | |
| 733 assert(value != null); | |
| 734 JS('void', '#[#] = #', table, key, value); | |
| 735 } | |
| 736 | |
| 737 static void _deleteTableEntry(var table, var key) { | |
| 738 JS('void', 'delete #[#]', table, key); | |
| 739 } | |
| 740 | |
| 741 List _getBucket(var table, var key) { | |
| 742 var hash = _computeHashCode(key); | |
| 743 return JS('var', '#[#]', table, hash); | |
| 744 } | |
| 745 | |
| 746 int _findBucketIndex(var bucket, var key) { | |
| 747 if (bucket == null) return -1; | |
| 748 int length = JS('int', '#.length', bucket); | |
| 749 for (int i = 0; i < length; i++) { | |
| 750 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); | |
| 751 if (cell._key == key) return i; | |
| 752 } | |
| 753 return -1; | |
| 754 } | |
| 755 | |
| 756 static _newHashTable() { | |
| 757 // Create a new JavaScript object to be used as a hash table. Use | |
| 758 // Object.create to avoid the properties on Object.prototype | |
| 759 // showing up as entries. | |
| 760 var table = JS('var', 'Object.create(null)'); | |
| 761 // Attempt to force the hash table into 'dictionary' mode by | |
| 762 // adding a property to it and deleting it again. | |
| 763 var temporaryKey = '<non-identifier-key>'; | |
| 764 _setTableEntry(table, temporaryKey, table); | |
| 765 _deleteTableEntry(table, temporaryKey); | |
| 766 return table; | |
| 767 } | |
| 768 | |
| 769 String toString() => Maps.mapToString(this); | |
| 770 } | |
| 771 class _LinkedIdentityHashMap<K, V> extends _LinkedHashMap<K, V> { | |
| 772 int _computeHashCode(var key) { | |
| 773 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 774 // issues with problematic keys like '__proto__'. Another option | |
| 775 // would be to throw an exception if the hash code isn't a number. | |
| 776 return JS('int', '# & 0x3ffffff', identityHashCode(key)); | |
| 777 } | |
| 778 | |
| 779 int _findBucketIndex(var bucket, var key) { | |
| 780 if (bucket == null) return -1; | |
| 781 int length = JS('int', '#.length', bucket); | |
| 782 for (int i = 0; i < length; i++) { | |
| 783 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); | |
| 784 if (identical(cell._key, key)) return i; | |
| 785 } | |
| 786 return -1; | |
| 787 } | |
| 788 } | |
| 789 class _LinkedCustomHashMap<K, V> extends _LinkedHashMap<K, V> { | |
| 790 final _Equality<K> _equals; | |
| 791 final _Hasher<K> _hashCode; | |
| 792 final _Predicate<Object> _validKey; | |
| 793 _LinkedCustomHashMap(this._equals, this._hashCode, | |
| 794 bool validKey(Object potentialKey)) | |
| 795 : _validKey = (validKey != null) ? validKey : ((v) => v is K); | |
| 796 | |
| 797 V operator[](Object key) { | |
| 798 if (!_validKey(key)) return null; | |
| 799 return super._get(key); | |
| 800 } | |
| 801 | |
| 802 void operator[]=(K key, V value) { | |
| 803 super._set(key, value); | |
| 804 } | |
| 805 | |
| 806 bool containsKey(Object key) { | |
| 807 if (!_validKey(key)) return false; | |
| 808 return super._containsKey(key); | |
| 809 } | |
| 810 | |
| 811 V remove(Object key) { | |
| 812 if (!_validKey(key)) return null; | |
| 813 return super._remove(key); | |
| 814 } | |
| 815 | |
| 816 int _computeHashCode(var key) { | |
| 817 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 818 // issues with problematic keys like '__proto__'. Another option | |
| 819 // would be to throw an exception if the hash code isn't a number. | |
| 820 return JS('int', '# & 0x3ffffff', _hashCode(key)); | |
| 821 } | |
| 822 | |
| 823 int _findBucketIndex(var bucket, var key) { | |
| 824 if (bucket == null) return -1; | |
| 825 int length = JS('int', '#.length', bucket); | |
| 826 for (int i = 0; i < length; i++) { | |
| 827 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); | |
| 828 if (_equals(cell._key, key)) return i; | |
| 829 } | |
| 830 return -1; | |
| 831 } | |
| 832 } | |
| 833 class LinkedHashMapCell { | |
| 834 final _key; | |
| 835 var _value; | |
| 836 | |
| 837 LinkedHashMapCell _next; | |
| 838 LinkedHashMapCell _previous; | |
| 839 | |
| 840 LinkedHashMapCell(this._key, this._value); | |
| 841 } | |
| 842 class LinkedHashMapKeyIterable<E> extends IterableBase<E> | |
| 843 implements EfficientLength { | |
| 844 final _map; | |
| 845 LinkedHashMapKeyIterable(this._map); | |
| 846 | |
| 847 int get length => _map._length; | |
| 848 bool get isEmpty => _map._length == 0; | |
| 849 | |
| 850 Iterator<E> get iterator { | |
| 851 return new LinkedHashMapKeyIterator<E>(_map, _map._modifications); | |
| 852 } | |
| 853 | |
| 854 bool contains(Object element) { | |
| 855 return _map.containsKey(element); | |
| 856 } | |
| 857 | |
| 858 void forEach(void f(E element)) { | |
| 859 LinkedHashMapCell cell = _map._first; | |
| 860 int modifications = _map._modifications; | |
| 861 while (cell != null) { | |
| 862 f(cell._key); | |
| 863 if (modifications != _map._modifications) { | |
| 864 throw new ConcurrentModificationError(_map); | |
| 865 } | |
| 866 cell = cell._next; | |
| 867 } | |
| 868 } | |
| 869 } | |
| 870 class LinkedHashMapKeyIterator<E> implements Iterator<E> { | |
| 871 final _map; | |
| 872 final int _modifications; | |
| 873 LinkedHashMapCell _cell; | |
| 874 E _current; | |
| 875 | |
| 876 LinkedHashMapKeyIterator(this._map, this._modifications) { | |
| 877 _cell = _map._first; | |
| 878 } | |
| 879 | |
| 880 E get current => _current; | |
| 881 | |
| 882 bool moveNext() { | |
| 883 if (_modifications != _map._modifications) { | |
| 884 throw new ConcurrentModificationError(_map); | |
| 885 } else if (_cell == null) { | |
| 886 _current = null; | |
| 887 return false; | |
| 888 } else { | |
| 889 _current = _cell._key; | |
| 890 _cell = _cell._next; | |
| 891 return true; | |
| 892 } | |
| 893 } | |
| 894 } | |
| 895 class _HashSet<E> extends _HashSetBase<E> implements HashSet<E> { | |
| 896 int _length = 0; | |
| 897 | |
| 898 // The hash set contents are divided into three parts: one part for | |
| 899 // string elements, one for numeric elements, and one for the | |
| 900 // rest. String and numeric elements map directly to a sentinel | |
| 901 // value, but the rest of the entries are stored in bucket lists of | |
| 902 // the form: | |
| 903 // | |
| 904 // [element-0, element-1, element-2, ...] | |
| 905 // | |
| 906 // where all elements in the same bucket share the same hash code. | |
| 907 var _strings; | |
| 908 var _nums; | |
| 909 var _rest; | |
| 910 | |
| 911 // When iterating over the hash set, it is very convenient to have a | |
| 912 // list of all the elements. We cache that on the instance and clear | |
| 913 // the the cache whenever the set changes. This is also used to | |
| 914 // guard against concurrent modifications. | |
| 915 List _elements; | |
| 916 | |
| 917 _HashSet(); | |
| 918 | |
| 919 Set<E> _newSet() => new _HashSet<E>(); | |
| 920 | |
| 921 // Iterable. | |
| 922 Iterator<E> get iterator { | |
| 923 return new HashSetIterator<E>(this, _computeElements()); | |
| 924 } | |
| 925 | |
| 926 int get length => _length; | |
| 927 bool get isEmpty => _length == 0; | |
| 928 bool get isNotEmpty => !isEmpty; | |
| 929 | |
| 930 bool contains(Object object) { | |
| 931 if (_isStringElement(object)) { | |
| 932 var strings = _strings; | |
| 933 return (strings == null) ? false : _hasTableEntry(strings, object); | |
| 934 } else if (_isNumericElement(object)) { | |
| 935 var nums = _nums; | |
| 936 return (nums == null) ? false : _hasTableEntry(nums, object); | |
| 937 } else { | |
| 938 return _contains(object); | |
| 939 } | |
| 940 } | |
| 941 | |
| 942 bool _contains(Object object) { | |
| 943 var rest = _rest; | |
| 944 if (rest == null) return false; | |
| 945 var bucket = _getBucket(rest, object); | |
| 946 return _findBucketIndex(bucket, object) >= 0; | |
| 947 } | |
| 948 | |
| 949 E lookup(Object object) { | |
| 950 if (_isStringElement(object) || _isNumericElement(object)) { | |
| 951 return this.contains(object) ? object : null; | |
| 952 } | |
| 953 return _lookup(object); | |
| 954 } | |
| 955 | |
| 956 E _lookup(Object object) { | |
| 957 var rest = _rest; | |
| 958 if (rest == null) return null; | |
| 959 var bucket = _getBucket(rest, object); | |
| 960 var index = _findBucketIndex(bucket, object); | |
| 961 if (index < 0) return null; | |
| 962 return bucket[index]; | |
| 963 } | |
| 964 | |
| 965 // Collection. | |
| 966 bool add(E element) { | |
| 967 if (_isStringElement(element)) { | |
| 968 var strings = _strings; | |
| 969 if (strings == null) _strings = strings = _newHashTable(); | |
| 970 return _addHashTableEntry(strings, element); | |
| 971 } else if (_isNumericElement(element)) { | |
| 972 var nums = _nums; | |
| 973 if (nums == null) _nums = nums = _newHashTable(); | |
| 974 return _addHashTableEntry(nums, element); | |
| 975 } else { | |
| 976 return _add(element); | |
| 977 } | |
| 978 } | |
| 979 | |
| 980 bool _add(E element) { | |
| 981 var rest = _rest; | |
| 982 if (rest == null) _rest = rest = _newHashTable(); | |
| 983 var hash = _computeHashCode(element); | |
| 984 var bucket = JS('var', '#[#]', rest, hash); | |
| 985 if (bucket == null) { | |
| 986 _setTableEntry(rest, hash, JS('var', '[#]', element)); | |
| 987 } else { | |
| 988 int index = _findBucketIndex(bucket, element); | |
| 989 if (index >= 0) return false; | |
| 990 JS('void', '#.push(#)', bucket, element); | |
| 991 } | |
| 992 _length++; | |
| 993 _elements = null; | |
| 994 return true; | |
| 995 } | |
| 996 | |
| 997 void addAll(Iterable<E> objects) { | |
| 998 for (E each in objects) { | |
| 999 add(each); | |
| 1000 } | |
| 1001 } | |
| 1002 | |
| 1003 bool remove(Object object) { | |
| 1004 if (_isStringElement(object)) { | |
| 1005 return _removeHashTableEntry(_strings, object); | |
| 1006 } else if (_isNumericElement(object)) { | |
| 1007 return _removeHashTableEntry(_nums, object); | |
| 1008 } else { | |
| 1009 return _remove(object); | |
| 1010 } | |
| 1011 } | |
| 1012 | |
| 1013 bool _remove(Object object) { | |
| 1014 var rest = _rest; | |
| 1015 if (rest == null) return false; | |
| 1016 var bucket = _getBucket(rest, object); | |
| 1017 int index = _findBucketIndex(bucket, object); | |
| 1018 if (index < 0) return false; | |
| 1019 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 1020 // the length reaches zero. | |
| 1021 _length--; | |
| 1022 _elements = null; | |
| 1023 // TODO(kasperl): It would probably be faster to move the | |
| 1024 // element to the end and reduce the length of the bucket list. | |
| 1025 JS('void', '#.splice(#, 1)', bucket, index); | |
| 1026 return true; | |
| 1027 } | |
| 1028 | |
| 1029 void clear() { | |
| 1030 if (_length > 0) { | |
| 1031 _strings = _nums = _rest = _elements = null; | |
| 1032 _length = 0; | |
| 1033 } | |
| 1034 } | |
| 1035 | |
| 1036 List _computeElements() { | |
| 1037 if (_elements != null) return _elements; | |
| 1038 List result = new List(_length); | |
| 1039 int index = 0; | |
| 1040 | |
| 1041 // Add all string elements to the list. | |
| 1042 var strings = _strings; | |
| 1043 if (strings != null) { | |
| 1044 var names = JS('var', 'Object.getOwnPropertyNames(#)', strings); | |
| 1045 int entries = JS('int', '#.length', names); | |
| 1046 for (int i = 0; i < entries; i++) { | |
| 1047 String element = JS('String', '#[#]', names, i); | |
| 1048 JS('void', '#[#] = #', result, index, element); | |
| 1049 index++; | |
| 1050 } | |
| 1051 } | |
| 1052 | |
| 1053 // Add all numeric elements to the list. | |
| 1054 var nums = _nums; | |
| 1055 if (nums != null) { | |
| 1056 var names = JS('var', 'Object.getOwnPropertyNames(#)', nums); | |
| 1057 int entries = JS('int', '#.length', names); | |
| 1058 for (int i = 0; i < entries; i++) { | |
| 1059 // Object.getOwnPropertyNames returns a list of strings, so we | |
| 1060 // have to convert the elements back to numbers (+). | |
| 1061 num element = JS('num', '+#[#]', names, i); | |
| 1062 JS('void', '#[#] = #', result, index, element); | |
| 1063 index++; | |
| 1064 } | |
| 1065 } | |
| 1066 | |
| 1067 // Add all the remaining elements to the list. | |
| 1068 var rest = _rest; | |
| 1069 if (rest != null) { | |
| 1070 var names = JS('var', 'Object.getOwnPropertyNames(#)', rest); | |
| 1071 int entries = JS('int', '#.length', names); | |
| 1072 for (int i = 0; i < entries; i++) { | |
| 1073 var entry = JS('String', '#[#]', names, i); | |
| 1074 var bucket = JS('var', '#[#]', rest, entry); | |
| 1075 int length = JS('int', '#.length', bucket); | |
| 1076 for (int i = 0; i < length; i++) { | |
| 1077 JS('void', '#[#] = #[#]', result, index, bucket, i); | |
| 1078 index++; | |
| 1079 } | |
| 1080 } | |
| 1081 } | |
| 1082 assert(index == _length); | |
| 1083 return _elements = result; | |
| 1084 } | |
| 1085 | |
| 1086 bool _addHashTableEntry(var table, E element) { | |
| 1087 if (_hasTableEntry(table, element)) return false; | |
| 1088 _setTableEntry(table, element, 0); | |
| 1089 _length++; | |
| 1090 _elements = null; | |
| 1091 return true; | |
| 1092 } | |
| 1093 | |
| 1094 bool _removeHashTableEntry(var table, Object element) { | |
| 1095 if (table != null && _hasTableEntry(table, element)) { | |
| 1096 _deleteTableEntry(table, element); | |
| 1097 _length--; | |
| 1098 _elements = null; | |
| 1099 return true; | |
| 1100 } else { | |
| 1101 return false; | |
| 1102 } | |
| 1103 } | |
| 1104 | |
| 1105 static bool _isStringElement(var element) { | |
| 1106 return element is String && element != '__proto__'; | |
| 1107 } | |
| 1108 | |
| 1109 static bool _isNumericElement(var element) { | |
| 1110 // Only treat unsigned 30-bit integers as numeric elements. This | |
| 1111 // way, we avoid converting them to strings when we use them as | |
| 1112 // keys in the JavaScript hash table object. | |
| 1113 return element is num && | |
| 1114 JS('bool', '(# & 0x3ffffff) === #', element, element); | |
| 1115 } | |
| 1116 | |
| 1117 int _computeHashCode(var element) { | |
| 1118 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1119 // issues with problematic elements like '__proto__'. Another | |
| 1120 // option would be to throw an exception if the hash code isn't a | |
| 1121 // number. | |
| 1122 return JS('int', '# & 0x3ffffff', element.hashCode); | |
| 1123 } | |
| 1124 | |
| 1125 static bool _hasTableEntry(var table, var key) { | |
| 1126 var entry = JS('var', '#[#]', table, key); | |
| 1127 // We take care to only store non-null entries in the table, so we | |
| 1128 // can check if the table has an entry for the given key with a | |
| 1129 // simple null check. | |
| 1130 return entry != null; | |
| 1131 } | |
| 1132 | |
| 1133 static void _setTableEntry(var table, var key, var value) { | |
| 1134 assert(value != null); | |
| 1135 JS('void', '#[#] = #', table, key, value); | |
| 1136 } | |
| 1137 | |
| 1138 static void _deleteTableEntry(var table, var key) { | |
| 1139 JS('void', 'delete #[#]', table, key); | |
| 1140 } | |
| 1141 | |
| 1142 List _getBucket(var table, var element) { | |
| 1143 var hash = _computeHashCode(element); | |
| 1144 return JS('var', '#[#]', table, hash); | |
| 1145 } | |
| 1146 | |
| 1147 int _findBucketIndex(var bucket, var element) { | |
| 1148 if (bucket == null) return -1; | |
| 1149 int length = JS('int', '#.length', bucket); | |
| 1150 for (int i = 0; i < length; i++) { | |
| 1151 if (JS('var', '#[#]', bucket, i) == element) return i; | |
| 1152 } | |
| 1153 return -1; | |
| 1154 } | |
| 1155 | |
| 1156 static _newHashTable() { | |
| 1157 // Create a new JavaScript object to be used as a hash table. Use | |
| 1158 // Object.create to avoid the properties on Object.prototype | |
| 1159 // showing up as entries. | |
| 1160 var table = JS('var', 'Object.create(null)'); | |
| 1161 // Attempt to force the hash table into 'dictionary' mode by | |
| 1162 // adding a property to it and deleting it again. | |
| 1163 var temporaryKey = '<non-identifier-key>'; | |
| 1164 _setTableEntry(table, temporaryKey, table); | |
| 1165 _deleteTableEntry(table, temporaryKey); | |
| 1166 return table; | |
| 1167 } | |
| 1168 } | |
| 1169 class _IdentityHashSet<E> extends _HashSet<E> { | |
| 1170 Set<E> _newSet() => new _IdentityHashSet<E>(); | |
| 1171 | |
| 1172 int _computeHashCode(var key) { | |
| 1173 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1174 // issues with problematic keys like '__proto__'. Another option | |
| 1175 // would be to throw an exception if the hash code isn't a number. | |
| 1176 return JS('int', '# & 0x3ffffff', identityHashCode(key)); | |
| 1177 } | |
| 1178 | |
| 1179 int _findBucketIndex(var bucket, var element) { | |
| 1180 if (bucket == null) return -1; | |
| 1181 int length = JS('int', '#.length', bucket); | |
| 1182 for (int i = 0; i < length; i++) { | |
| 1183 if (identical(JS('var', '#[#]', bucket, i), element)) return i; | |
| 1184 } | |
| 1185 return -1; | |
| 1186 } | |
| 1187 } | |
| 1188 class _CustomHashSet<E> extends _HashSet<E> { | |
| 1189 _Equality<E> _equality; | |
| 1190 _Hasher<E> _hasher; | |
| 1191 _Predicate<Object> _validKey; | |
| 1192 _CustomHashSet(this._equality, this._hasher, | |
| 1193 bool validKey(Object potentialKey)) | |
| 1194 : _validKey = (validKey != null) ? validKey : ((x) => x is E); | |
| 1195 | |
| 1196 Set<E> _newSet() => new _CustomHashSet<E>(_equality, _hasher, _validKey); | |
| 1197 | |
| 1198 int _findBucketIndex(var bucket, var element) { | |
| 1199 if (bucket == null) return -1; | |
| 1200 int length = JS('int', '#.length', bucket); | |
| 1201 for (int i = 0; i < length; i++) { | |
| 1202 if (_equality(JS('var', '#[#]', bucket, i), element)) return i; | |
| 1203 } | |
| 1204 return -1; | |
| 1205 } | |
| 1206 | |
| 1207 int _computeHashCode(var element) { | |
| 1208 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1209 // issues with problematic elements like '__proto__'. Another | |
| 1210 // option would be to throw an exception if the hash code isn't a | |
| 1211 // number. | |
| 1212 return JS('int', '# & 0x3ffffff', _hasher(element)); | |
| 1213 } | |
| 1214 | |
| 1215 bool add(E object) => super._add(object); | |
| 1216 | |
| 1217 bool contains(Object object) { | |
| 1218 if (!_validKey(object)) return false; | |
| 1219 return super._contains(object); | |
| 1220 } | |
| 1221 | |
| 1222 E lookup(Object object) { | |
| 1223 if (!_validKey(object)) return null; | |
| 1224 return super._lookup(object); | |
| 1225 } | |
| 1226 | |
| 1227 bool remove(Object object) { | |
| 1228 if (!_validKey(object)) return false; | |
| 1229 return super._remove(object); | |
| 1230 } | |
| 1231 } | |
| 1232 class HashSetIterator<E> implements Iterator<E> { | |
| 1233 final _set; | |
| 1234 final List _elements; | |
| 1235 int _offset = 0; | |
| 1236 E _current; | |
| 1237 | |
| 1238 HashSetIterator(this._set, this._elements); | |
| 1239 | |
| 1240 E get current => _current; | |
| 1241 | |
| 1242 bool moveNext() { | |
| 1243 var elements = _elements; | |
| 1244 int offset = _offset; | |
| 1245 if (JS('bool', '# !== #', elements, _set._elements)) { | |
| 1246 throw new ConcurrentModificationError(_set); | |
| 1247 } else if (offset >= JS('int', '#.length', elements)) { | |
| 1248 _current = null; | |
| 1249 return false; | |
| 1250 } else { | |
| 1251 _current = JS('var', '#[#]', elements, offset); | |
| 1252 // TODO(kasperl): For now, we have to tell the type inferrer to | |
| 1253 // treat the result of doing offset + 1 as an int. Otherwise, we | |
| 1254 // get unnecessary bailout code. | |
| 1255 _offset = JS('int', '#', offset + 1); | |
| 1256 return true; | |
| 1257 } | |
| 1258 } | |
| 1259 } | |
| 1260 class _LinkedHashSet<E> extends _HashSetBase<E> implements LinkedHashSet<E> { | |
| 1261 int _length = 0; | |
| 1262 | |
| 1263 // The hash set contents are divided into three parts: one part for | |
| 1264 // string elements, one for numeric elements, and one for the | |
| 1265 // rest. String and numeric elements map directly to their linked | |
| 1266 // cells, but the rest of the entries are stored in bucket lists of | |
| 1267 // the form: | |
| 1268 // | |
| 1269 // [cell-0, cell-1, ...] | |
| 1270 // | |
| 1271 // where all elements in the same bucket share the same hash code. | |
| 1272 var _strings; | |
| 1273 var _nums; | |
| 1274 var _rest; | |
| 1275 | |
| 1276 // The elements are stored in cells that are linked together | |
| 1277 // to form a double linked list. | |
| 1278 LinkedHashSetCell _first; | |
| 1279 LinkedHashSetCell _last; | |
| 1280 | |
| 1281 // We track the number of modifications done to the element set to | |
| 1282 // be able to throw when the set is modified while being iterated | |
| 1283 // over. | |
| 1284 int _modifications = 0; | |
| 1285 | |
| 1286 _LinkedHashSet(); | |
| 1287 | |
| 1288 Set<E> _newSet() => new _LinkedHashSet<E>(); | |
| 1289 | |
| 1290 void _unsupported(String operation) { | |
| 1291 throw 'LinkedHashSet: unsupported $operation'; | |
| 1292 } | |
| 1293 | |
| 1294 // Iterable. | |
| 1295 Iterator<E> get iterator { | |
| 1296 return new LinkedHashSetIterator(this, _modifications); | |
| 1297 } | |
| 1298 | |
| 1299 int get length => _length; | |
| 1300 bool get isEmpty => _length == 0; | |
| 1301 bool get isNotEmpty => !isEmpty; | |
| 1302 | |
| 1303 bool contains(Object object) { | |
| 1304 if (_isStringElement(object)) { | |
| 1305 var strings = _strings; | |
| 1306 if (strings == null) return false; | |
| 1307 LinkedHashSetCell cell = _getTableEntry(strings, object); | |
| 1308 return cell != null; | |
| 1309 } else if (_isNumericElement(object)) { | |
| 1310 var nums = _nums; | |
| 1311 if (nums == null) return false; | |
| 1312 LinkedHashSetCell cell = _getTableEntry(nums, object); | |
| 1313 return cell != null; | |
| 1314 } else { | |
| 1315 return _contains(object); | |
| 1316 } | |
| 1317 } | |
| 1318 | |
| 1319 bool _contains(Object object) { | |
| 1320 var rest = _rest; | |
| 1321 if (rest == null) return false; | |
| 1322 var bucket = _getBucket(rest, object); | |
| 1323 return _findBucketIndex(bucket, object) >= 0; | |
| 1324 } | |
| 1325 | |
| 1326 E lookup(Object object) { | |
| 1327 if (_isStringElement(object) || _isNumericElement(object)) { | |
| 1328 return this.contains(object) ? object : null; | |
| 1329 } else { | |
| 1330 return _lookup(object); | |
| 1331 } | |
| 1332 } | |
| 1333 | |
| 1334 E _lookup(Object object) { | |
| 1335 var rest = _rest; | |
| 1336 if (rest == null) return null; | |
| 1337 var bucket = _getBucket(rest, object); | |
| 1338 var index = _findBucketIndex(bucket, object); | |
| 1339 if (index < 0) return null; | |
| 1340 return bucket[index]._element; | |
| 1341 } | |
| 1342 | |
| 1343 void forEach(void action(E element)) { | |
| 1344 LinkedHashSetCell cell = _first; | |
| 1345 int modifications = _modifications; | |
| 1346 while (cell != null) { | |
| 1347 action(cell._element); | |
| 1348 if (modifications != _modifications) { | |
| 1349 throw new ConcurrentModificationError(this); | |
| 1350 } | |
| 1351 cell = cell._next; | |
| 1352 } | |
| 1353 } | |
| 1354 | |
| 1355 E get first { | |
| 1356 if (_first == null) throw new StateError("No elements"); | |
| 1357 return _first._element; | |
| 1358 } | |
| 1359 | |
| 1360 E get last { | |
| 1361 if (_last == null) throw new StateError("No elements"); | |
| 1362 return _last._element; | |
| 1363 } | |
| 1364 | |
| 1365 // Collection. | |
| 1366 bool add(E element) { | |
| 1367 if (_isStringElement(element)) { | |
| 1368 var strings = _strings; | |
| 1369 if (strings == null) _strings = strings = _newHashTable(); | |
| 1370 return _addHashTableEntry(strings, element); | |
| 1371 } else if (_isNumericElement(element)) { | |
| 1372 var nums = _nums; | |
| 1373 if (nums == null) _nums = nums = _newHashTable(); | |
| 1374 return _addHashTableEntry(nums, element); | |
| 1375 } else { | |
| 1376 return _add(element); | |
| 1377 } | |
| 1378 } | |
| 1379 | |
| 1380 bool _add(E element) { | |
| 1381 var rest = _rest; | |
| 1382 if (rest == null) _rest = rest = _newHashTable(); | |
| 1383 var hash = _computeHashCode(element); | |
| 1384 var bucket = JS('var', '#[#]', rest, hash); | |
| 1385 if (bucket == null) { | |
| 1386 LinkedHashSetCell cell = _newLinkedCell(element); | |
| 1387 _setTableEntry(rest, hash, JS('var', '[#]', cell)); | |
| 1388 } else { | |
| 1389 int index = _findBucketIndex(bucket, element); | |
| 1390 if (index >= 0) return false; | |
| 1391 LinkedHashSetCell cell = _newLinkedCell(element); | |
| 1392 JS('void', '#.push(#)', bucket, cell); | |
| 1393 } | |
| 1394 return true; | |
| 1395 } | |
| 1396 | |
| 1397 bool remove(Object object) { | |
| 1398 if (_isStringElement(object)) { | |
| 1399 return _removeHashTableEntry(_strings, object); | |
| 1400 } else if (_isNumericElement(object)) { | |
| 1401 return _removeHashTableEntry(_nums, object); | |
| 1402 } else { | |
| 1403 return _remove(object); | |
| 1404 } | |
| 1405 } | |
| 1406 | |
| 1407 bool _remove(Object object) { | |
| 1408 var rest = _rest; | |
| 1409 if (rest == null) return false; | |
| 1410 var bucket = _getBucket(rest, object); | |
| 1411 int index = _findBucketIndex(bucket, object); | |
| 1412 if (index < 0) return false; | |
| 1413 // Use splice to remove the [cell] element at the index and | |
| 1414 // unlink it. | |
| 1415 LinkedHashSetCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); | |
| 1416 _unlinkCell(cell); | |
| 1417 return true; | |
| 1418 } | |
| 1419 | |
| 1420 void removeWhere(bool test(E element)) { | |
| 1421 _filterWhere(test, true); | |
| 1422 } | |
| 1423 | |
| 1424 void retainWhere(bool test(E element)) { | |
| 1425 _filterWhere(test, false); | |
| 1426 } | |
| 1427 | |
| 1428 void _filterWhere(bool test(E element), bool removeMatching) { | |
| 1429 LinkedHashSetCell cell = _first; | |
| 1430 while (cell != null) { | |
| 1431 E element = cell._element; | |
| 1432 LinkedHashSetCell next = cell._next; | |
| 1433 int modifications = _modifications; | |
| 1434 bool shouldRemove = (removeMatching == test(element)); | |
| 1435 if (modifications != _modifications) { | |
| 1436 throw new ConcurrentModificationError(this); | |
| 1437 } | |
| 1438 if (shouldRemove) remove(element); | |
| 1439 cell = next; | |
| 1440 } | |
| 1441 } | |
| 1442 | |
| 1443 void clear() { | |
| 1444 if (_length > 0) { | |
| 1445 _strings = _nums = _rest = _first = _last = null; | |
| 1446 _length = 0; | |
| 1447 _modified(); | |
| 1448 } | |
| 1449 } | |
| 1450 | |
| 1451 bool _addHashTableEntry(var table, E element) { | |
| 1452 LinkedHashSetCell cell = _getTableEntry(table, element); | |
| 1453 if (cell != null) return false; | |
| 1454 _setTableEntry(table, element, _newLinkedCell(element)); | |
| 1455 return true; | |
| 1456 } | |
| 1457 | |
| 1458 bool _removeHashTableEntry(var table, Object element) { | |
| 1459 if (table == null) return false; | |
| 1460 LinkedHashSetCell cell = _getTableEntry(table, element); | |
| 1461 if (cell == null) return false; | |
| 1462 _unlinkCell(cell); | |
| 1463 _deleteTableEntry(table, element); | |
| 1464 return true; | |
| 1465 } | |
| 1466 | |
| 1467 void _modified() { | |
| 1468 // Value cycles after 2^30 modifications. If you keep hold of an | |
| 1469 // iterator for that long, you might miss a modification | |
| 1470 // detection, and iteration can go sour. Don't do that. | |
| 1471 _modifications = (_modifications + 1) & 0x3ffffff; | |
| 1472 } | |
| 1473 | |
| 1474 // Create a new cell and link it in as the last one in the list. | |
| 1475 LinkedHashSetCell _newLinkedCell(E element) { | |
| 1476 LinkedHashSetCell cell = new LinkedHashSetCell(element); | |
| 1477 if (_first == null) { | |
| 1478 _first = _last = cell; | |
| 1479 } else { | |
| 1480 LinkedHashSetCell last = _last; | |
| 1481 cell._previous = last; | |
| 1482 _last = last._next = cell; | |
| 1483 } | |
| 1484 _length++; | |
| 1485 _modified(); | |
| 1486 return cell; | |
| 1487 } | |
| 1488 | |
| 1489 // Unlink the given cell from the linked list of cells. | |
| 1490 void _unlinkCell(LinkedHashSetCell cell) { | |
| 1491 LinkedHashSetCell previous = cell._previous; | |
| 1492 LinkedHashSetCell next = cell._next; | |
| 1493 if (previous == null) { | |
| 1494 assert(cell == _first); | |
| 1495 _first = next; | |
| 1496 } else { | |
| 1497 previous._next = next; | |
| 1498 } | |
| 1499 if (next == null) { | |
| 1500 assert(cell == _last); | |
| 1501 _last = previous; | |
| 1502 } else { | |
| 1503 next._previous = previous; | |
| 1504 } | |
| 1505 _length--; | |
| 1506 _modified(); | |
| 1507 } | |
| 1508 | |
| 1509 static bool _isStringElement(var element) { | |
| 1510 return element is String && element != '__proto__'; | |
| 1511 } | |
| 1512 | |
| 1513 static bool _isNumericElement(var element) { | |
| 1514 // Only treat unsigned 30-bit integers as numeric elements. This | |
| 1515 // way, we avoid converting them to strings when we use them as | |
| 1516 // keys in the JavaScript hash table object. | |
| 1517 return element is num && | |
| 1518 JS('bool', '(# & 0x3ffffff) === #', element, element); | |
| 1519 } | |
| 1520 | |
| 1521 int _computeHashCode(var element) { | |
| 1522 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1523 // issues with problematic elements like '__proto__'. Another | |
| 1524 // option would be to throw an exception if the hash code isn't a | |
| 1525 // number. | |
| 1526 return JS('int', '# & 0x3ffffff', element.hashCode); | |
| 1527 } | |
| 1528 | |
| 1529 static _getTableEntry(var table, var key) { | |
| 1530 return JS('var', '#[#]', table, key); | |
| 1531 } | |
| 1532 | |
| 1533 static void _setTableEntry(var table, var key, var value) { | |
| 1534 assert(value != null); | |
| 1535 JS('void', '#[#] = #', table, key, value); | |
| 1536 } | |
| 1537 | |
| 1538 static void _deleteTableEntry(var table, var key) { | |
| 1539 JS('void', 'delete #[#]', table, key); | |
| 1540 } | |
| 1541 | |
| 1542 List _getBucket(var table, var element) { | |
| 1543 var hash = _computeHashCode(element); | |
| 1544 return JS('var', '#[#]', table, hash); | |
| 1545 } | |
| 1546 | |
| 1547 int _findBucketIndex(var bucket, var element) { | |
| 1548 if (bucket == null) return -1; | |
| 1549 int length = JS('int', '#.length', bucket); | |
| 1550 for (int i = 0; i < length; i++) { | |
| 1551 LinkedHashSetCell cell = JS('var', '#[#]', bucket, i); | |
| 1552 if (cell._element == element) return i; | |
| 1553 } | |
| 1554 return -1; | |
| 1555 } | |
| 1556 | |
| 1557 static _newHashTable() { | |
| 1558 // Create a new JavaScript object to be used as a hash table. Use | |
| 1559 // Object.create to avoid the properties on Object.prototype | |
| 1560 // showing up as entries. | |
| 1561 var table = JS('var', 'Object.create(null)'); | |
| 1562 // Attempt to force the hash table into 'dictionary' mode by | |
| 1563 // adding a property to it and deleting it again. | |
| 1564 var temporaryKey = '<non-identifier-key>'; | |
| 1565 _setTableEntry(table, temporaryKey, table); | |
| 1566 _deleteTableEntry(table, temporaryKey); | |
| 1567 return table; | |
| 1568 } | |
| 1569 } | |
| 1570 class _LinkedIdentityHashSet<E> extends _LinkedHashSet<E> { | |
| 1571 Set<E> _newSet() => new _LinkedIdentityHashSet<E>(); | |
| 1572 | |
| 1573 int _computeHashCode(var key) { | |
| 1574 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1575 // issues with problematic keys like '__proto__'. Another option | |
| 1576 // would be to throw an exception if the hash code isn't a number. | |
| 1577 return JS('int', '# & 0x3ffffff', identityHashCode(key)); | |
| 1578 } | |
| 1579 | |
| 1580 int _findBucketIndex(var bucket, var element) { | |
| 1581 if (bucket == null) return -1; | |
| 1582 int length = JS('int', '#.length', bucket); | |
| 1583 for (int i = 0; i < length; i++) { | |
| 1584 LinkedHashSetCell cell = JS('var', '#[#]', bucket, i); | |
| 1585 if (identical(cell._element, element)) return i; | |
| 1586 } | |
| 1587 return -1; | |
| 1588 } | |
| 1589 } | |
| 1590 class _LinkedCustomHashSet<E> extends _LinkedHashSet<E> { | |
| 1591 _Equality<E> _equality; | |
| 1592 _Hasher<E> _hasher; | |
| 1593 _Predicate<Object> _validKey; | |
| 1594 _LinkedCustomHashSet(this._equality, this._hasher, | |
| 1595 bool validKey(Object potentialKey)) | |
| 1596 : _validKey = (validKey != null) ? validKey : ((x) => x is E); | |
| 1597 | |
| 1598 Set<E> _newSet() => | |
| 1599 new _LinkedCustomHashSet<E>(_equality, _hasher, _validKey); | |
| 1600 | |
| 1601 int _findBucketIndex(var bucket, var element) { | |
| 1602 if (bucket == null) return -1; | |
| 1603 int length = JS('int', '#.length', bucket); | |
| 1604 for (int i = 0; i < length; i++) { | |
| 1605 LinkedHashSetCell cell = JS('var', '#[#]', bucket, i); | |
| 1606 if (_equality(cell._element, element)) return i; | |
| 1607 } | |
| 1608 return -1; | |
| 1609 } | |
| 1610 | |
| 1611 int _computeHashCode(var element) { | |
| 1612 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1613 // issues with problematic elements like '__proto__'. Another | |
| 1614 // option would be to throw an exception if the hash code isn't a | |
| 1615 // number. | |
| 1616 return JS('int', '# & 0x3ffffff', _hasher(element)); | |
| 1617 } | |
| 1618 | |
| 1619 bool add(E element) => super._add(element); | |
| 1620 | |
| 1621 bool contains(Object object) { | |
| 1622 if (!_validKey(object)) return false; | |
| 1623 return super._contains(object); | |
| 1624 } | |
| 1625 | |
| 1626 E lookup(Object object) { | |
| 1627 if (!_validKey(object)) return null; | |
| 1628 return super._lookup(object); | |
| 1629 } | |
| 1630 | |
| 1631 bool remove(Object object) { | |
| 1632 if (!_validKey(object)) return false; | |
| 1633 return super._remove(object); | |
| 1634 } | |
| 1635 | |
| 1636 bool containsAll(Iterable<Object> elements) { | |
| 1637 for (Object element in elements) { | |
| 1638 if (!_validKey(element) || !this.contains(element)) return false; | |
| 1639 } | |
| 1640 return true; | |
| 1641 } | |
| 1642 | |
| 1643 void removeAll(Iterable<Object> elements) { | |
| 1644 for (Object element in elements) { | |
| 1645 if (_validKey(element)) { | |
| 1646 super._remove(element); | |
| 1647 } | |
| 1648 } | |
| 1649 } | |
| 1650 } | |
| 1651 class LinkedHashSetCell { | |
| 1652 final _element; | |
| 1653 | |
| 1654 LinkedHashSetCell _next; | |
| 1655 LinkedHashSetCell _previous; | |
| 1656 | |
| 1657 LinkedHashSetCell(this._element); | |
| 1658 } | |
| 1659 class LinkedHashSetIterator<E> implements Iterator<E> { | |
| 1660 final _set; | |
| 1661 final int _modifications; | |
| 1662 LinkedHashSetCell _cell; | |
| 1663 E _current; | |
| 1664 | |
| 1665 LinkedHashSetIterator(this._set, this._modifications) { | |
| 1666 _cell = _set._first; | |
| 1667 } | |
| 1668 | |
| 1669 E get current => _current; | |
| 1670 | |
| 1671 bool moveNext() { | |
| 1672 if (_modifications != _set._modifications) { | |
| 1673 throw new ConcurrentModificationError(_set); | |
| 1674 } else if (_cell == null) { | |
| 1675 _current = null; | |
| 1676 return false; | |
| 1677 } else { | |
| 1678 _current = _cell._element; | |
| 1679 _cell = _cell._next; | |
| 1680 return true; | |
| 1681 } | |
| 1682 } | |
| 1683 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1162723007:
remove generated_sdk from checked in code (Closed)
Base URL: git@github.com:dart-lang/dev_compiler.git@master