haskey-btree 0.2.0.0 → 0.2.0.1
raw patch · 4 files changed
+21/−1 lines, 4 filesPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
API changes (from Hackage documentation)
+ Data.BTree.Alloc.Class: deleteOverflowData :: AllocM m => OverflowId -> m ()
- Data.BTree.Alloc.Class: allocOverflow :: (AllocM m, Value val) => val -> m OverflowId
+ Data.BTree.Alloc.Class: allocOverflow :: (AllocM m, (Value val)) => val -> m OverflowId
- Data.BTree.Alloc.Class: readOverflow :: (AllocReaderM m, Value val) => OverflowId -> m val
+ Data.BTree.Alloc.Class: readOverflow :: (AllocReaderM m, (Value val)) => OverflowId -> m val
- Data.BTree.Impure: [Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node (S height) key val
+ Data.BTree.Impure: [Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node ( 'S height) key val
- Data.BTree.Impure: [Leaf] :: {leafItems :: LeafItems key val} -> Node Z key val
+ Data.BTree.Impure: [Leaf] :: {leafItems :: LeafItems key val} -> Node 'Z key val
- Data.BTree.Impure.Insert: splitIndex :: (AllocM m, Key key, Value val) => Height (S height) -> Index key (NodeId height key val) -> m (Index key (Node (S height) key val))
+ Data.BTree.Impure.Insert: splitIndex :: (AllocM m, Key key, Value val) => Height ( 'S height) -> Index key (NodeId height key val) -> m (Index key (Node ( 'S height) key val))
- Data.BTree.Impure.Insert: splitLeaf :: (AllocM m, Key key, Value val) => LeafItems key val -> m (Index key (Node Z key val))
+ Data.BTree.Impure.Insert: splitLeaf :: (AllocM m, Key key, Value val) => LeafItems key val -> m (Index key (Node 'Z key val))
- Data.BTree.Impure.NonEmpty: [Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node (S height) key val
+ Data.BTree.Impure.NonEmpty: [Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node ( 'S height) key val
- Data.BTree.Impure.NonEmpty: [Leaf] :: {leafItems :: LeafItems key val} -> Node Z key val
+ Data.BTree.Impure.NonEmpty: [Leaf] :: {leafItems :: LeafItems key val} -> Node 'Z key val
- Data.BTree.Impure.Structures: [Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node (S height) key val
+ Data.BTree.Impure.Structures: [Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node ( 'S height) key val
- Data.BTree.Impure.Structures: [Leaf] :: {leafItems :: LeafItems key val} -> Node Z key val
+ Data.BTree.Impure.Structures: [Leaf] :: {leafItems :: LeafItems key val} -> Node 'Z key val
- Data.BTree.Impure.Structures: castNode' :: forall n h k v. (Typeable k, Typeable v) => Height h -> n h k v -> Either (n Z k v) (n (S h) k v)
+ Data.BTree.Impure.Structures: castNode' :: forall n h k v. (Typeable k, Typeable v) => Height h -> n h k v -> Either (n 'Z k v) (n ( 'S h) k v)
- Data.BTree.Impure.Structures: getIndexNode :: (Binary key, Binary val) => Height (S n) -> Get (Node (S n) key val)
+ Data.BTree.Impure.Structures: getIndexNode :: (Binary key, Binary val) => Height ( 'S n) -> Get (Node ( 'S n) key val)
- Data.BTree.Impure.Structures: getLeafNode :: (Ord key, Binary key, Binary val) => Height Z -> Get (Node Z key val)
+ Data.BTree.Impure.Structures: getLeafNode :: (Ord key, Binary key, Binary val) => Height 'Z -> Get (Node 'Z key val)
- Data.BTree.Impure.Structures: putIndexNode :: (Binary key, Binary val) => Node (S n) key val -> Put
+ Data.BTree.Impure.Structures: putIndexNode :: (Binary key, Binary val) => Node ( 'S n) key val -> Put
- Data.BTree.Impure.Structures: putLeafNode :: (Binary key, Binary val) => Node Z key val -> Put
+ Data.BTree.Impure.Structures: putLeafNode :: (Binary key, Binary val) => Node 'Z key val -> Put
- Data.BTree.Primitives.Height: [USucc] :: Height height -> UHeight (S height)
+ Data.BTree.Primitives.Height: [USucc] :: Height height -> UHeight ( 'S height)
- Data.BTree.Primitives.Height: [UZero] :: UHeight Z
+ Data.BTree.Primitives.Height: [UZero] :: UHeight 'Z
- Data.BTree.Primitives.Height: decrHeight :: Height (S h) -> Height h
+ Data.BTree.Primitives.Height: decrHeight :: Height ( 'S h) -> Height h
- Data.BTree.Primitives.Height: incrHeight :: Height h -> Height (S h)
+ Data.BTree.Primitives.Height: incrHeight :: Height h -> Height ( 'S h)
- Data.BTree.Primitives.Height: zeroHeight :: Height Z
+ Data.BTree.Primitives.Height: zeroHeight :: Height 'Z
- Data.BTree.Primitives.Key: class (Ord k, Value k) => Key k where narrow = (,)
+ Data.BTree.Primitives.Key: class (Ord k, Value k) => Key k
- Data.BTree.Primitives.Value: class (Binary v, Show v, Typeable v) => Value v where fixedSize _ = Nothing
+ Data.BTree.Primitives.Value: class (Binary v, Show v, Typeable v) => Value v
- Data.BTree.Pure: [Idx] :: {idxChildren :: Index key (Node height key val)} -> Node (S height) key val
+ Data.BTree.Pure: [Idx] :: {idxChildren :: Index key (Node height key val)} -> Node ( 'S height) key val
- Data.BTree.Pure: [Leaf] :: {leafItems :: Map key val} -> Node Z key val
+ Data.BTree.Pure: [Leaf] :: {leafItems :: Map key val} -> Node 'Z key val
Files
- haskey-btree.cabal +1/−1
- src/Data/BTree/Alloc/Class.hs +3/−0
- src/Data/BTree/Alloc/Debug.hs +1/−0
- src/Data/BTree/Impure/Insert.hs +16/−0
haskey-btree.cabal view
@@ -1,5 +1,5 @@ name: haskey-btree-version: 0.2.0.0+version: 0.2.0.1 synopsis: B+-tree implementation in Haskell. description: This package provides two B+-tree implementations. The first one is a pure
src/Data/BTree/Alloc/Class.hs view
@@ -64,4 +64,7 @@ -- | Free an overflow page. freeOverflow :: OverflowId -> m () + -- | Force delete overflow data from disk.+ deleteOverflowData :: OverflowId -> m ()+ --------------------------------------------------------------------------------
src/Data/BTree/Alloc/Debug.hs view
@@ -85,3 +85,4 @@ return (0, c) freeOverflow _ = return ()+ deleteOverflowData _ = return ()
src/Data/BTree/Impure/Insert.hs view
@@ -1,5 +1,6 @@ {-# LANGUAGE DataKinds #-} {-# LANGUAGE GADTs #-}+{-# LANGUAGE LambdaCase #-} {-# LANGUAGE ScopedTypeVariables #-} -- | Algorithms related to inserting key-value pairs in an impure B+-tree. module Data.BTree.Impure.Insert where@@ -73,6 +74,11 @@ newChildren <- splitIndex hgt (putIdx ctx newChildIdx) traverse (allocNode hgt) newChildren Leaf items -> do+ case M.lookup k items of+ Nothing -> return ()+ Just (RawValue _) -> return ()+ Just (OverflowValue oid) -> freeOverflow oid+ v' <- toLeafValue v traverse (allocNode hgt) =<< splitLeaf (M.insert k v' items) @@ -93,8 +99,18 @@ newChildren <- splitIndex h newIndex traverse (allocNode h) newChildren Leaf items -> do+ mapM_ (\k -> freeOverwrittenOverflowId $ M.lookup k items) $ M.keys kvs kvs' <- toLeafItems kvs traverse (allocNode h) =<< splitLeaf (M.union kvs' items)+ where+ freeOverwrittenOverflowId :: (AllocM m)+ => Maybe (LeafValue v)+ -> m ()+ freeOverwrittenOverflowId = \case+ Nothing -> return ()+ Just (RawValue _) -> return ()+ Just (OverflowValue oid) -> freeOverflow oid+ --------------------------------------------------------------------------------