OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2013, 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 part of dart.collection; |
| 6 |
| 7 class _LinkedHashMapTable<K, V> extends _LinkedHashTable<K> { |
| 8 static const int _INITIAL_CAPACITY = 8; |
| 9 static const int _VALUE_INDEX = 3; |
| 10 |
| 11 int get _entrySize => 4; |
| 12 |
| 13 _LinkedHashMapTable() : super(_INITIAL_CAPACITY); |
| 14 |
| 15 V _value(int offset) => _table[offset + _VALUE_INDEX]; |
| 16 void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; } |
| 17 |
| 18 _copyEntry(List oldTable, int fromOffset, int toOffset) { |
| 19 _table[toOffset + _VALUE_INDEX] = oldTable[fromOffset + _VALUE_INDEX]; |
| 20 } |
| 21 } |
| 22 |
| 23 /** |
| 24 * A hash-based map that iterates keys and values in key insertion order. |
| 25 */ |
| 26 class LinkedHashMap<K, V> implements Map<K, V> { |
| 27 final _LinkedHashMapTable _hashTable; |
| 28 |
| 29 LinkedHashMap() : _hashTable = new _LinkedHashMapTable<K, V>() { |
| 30 _hashTable._container = this; |
| 31 } |
| 32 |
| 33 factory LinkedHashMap.from(Map<K, V> other) { |
| 34 return new LinkedHashMap<K, V>()..addAll(other); |
| 35 } |
| 36 |
| 37 bool containsKey(K key) { |
| 38 return _hashTable._get(key) >= 0; |
| 39 } |
| 40 |
| 41 bool containsValue(V value) { |
| 42 int modificationCount = _hashTable._modificationCount; |
| 43 for (int offset = _hashTable._next(_LinkedHashTable._HEAD_OFFSET); |
| 44 offset != _LinkedHashTable._HEAD_OFFSET; |
| 45 offset = _hashTable._next(offset)) { |
| 46 if (_hashTable._value(offset) == value) { |
| 47 return true; |
| 48 } |
| 49 // The == call may modify the table. |
| 50 _hashTable._checkModification(modificationCount); |
| 51 } |
| 52 return false; |
| 53 } |
| 54 |
| 55 void addAll(Map<K, V> other) { |
| 56 other.forEach((K key, V value) { |
| 57 int offset = _hashTable._put(key); |
| 58 _hashTable._setValue(offset, value); |
| 59 _hashTable._checkCapacity(); |
| 60 }); |
| 61 } |
| 62 |
| 63 V operator [](K key) { |
| 64 int offset = _hashTable._get(key); |
| 65 if (offset >= 0) return _hashTable._value(offset); |
| 66 return null; |
| 67 } |
| 68 |
| 69 void operator []=(K key, V value) { |
| 70 int offset = _hashTable._put(key); |
| 71 _hashTable._setValue(offset, value); |
| 72 _hashTable._checkCapacity(); |
| 73 } |
| 74 |
| 75 V putIfAbsent(K key, V ifAbsent()) { |
| 76 int offset = _hashTable._probeForAdd(_hashTable._hashCodeOf(key), key); |
| 77 Object entry = _hashTable._table[offset]; |
| 78 if (!_hashTable._isFree(entry)) { |
| 79 return _hashTable._value(offset); |
| 80 } |
| 81 int modificationCount = _hashTable._modificationCount; |
| 82 V value = ifAbsent(); |
| 83 if (modificationCount == _hashTable._modificationCount) { |
| 84 _hashTable._setKey(offset, key); |
| 85 _hashTable._setValue(offset, value); |
| 86 _hashTable._linkLast(offset); |
| 87 if (entry == null) { |
| 88 _hashTable._entryCount++; |
| 89 _hashTable._checkCapacity(); |
| 90 } else { |
| 91 assert(identical(entry, _TOMBSTONE)); |
| 92 _hashTable._deletedCount--; |
| 93 } |
| 94 _hashTable._recordModification(); |
| 95 } else { |
| 96 // The table might have changed, so we can't trust [offset] any more. |
| 97 // Do another lookup before setting the value. |
| 98 offset = _hashTable._put(key); |
| 99 _hashTable._setValue(offset, value); |
| 100 _hashTable._checkCapacity(); |
| 101 } |
| 102 return value; |
| 103 } |
| 104 |
| 105 V remove(K key) { |
| 106 int offset = _hashTable._remove(key); |
| 107 if (offset < 0) return null; |
| 108 Object oldValue = _hashTable._value(offset); |
| 109 _hashTable._setValue(offset, null); |
| 110 _hashTable._checkCapacity(); |
| 111 return oldValue; |
| 112 } |
| 113 |
| 114 void clear() { |
| 115 _hashTable._clear(); |
| 116 } |
| 117 |
| 118 void forEach(void action (K key, V value)) { |
| 119 int modificationCount = _hashTable._modificationCount; |
| 120 for (int offset = _hashTable._next(_LinkedHashTable._HEAD_OFFSET); |
| 121 offset != _LinkedHashTable._HEAD_OFFSET; |
| 122 offset = _hashTable._next(offset)) { |
| 123 action(_hashTable._key(offset), _hashTable._value(offset)); |
| 124 _hashTable._checkModification(modificationCount); |
| 125 } |
| 126 } |
| 127 |
| 128 Iterable<K> get keys => new _LinkedHashTableKeyIterable<K>(_hashTable); |
| 129 Iterable<V> get values => |
| 130 new _LinkedHashTableValueIterable<V>(_hashTable, |
| 131 _LinkedHashMapTable._VALUE_INDEX); |
| 132 |
| 133 int get length => _hashTable._elementCount; |
| 134 |
| 135 bool get isEmpty => _hashTable._elementCount == 0; |
| 136 |
| 137 String toString() => Maps.mapToString(this); |
| 138 } |
OLD | NEW |