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

Side by Side Diff: sdk/lib/_internal/compiler/js_lib/linked_hash_map.dart

Issue 947373003: Rename Cell properties to avoid name clashes in type inference. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 5 years, 9 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 | Annotate | Revision Log
« no previous file with comments | « sdk/lib/_internal/compiler/js_lib/collection_patch.dart ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file 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 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. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 // Efficient JavaScript based implementation of a linked hash map used as a 5 // Efficient JavaScript based implementation of a linked hash map used as a
6 // backing map for constant maps and the [LinkedHashMap] patch 6 // backing map for constant maps and the [LinkedHashMap] patch
7 7
8 part of _js_helper; 8 part of _js_helper;
9 9
10 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap { 10 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap {
(...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after
78 other.forEach((K key, V value) { 78 other.forEach((K key, V value) {
79 this[key] = value; 79 this[key] = value;
80 }); 80 });
81 } 81 }
82 82
83 V operator[](Object key) { 83 V operator[](Object key) {
84 if (_isStringKey(key)) { 84 if (_isStringKey(key)) {
85 var strings = _strings; 85 var strings = _strings;
86 if (strings == null) return null; 86 if (strings == null) return null;
87 LinkedHashMapCell cell = _getTableEntry(strings, key); 87 LinkedHashMapCell cell = _getTableEntry(strings, key);
88 return (cell == null) ? null : cell.value; 88 return (cell == null) ? null : cell.hashMapCellValue;
89 } else if (_isNumericKey(key)) { 89 } else if (_isNumericKey(key)) {
90 var nums = _nums; 90 var nums = _nums;
91 if (nums == null) return null; 91 if (nums == null) return null;
92 LinkedHashMapCell cell = _getTableEntry(nums, key); 92 LinkedHashMapCell cell = _getTableEntry(nums, key);
93 return (cell == null) ? null : cell.value; 93 return (cell == null) ? null : cell.hashMapCellValue;
94 } else { 94 } else {
95 return internalGet(key); 95 return internalGet(key);
96 } 96 }
97 } 97 }
98 98
99 V internalGet(Object key) { 99 V internalGet(Object key) {
100 var rest = _rest; 100 var rest = _rest;
101 if (rest == null) return null; 101 if (rest == null) return null;
102 var bucket = _getBucket(rest, key); 102 var bucket = _getBucket(rest, key);
103 int index = internalFindBucketIndex(bucket, key); 103 int index = internalFindBucketIndex(bucket, key);
104 if (index < 0) return null; 104 if (index < 0) return null;
105 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); 105 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index);
106 return cell.value; 106 return cell.hashMapCellValue;
107 } 107 }
108 108
109 void operator[]=(K key, V value) { 109 void operator[]=(K key, V value) {
110 if (_isStringKey(key)) { 110 if (_isStringKey(key)) {
111 var strings = _strings; 111 var strings = _strings;
112 if (strings == null) _strings = strings = _newHashTable(); 112 if (strings == null) _strings = strings = _newHashTable();
113 _addHashTableEntry(strings, key, value); 113 _addHashTableEntry(strings, key, value);
114 } else if (_isNumericKey(key)) { 114 } else if (_isNumericKey(key)) {
115 var nums = _nums; 115 var nums = _nums;
116 if (nums == null) _nums = nums = _newHashTable(); 116 if (nums == null) _nums = nums = _newHashTable();
117 _addHashTableEntry(nums, key, value); 117 _addHashTableEntry(nums, key, value);
118 } else { 118 } else {
119 internalSet(key, value); 119 internalSet(key, value);
120 } 120 }
121 } 121 }
122 122
123 void internalSet(K key, V value) { 123 void internalSet(K key, V value) {
124 var rest = _rest; 124 var rest = _rest;
125 if (rest == null) _rest = rest = _newHashTable(); 125 if (rest == null) _rest = rest = _newHashTable();
126 var hash = internalComputeHashCode(key); 126 var hash = internalComputeHashCode(key);
127 var bucket = JS('var', '#[#]', rest, hash); 127 var bucket = JS('var', '#[#]', rest, hash);
128 if (bucket == null) { 128 if (bucket == null) {
129 LinkedHashMapCell cell = _newLinkedCell(key, value); 129 LinkedHashMapCell cell = _newLinkedCell(key, value);
130 _setTableEntry(rest, hash, JS('var', '[#]', cell)); 130 _setTableEntry(rest, hash, JS('var', '[#]', cell));
131 } else { 131 } else {
132 int index = internalFindBucketIndex(bucket, key); 132 int index = internalFindBucketIndex(bucket, key);
133 if (index >= 0) { 133 if (index >= 0) {
134 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); 134 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index);
135 cell.value = value; 135 cell.hashMapCellValue = value;
136 } else { 136 } else {
137 LinkedHashMapCell cell = _newLinkedCell(key, value); 137 LinkedHashMapCell cell = _newLinkedCell(key, value);
138 JS('void', '#.push(#)', bucket, cell); 138 JS('void', '#.push(#)', bucket, cell);
139 } 139 }
140 } 140 }
141 } 141 }
142 142
143 V putIfAbsent(K key, V ifAbsent()) { 143 V putIfAbsent(K key, V ifAbsent()) {
144 if (containsKey(key)) return this[key]; 144 if (containsKey(key)) return this[key];
145 V value = ifAbsent(); 145 V value = ifAbsent();
(...skipping 16 matching lines...) Expand all
162 if (rest == null) return null; 162 if (rest == null) return null;
163 var bucket = _getBucket(rest, key); 163 var bucket = _getBucket(rest, key);
164 int index = internalFindBucketIndex(bucket, key); 164 int index = internalFindBucketIndex(bucket, key);
165 if (index < 0) return null; 165 if (index < 0) return null;
166 // Use splice to remove the [cell] element at the index and 166 // Use splice to remove the [cell] element at the index and
167 // unlink the cell before returning its value. 167 // unlink the cell before returning its value.
168 LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); 168 LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index);
169 _unlinkCell(cell); 169 _unlinkCell(cell);
170 // TODO(kasperl): Consider getting rid of the bucket list when 170 // TODO(kasperl): Consider getting rid of the bucket list when
171 // the length reaches zero. 171 // the length reaches zero.
172 return cell.value; 172 return cell.hashMapCellValue;
173 } 173 }
174 174
175 void clear() { 175 void clear() {
176 if (_length > 0) { 176 if (_length > 0) {
177 _strings = _nums = _rest = _first = _last = null; 177 _strings = _nums = _rest = _first = _last = null;
178 _length = 0; 178 _length = 0;
179 _modified(); 179 _modified();
180 } 180 }
181 } 181 }
182 182
183 void forEach(void action(K key, V value)) { 183 void forEach(void action(K key, V value)) {
184 LinkedHashMapCell cell = _first; 184 LinkedHashMapCell cell = _first;
185 int modifications = _modifications; 185 int modifications = _modifications;
186 while (cell != null) { 186 while (cell != null) {
187 action(cell.key, cell.value); 187 action(cell.hashMapCellKey, cell.hashMapCellValue);
188 if (modifications != _modifications) { 188 if (modifications != _modifications) {
189 throw new ConcurrentModificationError(this); 189 throw new ConcurrentModificationError(this);
190 } 190 }
191 cell = cell._next; 191 cell = cell._next;
192 } 192 }
193 } 193 }
194 194
195 void _addHashTableEntry(var table, K key, V value) { 195 void _addHashTableEntry(var table, K key, V value) {
196 LinkedHashMapCell cell = _getTableEntry(table, key); 196 LinkedHashMapCell cell = _getTableEntry(table, key);
197 if (cell == null) { 197 if (cell == null) {
198 _setTableEntry(table, key, _newLinkedCell(key, value)); 198 _setTableEntry(table, key, _newLinkedCell(key, value));
199 } else { 199 } else {
200 cell.value = value; 200 cell.hashMapCellValue = value;
201 } 201 }
202 } 202 }
203 203
204 V _removeHashTableEntry(var table, Object key) { 204 V _removeHashTableEntry(var table, Object key) {
205 if (table == null) return null; 205 if (table == null) return null;
206 LinkedHashMapCell cell = _getTableEntry(table, key); 206 LinkedHashMapCell cell = _getTableEntry(table, key);
207 if (cell == null) return null; 207 if (cell == null) return null;
208 _unlinkCell(cell); 208 _unlinkCell(cell);
209 _deleteTableEntry(table, key); 209 _deleteTableEntry(table, key);
210 return cell.value; 210 return cell.hashMapCellValue;
211 } 211 }
212 212
213 void _modified() { 213 void _modified() {
214 // Value cycles after 2^30 modifications. If you keep hold of an 214 // Value cycles after 2^30 modifications. If you keep hold of an
215 // iterator for that long, you might miss a modification 215 // iterator for that long, you might miss a modification
216 // detection, and iteration can go sour. Don't do that. 216 // detection, and iteration can go sour. Don't do that.
217 _modifications = (_modifications + 1) & 0x3ffffff; 217 _modifications = (_modifications + 1) & 0x3ffffff;
218 } 218 }
219 219
220 // Create a new cell and link it in as the last one in the list. 220 // Create a new cell and link it in as the last one in the list.
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after
286 List _getBucket(var table, var key) { 286 List _getBucket(var table, var key) {
287 var hash = internalComputeHashCode(key); 287 var hash = internalComputeHashCode(key);
288 return JS('var', '#[#]', table, hash); 288 return JS('var', '#[#]', table, hash);
289 } 289 }
290 290
291 int internalFindBucketIndex(var bucket, var key) { 291 int internalFindBucketIndex(var bucket, var key) {
292 if (bucket == null) return -1; 292 if (bucket == null) return -1;
293 int length = JS('int', '#.length', bucket); 293 int length = JS('int', '#.length', bucket);
294 for (int i = 0; i < length; i++) { 294 for (int i = 0; i < length; i++) {
295 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); 295 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i);
296 if (cell.key == key) return i; 296 if (cell.hashMapCellKey == key) return i;
297 } 297 }
298 return -1; 298 return -1;
299 } 299 }
300 300
301 static _newHashTable() { 301 static _newHashTable() {
302 // Create a new JavaScript object to be used as a hash table. Use 302 // Create a new JavaScript object to be used as a hash table. Use
303 // Object.create to avoid the properties on Object.prototype 303 // Object.create to avoid the properties on Object.prototype
304 // showing up as entries. 304 // showing up as entries.
305 var table = JS('var', 'Object.create(null)'); 305 var table = JS('var', 'Object.create(null)');
306 // Attempt to force the hash table into 'dictionary' mode by 306 // Attempt to force the hash table into 'dictionary' mode by
307 // adding a property to it and deleting it again. 307 // adding a property to it and deleting it again.
308 var temporaryKey = '<non-identifier-key>'; 308 var temporaryKey = '<non-identifier-key>';
309 _setTableEntry(table, temporaryKey, table); 309 _setTableEntry(table, temporaryKey, table);
310 _deleteTableEntry(table, temporaryKey); 310 _deleteTableEntry(table, temporaryKey);
311 return table; 311 return table;
312 } 312 }
313 313
314 String toString() => Maps.mapToString(this); 314 String toString() => Maps.mapToString(this);
315 } 315 }
316 316
317 class LinkedHashMapCell { 317 class LinkedHashMapCell {
318 final key; 318 final hashMapCellKey;
319 var value; 319 var hashMapCellValue;
320 320
321 LinkedHashMapCell _next; 321 LinkedHashMapCell _next;
322 LinkedHashMapCell _previous; 322 LinkedHashMapCell _previous;
323 323
324 LinkedHashMapCell(this.key, this.value); 324 LinkedHashMapCell(this.hashMapCellKey, this.hashMapCellValue);
325 } 325 }
326 326
327 class LinkedHashMapKeyIterable<E> extends IterableBase<E> 327 class LinkedHashMapKeyIterable<E> extends IterableBase<E>
328 implements EfficientLength { 328 implements EfficientLength {
329 final _map; 329 final _map;
330 LinkedHashMapKeyIterable(this._map); 330 LinkedHashMapKeyIterable(this._map);
331 331
332 int get length => _map._length; 332 int get length => _map._length;
333 bool get isEmpty => _map._length == 0; 333 bool get isEmpty => _map._length == 0;
334 334
335 Iterator<E> get iterator { 335 Iterator<E> get iterator {
336 return new LinkedHashMapKeyIterator<E>(_map, _map._modifications); 336 return new LinkedHashMapKeyIterator<E>(_map, _map._modifications);
337 } 337 }
338 338
339 bool contains(Object element) { 339 bool contains(Object element) {
340 return _map.containsKey(element); 340 return _map.containsKey(element);
341 } 341 }
342 342
343 void forEach(void f(E element)) { 343 void forEach(void f(E element)) {
344 LinkedHashMapCell cell = _map._first; 344 LinkedHashMapCell cell = _map._first;
345 int modifications = _map._modifications; 345 int modifications = _map._modifications;
346 while (cell != null) { 346 while (cell != null) {
347 f(cell.key); 347 f(cell.hashMapCellKey);
348 if (modifications != _map._modifications) { 348 if (modifications != _map._modifications) {
349 throw new ConcurrentModificationError(_map); 349 throw new ConcurrentModificationError(_map);
350 } 350 }
351 cell = cell._next; 351 cell = cell._next;
352 } 352 }
353 } 353 }
354 } 354 }
355 355
356 class LinkedHashMapKeyIterator<E> implements Iterator<E> { 356 class LinkedHashMapKeyIterator<E> implements Iterator<E> {
357 final _map; 357 final _map;
358 final int _modifications; 358 final int _modifications;
359 LinkedHashMapCell _cell; 359 LinkedHashMapCell _cell;
360 E _current; 360 E _current;
361 361
362 LinkedHashMapKeyIterator(this._map, this._modifications) { 362 LinkedHashMapKeyIterator(this._map, this._modifications) {
363 _cell = _map._first; 363 _cell = _map._first;
364 } 364 }
365 365
366 E get current => _current; 366 E get current => _current;
367 367
368 bool moveNext() { 368 bool moveNext() {
369 if (_modifications != _map._modifications) { 369 if (_modifications != _map._modifications) {
370 throw new ConcurrentModificationError(_map); 370 throw new ConcurrentModificationError(_map);
371 } else if (_cell == null) { 371 } else if (_cell == null) {
372 _current = null; 372 _current = null;
373 return false; 373 return false;
374 } else { 374 } else {
375 _current = _cell.key; 375 _current = _cell.hashMapCellKey;
376 _cell = _cell._next; 376 _cell = _cell._next;
377 return true; 377 return true;
378 } 378 }
379 } 379 }
380 } 380 }
OLDNEW
« no previous file with comments | « sdk/lib/_internal/compiler/js_lib/collection_patch.dart ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698