{-# LANGUAGE BangPatterns, MagicHash, TypeOperators #-}

module Data.BloomFilter.Util
    (
      nextPowerOfTwo
    , (:*)(..)
    ) where

import Data.Bits ((.|.), unsafeShiftR)

-- | A strict pair type.
data a :* b = !a :* !b
            deriving ((a :* b) -> (a :* b) -> Bool
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, (a :* b) -> (a :* b) -> Bool
(a :* b) -> (a :* b) -> Ordering
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
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)

-- | Compute the nearest power of two greater to or equal than the
-- given number.
nextPowerOfTwo :: Int -> Int
{-# INLINE nextPowerOfTwo #-}
nextPowerOfTwo :: Int -> Int
nextPowerOfTwo Int
n =
    let a :: Int
a = Int
n forall a. Num a => a -> a -> a
- Int
1
        b :: Int
b = Int
a forall a. Bits a => a -> a -> a
.|. (Int
a forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int
1)
        c :: Int
c = Int
b forall a. Bits a => a -> a -> a
.|. (Int
b forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int
2)
        d :: Int
d = Int
c forall a. Bits a => a -> a -> a
.|. (Int
c forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int
4)
        e :: Int
e = Int
d forall a. Bits a => a -> a -> a
.|. (Int
d forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int
8)
        f :: Int
f = Int
e forall a. Bits a => a -> a -> a
.|. (Int
e forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int
16)
        g :: Int
g = Int
f forall a. Bits a => a -> a -> a
.|. (Int
f forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int
32)  -- in case we're on a 64-bit host
        !h :: Int
h = Int
g forall a. Num a => a -> a -> a
+ Int
1
    in Int
h