| 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 // Patch file for dart:collection classes. | |
| 6 import 'dart:_foreign_helper' show JS; | |
| 7 | |
| 8 patch class HashMap<K, V> { | |
| 9 int _length = 0; | |
| 10 | |
| 11 // The hash map contents are divided into three parts: one part for | |
| 12 // string keys, one for numeric keys, and one for the rest. String | |
| 13 // and numeric keys map directly to their values, but the rest of | |
| 14 // the entries are stored in bucket lists of the form: | |
| 15 // | |
| 16 // [key-0, value-0, key-1, value-1, ...] | |
| 17 // | |
| 18 // where all keys in the same bucket share the same hash code. | |
| 19 var _strings; | |
| 20 var _nums; | |
| 21 var _rest; | |
| 22 | |
| 23 // When iterating over the hash map, it is very convenient to have a | |
| 24 // list of all the keys. We cache that on the instance and clear the | |
| 25 // the cache whenever the key set changes. This is also used to | |
| 26 // guard against concurrent modifications. | |
| 27 List _keys; | |
| 28 | |
| 29 patch HashMap(); | |
| 30 | |
| 31 patch int get length => _length; | |
| 32 patch bool get isEmpty => _length == 0; | |
| 33 patch bool get isNotEmpty => !isEmpty; | |
| 34 | |
| 35 patch Iterable<K> get keys { | |
| 36 return new HashMapKeyIterable<K>(this); | |
| 37 } | |
| 38 | |
| 39 patch Iterable<V> get values { | |
| 40 return keys.map((each) => this[each]); | |
| 41 } | |
| 42 | |
| 43 patch bool containsKey(K key) { | |
| 44 if (_isStringKey(key)) { | |
| 45 var strings = _strings; | |
| 46 return (strings == null) ? false : _hasTableEntry(strings, key); | |
| 47 } else if (_isNumericKey(key)) { | |
| 48 var nums = _nums; | |
| 49 return (nums == null) ? false : _hasTableEntry(nums, key); | |
| 50 } else { | |
| 51 var rest = _rest; | |
| 52 if (rest == null) return false; | |
| 53 var bucket = _getBucket(rest, key); | |
| 54 return _findBucketIndex(bucket, key) >= 0; | |
| 55 } | |
| 56 } | |
| 57 | |
| 58 patch bool containsValue(V value) { | |
| 59 return _computeKeys().any((each) => this[each] == value); | |
| 60 } | |
| 61 | |
| 62 patch void addAll(Map<K, V> other) { | |
| 63 other.forEach((K key, V value) { | |
| 64 this[key] = value; | |
| 65 }); | |
| 66 } | |
| 67 | |
| 68 patch V operator[](K key) { | |
| 69 if (_isStringKey(key)) { | |
| 70 var strings = _strings; | |
| 71 return (strings == null) ? null : _getTableEntry(strings, key); | |
| 72 } else if (_isNumericKey(key)) { | |
| 73 var nums = _nums; | |
| 74 return (nums == null) ? null : _getTableEntry(nums, key); | |
| 75 } else { | |
| 76 var rest = _rest; | |
| 77 if (rest == null) return null; | |
| 78 var bucket = _getBucket(rest, key); | |
| 79 int index = _findBucketIndex(bucket, key); | |
| 80 return (index < 0) ? null : JS('var', '#[#]', bucket, index + 1); | |
| 81 } | |
| 82 } | |
| 83 | |
| 84 patch void operator[]=(K key, V value) { | |
| 85 if (_isStringKey(key)) { | |
| 86 var strings = _strings; | |
| 87 if (strings == null) _strings = strings = _newHashTable(); | |
| 88 _addHashTableEntry(strings, key, value); | |
| 89 } else if (_isNumericKey(key)) { | |
| 90 var nums = _nums; | |
| 91 if (nums == null) _nums = nums = _newHashTable(); | |
| 92 _addHashTableEntry(nums, key, value); | |
| 93 } else { | |
| 94 var rest = _rest; | |
| 95 if (rest == null) _rest = rest = _newHashTable(); | |
| 96 var hash = _computeHashCode(key); | |
| 97 var bucket = JS('var', '#[#]', rest, hash); | |
| 98 if (bucket == null) { | |
| 99 _setTableEntry(rest, hash, JS('var', '[#, #]', key, value)); | |
| 100 _length++; | |
| 101 _keys = null; | |
| 102 } else { | |
| 103 int index = _findBucketIndex(bucket, key); | |
| 104 if (index >= 0) { | |
| 105 JS('void', '#[#] = #', bucket, index + 1, value); | |
| 106 } else { | |
| 107 JS('void', '#.push(#, #)', bucket, key, value); | |
| 108 _length++; | |
| 109 _keys = null; | |
| 110 } | |
| 111 } | |
| 112 } | |
| 113 } | |
| 114 | |
| 115 patch V putIfAbsent(K key, V ifAbsent()) { | |
| 116 if (containsKey(key)) return this[key]; | |
| 117 V value = ifAbsent(); | |
| 118 this[key] = value; | |
| 119 return value; | |
| 120 } | |
| 121 | |
| 122 patch V remove(K key) { | |
| 123 if (_isStringKey(key)) { | |
| 124 return _removeHashTableEntry(_strings, key); | |
| 125 } else if (_isNumericKey(key)) { | |
| 126 return _removeHashTableEntry(_nums, key); | |
| 127 } else { | |
| 128 var rest = _rest; | |
| 129 if (rest == null) return null; | |
| 130 var bucket = _getBucket(rest, key); | |
| 131 int index = _findBucketIndex(bucket, key); | |
| 132 if (index < 0) return null; | |
| 133 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 134 // the length reaches zero. | |
| 135 _length--; | |
| 136 _keys = null; | |
| 137 // Use splice to remove the two [key, value] elements at the | |
| 138 // index and return the value. | |
| 139 return JS('var', '#.splice(#, 2)[1]', bucket, index); | |
| 140 } | |
| 141 } | |
| 142 | |
| 143 patch void clear() { | |
| 144 if (_length > 0) { | |
| 145 _strings = _nums = _rest = _keys = null; | |
| 146 _length = 0; | |
| 147 } | |
| 148 } | |
| 149 | |
| 150 patch void forEach(void action(K key, V value)) { | |
| 151 List keys = _computeKeys(); | |
| 152 for (int i = 0, length = keys.length; i < length; i++) { | |
| 153 var key = JS('var', '#[#]', keys, i); | |
| 154 action(key, this[key]); | |
| 155 if (JS('bool', '# !== #', keys, _keys)) { | |
| 156 throw new ConcurrentModificationError(this); | |
| 157 } | |
| 158 } | |
| 159 } | |
| 160 | |
| 161 List _computeKeys() { | |
| 162 if (_keys != null) return _keys; | |
| 163 List result = new List(_length); | |
| 164 int index = 0; | |
| 165 | |
| 166 // Add all string keys to the list. | |
| 167 var strings = _strings; | |
| 168 if (strings != null) { | |
| 169 var names = JS('var', 'Object.getOwnPropertyNames(#)', strings); | |
| 170 int entries = JS('int', '#.length', names); | |
| 171 for (int i = 0; i < entries; i++) { | |
| 172 String key = JS('String', '#[#]', names, i); | |
| 173 JS('void', '#[#] = #', result, index, key); | |
| 174 index++; | |
| 175 } | |
| 176 } | |
| 177 | |
| 178 // Add all numeric keys to the list. | |
| 179 var nums = _nums; | |
| 180 if (nums != null) { | |
| 181 var names = JS('var', 'Object.getOwnPropertyNames(#)', nums); | |
| 182 int entries = JS('int', '#.length', names); | |
| 183 for (int i = 0; i < entries; i++) { | |
| 184 // Object.getOwnPropertyNames returns a list of strings, so we | |
| 185 // have to convert the keys back to numbers (+). | |
| 186 num key = JS('num', '+#[#]', names, i); | |
| 187 JS('void', '#[#] = #', result, index, key); | |
| 188 index++; | |
| 189 } | |
| 190 } | |
| 191 | |
| 192 // Add all the remaining keys to the list. | |
| 193 var rest = _rest; | |
| 194 if (rest != null) { | |
| 195 var names = JS('var', 'Object.getOwnPropertyNames(#)', rest); | |
| 196 int entries = JS('int', '#.length', names); | |
| 197 for (int i = 0; i < entries; i++) { | |
| 198 var key = JS('String', '#[#]', names, i); | |
| 199 var bucket = JS('var', '#[#]', rest, key); | |
| 200 int length = JS('int', '#.length', bucket); | |
| 201 for (int i = 0; i < length; i += 2) { | |
| 202 var key = JS('var', '#[#]', bucket, i); | |
| 203 JS('void', '#[#] = #', result, index, key); | |
| 204 index++; | |
| 205 } | |
| 206 } | |
| 207 } | |
| 208 assert(index == _length); | |
| 209 return _keys = result; | |
| 210 } | |
| 211 | |
| 212 void _addHashTableEntry(var table, K key, V value) { | |
| 213 if (!_hasTableEntry(table, key)) { | |
| 214 _length++; | |
| 215 _keys = null; | |
| 216 } | |
| 217 _setTableEntry(table, key, value); | |
| 218 } | |
| 219 | |
| 220 V _removeHashTableEntry(var table, K key) { | |
| 221 if (table != null && _hasTableEntry(table, key)) { | |
| 222 V value = _getTableEntry(table, key); | |
| 223 _deleteTableEntry(table, key); | |
| 224 _length--; | |
| 225 _keys = null; | |
| 226 return value; | |
| 227 } else { | |
| 228 return null; | |
| 229 } | |
| 230 } | |
| 231 | |
| 232 static bool _isStringKey(var key) { | |
| 233 return key is String && key != '__proto__'; | |
| 234 } | |
| 235 | |
| 236 static bool _isNumericKey(var key) { | |
| 237 // Only treat unsigned 30-bit integers as numeric keys. This way, | |
| 238 // we avoid converting them to strings when we use them as keys in | |
| 239 // the JavaScript hash table object. | |
| 240 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); | |
| 241 } | |
| 242 | |
| 243 static int _computeHashCode(var key) { | |
| 244 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 245 // issues with problematic keys like '__proto__'. Another option | |
| 246 // would be to throw an exception if the hash code isn't a number. | |
| 247 return JS('int', '# & 0x3ffffff', key.hashCode); | |
| 248 } | |
| 249 | |
| 250 static bool _hasTableEntry(var table, var key) { | |
| 251 var entry = JS('var', '#[#]', table, key); | |
| 252 // We take care to only store non-null entries in the table, so we | |
| 253 // can check if the table has an entry for the given key with a | |
| 254 // simple null check. | |
| 255 return entry != null; | |
| 256 } | |
| 257 | |
| 258 static _getTableEntry(var table, var key) { | |
| 259 var entry = JS('var', '#[#]', table, key); | |
| 260 // We store the table itself as the entry to signal that it really | |
| 261 // is a null value, so we have to map back to null here. | |
| 262 return JS('bool', '# === #', entry, table) ? null : entry; | |
| 263 } | |
| 264 | |
| 265 static void _setTableEntry(var table, var key, var value) { | |
| 266 // We only store non-null entries in the table, so we have to | |
| 267 // change null values to refer to the table itself. Such values | |
| 268 // will be recognized and mapped back to null on access. | |
| 269 if (value == null) { | |
| 270 // Do not update [value] with [table], otherwise our | |
| 271 // optimizations could be confused by this opaque object being | |
| 272 // now used for more things than storing and fetching from it. | |
| 273 JS('void', '#[#] = #', table, key, table); | |
| 274 } else { | |
| 275 JS('void', '#[#] = #', table, key, value); | |
| 276 } | |
| 277 } | |
| 278 | |
| 279 static void _deleteTableEntry(var table, var key) { | |
| 280 JS('void', 'delete #[#]', table, key); | |
| 281 } | |
| 282 | |
| 283 static List _getBucket(var table, var key) { | |
| 284 var hash = _computeHashCode(key); | |
| 285 return JS('var', '#[#]', table, hash); | |
| 286 } | |
| 287 | |
| 288 static int _findBucketIndex(var bucket, var key) { | |
| 289 if (bucket == null) return -1; | |
| 290 int length = JS('int', '#.length', bucket); | |
| 291 for (int i = 0; i < length; i += 2) { | |
| 292 if (JS('var', '#[#]', bucket, i) == key) return i; | |
| 293 } | |
| 294 return -1; | |
| 295 } | |
| 296 | |
| 297 static _newHashTable() { | |
| 298 // Create a new JavaScript object to be used as a hash table. Use | |
| 299 // Object.create to avoid the properties on Object.prototype | |
| 300 // showing up as entries. | |
| 301 var table = JS('var', 'Object.create(null)'); | |
| 302 // Attempt to force the hash table into 'dictionary' mode by | |
| 303 // adding a property to it and deleting it again. | |
| 304 var temporaryKey = '<non-identifier-key>'; | |
| 305 _setTableEntry(table, temporaryKey, table); | |
| 306 _deleteTableEntry(table, temporaryKey); | |
| 307 return table; | |
| 308 } | |
| 309 } | |
| 310 | |
| 311 class HashMapKeyIterable<E> extends IterableBase<E> { | |
| 312 final _map; | |
| 313 HashMapKeyIterable(this._map); | |
| 314 | |
| 315 int get length => _map._length; | |
| 316 bool get isEmpty => _map._length == 0; | |
| 317 | |
| 318 Iterator<E> get iterator { | |
| 319 return new HashMapKeyIterator<E>(_map, _map._computeKeys()); | |
| 320 } | |
| 321 | |
| 322 bool contains(E element) { | |
| 323 return _map.containsKey(element); | |
| 324 } | |
| 325 | |
| 326 void forEach(void f(E element)) { | |
| 327 List keys = _map._computeKeys(); | |
| 328 for (int i = 0, length = JS('int', '#.length', keys); i < length; i++) { | |
| 329 f(JS('var', '#[#]', keys, i)); | |
| 330 if (JS('bool', '# !== #', keys, _map._keys)) { | |
| 331 throw new ConcurrentModificationError(_map); | |
| 332 } | |
| 333 } | |
| 334 } | |
| 335 } | |
| 336 | |
| 337 class HashMapKeyIterator<E> implements Iterator<E> { | |
| 338 final _map; | |
| 339 final List _keys; | |
| 340 int _offset = 0; | |
| 341 E _current; | |
| 342 | |
| 343 HashMapKeyIterator(this._map, this._keys); | |
| 344 | |
| 345 E get current => _current; | |
| 346 | |
| 347 bool moveNext() { | |
| 348 var keys = _keys; | |
| 349 int offset = _offset; | |
| 350 if (JS('bool', '# !== #', keys, _map._keys)) { | |
| 351 throw new ConcurrentModificationError(_map); | |
| 352 } else if (offset >= JS('int', '#.length', keys)) { | |
| 353 _current = null; | |
| 354 return false; | |
| 355 } else { | |
| 356 _current = JS('var', '#[#]', keys, offset); | |
| 357 // TODO(kasperl): For now, we have to tell the type inferrer to | |
| 358 // treat the result of doing offset + 1 as an int. Otherwise, we | |
| 359 // get unnecessary bailout code. | |
| 360 _offset = JS('int', '#', offset + 1); | |
| 361 return true; | |
| 362 } | |
| 363 } | |
| 364 } | |
| 365 | |
| 366 patch class LinkedHashMap<K, V> { | |
| 367 int _length = 0; | |
| 368 | |
| 369 // The hash map contents are divided into three parts: one part for | |
| 370 // string keys, one for numeric keys, and one for the rest. String | |
| 371 // and numeric keys map directly to their linked cells, but the rest | |
| 372 // of the entries are stored in bucket lists of the form: | |
| 373 // | |
| 374 // [cell-0, cell-1, ...] | |
| 375 // | |
| 376 // where all keys in the same bucket share the same hash code. | |
| 377 var _strings; | |
| 378 var _nums; | |
| 379 var _rest; | |
| 380 | |
| 381 // The keys and values are stored in cells that are linked together | |
| 382 // to form a double linked list. | |
| 383 LinkedHashMapCell _first; | |
| 384 LinkedHashMapCell _last; | |
| 385 | |
| 386 // We track the number of modifications done to the key set of the | |
| 387 // hash map to be able to throw when the map is modified while being | |
| 388 // iterated over. | |
| 389 int _modifications = 0; | |
| 390 | |
| 391 patch LinkedHashMap(); | |
| 392 | |
| 393 patch int get length => _length; | |
| 394 patch bool get isEmpty => _length == 0; | |
| 395 patch bool get isNotEmpty => !isEmpty; | |
| 396 | |
| 397 | |
| 398 patch Iterable<K> get keys { | |
| 399 return new LinkedHashMapKeyIterable<K>(this); | |
| 400 } | |
| 401 | |
| 402 patch Iterable<V> get values { | |
| 403 return keys.map((each) => this[each]); | |
| 404 } | |
| 405 | |
| 406 patch bool containsKey(K key) { | |
| 407 if (_isStringKey(key)) { | |
| 408 var strings = _strings; | |
| 409 if (strings == null) return false; | |
| 410 LinkedHashMapCell cell = _getTableEntry(strings, key); | |
| 411 return cell != null; | |
| 412 } else if (_isNumericKey(key)) { | |
| 413 var nums = _nums; | |
| 414 if (nums == null) return false; | |
| 415 LinkedHashMapCell cell = _getTableEntry(nums, key); | |
| 416 return cell != null; | |
| 417 } else { | |
| 418 var rest = _rest; | |
| 419 if (rest == null) return false; | |
| 420 var bucket = _getBucket(rest, key); | |
| 421 return _findBucketIndex(bucket, key) >= 0; | |
| 422 } | |
| 423 } | |
| 424 | |
| 425 patch bool containsValue(V value) { | |
| 426 return keys.any((each) => this[each] == value); | |
| 427 } | |
| 428 | |
| 429 patch void addAll(Map<K, V> other) { | |
| 430 other.forEach((K key, V value) { | |
| 431 this[key] = value; | |
| 432 }); | |
| 433 } | |
| 434 | |
| 435 patch V operator[](K key) { | |
| 436 if (_isStringKey(key)) { | |
| 437 var strings = _strings; | |
| 438 if (strings == null) return null; | |
| 439 LinkedHashMapCell cell = _getTableEntry(strings, key); | |
| 440 return (cell == null) ? null : cell._value; | |
| 441 } else if (_isNumericKey(key)) { | |
| 442 var nums = _nums; | |
| 443 if (nums == null) return null; | |
| 444 LinkedHashMapCell cell = _getTableEntry(nums, key); | |
| 445 return (cell == null) ? null : cell._value; | |
| 446 } else { | |
| 447 var rest = _rest; | |
| 448 if (rest == null) return null; | |
| 449 var bucket = _getBucket(rest, key); | |
| 450 int index = _findBucketIndex(bucket, key); | |
| 451 if (index < 0) return null; | |
| 452 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | |
| 453 return cell._value; | |
| 454 } | |
| 455 } | |
| 456 | |
| 457 patch void operator[]=(K key, V value) { | |
| 458 if (_isStringKey(key)) { | |
| 459 var strings = _strings; | |
| 460 if (strings == null) _strings = strings = _newHashTable(); | |
| 461 _addHashTableEntry(strings, key, value); | |
| 462 } else if (_isNumericKey(key)) { | |
| 463 var nums = _nums; | |
| 464 if (nums == null) _nums = nums = _newHashTable(); | |
| 465 _addHashTableEntry(nums, key, value); | |
| 466 } else { | |
| 467 var rest = _rest; | |
| 468 if (rest == null) _rest = rest = _newHashTable(); | |
| 469 var hash = _computeHashCode(key); | |
| 470 var bucket = JS('var', '#[#]', rest, hash); | |
| 471 if (bucket == null) { | |
| 472 LinkedHashMapCell cell = _newLinkedCell(key, value); | |
| 473 _setTableEntry(rest, hash, JS('var', '[#]', cell)); | |
| 474 } else { | |
| 475 int index = _findBucketIndex(bucket, key); | |
| 476 if (index >= 0) { | |
| 477 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | |
| 478 cell._value = value; | |
| 479 } else { | |
| 480 LinkedHashMapCell cell = _newLinkedCell(key, value); | |
| 481 JS('void', '#.push(#)', bucket, cell); | |
| 482 } | |
| 483 } | |
| 484 } | |
| 485 } | |
| 486 | |
| 487 patch V putIfAbsent(K key, V ifAbsent()) { | |
| 488 if (containsKey(key)) return this[key]; | |
| 489 V value = ifAbsent(); | |
| 490 this[key] = value; | |
| 491 return value; | |
| 492 } | |
| 493 | |
| 494 patch V remove(K key) { | |
| 495 if (_isStringKey(key)) { | |
| 496 return _removeHashTableEntry(_strings, key); | |
| 497 } else if (_isNumericKey(key)) { | |
| 498 return _removeHashTableEntry(_nums, key); | |
| 499 } else { | |
| 500 var rest = _rest; | |
| 501 if (rest == null) return null; | |
| 502 var bucket = _getBucket(rest, key); | |
| 503 int index = _findBucketIndex(bucket, key); | |
| 504 if (index < 0) return null; | |
| 505 // Use splice to remove the [cell] element at the index and | |
| 506 // unlink the cell before returning its value. | |
| 507 LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); | |
| 508 _unlinkCell(cell); | |
| 509 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 510 // the length reaches zero. | |
| 511 return cell._value; | |
| 512 } | |
| 513 } | |
| 514 | |
| 515 patch void clear() { | |
| 516 if (_length > 0) { | |
| 517 _strings = _nums = _rest = _first = _last = null; | |
| 518 _length = 0; | |
| 519 _modified(); | |
| 520 } | |
| 521 } | |
| 522 | |
| 523 patch void forEach(void action(K key, V value)) { | |
| 524 LinkedHashMapCell cell = _first; | |
| 525 int modifications = _modifications; | |
| 526 while (cell != null) { | |
| 527 action(cell._key, cell._value); | |
| 528 if (modifications != _modifications) { | |
| 529 throw new ConcurrentModificationError(this); | |
| 530 } | |
| 531 cell = cell._next; | |
| 532 } | |
| 533 } | |
| 534 | |
| 535 void _addHashTableEntry(var table, K key, V value) { | |
| 536 LinkedHashMapCell cell = _getTableEntry(table, key); | |
| 537 if (cell == null) { | |
| 538 _setTableEntry(table, key, _newLinkedCell(key, value)); | |
| 539 } else { | |
| 540 cell._value = value; | |
| 541 } | |
| 542 } | |
| 543 | |
| 544 V _removeHashTableEntry(var table, K key) { | |
| 545 if (table == null) return null; | |
| 546 LinkedHashMapCell cell = _getTableEntry(table, key); | |
| 547 if (cell == null) return null; | |
| 548 _unlinkCell(cell); | |
| 549 _deleteTableEntry(table, key); | |
| 550 return cell._value; | |
| 551 } | |
| 552 | |
| 553 void _modified() { | |
| 554 // Value cycles after 2^30 modifications. If you keep hold of an | |
| 555 // iterator for that long, you might miss a modification | |
| 556 // detection, and iteration can go sour. Don't do that. | |
| 557 _modifications = (_modifications + 1) & 0x3ffffff; | |
| 558 } | |
| 559 | |
| 560 // Create a new cell and link it in as the last one in the list. | |
| 561 LinkedHashMapCell _newLinkedCell(K key, V value) { | |
| 562 LinkedHashMapCell cell = new LinkedHashMapCell(key, value); | |
| 563 if (_first == null) { | |
| 564 _first = _last = cell; | |
| 565 } else { | |
| 566 LinkedHashMapCell last = _last; | |
| 567 cell._previous = last; | |
| 568 _last = last._next = cell; | |
| 569 } | |
| 570 _length++; | |
| 571 _modified(); | |
| 572 return cell; | |
| 573 } | |
| 574 | |
| 575 // Unlink the given cell from the linked list of cells. | |
| 576 void _unlinkCell(LinkedHashMapCell cell) { | |
| 577 LinkedHashMapCell previous = cell._previous; | |
| 578 LinkedHashMapCell next = cell._next; | |
| 579 if (previous == null) { | |
| 580 assert(cell == _first); | |
| 581 _first = next; | |
| 582 } else { | |
| 583 previous._next = next; | |
| 584 } | |
| 585 if (next == null) { | |
| 586 assert(cell == _last); | |
| 587 _last = previous; | |
| 588 } else { | |
| 589 next._previous = previous; | |
| 590 } | |
| 591 _length--; | |
| 592 _modified(); | |
| 593 } | |
| 594 | |
| 595 static bool _isStringKey(var key) { | |
| 596 return key is String && key != '__proto__'; | |
| 597 } | |
| 598 | |
| 599 static bool _isNumericKey(var key) { | |
| 600 // Only treat unsigned 30-bit integers as numeric keys. This way, | |
| 601 // we avoid converting them to strings when we use them as keys in | |
| 602 // the JavaScript hash table object. | |
| 603 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); | |
| 604 } | |
| 605 | |
| 606 static int _computeHashCode(var key) { | |
| 607 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 608 // issues with problematic keys like '__proto__'. Another option | |
| 609 // would be to throw an exception if the hash code isn't a number. | |
| 610 return JS('int', '# & 0x3ffffff', key.hashCode); | |
| 611 } | |
| 612 | |
| 613 static _getTableEntry(var table, var key) { | |
| 614 return JS('var', '#[#]', table, key); | |
| 615 } | |
| 616 | |
| 617 static void _setTableEntry(var table, var key, var value) { | |
| 618 assert(value != null); | |
| 619 JS('void', '#[#] = #', table, key, value); | |
| 620 } | |
| 621 | |
| 622 static void _deleteTableEntry(var table, var key) { | |
| 623 JS('void', 'delete #[#]', table, key); | |
| 624 } | |
| 625 | |
| 626 static List _getBucket(var table, var key) { | |
| 627 var hash = _computeHashCode(key); | |
| 628 return JS('var', '#[#]', table, hash); | |
| 629 } | |
| 630 | |
| 631 static int _findBucketIndex(var bucket, var key) { | |
| 632 if (bucket == null) return -1; | |
| 633 int length = JS('int', '#.length', bucket); | |
| 634 for (int i = 0; i < length; i++) { | |
| 635 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); | |
| 636 if (cell._key == key) return i; | |
| 637 } | |
| 638 return -1; | |
| 639 } | |
| 640 | |
| 641 static _newHashTable() { | |
| 642 // Create a new JavaScript object to be used as a hash table. Use | |
| 643 // Object.create to avoid the properties on Object.prototype | |
| 644 // showing up as entries. | |
| 645 var table = JS('var', 'Object.create(null)'); | |
| 646 // Attempt to force the hash table into 'dictionary' mode by | |
| 647 // adding a property to it and deleting it again. | |
| 648 var temporaryKey = '<non-identifier-key>'; | |
| 649 _setTableEntry(table, temporaryKey, table); | |
| 650 _deleteTableEntry(table, temporaryKey); | |
| 651 return table; | |
| 652 } | |
| 653 } | |
| 654 | |
| 655 class LinkedHashMapCell { | |
| 656 final _key; | |
| 657 var _value; | |
| 658 | |
| 659 LinkedHashMapCell _next; | |
| 660 LinkedHashMapCell _previous; | |
| 661 | |
| 662 LinkedHashMapCell(this._key, this._value); | |
| 663 } | |
| 664 | |
| 665 class LinkedHashMapKeyIterable<E> extends IterableBase<E> { | |
| 666 final _map; | |
| 667 LinkedHashMapKeyIterable(this._map); | |
| 668 | |
| 669 int get length => _map._length; | |
| 670 bool get isEmpty => _map._length == 0; | |
| 671 | |
| 672 Iterator<E> get iterator { | |
| 673 return new LinkedHashMapKeyIterator<E>(_map, _map._modifications); | |
| 674 } | |
| 675 | |
| 676 bool contains(E element) { | |
| 677 return _map.containsKey(element); | |
| 678 } | |
| 679 | |
| 680 void forEach(void f(E element)) { | |
| 681 LinkedHashMapCell cell = _map._first; | |
| 682 int modifications = _map._modifications; | |
| 683 while (cell != null) { | |
| 684 f(cell._key); | |
| 685 if (modifications != _map._modifications) { | |
| 686 throw new ConcurrentModificationError(_map); | |
| 687 } | |
| 688 cell = cell._next; | |
| 689 } | |
| 690 } | |
| 691 } | |
| 692 | |
| 693 class LinkedHashMapKeyIterator<E> implements Iterator<E> { | |
| 694 final _map; | |
| 695 final int _modifications; | |
| 696 LinkedHashMapCell _cell; | |
| 697 E _current; | |
| 698 | |
| 699 LinkedHashMapKeyIterator(this._map, this._modifications) { | |
| 700 _cell = _map._first; | |
| 701 } | |
| 702 | |
| 703 E get current => _current; | |
| 704 | |
| 705 bool moveNext() { | |
| 706 if (_modifications != _map._modifications) { | |
| 707 throw new ConcurrentModificationError(_map); | |
| 708 } else if (_cell == null) { | |
| 709 _current = null; | |
| 710 return false; | |
| 711 } else { | |
| 712 _current = _cell._key; | |
| 713 _cell = _cell._next; | |
| 714 return true; | |
| 715 } | |
| 716 } | |
| 717 } | |
| 718 | |
| 719 patch class HashSet<E> { | |
| 720 int _length = 0; | |
| 721 | |
| 722 // The hash set contents are divided into three parts: one part for | |
| 723 // string elements, one for numeric elements, and one for the | |
| 724 // rest. String and numeric elements map directly to a sentinel | |
| 725 // value, but the rest of the entries are stored in bucket lists of | |
| 726 // the form: | |
| 727 // | |
| 728 // [element-0, element-1, element-2, ...] | |
| 729 // | |
| 730 // where all elements in the same bucket share the same hash code. | |
| 731 var _strings; | |
| 732 var _nums; | |
| 733 var _rest; | |
| 734 | |
| 735 // When iterating over the hash set, it is very convenient to have a | |
| 736 // list of all the elements. We cache that on the instance and clear | |
| 737 // the the cache whenever the set changes. This is also used to | |
| 738 // guard against concurrent modifications. | |
| 739 List _elements; | |
| 740 | |
| 741 patch HashSet(); | |
| 742 | |
| 743 // Iterable. | |
| 744 patch Iterator<E> get iterator { | |
| 745 return new HashSetIterator<E>(this, _computeElements()); | |
| 746 } | |
| 747 | |
| 748 patch int get length => _length; | |
| 749 patch bool get isEmpty => _length == 0; | |
| 750 patch bool get isNotEmpty => !isEmpty; | |
| 751 | |
| 752 patch bool contains(Object object) { | |
| 753 if (_isStringElement(object)) { | |
| 754 var strings = _strings; | |
| 755 return (strings == null) ? false : _hasTableEntry(strings, object); | |
| 756 } else if (_isNumericElement(object)) { | |
| 757 var nums = _nums; | |
| 758 return (nums == null) ? false : _hasTableEntry(nums, object); | |
| 759 } else { | |
| 760 var rest = _rest; | |
| 761 if (rest == null) return false; | |
| 762 var bucket = _getBucket(rest, object); | |
| 763 return _findBucketIndex(bucket, object) >= 0; | |
| 764 } | |
| 765 } | |
| 766 | |
| 767 // Collection. | |
| 768 patch void add(E element) { | |
| 769 if (_isStringElement(element)) { | |
| 770 var strings = _strings; | |
| 771 if (strings == null) _strings = strings = _newHashTable(); | |
| 772 _addHashTableEntry(strings, element); | |
| 773 } else if (_isNumericElement(element)) { | |
| 774 var nums = _nums; | |
| 775 if (nums == null) _nums = nums = _newHashTable(); | |
| 776 _addHashTableEntry(nums, element); | |
| 777 } else { | |
| 778 var rest = _rest; | |
| 779 if (rest == null) _rest = rest = _newHashTable(); | |
| 780 var hash = _computeHashCode(element); | |
| 781 var bucket = JS('var', '#[#]', rest, hash); | |
| 782 if (bucket == null) { | |
| 783 _setTableEntry(rest, hash, JS('var', '[#]', element)); | |
| 784 } else { | |
| 785 int index = _findBucketIndex(bucket, element); | |
| 786 if (index >= 0) return; | |
| 787 JS('void', '#.push(#)', bucket, element); | |
| 788 } | |
| 789 _length++; | |
| 790 _elements = null; | |
| 791 } | |
| 792 } | |
| 793 | |
| 794 patch void addAll(Iterable<E> objects) { | |
| 795 for (E each in objects) { | |
| 796 add(each); | |
| 797 } | |
| 798 } | |
| 799 | |
| 800 patch bool remove(Object object) { | |
| 801 if (_isStringElement(object)) { | |
| 802 return _removeHashTableEntry(_strings, object); | |
| 803 } else if (_isNumericElement(object)) { | |
| 804 return _removeHashTableEntry(_nums, object); | |
| 805 } else { | |
| 806 var rest = _rest; | |
| 807 if (rest == null) return false; | |
| 808 var bucket = _getBucket(rest, object); | |
| 809 int index = _findBucketIndex(bucket, object); | |
| 810 if (index < 0) return false; | |
| 811 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 812 // the length reaches zero. | |
| 813 _length--; | |
| 814 _elements = null; | |
| 815 // TODO(kasperl): It would probably be faster to move the | |
| 816 // element to the end and reduce the length of the bucket list. | |
| 817 JS('void', '#.splice(#, 1)', bucket, index); | |
| 818 return true; | |
| 819 } | |
| 820 } | |
| 821 | |
| 822 patch void removeAll(Iterable objectsToRemove) { | |
| 823 for (var each in objectsToRemove) { | |
| 824 remove(each); | |
| 825 } | |
| 826 } | |
| 827 | |
| 828 patch void removeWhere(bool test(E element)) { | |
| 829 removeAll(_computeElements().where(test)); | |
| 830 } | |
| 831 | |
| 832 patch void retainWhere(bool test(E element)) { | |
| 833 removeAll(_computeElements().where((E element) => !test(element))); | |
| 834 } | |
| 835 | |
| 836 patch void clear() { | |
| 837 if (_length > 0) { | |
| 838 _strings = _nums = _rest = _elements = null; | |
| 839 _length = 0; | |
| 840 } | |
| 841 } | |
| 842 | |
| 843 List _computeElements() { | |
| 844 if (_elements != null) return _elements; | |
| 845 List result = new List(_length); | |
| 846 int index = 0; | |
| 847 | |
| 848 // Add all string elements to the list. | |
| 849 var strings = _strings; | |
| 850 if (strings != null) { | |
| 851 var names = JS('var', 'Object.getOwnPropertyNames(#)', strings); | |
| 852 int entries = JS('int', '#.length', names); | |
| 853 for (int i = 0; i < entries; i++) { | |
| 854 String element = JS('String', '#[#]', names, i); | |
| 855 JS('void', '#[#] = #', result, index, element); | |
| 856 index++; | |
| 857 } | |
| 858 } | |
| 859 | |
| 860 // Add all numeric elements to the list. | |
| 861 var nums = _nums; | |
| 862 if (nums != null) { | |
| 863 var names = JS('var', 'Object.getOwnPropertyNames(#)', nums); | |
| 864 int entries = JS('int', '#.length', names); | |
| 865 for (int i = 0; i < entries; i++) { | |
| 866 // Object.getOwnPropertyNames returns a list of strings, so we | |
| 867 // have to convert the elements back to numbers (+). | |
| 868 num element = JS('num', '+#[#]', names, i); | |
| 869 JS('void', '#[#] = #', result, index, element); | |
| 870 index++; | |
| 871 } | |
| 872 } | |
| 873 | |
| 874 // Add all the remaining elements to the list. | |
| 875 var rest = _rest; | |
| 876 if (rest != null) { | |
| 877 var names = JS('var', 'Object.getOwnPropertyNames(#)', rest); | |
| 878 int entries = JS('int', '#.length', names); | |
| 879 for (int i = 0; i < entries; i++) { | |
| 880 var entry = JS('String', '#[#]', names, i); | |
| 881 var bucket = JS('var', '#[#]', rest, entry); | |
| 882 int length = JS('int', '#.length', bucket); | |
| 883 for (int i = 0; i < length; i++) { | |
| 884 JS('void', '#[#] = #[#]', result, index, bucket, i); | |
| 885 index++; | |
| 886 } | |
| 887 } | |
| 888 } | |
| 889 assert(index == _length); | |
| 890 return _elements = result; | |
| 891 } | |
| 892 | |
| 893 void _addHashTableEntry(var table, E element) { | |
| 894 if (_hasTableEntry(table, element)) return; | |
| 895 _setTableEntry(table, element, 0); | |
| 896 _length++; | |
| 897 _elements = null; | |
| 898 } | |
| 899 | |
| 900 bool _removeHashTableEntry(var table, E element) { | |
| 901 if (table != null && _hasTableEntry(table, element)) { | |
| 902 _deleteTableEntry(table, element); | |
| 903 _length--; | |
| 904 _elements = null; | |
| 905 return true; | |
| 906 } else { | |
| 907 return false; | |
| 908 } | |
| 909 } | |
| 910 | |
| 911 static bool _isStringElement(var element) { | |
| 912 return element is String && element != '__proto__'; | |
| 913 } | |
| 914 | |
| 915 static bool _isNumericElement(var element) { | |
| 916 // Only treat unsigned 30-bit integers as numeric elements. This | |
| 917 // way, we avoid converting them to strings when we use them as | |
| 918 // keys in the JavaScript hash table object. | |
| 919 return element is num && | |
| 920 JS('bool', '(# & 0x3ffffff) === #', element, element); | |
| 921 } | |
| 922 | |
| 923 static int _computeHashCode(var element) { | |
| 924 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 925 // issues with problematic elements like '__proto__'. Another | |
| 926 // option would be to throw an exception if the hash code isn't a | |
| 927 // number. | |
| 928 return JS('int', '# & 0x3ffffff', element.hashCode); | |
| 929 } | |
| 930 | |
| 931 static bool _hasTableEntry(var table, var key) { | |
| 932 var entry = JS('var', '#[#]', table, key); | |
| 933 // We take care to only store non-null entries in the table, so we | |
| 934 // can check if the table has an entry for the given key with a | |
| 935 // simple null check. | |
| 936 return entry != null; | |
| 937 } | |
| 938 | |
| 939 static void _setTableEntry(var table, var key, var value) { | |
| 940 assert(value != null); | |
| 941 JS('void', '#[#] = #', table, key, value); | |
| 942 } | |
| 943 | |
| 944 static void _deleteTableEntry(var table, var key) { | |
| 945 JS('void', 'delete #[#]', table, key); | |
| 946 } | |
| 947 | |
| 948 static List _getBucket(var table, var element) { | |
| 949 var hash = _computeHashCode(element); | |
| 950 return JS('var', '#[#]', table, hash); | |
| 951 } | |
| 952 | |
| 953 static int _findBucketIndex(var bucket, var element) { | |
| 954 if (bucket == null) return -1; | |
| 955 int length = JS('int', '#.length', bucket); | |
| 956 for (int i = 0; i < length; i++) { | |
| 957 if (JS('var', '#[#]', bucket, i) == element) return i; | |
| 958 } | |
| 959 return -1; | |
| 960 } | |
| 961 | |
| 962 static _newHashTable() { | |
| 963 // Create a new JavaScript object to be used as a hash table. Use | |
| 964 // Object.create to avoid the properties on Object.prototype | |
| 965 // showing up as entries. | |
| 966 var table = JS('var', 'Object.create(null)'); | |
| 967 // Attempt to force the hash table into 'dictionary' mode by | |
| 968 // adding a property to it and deleting it again. | |
| 969 var temporaryKey = '<non-identifier-key>'; | |
| 970 _setTableEntry(table, temporaryKey, table); | |
| 971 _deleteTableEntry(table, temporaryKey); | |
| 972 return table; | |
| 973 } | |
| 974 } | |
| 975 | |
| 976 // TODO(kasperl): Share this code with HashMapKeyIterator<E>? | |
| 977 class HashSetIterator<E> implements Iterator<E> { | |
| 978 final _set; | |
| 979 final List _elements; | |
| 980 int _offset = 0; | |
| 981 E _current; | |
| 982 | |
| 983 HashSetIterator(this._set, this._elements); | |
| 984 | |
| 985 E get current => _current; | |
| 986 | |
| 987 bool moveNext() { | |
| 988 var elements = _elements; | |
| 989 int offset = _offset; | |
| 990 if (JS('bool', '# !== #', elements, _set._elements)) { | |
| 991 throw new ConcurrentModificationError(_set); | |
| 992 } else if (offset >= JS('int', '#.length', elements)) { | |
| 993 _current = null; | |
| 994 return false; | |
| 995 } else { | |
| 996 _current = JS('var', '#[#]', elements, offset); | |
| 997 // TODO(kasperl): For now, we have to tell the type inferrer to | |
| 998 // treat the result of doing offset + 1 as an int. Otherwise, we | |
| 999 // get unnecessary bailout code. | |
| 1000 _offset = JS('int', '#', offset + 1); | |
| 1001 return true; | |
| 1002 } | |
| 1003 } | |
| 1004 } | |
| 1005 | |
| 1006 patch class LinkedHashSet<E> extends _HashSetBase<E> { | |
| 1007 int _length = 0; | |
| 1008 | |
| 1009 // The hash set contents are divided into three parts: one part for | |
| 1010 // string elements, one for numeric elements, and one for the | |
| 1011 // rest. String and numeric elements map directly to their linked | |
| 1012 // cells, but the rest of the entries are stored in bucket lists of | |
| 1013 // the form: | |
| 1014 // | |
| 1015 // [cell-0, cell-1, ...] | |
| 1016 // | |
| 1017 // where all elements in the same bucket share the same hash code. | |
| 1018 var _strings; | |
| 1019 var _nums; | |
| 1020 var _rest; | |
| 1021 | |
| 1022 // The elements are stored in cells that are linked together | |
| 1023 // to form a double linked list. | |
| 1024 LinkedHashSetCell _first; | |
| 1025 LinkedHashSetCell _last; | |
| 1026 | |
| 1027 // We track the number of modifications done to the element set to | |
| 1028 // be able to throw when the set is modified while being iterated | |
| 1029 // over. | |
| 1030 int _modifications = 0; | |
| 1031 | |
| 1032 patch LinkedHashSet(); | |
| 1033 | |
| 1034 void _unsupported(String operation) { | |
| 1035 throw 'LinkedHashSet: unsupported $operation'; | |
| 1036 } | |
| 1037 | |
| 1038 // Iterable. | |
| 1039 patch Iterator<E> get iterator { | |
| 1040 return new LinkedHashSetIterator(this, _modifications); | |
| 1041 } | |
| 1042 | |
| 1043 patch int get length => _length; | |
| 1044 patch bool get isEmpty => _length == 0; | |
| 1045 patch bool get isNotEmpty => !isEmpty; | |
| 1046 | |
| 1047 patch bool contains(Object object) { | |
| 1048 if (_isStringElement(object)) { | |
| 1049 var strings = _strings; | |
| 1050 if (strings == null) return false; | |
| 1051 LinkedHashSetCell cell = _getTableEntry(strings, object); | |
| 1052 return cell != null; | |
| 1053 } else if (_isNumericElement(object)) { | |
| 1054 var nums = _nums; | |
| 1055 if (nums == null) return false; | |
| 1056 LinkedHashSetCell cell = _getTableEntry(nums, object); | |
| 1057 return cell != null; | |
| 1058 } else { | |
| 1059 var rest = _rest; | |
| 1060 if (rest == null) return false; | |
| 1061 var bucket = _getBucket(rest, object); | |
| 1062 return _findBucketIndex(bucket, object) >= 0; | |
| 1063 } | |
| 1064 } | |
| 1065 | |
| 1066 patch void forEach(void action(E element)) { | |
| 1067 LinkedHashSetCell cell = _first; | |
| 1068 int modifications = _modifications; | |
| 1069 while (cell != null) { | |
| 1070 action(cell._element); | |
| 1071 if (modifications != _modifications) { | |
| 1072 throw new ConcurrentModificationError(this); | |
| 1073 } | |
| 1074 cell = cell._next; | |
| 1075 } | |
| 1076 } | |
| 1077 | |
| 1078 patch E get first { | |
| 1079 if (_first == null) throw new StateError("No elements"); | |
| 1080 return _first._element; | |
| 1081 } | |
| 1082 | |
| 1083 patch E get last { | |
| 1084 if (_last == null) throw new StateError("No elements"); | |
| 1085 return _last._element; | |
| 1086 } | |
| 1087 | |
| 1088 // Collection. | |
| 1089 patch void add(E element) { | |
| 1090 if (_isStringElement(element)) { | |
| 1091 var strings = _strings; | |
| 1092 if (strings == null) _strings = strings = _newHashTable(); | |
| 1093 _addHashTableEntry(strings, element); | |
| 1094 } else if (_isNumericElement(element)) { | |
| 1095 var nums = _nums; | |
| 1096 if (nums == null) _nums = nums = _newHashTable(); | |
| 1097 _addHashTableEntry(nums, element); | |
| 1098 } else { | |
| 1099 var rest = _rest; | |
| 1100 if (rest == null) _rest = rest = _newHashTable(); | |
| 1101 var hash = _computeHashCode(element); | |
| 1102 var bucket = JS('var', '#[#]', rest, hash); | |
| 1103 if (bucket == null) { | |
| 1104 LinkedHashSetCell cell = _newLinkedCell(element); | |
| 1105 _setTableEntry(rest, hash, JS('var', '[#]', cell)); | |
| 1106 } else { | |
| 1107 int index = _findBucketIndex(bucket, element); | |
| 1108 if (index >= 0) return; | |
| 1109 LinkedHashSetCell cell = _newLinkedCell(element); | |
| 1110 JS('void', '#.push(#)', bucket, cell); | |
| 1111 } | |
| 1112 } | |
| 1113 } | |
| 1114 | |
| 1115 patch void addAll(Iterable<E> objects) { | |
| 1116 for (E object in objects) { | |
| 1117 add(object); | |
| 1118 } | |
| 1119 } | |
| 1120 | |
| 1121 patch bool remove(Object object) { | |
| 1122 if (_isStringElement(object)) { | |
| 1123 return _removeHashTableEntry(_strings, object); | |
| 1124 } else if (_isNumericElement(object)) { | |
| 1125 return _removeHashTableEntry(_nums, object); | |
| 1126 } else { | |
| 1127 var rest = _rest; | |
| 1128 if (rest == null) return false; | |
| 1129 var bucket = _getBucket(rest, object); | |
| 1130 int index = _findBucketIndex(bucket, object); | |
| 1131 if (index < 0) return false; | |
| 1132 // Use splice to remove the [cell] element at the index and | |
| 1133 // unlink it. | |
| 1134 LinkedHashSetCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); | |
| 1135 _unlinkCell(cell); | |
| 1136 return true; | |
| 1137 } | |
| 1138 } | |
| 1139 | |
| 1140 patch void removeAll(Iterable objectsToRemove) { | |
| 1141 for (var each in objectsToRemove) { | |
| 1142 remove(each); | |
| 1143 } | |
| 1144 } | |
| 1145 | |
| 1146 patch void removeWhere(bool test(E element)) { | |
| 1147 _filterWhere(test, true); | |
| 1148 } | |
| 1149 | |
| 1150 patch void retainWhere(bool test(E element)) { | |
| 1151 _filterWhere(test, false); | |
| 1152 } | |
| 1153 | |
| 1154 void _filterWhere(bool test(E element), bool removeMatching) { | |
| 1155 LinkedHashSetCell cell = _first; | |
| 1156 while (cell != null) { | |
| 1157 E element = cell._element; | |
| 1158 LinkedHashSetCell next = cell._next; | |
| 1159 int modifications = _modifications; | |
| 1160 bool shouldRemove = (removeMatching == test(element)); | |
| 1161 if (modifications != _modifications) { | |
| 1162 throw new ConcurrentModificationError(this); | |
| 1163 } | |
| 1164 if (shouldRemove) remove(element); | |
| 1165 cell = next; | |
| 1166 } | |
| 1167 } | |
| 1168 | |
| 1169 patch void clear() { | |
| 1170 if (_length > 0) { | |
| 1171 _strings = _nums = _rest = _first = _last = null; | |
| 1172 _length = 0; | |
| 1173 _modified(); | |
| 1174 } | |
| 1175 } | |
| 1176 | |
| 1177 void _addHashTableEntry(var table, E element) { | |
| 1178 LinkedHashSetCell cell = _getTableEntry(table, element); | |
| 1179 if (cell != null) return; | |
| 1180 _setTableEntry(table, element, _newLinkedCell(element)); | |
| 1181 } | |
| 1182 | |
| 1183 bool _removeHashTableEntry(var table, E element) { | |
| 1184 if (table == null) return false; | |
| 1185 LinkedHashSetCell cell = _getTableEntry(table, element); | |
| 1186 if (cell == null) return false; | |
| 1187 _unlinkCell(cell); | |
| 1188 _deleteTableEntry(table, element); | |
| 1189 return true; | |
| 1190 } | |
| 1191 | |
| 1192 void _modified() { | |
| 1193 // Value cycles after 2^30 modifications. If you keep hold of an | |
| 1194 // iterator for that long, you might miss a modification | |
| 1195 // detection, and iteration can go sour. Don't do that. | |
| 1196 _modifications = (_modifications + 1) & 0x3ffffff; | |
| 1197 } | |
| 1198 | |
| 1199 // Create a new cell and link it in as the last one in the list. | |
| 1200 LinkedHashSetCell _newLinkedCell(E element) { | |
| 1201 LinkedHashSetCell cell = new LinkedHashSetCell(element); | |
| 1202 if (_first == null) { | |
| 1203 _first = _last = cell; | |
| 1204 } else { | |
| 1205 LinkedHashSetCell last = _last; | |
| 1206 cell._previous = last; | |
| 1207 _last = last._next = cell; | |
| 1208 } | |
| 1209 _length++; | |
| 1210 _modified(); | |
| 1211 return cell; | |
| 1212 } | |
| 1213 | |
| 1214 // Unlink the given cell from the linked list of cells. | |
| 1215 void _unlinkCell(LinkedHashSetCell cell) { | |
| 1216 LinkedHashSetCell previous = cell._previous; | |
| 1217 LinkedHashSetCell next = cell._next; | |
| 1218 if (previous == null) { | |
| 1219 assert(cell == _first); | |
| 1220 _first = next; | |
| 1221 } else { | |
| 1222 previous._next = next; | |
| 1223 } | |
| 1224 if (next == null) { | |
| 1225 assert(cell == _last); | |
| 1226 _last = previous; | |
| 1227 } else { | |
| 1228 next._previous = previous; | |
| 1229 } | |
| 1230 _length--; | |
| 1231 _modified(); | |
| 1232 } | |
| 1233 | |
| 1234 static bool _isStringElement(var element) { | |
| 1235 return element is String && element != '__proto__'; | |
| 1236 } | |
| 1237 | |
| 1238 static bool _isNumericElement(var element) { | |
| 1239 // Only treat unsigned 30-bit integers as numeric elements. This | |
| 1240 // way, we avoid converting them to strings when we use them as | |
| 1241 // keys in the JavaScript hash table object. | |
| 1242 return element is num && | |
| 1243 JS('bool', '(# & 0x3ffffff) === #', element, element); | |
| 1244 } | |
| 1245 | |
| 1246 static int _computeHashCode(var element) { | |
| 1247 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 1248 // issues with problematic elements like '__proto__'. Another | |
| 1249 // option would be to throw an exception if the hash code isn't a | |
| 1250 // number. | |
| 1251 return JS('int', '# & 0x3ffffff', element.hashCode); | |
| 1252 } | |
| 1253 | |
| 1254 static _getTableEntry(var table, var key) { | |
| 1255 return JS('var', '#[#]', table, key); | |
| 1256 } | |
| 1257 | |
| 1258 static void _setTableEntry(var table, var key, var value) { | |
| 1259 assert(value != null); | |
| 1260 JS('void', '#[#] = #', table, key, value); | |
| 1261 } | |
| 1262 | |
| 1263 static void _deleteTableEntry(var table, var key) { | |
| 1264 JS('void', 'delete #[#]', table, key); | |
| 1265 } | |
| 1266 | |
| 1267 static List _getBucket(var table, var element) { | |
| 1268 var hash = _computeHashCode(element); | |
| 1269 return JS('var', '#[#]', table, hash); | |
| 1270 } | |
| 1271 | |
| 1272 static int _findBucketIndex(var bucket, var element) { | |
| 1273 if (bucket == null) return -1; | |
| 1274 int length = JS('int', '#.length', bucket); | |
| 1275 for (int i = 0; i < length; i++) { | |
| 1276 LinkedHashSetCell cell = JS('var', '#[#]', bucket, i); | |
| 1277 if (cell._element == element) return i; | |
| 1278 } | |
| 1279 return -1; | |
| 1280 } | |
| 1281 | |
| 1282 static _newHashTable() { | |
| 1283 // Create a new JavaScript object to be used as a hash table. Use | |
| 1284 // Object.create to avoid the properties on Object.prototype | |
| 1285 // showing up as entries. | |
| 1286 var table = JS('var', 'Object.create(null)'); | |
| 1287 // Attempt to force the hash table into 'dictionary' mode by | |
| 1288 // adding a property to it and deleting it again. | |
| 1289 var temporaryKey = '<non-identifier-key>'; | |
| 1290 _setTableEntry(table, temporaryKey, table); | |
| 1291 _deleteTableEntry(table, temporaryKey); | |
| 1292 return table; | |
| 1293 } | |
| 1294 } | |
| 1295 | |
| 1296 class LinkedHashSetCell { | |
| 1297 final _element; | |
| 1298 | |
| 1299 LinkedHashSetCell _next; | |
| 1300 LinkedHashSetCell _previous; | |
| 1301 | |
| 1302 LinkedHashSetCell(this._element); | |
| 1303 } | |
| 1304 | |
| 1305 // TODO(kasperl): Share this code with LinkedHashMapKeyIterator<E>? | |
| 1306 class LinkedHashSetIterator<E> implements Iterator<E> { | |
| 1307 final _set; | |
| 1308 final int _modifications; | |
| 1309 LinkedHashSetCell _cell; | |
| 1310 E _current; | |
| 1311 | |
| 1312 LinkedHashSetIterator(this._set, this._modifications) { | |
| 1313 _cell = _set._first; | |
| 1314 } | |
| 1315 | |
| 1316 E get current => _current; | |
| 1317 | |
| 1318 bool moveNext() { | |
| 1319 if (_modifications != _set._modifications) { | |
| 1320 throw new ConcurrentModificationError(_set); | |
| 1321 } else if (_cell == null) { | |
| 1322 _current = null; | |
| 1323 return false; | |
| 1324 } else { | |
| 1325 _current = _cell._element; | |
| 1326 _cell = _cell._next; | |
| 1327 return true; | |
| 1328 } | |
| 1329 } | |
| 1330 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 16538002:
Move lib from sdk/lib/_internal/compiler/implementation to _internal root. (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/