gale client

root / CircularBuffer.hs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
{-# LANGUAGE ParallelListComp, PatternGuards, FlexibleContexts #-}
module CircularBuffer(
    CircularBuffer,
    new,
    get,
    append,
    toList,
    CircularBuffer.length
    ) where

import Control.Concurrent
import Data.Array.IO

data Meta = Full {-# UNPACK #-} !Int | Partial {-# UNPACK #-} !Int
data CircularBuffer e = CB { arr :: !(IOArray Int e), mvar :: !(MVar Meta)}
--    FullCB    { start :: !Int, arr ::  }
--    | PartialCB { len :: !Int, arr :: !(IOArray Int e) }

new :: Int -> IO (CircularBuffer a)
new s | s < 1 = fail "cannot create that small of a circular buffer"
new s = do
    a <- newArray_ (0,s - 1)
    m <- newMVar $ Partial 0
    return CB { mvar = m,  arr = a }

get :: CircularBuffer a -> Int -> IO a
get CB { arr = arr, mvar = mvar} w = withMVar mvar go where
    go (Partial 0) = fail "attempt to read empty CircularBuffer"
    go (Partial len) = do
        let m = w `mod` len
            w' = if m < 0 then m + len else m
        readArray arr w'
    go (Full start) = do
        bnds <- getBounds arr
        let m = (w + start) `mod` len
            w' = if m < 0 then m + len else m
            len = snd bnds + 1
        readArray arr w'

length :: CircularBuffer a -> IO Int
length CB { arr = arr, mvar = mvar} = withMVar mvar go where
    go (Full _) = do
        bnds <- getBounds arr
        return $ (snd bnds) + 1
    go (Partial len) = return len

append :: CircularBuffer a -> [a] -> IO ()
append CB {arr = arr, mvar = mvar} xs = do
    bnds <- getBounds arr
    let alen = snd bnds + 1
        xslen = Prelude.length xs
        go _ | xslen >= alen = do
            sequence_ [writeArray arr i e | i <- [0..] | e <- (drop $ xslen - alen) xs  ]
            return (Full 0)
        go (Full start) = do
            let nstart = (start + xslen) `mod` alen
            sequence_ [writeArray arr (i `mod` alen) e | i <- [start..] | e <-  xs  ]
            return (Full nstart)
        go (Partial len) | len + xslen ==  alen = do
            sequence_ [writeArray arr i e | i <- [len..] | e <-  xs  ]
            return (Full 0)
        go (Partial len) | nlen <- len + xslen, nlen < alen = do
            sequence_ [writeArray arr i e | i <- [len..] | e <-  xs  ]
            return (Partial nlen)
        go (Partial len)  = do
            sequence_ [writeArray arr (i `mod` alen) e | i <- [len..] | e <-  xs  ]
            return (Full (xslen + len - alen))
    modifyMVar_ mvar go



--prepend :: CircularBuffer a -> [a] -> IO ()

toList :: CircularBuffer a -> IO [a]
toList CB { arr = arr, mvar = mvar} = withMVar mvar go where
    go (Partial len) = do
        es <- getElems arr
        return (take len es)
    go (Full start) = do
        es <- getElems arr
        let (a,b) = splitAt start es
        return (b ++ a)

--first cb = read cb 0
--last cb = read cb -1