1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala.collection
package mutable
/**
* @define Coll OpenHashMap
* @define coll open hash map
*
* @since 2.7
*/
object OpenHashMap {
def apply[K, V](elems : (K, V)*) = {
val dict = new OpenHashMap[K, V];
elems.foreach({case (x, y) => dict(x) = y});
dict;
}
def empty[K, V] = new OpenHashMap[K, V];
final private class OpenEntry[Key, Value](val key: Key,
val hash: Int,
var value: Option[Value])
extends HashEntry[Key, OpenEntry[Key, Value]]
private[mutable] def highestOneBit(j : Int) = { // This should really go somewhere central as we're now code sharing by cut and paste. :(
var i = j;
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
i - (i >>> 1);
}
private[mutable] def nextPowerOfTwo(i : Int) = highestOneBit(i) << 1;
}
/** A mutable hash map based on an open hashing scheme. The precise scheme is undefined,
* but it should make a reasonable effort to ensure that an insert with consecutive hash
* codes is not unneccessarily penalised. In particular, mappings of consecutive integer
* keys should work without significant performance loss.
*
* @tparam Key type of the keys in this map.
* @tparam Value type of the values in this map.
* @param initialSize the initial size of the internal hash table.
*
* @author David MacIver
* @since 2.7
*
* @define Coll OpenHashMap
* @define coll open hash map
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
class OpenHashMap[Key, Value](initialSize : Int)
extends Map[Key, Value]
with MapLike[Key, Value, OpenHashMap[Key, Value]] {
import OpenHashMap.OpenEntry
type Entry = OpenEntry[Key, Value]
/**
* A default constructor creates a hashmap with initial size 8.
*/
def this() = this(8);
override def empty: OpenHashMap[Key, Value] = OpenHashMap.empty[Key, Value]
private[this] val actualInitialSize = OpenHashMap.nextPowerOfTwo(initialSize);
private var mask = actualInitialSize - 1;;
private var table : Array[Entry] = new Array[Entry](actualInitialSize);
private var _size = 0;
private var deleted = 0;
// Used for tracking inserts so that iterators can determine in concurrent modification has occurred.
private[this] var modCount = 0;
override def size = _size;
private[this] def size_=(s : Int) = _size = s;
/** Returns a mangled hash code of the provided key. */
protected def hashOf(key : Key) = {
var h = key.##
h ^= ((h >>> 20) ^ (h >>> 12));
h ^ (h >>> 7) ^ (h >>> 4);
}
private[this] def growTable = {
val oldSize = mask + 1;
val newSize = 4 * oldSize;
val oldTable = table;
table = new Array[Entry](newSize);
mask = newSize - 1;
oldTable.foreach( entry =>
if (entry != null && entry.value != None) addEntry(entry));
deleted = 0;
}
private[this] def findIndex(key : Key) : Int = findIndex(key, hashOf(key));
private[this] def findIndex(key : Key, hash : Int) : Int = {
var j = hash;
var index = hash & mask;
var perturb = index;
while(table(index) != null &&
!(table(index).hash == hash &&
table(index).key == key)){
j = 5 * j + 1 + perturb;
perturb >>= 5;
index = j & mask;
}
index;
}
private[this] def addEntry(entry : Entry) =
if (entry != null) table(findIndex(entry.key, entry.hash)) = entry;
override def update(key : Key, value : Value) {
put(key, hashOf(key), value);
}
def += (kv: (Key, Value)): this.type = { put(kv._1, kv._2); this }
def -= (key: Key): this.type = { remove(key); this }
override def put(key : Key, value : Value): Option[Value] =
put(key, hashOf(key), value)
private def put(key : Key, hash : Int, value : Value): Option[Value] = {
if (2 * (size + deleted) > mask) growTable;
val index = findIndex(key, hash);
val entry = table(index);
if (entry == null) {
table(index) = new OpenEntry(key, hash, Some(value));
modCount += 1;
size += 1;
None
} else {
val res = entry.value
if (entry.value == None) { size += 1; modCount += 1 }
entry.value = Some(value);
res
}
}
override def remove(key : Key): Option[Value] = {
val index = findIndex(key);
if (table(index) != null && table(index).value != None){
val res = table(index).value
table(index).value = None;
size -= 1;
deleted += 1;
res
} else None
}
def get(key : Key) : Option[Value] = {
val hash = hashOf(key);
var j = hash;
var index = hash & mask;
var perturb = index;
var entry = table(index);
while(entry != null){
if (entry.hash == hash &&
entry.key == key){
return entry.value;
}
j = 5 * j + 1 + perturb;
perturb >>= 5;
index = j & mask;
entry = table(index);
}
None;
}
/** An iterator over the elements of this map. Use of this iterator follows the same
* contract for concurrent modification as the foreach method.
*
* @return the iterator
*/
def iterator = new Iterator[(Key, Value)]{
var index = 0;
val initialModCount = modCount;
private[this] def advance {
if (initialModCount != modCount) system.error("Concurrent modification");
while((index <= mask) && (table(index) == null || table(index).value == None)) index+=1;
}
def hasNext = {advance; index <= mask; }
def next = {
advance;
val result = table(index);
index += 1;
(result.key, result.value.get);
}
}
override def clone = {
val it = new OpenHashMap[Key, Value]
foreachUndeletedEntry(entry => it.put(entry.key, entry.hash, entry.value.get));
it
}
/**
* Loop over the key, value mappings of this map.
*
* The behaviour of modifying the map during an iteration is as follows:
*
* <ul>
* <li>Deleting a mapping is always permitted.</li>
* <li>Changing the value of mapping which is already present is permitted.</li>
* <li>Anything else is not permitted. It will usually, but not always, throw an exception.</li>
* </ul>
*
* @tparam U The return type of the specified function `f`, return result of which is ignored.
* @param f The function to apply to each key, value mapping.
*/
override def foreach[U](f : ((Key, Value)) => U) {
val startModCount = modCount;
foreachUndeletedEntry(entry => {
if (modCount != startModCount) system.error("Concurrent Modification")
f((entry.key, entry.value.get))}
);
}
private[this] def foreachUndeletedEntry(f : Entry => Unit){
table.foreach(entry => if (entry != null && entry.value != None) f(entry));
}
override def transform(f : (Key, Value) => Value) = {
foreachUndeletedEntry(entry => entry.value = Some(f(entry.key, entry.value.get)));
this
}
override def retain(f : (Key, Value) => Boolean) = {
foreachUndeletedEntry(entry => if (!f(entry.key, entry.value.get)) {entry.value = None; size -= 1; deleted += 1} );
this
}
override def stringPrefix = "OpenHashMap"
}
|