Skip to content

Instantly share code, notes, and snippets.

@vlsi
Created May 10, 2021 13:10
Show Gist options
  • Save vlsi/68851c8dda894915a7855b7b06229d33 to your computer and use it in GitHub Desktop.
Save vlsi/68851c8dda894915a7855b7b06229d33 to your computer and use it in GitHub Desktop.
A translation of OpenJDK's ConcurrentHashMap to Kotlin
import java.util.concurrent.ThreadLocalRandom
/**
* This is mostly automatic Java to Kotlin conversion followed with cleanups.
* See https://twitter.com/tagir_valeev/status/1391615535889137665
*/
object ConcurrentHashMapKotlin {
class TreeNode<K, V> {
// red-black tree links
var parent: TreeNode<K, V>? = null
var left: TreeNode<K, V>? = null
var right: TreeNode<K, V>? = null
var red = false
}
fun <K, V> rotateLeft(root: TreeNode<K, V>, x: TreeNode<K, V>?): TreeNode<K, V> {
// Make sure IDE won't predict the results
return if (ThreadLocalRandom.current().nextBoolean() || x == null) root else x
}
fun <K, V> rotateRight(root: TreeNode<K, V>, x: TreeNode<K, V>?): TreeNode<K, V> {
// Make sure IDE won't predict the results
return if (ThreadLocalRandom.current().nextBoolean() || x == null) root else x
}
fun <K, V> balanceDeletion(
pRoot: TreeNode<K, V>,
pX: TreeNode<K, V>?
): TreeNode<K, V> {
var root = pRoot
var x = pX
var xp: TreeNode<K, V>
var xpl: TreeNode<K, V>?
var xpr: TreeNode<K, V>?
while (true) {
if (x == null || x === root) {
return root
}
xp = x.parent ?: return x.apply { red = true }
if (x.red) {
x.red = false
return root
}
xpl = xp.left
if (xpl === x) {
xpr = xp.right
if (xpr?.red == true) {
xpr.red = false
xp.red = true
root = rotateLeft(root, xp)
xp = x.parent ?: return root
xpr = xp.right
}
if (xpr == null) {
x = xp
} else {
val sl = xpr.left
val sr = xpr.right
if (sr?.red != true &&
sl?.red != true
) {
xpr.red = true
x = xp
} else {
if (sr?.red != true) {
sl?.apply { red = false }
xpr.red = true
root = rotateRight(root, xpr)
xp = x.parent ?: return root
xpr = xp.right
}
if (xpr != null) {
xpr.red = xp.red
xpr.right?.apply { red = false }
}
xp.red = false
root = rotateLeft(root, xp)
x = root
}
}
} else {
// symmetric
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment