radix-tree 1.0.0.1 → 1.0.0.2

raw patch · 10 files changed

+102/−47 lines, 10 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

CHANGELOG.md +9/−0
radix-tree.cabal +1/−1
src/Data/Patricia/Word/Lazy/Debug.hs +5/−5
src/Data/Patricia/Word/Strict/Debug.hs +5/−5
src/Data/RadixNTree/Word8/Lazy/Debug.hs +4/−4
src/Data/RadixNTree/Word8/Strict/Debug.hs +5/−5
src/Data/Zebra/Word/Debug.hs +7/−7
src/Data/Zebra/Word/Internal.hs +26/−6
src/Radix/Word/Debug.hs +19/−7
src/Radix/Word8/Debug.hs +21/−7

CHANGELOG.md view

@@ -1,3 +1,12 @@+## 1.0.0.0 -- September 2024++* Fixed `Data.Zebra.Word.fillRange`.+  Previously it produced malformed trees in certain cases.++## 1.0.0.1 -- May 2024++* Radix tree performance tweaks+ ## 1.0.0.0 -- April 2024  * Initial rewrite

radix-tree.cabal view

@@ -1,5 +1,5 @@ name:          radix-tree-version:       1.0.0.1+version:       1.0.0.2  category:      Data Structures synopsis:      Radix trees

src/Data/Patricia/Word/Lazy/Debug.hs view

@@ -58,15 +58,15 @@     go s q x =       case x of         Bin p l r-          | p == 0                 -> Invalid ZeroPrefix-          | not $ validBelow q s p -> Invalid $ PrefixBelow q p-          | otherwise              ->+          | p == 0                  -> Invalid ZeroPrefix+          | not $ validPrefix q s p -> Invalid $ PrefixBelow q p+          | otherwise               ->               case go L p l of                 Valid -> go R p r                 err   -> err          Tip k _-          | not $ validBelow q s k -> Invalid $ KeyBelow q k-          | otherwise              -> Valid+          | not $ validKey q s k -> Invalid $ KeyBelow q k+          | otherwise            -> Valid          Nil -> Invalid $ MalformedBin q

src/Data/Patricia/Word/Strict/Debug.hs view

@@ -58,15 +58,15 @@     go s q x =       case x of         Bin p l r-          | p == 0                 -> Invalid ZeroPrefix-          | not $ validBelow q s p -> Invalid $ PrefixBelow q p-          | otherwise              ->+          | p == 0                  -> Invalid ZeroPrefix+          | not $ validPrefix q s p -> Invalid $ PrefixBelow q p+          | otherwise               ->               case go L p l of                 Valid -> go R p r                 err   -> err          Tip k _-          | not $ validBelow q s k -> Invalid $ KeyBelow q k-          | otherwise              -> Valid+          | not $ validKey q s k -> Invalid $ KeyBelow q k+          | otherwise            -> Valid          Nil -> Invalid $ MalformedBin q

src/Data/RadixNTree/Word8/Lazy/Debug.hs view

@@ -90,16 +90,16 @@     goBin s b q x =       case x of         Bin p l r-          | p == 0                 -> Invalid (Build b) ZeroPrefix-          | not $ validBelow q s p -> Invalid (Build b) $ PrefixBelow q p+          | p == 0                  -> Invalid (Build b) ZeroPrefix+          | not $ validPrefix q s p -> Invalid (Build b) $ PrefixBelow q p           | otherwise              ->               case goBin L b p l of                 Valid -> goBin R b p r                 err   -> err          Tip arr mx dx-          | sizeofByteArray arr <= 0                    -> Invalid (Build b) EmptyByteArray-          | not $ validBelow q s (indexByteArray arr 0) ->+          | sizeofByteArray arr <= 0                  -> Invalid (Build b) EmptyByteArray+          | not $ validKey q s (indexByteArray arr 0) ->               Invalid (Build b) $ KeyBelow q (indexByteArray arr 0)            | Nothing <- mx, Tip _ _ _ <- dx     -> Invalid (Build b) UncompressedTip

src/Data/RadixNTree/Word8/Strict/Debug.hs view

@@ -90,16 +90,16 @@     goBin s b q x =       case x of         Bin p l r-          | p == 0                 -> Invalid (Build b) ZeroPrefix-          | not $ validBelow q s p -> Invalid (Build b) $ PrefixBelow q p-          | otherwise              ->+          | p == 0                  -> Invalid (Build b) ZeroPrefix+          | not $ validPrefix q s p -> Invalid (Build b) $ PrefixBelow q p+          | otherwise               ->               case goBin L b p l of                 Valid -> goBin R b p r                 err   -> err          Tip arr mx dx-          | sizeofByteArray arr <= 0                    -> Invalid (Build b) EmptyByteArray-          | not $ validBelow q s (indexByteArray arr 0) ->+          | sizeofByteArray arr <= 0                  -> Invalid (Build b) EmptyByteArray+          | not $ validKey q s (indexByteArray arr 0) ->               Invalid (Build b) $ KeyBelow q (indexByteArray arr 0)            | Nothing <- mx, Tip _ _ _ <- dx     -> Invalid (Build b) UncompressedTip

