Created
May 10, 2021 13:10
-
-
Save vlsi/68851c8dda894915a7855b7b06229d33 to your computer and use it in GitHub Desktop.
A translation of OpenJDK's ConcurrentHashMap to Kotlin
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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