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

Side by Side Diff: sdk/lib/collection/linked_hash_map.dart

Issue 12212211: Reapply "New implementation of {,Linked}Hash{Set,Map}." (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Fix breaks in pub. Created 7 years, 10 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/collection/hash_table.dart ('k') | sdk/lib/collection/linked_hash_set.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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 }
OLDNEW
« no previous file with comments | « sdk/lib/collection/hash_table.dart ('k') | sdk/lib/collection/linked_hash_set.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698