btree-concurrent 0.1.4 → 0.1.5

raw patch · 3 files changed

+81/−4 lines, 3 files

Files

• Data/BTree/UUID.hs +49/−0
• README.md +28/−3
• btree-concurrent.cabal +4/−1

@@ -0,0 +1,49 @@+{-# LANGUAGE DeriveDataTypeable+           , GeneralizedNewtypeDeriving+  #-}++module Data.BTree.UUID+       ( UUID+       , uuid+       )+       where+++import Data.Word+import Text.Printf+import Control.Concurrent+import Data.Typeable++import qualified Data.Char as C++import Data.Serialize++import System.IO.Unsafe+import qualified Data.ByteString.Char8      as B+import qualified Data.ByteString.Lazy.Char8 as BL+import qualified Data.ByteString.Base64     as B64++newtype UUID = UUID { unUUID :: B.ByteString }+             deriving (Ord, Eq)+++instance Serialize UUID where+  put = put . unUUID+  get = UUID `fmap` get++++instance Show UUID where+  show (UUID bs) = B.unpack $ B64.encode bs+++uuids :: MVar Int+uuids = unsafePerformIO $ newMVar 1+{-# NOINLINE uuids #-}+++uuid :: IO UUID+uuid = (UUID . encode) `fmap`+       (modifyMVar uuids $ \n -> return (n+1, n))++

@@ -1,7 +1,32 @@ btree-concurrent ================ -A backend agnostic, concurrent BTree written in Haskell. -Although the code does work, it is neither production-ready nor complete. See-the TODO.org file for more details on missing parts.+A backend agnostic, concurrent BTree with relaxed balance[1] written in Haskell using a mix of IO operations and pure STM.+++Although the code does work, it is neither production-ready nor complete.+++Features include:++* Caching: While nodes are periodically saved on persistent storage (e.g. disk) they are cached in-memory during operations.++* Live flushing: It is possible to save the current version of the tree to disk and run modifying operations at the same time. The nodes are updated buttom-up to ensure a valid tree in the case of a crash.++* Backend agnosticism: A simple API is used as an abstraction for the persistent storage.++* Verification: The test-suite uses QuickCheck to compare the trees behaviour to that of Data.Map.+++Deficients include:++* Too much memory usage. Nodes are not stored in a compact fashion and are constantly being serialized/deserialized.++* findMin and findMax are incomplete and may fail (see TODO for details).++* The implementation does not parallelize well.++++[1] B-trees with relaxed balance, K. S. Larsen & R. Fagerberg, Parallel Processing Symposium, 1995. Proceedings., 9th International

@@ -1,5 +1,5 @@ name:               btree-concurrent-version:            0.1.4+version:            0.1.5 homepage:           https://github.com/brinchj/btree-concurrent synopsis:           A backend agnostic, concurrent BTree description:        A backend agnostic, concurrent BTree@@ -68,6 +68,9 @@         Data.BTree.KVBackend.Class         Data.BTree.KVBackend.Files         Data.BTree.KVBackend.Util++    other-modules:+        Data.BTree.UUID       build-depends: