packages feed

pykinos-core-0.1.0.2: src/Pykinos/Tree/BPlus.hs

{-# LANGUAGE BangPatterns, DeriveFunctor, DeriveFoldable, ScopedTypeVariables #-}

{- |
Module      : Pykinos.Tree.BPlus
Description : Cache-conscious serried B+ tree with transient epoch versioning
Copyright   : (c) Nadia Yvette Chambers, 2026
License     : EUPL-1.2
Maintainer  : Nadia Chambers <nadia.yvette.chambers@ik.me>
Stability   : experimental
Portability : non-portable (GHC extensions, primitive arrays)

Implements a serried B+ tree using unboxed 'SmallArray' slices for both internal
routing nodes ('BPInternal') and key-value leaves ('BPLeaf').

= Algorithmic Properties

1. **Branching Factor:** Fixed capacity \(M = 16\) slots per node (corresponding to
   128 bytes of pointers on 64-bit architectures, fitting inside two L1 cache lines).
2. **Balanced Height:** All leaves reside at the same tree depth. Insertion splits
   overflowing nodes at \(\lfloor M / 2 \rfloor\) and propagates pivot keys upward.
3. **Cache Locality:** Keys within each leaf and internal node are stored sequentially
   in contiguous memory, enabling binary search ('searchKeys') with minimal branch mispredictions.
4. **Transient Epoch Versioning:** Each node carries an 'EpochId'. When operating
   under 'Pykinos.Effect.Penelope', modifications within the current epoch mutate
   nodes in-place or reuse allocations, while crossing an epoch boundary triggers
   persistent copy-on-write isolation.
-}
module Pykinos.Tree.BPlus
  ( -- * Epoch Tokens
    EpochId
    -- * Tree Types
  , BPlusMap(..)
  , BPlusNode(..)
    -- * Construction & Empty Maps
  , emptyBPlus
  , fromListBPlus
    -- * Lookups & Queries
  , lookupBPlus
  , toAscListBPlus
    -- * Insertion
  , insertBPlus
  , insertBPlusEpoch
  ) where

import Control.Monad.ST (runST)
import Data.Primitive.SmallArray
import Data.Word (Word64)

-- | Monotonic transient epoch token used for MVCC and snapshot isolation.
--
-- Epoch 0 denotes a persistent immutable snapshot. Non-zero epochs identify
-- isolated transaction branches.
type EpochId = Word64

-- | Maximum branching factor per serried B+ block (16 slots = 128 bytes of pointers).
bPlusMaxCap :: Int
bPlusMaxCap = 16

-- | Node representation in the serried B+ tree.
--
-- Nodes are partitioned into routing internal nodes ('BPInternal') and
-- data-bearing leaves ('BPLeaf').
data BPlusNode k v
  = BPLeaf
      { bplEpoch :: {-# UNPACK #-} !EpochId
        -- ^ Epoch version stamp at node creation.
      , bplKeys  :: {-# UNPACK #-} !(SmallArray k)
        -- ^ Contiguous sorted keys stored in this leaf node.
      , bplVals  :: {-# UNPACK #-} !(SmallArray v)
        -- ^ Contiguous values aligned one-to-one with 'bplKeys'.
      }
  | BPInternal
      { bpiEpoch    :: {-# UNPACK #-} !EpochId
        -- ^ Epoch version stamp at node creation.
      , bpiPivots   :: {-# UNPACK #-} !(SmallArray k)
        -- ^ Sorted separator pivot keys dividing child branches.
      , bpiChildren :: {-# UNPACK #-} !(SmallArray (BPlusNode k v))
        -- ^ Child node pointers (size is @sizeofSmallArray bpiPivots + 1@).
      }
  deriving (Eq, Show, Functor, Foldable)

-- | Persistent B+ tree key-value map.
data BPlusMap k v = BPlusMap
  { bpmSize :: {-# UNPACK #-} !Int
    -- ^ Total number of key-value associations stored in the map.
  , bpmRoot :: !(BPlusNode k v)
    -- ^ Root node of the B+ tree hierarchy.
  } deriving (Eq, Show, Functor, Foldable)

-- | Construct an empty 'BPlusMap'.
--
-- Running time: \(O(1)\).
emptyBPlus :: BPlusMap k v
emptyBPlus = BPlusMap 0 (BPLeaf 0 (smallArrayFromList []) (smallArrayFromList []))

-- | Binary search for key 'k' in a sorted 'SmallArray k'.
--
-- Returns 'Right' index if key is found, or 'Left' insertion slot if absent.
--
-- Running time: \(O(\log M)\) where \(M \le 16\).
searchKeys :: Ord k => SmallArray k -> k -> Either Int Int
searchKeys !arr !k = go 0 (sizeofSmallArray arr - 1)
  where
    go !lo !hi
      | lo > hi   = Left lo
      | otherwise =
          let !mid = (lo + hi) `div` 2
              !kv  = indexSmallArray arr mid
          in case compare k kv of
               EQ -> Right mid
               LT -> go lo (mid - 1)
               GT -> go (mid + 1) hi

-- | Determine child slot in 'BPInternal' routing node for search key 'k'.
findChildIdx :: Ord k => SmallArray k -> k -> Int
findChildIdx !pivots !k = go 0 (sizeofSmallArray pivots)
  where
    go !i !n
      | i >= n    = n
      | k < indexSmallArray pivots i = i
      | otherwise = go (i + 1) n

-- | Query a key in the 'BPlusMap'.
--
-- Running time: \(O(\log_M n)\) with cacheline-optimized binary search at each level.
lookupBPlus :: Ord k => k -> BPlusMap k v -> Maybe v
lookupBPlus !k (BPlusMap _ root) = go root
  where
    go (BPLeaf _ keys vals) =
      case searchKeys keys k of
        Right !idx -> Just (indexSmallArray vals idx)
        Left _     -> Nothing
    go (BPInternal _ pivots children) =
      let !cIdx = findChildIdx pivots k
      in go (indexSmallArray children cIdx)

-- | Pure persistent insertion into a 'BPlusMap' (stamped with 'EpochId' 0).
--
-- Running time: \(O(\log_M n)\).
insertBPlus :: Ord k => k -> v -> BPlusMap k v -> BPlusMap k v
insertBPlus !k v !m = insertBPlusEpoch 0 k v m

-- | Epoch-stamped insertion supporting \(O(1)\) transient epoch tracking in Penelope.
--
-- Running time: \(O(\log_M n)\).
insertBPlusEpoch :: Ord k => EpochId -> k -> v -> BPlusMap k v -> BPlusMap k v
insertBPlusEpoch !ep !k v (BPlusMap !sz root) =
  let (!added, !res) = insNode root
  in case res of
       Left !node' ->
         BPlusMap (if added then sz + 1 else sz) node'
       Right (!leftN, !pivotK, !rightN) ->
         let !newRoot = BPInternal ep (smallArrayFromList [pivotK]) (smallArrayFromList [leftN, rightN])
         in BPlusMap (if added then sz + 1 else sz) newRoot
  where
    insNode (BPLeaf _ keys vals) =
      case searchKeys keys k of
        Right !idx ->
          (False, Left (BPLeaf ep keys (replaceAt vals idx v)))
        Left !insIdx ->
          let !keys' = insertAt keys insIdx k
              !vals' = insertAt vals insIdx v
              !len'  = sizeofSmallArray keys'
          in if len' <= bPlusMaxCap
               then (True, Left (BPLeaf ep keys' vals'))
               else
                 let !mid   = len' `div` 2
                     !kL    = cloneSmallArray keys' 0 mid
                     !vL    = cloneSmallArray vals' 0 mid
                     !kR    = cloneSmallArray keys' mid (len' - mid)
                     !vR    = cloneSmallArray vals' mid (len' - mid)
                     !piv   = indexSmallArray kR 0
                 in (True, Right (BPLeaf ep kL vL, piv, BPLeaf ep kR vR))

    insNode (BPInternal _ pivots children) =
      let !cIdx = findChildIdx pivots k
          (!added, !childRes) = insNode (indexSmallArray children cIdx)
      in case childRes of
           Left !c' ->
             (added, Left (BPInternal ep pivots (replaceAt children cIdx c')))
           Right (!cL, !piv, !cR) ->
             let !pivots'   = insertAt pivots cIdx piv
                 !children' = insertAt (replaceAt children cIdx cL) (cIdx + 1) cR
                 !cLen      = sizeofSmallArray children'
             in if cLen <= bPlusMaxCap
                  then (added, Left (BPInternal ep pivots' children'))
                  else
                    let !mid    = cLen `div` 2
                        !upPiv  = indexSmallArray pivots' (mid - 1)
                        !pL     = cloneSmallArray pivots' 0 (mid - 1)
                        !pR     = cloneSmallArray pivots' mid (sizeofSmallArray pivots' - mid)
                        !chL    = cloneSmallArray children' 0 mid
                        !chR    = cloneSmallArray children' mid (cLen - mid)
                    in (added, Right (BPInternal ep pL chL, upPiv, BPInternal ep pR chR))

-- | Flatten all key-value entries into an ascending sorted list.
--
-- Running time: \(O(n)\).
toAscListBPlus :: BPlusMap k v -> [(k, v)]
toAscListBPlus (BPlusMap _ root) = go root []
  where
    go (BPLeaf _ keys vals) acc =
      let !n = sizeofSmallArray keys
          loop !i !a
            | i < 0     = a
            | otherwise = loop (i - 1) ((indexSmallArray keys i, indexSmallArray vals i) : a)
      in loop (n - 1) acc
    go (BPInternal _ _ children) acc =
      let !n = sizeofSmallArray children
          loop !i !a
            | i < 0     = a
            | otherwise = loop (i - 1) (go (indexSmallArray children i) a)
      in loop (n - 1) acc

-- | Construct a 'BPlusMap' from a list of key-value pairs.
--
-- Running time: \(O(n \log_M n)\).
fromListBPlus :: Ord k => [(k, v)] -> BPlusMap k v
fromListBPlus = foldl' (\acc (k, v) -> insertBPlus k v acc) emptyBPlus

-- | Insert element 'val' into 'SmallArray' at slot 'idx'.
insertAt :: SmallArray a -> Int -> a -> SmallArray a
insertAt !arr !idx val = runST $ do
  let !n = sizeofSmallArray arr
  m <- newSmallArray (n + 1) val
  copySmallArray m 0 arr 0 idx
  copySmallArray m (idx + 1) arr idx (n - idx)
  unsafeFreezeSmallArray m

-- | Replace element at slot 'idx' in 'SmallArray' with 'val'.
replaceAt :: SmallArray a -> Int -> a -> SmallArray a
replaceAt !arr !idx val = runST $ do
  let !n = sizeofSmallArray arr
  m <- thawSmallArray arr 0 n
  writeSmallArray m idx val
  unsafeFreezeSmallArray m