src/Data/Zebra/Word/Debug.hs view

@@ -95,9 +95,9 @@     go s q x cL =       case x of         Bin p l r-          | p == 0                 -> Break ZeroPrefix-          | not $ validBelow q s p -> Break $ PrefixBelow q p-          | otherwise              ->+          | p == 0                  -> Break ZeroPrefix+          | not $ validPrefix q s p -> Break $ PrefixBelow q p+          | otherwise               ->               case go L p l cL of                 Carry cR -> go R p r (Just cR)                 err      -> err@@ -108,7 +108,7 @@         Nil _ -> Break FoundNil      goTip s q k cL c-      | k == 0                 = Break ZeroKey-      | not $ validBelow q s k = Break $ KeyBelow q k-      | Just x <- cL, x == c   = Break $ NoSwitch c k-      | otherwise              = Carry c+      | k == 0               = Break ZeroKey+      | not $ validKey q s k = Break $ KeyBelow q k+      | Just x <- cL, x == c = Break $ NoSwitch c k+      | otherwise            = Carry c

src/Data/Zebra/Word/Internal.hs view

@@ -1963,17 +1963,37 @@      goTip k c t       | wR < k    = if c == x-                      then join k t pM binM+                      then if xor wL wR < xor wR k+                             then join k t pM binM+                             else let !(# o #) = invert x++                                      !mJ = branchingBit wR k++                                      !pJ = mask wR mJ .|. mJ++                                  in join+                                       wL (tip wL x)+                                       pJ (Bin pJ (tip wR o) t)                       else t        | k < wL    = if c == x                       then t-                      else if k == 0-                             then binM-                             else join k t pM binM+                      else if xor k wL > xor wL wR+                             then join k t pM binM+                             else let !mJ = branchingBit k wL -      | c == x    = tip wL c-      | otherwise = tip wR c+                                      !pJ = mask k mJ .|. mJ++                                  in join+                                       pJ (Bin pJ t (tip wL x))+                                       wR (tip wR c)++      | otherwise =+          let w = if c == x+                    then wL+                    else wR++          in tip w c

src/Radix/Word/Debug.hs view

@@ -1,6 +1,8 @@ module Radix.Word.Debug   ( S (..)-  , validBelow++  , validPrefix+  , validKey   ) where  import           Radix.Word.Foundation@@ -14,10 +16,20 @@        | R -- ^ Right. Masked bit of the prefix above this node must be @1@.          deriving Show +++-- | Check whether the prefix below aligns with the side the branch is on.+validPrefix :: Prefix -> S -> Prefix -> Bool+validPrefix p s o =+  let low = p .&. negate p+  in case s of+       L -> o < p && p - o < low+       R -> p < o && o - p < low+ -- | Check whether the key below aligns with the side the branch is on.-validBelow :: Prefix -> S -> Key -> Bool-validBelow p1 s p2 =-  let q = p2 .&. (p1 .&. negate p1)-  in not (beyond p1 p2) && case s of-                             L -> q == 0-                             R -> q /= 0+validKey :: Prefix -> S -> Key -> Bool+validKey p s k =+  let low = p .&. negate p+  in case s of+       L -> k <  p && p - k <= low+       R -> p <= k && k - p <  low

src/Radix/Word8/Debug.hs view

@@ -1,6 +1,8 @@ module Radix.Word8.Debug   ( S (..)-  , validBelow++  , validPrefix+  , validKey   ) where  import           Radix.Word8.Foundation@@ -14,10 +16,22 @@        | R -- ^ Right. Masked bit of the prefix above this node must be @1@.          deriving Show +++-- | Check whether the prefix below aligns with the side the branch is on.+validPrefix :: Prefix -> S -> Prefix -> Bool+validPrefix p s o =+  let low = p .&. negate p+  in case s of+       L -> o < p && p - o < low+       R -> p < o && o - p < low+++ -- | Check whether the key below aligns with the side the branch is on.-validBelow :: Prefix -> S -> Key -> Bool-validBelow p1 s p2 =-  let q = p2 .&. (p1 .&. negate p1)-  in not (beyond p1 p2) && case s of-                             L -> q == 0-                             R -> q /= 0+validKey :: Prefix -> S -> Key -> Bool+validKey p s k =+  let low = p .&. negate p+  in case s of+       L -> k <  p && p - k <= low+       R -> p <= k && k - p <  low