-
Notifications
You must be signed in to change notification settings - Fork 1k
/
DefaultPool.kt
113 lines (92 loc) · 3.63 KB
/
DefaultPool.kt
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
package io.ktor.utils.io.pool
import io.ktor.utils.io.utils.*
import java.util.concurrent.atomic.*
import kotlin.jvm.*
private const val MULTIPLIER = 4
// number of attempts to find a slot
private const val PROBE_COUNT = 8
// fractional part of golden ratio
private const val MAGIC = 2654435769.toInt()
private const val MAX_CAPACITY = Int.MAX_VALUE / MULTIPLIER
public actual abstract class DefaultPool<T : Any>
actual constructor(actual final override val capacity: Int) : ObjectPool<T> {
init {
require(capacity > 0) { "capacity should be positive but it is $capacity" }
require(capacity <= MAX_CAPACITY) {
"capacity should be less or equal to $MAX_CAPACITY but it is $capacity"
}
}
// factory
protected actual abstract fun produceInstance(): T
// optional cleaning of popped items
protected actual open fun clearInstance(instance: T): T = instance
// optional validation for recycled items
protected actual open fun validateInstance(instance: T) {}
// optional destruction of unpoolable items
protected actual open fun disposeInstance(instance: T) {}
@Volatile
private var top: Long = 0L
// closest power of 2 that is equal or larger than capacity * MULTIPLIER
private val maxIndex = Integer.highestOneBit(capacity * MULTIPLIER - 1) * 2
// for hash function
private val shift = Integer.numberOfLeadingZeros(maxIndex) + 1
// zero index is reserved for both
private val instances = AtomicReferenceArray<T?>(maxIndex + 1)
private val next = IntArray(maxIndex + 1)
actual final override fun borrow(): T =
tryPop()?.let { clearInstance(it) } ?: produceInstance()
actual final override fun recycle(instance: T) {
validateInstance(instance)
if (!tryPush(instance)) disposeInstance(instance)
}
actual final override fun dispose() {
while (true) {
val instance = tryPop() ?: return
disposeInstance(instance)
}
}
private fun tryPush(instance: T): Boolean {
var index = ((System.identityHashCode(instance) * MAGIC) ushr shift) + 1
repeat(PROBE_COUNT) {
if (instances.compareAndSet(index, null, instance)) {
pushTop(index)
return true
}
if (--index == 0) index = maxIndex
}
return false
}
private fun tryPop(): T? {
val index = popTop()
return if (index == 0) null else instances.getAndSet(index, null)
}
private fun pushTop(index: Int) {
require(index > 0) { "index should be positive" }
while (true) { // lock-free loop on top
val top = this.top // volatile read
val topVersion = (top shr 32 and 0xffffffffL) + 1L
val topIndex = (top and 0xffffffffL).toInt()
val newTop = topVersion shl 32 or index.toLong()
next[index] = topIndex
if (Top.compareAndSet(this, top, newTop)) return
}
}
private fun popTop(): Int {
// lock-free loop on top
while (true) {
// volatile read
val top = this.top
if (top == 0L) return 0
val newVersion = (top shr 32 and 0xffffffffL) + 1L
val topIndex = (top and 0xffffffffL).toInt()
if (topIndex == 0) return 0
val next = next[topIndex]
val newTop = newVersion shl 32 or next.toLong()
if (Top.compareAndSet(this, top, newTop)) return topIndex
}
}
public companion object {
// todo: replace with atomicfu, remove companion object
private val Top = longUpdater(DefaultPool<*>::top)
}
}