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: pkg/compiler/lib/src/util/maplet.dart

Issue 693183006: Revert "Move dart2js from sdk/lib/_internal/compiler to pkg/compiler" (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 1 month 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
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 library dart2js.util.maplet;
6
7 import 'dart:collection' show MapBase, IterableBase;
8
9 class Maplet<K, V> extends MapBase<K, V> {
10 static const _MARKER = const _MapletMarker();
11 static const CAPACITY = 8;
12
13 // The maplet can be in one of four states:
14 //
15 // * Empty (extra: null, key: marker, value: null)
16 // * Single element (extra: null, key: key, value: value)
17 // * List-backed (extra: length, key: list, value: null)
18 // * Map-backed (extra: marker, key: map, value: null)
19 //
20 // When the maplet is list-backed, the list has two sections: One
21 // for keys and one for values. The first [CAPACITY] entries are
22 // the keys and they may contain markers for deleted elements. After
23 // the keys there are [CAPACITY] entries for the values.
24
25 var _key = _MARKER;
26 var _value;
27 var _extra;
28
29 Maplet();
30
31 Maplet.from(Maplet<K, V> other) {
32 other.forEach((K key, V value) {
33 this[key] = value;
34 });
35 }
36
37 bool get isEmpty {
38 if (_extra == null) {
39 return _MARKER == _key;
40 } else if (_MARKER == _extra) {
41 return _key.isEmpty;
42 } else {
43 return _extra == 0;
44 }
45 }
46
47 int get length {
48 if (_extra == null) {
49 return (_MARKER == _key) ? 0 : 1;
50 } else if (_MARKER == _extra) {
51 return _key.length;
52 } else {
53 return _extra;
54 }
55 }
56
57 bool containsKey(K key) {
58 if (_extra == null) {
59 return _key == key;
60 } else if (_MARKER == _extra) {
61 return _key.containsKey(key);
62 } else {
63 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) {
64 var candidate = _key[i];
65 if (_MARKER == candidate) continue;
66 if (candidate == key) return true;
67 remaining--;
68 }
69 return false;
70 }
71 }
72
73 V operator [](K key) {
74 if (_extra == null) {
75 return (_key == key) ? _value : null;
76 } else if (_MARKER == _extra) {
77 return _key[key];
78 } else {
79 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) {
80 var candidate = _key[i];
81 if (_MARKER == candidate) continue;
82 if (candidate == key) return _key[i + CAPACITY];
83 remaining--;
84 }
85 return null;
86 }
87 }
88
89 void operator []=(K key, V value) {
90 if (_extra == null) {
91 if (_MARKER == _key) {
92 _key = key;
93 _value = value;
94 } else if (_key == key) {
95 _value = value;
96 } else {
97 List list = new List(CAPACITY * 2);
98 list[0] = _key;
99 list[1] = key;
100 list[CAPACITY] = _value;
101 list[CAPACITY + 1] = value;
102 _key = list;
103 _value = null;
104 _extra = 2; // Two elements.
105 }
106 } else if (_MARKER == _extra) {
107 _key[key] = value;
108 } else {
109 int remaining = _extra;
110 int index = 0;
111 int copyTo, copyFrom;
112 while (remaining > 0 && index < CAPACITY) {
113 var candidate = _key[index];
114 if (_MARKER == candidate) {
115 // Keep track of the last range of empty slots in the
116 // list. When we're done we'll move all the elements
117 // after those empty slots down, so that adding an element
118 // after that will preserve the insertion order.
119 if (copyFrom == index) {
120 copyFrom++;
121 } else {
122 copyTo = index;
123 copyFrom = index + 1;
124 }
125 } else if (candidate == key) {
126 _key[CAPACITY + index] = value;
127 return;
128 } else {
129 // Skipped an element that didn't match.
130 remaining--;
131 }
132 index++;
133 }
134 if (index < CAPACITY) {
135 _key[index] = key;
136 _key[CAPACITY + index] = value;
137 _extra++;
138 } else if (_extra < CAPACITY) {
139 // Move the last elements down into the last empty slots
140 // so that we have empty slots after the last element.
141 while (copyFrom < CAPACITY) {
142 _key[copyTo] = _key[copyFrom];
143 _key[CAPACITY + copyTo] = _key[CAPACITY + copyFrom];
144 copyTo++;
145 copyFrom++;
146 }
147 // Insert the new element as the last element.
148 _key[copyTo] = key;
149 _key[CAPACITY + copyTo] = value;
150 copyTo++;
151 // Add one to the length encoded in the extra field.
152 _extra++;
153 // Clear all elements after the new last elements to
154 // make sure we don't keep extra stuff alive.
155 while (copyTo < CAPACITY) {
156 _key[copyTo] = _key[CAPACITY + copyTo] = null;
157 copyTo++;
158 }
159 } else {
160 Map map = new Map();
161 forEach((eachKey, eachValue) => map[eachKey] = eachValue);
162 map[key] = value;
163 _key = map;
164 _extra = _MARKER;
165 }
166 }
167 }
168
169 V remove(K key) {
170 if (_extra == null) {
171 if (_key != key) return null;
172 _key = _MARKER;
173 V result = _value;
174 _value = null;
175 return result;
176 } else if (_MARKER == _extra) {
177 return _key.remove(key);
178 } else {
179 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) {
180 var candidate = _key[i];
181 if (_MARKER == candidate) continue;
182 if (candidate == key) {
183 int valueIndex = CAPACITY + i;
184 var result = _key[valueIndex];
185 _key[i] = _MARKER;
186 _key[valueIndex] = null;
187 _extra--;
188 return result;
189 }
190 remaining--;
191 }
192 return null;
193 }
194 }
195
196 void forEach(void action(K key, V value)) {
197 if (_extra == null) {
198 if (_MARKER != _key) action(_key, _value);
199 } else if (_MARKER == _extra) {
200 _key.forEach(action);
201 } else {
202 for (int remaining = _extra, i = 0; remaining > 0 && i < CAPACITY; i++) {
203 var candidate = _key[i];
204 if (_MARKER == candidate) continue;
205 action(candidate, _key[CAPACITY + i]);
206 remaining--;
207 }
208 }
209 }
210
211 void clear() {
212 _key = _MARKER;
213 _value = _extra = null;
214 }
215
216 Iterable<K> get keys => new _MapletKeyIterable<K>(this);
217 }
218
219 class _MapletMarker {
220 const _MapletMarker();
221 }
222
223 class _MapletKeyIterable<K> extends IterableBase<K> {
224 final Maplet<K, dynamic> maplet;
225
226 _MapletKeyIterable(this.maplet);
227
228 Iterator<K> get iterator {
229 if (maplet._extra == null) {
230 return new _MapletSingleIterator<K>(maplet._key);
231 } else if (Maplet._MARKER == maplet._extra) {
232 return maplet._key.keys.iterator;
233 } else {
234 return new _MapletListIterator<K>(maplet._key, maplet._extra);
235 }
236 }
237 }
238
239 class _MapletSingleIterator<K> implements Iterator<K> {
240 var _element;
241 K _current;
242
243 _MapletSingleIterator(this._element);
244
245 K get current => _current;
246
247 bool moveNext() {
248 if (Maplet._MARKER == _element) {
249 _current = null;
250 return false;
251 }
252 _current = _element;
253 _element = Maplet._MARKER;
254 return true;
255 }
256 }
257
258 class _MapletListIterator<K> implements Iterator<K> {
259 final List _list;
260 int _remaining;
261 int _index = 0;
262 K _current;
263
264 _MapletListIterator(this._list, this._remaining);
265
266 K get current => _current;
267
268 bool moveNext() {
269 while (_remaining > 0) {
270 var candidate = _list[_index++];
271 if (Maplet._MARKER != candidate) {
272 _current = candidate;
273 _remaining--;
274 return true;
275 }
276 }
277 _current = null;
278 return false;
279 }
280 }
OLDNEW
« no previous file with comments | « pkg/compiler/lib/src/util/link_implementation.dart ('k') | pkg/compiler/lib/src/util/setlet.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698