Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(69)

Side by Side Diff: tool/input_sdk/private/linked_hash_map.dart

Issue 1963723003: update Map (Closed) Base URL: git@github.com:dart-lang/dev_compiler.git@master
Patch Set: Created 4 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698