Advertisement
EeZotop

Untitled

Jan 22nd, 2022
1,112
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import kotlinx.atomicfu.*
  2.  
  3. class DynamicArrayImpl<E> : DynamicArray<E> {
  4.     private class Moved<E>(el: E) {
  5.         val elem = el
  6.     }
  7.  
  8.     private val core = atomic(Core(INITIAL_CAPACITY))
  9.     private val prepared = atomic<Core?>(null)
  10.  
  11.     override fun get(index: Int): E {
  12.         val currCore = core.value
  13.         if (index >= currCore.size.value) {
  14.             throw IndexOutOfBoundsException()
  15.         }
  16.  
  17.         val currElem = currCore.array[index].value!!
  18.  
  19.         @Suppress("UNCHECKED_CAST")
  20.         return when (currElem) {
  21.             is Moved<*> -> currElem.elem!!
  22.             else -> currElem
  23.         } as E
  24.     }
  25.  
  26.     override fun put(index: Int, element: E) {
  27.         while (true) {
  28.             val currCore = core.value
  29.             val currSize = currCore.size.value
  30.             if (index >= currSize) {
  31.                 throw IndexOutOfBoundsException()
  32.             }
  33.  
  34.             val currElem = currCore.array[index].value
  35.             if (currElem == null && currCore.array[index].compareAndSet(null, element)) {
  36.                 return
  37.             }
  38.         }
  39.     }
  40.  
  41.     override fun pushBack(element: E) {
  42.         wholeThing@ while (true) {
  43.             val currCore = core.value
  44.  
  45.             addingToLast@ while (true) {
  46.                 val currSize = currCore.size.value
  47.                 if (currSize < currCore.array.size) {
  48.                     if (currCore.array[currSize].compareAndSet(null, element)) {
  49.                         currCore.size.getAndIncrement()
  50.                         return
  51.                     } else {
  52.                         val currVal = currCore.array[currSize].value
  53.                         if (currVal is Moved<*>) {
  54.                             // someone else started moving array and stolen this element
  55.                             continue@wholeThing
  56.                         } else {
  57.                             // someone inserted an element here
  58.                             continue@addingToLast
  59.                         }
  60.                     }
  61.                 } else { // currSize == currCore.array.size
  62.                     resize(currCore.array.size * 2)
  63.                     continue@wholeThing
  64.                 }
  65.             }
  66.         }
  67.     }
  68.  
  69.     override val size: Int
  70.         get() {
  71.             return core.value.size.value
  72.         }
  73.  
  74.  
  75.     private fun resize(wishedCap: Int) {
  76.         while (true) {
  77.             val currCore = core.value
  78.             if (currCore.array.size >= wishedCap) {
  79.                 return
  80.             }
  81.  
  82.             val nextCore = prepared.value
  83.             if (nextCore != null) {
  84.                 moveValues(currCore, nextCore)
  85.             } else {
  86.                 val createdCore = Core(wishedCap, currCore.array.size)
  87.                 if (prepared.compareAndSet(null, createdCore)) {
  88.                     moveValues(currCore, createdCore)
  89.                     return
  90.                 }
  91.             }
  92.         }
  93.     }
  94.  
  95.     private fun moveValues(from: Core, to: Core) {
  96.         val fromArr = from.array
  97.         val toArr = to.array
  98.  
  99.         for (i in 0 until fromArr.size) {
  100.             val currElem = fromArr[i].value
  101.             fromArr[i].compareAndSet(currElem, Moved(currElem))
  102.             if (currElem != null) {
  103.                 toArr[i].compareAndSet(null, currElem)
  104.             }
  105.         }
  106.     }
  107. }
  108.  
  109. private class Core(capacity: Int, reservedSize: Int = 0) {
  110.     val array = atomicArrayOfNulls<Any>(capacity)
  111.     val size = atomic(reservedSize)
  112. }
  113.  
  114. private const val INITIAL_CAPACITY = 1 // DO NOT CHANGE ME
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement