| 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 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 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 694353007:
Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart