Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import kotlinx.atomicfu.*
- class DynamicArrayImpl<E> : DynamicArray<E> {
- interface Node<E> {
- interface WithValue<E> : Node<E> {
- val value: E
- }
- class Normal<E>(override val value: E) : WithValue<E>
- class CopyInProgress<E>(override val value: E) : WithValue<E>
- class CopyComplete<E>() : Node<E>
- }
- private class Core<E>(val capacity: Int) {
- val array = atomicArrayOfNulls<Node<E>>(capacity)
- val next: AtomicRef<Core<E>?> = atomic(null)
- val leftToCopy = atomic(capacity)
- fun getOrCreateNext(): Core<E> {
- val oldValue = next.value
- if (oldValue == null) {
- next.compareAndSet(null, Core(capacity * GROW_FACTOR))
- }
- // CAS should finish with success, in this or other thread
- return next.value!!
- }
- }
- companion object {
- private const val GROW_FACTOR = 2
- private const val INITIAL_CAPACITY = 1 // DO NOT CHANGE ME - OK, NOT CHANGED!
- }
- private val core = atomic(Core<E>(INITIAL_CAPACITY))
- private val sizeVal: AtomicInt = atomic(0)
- override fun get(index: Int): E {
- require(0 <= index && index < sizeVal.value)
- // Yes, we can return value from [Node.CopyInProgress],
- // but let's help other threads to finish copy to new core operation
- return doActionOnNormalNode(index) { _, node -> node.value }
- }
- override fun put(index: Int, element: E) {
- require(0 <= index && index < sizeVal.value)
- doActionOnNormalNode(index) { core, normal ->
- when (core.array[index].compareAndSet(normal, Node.Normal(element))) {
- true -> true // Stop retrying CAS - we're done
- false -> null // CAS failed, retry
- }
- }
- }
- override fun pushBack(element: E) {
- var currentCore = tryRemoveCopiedCores()
- while (true) {
- currentCore = skipCopiedCores(currentCore)
- val currentSize = size
- if (currentSize >= currentCore.capacity) {
- currentCore = buildNextCore(currentCore)
- continue
- }
- if (!currentCore.array[currentSize].compareAndSet(null, Node.Normal(element))) {
- continue
- }
- sizeVal.incrementAndGet()
- return
- }
- }
- override val size: Int
- get() = sizeVal.value
- private fun buildNextCore(fromCore: Core<E>): Core<E> {
- val nextCore = fromCore.getOrCreateNext()
- // Copy elements to new core
- for (i in 0 until fromCore.capacity) {
- // Ignore nulls
- var node = fromCore.array[i].value!!
- // Mark existing core values with "Copy in progress"
- retryMarkAsInProgress@ while (node is Node.Normal) {
- if (fromCore.array[i].compareAndSet(node, Node.CopyInProgress(node.value))) {
- break@retryMarkAsInProgress
- }
- node = fromCore.array[i].value!!
- }
- // Nothing to do if node already copied
- if (node is Node.CopyComplete) {
- continue
- }
- // If node is marked with "Copy in progress", try to copy it to new core
- val value = (node as Node.WithValue).value
- if (nextCore.array[i].value != null || nextCore.array[i].compareAndSet(null, Node.Normal(value))) {
- // If copy complete, we can release this node in old core
- fromCore.array[i].compareAndSet(node, Node.CopyComplete())
- fromCore.leftToCopy.decrementAndGet()
- }
- }
- return nextCore
- }
- /**
- * Retries to perform [action] on actual `Normal` node on [index],
- * stops iterating when [action] retries non-null value.
- * A short way to find node in the correct core and process it
- */
- private fun <R> doActionOnNormalNode(index: Int, action: (Core<E>, Node.Normal<E>) -> R?): R {
- var currentCore = tryRemoveCopiedCores()
- while (true) {
- currentCore = skipCopiedCores(currentCore)
- if (index >= currentCore.capacity) {
- currentCore = currentCore.next.value!!
- continue
- }
- val node = currentCore.array[index].value ?: continue
- if (node is Node.Normal) {
- return action(currentCore, node) ?: continue
- } else if (node is Node.CopyInProgress) {
- buildNextCore(currentCore)
- } else {
- currentCore = currentCore.next.value!!
- }
- }
- }
- private fun tryRemoveCopiedCores(): Core<E> {
- var currentCore = core.value
- while (currentCore.leftToCopy.value == 0) {
- val nextNode = currentCore.next.value!!
- if (!core.compareAndSet(currentCore, nextNode)) {
- return currentCore
- }
- currentCore = nextNode
- }
- return currentCore
- }
- private fun skipCopiedCores(fromCore: Core<E>): Core<E> {
- var temp = fromCore
- while (temp.leftToCopy.value == 0) {
- temp = temp.next.value!!
- }
- return temp
- }
- }
Add Comment
Please, Sign In to add comment