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

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

Issue 12827018: Add a new implementation of HashMap that uses JS objects for its (multiple) hash tables. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Remove type. Created 7 years, 8 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/_internal/libraries.dart ('k') | tests/corelib/map_keys_test.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file 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 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 part of dart.collection; 5 part of dart.collection;
6 6
7 class _HashMapTable<K, V> extends _HashTable<K> { 7 class _HashMapTable<K, V> extends _HashTable<K> {
8 static const int _INITIAL_CAPACITY = 8; 8 static const int _INITIAL_CAPACITY = 8;
9 static const int _VALUE_INDEX = 1; 9 static const int _VALUE_INDEX = 1;
10 10
11 _HashMapTable() : super(_INITIAL_CAPACITY); 11 _HashMapTable() : super(_INITIAL_CAPACITY);
12 12
13 int get _entrySize => 2; 13 int get _entrySize => 2;
14 14
15 V _value(int offset) => _table[offset + _VALUE_INDEX]; 15 V _value(int offset) => _table[offset + _VALUE_INDEX];
16 void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; } 16 void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; }
17 17
18 _copyEntry(List fromTable, int fromOffset, int toOffset) { 18 _copyEntry(List fromTable, int fromOffset, int toOffset) {
19 _table[toOffset + _VALUE_INDEX] = fromTable[fromOffset + _VALUE_INDEX]; 19 _table[toOffset + _VALUE_INDEX] = fromTable[fromOffset + _VALUE_INDEX];
20 } 20 }
21 } 21 }
22 22
23 class HashMap<K, V> implements Map<K, V> { 23 class HashMap<K, V> implements Map<K, V> {
24 final _HashMapTable<K, V> _hashTable; 24 external HashMap();
25
26 HashMap() : _hashTable = new _HashMapTable<K, V>() {
27 _hashTable._container = this;
28 }
29 25
30 factory HashMap.from(Map<K, V> other) { 26 factory HashMap.from(Map<K, V> other) {
31 return new HashMap<K, V>()..addAll(other); 27 return new HashMap<K, V>()..addAll(other);
32 } 28 }
33 29
34 bool containsKey(K key) { 30 external int get length;
35 return _hashTable._get(key) >= 0; 31 external bool get isEmpty;
36 }
37 32
38 bool containsValue(V value) { 33 external Iterable<K> get keys;
39 List table = _hashTable._table; 34 external Iterable<V> get values;
40 int entrySize = _hashTable._entrySize;
41 for (int offset = 0; offset < table.length; offset += entrySize) {
42 if (!_hashTable._isFree(table[offset]) &&
43 _hashTable._value(offset) == value) {
44 return true;
45 }
46 }
47 return false;
48 }
49 35
50 void addAll(Map<K, V> other) { 36 external bool containsKey(K key);
51 other.forEach((K key, V value) { 37 external bool containsValue(V value);
52 int offset = _hashTable._put(key);
53 _hashTable._setValue(offset, value);
54 _hashTable._checkCapacity();
55 });
56 }
57 38
58 V operator [](K key) { 39 external void addAll(Map<K, V> other);
59 int offset = _hashTable._get(key);
60 if (offset >= 0) return _hashTable._value(offset);
61 return null;
62 }
63 40
64 void operator []=(K key, V value) { 41 external V operator [](K key);
65 int offset = _hashTable._put(key); 42 external void operator []=(K key, V value);
66 _hashTable._setValue(offset, value);
67 _hashTable._checkCapacity();
68 }
69 43
70 V putIfAbsent(K key, V ifAbsent()) { 44 external V putIfAbsent(K key, V ifAbsent());
71 int offset = _hashTable._probeForAdd(_hashTable._hashCodeOf(key), key);
72 Object entry = _hashTable._table[offset];
73 if (!_hashTable._isFree(entry)) {
74 return _hashTable._value(offset);
75 }
76 int modificationCount = _hashTable._modificationCount;
77 V value = ifAbsent();
78 if (modificationCount == _hashTable._modificationCount) {
79 _hashTable._setKey(offset, key);
80 _hashTable._setValue(offset, value);
81 if (entry == null) {
82 _hashTable._entryCount++;
83 _hashTable._checkCapacity();
84 } else {
85 assert(identical(entry, _TOMBSTONE));
86 _hashTable._deletedCount--;
87 }
88 _hashTable._recordModification();
89 } else {
90 // The table might have changed, so we can't trust [offset] any more.
91 // Do another lookup before setting the value.
92 offset = _hashTable._put(key);
93 _hashTable._setValue(offset, value);
94 _hashTable._checkCapacity();
95 }
96 return value;
97 }
98 45
99 V remove(K key) { 46 external V remove(K key);
100 int offset = _hashTable._remove(key); 47 external void clear();
101 if (offset < 0) return null;
102 V oldValue = _hashTable._value(offset);
103 _hashTable._setValue(offset, null);
104 _hashTable._checkCapacity();
105 return oldValue;
106 }
107 48
108 void clear() { 49 external void forEach(void action(K key, V value));
109 _hashTable._clear();
110 }
111
112 void forEach(void action (K key, V value)) {
113 int modificationCount = _hashTable._modificationCount;
114 List table = _hashTable._table;
115 int entrySize = _hashTable._entrySize;
116 for (int offset = 0; offset < table.length; offset += entrySize) {
117 Object entry = table[offset];
118 if (!_hashTable._isFree(entry)) {
119 K key = entry;
120 V value = _hashTable._value(offset);
121 action(key, value);
122 _hashTable._checkModification(modificationCount);
123 }
124 }
125 }
126
127 Iterable<K> get keys => new _HashTableKeyIterable<K>(_hashTable);
128 Iterable<V> get values =>
129 new _HashTableValueIterable<V>(_hashTable, _HashMapTable._VALUE_INDEX);
130
131 int get length => _hashTable._elementCount;
132
133 bool get isEmpty => _hashTable._elementCount == 0;
134 50
135 String toString() => Maps.mapToString(this); 51 String toString() => Maps.mapToString(this);
136 } 52 }
OLDNEW
« no previous file with comments | « sdk/lib/_internal/libraries.dart ('k') | tests/corelib/map_keys_test.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698