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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package collection
package mutable
/**
* @define Coll `OpenHashMap`
* @define coll open hash map
*
* @since 2.7
*/
object OpenHashMap {
import generic.BitOperations.Int.highestOneBit
def apply[K, V](elems : (K, V)*) = new OpenHashMap[K, V] ++= elems
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 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 AbstractMap[Key, Value]
with Map[Key, Value]
with MapLike[Key, Value, OpenHashMap[Key, Value]] {
import OpenHashMap.OpenEntry
private 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: Iterator[(Key, Value)] = new AbstractIterator[(Key, Value)] {
var index = 0
val initialModCount = modCount
private[this] def advance() {
if (initialModCount != modCount) sys.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:
* - Deleting a mapping is always permitted.
* - Changing the value of mapping which is already present is permitted.
* - Anything else is not permitted. It will usually, but not always, throw an exception.
*
* @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) sys.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"
}
|