vcache-trie 0.1 → 0.1.1

raw patch · 2 files changed

+18/−18 lines, 2 files

Files

• hsrc_lib/Data/VCache/Trie/Type.hs +15/−14
• vcache-trie.cabal +3/−4

@@ -1,6 +1,12 @@ {-# LANGUAGE DeriveDataTypeable #-}  -- | The underlying structure for a Trie. +--+-- This is an internal module, but is exposed for now because I'm not+-- sure how to best generically target features such as structural +-- diffs. And we might eventually benefit from zippers, etc. After +-- experimenting and learning, I ask you to push the best generic +-- code into the vcache-trie package (i.e. send a pull request). module Data.VCache.Trie.Type     ( Trie(..)     , Node(..)@@ -32,6 +38,9 @@ -- larger values.  -- ++-- | A node should either accept a value or branch into at least two+-- children.  data Node a = Node     { trie_branch :: {-# UNPACK #-} !(Children a) -- arity 256; one byte from prefix     , trie_prefix :: {-# UNPACK #-} !ByteString   -- compact extended prefix@@ -43,20 +52,12 @@ type Child a = Maybe (VRef (Node a))  --- | A trie data structure with bytesting keys, above VCache.------ This trie uses a simple node structure, with a large branching--- factor (arity 256), and serializing large shared prefixes and the--- element values into the same node. The root of the trie is simply --- a `Maybe (VRef node)`, so is efficient for equality comparisons and--- serialization purposes. The basic 'Show' instance reports only the--- root reference address.------ The trie supports keys of arbitrary size, though very large keys may--- cause some performance degradation. Similarly, very large values may--- cause performance degradation since every lookup will load every value--- in the path. ---+-- | A trie data structure with bytestring keys, above VCache.+-- +-- A trie supports keys of arbitrary size, though very large keys may+-- cause performance degradation. Values are directly serialized into+-- nodes, so very large values should use indirection.+--  data Trie a = Trie      { trie_root  :: !(Child a)     , trie_space :: !VSpace

@@ -1,5 +1,5 @@ Name: vcache-trie-Version: 0.1+Version: 0.1.1 Synopsis: patricia tries modeled above VCache  Category: Database Description:@@ -10,8 +10,7 @@   shared prefixes or elements with a common prefix are likely to be   updated together.   .-  Currently, the implementation is specialized to a bytestring trie,-  and follows the interface of the bytestring-trie package.+  Currently, the implementation is specialized to a bytestring trie.    Author: David Barbour Maintainer: dmbarbour@gmail.com@@ -40,12 +39,12 @@    Exposed-Modules:     Data.VCache.Trie+    Data.VCache.Trie.Type    Other-Modules:      Strict     Ident-    Data.VCache.Trie.Type     -- Data.VCache.Trie.Mem     -- Data.VCache.Trie.MemType