{-# LANGUAGE BangPatterns, MagicHash, TypeOperators #-}
module Data.BloomFilter.Util
(
FastShift(..)
, nextPowerOfTwo
, (:*)(..)
) where
import Data.Bits ((.|.))
import qualified Data.Bits as Bits
import GHC.Base
import GHC.Word
data a :* b = !a :* !b
deriving ((a :* b) -> (a :* b) -> Bool
((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> Bool) -> Eq (a :* b)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a b. (Eq a, Eq b) => (a :* b) -> (a :* b) -> Bool
/= :: (a :* b) -> (a :* b) -> Bool
$c/= :: forall a b. (Eq a, Eq b) => (a :* b) -> (a :* b) -> Bool
== :: (a :* b) -> (a :* b) -> Bool
$c== :: forall a b. (Eq a, Eq b) => (a :* b) -> (a :* b) -> Bool
Eq, Eq (a :* b)
Eq (a :* b)
-> ((a :* b) -> (a :* b) -> Ordering)
-> ((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> Bool)
-> ((a :* b) -> (a :* b) -> a :* b)
-> ((a :* b) -> (a :* b) -> a :* b)
-> Ord (a :* b)
(a :* b) -> (a :* b) -> Bool
(a :* b) -> (a :* b) -> Ordering
(a :* b) -> (a :* b) -> a :* b
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
forall {a} {b}. (Ord a, Ord b) => Eq (a :* b)
forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Ordering
forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> a :* b
min :: (a :* b) -> (a :* b) -> a :* b
$cmin :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> a :* b
max :: (a :* b) -> (a :* b) -> a :* b
$cmax :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> a :* b
>= :: (a :* b) -> (a :* b) -> Bool
$c>= :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
> :: (a :* b) -> (a :* b) -> Bool
$c> :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
<= :: (a :* b) -> (a :* b) -> Bool
$c<= :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
< :: (a :* b) -> (a :* b) -> Bool
$c< :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Bool
compare :: (a :* b) -> (a :* b) -> Ordering
$ccompare :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Ordering
Ord, Int -> (a :* b) -> ShowS
[a :* b] -> ShowS
(a :* b) -> String
(Int -> (a :* b) -> ShowS)
-> ((a :* b) -> String) -> ([a :* b] -> ShowS) -> Show (a :* b)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall a b. (Show a, Show b) => Int -> (a :* b) -> ShowS
forall a b. (Show a, Show b) => [a :* b] -> ShowS
forall a b. (Show a, Show b) => (a :* b) -> String
showList :: [a :* b] -> ShowS
$cshowList :: forall a b. (Show a, Show b) => [a :* b] -> ShowS
show :: (a :* b) -> String
$cshow :: forall a b. (Show a, Show b) => (a :* b) -> String
showsPrec :: Int -> (a :* b) -> ShowS
$cshowsPrec :: forall a b. (Show a, Show b) => Int -> (a :* b) -> ShowS
Show)
nextPowerOfTwo :: Int -> Int
{-# INLINE nextPowerOfTwo #-}
nextPowerOfTwo :: Int -> Int
nextPowerOfTwo Int
n =
let a :: Int
a = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
b :: Int
b = Int
a Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
a Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
1)
c :: Int
c = Int
b Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
b Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
2)
d :: Int
d = Int
c Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
c Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
4)
e :: Int
e = Int
d Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
d Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
8)
f :: Int
f = Int
e Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
e Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
16)
g :: Int
g = Int
f Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. (Int
f Int -> Int -> Int
forall a. FastShift a => a -> Int -> a
`shiftR` Int
32)
!h :: Int
h = Int
g Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
in Int
h
class FastShift a where
shiftL :: a -> Int -> a
shiftR :: a -> Int -> a
instance FastShift Word32 where
{-# INLINE shiftL #-}
shiftL :: Word32 -> Int -> Word32
shiftL (W32# Word#
x#) (I# Int#
i#) = Word# -> Word32
W32# (Word#
x# Word# -> Int# -> Word#
`uncheckedShiftL#` Int#
i#)
{-# INLINE shiftR #-}
shiftR :: Word32 -> Int -> Word32
shiftR (W32# Word#
x#) (I# Int#
i#) = Word# -> Word32
W32# (Word#
x# Word# -> Int# -> Word#
`uncheckedShiftRL#` Int#
i#)
instance FastShift Word64 where
{-# INLINE shiftL #-}
shiftL :: Word64 -> Int -> Word64
shiftL (W64# Word#
x#) (I# Int#
i#) = Word# -> Word64
W64# (Word#
x# Word# -> Int# -> Word#
`uncheckedShiftL64#` Int#
i#)
{-# INLINE shiftR #-}
shiftR :: Word64 -> Int -> Word64
shiftR (W64# Word#
x#) (I# Int#
i#) = Word# -> Word64
W64# (Word#
x# Word# -> Int# -> Word#
`uncheckedShiftRL64#` Int#
i#)
instance FastShift Int where
{-# INLINE shiftL #-}
shiftL :: Int -> Int -> Int
shiftL (I# Int#
x#) (I# Int#
i#) = Int# -> Int
I# (Int#
x# Int# -> Int# -> Int#
`iShiftL#` Int#
i#)
{-# INLINE shiftR #-}
shiftR :: Int -> Int -> Int
shiftR (I# Int#
x#) (I# Int#
i#) = Int# -> Int
I# (Int#
x# Int# -> Int# -> Int#
`iShiftRA#` Int#
i#)
instance FastShift Integer where
{-# INLINE shiftL #-}
shiftL :: Integer -> Int -> Integer
shiftL = Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
Bits.shiftL
{-# INLINE shiftR #-}
shiftR :: Integer -> Int -> Integer
shiftR = Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
Bits.shiftR