OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 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 patch class Expando<T> { | 5 patch class Expando<T> { |
6 /* patch */ Expando([this.name]) : _data = new List(); | 6 /* patch */ Expando([this.name]) |
| 7 : _data = new List(_minSize), |
| 8 _used = 0; |
| 9 |
| 10 static const _minSize = 8; |
| 11 static final _deletedEntry = new _WeakProperty(null, null); |
7 | 12 |
8 /* patch */ T operator[](Object object) { | 13 /* patch */ T operator[](Object object) { |
9 _checkType(object); | 14 _checkType(object); |
10 var doCompact = false; | 15 |
11 var result = null; | 16 var mask = _size - 1; |
12 for (int i = 0; i < _data.length; ++i) { | 17 var idx = object.hashCode & mask; |
13 var key = _data[i].key; | 18 var wp = _data[idx]; |
14 if (identical(key, object)) { | 19 |
15 result = _data[i].value; | 20 while (wp != null) { |
16 break; | 21 if (identical(wp.key, object)) { |
| 22 return wp.value; |
| 23 } else if (wp.key == null) { |
| 24 // This entry has been cleared by the GC. |
| 25 _data[idx] = _deletedEntry; |
17 } | 26 } |
18 if (key == null) { | 27 idx = (idx + 1) & mask; |
19 doCompact = true; | 28 wp = _data[idx]; |
20 _data[i] = null; | |
21 } | |
22 } | 29 } |
23 if (doCompact) { | 30 |
24 _data = _data.where((e) => (e != null)).toList(); | 31 return null; |
25 } | |
26 return result; | |
27 } | 32 } |
28 | 33 |
29 /* patch */ void operator[]=(Object object, T value) { | 34 /* patch */ void operator[]=(Object object, T value) { |
30 _checkType(object); | 35 _checkType(object); |
31 var doCompact = false; | 36 |
32 int i = 0; | 37 var mask = _size - 1; |
33 for (; i < _data.length; ++i) { | 38 var idx = object.hashCode & mask; |
34 var key = _data[i].key; | 39 var empty_idx = -1; |
35 if (identical(key, object)) { | 40 var wp = _data[idx]; |
36 break; | 41 |
| 42 while (wp != null) { |
| 43 if (identical(wp.key, object)) { |
| 44 if (value != null) { |
| 45 // Update the associated value. |
| 46 wp.value = value; |
| 47 } else { |
| 48 // Mark the entry as deleted. |
| 49 _data[idx] = _deletedEntry; |
| 50 } |
| 51 return; |
| 52 } else if ((empty_idx < 0) && identical(wp, _deletedEntry)) { |
| 53 empty_idx = idx; // Insert at this location if not found. |
| 54 } else if (wp.key == null) { |
| 55 // This entry has been cleared by the GC. |
| 56 _data[idx] = _deletedEntry; |
| 57 if (empty_idx < 0) { |
| 58 empty_idx = idx; // Insert at this location if not found. |
| 59 } |
37 } | 60 } |
38 if (key == null) { | 61 idx = (idx + 1) & mask; |
39 doCompact = true; | 62 wp = _data[idx]; |
40 _data[i] = null; | 63 } |
| 64 |
| 65 if (value == null) { |
| 66 // Not entering a null value. We just needed to make sure to clear an |
| 67 // existing value if it existed. |
| 68 return; |
| 69 } |
| 70 |
| 71 if (empty_idx >= 0) { |
| 72 // We will be reusing the empty slot below. |
| 73 _used--; |
| 74 idx = empty_idx; |
| 75 } |
| 76 |
| 77 if (_used < _limit) { |
| 78 _data[idx] = new _WeakProperty(object, value); |
| 79 _used++; |
| 80 return; |
| 81 } |
| 82 |
| 83 // Grow/reallocate if too many slots have been used. |
| 84 _rehash(); |
| 85 this[object] = value; // Recursively add the value. |
| 86 } |
| 87 |
| 88 _rehash() { |
| 89 // Determine the population count of the map to allocate an appropriately |
| 90 // sized map below. |
| 91 var count = 0; |
| 92 var old_data = _data; |
| 93 var len = old_data.length; |
| 94 for (var i = 0; i < len; i++) { |
| 95 var entry = old_data[i]; |
| 96 if ((entry != null) && (entry.key != null)) { |
| 97 // Only count non-cleared entries. |
| 98 count++; |
41 } | 99 } |
42 } | 100 } |
43 if (i != _data.length && value == null) { | 101 |
44 doCompact = true; | 102 var new_size = _size; |
45 _data[i] = null; | 103 if (count <= (new_size >> 2)) { |
46 } else if (i != _data.length) { | 104 new_size = new_size >> 1; |
47 _data[i].value = value; | 105 } else if (count > (new_size >> 1)) { |
48 } else { | 106 new_size = new_size << 1; |
49 _data.add(new _WeakProperty(object, value)); | |
50 } | 107 } |
51 if (doCompact) { | 108 new_size = (new_size < _minSize) ? _minSize : new_size; |
52 _data = _data.where((e) => (e != null)).toList(); | 109 |
| 110 // Reset the mappings to empty so that we can just add the existing |
| 111 // valid entries. |
| 112 _data = new List(new_size); |
| 113 _used = 0; |
| 114 |
| 115 for (var i = 0; i < old_data.length; i++) { |
| 116 var entry = old_data[i]; |
| 117 if ((entry != null) && (entry.key != null)) { |
| 118 this[entry.key] = entry.value; |
| 119 } |
53 } | 120 } |
54 } | 121 } |
55 | 122 |
56 static _checkType(object) { | 123 static _checkType(object) { |
57 if (object == null || object is bool || object is num || object is String) { | 124 if ((object == null) || |
| 125 (object is bool) || |
| 126 (object is num) || |
| 127 (object is String)) { |
58 throw new ArgumentError(object); | 128 throw new ArgumentError(object); |
59 } | 129 } |
60 } | 130 } |
61 | 131 |
| 132 get _size => _data.length; |
| 133 get _limit => (3 * (_size ~/ 4)); |
| 134 |
62 List _data; | 135 List _data; |
| 136 int _used; // Number of used (active and deleted) slots. |
63 } | 137 } |
OLD | NEW |