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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id: HashMap.scala 16893 2009-01-13 13:09:22Z cunei $
package scalax.collection.immutable
import generic._
/** The canonical factory methods for <a href="HashMap.html">immutable HashMap's</a>.
*
* @author Martin Odersky
* @version 2.0, 19/01/2007
*/
object HashMap extends MapFactory[HashMap] {
/** The empty map of this type */
def empty[A, B] = new HashMap[A, B]
}
/** This class implements immutable maps using a hash table.
* It is optimized for sequential accesses where the last updated table is accessed most often.
* It supports with reasonable efficiency accesses to previous versions of the table by keeping
* a change log that's regularly compacted.
* It needs to synchronize most methods, so it is less suitable for highly concurrent accesses.
*
* @author Martin Odersky
* @version 2.0, 19/01/2007
*/
@serializable
class HashMap[A, B] extends Map[A,B]
with MapTemplate[A, B, HashMap]
with collection.mutable.HashTable[A] {
type Entry = collection.mutable.DefaultEntry[A, Any]
protected var later: HashMap[A, B] = null
protected var oldKey: A = _
protected var oldValue: Option[B] = _
protected var deltaSize: Int = _
override def empty[B] = HashMap.empty[A, B]
def get(key: A): Option[B] = synchronized {
var m = this
var cnt = 0
while (m.later != null) {
if (key == m.oldKey) return m.oldValue
cnt += 1
m = m.later
}
if (cnt > logLimit) makeCopy(m)
val e = m.findEntry(key)
if (e == null) None
else Some(getValue(e))
}
def update(key: A, value: B): HashMap[A, B] = synchronized {
makeCopyIfUpdated()
val e = findEntry(key)
if (e == null) {
markUpdated(key, None, 1)
later.addEntry(new Entry(key, value))
} else {
markUpdated(key, Some(getValue(e)), 0)
e.value = value
}
later
}
def - (key: A): HashMap[A, B] = synchronized {
makeCopyIfUpdated()
val e = findEntry(key)
if (e == null) this
else {
markUpdated(key, Some(getValue(e)), -1)
later removeEntry key
later
}
}
override def size: Int = synchronized {
var m = this
var cnt = 0
var s = 0
while (m.later != null) {
s -= m.deltaSize
cnt += 1
m = m.later
}
s += m.tableSize
if (cnt > logLimit) makeCopy(m)
s
}
def elements = synchronized {
makeCopyIfUpdated()
entries map {e => (e.key, getValue(e))}
}
private def getValue(e: Entry) =
e.value.asInstanceOf[B]
private def logLimit: Int = Math.sqrt(table.length).toInt
private def markUpdated(key: A, ov: Option[B], delta: Int) {
val lv = loadFactor
later = new HashMap[A, B] {
override def initialSize = 0
override def loadFactor = lv
table = HashMap.this.table
tableSize = HashMap.this.tableSize
threshold = HashMap.this.threshold
}
oldKey = key
oldValue = ov
deltaSize = delta
}
private def makeCopy(last: HashMap[A, B]) {
def undo(m: HashMap[A, B]) {
if (m ne last) {
undo(m.later)
if (m.deltaSize == 1) removeEntry(m.oldKey)
else if (m.deltaSize == 0) findEntry(m.oldKey).value = m.oldValue.get
else if (m.deltaSize == -1) addEntry(new Entry(m.oldKey, m.oldValue.get))
}
}
def copy(e: Entry): Entry =
if (e == null) null
else {
val rest = copy(e.next)
val result = new Entry(e.key, e.value)
result.next = rest
result
}
val ltable = last.table
val s = ltable.length
table = new scala.Array[collection.mutable.HashEntry[A, Entry]](s)
var i = 0
while (i < s) {
table(i) = copy(ltable(i).asInstanceOf[Entry])
i += 1
}
tableSize = last.tableSize
threshold = last.threshold
undo(this)
later = null
}
private def makeCopyIfUpdated() {
var m = this
while (m.later != null) m = m.later
if (m ne this) makeCopy(m)
}
}
|
