{-# LANGUAGE BangPatterns   #-}
{-# LANGUAGE DeriveFunctor  #-}
{-# LANGUAGE NamedFieldPuns #-}
{-# OPTIONS_HADDOCK not-home #-}

module Database.LSMTree.Internal.RawPage (
    RawPage (..),
    emptyRawPage,
    makeRawPage,
    unsafeMakeRawPage,
    rawPageRawBytes,
    rawPageNumKeys,
    rawPageNumBlobs,
    rawPageLookup,
    RawPageLookup(..),
    rawPageOverflowPages,
    rawPageFindKey,
    rawPageIndex,
    RawPageIndex(..),
    getRawPageIndexKey,
    -- * Test and debug
    rawPageKeyOffsets,
    rawPageValueOffsets,
    rawPageValueOffsets1,
    rawPageHasBlobSpanAt,
    rawPageBlobSpanIndex,
    rawPageOpAt,
    rawPageKeys,
    rawPageValues,
) where

import           Control.DeepSeq (NFData (rnf))
import           Control.Exception (assert)
import           Data.Bits (complement, popCount, unsafeShiftL, unsafeShiftR,
                     (.&.))
import           Data.Primitive.ByteArray (ByteArray (..), byteArrayFromList,
                     copyByteArray, fillByteArray, indexByteArray,
                     isByteArrayPinned, newAlignedPinnedByteArray, runByteArray,
                     sizeofByteArray)
import qualified Data.Vector as V
import qualified Data.Vector.Primitive as VP
import           Data.Word (Word16, Word32, Word64, Word8)
import           Database.LSMTree.Internal.BitMath
import           Database.LSMTree.Internal.BlobRef (BlobSpan (..))
import           Database.LSMTree.Internal.Entry (Entry (..))
import           Database.LSMTree.Internal.RawBytes (RawBytes (..))
import qualified Database.LSMTree.Internal.RawBytes as RB
import           Database.LSMTree.Internal.Serialise (SerialisedKey (..),
                     SerialisedValue (..))
import           Database.LSMTree.Internal.Vector
import qualified GHC.List as List

-------------------------------------------------------------------------------
-- RawPage type
-------------------------------------------------------------------------------

data RawPage = RawPage
    !Int        -- ^ offset in Word16s.
    !ByteArray
  deriving stock (Int -> RawPage -> ShowS
[RawPage] -> ShowS
RawPage -> String
(Int -> RawPage -> ShowS)
-> (RawPage -> String) -> ([RawPage] -> ShowS) -> Show RawPage
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> RawPage -> ShowS
showsPrec :: Int -> RawPage -> ShowS
$cshow :: RawPage -> String
show :: RawPage -> String
$cshowList :: [RawPage] -> ShowS
showList :: [RawPage] -> ShowS
Show)

emptyRawPage :: RawPage
emptyRawPage :: RawPage
emptyRawPage = (ByteArray -> Int -> RawPage) -> Int -> ByteArray -> RawPage
forall a b c. (a -> b -> c) -> b -> a -> c
flip ByteArray -> Int -> RawPage
makeRawPage Int
0 (ByteArray -> RawPage) -> ByteArray -> RawPage
forall a b. (a -> b) -> a -> b
$ [Word8] -> ByteArray
forall a. Prim a => [a] -> ByteArray
byteArrayFromList
   [ Word8
0, Word8
0, Word8
0, Word8
0
   , Word8
8, Word8
0, Word8
0, Word8
0
   , Word8
10 :: Word8
   ]

invariant :: RawPage -> Bool
invariant :: RawPage -> Bool
invariant (RawPage Int
off ByteArray
ba) = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and
    [ Int
off Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0                                      -- offset is positive
    , Int -> Int
forall a. (Bits a, Num a) => a -> a
mod8 Int
offsetInBytes Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0                       -- 64 bit/8 byte alignment
    , (ByteArray -> Int
sizeofByteArray ByteArray
ba Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
offsetInBytes) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
4096  -- there is always 4096 bytes
    , ByteArray -> Bool
isByteArrayPinned ByteArray
ba                          -- bytearray should be pinned
    ]
  where
    offsetInBytes :: Int
offsetInBytes = Int -> Int
forall a. Bits a => a -> a
mul2 Int
off

instance NFData RawPage where
  rnf :: RawPage -> ()
rnf (RawPage Int
_ ByteArray
_) = ()

-- | This instance assumes pages are 4096 bytes in size
instance Eq RawPage where
    RawPage Int
off1 ByteArray
ba1 == :: RawPage -> RawPage -> Bool
== RawPage Int
off2 ByteArray
ba2 = Vector Word16
v1 Vector Word16 -> Vector Word16 -> Bool
forall a. Eq a => a -> a -> Bool
== Vector Word16
v2
      where
        v1, v2 :: VP.Vector Word16
        v1 :: Vector Word16
v1 = Int -> Int -> ByteArray -> Vector Word16
forall a. Prim a => Int -> Int -> ByteArray -> Vector a
mkPrimVector Int
off1 Int
2048 ByteArray
ba1
        v2 :: Vector Word16
v2 = Int -> Int -> ByteArray -> Vector Word16
forall a. Prim a => Int -> Int -> ByteArray -> Vector a
mkPrimVector Int
off2 Int
2048 ByteArray
ba2

-- | Create 'RawPage'.
--
-- This function may copy data to satisfy internal 'RawPage' invariants.
-- Use 'unsafeMakeRawPage' if you don't want copy.
makeRawPage ::
       ByteArray  -- ^ bytearray, must contain 4096 bytes (after offset)
    -> Int        -- ^ offset in bytes, must be 8 byte aligned.
    -> RawPage
makeRawPage :: ByteArray -> Int -> RawPage
makeRawPage ByteArray
ba Int
off
    | RawPage -> Bool
invariant RawPage
page = RawPage
page
    | Bool
otherwise      = Int -> ByteArray -> RawPage
RawPage Int
0 (ByteArray -> RawPage) -> ByteArray -> RawPage
forall a b. (a -> b) -> a -> b
$ (forall s. ST s (MutableByteArray s)) -> ByteArray
runByteArray ((forall s. ST s (MutableByteArray s)) -> ByteArray)
-> (forall s. ST s (MutableByteArray s)) -> ByteArray
forall a b. (a -> b) -> a -> b
$ do
        MutableByteArray s
mba <- Int -> Int -> ST s (MutableByteArray (PrimState (ST s)))
forall (m :: * -> *).
PrimMonad m =>
Int -> Int -> m (MutableByteArray (PrimState m))
newAlignedPinnedByteArray Int
4096 Int
8
        MutableByteArray (PrimState (ST s))
-> Int -> Int -> Word8 -> ST s ()
forall (m :: * -> *).
PrimMonad m =>
MutableByteArray (PrimState m) -> Int -> Int -> Word8 -> m ()
fillByteArray MutableByteArray s
MutableByteArray (PrimState (ST s))
mba Int
0 Int
4096 Word8
0
        MutableByteArray (PrimState (ST s))
-> Int -> ByteArray -> Int -> Int -> ST s ()
forall (m :: * -> *).
PrimMonad m =>
MutableByteArray (PrimState m)
-> Int -> ByteArray -> Int -> Int -> m ()
copyByteArray MutableByteArray s
MutableByteArray (PrimState (ST s))
mba Int
0 ByteArray
ba Int
off (Int -> Int -> Int -> Int
forall {a}. Ord a => a -> a -> a -> a
clamp Int
0 Int
4096 (ByteArray -> Int
sizeofByteArray ByteArray
ba Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
off))
        MutableByteArray s -> ST s (MutableByteArray s)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return MutableByteArray s
mba
  where
    page :: RawPage
page = Int -> ByteArray -> RawPage
RawPage (Int -> Int
forall a. Bits a => a -> a
div2 Int
off) ByteArray
ba
    clamp :: a -> a -> a -> a
clamp a
l a
u a
x = a -> a -> a
forall a. Ord a => a -> a -> a
max a
l (a -> a -> a
forall a. Ord a => a -> a -> a
min a
u a
x)

unsafeMakeRawPage ::
       ByteArray  -- ^ bytearray, must be pinned and contain 4096 bytes (after offset)
    -> Int        -- ^ offset in bytes, must be 8 byte aligned.
    -> RawPage
unsafeMakeRawPage :: ByteArray -> Int -> RawPage
unsafeMakeRawPage ByteArray
ba Int
off = Bool -> RawPage -> RawPage
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (RawPage -> Bool
invariant RawPage
page) RawPage
page
  where
    page :: RawPage
page = Int -> ByteArray -> RawPage
RawPage (Int -> Int
forall a. Bits a => a -> a
div2 Int
off) ByteArray
ba

rawPageRawBytes :: RawPage -> RawBytes
rawPageRawBytes :: RawPage -> RawBytes
rawPageRawBytes (RawPage Int
off ByteArray
ba) =
      Int -> Int -> ByteArray -> RawBytes
RB.fromByteArray (Int -> Int
forall a. Bits a => a -> a
mul2 Int
off) Int
4096 ByteArray
ba

-------------------------------------------------------------------------------
-- Lookup function
-------------------------------------------------------------------------------

data RawPageLookup entry =
       -- | The key is not present on the page.
       LookupEntryNotPresent

       -- | The key is present and corresponds to a normal entry that fits
       -- fully within the page.
     | LookupEntry !entry

       -- | The key is present and corresponds to an entry where the value
       -- may have overflowed onto subsequent pages. In this case the entry
       -- contains the /prefix/ of the value (that did fit on the page). The
       -- length of the suffix is returned separately.
     | LookupEntryOverflow !entry !Word32
  deriving stock (RawPageLookup entry -> RawPageLookup entry -> Bool
(RawPageLookup entry -> RawPageLookup entry -> Bool)
-> (RawPageLookup entry -> RawPageLookup entry -> Bool)
-> Eq (RawPageLookup entry)
forall entry.
Eq entry =>
RawPageLookup entry -> RawPageLookup entry -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall entry.
Eq entry =>
RawPageLookup entry -> RawPageLookup entry -> Bool
== :: RawPageLookup entry -> RawPageLookup entry -> Bool
$c/= :: forall entry.
Eq entry =>
RawPageLookup entry -> RawPageLookup entry -> Bool
/= :: RawPageLookup entry -> RawPageLookup entry -> Bool
Eq, (forall a b. (a -> b) -> RawPageLookup a -> RawPageLookup b)
-> (forall a b. a -> RawPageLookup b -> RawPageLookup a)
-> Functor RawPageLookup
forall a b. a -> RawPageLookup b -> RawPageLookup a
forall a b. (a -> b) -> RawPageLookup a -> RawPageLookup b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> RawPageLookup a -> RawPageLookup b
fmap :: forall a b. (a -> b) -> RawPageLookup a -> RawPageLookup b
$c<$ :: forall a b. a -> RawPageLookup b -> RawPageLookup a
<$ :: forall a b. a -> RawPageLookup b -> RawPageLookup a
Functor, Int -> RawPageLookup entry -> ShowS
[RawPageLookup entry] -> ShowS
RawPageLookup entry -> String
(Int -> RawPageLookup entry -> ShowS)
-> (RawPageLookup entry -> String)
-> ([RawPageLookup entry] -> ShowS)
-> Show (RawPageLookup entry)
forall entry. Show entry => Int -> RawPageLookup entry -> ShowS
forall entry. Show entry => [RawPageLookup entry] -> ShowS
forall entry. Show entry => RawPageLookup entry -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall entry. Show entry => Int -> RawPageLookup entry -> ShowS
showsPrec :: Int -> RawPageLookup entry -> ShowS
$cshow :: forall entry. Show entry => RawPageLookup entry -> String
show :: RawPageLookup entry -> String
$cshowList :: forall entry. Show entry => [RawPageLookup entry] -> ShowS
showList :: [RawPageLookup entry] -> ShowS
Show)

-- |
-- __Time:__ \( \mathcal{O}\left( \log_2 n \right) \)
-- where \( n \) is the number of entries in the 'RawPage'.
--
-- Return the 'Entry' corresponding to the supplied 'SerialisedKey' if it exists
-- within the 'RawPage'.
rawPageLookup ::
       RawPage
    -> SerialisedKey
    -> RawPageLookup (Entry SerialisedValue BlobSpan)
rawPageLookup :: RawPage
-> SerialisedKey -> RawPageLookup (Entry SerialisedValue BlobSpan)
rawPageLookup !RawPage
page !SerialisedKey
key
  | Word16
dirNumKeys Word16 -> Word16 -> Bool
forall a. Eq a => a -> a -> Bool
== Word16
1 = RawPageLookup (Entry SerialisedValue BlobSpan)
lookup1
  | Bool
otherwise       = case Int -> RawPage -> SerialisedKey -> BinarySearchResult
bisectPageToKey (Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys) RawPage
page SerialisedKey
key of
    KeyWasFoundAt Int
i -> Entry SerialisedValue BlobSpan
-> RawPageLookup (Entry SerialisedValue BlobSpan)
forall entry. entry -> RawPageLookup entry
LookupEntry (Entry SerialisedValue BlobSpan
 -> RawPageLookup (Entry SerialisedValue BlobSpan))
-> Entry SerialisedValue BlobSpan
-> RawPageLookup (Entry SerialisedValue BlobSpan)
forall a b. (a -> b) -> a -> b
$ RawPage -> Int -> Entry SerialisedValue BlobSpan
rawPageEntryAt RawPage
page Int
i
    BinarySearchResult
_               -> RawPageLookup (Entry SerialisedValue BlobSpan)
forall entry. RawPageLookup entry
LookupEntryNotPresent
  where
    !dirNumKeys :: Word16
dirNumKeys = RawPage -> Word16
rawPageNumKeys RawPage
page

    lookup1 :: RawPageLookup (Entry SerialisedValue BlobSpan)
lookup1
      | SerialisedKey
key SerialisedKey -> SerialisedKey -> Bool
forall a. Eq a => a -> a -> Bool
== RawPage -> Int -> SerialisedKey
rawPageKeyAt RawPage
page Int
0
      = let !entry :: Entry SerialisedValue BlobSpan
entry  = RawPage -> Entry SerialisedValue BlobSpan
rawPageEntry1 RawPage
page
            !suffix :: Word32
suffix = RawPage -> Word32
rawPageSingleValueSuffix RawPage
page
         in if Word32
suffix Word32 -> Word32 -> Bool
forall a. Ord a => a -> a -> Bool
> Word32
0
              then Entry SerialisedValue BlobSpan
-> Word32 -> RawPageLookup (Entry SerialisedValue BlobSpan)
forall entry. entry -> Word32 -> RawPageLookup entry
LookupEntryOverflow Entry SerialisedValue BlobSpan
entry Word32
suffix
              else Entry SerialisedValue BlobSpan
-> RawPageLookup (Entry SerialisedValue BlobSpan)
forall entry. entry -> RawPageLookup entry
LookupEntry         Entry SerialisedValue BlobSpan
entry
      | Bool
otherwise
      = RawPageLookup (Entry SerialisedValue BlobSpan)
forall entry. RawPageLookup entry
LookupEntryNotPresent

-- |
-- __Time:__ \( \mathcal{O}\left( \log_2 n \right) \)
-- where \( n \) is the number of entries in the 'RawPage'.
--
-- Return the least entry number in the 'RawPage' (if it exists)
-- which is greater than or equal to the supplied 'SerialisedKey'.
--
-- The following law always holds \( \forall \mathtt{key} \mathtt{page} \):
--
--   * maybe True (key <=) (getRawPageIndexKey . rawPageIndex page . id   =<< rawPageFindKey page key)
--
--   * maybe True (key > ) (getRawPageIndexKey . rawPageIndex page . pred =<< rawPageFindKey page key)
--
--   * maybe (maximum (rawPageKeys page) < key) (rawPageFindKey page key)
rawPageFindKey ::
       RawPage
    -> SerialisedKey
    -> Maybe Word16  -- ^ entry number of first entry greater or equal to the key
rawPageFindKey :: RawPage -> SerialisedKey -> Maybe Word16
rawPageFindKey !RawPage
page !SerialisedKey
key
  | Word16
dirNumKeys Word16 -> Word16 -> Bool
forall a. Eq a => a -> a -> Bool
== Word16
1 = Maybe Word16
lookup1
  | Bool
otherwise       = case Int -> RawPage -> SerialisedKey -> BinarySearchResult
bisectPageToKey (Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys) RawPage
page SerialisedKey
key of
    BinarySearchResult
KeyNotFoundExceedsPage   -> Maybe Word16
forall a. Maybe a
Nothing
    KeyNotFoundNearestIsAt Int
i -> Word16 -> Maybe Word16
forall a. a -> Maybe a
Just (Word16 -> Maybe Word16) -> Word16 -> Maybe Word16
forall a b. (a -> b) -> a -> b
$ Int -> Word16
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
i
    KeyWasFoundAt          Int
i -> Word16 -> Maybe Word16
forall a. a -> Maybe a
Just (Word16 -> Maybe Word16) -> Word16 -> Maybe Word16
forall a b. (a -> b) -> a -> b
$ Int -> Word16
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
i

  where
    !dirNumKeys :: Word16
dirNumKeys = RawPage -> Word16
rawPageNumKeys RawPage
page

    lookup1 :: Maybe Word16
lookup1
      | SerialisedKey
key SerialisedKey -> SerialisedKey -> Bool
forall a. Ord a => a -> a -> Bool
<= RawPage -> Int -> SerialisedKey
rawPageKeyAt RawPage
page Int
0 = Word16 -> Maybe Word16
forall a. a -> Maybe a
Just Word16
0
      | Bool
otherwise                  = Maybe Word16
forall a. Maybe a
Nothing

-- | This data-type facilitates the code reuse of 'bisectPageToKey' between the
-- and 'rawPageLookup' and 'rawPageFindKey'.
data BinarySearchResult
  = KeyNotFoundExceedsPage
  | KeyNotFoundNearestIsAt {-# UNPACK #-} !Int
  | KeyWasFoundAt {-# UNPACK #-} !Int

-- | Binary search procedure shared between 'rawPageLookup' and 'rawPageFindKey'.
{-# INLINE bisectPageToKey #-}
bisectPageToKey ::
     Int
  -> RawPage
  -> SerialisedKey
  -> BinarySearchResult
bisectPageToKey :: Int -> RawPage -> SerialisedKey -> BinarySearchResult
bisectPageToKey !Int
numKeys !RawPage
page !SerialisedKey
key = Int -> Int -> BinarySearchResult
go Int
0 Int
numKeys
  where
    -- Binary search for within the range [i, j)
    -- for the index k corresponding to key.
    --
    -- If k > key, search [ k + 1, j )
    -- If k < key, search [     i, j )
    go :: Int -> Int -> BinarySearchResult
    go :: Int -> Int -> BinarySearchResult
go !Int
i !Int
j
      | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
j =
        if Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
numKeys
        then BinarySearchResult
KeyNotFoundExceedsPage
        else Int -> BinarySearchResult
KeyNotFoundNearestIsAt Int
j
      | Bool
otherwise =
        let !k :: Int
k = Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a. Bits a => a -> a
div2 (Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i)
        in  case SerialisedKey
key SerialisedKey -> SerialisedKey -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` RawPage -> Int -> SerialisedKey
rawPageKeyAt RawPage
page Int
k of
          Ordering
GT -> Int -> Int -> BinarySearchResult
go (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int
j
          Ordering
EQ -> Int -> BinarySearchResult
KeyWasFoundAt Int
k
          Ordering
LT -> Int -> Int -> BinarySearchResult
go Int
i Int
k

data RawPageIndex entry =
       IndexNotPresent
       -- | The index is present and corresponds to a normal entry that fits
       -- fully within the page (but might be the only entry on the page).
     | IndexEntry !SerialisedKey !entry
       -- | The index is present and corresponds to an entry where the value
       -- has overflowed onto subsequent pages. In this case only prefix entry
       -- and the length of the suffix are returned.
       -- The caller can copy the full serialised pages themselves.
     | IndexEntryOverflow !SerialisedKey !entry !Word32
  deriving stock (RawPageIndex entry -> RawPageIndex entry -> Bool
(RawPageIndex entry -> RawPageIndex entry -> Bool)
-> (RawPageIndex entry -> RawPageIndex entry -> Bool)
-> Eq (RawPageIndex entry)
forall entry.
Eq entry =>
RawPageIndex entry -> RawPageIndex entry -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall entry.
Eq entry =>
RawPageIndex entry -> RawPageIndex entry -> Bool
== :: RawPageIndex entry -> RawPageIndex entry -> Bool
$c/= :: forall entry.
Eq entry =>
RawPageIndex entry -> RawPageIndex entry -> Bool
/= :: RawPageIndex entry -> RawPageIndex entry -> Bool
Eq, (forall a b. (a -> b) -> RawPageIndex a -> RawPageIndex b)
-> (forall a b. a -> RawPageIndex b -> RawPageIndex a)
-> Functor RawPageIndex
forall a b. a -> RawPageIndex b -> RawPageIndex a
forall a b. (a -> b) -> RawPageIndex a -> RawPageIndex b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> RawPageIndex a -> RawPageIndex b
fmap :: forall a b. (a -> b) -> RawPageIndex a -> RawPageIndex b
$c<$ :: forall a b. a -> RawPageIndex b -> RawPageIndex a
<$ :: forall a b. a -> RawPageIndex b -> RawPageIndex a
Functor, Int -> RawPageIndex entry -> ShowS
[RawPageIndex entry] -> ShowS
RawPageIndex entry -> String
(Int -> RawPageIndex entry -> ShowS)
-> (RawPageIndex entry -> String)
-> ([RawPageIndex entry] -> ShowS)
-> Show (RawPageIndex entry)
forall entry. Show entry => Int -> RawPageIndex entry -> ShowS
forall entry. Show entry => [RawPageIndex entry] -> ShowS
forall entry. Show entry => RawPageIndex entry -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall entry. Show entry => Int -> RawPageIndex entry -> ShowS
showsPrec :: Int -> RawPageIndex entry -> ShowS
$cshow :: forall entry. Show entry => RawPageIndex entry -> String
show :: RawPageIndex entry -> String
$cshowList :: forall entry. Show entry => [RawPageIndex entry] -> ShowS
showList :: [RawPageIndex entry] -> ShowS
Show)

-- |
-- __Time:__ \( \mathcal{O}\left( 1 \right) \)
--
-- Conveniently access the 'SerialisedKey' of a 'RawPageIndex'.
{-# INLINE getRawPageIndexKey #-}
getRawPageIndexKey :: RawPageIndex e -> Maybe SerialisedKey
getRawPageIndexKey :: forall e. RawPageIndex e -> Maybe SerialisedKey
getRawPageIndexKey = \case
  IndexEntry SerialisedKey
k e
_ -> SerialisedKey -> Maybe SerialisedKey
forall a. a -> Maybe a
Just SerialisedKey
k
  IndexEntryOverflow SerialisedKey
k e
_ Word32
_ -> SerialisedKey -> Maybe SerialisedKey
forall a. a -> Maybe a
Just SerialisedKey
k
  RawPageIndex e
IndexNotPresent -> Maybe SerialisedKey
forall a. Maybe a
Nothing


{-# INLINE rawPageIndex #-}
rawPageIndex ::
       RawPage
    -> Word16
    -> RawPageIndex (Entry SerialisedValue BlobSpan)
rawPageIndex :: RawPage -> Word16 -> RawPageIndex (Entry SerialisedValue BlobSpan)
rawPageIndex !RawPage
page !Word16
ix
  | Word16
ix Word16 -> Word16 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word16
dirNumKeys =
      RawPageIndex (Entry SerialisedValue BlobSpan)
forall entry. RawPageIndex entry
IndexNotPresent
  | Word16
dirNumKeys Word16 -> Word16 -> Bool
forall a. Ord a => a -> a -> Bool
> Word16
1 =
      let ix' :: Int
ix' = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
ix
       in SerialisedKey
-> Entry SerialisedValue BlobSpan
-> RawPageIndex (Entry SerialisedValue BlobSpan)
forall entry. SerialisedKey -> entry -> RawPageIndex entry
IndexEntry (RawPage -> Int -> SerialisedKey
rawPageKeyAt RawPage
page Int
ix') (RawPage -> Int -> Entry SerialisedValue BlobSpan
rawPageEntryAt RawPage
page Int
ix')
  | Bool
otherwise =
      let key :: SerialisedKey
key = RawPage -> Int -> SerialisedKey
rawPageKeyAt RawPage
page Int
0
          entry :: Entry SerialisedValue BlobSpan
entry = RawPage -> Entry SerialisedValue BlobSpan
rawPageEntry1 RawPage
page
          !suffix :: Word32
suffix = RawPage -> Word32
rawPageSingleValueSuffix RawPage
page
       in if Word32
suffix Word32 -> Word32 -> Bool
forall a. Ord a => a -> a -> Bool
<= Word32
0
         then SerialisedKey
-> Entry SerialisedValue BlobSpan
-> RawPageIndex (Entry SerialisedValue BlobSpan)
forall entry. SerialisedKey -> entry -> RawPageIndex entry
IndexEntry SerialisedKey
key Entry SerialisedValue BlobSpan
entry
         else SerialisedKey
-> Entry SerialisedValue BlobSpan
-> Word32
-> RawPageIndex (Entry SerialisedValue BlobSpan)
forall entry.
SerialisedKey -> entry -> Word32 -> RawPageIndex entry
IndexEntryOverflow SerialisedKey
key Entry SerialisedValue BlobSpan
entry Word32
suffix
  where
    !dirNumKeys :: Word16
dirNumKeys = RawPage -> Word16
rawPageNumKeys RawPage
page

-- | for non-single key page case
rawPageEntryAt :: RawPage -> Int -> Entry SerialisedValue BlobSpan
rawPageEntryAt :: RawPage -> Int -> Entry SerialisedValue BlobSpan
rawPageEntryAt RawPage
page Int
i =
    Bool
-> Entry SerialisedValue BlobSpan -> Entry SerialisedValue BlobSpan
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (RawPage -> Word16
rawPageNumKeys RawPage
page)) (Entry SerialisedValue BlobSpan -> Entry SerialisedValue BlobSpan)
-> Entry SerialisedValue BlobSpan -> Entry SerialisedValue BlobSpan
forall a b. (a -> b) -> a -> b
$
    Bool
-> Entry SerialisedValue BlobSpan -> Entry SerialisedValue BlobSpan
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (RawPage -> Word16
rawPageNumKeys RawPage
page Word16 -> Word16 -> Bool
forall a. Ord a => a -> a -> Bool
> Word16
1) (Entry SerialisedValue BlobSpan -> Entry SerialisedValue BlobSpan)
-> Entry SerialisedValue BlobSpan -> Entry SerialisedValue BlobSpan
forall a b. (a -> b) -> a -> b
$
    case RawPage -> Int -> Word64
rawPageOpAt RawPage
page Int
i of
      Word64
0 -> if RawPage -> Int -> Word64
rawPageHasBlobSpanAt RawPage
page Int
i Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0
           then SerialisedValue -> Entry SerialisedValue BlobSpan
forall v b. v -> Entry v b
Insert (RawPage -> Int -> SerialisedValue
rawPageValueAt RawPage
page Int
i)
           else SerialisedValue -> BlobSpan -> Entry SerialisedValue BlobSpan
forall v b. v -> b -> Entry v b
InsertWithBlob (RawPage -> Int -> SerialisedValue
rawPageValueAt RawPage
page Int
i)
                               (RawPage -> Int -> BlobSpan
rawPageBlobSpanIndex RawPage
page
                                  (RawPage -> Int -> Int
rawPageCalculateBlobIndex RawPage
page Int
i))
      Word64
1 -> SerialisedValue -> Entry SerialisedValue BlobSpan
forall v b. v -> Entry v b
Mupdate (RawPage -> Int -> SerialisedValue
rawPageValueAt RawPage
page Int
i)
      Word64
_ -> Entry SerialisedValue BlobSpan
forall v b. Entry v b
Delete

-- | Single key page case
rawPageEntry1 :: RawPage -> Entry SerialisedValue BlobSpan
rawPageEntry1 :: RawPage -> Entry SerialisedValue BlobSpan
rawPageEntry1 RawPage
page =
    case RawPage -> Int -> Word64
rawPageOpAt RawPage
page Int
0 of
      Word64
0 -> if RawPage -> Int -> Word64
rawPageHasBlobSpanAt RawPage
page Int
0 Word64 -> Word64 -> Bool
forall a. Eq a => a -> a -> Bool
== Word64
0
           then SerialisedValue -> Entry SerialisedValue BlobSpan
forall v b. v -> Entry v b
Insert (RawPage -> SerialisedValue
rawPageSingleValuePrefix RawPage
page)
           else SerialisedValue -> BlobSpan -> Entry SerialisedValue BlobSpan
forall v b. v -> b -> Entry v b
InsertWithBlob (RawPage -> SerialisedValue
rawPageSingleValuePrefix RawPage
page)
                               (RawPage -> Int -> BlobSpan
rawPageBlobSpanIndex RawPage
page
                                  (RawPage -> Int -> Int
rawPageCalculateBlobIndex RawPage
page Int
0))
      Word64
1 -> SerialisedValue -> Entry SerialisedValue BlobSpan
forall v b. v -> Entry v b
Mupdate (RawPage -> SerialisedValue
rawPageSingleValuePrefix RawPage
page)
      Word64
_ -> Entry SerialisedValue BlobSpan
forall v b. Entry v b
Delete

-- | Calculate the number of overflow pages that are expected to follow this
-- page.
--
-- This will be non-zero when the page contains a single key\/op entry that is
-- itself too large to fit within the page.
--
rawPageOverflowPages :: RawPage -> Int
rawPageOverflowPages :: RawPage -> Int
rawPageOverflowPages RawPage
page
  | RawPage -> Word16
rawPageNumKeys RawPage
page Word16 -> Word16 -> Bool
forall a. Eq a => a -> a -> Bool
== Word16
1
  , let (Word16
_, Word32
end) = RawPage -> (Word16, Word32)
rawPageValueOffsets1 RawPage
page
  = Word32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word32 -> Word32
forall a. (Bits a, Num a) => a -> a
ceilDivPageSize Word32
end Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
- Word32
1)  -- don't count the first page

  | Bool
otherwise = Int
0

-------------------------------------------------------------------------------
-- Accessors
-------------------------------------------------------------------------------

-- Note: indexByteArray's offset is given in elements of type a rather than in bytes.

rawPageNumKeys :: RawPage -> Word16
rawPageNumKeys :: RawPage -> Word16
rawPageNumKeys (RawPage Int
off ByteArray
ba) = ByteArray -> Int -> Word16
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba Int
off

rawPageNumBlobs :: RawPage -> Word16
rawPageNumBlobs :: RawPage -> Word16
rawPageNumBlobs (RawPage Int
off ByteArray
ba) = ByteArray -> Int -> Word16
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)

rawPageKeysOffset :: RawPage -> Word16
rawPageKeysOffset :: RawPage -> Word16
rawPageKeysOffset (RawPage Int
off ByteArray
ba) = ByteArray -> Int -> Word16
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
2)

type KeyOffset = Word16
type ValueOffset = Word16

rawPageKeyOffsets :: RawPage -> VP.Vector KeyOffset
rawPageKeyOffsets :: RawPage -> Vector Word16
rawPageKeyOffsets page :: RawPage
page@(RawPage Int
off ByteArray
ba) =
    Int -> Int -> ByteArray -> Vector Word16
forall a. Prim a => Int -> Int -> ByteArray -> Vector a
mkPrimVector
        (Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16 -> Word16
forall a. Bits a => a -> a
div2 Word16
dirOffset))
        (Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
        ByteArray
ba
  where
    !dirNumKeys :: Word16
dirNumKeys = RawPage -> Word16
rawPageNumKeys RawPage
page
    !dirOffset :: Word16
dirOffset  = RawPage -> Word16
rawPageKeysOffset RawPage
page

-- | for non-single key page case
rawPageValueOffsets :: RawPage -> VP.Vector ValueOffset
rawPageValueOffsets :: RawPage -> Vector Word16
rawPageValueOffsets page :: RawPage
page@(RawPage Int
off ByteArray
ba) =
    Bool -> Vector Word16 -> Vector Word16
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (Word16
dirNumKeys Word16 -> Word16 -> Bool
forall a. Eq a => a -> a -> Bool
/= Word16
1) (Vector Word16 -> Vector Word16) -> Vector Word16 -> Vector Word16
forall a b. (a -> b) -> a -> b
$
    Int -> Int -> ByteArray -> Vector Word16
forall a. Prim a => Int -> Int -> ByteArray -> Vector a
mkPrimVector
        (Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16 -> Word16
forall a. Bits a => a -> a
div2 Word16
dirOffset) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys)
        (Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
        ByteArray
ba
  where
    !dirNumKeys :: Word16
dirNumKeys = RawPage -> Word16
rawPageNumKeys RawPage
page
    !dirOffset :: Word16
dirOffset  = RawPage -> Word16
rawPageKeysOffset RawPage
page

-- | single key page case
{-# INLINE rawPageValueOffsets1 #-}
rawPageValueOffsets1 :: RawPage -> (Word16, Word32)
rawPageValueOffsets1 :: RawPage -> (Word16, Word32)
rawPageValueOffsets1 page :: RawPage
page@(RawPage Int
off ByteArray
ba) =
    Bool -> (Word16, Word32) -> (Word16, Word32)
forall a. (?callStack::CallStack) => Bool -> a -> a
assert (RawPage -> Word16
rawPageNumKeys RawPage
page Word16 -> Word16 -> Bool
forall a. Eq a => a -> a -> Bool
== Word16
1) ((Word16, Word32) -> (Word16, Word32))
-> (Word16, Word32) -> (Word16, Word32)
forall a b. (a -> b) -> a -> b
$
    ( ByteArray -> Int -> Word16
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16 -> Word16
forall a. Bits a => a -> a
div2 Word16
dirOffset) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
    , ByteArray -> Int -> Word32
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int -> Int
forall a. Bits a => a -> a
div2 (Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16 -> Word16
forall a. Bits a => a -> a
div2 Word16
dirOffset)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
    )
  where
    !dirOffset :: Word16
dirOffset = RawPage -> Word16
rawPageKeysOffset RawPage
page

rawPageHasBlobSpanAt :: RawPage -> Int -> Word64
rawPageHasBlobSpanAt :: RawPage -> Int -> Word64
rawPageHasBlobSpanAt _page :: RawPage
_page@(RawPage Int
off ByteArray
ba) Int
i = do
    let j :: Int
j = Int -> Int
forall a. Bits a => a -> a
div64 Int
i
    let k :: Int
k = Int -> Int
forall a. (Bits a, Num a) => a -> a
mod64 Int
i
    let word :: Word64
word = ByteArray -> Int -> Word64
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int -> Int
forall a. Bits a => a -> a
div4 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j)
    Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
unsafeShiftR Word64
word Int
k Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
1

rawPageOpAt :: RawPage -> Int -> Word64
rawPageOpAt :: RawPage -> Int -> Word64
rawPageOpAt page :: RawPage
page@(RawPage Int
off ByteArray
ba) Int
i = do
    let j :: Int
j = Int -> Int
forall a. Bits a => a -> a
div32 Int
i
    let k :: Int
k = Int -> Int
forall a. (Bits a, Num a) => a -> a
mod32 Int
i
    let word :: Word64
word = ByteArray -> Int -> Word64
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int -> Int
forall a. Bits a => a -> a
div4 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a. (Bits a, Num a) => a -> a
ceilDiv64 (Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j)
    Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
unsafeShiftR Word64
word (Int -> Int
forall a. Bits a => a -> a
mul2 Int
k) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
3
  where
    !dirNumKeys :: Word16
dirNumKeys = RawPage -> Word16
rawPageNumKeys RawPage
page

rawPageKeys :: RawPage -> V.Vector SerialisedKey
rawPageKeys :: RawPage -> Vector SerialisedKey
rawPageKeys page :: RawPage
page@(RawPage Int
off ByteArray
ba) = do
    let offs :: Vector Word16
offs = RawPage -> Vector Word16
rawPageKeyOffsets RawPage
page
    [SerialisedKey] -> Vector SerialisedKey
forall a. [a] -> Vector a
V.fromList
        [ RawBytes -> SerialisedKey
SerialisedKey (Int -> Int -> ByteArray -> RawBytes
RB.fromByteArray (Int -> Int
forall a. Bits a => a -> a
mul2 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
start) (Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
start) ByteArray
ba)
        | Int
i <- [ Int
0 .. Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys Int -> Int -> Int
forall a. Num a => a -> a -> a
-  Int
1 ] :: [Int]
        , let start :: Int
start = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word16 -> Int -> Word16
forall a. Prim a => Vector a -> Int -> a
VP.unsafeIndex Vector Word16
offs Int
i) :: Int
        , let end :: Int
end   = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word16 -> Int -> Word16
forall a. Prim a => Vector a -> Int -> a
VP.unsafeIndex Vector Word16
offs (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)) :: Int
        ]
  where
    !dirNumKeys :: Word16
dirNumKeys = RawPage -> Word16
rawPageNumKeys RawPage
page

rawPageKeyAt :: RawPage -> Int -> SerialisedKey
rawPageKeyAt :: RawPage -> Int -> SerialisedKey
rawPageKeyAt page :: RawPage
page@(RawPage Int
off ByteArray
ba) Int
i = do
    RawBytes -> SerialisedKey
SerialisedKey (Int -> Int -> ByteArray -> RawBytes
RB.fromByteArray (Int -> Int
forall a. Bits a => a -> a
mul2 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
start) (Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
start) ByteArray
ba)
  where
    offs :: Vector Word16
offs  = RawPage -> Vector Word16
rawPageKeyOffsets RawPage
page
    start :: Int
start = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word16 -> Int -> Word16
forall a. Prim a => Vector a -> Int -> a
VP.unsafeIndex Vector Word16
offs Int
i) :: Int
    end :: Int
end   = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word16 -> Int -> Word16
forall a. Prim a => Vector a -> Int -> a
VP.unsafeIndex Vector Word16
offs (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)) :: Int

-- | Non-single page case
rawPageValues :: RawPage -> V.Vector SerialisedValue
rawPageValues :: RawPage -> Vector SerialisedValue
rawPageValues page :: RawPage
page@(RawPage Int
off ByteArray
ba) =
    let offs :: Vector Word16
offs = RawPage -> Vector Word16
rawPageValueOffsets RawPage
page in
    [SerialisedValue] -> Vector SerialisedValue
forall a. [a] -> Vector a
V.fromList
        [ RawBytes -> SerialisedValue
SerialisedValue (RawBytes -> SerialisedValue) -> RawBytes -> SerialisedValue
forall a b. (a -> b) -> a -> b
$ Int -> Int -> ByteArray -> RawBytes
RB.fromByteArray (Int -> Int
forall a. Bits a => a -> a
mul2 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
start) (Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
start) ByteArray
ba
        | Int
i <- [ Int
0 .. Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys Int -> Int -> Int
forall a. Num a => a -> a -> a
-  Int
1 ] :: [Int]
        , let start :: Int
start = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word16 -> Int -> Word16
forall a. Prim a => Vector a -> Int -> a
VP.unsafeIndex Vector Word16
offs Int
i) :: Int
        , let end :: Int
end   = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word16 -> Int -> Word16
forall a. Prim a => Vector a -> Int -> a
VP.unsafeIndex Vector Word16
offs (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)) :: Int
        ]
  where
    !dirNumKeys :: Word16
dirNumKeys = RawPage -> Word16
rawPageNumKeys RawPage
page

-- | Non-single page case
rawPageValueAt :: RawPage -> Int -> SerialisedValue
rawPageValueAt :: RawPage -> Int -> SerialisedValue
rawPageValueAt page :: RawPage
page@(RawPage Int
off ByteArray
ba) Int
i =
    RawBytes -> SerialisedValue
SerialisedValue (Int -> Int -> ByteArray -> RawBytes
RB.fromByteArray (Int -> Int
forall a. Bits a => a -> a
mul2 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
start) (Int
end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
start) ByteArray
ba)
  where
    offs :: Vector Word16
offs  = RawPage -> Vector Word16
rawPageValueOffsets RawPage
page
    start :: Int
start = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word16 -> Int -> Word16
forall a. Prim a => Vector a -> Int -> a
VP.unsafeIndex Vector Word16
offs Int
i) :: Int
    end :: Int
end   = Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word16 -> Int -> Word16
forall a. Prim a => Vector a -> Int -> a
VP.unsafeIndex Vector Word16
offs (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)) :: Int

-- | Single key page case
rawPageSingleValuePrefix :: RawPage -> SerialisedValue
rawPageSingleValuePrefix :: RawPage -> SerialisedValue
rawPageSingleValuePrefix page :: RawPage
page@(RawPage Int
off ByteArray
ba) =
    RawBytes -> SerialisedValue
SerialisedValue (RawBytes -> SerialisedValue) -> RawBytes -> SerialisedValue
forall a b. (a -> b) -> a -> b
$
      Int -> Int -> ByteArray -> RawBytes
RB.fromByteArray
        (Int -> Int
forall a. Bits a => a -> a
mul2 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
start)
        (Word32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word32
prefix_end Int -> Int -> Int
forall a. Num a => a -> a -> a
- Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
start)
        ByteArray
ba
  where
    (Word16
start, Word32
end) = RawPage -> (Word16, Word32)
rawPageValueOffsets1 RawPage
page
    prefix_end :: Word32
prefix_end   = Word32 -> Word32 -> Word32
forall a. Ord a => a -> a -> a
min Word32
4096 Word32
end

-- | Single key page case
rawPageSingleValueSuffix :: RawPage -> Word32
rawPageSingleValueSuffix :: RawPage -> Word32
rawPageSingleValueSuffix RawPage
page
    | Word32
end Word32 -> Word32 -> Bool
forall a. Ord a => a -> a -> Bool
> Word32
4096 = Word32
end Word32 -> Word32 -> Word32
forall a. Num a => a -> a -> a
- Word32
4096
    | Bool
otherwise  = Word32
0
  where
    (Word16
_, Word32
end) = RawPage -> (Word16, Word32)
rawPageValueOffsets1 RawPage
page

-- we could create unboxed array.
{-# INLINE rawPageBlobSpanIndex #-}
rawPageBlobSpanIndex :: RawPage
    -> Int -- ^ blobspan index. Calculate with 'rawPageCalculateBlobIndex'
    -> BlobSpan
rawPageBlobSpanIndex :: RawPage -> Int -> BlobSpan
rawPageBlobSpanIndex page :: RawPage
page@(RawPage Int
off ByteArray
ba) Int
i = Word64 -> Word32 -> BlobSpan
BlobSpan
    ( ByteArray -> Int -> Word64
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int
off1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i) )
    ( ByteArray -> Int -> Word32
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int
off2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i) )
  where
    !dirNumKeys :: Word16
dirNumKeys  = RawPage -> Word16
rawPageNumKeys RawPage
page
    !dirNumBlobs :: Word16
dirNumBlobs = RawPage -> Word16
rawPageNumBlobs RawPage
page

    -- offset to start of blobspan arr
    off1 :: Int
off1 = Int -> Int
forall a. Bits a => a -> a
div4 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a. (Bits a, Num a) => a -> a
ceilDiv64 (Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumKeys) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int
forall a. (Bits a, Num a) => a -> a
ceilDiv64 (Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word16 -> Word16
forall a. Bits a => a -> a
mul2 Word16
dirNumKeys))
    off2 :: Int
off2 = Int -> Int
forall a. Bits a => a -> a
mul2 (Int
off1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word16 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word16
dirNumBlobs)

rawPageCalculateBlobIndex ::
       RawPage
    -> Int  -- ^ key index
    -> Int  -- ^ blobspan index
rawPageCalculateBlobIndex :: RawPage -> Int -> Int
rawPageCalculateBlobIndex (RawPage Int
off ByteArray
ba) Int
i = do
    let j :: Int
j = Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftR Int
i Int
6 -- `div` 64
    let k :: Int
k = Int
i Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
63         -- `mod` 64
    -- generic sum isn't too great
    let s :: Int
s = (Int -> Int -> Int) -> Int -> [Int] -> Int
forall a b. (b -> a -> b) -> b -> [a] -> b
List.foldl' Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Int
0 [ Word64 -> Int
forall a. Bits a => a -> Int
popCount (ByteArray -> Int -> Word64
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int -> Int
forall a. Bits a => a -> a
div4 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
jj) :: Word64) | Int
jj <- [Int
0 .. Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1 ] ]
    let word :: Word64
word = ByteArray -> Int -> Word64
forall a. Prim a => ByteArray -> Int -> a
indexByteArray ByteArray
ba (Int -> Int
forall a. Bits a => a -> a
div4 Int
off Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j) :: Word64
    Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Word64 -> Int
forall a. Bits a => a -> Int
popCount (Word64
word Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64 -> Word64
forall a. Bits a => a -> a
complement (Word64 -> Int -> Word64
forall a. Bits a => a -> Int -> a
unsafeShiftL Word64
0xffffffffffffffff Int
k))