    {-# LANGUAGE BangPatterns, MagicHash #-}
    {-# LANGUAGE CPP #-}
    #if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702
    {-# LANGUAGE Trustworthy #-}
    #endif
    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Data.CharSet.ByteSet
    -- Copyright   :  Edward Kmett 2011
    --                Bryan O'Sullivan 2008
    -- License     :  BSD3
    --
    -- Maintainer  :  ekmett@gmail.com
    -- Stability   :  experimental
    -- Portability :  non-portable (BangPatterns, MagicHash)
    --
    -- Fast set membership tests for byte values, The set representation is
    -- unboxed for efficiency and uses a lookup table. This is a fairly minimal
    -- API. You probably want to use CharSet.
    -----------------------------------------------------------------------------
    module Data.CharSet.ByteSet
        (
        -- * Data type
          ByteSet(..)
        -- * Construction
        , fromList
        -- * Lookup
        , member
        ) where

    import Data.Bits ((.&.), (.|.))
    import Foreign.Storable (peekByteOff, pokeByteOff)
    import GHC.Base (Int(I#), iShiftRA#, narrow8Word#, shiftL#)
    import GHC.Word (Word8(W8#))
    import qualified Data.ByteString as B
    import qualified Data.ByteString.Internal as I
    import qualified Data.ByteString.Unsafe as U

    newtype ByteSet = ByteSet B.ByteString deriving (ByteSet -> ByteSet -> Bool
    (ByteSet -> ByteSet -> Bool)
    -> (ByteSet -> ByteSet -> Bool) -> Eq ByteSet
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    /= :: ByteSet -> ByteSet -> Bool
    $c/= :: ByteSet -> ByteSet -> Bool
    == :: ByteSet -> ByteSet -> Bool
    $c== :: ByteSet -> ByteSet -> Bool
    Eq, Eq ByteSet
    Eq ByteSet =>
    (ByteSet -> ByteSet -> Ordering)
    -> (ByteSet -> ByteSet -> Bool)
    -> (ByteSet -> ByteSet -> Bool)
    -> (ByteSet -> ByteSet -> Bool)
    -> (ByteSet -> ByteSet -> Bool)
    -> (ByteSet -> ByteSet -> ByteSet)
    -> (ByteSet -> ByteSet -> ByteSet)
    -> Ord ByteSet
    ByteSet -> ByteSet -> Bool
    ByteSet -> ByteSet -> Ordering
    ByteSet -> ByteSet -> ByteSet
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    min :: ByteSet -> ByteSet -> ByteSet
    $cmin :: ByteSet -> ByteSet -> ByteSet
    max :: ByteSet -> ByteSet -> ByteSet
    $cmax :: ByteSet -> ByteSet -> ByteSet
    >= :: ByteSet -> ByteSet -> Bool
    $c>= :: ByteSet -> ByteSet -> Bool
    > :: ByteSet -> ByteSet -> Bool
    $c> :: ByteSet -> ByteSet -> Bool
    <= :: ByteSet -> ByteSet -> Bool
    $c<= :: ByteSet -> ByteSet -> Bool
    < :: ByteSet -> ByteSet -> Bool
    $c< :: ByteSet -> ByteSet -> Bool
    compare :: ByteSet -> ByteSet -> Ordering
    $ccompare :: ByteSet -> ByteSet -> Ordering
    $cp1Ord :: Eq ByteSet
    Ord, Int -> ByteSet -> ShowS
    [ByteSet] -> ShowS
    ByteSet -> String
    (Int -> ByteSet -> ShowS)
    -> (ByteSet -> String) -> ([ByteSet] -> ShowS) -> Show ByteSet
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    showList :: [ByteSet] -> ShowS
    $cshowList :: [ByteSet] -> ShowS
    show :: ByteSet -> String
    $cshow :: ByteSet -> String
    showsPrec :: Int -> ByteSet -> ShowS
    $cshowsPrec :: Int -> ByteSet -> ShowS
    Show)

    data I = I {-# UNPACK #-} !Int {-# UNPACK #-} !Word8

    shiftR :: Int -> Int -> Int
    shiftR :: Int -> Int -> Int
    shiftR (I# x# :: Int#
    x#) (I# i# :: Int#
    i#) = Int# -> Int
    I# (Int#
    x# Int# -> Int# -> Int#
    `iShiftRA#` Int#
    i#)

    shiftL :: Word8 -> Int -> Word8
    shiftL :: Word8 -> Int -> Word8
    shiftL (W8# x# :: Word#
    x#) (I# i# :: Int#
    i#) = Word# -> Word8
    W8# (Word# -> Word#
    narrow8Word# (Word#
    x# Word# -> Int# -> Word#
    `shiftL#` Int#
    i#))

    index :: Int -> I
    index :: Int -> I
    index i :: Int
    i = Int -> Word8 -> I
    I (Int
    i Int -> Int -> Int
    `shiftR` 3) (1 Word8 -> Int -> Word8
    `shiftL` (Int
    i Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. 7))
    {-# INLINE index #-}

    fromList :: [Word8] -> ByteSet
    fromList :: [Word8] -> ByteSet
    fromList s0 :: [Word8]
    s0 = ByteString -> ByteSet
    ByteSet (ByteString -> ByteSet) -> ByteString -> ByteSet
    forall a b. (a -> b) -> a -> b
    $ Int -> (Ptr Word8 -> IO ()) -> ByteString
    I.unsafeCreate 32 ((Ptr Word8 -> IO ()) -> ByteString)
    -> (Ptr Word8 -> IO ()) -> ByteString
    forall a b. (a -> b) -> a -> b
    $ \t :: Ptr Word8
    t -> do
      Ptr Word8
    _ <- Ptr Word8 -> Word8 -> CSize -> IO (Ptr Word8)
    I.memset Ptr Word8
    t 0 32
      let go :: [a] -> IO ()
    go [] = () -> IO ()
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
          go (c :: a
    c:cs :: [a]
    cs) = do
            Word8
    prev <- Ptr Word8 -> Int -> IO Word8
    forall a b. Storable a => Ptr b -> Int -> IO a
    peekByteOff Ptr Word8
    t Int
    byte :: IO Word8
            Ptr Word8 -> Int -> Word8 -> IO ()
    forall a b. Storable a => Ptr b -> Int -> a -> IO ()
    pokeByteOff Ptr Word8
    t Int
    byte (Word8
    prev Word8 -> Word8 -> Word8
    forall a. Bits a => a -> a -> a
    .|. Word8
    bit)
            [a] -> IO ()
    go [a]
    cs
            where I byte :: Int
    byte bit :: Word8
    bit = Int -> I
    index (a -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral a
    c)
      [Word8] -> IO ()
    forall a. Integral a => [a] -> IO ()
    go [Word8]
    s0

    -- | Check the set for membership.
    member :: Word8 -> ByteSet -> Bool
    member :: Word8 -> ByteSet -> Bool
    member w :: Word8
    w (ByteSet t :: ByteString
    t) = ByteString -> Int -> Word8
    U.unsafeIndex ByteString
    t Int
    byte Word8 -> Word8 -> Word8
    forall a. Bits a => a -> a -> a
    .&. Word8
    bit Word8 -> Word8 -> Bool
    forall a. Eq a => a -> a -> Bool
    /= 0
      where
        I byte :: Int
    byte bit :: Word8
    bit = Int -> I
    index (Word8 -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Word8
    w)