    {-# 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
    ((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
    $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
    /= :: (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
    $ccompare :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> Ordering
    compare :: (a :* b) -> (a :* b) -> Ordering
    $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
    >= :: (a :* b) -> (a :* b) -> Bool
    $cmax :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> a :* b
    max :: (a :* b) -> (a :* b) -> a :* b
    $cmin :: forall a b. (Ord a, Ord b) => (a :* b) -> (a :* b) -> a :* b
    min :: (a :* b) -> (a :* b) -> a :* b
    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
    $cshowsPrec :: forall a b. (Show a, Show b) => Int -> (a :* b) -> ShowS
    showsPrec :: Int -> (a :* b) -> ShowS
    $cshow :: forall a b. (Show a, Show b) => (a :* b) -> String
    show :: (a :* b) -> String
    $cshowList :: forall a b. (Show a, Show b) => [a :* b] -> ShowS
    showList :: [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 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. Bits a => a -> Int -> a
    `unsafeShiftR` Int
    1)
            c :: Int
    c = Int
    b Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .|. (Int
    b Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `unsafeShiftR` Int
    2)
            d :: Int
    d = Int
    c Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .|. (Int
    c Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `unsafeShiftR` Int
    4)
            e :: Int
    e = Int
    d Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .|. (Int
    d Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `unsafeShiftR` Int
    8)
            f :: Int
    f = Int
    e Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .|. (Int
    e Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `unsafeShiftR` Int
    16)
            g :: Int
    g = Int
    f Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .|. (Int
    f Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `unsafeShiftR` Int
    32)  -- in case we're on a 64-bit host
            !h :: Int
    h = Int
    g Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1
        in Int
    h