OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2014, 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 // Efficient JavaScript based implementation of a linked hash map used as a |
| 6 // backing map for constant maps and the [LinkedHashMap] patch |
| 7 |
| 8 part of dart._js_helper; |
| 9 |
| 10 // DDC-specific, just use Object-backed maps |
| 11 //const _USE_ES6_MAPS = const bool.fromEnvironment("dart2js.use.es6.maps"); |
| 12 |
| 13 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap { |
| 14 int _length = 0; |
| 15 |
| 16 // The hash map contents are divided into three parts: one part for |
| 17 // string keys, one for numeric keys, and one for the rest. String |
| 18 // and numeric keys map directly to their linked cells, but the rest |
| 19 // of the entries are stored in bucket lists of the form: |
| 20 // |
| 21 // [cell-0, cell-1, ...] |
| 22 // |
| 23 // where all keys in the same bucket share the same hash code. |
| 24 var _strings; |
| 25 var _nums; |
| 26 var _rest; |
| 27 |
| 28 // The keys and values are stored in cells that are linked together |
| 29 // to form a double linked list. |
| 30 LinkedHashMapCell/*<K, V>*/ _first; |
| 31 LinkedHashMapCell/*<K, V>*/ _last; |
| 32 |
| 33 // We track the number of modifications done to the key set of the |
| 34 // hash map to be able to throw when the map is modified while being |
| 35 // iterated over. |
| 36 int _modifications = 0; |
| 37 |
| 38 // static bool get _supportsEs6Maps { |
| 39 // return JS('returns:bool;depends:none;effects:none;throws:never;gvn:true', |
| 40 // 'typeof Map != "undefined"'); |
| 41 // } |
| 42 |
| 43 JsLinkedHashMap(); |
| 44 |
| 45 /// If ES6 Maps are available returns a linked hash-map backed by an ES6 Map. |
| 46 // @ForceInline() |
| 47 factory JsLinkedHashMap.es6() { |
| 48 // return (_USE_ES6_MAPS && JsLinkedHashMap._supportsEs6Maps) |
| 49 // ? new Es6LinkedHashMap<K, V>() |
| 50 // : new JsLinkedHashMap<K, V>(); |
| 51 return new JsLinkedHashMap<K, V>(); |
| 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 LinkedHashMapKeyIterable<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 if (strings == null) return false; |
| 70 return _containsTableEntry(strings, key); |
| 71 } else if (_isNumericKey(key)) { |
| 72 var nums = _nums; |
| 73 if (nums == null) return false; |
| 74 return _containsTableEntry(nums, key); |
| 75 } else { |
| 76 return internalContainsKey(key); |
| 77 } |
| 78 } |
| 79 |
| 80 bool internalContainsKey(Object key) { |
| 81 var rest = _rest; |
| 82 if (rest == null) return false; |
| 83 var bucket = _getBucket(rest, key); |
| 84 return internalFindBucketIndex(bucket, key) >= 0; |
| 85 } |
| 86 |
| 87 bool containsValue(Object value) { |
| 88 return keys.any((each) => this[each] == value); |
| 89 } |
| 90 |
| 91 void addAll(Map<K, V> other) { |
| 92 other.forEach((K key, V value) { |
| 93 this[key] = value; |
| 94 }); |
| 95 } |
| 96 |
| 97 V operator [](Object key) { |
| 98 if (_isStringKey(key)) { |
| 99 var strings = _strings; |
| 100 if (strings == null) return null; |
| 101 LinkedHashMapCell/*<K, V>*/ cell = _getTableCell(strings, key); |
| 102 return (cell == null) ? null : cell.hashMapCellValue; |
| 103 } else if (_isNumericKey(key)) { |
| 104 var nums = _nums; |
| 105 if (nums == null) return null; |
| 106 LinkedHashMapCell/*<K, V>*/ cell = _getTableCell(nums, key); |
| 107 return (cell == null) ? null : cell.hashMapCellValue; |
| 108 } else { |
| 109 return internalGet(key); |
| 110 } |
| 111 } |
| 112 |
| 113 V internalGet(Object key) { |
| 114 var rest = _rest; |
| 115 if (rest == null) return null; |
| 116 var bucket = _getBucket(rest, key); |
| 117 int index = internalFindBucketIndex(bucket, key); |
| 118 if (index < 0) return null; |
| 119 LinkedHashMapCell/*<K, V>*/ cell = JS('var', '#[#]', bucket, index); |
| 120 return cell.hashMapCellValue; |
| 121 } |
| 122 |
| 123 void operator []=(K key, V value) { |
| 124 if (_isStringKey(key)) { |
| 125 var strings = _strings; |
| 126 if (strings == null) _strings = strings = _newHashTable(); |
| 127 _addHashTableEntry(strings, key, value); |
| 128 } else if (_isNumericKey(key)) { |
| 129 var nums = _nums; |
| 130 if (nums == null) _nums = nums = _newHashTable(); |
| 131 _addHashTableEntry(nums, key, value); |
| 132 } else { |
| 133 internalSet(key, value); |
| 134 } |
| 135 } |
| 136 |
| 137 void internalSet(K key, V value) { |
| 138 var rest = _rest; |
| 139 if (rest == null) _rest = rest = _newHashTable(); |
| 140 var hash = internalComputeHashCode(key); |
| 141 var bucket = _getTableBucket(rest, hash); |
| 142 if (bucket == null) { |
| 143 LinkedHashMapCell/*<K, V>*/ cell = _newLinkedCell(key, value); |
| 144 _setTableEntry(rest, hash, JS('var', '[#]', cell)); |
| 145 } else { |
| 146 int index = internalFindBucketIndex(bucket, key); |
| 147 if (index >= 0) { |
| 148 LinkedHashMapCell/*<K, V>*/ cell = JS('var', '#[#]', bucket, index); |
| 149 cell.hashMapCellValue = value; |
| 150 } else { |
| 151 LinkedHashMapCell/*<K, V>*/ cell = _newLinkedCell(key, value); |
| 152 JS('void', '#.push(#)', bucket, cell); |
| 153 } |
| 154 } |
| 155 } |
| 156 |
| 157 V putIfAbsent(K key, V ifAbsent()) { |
| 158 if (containsKey(key)) return this[key]; |
| 159 V value = ifAbsent(); |
| 160 this[key] = value; |
| 161 return value; |
| 162 } |
| 163 |
| 164 V remove(Object key) { |
| 165 if (_isStringKey(key)) { |
| 166 return _removeHashTableEntry(_strings, key); |
| 167 } else if (_isNumericKey(key)) { |
| 168 return _removeHashTableEntry(_nums, key); |
| 169 } else { |
| 170 return internalRemove(key); |
| 171 } |
| 172 } |
| 173 |
| 174 V internalRemove(Object key) { |
| 175 var rest = _rest; |
| 176 if (rest == null) return null; |
| 177 var bucket = _getBucket(rest, key); |
| 178 int index = internalFindBucketIndex(bucket, key); |
| 179 if (index < 0) return null; |
| 180 // Use splice to remove the [cell] element at the index and |
| 181 // unlink the cell before returning its value. |
| 182 LinkedHashMapCell/*<K, V>*/ cell = |
| 183 JS('var', '#.splice(#, 1)[0]', bucket, index); |
| 184 _unlinkCell(cell); |
| 185 // TODO(kasperl): Consider getting rid of the bucket list when |
| 186 // the length reaches zero. |
| 187 return cell.hashMapCellValue; |
| 188 } |
| 189 |
| 190 void clear() { |
| 191 if (_length > 0) { |
| 192 _strings = _nums = _rest = _first = _last = null; |
| 193 _length = 0; |
| 194 _modified(); |
| 195 } |
| 196 } |
| 197 |
| 198 void forEach(void action(K key, V value)) { |
| 199 LinkedHashMapCell/*<K, V>*/ cell = _first; |
| 200 int modifications = _modifications; |
| 201 while (cell != null) { |
| 202 action(cell.hashMapCellKey, cell.hashMapCellValue); |
| 203 if (modifications != _modifications) { |
| 204 throw new ConcurrentModificationError(this); |
| 205 } |
| 206 cell = cell._next; |
| 207 } |
| 208 } |
| 209 |
| 210 void _addHashTableEntry(var table, K key, V value) { |
| 211 LinkedHashMapCell/*<K, V>*/ cell = _getTableCell(table, key); |
| 212 if (cell == null) { |
| 213 _setTableEntry(table, key, _newLinkedCell(key, value)); |
| 214 } else { |
| 215 cell.hashMapCellValue = value; |
| 216 } |
| 217 } |
| 218 |
| 219 V _removeHashTableEntry(var table, Object key) { |
| 220 if (table == null) return null; |
| 221 LinkedHashMapCell/*<K, V>*/ cell = _getTableCell(table, key); |
| 222 if (cell == null) return null; |
| 223 _unlinkCell(cell); |
| 224 _deleteTableEntry(table, key); |
| 225 return cell.hashMapCellValue; |
| 226 } |
| 227 |
| 228 void _modified() { |
| 229 // Value cycles after 2^30 modifications so that modification counts are |
| 230 // always unboxed (Smi) values. Modification detection will be missed if you |
| 231 // make exactly some multiple of 2^30 modifications between advances of an |
| 232 // iterator. |
| 233 _modifications = (_modifications + 1) & 0x3ffffff; |
| 234 } |
| 235 |
| 236 // Create a new cell and link it in as the last one in the list. |
| 237 LinkedHashMapCell/*<K, V>*/ _newLinkedCell(K key, V value) { |
| 238 LinkedHashMapCell/*<K, V>*/ cell = |
| 239 new LinkedHashMapCell/*<K, V>*/(key, value); |
| 240 if (_first == null) { |
| 241 _first = _last = cell; |
| 242 } else { |
| 243 LinkedHashMapCell/*<K, V>*/ last = _last; |
| 244 cell._previous = last; |
| 245 _last = last._next = cell; |
| 246 } |
| 247 _length++; |
| 248 _modified(); |
| 249 return cell; |
| 250 } |
| 251 |
| 252 // Unlink the given cell from the linked list of cells. |
| 253 void _unlinkCell(LinkedHashMapCell/*<K, V>*/ cell) { |
| 254 LinkedHashMapCell/*<K, V>*/ previous = cell._previous; |
| 255 LinkedHashMapCell/*<K, V>*/ next = cell._next; |
| 256 if (previous == null) { |
| 257 assert(cell == _first); |
| 258 _first = next; |
| 259 } else { |
| 260 previous._next = next; |
| 261 } |
| 262 if (next == null) { |
| 263 assert(cell == _last); |
| 264 _last = previous; |
| 265 } else { |
| 266 next._previous = previous; |
| 267 } |
| 268 _length--; |
| 269 _modified(); |
| 270 } |
| 271 |
| 272 static bool _isStringKey(var key) { |
| 273 return key is String; |
| 274 } |
| 275 |
| 276 static bool _isNumericKey(var key) { |
| 277 // Only treat unsigned 30-bit integers as numeric keys. This way, |
| 278 // we avoid converting them to strings when we use them as keys in |
| 279 // the JavaScript hash table object. |
| 280 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); |
| 281 } |
| 282 |
| 283 int internalComputeHashCode(var key) { |
| 284 // We force the hash codes to be unsigned 30-bit integers to avoid |
| 285 // issues with problematic keys like '__proto__'. Another option |
| 286 // would be to throw an exception if the hash code isn't a number. |
| 287 return JS('int', '# & 0x3ffffff', key.hashCode); |
| 288 } |
| 289 |
| 290 List<dynamic/*=LinkedHashMapCell<K, V>*/ > _getBucket(var table, var key) { |
| 291 var hash = internalComputeHashCode(key); |
| 292 return _getTableBucket(table, hash); |
| 293 } |
| 294 |
| 295 int internalFindBucketIndex(var bucket, var key) { |
| 296 if (bucket == null) return -1; |
| 297 int length = JS('int', '#.length', bucket); |
| 298 for (int i = 0; i < length; i++) { |
| 299 LinkedHashMapCell/*<K, V>*/ cell = JS('var', '#[#]', bucket, i); |
| 300 if (cell.hashMapCellKey == key) return i; |
| 301 } |
| 302 return -1; |
| 303 } |
| 304 |
| 305 String toString() => Maps.mapToString(this); |
| 306 |
| 307 /*=LinkedHashMapCell<K, V>*/ _getTableCell(var table, var key) { |
| 308 return JS('var', '#[#]', table, key); |
| 309 } |
| 310 |
| 311 /*=List<LinkedHashMapCell<K, V>>*/ _getTableBucket(var table, var key) { |
| 312 return JS('var', '#[#]', table, key); |
| 313 } |
| 314 |
| 315 void _setTableEntry(var table, var key, var value) { |
| 316 assert(value != null); |
| 317 JS('void', '#[#] = #', table, key, value); |
| 318 } |
| 319 |
| 320 void _deleteTableEntry(var table, var key) { |
| 321 JS('void', 'delete #[#]', table, key); |
| 322 } |
| 323 |
| 324 bool _containsTableEntry(var table, var key) { |
| 325 LinkedHashMapCell/*<K, V>*/ cell = _getTableCell(table, key); |
| 326 return cell != null; |
| 327 } |
| 328 |
| 329 _newHashTable() { |
| 330 // Create a new JavaScript object to be used as a hash table. Use |
| 331 // Object.create to avoid the properties on Object.prototype |
| 332 // showing up as entries. |
| 333 var table = JS('var', 'Object.create(null)'); |
| 334 // Attempt to force the hash table into 'dictionary' mode by |
| 335 // adding a property to it and deleting it again. |
| 336 var temporaryKey = '<non-identifier-key>'; |
| 337 _setTableEntry(table, temporaryKey, table); |
| 338 _deleteTableEntry(table, temporaryKey); |
| 339 return table; |
| 340 } |
| 341 } |
| 342 |
| 343 class Es6LinkedHashMap<K, V> extends JsLinkedHashMap<K, V> { |
| 344 @override |
| 345 /*=LinkedHashMapCell<K, V>*/ _getTableCell(var table, var key) { |
| 346 return JS('var', '#.get(#)', table, key); |
| 347 } |
| 348 |
| 349 @override |
| 350 /*=List<LinkedHashMapCell<K, V>>*/ _getTableBucket(var table, var key) { |
| 351 return JS('var', '#.get(#)', table, key); |
| 352 } |
| 353 |
| 354 @override |
| 355 void _setTableEntry(var table, var key, var value) { |
| 356 JS('void', '#.set(#, #)', table, key, value); |
| 357 } |
| 358 |
| 359 @override |
| 360 void _deleteTableEntry(var table, var key) { |
| 361 JS('void', '#.delete(#)', table, key); |
| 362 } |
| 363 |
| 364 @override |
| 365 bool _containsTableEntry(var table, var key) { |
| 366 return JS('bool', '#.has(#)', table, key); |
| 367 } |
| 368 |
| 369 @override |
| 370 _newHashTable() { |
| 371 return JS('var', 'new Map()'); |
| 372 } |
| 373 } |
| 374 |
| 375 class LinkedHashMapCell<K, V> { |
| 376 final dynamic/*=K*/ hashMapCellKey; |
| 377 dynamic/*=V*/ hashMapCellValue; |
| 378 |
| 379 LinkedHashMapCell/*<K, V>*/ _next; |
| 380 LinkedHashMapCell/*<K, V>*/ _previous; |
| 381 |
| 382 LinkedHashMapCell(this.hashMapCellKey, this.hashMapCellValue); |
| 383 } |
| 384 |
| 385 class LinkedHashMapKeyIterable<E> extends Iterable<E> |
| 386 implements EfficientLength { |
| 387 final dynamic/*=JsLinkedHashMap<E, dynamic>*/ _map; |
| 388 LinkedHashMapKeyIterable(this._map); |
| 389 |
| 390 int get length => _map._length; |
| 391 bool get isEmpty => _map._length == 0; |
| 392 |
| 393 Iterator<E> get iterator { |
| 394 return new LinkedHashMapKeyIterator<E>(_map, _map._modifications); |
| 395 } |
| 396 |
| 397 bool contains(Object element) { |
| 398 return _map.containsKey(element); |
| 399 } |
| 400 |
| 401 void forEach(void f(E element)) { |
| 402 LinkedHashMapCell/*<E, dynamic>*/ cell = _map._first; |
| 403 int modifications = _map._modifications; |
| 404 while (cell != null) { |
| 405 f(cell.hashMapCellKey); |
| 406 if (modifications != _map._modifications) { |
| 407 throw new ConcurrentModificationError(_map); |
| 408 } |
| 409 cell = cell._next; |
| 410 } |
| 411 } |
| 412 } |
| 413 |
| 414 class LinkedHashMapKeyIterator<E> implements Iterator<E> { |
| 415 final dynamic/*=JsLinkedHashMap<E, dynamic>*/ _map; |
| 416 final int _modifications; |
| 417 LinkedHashMapCell/*<E, dynamic>*/ _cell; |
| 418 E _current; |
| 419 |
| 420 LinkedHashMapKeyIterator(this._map, this._modifications) { |
| 421 _cell = _map._first; |
| 422 } |
| 423 |
| 424 E get current => _current; |
| 425 |
| 426 bool moveNext() { |
| 427 if (_modifications != _map._modifications) { |
| 428 throw new ConcurrentModificationError(_map); |
| 429 } else if (_cell == null) { |
| 430 _current = null; |
| 431 return false; |
| 432 } else { |
| 433 _current = _cell.hashMapCellKey; |
| 434 _cell = _cell._next; |
| 435 return true; |
| 436 } |
| 437 } |
| 438 } |
OLD | NEW |