{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}
{-# OPTIONS_GHC -Wall #-}
module Data.Primitive.Sort
(
sort
, sortUnique
, sortTagged
, sortUniqueTagged
, sortMutable
, sortUniqueMutable
, sortTaggedMutable
, sortUniqueTaggedMutable
) where
import Control.Monad.ST
import Control.Applicative
import GHC.ST (ST(..))
import GHC.IO (IO(..))
import GHC.Int (Int(..))
import Control.Monad
import GHC.Prim
import Control.Concurrent (getNumCapabilities)
import Data.Primitive.Contiguous (Contiguous,Mutable,Element)
import qualified Data.Primitive.Contiguous as C
sort :: (Contiguous arr, Element arr a, Ord a)
=> arr a
-> arr a
{-# INLINABLE sort #-}
sort !src = runST $ do
let len = C.size src
dst <- C.new (C.size src)
C.copy dst 0 src 0 len
res <- sortMutable dst
C.unsafeFreeze res
sortTagged :: forall k v karr varr. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> karr k
-> varr v
-> (karr k,varr v)
{-# INLINABLE sortTagged #-}
sortTagged !src !srcTags = runST $ do
let len = min (C.size src) (C.size srcTags)
dst <- C.new len
C.copy dst 0 src 0 len
dstTags <- C.new len
C.copy dstTags 0 srcTags 0 len
(res,resTags) <- sortTaggedMutableN len dst dstTags
res' <- C.unsafeFreeze res
resTags' <- C.unsafeFreeze resTags
return (res',resTags')
sortUniqueTagged :: forall k v karr varr. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> karr k
-> varr v
-> (karr k,varr v)
{-# INLINABLE sortUniqueTagged #-}
sortUniqueTagged !src !srcTags = runST $ do
let len = min (C.size src) (C.size srcTags)
dst <- C.new len
C.copy dst 0 src 0 len
dstTags <- C.new len
C.copy dstTags 0 srcTags 0 len
(res0,resTags0) <- sortTaggedMutableN len dst dstTags
(res1,resTags1) <- uniqueTaggedMutableN len res0 resTags0
res' <- C.unsafeFreeze res1
resTags' <- C.unsafeFreeze resTags1
return (res',resTags')
sortMutable :: (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a
-> ST s (Mutable arr s a)
{-# INLINABLE sortMutable #-}
sortMutable !dst = do
len <- C.sizeMutable dst
if len < threshold
then insertionSortRange dst 0 len
else do
work <- C.new len
C.copyMutable work 0 dst 0 len
caps <- unsafeEmbedIO getNumCapabilities
let minElemsPerThread = 20000
maxThreads = unsafeQuot len minElemsPerThread
preThreads = min caps maxThreads
threads = if preThreads == 1 then 1 else preThreads * 8
splitMergeParallel dst work threads 0 len
return dst
sortTaggedMutable :: (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable varr s v
-> ST s (Mutable karr s k, Mutable varr s v)
{-# INLINABLE sortTaggedMutable #-}
sortTaggedMutable !dst0 !dstTags0 = do
(!dst,!dstTags,!len) <- alignArrays dst0 dstTags0
sortTaggedMutableN len dst dstTags
alignArrays :: (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable varr s v
-> ST s (Mutable karr s k, Mutable varr s v,Int)
{-# INLINABLE alignArrays #-}
alignArrays dst0 dstTags0 = do
lenDst <- C.sizeMutable dst0
lenDstTags <- C.sizeMutable dstTags0
if lenDst == lenDstTags
then return (dst0,dstTags0,lenDst)
else if lenDst < lenDstTags
then do
dstTags <- C.resize dstTags0 lenDst
return (dst0,dstTags,lenDst)
else do
dst <- C.resize dst0 lenDstTags
return (dst,dstTags0,lenDstTags)
sortUniqueTaggedMutable :: (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable varr s v
-> ST s (Mutable karr s k, Mutable varr s v)
{-# INLINABLE sortUniqueTaggedMutable #-}
sortUniqueTaggedMutable dst0 dstTags0 = do
(!dst1,!dstTags1,!len) <- alignArrays dst0 dstTags0
(!dst2,!dstTags2) <- sortTaggedMutableN len dst1 dstTags1
uniqueTaggedMutableN len dst2 dstTags2
sortTaggedMutableN :: (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Int
-> Mutable karr s k
-> Mutable varr s v
-> ST s (Mutable karr s k, Mutable varr s v)
{-# INLINABLE sortTaggedMutableN #-}
sortTaggedMutableN !len !dst !dstTags = if len < thresholdTagged
then do
insertionSortTaggedRange dst dstTags 0 len
return (dst,dstTags)
else do
work <- C.cloneMutable dst 0 len
workTags <- C.cloneMutable dstTags 0 len
caps <- unsafeEmbedIO getNumCapabilities
let minElemsPerThread = 20000
maxThreads = unsafeQuot len minElemsPerThread
preThreads = min caps maxThreads
threads = if preThreads == 1 then 1 else preThreads * 8
splitMergeParallelTagged dst work dstTags workTags threads 0 len
return (dst,dstTags)
sortUnique :: (Contiguous arr, Element arr a, Ord a)
=> arr a -> arr a
{-# INLINABLE sortUnique #-}
sortUnique src = runST $ do
let len = C.size src
dst <- C.new len
C.copy dst 0 src 0 len
res <- sortUniqueMutable dst
C.unsafeFreeze res
sortUniqueMutable :: (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a
-> ST s (Mutable arr s a)
{-# INLINABLE sortUniqueMutable #-}
sortUniqueMutable marr = do
res <- sortMutable marr
uniqueMutable res
uniqueMutable :: forall arr s a. (Contiguous arr, Element arr a, Eq a)
=> Mutable arr s a -> ST s (Mutable arr s a)
{-# INLINABLE uniqueMutable #-}
uniqueMutable !marr = do
!len <- C.sizeMutable marr
if len > 1
then do
!a0 <- C.read marr 0
let findFirstDuplicate :: a -> Int -> ST s Int
findFirstDuplicate !prev !ix = if ix < len
then do
a <- C.read marr ix
if a == prev
then return ix
else findFirstDuplicate a (ix + 1)
else return ix
dupIx <- findFirstDuplicate a0 1
if dupIx == len
then return marr
else do
let deduplicate :: a -> Int -> Int -> ST s Int
deduplicate !prev !srcIx !dstIx = if srcIx < len
then do
a <- C.read marr srcIx
if a == prev
then deduplicate a (srcIx + 1) dstIx
else do
C.write marr dstIx a
deduplicate a (srcIx + 1) (dstIx + 1)
else return dstIx
!a <- C.read marr dupIx
!reducedLen <- deduplicate a (dupIx + 1) dupIx
C.resize marr reducedLen
else return marr
uniqueTaggedMutableN :: forall karr varr s k v. (Contiguous karr, Element karr k, Eq k, Contiguous varr, Element varr v)
=> Int
-> Mutable karr s k
-> Mutable varr s v
-> ST s (Mutable karr s k, Mutable varr s v)
{-# INLINABLE uniqueTaggedMutableN #-}
uniqueTaggedMutableN !len !marr !marrTags = if len > 1
then do
!a0 <- C.read marr 0
let findFirstDuplicate :: k -> Int -> ST s Int
findFirstDuplicate !prev !ix = if ix < len
then do
a <- C.read marr ix
if a == prev
then return ix
else findFirstDuplicate a (ix + 1)
else return ix
dupIx <- findFirstDuplicate a0 1
if dupIx == len
then return (marr,marrTags)
else do
C.read marrTags dupIx >>= C.write marrTags (dupIx - 1)
let deduplicate :: k -> Int -> Int -> ST s Int
deduplicate !prev !srcIx !dstIx = if srcIx < len
then do
a <- C.read marr srcIx
if a == prev
then do
C.read marrTags srcIx >>= C.write marrTags (dstIx - 1)
deduplicate a (srcIx + 1) dstIx
else do
C.read marrTags srcIx >>= C.write marrTags dstIx
C.write marr dstIx a
deduplicate a (srcIx + 1) (dstIx + 1)
else return dstIx
!a <- C.read marr dupIx
!reducedLen <- deduplicate a (dupIx + 1) dupIx
liftA2 (,) (C.resize marr reducedLen) (C.resize marrTags reducedLen)
else return (marr,marrTags)
unsafeEmbedIO :: IO a -> ST s a
unsafeEmbedIO (IO f) = ST (unsafeCoerce# f)
half :: Int -> Int
half x = unsafeQuot x 2
splitMergeParallel :: forall arr s a. (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a
-> Mutable arr s a
-> Int
-> Int
-> Int
-> ST s ()
{-# INLINABLE splitMergeParallel #-}
splitMergeParallel !arr !work !level !start !end = if level > 1
then if end - start < threshold
then insertionSortRange arr start end
else do
let !mid = unsafeQuot (end + start) 2
!levelDown = half level
tandem
(splitMergeParallel work arr levelDown start mid)
(splitMergeParallel work arr levelDown mid end)
mergeParallel work arr level start mid end
else splitMerge arr work start end
splitMergeParallelTagged :: forall karr varr s k v. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable karr s k
-> Mutable varr s v
-> Mutable varr s v
-> Int
-> Int
-> Int
-> ST s ()
{-# INLINABLE splitMergeParallelTagged #-}
splitMergeParallelTagged !arr !work !arrTags !workTags !level !start !end = if level > 1
then do
let !mid = unsafeQuot (end + start) 2
!levelDown = half level
tandem
(splitMergeParallelTagged work arr workTags arrTags levelDown start mid)
(splitMergeParallelTagged work arr workTags arrTags levelDown mid end)
mergeParallelTagged work arr workTags arrTags level start mid end
else splitMergeTagged arr work arrTags workTags start end
splitMerge :: forall arr s a. (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a
-> Mutable arr s a
-> Int
-> Int
-> ST s ()
{-# INLINABLE splitMerge #-}
splitMerge !arr !work !start !end = if end - start < 2
then return ()
else if end - start > threshold
then do
let !mid = unsafeQuot (end + start) 2
splitMerge work arr start mid
splitMerge work arr mid end
mergeNonContiguous work arr start mid mid end start
else insertionSortRange arr start end
splitMergeTagged :: (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable karr s k
-> Mutable varr s v
-> Mutable varr s v
-> Int
-> Int
-> ST s ()
{-# INLINABLE splitMergeTagged #-}
splitMergeTagged !arr !work !arrTags !workTags !start !end = if end - start < 2
then return ()
else if end - start > thresholdTagged
then do
let !mid = unsafeQuot (end + start) 2
splitMergeTagged work arr workTags arrTags start mid
splitMergeTagged work arr workTags arrTags mid end
mergeNonContiguousTagged work arr workTags arrTags start mid mid end start
else insertionSortTaggedRange arr arrTags start end
mergeParallel :: forall arr s a. (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a
-> Mutable arr s a
-> Int
-> Int
-> Int
-> Int
-> ST s ()
{-# INLINABLE mergeParallel #-}
mergeParallel !src !dst !threads !start !mid !end = do
!lock <- newLock
let go :: Int
-> Int
-> Int
-> ST s Int
go !prevEndA !prevEndB !ix =
if | prevEndA == mid && prevEndB == end -> return ix
| prevEndA == mid -> do
forkST_ $ do
let !startA = mid
!endA = mid
!startB = prevEndB
!endB = end
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguous src dst startA endA startB endB startDst
putLock lock
go mid end (ix + 1)
| prevEndB == end -> do
forkST_ $ do
let !startA = prevEndA
!endA = mid
!startB = end
!endB = end
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguous src dst startA endA startB endB startDst
putLock lock
go mid end (ix + 1)
| ix == threads - 1 -> do
forkST_ $ do
let !startA = prevEndA
!endA = mid
!startB = prevEndB
!endB = end
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguous src dst startA endA startB endB startDst
putLock lock
return (ix + 1)
| otherwise -> do
!endElem <- C.read src (start + chunk * (ix + 1))
!endA <- findIndexOfGtElem src (endElem :: a) prevEndA mid
!endB <- findIndexOfGtElem src endElem prevEndB end
forkST_ $ do
let !startA = prevEndA
!startB = prevEndB
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguous src dst startA endA startB endB startDst
putLock lock
go endA endB (ix + 1)
!endElem <- C.read src (start + chunk)
!endA <- findIndexOfGtElem src (endElem :: a) start mid
!endB <- findIndexOfGtElem src endElem mid end
forkST_ $ do
let !startA = start
!startB = mid
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguous src dst startA endA startB endB startDst
putLock lock
total <- go endA endB 1
replicateM_ total (takeLock lock)
where
!chunk = unsafeQuot (end - start) threads
mergeParallelTagged :: forall karr varr s k v. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable karr s k
-> Mutable varr s v
-> Mutable varr s v
-> Int
-> Int
-> Int
-> Int
-> ST s ()
{-# INLINABLE mergeParallelTagged #-}
mergeParallelTagged !src !dst !srcTags !dstTags !threads !start !mid !end = do
!lock <- newLock
let go :: Int
-> Int
-> Int
-> ST s Int
go !prevEndA !prevEndB !ix =
if | prevEndA == mid && prevEndB == end -> return ix
| prevEndA == mid -> do
forkST_ $ do
let !startA = mid
!endA = mid
!startB = prevEndB
!endB = end
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguousTagged src dst srcTags dstTags startA endA startB endB startDst
putLock lock
go mid end (ix + 1)
| prevEndB == end -> do
forkST_ $ do
let !startA = prevEndA
!endA = mid
!startB = end
!endB = end
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguousTagged src dst srcTags dstTags startA endA startB endB startDst
putLock lock
go mid end (ix + 1)
| ix == threads - 1 -> do
forkST_ $ do
let !startA = prevEndA
!endA = mid
!startB = prevEndB
!endB = end
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguousTagged src dst srcTags dstTags startA endA startB endB startDst
putLock lock
return (ix + 1)
| otherwise -> do
!endElem <- C.read src (start + chunk * (ix + 1))
!endA <- findIndexOfGtElem src (endElem :: k) prevEndA mid
!endB <- findIndexOfGtElem src endElem prevEndB end
forkST_ $ do
let !startA = prevEndA
!startB = prevEndB
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguousTagged src dst srcTags dstTags startA endA startB endB startDst
putLock lock
go endA endB (ix + 1)
!endElem <- C.read src (start + chunk)
!endA <- findIndexOfGtElem src (endElem :: k) start mid
!endB <- findIndexOfGtElem src endElem mid end
forkST_ $ do
let !startA = start
!startB = mid
!startDst = (startA - start) + (startB - mid) + start
mergeNonContiguousTagged src dst srcTags dstTags startA endA startB endB startDst
putLock lock
total <- go endA endB 1
replicateM_ total (takeLock lock)
where
!chunk = unsafeQuot (end - start) threads
unsafeQuot :: Int -> Int -> Int
unsafeQuot (I# a) (I# b) = I# (quotInt# a b)
findIndexOfGtElem :: forall arr s a. (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a -> a -> Int -> Int -> ST s Int
{-# INLINABLE findIndexOfGtElem #-}
findIndexOfGtElem !v !needle !start !end = go start end
where
go :: Int -> Int -> ST s Int
go !lo !hi = if lo < hi
then do
let !mid = lo + half (hi - lo)
!val <- C.read v mid
if | val == needle -> gallopToGtIndex v needle (mid + 1) hi
| val < needle -> go (mid + 1) hi
| otherwise -> go lo mid
else return lo
gallopToGtIndex :: forall arr s a. (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a -> a -> Int -> Int -> ST s Int
{-# INLINABLE gallopToGtIndex #-}
gallopToGtIndex !v !val !start !end = go start
where
go :: Int -> ST s Int
go !ix = if ix < end
then do
!a <- C.read v ix
if a > val
then return ix
else go (ix + 1)
else return end
mergeNonContiguous :: forall arr s a. (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a
-> Mutable arr s a
-> Int
-> Int
-> Int
-> Int
-> Int
-> ST s ()
{-# INLINABLE mergeNonContiguous #-}
mergeNonContiguous !src !dst !startA !endA !startB !endB !startDst =
if startB < endB
then stepA startA startB startDst
else if startA < endA
then stepB startA startB startDst
else return ()
where
continue :: Int -> Int -> Int -> ST s ()
continue ixA ixB ixDst = do
!a <- C.read src ixA
!b <- C.read src ixB
if (a :: a) <= b
then do
C.write dst ixDst a
stepA (ixA + 1) ixB (ixDst + 1)
else do
C.write dst ixDst b
stepB ixA (ixB + 1) (ixDst + 1)
stepB :: Int -> Int -> Int -> ST s ()
stepB !ixA !ixB !ixDst = if ixB < endB
then continue ixA ixB ixDst
else finishA ixA ixDst
stepA :: Int -> Int -> Int -> ST s ()
stepA !ixA !ixB !ixDst = if ixA < endA
then continue ixA ixB ixDst
else finishB ixB ixDst
finishB :: Int -> Int -> ST s ()
finishB !ixB !ixDst = C.copyMutable dst ixDst src ixB (endB - ixB)
finishA :: Int -> Int -> ST s ()
finishA !ixA !ixDst = C.copyMutable dst ixDst src ixA (endA - ixA)
mergeNonContiguousTagged :: forall karr varr k v s. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable karr s k
-> Mutable varr s v
-> Mutable varr s v
-> Int
-> Int
-> Int
-> Int
-> Int
-> ST s ()
{-# INLINABLE mergeNonContiguousTagged #-}
mergeNonContiguousTagged !src !dst !srcTags !dstTags !startA !endA !startB !endB !startDst =
if startB < endB
then stepA startA startB startDst
else if startA < endA
then stepB startA startB startDst
else return ()
where
continue :: Int -> Int -> Int -> ST s ()
continue ixA ixB ixDst = do
!a <- C.read src ixA
!b <- C.read src ixB
if a <= b
then do
C.write dst ixDst a
(C.read srcTags ixA :: ST s v) >>= C.write dstTags ixDst
stepA (ixA + 1) ixB (ixDst + 1)
else do
C.write dst ixDst b
(C.read srcTags ixB :: ST s v) >>= C.write dstTags ixDst
stepB ixA (ixB + 1) (ixDst + 1)
stepB :: Int -> Int -> Int -> ST s ()
stepB !ixA !ixB !ixDst = if ixB < endB
then continue ixA ixB ixDst
else finishA ixA ixDst
stepA :: Int -> Int -> Int -> ST s ()
stepA !ixA !ixB !ixDst = if ixA < endA
then continue ixA ixB ixDst
else finishB ixB ixDst
finishB :: Int -> Int -> ST s ()
finishB !ixB !ixDst = do
C.copyMutable dst ixDst src ixB (endB - ixB)
C.copyMutable dstTags ixDst srcTags ixB (endB - ixB)
finishA :: Int -> Int -> ST s ()
finishA !ixA !ixDst = do
C.copyMutable dst ixDst src ixA (endA - ixA)
C.copyMutable dstTags ixDst srcTags ixA (endA - ixA)
threshold :: Int
threshold = 16
thresholdTagged :: Int
thresholdTagged = 16
insertionSortRange :: forall arr s a. (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a
-> Int
-> Int
-> ST s ()
{-# INLINABLE insertionSortRange #-}
insertionSortRange !arr !start !end = go start
where
go :: Int -> ST s ()
go !ix = if ix < end
then do
!a <- C.read arr ix
insertElement arr (a :: a) start ix
go (ix + 1)
else return ()
insertElement :: forall arr s a. (Contiguous arr, Element arr a, Ord a)
=> Mutable arr s a
-> a
-> Int
-> Int
-> ST s ()
{-# INLINABLE insertElement #-}
insertElement !arr !a !start !end = go end
where
go :: Int -> ST s ()
go !ix = if ix > start
then do
!b <- C.read arr (ix - 1)
if b <= a
then do
C.copyMutable arr (ix + 1) arr ix (end - ix)
C.write arr ix a
else go (ix - 1)
else do
C.copyMutable arr (ix + 1) arr ix (end - ix)
C.write arr ix a
insertionSortTaggedRange :: forall karr varr s k v. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable varr s v
-> Int
-> Int
-> ST s ()
{-# INLINABLE insertionSortTaggedRange #-}
insertionSortTaggedRange !karr !varr !start !end = go start
where
go :: Int -> ST s ()
go !ix = if ix < end
then do
!a <- C.read karr ix
!v <- C.read varr ix
insertElementTagged karr varr a v start ix
go (ix + 1)
else return ()
insertElementTagged :: forall karr varr s k v. (Contiguous karr, Element karr k, Ord k, Contiguous varr, Element varr v)
=> Mutable karr s k
-> Mutable varr s v
-> k
-> v
-> Int
-> Int
-> ST s ()
{-# INLINABLE insertElementTagged #-}
insertElementTagged !karr !varr !a !v !start !end = go end
where
go :: Int -> ST s ()
go !ix = if ix > start
then do
!b <- C.read karr (ix - 1)
if b <= a
then do
C.copyMutable karr (ix + 1) karr ix (end - ix)
C.write karr ix a
C.copyMutable varr (ix + 1) varr ix (end - ix)
C.write varr ix v
else go (ix - 1)
else do
C.copyMutable karr (ix + 1) karr ix (end - ix)
C.write karr ix a
C.copyMutable varr (ix + 1) varr ix (end - ix)
C.write varr ix v
forkST_ :: ST s a -> ST s ()
forkST_ action = ST $ \s1 -> case forkST# action s1 of
(# s2, _ #) -> (# s2, () #)
forkST# :: a -> State# s -> (# State# s, ThreadId# #)
forkST# = unsafeCoerce# fork#
data Lock s = Lock (MVar# s ())
newLock :: ST s (Lock s)
newLock = ST $ \s1 -> case newMVar# s1 of
(# s2, v #) -> (# s2, Lock v #)
takeLock :: Lock s -> ST s ()
takeLock (Lock mvar#) = ST $ \ s# -> takeMVar# mvar# s#
putLock :: Lock s -> ST s ()
putLock (Lock mvar#) = ST $ \ s# ->
case putMVar# mvar# () s# of
s2# -> (# s2#, () #)
tandem :: ST s () -> ST s () -> ST s ()
tandem a b = do
lock <- newLock
forkST_ (b >> putLock lock)
a
takeLock lock