vcache-trie 0.1.1 → 0.1.2

raw patch · 3 files changed

+24/−9 lines, 3 files

Files

• hsrc_lib/Data/VCache/Trie.hs +18/−6
• hsrc_lib/Data/VCache/Trie/Type.hs +1/−1
• vcache-trie.cabal +5/−2

@@ -7,6 +7,7 @@     , null, size     , lookup, lookup', lookupc     , prefixKeys, lookupPrefix, deletePrefix+    , lookupPrefixNode     , insert, delete, adjust     , insertList, deleteList @@ -127,14 +128,25 @@      -- | Obtain a trie rooted at a given prefix. ----- This operation may need to allocate a new node.+-- This operation may need to allocate in VCache, e.g. to delete+-- some fraction of the requested prefix. This isn't optimal for+-- performance. lookupPrefix :: (VCacheable a) => ByteString -> Trie a -> Trie a lookupPrefix k tr =-    let child = _lookupP k (trie_root tr) in-    Trie child (trie_space tr)+    let node = lookupPrefixNode k tr in+    let vc = trie_space tr in+    let child = vref vc <$> node in+    Trie child vc -_lookupP :: (VCacheable a) => ByteString -> Child a -> Child a-_lookupP key c | B.null key = c -- stop on exact node+-- | Obtain a trie node rooted at a given prefix, if any content+-- exists at this prefix. This operation allows some performance +-- benefits compared to 'lookupPrefix' because it never allocates+-- at the VCache layer. +lookupPrefixNode :: (VCacheable a) => ByteString -> Trie a -> Maybe (Node a)+lookupPrefixNode k = _lookupP k . trie_root++_lookupP :: (VCacheable a) => ByteString -> Child a -> Maybe (Node a)+_lookupP key c | B.null key = deref' <$> c -- stop on exact node _lookupP _ Nothing = Nothing --  _lookupP key (Just c) =      let tn = deref' c in@@ -147,7 +159,7 @@             assert (s == k) $             let pre' = B.drop k pre in -- trim key from prefix             let tn' = tn { trie_prefix = pre' } in-            Just $! vref (vref_space c) tn' -- allocate new node+            Just $! tn' -- allocate new node        else if (s < p) then Nothing else              assert (s == p) $             let key' = B.drop (p+1) key in

@@ -68,7 +68,7 @@     put (Node c p v) = putChildren c >> put p >> put v instance (VCacheable a) => VCacheable (Trie a) where     get = Trie <$> get <*> getVSpace-    put = put . trie_root+    put (Trie r vc) = put r >> put vc instance Show (Trie a) where     showsPrec _ t = showString "Trie#" . shows (unsafeTrieAddr t) 

@@ -1,5 +1,5 @@ Name: vcache-trie-Version: 0.1.1+Version: 0.1.2 Synopsis: patricia tries modeled above VCache  Category: Database Description:@@ -8,7 +8,7 @@   structures be modeled above it. The trie is useful for modeling key   value databases or abstract virtual filesystems, where keys have    shared prefixes or elements with a common prefix are likely to be-  updated together.+  updated together.    .   Currently, the implementation is specialized to a bytestring trie.   @@ -40,6 +40,9 @@   Exposed-Modules:     Data.VCache.Trie     Data.VCache.Trie.Type++    -- Data.VCache.Trie.Monoid+    -- Data.VCache.Trie.Monoid.Type    Other-Modules: