blob: ff470ef5dc267dc1e69271090b2dcf2153da8b3a (
plain) (
blame)
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
|
package dotty.tools.dotc.util
/** A hash set that allows some privileged protected access to its internals
*/
class HashSet[T >: Null <: AnyRef](initialCapacity: Int, loadFactor: Float = 0.25f) extends Set[T] {
private var used: Int = _
private var limit: Int = _
private var table: Array[AnyRef] = _
clear()
/** The number of elements in the set */
def size: Int = used
private def allocate(size: Int) = {
table = new Array[AnyRef](size)
limit = (size * loadFactor).toInt
}
/** Remove all elements from this set and set back to initial configuration */
def clear(): Unit = {
used = 0
allocate(initialCapacity)
}
/** Turn hashode `x` into a table index */
private def index(x: Int): Int = math.abs(x % table.length)
/** Hashcode, can be overridden */
def hash(x: T): Int = x.hashCode
/** Find entry such that `x equals entry`. If it exists, return it.
* If not, enter `x` in set and return `x`.
*/
def findEntryOrUpdate(x: T): T = {
var h = index(hash(x))
var entry = table(h)
while (entry ne null) {
if (x equals entry) return entry.asInstanceOf[T]
h = index(h + 1)
entry = table(h)
}
addEntryAt(h, x)
}
/** Add entry at `x` at index `idx` */
private def addEntryAt(idx: Int, x: T) = {
table(idx) = x
used += 1
if (used > limit) growTable()
x
}
/** The entry in the set such that `x equals entry`, or else `null`. */
def findEntry(x: T): T = {
var h = index(hash(x))
var entry = table(h)
while ((entry ne null) && !(x equals entry)) {
h = index(h + 1)
entry = table(h)
}
entry.asInstanceOf[T]
}
private var rover: Int = -1
/** Add entry `x` to set */
def addEntry(x: T): Unit = {
var h = index(hash(x))
var entry = table(h)
while (entry ne null) {
if (x equals entry) return
h = index(h + 1)
entry = table(h)
}
table(h) = x
used += 1
if (used > (table.length >> 2)) growTable()
}
/** Add all entries in `xs` to set */
def addEntries(xs: TraversableOnce[T]): Unit = {
xs foreach addEntry
}
/** The iterator of all elements in the set */
def iterator = new Iterator[T] {
private var i = 0
def hasNext: Boolean = {
while (i < table.length && (table(i) eq null)) i += 1
i < table.length
}
def next(): T =
if (hasNext) { i += 1; table(i - 1).asInstanceOf[T] }
else null
}
/** Privileged access: Find first entry with given hashcode */
protected def findEntryByHash(hashCode: Int): T = {
rover = index(hashCode)
nextEntryByHash(hashCode)
}
/** Privileged access: Find next entry with given hashcode. Needs to immediately
* follow a `findEntryByhash` or `nextEntryByHash` operation.
*/
protected def nextEntryByHash(hashCode: Int): T = {
var entry = table(rover)
while (entry ne null) {
rover = index(rover + 1)
if (hash(entry.asInstanceOf[T]) == hashCode) return entry.asInstanceOf[T]
entry = table(rover)
}
null
}
/** Privileged access: Add entry `x` at the last position where an unsuccsessful
* `findEntryByHash` or `nextEntryByhash` operation returned. Needs to immediately
* follow a `findEntryByhash` or `nextEntryByHash` operation that was unsucessful,
* i.e. that returned `null`.
*/
protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x)
private def addOldEntry(x: T): Unit = {
var h = index(hash(x))
var entry = table(h)
while (entry ne null) {
h = index(h + 1)
entry = table(h)
}
table(h) = x
}
private def growTable(): Unit = {
val oldtable = table
allocate(table.length * 2)
var i = 0
while (i < oldtable.length) {
val entry = oldtable(i)
if (entry ne null) addOldEntry(entry.asInstanceOf[T])
i += 1
}
}
override def toString() = "HashSet(%d / %d)".format(used, table.length)
}
|
